Вопрос 6. Метод потенциалов для решения транспортной задачи в сетевой постановке.

Простейшая задача на перевозки по критерию минимизации транспортных расходов формулируется следующим образом.

В m пунктах производства A₁,A₂,…A_m находится однородный продукт (уголь, картофель и т. д.) в количествах соответственно a₁,a₂…a_m единиц, которые должны быть доставлены в n пунктов потребления B₁,B₂,…B_n в количествах b₁,b₂…b_n единиц. Известны транспортные издержки c_ij, связанные с перевозкой единицы продукты из пункта A_i в пункт B_j. Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами доставки.

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

Транспортная задача, в которой это условие выполняется, называется закрытой или задачей с правильным балансом, в противном случае – открытой.

Открытую транспортную задачу можно формально преобразовать в закрытую путем введения фиктивного пункта потребления B_n+1 со спросом

в случае превышения запасов продукта над спросом или фиктивного пункта производства A_m+1 с запасом продукта

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

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

Математическая модель задачи имеет вид.

Целевые переменные x_ij – это количество единиц продукта, поставляемого из пункта A_i в пункт B_j. Целевая функция –

Ограничения по запасам и по потребностям

И ограничение из соображений здравого смысла .

Это задача линейного программирования со следующими особенностями:

1. Коэффициенты при переменных во всех уравнениях ограничений равны либо 0, либо 1.

2. Каждая переменная встречается в 2 и только в 2 уравнениях: один раз в системе ограничений по запасам и один раз в системе ограничений по потребностям.

3. Система ограничений симметрична относительно всех .

Построим к данной задаче двойственную ей:

Если – оптимальный план, то, а для.

называют потенциалами поставщиков A_i и потребителей B_j. Потенциалы представляют собой оценки, определяющие влияние объемов запаса продукта и уровней спроса на оптимальное значение целевой функции транспортных расходов.

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

Решение задачи на сети методом потенциалов начинается с построения начального опорного плана. Поставки груза из вершины в вершину будем обозначать стрелками с указанием величин поставок.

Опорный план должен удовлетворять следующим требованиям:

1) все запасы должны быть распределены, а потребности удовлетворены;

2) к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

3) общее количество стрелок должно быть на единицу меньше числа вершин;

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

Далее следует проверить план на оптимальность. Для этого вычисляют потенциалы. Одной из вершин (например, вершине 1) присваивают некоторое значение потенциала (например, равное 0). (Для большей наглядности потенциалы заключают в рамки.) После этого, двигаясь по стрелкам, определяют потенциалы остальных вершин, руководствуясь правилом: если стрелка выходит из вершины, то к потенциалу этой вершины прибавляем с_ij, если же направление стрелки противоположно, то с_ij вычитаем.

После вычисления потенциалов находят характеристики ребер без стрелок по правилу: из большего потенциала вычитается меньший, а разность вычитается из показателя с_ij, отвечающего данному ребру; если все ребра без стрелок имеют неотрицательные характеристики, то составленный план является оптимальным.

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

При определении величины поставки для "загружаемого " ребра рассматриваются все стрелки образовавшегося контура (если на сети – опорный план, то такой контур всегда существует, причем только один!), имеющие направление, противоположное направлению новой стрелки, и среди них находится стрелка с наименьшей поставкой – Р. Выбранная таким образом величина прибавляется ко всем поставкам со стрелками, имеющими то же направление, что и новая стрелка, и вычитается из поставок в стрелках, имеющих противоположное направление. Поставки в стрелках, не входящих в контур, сохраняются неизменными. Стрелка, по которой выбрано число Р, ликвидируется, и общее число стрелок остается прежним.

Новый опорный план исследуется на оптимальность подобно предыдущему.

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

Вырождение плана транспортной задачи в сетевой постановке внешне проявляется в том, что при полном использовании запасов и полном удовлетворении потребностей количество стрелок оказывается меньше, чем n - 1, где n – общее число вершин (включая и нулевые!).

Способ преодоления вырождения весьма прост: дополнительно вводится нужное количество стрелок с нулевыми поставками. Направления стрелок выбираются произвольно, однако они не должны образовывать замкнутый контур.

Пример 6: Решить транспортную задачу, представленную сетью (рисунок 9)

Рисунок 9

Проверим, является ли баланс задачи правильным, а сама задача – закрытой. Определим величину суммарного запаса груза=15+60+25=100 и величину суммарного спроса=40+35+55=130. Как видим, спрос превышает предложение, поэтому введем фиктивного производителя с запасом груза, равным 30 единицам продукта и составим начальный план, удовлетворяющий условиям опорного плана (рисунок 10)

Рисунок 10

Действительно:

• весь груз распределен, а спрос удовлетворен в полном объеме,

• все вершины задействованы (у каждой есть, по крайней мере, одна либо входящая, либо исходящая дуга)

• количество стрелок (6) на единицу меньше количества вершин сети (7)

• стрелки не образуют замкнутый контур.

Проверим, данный план перевозок на оптимальность.

Пусть потенциал 1 вершины равен 10. Дальше по стрелкам пути находим потенциалы остальных вершин

Потенциалы вершин		Характеристики ребер без стрелок
Номер вершины	Ее потенциал	Ребро	Его характеристика
1	10	(1;3)	=1-(10-9)=0
2	12	(1;6)	=3 -(16-10)=-3<0
3	9	(2;3)	=5 -(12-9)=2
4	12
5	18
6	16
7	16

Так как среди характеристик ребер без стрелок есть отрицательная, то начальный план не является оптимальным. Введем в план стрелку 16 (направление задается от вершины с меньшим потенциалом к вершине с большим потенциалом). В направлении, противоположном стрелкам начального плана образуется замкнутый контур:

16.

Дуга (1;6) получает нагрузку P.

При этом дуга (1;2) ликвидируется, а нагрузка дуги (2;6), как противоположной по направлению к (1;6), меняется с 40 на 25 (40–15=25).

Получаем новый план (рисунок 11).

Рисунок 11

Проверим, данный план перевозок на оптимальность.

Потенциалы вершин		Характеристики ребер без стрелок
Номер вершины	Ее потенциал	Ребро	Его характеристика
1	10	(1;3)	=1-(10-6)=-3<0
2	9	(1;2)	=2 -(10-9)=1
3	6	(2;3)	=5 -(9-6)=2
4	9
5	15
6	13
7	13

Так как среди характеристик ребер без стрелок есть отрицательная, то начальный план не является оптимальным. Введем в план стрелку 31. В направлении, противоположном стрелкам начального плана образуется замкнутый контур:1.

Дуга (3;1) получает нагрузку

P.

При этом дуга (4;5) ликвидируется, нагрузка дуги (3;4), как противоположной по направлению к (3;1), уменьшается на 5, а нагрузки, сонаправленных с (3;1) дуг (1;6), (6;5) – увеличиваются на 5. Получаем новый план (рисунок 12).

Рисунок 12

Проверим, данный план перевозок на оптимальность.

Номер вершины	Ее потенциал	Ребро	Его характеристика
1	10	(2;3)	=5-(9-9)=0
2	9	(1;2)	=2 -(10-9)=1
3	9	(4;5)	=6 -(15-12)=3
4	12	Отрицательных нет, план оптимален: (т. к. был введен фиктивный производственный пункт) + =340 денежных единиц.
5	15
6	13
7	13