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

Проверим условие разрешимости транспортной задачи:
j=13aj=130+20+130=280
i=13bi=160+50+100=310
Т.к. ai≠bj, то имеем ТЗ открытого типа. Чтобы получить закрытую модель, введем дополнительную (фиктивную) строку магазинов, равную 30 (310-280).
Найдем исходный опорный план методом наименьшей стоимости:
Потребители Поставщики
160 50 100
130 30 4
6 100 2
20
8 20 3
5
130 130 4
8
4
30 0 0 30 0
0
Т.о. мы получили первый опорный план: X0=3001000200130003000
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=6 шт., т.е. заполненных клеток должно быть 6 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 4*30 + 2*100 + 3*20 + 4*130 + 0*30 = 900
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=4; V1=4U1+V3=2; V3=2U3+V1=4; U3=0U4+V1=0; U4=-4U4+V2=0; V2=4U2+V2=3; U2=-1
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
12=0+4-6=-221=-1+4-8=-523=-1+2-5=-4
32=0+4-8=-433=0+2-4=-243=-4+2-0=-2
Т.к. все оценки ij 0, то план оптимальный.
F(x) = 4*30 + 2*100 + 3*20 + 4*130 + 0*30 = 900
Найдем исходный опорный план методом северо-западного угла:
Потребители Поставщики
160 50 100
130 130 4
6
2
20 20 8
3
5
130 10 4 50 8 70 4
30
0
0 30 0
Т.о . мы получили первый опорный план: X0=1300020001005007030
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=6 шт., т.е. заполненных клеток должно быть 6 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 4*130 + 8*20 + 4*10 + 8*50 + 4*70 + 0*30 = 1400
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=4; V1=4U2+V1=8; U2=4U3+V1=4; U3=0U3+V2=8; V2=8U3+V3=4; V3=4U4+V3=0; U4=-4
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
12=0+8-6=213=0+4-2=222=4+8-3=9
23=4+4-5=341=-4+4-0=042=-4+8-0=4
Т.к. среди оценок есть положительные, то план X0 не оптимальный. Строим цикл пересчета для свободной клетки (2;2): 2;2 2;1 3;1 3;2. Определим значение Q; Q min20, 50 20
Потребители Поставщики
160 50 100
130 130 4
6
2
20 32702510477520 8
3
5
[-Q]
[+Q]
130 10 4 50 8 70 4
[+Q]
[-Q]
30
0
0 30 0
Прибавляем 20 к объемам, стоящим в плюсовых клетках, и вычитаем 20 из xij, стоящих в минусовых клетках