Метод потенциалов решения транспортных задач
Метод потенциалов:
Введем строку потенциалов ui и столбец потенциалов vj.
Полагая, что u1=0, остальные ui и vj найдем так, чтобы
а) для заполненных клеток выполнялись равенства ;
б) для незаполненных клеток выполнялись равенства (оценки пустых клеток).
Критерий оптимальности:
Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия то Х0 является оптимальным планом транспортной задачи.
Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.
Пример 3: Проверить план, построенный методом северо-западного угла на оптимальность методом потенциалов.
Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.
(перепишите в свою заготовленную таблицу план, полученный методом северо-западного угла).
По заполненным клеткам вычислим потенциалы по правилу :
Таким образом, мы вычислили потенциалы заполненных клеток.
Для пустых клеток вычислим их оценки .
Будем их записывать в верхний правый угол клетки.
Так среди оценок пустых клеток есть отрицательные – план не оптимальный.
Необходимо построить следующий план. Для этого построим цикл перерасчета таблицы.
Цикл перерасчёта таблицы – это последовательность клеток, удовлетворяющая условиям:
· Одна клетка пустая с отрицательной оценкой, все остальные заполненные.
|
|
· Любые две соседние клетки находятся в одной строке или в одном столбце.
· Пустой клетке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".
Далее составляем новую таблицу по следующему правилу:
· Клетки вне цикла остаются без изменения.
· В минусовых клетках находят число X = min(Xij).
· В плюсовых клетках цикла добавляем Х.
· Из минусовых клеток цикла вычитаем Х.
Получим новую таблицу, дающую новое решение Х, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.
Пример 4: Для плана примера 3 построим цикл перерасчета.
Заполним одну из пустых клеток с отрицательной оценкой. Возьмем клетку А3В3, так как в ней стоимость меньше, чем в клетке А3В1.
Построим цикл перерасчета:
Построим второй опорный план:
Заполненных клеток должно быть 3+5-1=7.
Вычислим суммарную стоимость перевозок для построенного плана:
F = 15*1+5*5+12*1+0*2+5*1+8*3+15*3=126.
Проверим план на оптимальность методом потенциалов.
Так среди оценок пустых клеток есть отрицательные – план не оптимальный.
|
|
Построим следующий план.
Для этого построим цикл перерасчета таблицы.
Третий опорный план:
Вычислим суммарную стоимость перевозок для построенного плана:
F = 15*1+5*5+12*1+5*1+8*3+0*3+15*3=126.
Проверим план на оптимальность методом потенциалов.
Так среди оценок пустых клеток есть отрицательные – план не оптимальный.
Построим следующий план.
Для этого построим цикл перерасчета таблицы.
Четвертый опорный план:
Так как среди оценок пустых клеток нет отрицательных значений, то построенный план оптимальный.
При этом суммарная стоимость перевозок
F = 15*1+5*4+12*1+5*1+8*3+0*3+15*3=121 является минимальной.
Запишем ответ задачи:
Ответ: Чтобы транспортные расходы были минимальными 121 ден.ед. необходимо перевозить: с 1-го склада – 15 компьютеров в 1-ый магазин; со 2-ого склада – 12 - во 2-ой магазин, 8 - в 4-ый и 5 - в 5-ый магазин; с 3-его склада – 5 компьютеров в 1-ый магазин, 5 – во 2-ой и 10 – в 5-ый.
Дайте ответы на контрольные вопросы:
1. Как построить опорный план транспортной задачи?
2. В чем суть метода потенциалов?
3. Как строится цикл перерасчета?
Отчет по практической работе (ответы на контрольные вопросы)
присылайте на электронный адрес:
larisanikolaevna.epgl@yandex.ru
|
|
Дата добавления: 2022-01-22; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!