Оптимальный план транспортной задачи. Метод потенциалов

Заметим, что для всех полученных решений число заполненных (отличных от нуля) клеток транспортной таблицы в точности равно числу базисных переменных задачи, т.е. 6.

Определение 3.4.1 Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно , где – число производителей, – число потребителей, то план перевозок невырожденный.

Определение 3.4.2 Если число заполненных клеток транспортной таблицы меньше , то план перевозок вырожденный.

Вырожденный план перевозок получится, если на каком-то шаге одновременно удовлетворяется спрос потребителя и исчерпывается предложение соответствующего поставщика, т.е. одновременно вычеркивается строка и столбец.

Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты – это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные за­траты не больше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них — метод потенциалов.

Дата добавления: 2014-01-04