Метод наименьшего элемента

Алгоритм решения транспортных задач.

1) Составить опорный план, т.е. начальное приближение.

2) Составить математическую модель исходной прямой и математическую модель двойственной задач.

3) Пользуясь методом наименьшего (наибольшего) элемента и методом потенциалов найти улучшение исходного опорного плана до тех пор, пока он не будет удовлетворять условию оптимальности.

1) Сбалансировать задачу (убедиться, что задача сбалансирована).

2) Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.

3) В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.

4) Проверить, остался ли нераспределенным груз у этого поставщика.

5) Если груз распределен не полностью, то применяем п.2 относительно строки этого поставщика. Продолжать до тех пор, пока груз этого поставщика будет полностью распределен.

Если груз поставщика распределен полностью, проверить, полностью ли удовлетворен объем потребителя.

Если потребитель полностью удовлетворен, то применить пункт 2 относительно оставшихся поставщиков и потребностей в таблице.

Если объем потребителя полностью не удовлетворен, тогда применяется пункт 2 относительно соответствующего столбца.

6) Проверить план на вырожденность. Количество базисных клеток должно быть равным r=m+n-1.

Если план вырожденный, то поставить фиктивное значение груза так, чтобы иметь возможность найти потенциалы всех базисных клеток (ставить нулевую перевозку).

7) Проверить на оптимальность и по возможности дальше улучшить, перейдя к методу потенциалов.

Дата добавления: 2013-12-11