Постановка и основные свойства транспортной задачи (стр. 5 из 7)
на этом один шаг метода заканчивается.
2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент
причем
, (1.27)
где
(1.28)
Если 
, то заполняем нулями строку 
, начиная с ( 
+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 к Хk+1 значение целевой функции не изменяется, а в базис вводится элемент 
, для которого перевозка станет равной .
Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6)
Проверим условие баланса 
Предварительный этап. Методом минимального элемента строим начальный базисный план Х0 (Табл. 5)
Таблица 5
| C = | ai bj | 4 | 6 | 8 | 6 |
| 6 | 2(5) | 2(4) | 3(6) | 4(11) | |
| 8 | 6(12) | 4(10) | 3(9) | 1(3) | |
| 10 | 1(1) | 2(6) | 2(7) | 1(2) |
Так как m + n – 1 = 6; k = 4, то план х0 – вырожденный; l = m+ n -1 – k = 2.
Два нулевых элемента Х0 делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов 
, 
и положим их равными .
Схема перевозок для плана Х0 показана на рис. 6.
 |
Рис. 6.
Для вычисления предварительных потенциалов выберем начальный пункт А1 и допустим, что 
. Потенциалы всех остальных пунктов вычисляем по формулам
, 
Для проверки оптимальности плана х0 строим матрицу С1, элементы которой вычисляем по соотношению
Так как в матрице С1 элемент С23 = – 3 < 0, то план Х0 – неоптимальный.
Первая итерация. Второй этап.
 |  |  |  |  | | ||||||
*  | 6* | 0 | 0 | | 6 | 0 | 0 | ||||
| X0 = |  |  0* | * | 8 | 0+ |  | X1 = | 0 | 0 | 6 | |
| 4 | 0 | 0 | 6* | 1 = | 4 | 0 | 0 | 6 | |||
 |
