В m заводах имеется однородный груз продукции в количествах . Этот груз нужно перевести

В m заводах имеется однородный груз продукции в количествах . Этот груз нужно перевести n потребителям, потребности которых равны . Стоимость перевозки единицы груза из i – го завода j – ому потребителю равна (таблица 3). Требуется составить план перевозки груза с заводов потребителям, при котором суммарные расходы на перевозку будут минимальными. Заводы Потребители Запас продукции, ед. В1 В2 В3 В4 А1 А2 А3 Потребность в продукции, ед. Исходные данные по вариантам заданий указаны в таблице 600 с23 3 400 с24 9 700 с31 4 400 с32 8 300 с33 6 800 с34 2 200 4 40 6 8 5 7

Bj
ai 200 300 800 200
600 4 40 6 8
400 5 7 3 9
700 4 8 6 2
Проверим условие разрешимости транспортной задачи:
i=13ai=600+400+700=1700
j=15bj=200+300+800+200=1500
Т.к. ai≠bj, то имеем ТЗ открытого типа. Чтобы получить закрытую модель, введем дополнительный (фиктивный) столбец потребителей, равный 200 (1700-1500).
Найдем исходный опорный план методом северо-западного угла. Заполнять начинаем с клетки (1;1):
200 300 800 200 200
600 200 4 300 40 100 6
8
0
400
5
7 400 3
9
0
700
4
8 300 6 200 2 200 0
Т.о. мы получили первый опорный план:
X0=20030000100 0 0400 0 00 0300 200200
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=7 шт., т.е. заполненных клеток должно быть 7 штук. В таблице это выполняется, значит, исходный опорный план найден верно

. Найдем значение целевой функции
F(x) = 4*200 + 40*300 + 6*100 + 3*400 + 6*300 + 2*200 + 0*200 = 16800
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=4; V1=4U1+V2=40; V2=40U1+V3=6; V3=6U2+V3=3; U2=-3U3+V3=6; U3=0U3+V4=2; V4=2U3+V5=0; V5=0
Найдем оценки свободных клеток (клеток с прочерками) по формуле: ij Ui Vj Cij:
14=0+2-8=-615=0+0-0=021=-3+4-5=-422=-3+40-7=30
24=-3+2-9=-1025=-3+0-0=-331=0+4-4=032=0+40-8=32
Т.к. среди оценок есть положительные, то план X0 не оптимальный. Строим цикл пересчета для свободной клетки (3;2): 3;23;31;31;2