Главная | Обратная связь | Поможем написать вашу работу!

Алгоритм решения транспортной задачи методом потенциалов

1. Составляем исходный опорный план.

2. Находим потенциалы потребителей и поставщиков. Для этого составляем систему уравнений

где – тарифы занятых клеток. Уравнений в системе будет столько, сколько заполнено клеток, т. е. m+n-1. Потенциалов m+n. Поэтому, положим , остальные неизвестные находим из уравнений.

3. Для каждой свободной клетки находим сумму потенциалов, соответствующих этой клетке. Назовем ее косвенным тарифом и обозначим .

4. Определим разности между тарифами и косвенными тарифами

Эти разности называются характеристиками свободных клеток.

Если все характеристики неотрицательны, то план оптимален.

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

5. Для улучшения плана занесем поставку в ту клетку, которая соответствует наименьшей отрицательной характеристике. Для определения величины поставки отметим выбранную клетку знаком «+» и построим для нее «контур».

Для контура характерно следующее:

1) контур является замкнутой ломаной, состоящей из горизонтальных и вертикальных отрезков;

2) вершины контура лежат в занятых клетках, за исключением клетки, для которой строится контур;

3) отрезки контура могут пересекать занятые клетки, не являющиеся вершинами данного контура;

4) каждой свободной клетке соответствует только один контур.

Некоторые разновидности контуров показаны на рисунке.

Двигаясь по контуру от клетки, отмеченной знаком «+», поочередно проставляем в вершинах контура знаки «–» и «+».

Затем находим – величина грузов в клетках, отмеченных знаком «–». Q и определяет величину груза, который надо занести в свободную клетку. Далее, двигаясь по контуру, прибавляем Q к величинам поставок, находящихся в «положительных» клетках, и вычитаем Q из величин поставок, находящихся в «отрицательных» клетках. Получаем новый опорный план. Проверяем его на оптимальность.

Процесс продолжается до тех пор, пока все характеристики свободных клеток не станут неотрицательными.

Замечание 2. Часто приходится решать задачи, в которых нарушено в ту или иную сторону условие равновесия, т. е.

Такие задачи называются открытыми. Чтобы привести задачу к закрытой задаче, в первом случае вводится дополнительный столбец так называемого фиктивного потребителя со спросом, равным избытку продукции

Все тарифы этого столбца полагаем равными нулю.

Во втором случае приведение к закрытой задаче достигается введением фиктивного поставщика с объемом возможных поставок, равным недостатку продукции

Стоимости перевозок от фиктивного поставщика ко всем потребителям также равны нулю.

Пример 1. Рассмотрим задачу: имеется три поставщика с определенными запасами однородного груза и четыре потребителя с известными потребностями в этом грузе . Кроме того, задана матрица тарифов:

Модель задачи открытая, так как :

Поэтому вводим фиктивного потребителя с потребностью в 20 единиц груза и нулевыми тарифами.

Составляем таблицу и первоначальное распределение поставок производим по методу «северо-западного» угла:

-1

Число занятых клеток должно быть равно 3+5–1=7, у нас получилось 6. Это получилось потому, что при заполнении клетки (1,2) мы одновременно вычеркнули первую строку и второй столбец. Надо занести нулевую поставку в одну из клеток, расположенных рядом по строке или столбцу то клетки (1,2), т.е. или в (1,3), или в (2,2). Займем клетку (1,3). При таком расположении поставок затраты на перевозку груза составят:

Вычислим потенциалы , исходя из того, что для занятых клеток должно выполняться равенство . Полагаем, что один из потенциалов равен нулю, например .

Далее вычислим характеристики для свободных клеток: . Отрицательные характеристики заносятся в левый нижний угол клетки.

Выбираем клетку с наименьшей отрицательной характеристикой, т.е. (2,2). Строим контур с вершиной в этой клетке. Свободную клетку помечаем знаком «+», следующую по контуру – знаком «–» и т.д., меняя знаки. В свободную клетку заносится минимальная поставка из клеток, помеченных знаком «–». В нашем случае обе поставки равны 20 единицам. Поэтому мы вычитаем 20 единиц груза из поставок, стоящих в «отрицательных клетках» и прибавляем 20 единиц груза к поставкам, стоящим в «положительных клетках». Так как в «отрицательных клетках» было по 20 единиц груза, то после перераспределения поставок, в одну из них запишем нулевую поставку, а другую оставим пустой. Получим следующее (лучшее) распределение:

-1

При таком распределении поставка в 20 ед. попала в клетку с характеристикой равной –4, следовательно функция затрат улучшилась на ед. Т.о. .

Снова полагаем и вычисляем потенциалы. Далее, как и прежде, вычисляем характеристики для свободных клеток"ободную клетку заносится минимальная поставка из клеток, помеченных знаком "лбцу то клетки (1,2), т.е. олбец.. Выбираем клетку с наименьшей отрицательной характеристикой, например, (2,5). Строим контур. Груз, равный min (20, 20) = 20 ед. перераспределяем по контуру. Получаем следующее распределение:

-1

При таком распределении .

Находим потенциалы, характеристики для незанятых клеток и строим контур для клетки (2,1). Поставку, равную min (10,0) =0, перераспределяем по контуру. Получаем следующее распределение:

-1

Продолжая вышеописанный процесс нахождения потенциалов, характеристик для пустых клеток и построение контура, приходим к следующему распределению:


		20		10
10	20			10
			50	0

Найдя для этого распределения характеристики незанятых клеток, видим, что среди них нет отрицательных характеристик, и, следовательно, мы нашли оптимальное решение, при котором функция затрат на перевозку груза достигла своего минимального значения:

Чтобы оптимальный план получить за меньшее число итераций, надо первоначальное распределение поставок проводить по методу «наименьшего тарифа», т.е. сначала заполнить клетки соответствующие минимальным тарифам.

Попробуйте для следующей задачи составить первоначальный опорный план по методу «наименьшего тарифа».