2015-04-06
1885
В трех хранилищах горючего ежедневно хранится 175. 125, 140 тонн бензина. Этот бензин ежедневно получают 4 заправочные станции в количестве 180, 110, 60, 40.
Стоимости перевозок:
9 7 5 3
1 2 4 6
8 10 12 1
Составить такой план распределения горючего, при котором затраты на транспортировку будут минимальными.
1) Определим модель задачи:
åаi ≠ åвjÞ модель открытая, поэтому добавим фиктивного получателя груза (50 ед.).
2) Распределим груз по методу min элемента
| V1=5 | V2=7 | V3=5 | V4=-2 | V5=0 | ||
| bi ai | ||||||
| U1=0 | 9 | 7 | 5 | 3 | 0 50 | |
| U2=-4 | 1 125 | 2 | 4 | 6 | 0 | |
| U3=3 | 8 | 10 45 | 12 | 1 40 | 0 |
3)Определим первоначальную стоимость перевозки груза:
Z1= 65*7+60*5+125*1 +55*8+45*10+40*1=1810
4)Определим потенциал для занятых клеток, исходя из условия Cij=Ui+Vj
5)Определим оценки свободных клеток ∆ ij по формуле:
∆ij =Cij-(Ui+Vj)
| ∆11=4 ∆14=5 ∆22=-1 ∆23=3 ∆24=12 ∆25=4 ∆33=4 ∆35=-3 |
Т.к. среди оценок свободных клеток есть отрицательные, то решение не оптимально. Перейдем к другой итерации.
6) Построим цикл по l.
l=min (45, 50)=45
| V1=8 | V2=7 | V3=5 | V4=1 | V4=0 | ||
| bi ai | ||||||
| U1=0 | 9 | 7 110 | 5 | 3 | 0 | |
| U2=-7 | 1 125 | 2 | 4 | 6 | 0 | |
| U3=0 | 8 55 | 10 | 12 | 1 40 | 0 45 |
7)Определим стоимость перевозки груза:
Z2= 1810 - /-3/*45 = 1675
Повторяя алгоритм метода потенциалов, определим потенциал для занятых клеток Ui и Vi,, а затем оценки свободных клеток.
| ∆11=1 ∆14=2 ∆15=0 ∆22=2 ∆23=6 ∆24=12 ∆25=7 ∆32=3 ∆33=7 |
Т.к. среди оценок свободных клеток нет отрицательных, то решение оптимально.
Дадим экономическую интерпретацию задачи.
В результате решения получим оптимальный план распределения горючего, при котором затраты на транспортировку будут минимальными в размере 1675 у.е..
В этом случае горючее будет распределено следующим образом:
Горючее из первого хранилища отправляется на вторую и третью заправочные станции в количестве 110, 60 единиц соответственно и 5 единиц груза остается недораспределенным, т.к. этот груз не был затребован.
Горючее из второго хранилища в полном объеме 125 единиц отправляется на первую заправочную станцию.
Горючее из третьего хранилища отправляется на первую и четвертую заправочные станции в количестве 55 и 40 единиц соответственно, а 45 единиц груза остается недораспределенным.
Контрольные вопросы и упражнения
1. Дать определение задачи транспортного типа.
2. Какие модели задач транспортного типа существуют?
3. Как перейти от открытой модели к закрытой?
4. Сколько клеток должно быть занято в распределительной таблице?
5. Какие методы построения опорного плана известны?
6. В чем состоит сущность метода северно-западного угла?
7. В чем состоит сущность метода минимального элемента?
8. В каком случае говорят о базисном нуле?
9. Что называется потенциалом?
10.Какая формула используется для определения потенциалов занятых клеток?
11. С какой целью определяют оценки свободных клеток?
12. По какой формуле определяют оценки свободных клеток?
13. Каким образом осуществляется переход к новой итерации?
14. Какое условие должно соблюдаться при построении цикла по λ?
15. В какую клетку ставят число λ?
16. Как определяют значение λ?
17. Как пересчитывают значение функции в новой итерации?
18. Какие методы решения задач транспортного типа существуют еще?
19. Тест на тему «Транспортные задачи»
