Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рассмотрим пример.
|
|
В трех хранилищах горючего ежедневно хранится 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. Тест на тему «Транспортные задачи»
1. Каким должен быть перевозимый груз?
А. Разным.
Б. Однородным.
В. Любым.
2. Какие методы используются для получения исходного плана?
А. Метод северо–западного угла, метод минимального элемента.
Б. Метод Гомори, метод минимального элемента.
В. Метод потенциалов, метод минимального угла.
3. В каком случае план является вырожденным?
А. если количество заполненных клеток меньше m+n-1.
Б. если количество заполненных клеток равно m+n-1.
В. в таблице появляется прямоугольник, все вершины которого - заполненные клетки.
4. Что учитывает метод минимального элемента при построение исходного плана?
А. Потребителей.
Б. Потребитель сырья.
В. Стоимость перевозок.
5.В методе потенциалов для каждой заполненной клетки строится соотношение:
А.UI +VJ =CIJ
Б. C’IJ =UI +VJ
В. C’IJ – CIJ < =0
6.Когда в таблицу вводят фиктивного потребителя?
А. Если ∑ аi ≠ ∑ вj
Б. Если ∑ аi < ∑ вj
В. Если ∑ аi > ∑ вj
7. В каком случае модель является закрытой?
А. ∑ аi < ∑ вj
Б. ∑ аi > ∑ вj
В. ∑ аi = ∑ вj
8. По какой формуле определяется оценка свободных клеток?
А. Δ ij=Cij+(Ui+Vj).
Б. Δ ij=Cij-(Ui+Vj).
В. Δ ij=Cij+(Ui-Vj).
9.По каким клеткам строятся цикл?
А. Свободным.
Б. Отрицательным.
В.Занятым.
10. По какой формуле определяется новое значение стоимости перевозки?
А. Z’ = Z - λ * |Δ ij|.
Б. Z’ = Z + Δ ij * | λ |.
В. Z’ = Z + λ * | Δ ij |.
11. Что обеспечивает метод потенциалов?
А. переменное убывание значений целевой функции.
Б. новый базисный план.
В. монотонное убывание значений целевой функции и за конечное число шагов найти минимум функции.
|
|