1) Составить опорный план, т.е. начальное приближение.
2) Составить математическую модель исходной прямой и математическую модель двойственной задач.
3) Пользуясь методом наименьшего (наибольшего) элемента и методом потенциалов найти улучшение исходного опорного плана до тех пор, пока он не будет удовлетворять условию оптимальности.
Метод наименьшего элемента.
Сбалансировать задачу (убедиться, что задача сбалансирована).
1) Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.
2) В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.
3) Проверить, остался ли нераспределенным груз у этого поставщика.
4) Если груз распределен не полностью, то применяем п.2 относительно строки этого поставщика. Продолжать до тех пор, пока груз этого поставщика будет полностью распределен.
|
|
Если груз поставщика распределен полностью, проверить, полностью ли удовлетворен объем потребителя.
Если потребитель полностью удовлетворен, то применить пункт 2 относительно оставшихся поставщиков и потребностей в таблице.
Если объем потребителя полностью не удовлетворен, тогда применяется пункт 2 относительно соответствующего столбца.
5) Проверить план на вырожденность. Количество базисных клеток должно быть равным r=m+n-1.
Если план вырожденный, то поставить фиктивное значение груза так, чтобы иметь возможность найти потенциалы всех базисных клеток (ставить нулевую перевозку).
6) Проверить на оптимальность и по возможности дальше улучшить, перейдя к методу потенциалов.