Контрольная работа: Постановка и основные свойства транспортной задачи
Если 
, то заполняем нулями строку 
, начиная с (
+1) – го элемента. В противном случае заполняем нулями столбец 
, начиная с элемента ( +1). Если 
, то заполняем нулями остаток строки и столбца . Далее вычисляем 
. На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.
Метод минимального элемента
Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С =
. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.
Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х 0 .
Пусть элементом с минимальным порядковым номером оказался 
. Возможные три случая: а) если 
, то оставшуюся часть 
-й строки заполняем нулями; б) если 
, то оставшуюся часть 
-го столбца заполняем нулями; в) если 
, то оставшуюся часть -й строки и -го столбца заполняем нулями.
Дале этот процесс повторяют с незаполненной частью матрицы Х 1 .
Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи.
Таблица. 3.
| Ai \ Bj | 1 | 2 | 3 | 4 | Bj / ai |
| 1 | 7(10) | 8(11) | 5(7) | 3(5) | 11 |
| 2 | 2(3) | 4(4) | 5(8) | 9(12) | 11 |
| 3 | 6(9) | 3(4) | 1(1) | 2(2) | 8 |
| Ai / bj | 5 | 9 | 9 | 7 | bj \ ai |
Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 3.4).
Соответствующее значение целевой функции равно
3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92
Таблица 4
| Х0 |  |  |  | |||||
| 0 | 3 | 1 | 7 | 11 | 4 | 3 | 0 | |
| 5 | 6 | 0 | 0 | 11 | 6 | 0 | ||
| 0 | 0 | 8 | 0 | 8 | 0 | |||
 | 5 | 9 | 9 | 7 | ||||
 | 0 | 3 | 1 | 0 | ||||
 | 0 | 0 | ||||||
Решение транспортной задачи при вырожденном опорном плане
Опорный план называется вырожденным, если число его ненулевых перевозок k меньше ранга матрицы ограничений. В процессе построения начального плана или при его улучшении очередной план может оказаться вырожденным.
Рассмотрим два случая.
1. Вырожденный план является начальным Х 0 . Тогда выбирают некоторые нулевые элементы матрицы Х 0 в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется 
. Далее данные элементы заменяют на 
(где 
– произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Х k вместо пишут нули.
2. Вырожденный план получается при построении плана Х k+1 на базе Х k , если цепочка в плане Х k содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Х k+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге 
, то при переходе от Х k к Х