На складах временного хранения трех таможенных пропускных пунктов Брусничное
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
На складах временного хранения трех таможенных пропускных пунктов Брусничное, Торфяновка и Светогорск скопились элитные машины фирм 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, стоящих в минусовых клетках
Задать вопрос
на новый заказ в Автор24.
