Решение задач линейного программирования в среде Maple (стр. 3 из 3)
Этот метод можно сформулировать в виде единой правилы:
Неизвестный потенциал находится вычитанием известного из цены перевозки в заполненной клетке
Применим это правило для определения u и vв нашем примере и получим:
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.
И данное число надо подставить в цикл
Список литературы
1. Матвеев В.А. Конечные бескоалиционные игры и равновесия. Псков, 2004,176с.
2. Аладьев В.З., Богдявичюс М.А. MAPLE 6: Решение математических, статистических и физико – технических задач – М.: Лаборатория Базовых Знаний,2001 – 824с..
3. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.:ВШ, Книжный дом «Университет», 1998.
4. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993.
5. Воробьёв Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.
6. Прохоров Г.В., Колбеев В.В., Желнов К.И., Леденев М.А..Математический пакет MapleVRelease 4. М. 1998.