На складах временного хранения трех таможенных пропускных пунктов Брусничное

Проверим условие разрешимости транспортной задачи:
j=13aj=50+300+210=560
i=13bi=240+160+170=570
Т.к. ai≠bj, то имеем ТЗ открытого типа. Чтобы получить закрытую модель, введем дополнительную (фиктивную) строку магазинов, равную 10 (570-560).
Найдем исходный опорный план методом наименьшей стоимости:
Потребители Поставщики
240 160 170
50 30 8 20 8
8
300
7 130 6 170 2
210 210 4
7
6
10
0 10 0
0
Т.о. мы получили первый опорный план: X0=302000130170210001000
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=6 шт., т.е. заполненных клеток должно быть 6 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 8*30 + 8*20 + 6*130 + 2*170 + 4*210 + 0*10 = 2360
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=8; V1=8U3+V1=4; U3=-4U1+V2=8; V2=8U2+V2=6; U2=-2U2+V3=2; V3=4U4+V2=0; U4=-8
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
13=0+4-8=-421=-2+8-7=-132=-4+8-7=-3
33=-4+4-6=-641=-8+8-0=043=-8+4-0=-4
Т.к. все оценки ij 0, то план оптимальный.
F(x) = 8*30 + 8*20 + 6*130 + 2*170 + 4*210 + 0*10 = 2360
Найдем исходный опорный план методом северо-западного угла:
Потребители Поставщики
240 160 170
50 50 8
8
8
300 190 7 110 6
2
210
4 50 7 160 6
10
0
0 10 0
Т.о . мы получили первый опорный план: X0=500019011000050016010
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=6 шт., т.е. заполненных клеток должно быть 6 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 8*50 + 7*190 + 6*110 + 7*50 + 6*160 + 0*10 = 3700
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=8; V1=8U2+V1=7; U2=-1U2+V2=6; V2=7U3+V2=7; U3=0U3+V3=6; V3=6U4+V3=0; U4=-6
Найдем оценки свободных клеток (клеток с прочерками) по формуле: ij Ui Vj Cij:
12=0+7-8=-113=0+6-8=-223=-1+6-2=3
31=0+8-4=441=-6+8-0=242=-6+7-0=1
Т.к. среди оценок есть положительные, то план X0 не оптимальный. Строим цикл пересчета для свободной клетки (3;1): 3;1 3;2 2;2 2;1. Определим значение Q; Q min190, 50 50
Потребители Поставщики
240 160 170
50 50 8
8
8
300 313863868220190 7 110 6
2
[-Q]
[+Q]
210
4 50 7 160 6
[+Q]
[-Q]
10
0
0 10 0
Прибавляем 50 к объемам, стоящим в плюсовых клетках, и вычитаем 50 из xij, стоящих в минусовых клетках