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