Читайте также:
|
1) Для всех базисных клеток создать систему уравнений вида 
.
Выбрать переменную Ui или Vj, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно Ui и Vj и найти эти значения.
2) Для всех свободных клеток составить и проверить выполнение неравенств: 
Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.
Если хотя бы для одной клетки не выполняется это неравенство, то необходимо улучшить опорный план с помощью коэффициента перераспределения W.
3) Находим клетку, где сильнее всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим W со знаком «+».
4) Построить контур перераспределения груза, начиная с выбранной клетки, исходя из следующих правил:
- В строке и столбце должно быть четное число W;
- Контур меняет направление только в базисных клетках;
- Коэффициент W меняет свой знак с «+» на «-» поочередно в углах контура.
5) После построения контура отметить, в каких базисных клетках коэффициент W стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент W будет равен перевозке в выбранной клетке.
6) Найти новый план, перераспределив найденное значение W по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку.
7) Проверить новый план в соответствии в п.2. если неравенства для свободных клеток выполняются, значит найденный план оптимален.
Если в математической модели целевая функция на максимум (Zmax), то задача решается методом максимального элемента. т.е. грузоперевозка (Xij) распределяется при составлении опорного плана с учетом наибольшего значения Cij аналогично метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства 
Дата добавления: 2015-02-16; просмотров: 76 | Поможем написать вашу работу | Нарушение авторских прав |