Решение задач транспортного типа методами северо-западного угла, минимального элемента, двойного предпочтения, потенциалов и венгерским методом

Методы решения задач транспортного типа

Задание

Решить методами северо-западного угла, минимального элемента, двойного предпочтения, потенциалов и венгерским методом.

Метод северо-западного угла

Начиная  с левого верхнего угла, берем максимально возможное значение элемента  и двигаемся по диагонали, заполняя ячейки.

В верхнюю левую ячейку ставим максимально возможное значение элемента – 6. Обнуляем оставшиеся элементы столбца, т. к. их заполнить уже нельзя. Во вторую ячейку первой строки ставим максимально возможное значение – 6 и обнуляем оставшиеся элементы столбца . В следующую ячейку строки ставим максимально возможное значение – 4 и обнуляем оставшиеся элементы строки. В третью ячейку второй строки ставим – 9 и обнуляем оставшиеся элементы столбца. В четвертую ячейку втрой строки ставим – 6 и обнуляем оставшиеся элементы строки. В четвертую ячейку третьей строки ставим – 14 и обнуляем оставшиеся элементы строки. В пятую ячейку четвертой строки ставим максимальное значение =15  Считаем Z.

Z = 6*30+6*2+4*5+9*9+6*5+14*6+15*8=527

Метод минимального элемента

Выбираем в строках минимальные элементы и ставим в них максимально возможные значения. В ячейки отмеченные «*» ставим максимально возможные значения, отдавая предпочтение минимальным стоимостям. Обнуляем ячейки в заполненных строках и столбцах. Оставшиеся ячейки заполняем максимально возможными значения, отдавая предпочтение минимальным стоимостям и обнуляем оставшиеся ячейки.

 Считаем Z.

Z=6*2+10*15+6*5+9*5+11*6+3*26+13*4+2*8=449

Метод двойного предпочтения

Выбираем в строках и столбцах минимальные элементы и отмечаем их «*». В ячейки отмеченные двумя «*» ставим максимально возможные значения. В ячейки с одной «*» ставим максимально возможные значения, отдавая предпочтение минимальным стоимостям или обнуляем их, если строка или столбец уже заполнены.

Обнуляем заполненные строки и столбцы.

Оставшиеся ячейки заполняем максимально возможными значения, отдавая предпочтение минимальным стоимостям и обнуляем оставшиеся ячейки.

Считаем Z.

Z=6*2+10*15+6*5+9*5+11*6+3*26+13*4+2*8=449

Метод потенциалов

Расставляем значения элементов по методу северо-западного угла. Находим потенциалы для каждого столбца и строки по правилу: C_ij=u_i+v_j.

U₁=0, т. к. первая строка наиболее заполнена. Рассматриваем незаполненные ячейки и отмечаем их, если C_ij < u_i+v_j.

Рассматриваем незаполненные ячейки и отмечаем их в соответствии с правилом:

C_ij ≥ u_i+v_j.

Переносим 6 элементов в соответствии с направлением стрелок, для оптимизации заполнения таблицы. И рассчитываем новые потенциалы. Рассматриваем незаполненные ячейки и отмечаем их, если C_ij < u_i+v_j.