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