На складах временного хранения трех таможенных пропускных пунктов Брусничное, Торфяновка и Светогорск скопились элитные

На складах временного хранения трех таможенных пропускных пунктов Брусничное, Торфяновка и Светогорск скопились элитные машины фирм BMW, которые требуется переместить в магазины СПб: "Олимп", "BMW-автодом", "Евросиб". Предложить план перевозок, при котором суммарные транспортные затраты будут наименьшими. (найти опорное решение двумя способами, проверить каждое решение на оптимальность и, если решение не является оптимальным, методом потенциалов найти оптимальное решение) Брусничное Торфя- новка Свето- горск 240 160 170 Олимп 50 8 8 8 BMW-автодом 300 7 6 2 Евросиб 210 4 7 6

Проверим условие разрешимости транспортной задачи:
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, стоящих в минусовых клетках