Постановка и основные свойства транспортной задачи (стр. 7 из 7)
.
Возможен один из двух случаев: 1) 
, 2) 
. В первом случае 
-ю строку Сk отмечают знаком '+' справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем Сk называется такой элемент 
, для которого 
). Если таким существенным нулем оказался элемент 
, а сам столбец – выделен, то знак выделения '+' над столбцом уничтожают, а сам этот нуль отмечают звездочкой.
Затем просматривают -й столбец и отыскивают в нем нуль (нули), расположенные в отличных от 
-й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки.
Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:
1) найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке 
. Тогда отметив его штрихом, переходим ко второму этапу;
2) все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка 
. Тогда переходим к третьему этапу.
Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.
Второй этап. Состоит в построении цепочки из нулей матрицы Сk, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Хk+1
Пусть для некоторого нуля со штрихом матрицы Сk, расположенного, например, в позиции ( 
), невязка строки 
. Начиная с этого элемента 
, строят цепочку из отмеченных нулей матрицы Сk: двигаясь по столбцу 
, выбирают нуль со звездочкой 
, далее двигаясь от него по строке 
, находят нуль со штрихом 
. Потом движутся от него по столбцу 2 к следующему нулю со звездочкой и т.д. Такой последовательный переход от 0' к 0* по столбцу и от 0* к 0' по строке осуществляют до тех пор, пока это возможно.
Можно доказать, что процесс построения цепочки однозначный и законченный, цепочка не имеет циклов, начинается и заканчивается нулем со штрихом.
После того как цепочка вида
построена, осуществляют переход к матрице 
от матрицы Хk по формулам
(1.3.7)
где 
(1.3.8)
Таким образом, 
-минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.
Вычисляем невязку для 
На этом (k+1) – я итерация заканчивается.
Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы Сk к эквивалентной матрице С′k, в которой появляется новый невыделенный нуль (или нули). Пусть 
, где минимум выбирают из всех невыделенных элементов матрицы Сk. Тогда из всех элементов невыделенных строк матрицы Сk вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули.
Далее переходят к первому этапу, и в зависимости от его результата либо переходят ко второму этапу, либо снова возвращаются к третьему этапу. За конечное число повторов пары этапов третий – первый обязательно перейдем ко второму этапу.
Если после выполнения второго этапа 
то Хk+1 – оптимальный план. В противном случае переходим к (k+2) итерации.
Отметим некоторые важные особенности венгерского метода.
Поскольку данный метод в отличие от метода потенциалов не использует опорных планов, то явление вырожденности плана для него отсутствует. Это устраняет возможность зацикливания, связанного с вырожденностью планов Т-задачи, которая облегчает программирование метода и его реализацию на ЭВМ.
Метод позволяет на каждой итерации по величине невязки 
оценить близость Хk к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций Nост:
. (1.3.9)
Эта формула справедлива для целочисленных значений всех переменных 
и 
.
Список литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа.
2. Вентцель Е.С. Исследование операций. – М.: Наука, 1976.
3. Горелик В.А., Ушаков И.А. Исследование операций. – М: Машиностроение, 1986. – 286 с.
4. Давыдов Э.Т. Исследование операций: Учебное пособие для студентов вузов. – М.: Высшая школа, 1990. – 383 с.
5. Ермолаев Ю.М. Математические методы исследования операций. – К.: Наука, 1979.
6. Кузнецов Ю.Н. Математическое программирование. – М.: Наука, 1976.
7. Минц М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990.
8. Таха Х. Введение в исследование операций. – м.: Мир, 1985.
9. Толбатов Ю.А. Эконометрика в Excel. – К.: Четверта хвиля, 1997.