Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Пример решения транспортной задачи методом потенциалов
1. Закрытая транспортная задача.
| b1 = 150 | b2 = 150 | b3 = 300 | |
| a1 = 100 | |||
| a2 = 200 | |||
| a3 = 300 |
2. Строим 1-ое опорное решение методом наименьших стоимостей.
| b1 = 150 | b2 = 150 | b3 = 300 | ||
| a1 = 100 | 100 1 | u1 | ||
| a2 = 200 | 200 6 | u2 | ||
| a3 = 300 | 150 3 | 50 2 | 100 5 | u3 |
| v1 | v2 | v3 |
3, 4. Проверяем 1-ое опорное решение на оптимальность методом потенциалов.
u1 + v2 = 1
u2 + v3 = 6
u3 + v1 = 3
u3 + v2 = 2
u3 + v3 = 5
u1 = 0 v1 = 2
u2 = 2 v2 = 1
u3 = 1 v3 = 4
Õ11 = 2 – (0 + 2) = 0
Õ13 = 2 – (0 + 4) = -2 < 0
Õ21 = 5 – (2 + 2) = 1 > 0
Õ22 = 7 – (2+ 1) = 4 > 0
Вывод: 1-ый план не является оптимальным.
5. Переходим к новому опорному решению, на котором значение целевой функции будет меньше. Строим цикл.
- 100 + 0
+ 50 - 100
0 100
 |
150 0
| b1 = 150 | b2 = 150 | b3 = 300 | ||
| a1 = 100 | 0 1 | 100 2 | u1 | |
| a2 = 200 | 200 6 | u2 | ||
| a3 = 300 | 150 3 | 150 2 | u3 | |
| v1 | v2 | v3 |
Проверяем 2-ое опорное решение на оптимальность методом потенциалов.
u1 + v2 = 1
u1 + v3 = 2
u2 + v3 = 6
u3 + v1 = 3
u3 + v2 = 2
u1 = 0 v1 = 2
u2 = 4 v2 = 1
u3 = 1 v3 = 2
Õ11 = 2 – (0 + 2) = 0
Õ21 = 5 – (4 + 2) = -1 < 0
Õ22 = 7 – (4+ 1) = 2 > 0
Õ33 = 5 – (1 + 3) = 2 > 0
Вывод: 2-ий план не является оптимальным.
- 0 
+ 100
+ 0 - 200
- 150 + 150
0 100
0 200
150 150
| b1 = 150 | b2 = 150 | b3 = 300 | ||
| a1 = 100 | 100 2 | u1 | ||
| a2 = 200 | 0 5 | 200 6 | u2 | |
| a3 = 300 | 150 3 | 150 2 | u3 | |
| v1 | v2 | v3 |
Проверяем 3-ье опорное решение на оптимальность методом потенциалов.
u1 + v3 = 2
u2 + v1 = 5
u2 + v3 = 6
u3 + v1 = 3
u3 + v2 = 2
u1 = 0 v1 = 1
u2 = 4 v2 = 0
u3 = 2 v3 = 2
Õ11 = 2 – (0 + 1) = 1 > 0
Õ12 = 1 – (0 + 0) = 1 > 0
Õ22 = 7 – (4+ 0) = 3 > 0
Õ33 = 5 – (2 +2) = 1 > 0
Получили оптимальное решение.
x11 = 0
x12 = 0
x13 = 100
x21 = 0
x22 = 0
x23 = 200
x31 = 150
x32 = 150
x33 = 0
L(x) = 100*2 + 0*5 + 200*6 + 150*3 + 150*2 = 2150 (у. е.)
| <== предыдущая страница | | | следующая страница ==> |
| Алгоритм решения транспортной задачи методом потенциалов | | | Постановка задачи. Транспортная задача – одна из распространенных задач линейного программирования |
Дата добавления: 2015-06-30; просмотров: 157; Нарушение авторских прав
Мы поможем в написании ваших работ!