Курсовая работа: Решение транспортной задачи в Excel
u1 =0, u2 =-8, u3 =-6
v1 =5, v2 =10, v3 =12
Переходим к проверке условий оптимальности (1). Достаточно проверять их для незаполненных клеток, так как для клеток заполненных эти условия выполняются как равенства. Для проверки берется незаполненная клетка, складываются соответствующие ей потенциалы (первый элемент строки и последний элемент столбца) и из них вычитается цена перевозки в данной клетке. Если полученное число отрицательное (или ноль), то оптимальность в данной клетке не нарушается (в случае выполнения условия (1) для всех незаполненных клеток, имеем оптимальный план перевозок). Если же в таблице встретилась хотя бы одна клетка, для которой это число положительно, тогда решение не является оптимальным и может быть улучшено.
Проверим на оптимальность имеющееся решение
(2,1)u2 +v1 -c21 =-8+5-8=-11<0
(2,2) u 2 +v2 -c22 =-8+10-6=-4<0
(3,1)u3 +v1 -c31 =-10+ 5-0=-5<0
(3,3)u3 +v3 -c33 =-10+12-0=2>0
Следовательно, условие оптимальности нарушено в клетке (3,3).
Имеющийся план перевозок можно улучшить.
Дадим описание заключительного шага алгоритма метода потенциалов.
ШАГ 3 Улучшение плана перевозок .
Улучшение плана происходит путем назначения перевозки θ>0 в ту клетку (i , j) таблицы, в которой нарушилось условие оптимальности. Но назначение ненулевой перевозки нарушает условия баланса вывоза продукции от поставщика i (вывозит весь запас и еще плюсθ>0 ) и условия баланса привоза продукции к потребителю j(получает все что можно и еще плюс θ > 0). Условия баланса восстанавливают путем уменьшения вывоза от i-поставщика к какому-то другому потребителю j(уменьшают на θ перевозку в какой-то заполненной клетке (i , j) строки i). При этом нарушается баланс привоза продукции к потребителю j (получает на θ меньше, чем ему требуется). Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т.д. до тех пор, пока цикл перемещения перевозок не замкнется на клетке, в которой нарушалось условие оптимальности. Продемонстрируем эти рассуждения на нашем примере.
120 | 60 | 50+ Ө | 10- Ө |
70 | - | - | 70 |
50 | - | 50- Ө | * + Ө |
60 | 100 | 80 |
120 | 60 | 60 | -(0) |
70 | - | - | 70 |
50 | - | 40 | * 10 |
60 | 100 | 80 |
1. Оптимальность нарушена в клетке (3,3). Назначим в нее перевозку θ>0 (+θ означает, увеличение на θ).
2.Нарушается баланс вывоза от поставщика 3 (вывозит 50+ θ, а это больше его запаса!). Уменьшаем на θ перевозку в заполненной клетке строки 3 (вне заполненной уменьшать нельзя, так как это приведет к отрицательной перевозке).
Рассмотрим те клетки цикла в которых уменьшаем на θ перевозку и берём минимум из вычетаемых, у нас это min{10- θ ,50- θ }=10.
И данное число надо подставить в цикл
§3. Транспортные задачи по различным критериям
Транспортная задача по критерию времени
Иногда возникает ситуация, когда в условиях (ТЗ) необходимо минимизировать не стоимость перевозок, а время их выполнения (Срочные грузы, перевозки скоропортящихся продуктов, работа «скорой помощи» и т.д.)
Имеется m поставщиков однородного груза и n потребителей груза. Для каждой пары (,) известно время , за которое груз перевозится от к . Требуется составить такой план перевозок, при котором все запасы поставщиков будут вывезены, а все запросы потребителей будут полностью удовлетворенны и наибольшее время доставки всех грузов будет минимизирован.
Задача о назначениях (Венгерский метод)
Имеется n видов работ и n рабочих. Каждый рабочий может выполнить любую из nработ за некоторое время (цена рабочего). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий.
§4. Решение транспортной задачи в Excel
В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов.
· В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах.
· В ячейки E5:I5 - заявки на продукцию, поступившие от магазинов.
· В ячейки B8:F9 - матрицу транспортных расходов, задающую расходы на перевозку из I-го склада в J-й магазин единицы продукции.