Для контроля за работой космической ракеты используются четыре видадатчиков

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 70 + 90 + 60 = 220 ∑b = 20 + 40 + 50 + 40 = 150 Условие баланса не соблюдается. Запасов больше потребностей. Следовательно, модель транспортной задачи является открытой. Добавим фиктивного потребителя B5 с потребностями 220-150=70. Занесем данные в распределительную таблицу.
Для составления опорного плана перевозок методом «минимального элемента» запишем распределительную таблицу (табл. 1).
Таблица 1
B1
B2
B3
B4
B5
A1
1
1
5
3
  0 70
A2
5
2
5
5
0 90
A3
3
4
1
2
0 60
20 40 50 40 70 220
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Наименьший элемент равен c15=0. Для этого элемента запасы равны 70, потребности 70. Поскольку минимальным является 70, то вычитаем его. Таким образом, т. е. «поставка» для клетки (1;5) x15=70 и столбец B5 закрыт и строка A1 закрыта.
Следующий наименьший доступный элемент равен c33=1. Для этого элемента запасы равны 60, потребности 50. Поскольку минимальным является 50, то вычитаем его. Таким образом, т. е. «поставка» для клетки (3;3) x33=50 и столбец B3 закрыт.
Следующий наименьший доступный элемент равен c34=2. Для этого элемента запасы равны 10, потребности 40. Поскольку минимальным является 10, то вычитаем его . Таким образом, т. е. «поставка» для клетки (3;4) x34=10 и строка A3 закрыта.
Следующий наименьший доступный элемент равен c22=2. Для этого элемента запасы равны 90, потребности 40. Поскольку минимальным является 40, то вычитаем его. Таким образом, т. е. «поставка» для клетки (2;2) x22=40 и столбец B2 закрыт.
Следующий наименьший доступный элемент равен c24=5. Для этого элемента запасы равны 30, потребности 30. Поскольку минимальным является 30, то вычитаем его. Таким образом, т. е. «поставка» для клетки (2;4) x24=30 и столбец B4 закрыт, строка A2 тоже.
В результате получен первый опорный план (табл.2), который является допустимым, так как все датчики распределены по самописцам, а план соответствует системе ограничений транспортной задачи.
Таблица 2
B1
B2
B3
B4
B5
A1
1
0 1
5
3
  0
70 70
A2
5
20 2
40 5
5
30 0 90
A3
3
4
1
50 2
10 0 60
20 40 50 40 70 220
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. Необходимо добавить нулевую поставку x11=0. Значение целевой функции для этого опорного плана равно: F(x) = 0*1 + 20*5 + 40*2 + 30*5 + 70*0 + 50*1 + 10*2 = 400 ед.времениПроверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 1; 0 + v1 = 1; v1 = 1 u1 + v5 = 0; 0 + v5 = 0; v5 = 0 u2 + v1 = 5; 1 + u2 = 5; u2 = 4 u2 + v2 = 2; 4 + v2 = 2; v2 = -2 u2 + v4 = 5; 4 + v4 = 5; v4 = 1 u3 + v4 = 2; 1 + u3 = 2; u3 = 1 u3 + v3 = 1; 1 + v3 = 1; v3 = 0
Добавим предварительные потенциалы на план (табл.3)
Таблица 3
v1 = 1
B1
v2 = -2
B2
v3 = 0
B3
v4 = 1
B4
v5 = 0
B5
u1=0
A1
1 1
0 -2 1
0 5
1 5
  0 0
70 70
u2 = 4
A2
5 5
20 2 2
40 4 5
5 5
30 4 0 90
u3 = 1
A3
2 3
-1 4
1 1
50 2 2
10 1 0
60
20 40 50 40 70 220
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;5): 0 + 4 > 0; ∆25 = 0 - 4 = -4 < 0 Выбираем минимальную оценку свободной клетки (1;5): -4 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 4
v1 = 1
B1
v2 = -2
B2
v3 = 0
B3
v4 = 1
B4
v5 = 0
B5
u1=0
A1
1 1
0[+] -2 1
0 5
-1 5
  0 0
70[-] 70
u2 = 4
A2
5 5
20[-] 2 2
40 4 5
3 5
30 4 0
[+] 90
u3 = 1
A3
2 3
-1 4
1 1
50 2 2
10 1 0
60
20 40 50 40 70 220
Цикл приведен в таблице 4 (2,5 → 1,5 → 1,1 → 2,1 → 2,5)