Транспортные задачи линейного программирования

Транспортная задача линейного рограммирования является одной из самых распространенных специальных задач линейного программирования. Первая строгая постановка задачи принадлежит Хичкоку, и поэтому в зарубежной литературе иногда её называют проблемой Хичкока. Первый точный метод решения транспортной задачи был разработан российскими учеными Л.В. Канторовичем и М.К. Гавуриным. В настоящей работе рассмотрены два варианта постановок транспортной задачи: сетевая и матричная.

Транспортная задача в сетевой постановке

Пусть G =á E, V, H ñ c вязный ориентированный граф, где Е – множество вершин, V – множество ориентированных дуг, H – отображение H: V®E´E, H (v)=(h ₁(v), h ₂(v)). Вершину h ₁(v) будем называть началом дуги v, h ₂(v)– ее концом. V⁺_i – множество дуг, входящих в вершину i, V^-_i – множество дуг, выходящих из вершины i. Все вершины графа делятся на пункты производства (источники) и пункты потребления (стоки)потока. Для каждой вершины iÎЕ известна величина, задающая объем производства или потребления i –ой вершины, причем, если b_i< 0, то вершина i – пункт производства (источник), если b_i> 0, то i –я вершина – пункт потребления (сток) потока, если b_i =0, то вершина i – промежуточная вершина.

Для каждой дуги v Î V задана величина c_v, характеризующая стоимость перевоза единицы груза по данной дуге. Задача состоит в том, чтобы определить количество перевозимого груза x_v по каждой дуге vÎV при условии, что весь поток из пунктов производства будет вывезен, потребности всех пунктов потребления будут удовлетворены и суммарная стоимость транспорта потока будет наименьшей.

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

	(6. 1)
при ограничениях ,	(6. 2)
xv ³0, v Î V,	(6.3)

где (6.1) – минимизируемый функционал (суммарная стоимость перевоза потока), (6.2) – уравнение материального баланса, т.е. суммарный поток, входящий в вершину, минус суммарный поток, выходящий из вершины, должен быть равен объему потока, производимому (потребляемому) в i –ом пункте, соотношение (6.3) означает, что транспортируемый поток движется только в направлении дуг графа G.

Если задача (6.1)–(6.3) разрешима, то . Легко видеть, что она является задачей линейного программирования и может быть решена алгоритмом симплекс-метода. Однако сетевая структура задачи позволяет разработать более эффективные методы ее решения. Таковым является метод потенциалов для решения транспортных задач.

Метод потенциалов решения данной задачи предполагает, что на исходном графе некоторым способом определено начальное исходное базисное дерево G¢ =á E, V', H ñ, (его дуги будем называть базисными), по которому осуществляется перевозка груза таким образом,

Для определения величин x_vÎV' можно воспользоваться следующим алгоритмом:

Алгоритм 1.

0 – шаг. E¢:= E.

k– й шаг. Если E¢ ¹Æ, то найти вершину, для которой (|V'⁺_i|+|V' ^–_i| =1) {т.е. вершина i концевая на G¢ =á E', V', H ñ}.

Если |V'⁺_i| =1, то для дуги v Î V'⁺_i выполнить:

x_v:= b_i, .

Если |V' ^–_i| =1, то для дуги v Î V' ^–_i выполнить:

x_v:=– b_i, .

Перейти к следующему шагу.

Замечание. В результате работы алгоритма может получиться недопустимое решение: т.е. для некоторых v Î V x_v< 0. В этом случае следует сменить исходное базисное дерево. Однако это не гарантирует, что на нем будет получено допустимое решение. Далее будет описан алгоритм, позволяющий либо определить базисное решение, либо доказать, что его не существует.

Будем считать, что исходное базисное дерево G’ найдено и для v Î V' определены x_v> 0. Для того, чтобы определить, является ли полученное решение оптимальным, воспользуемся следующим критерием оптимальности:

Критерий оптимальности:

Пусть x_v, v Î V, – такое решение задачи (6.1) – (6.3), что для vÎV\V' x_v =0 и для v Î V' x_v ³0. Это решение оптимально тогда и только тогда, когда существуют числа u_i, i Î E,называемые потенциалами, такие, что

	(6.4)
	(6.5)

Если переменные u_i, i Î E, интерпретировать как цены перевозимой продукции, то выписанные зависимости интерпретируются так. По дуге, по которой перевозится продукция цена в конце равна цене в начале плюс стоимость перевозки. В оптимальном решении по дуге не везется продукция, когда цена в конце дуги меньше цены в начале плюс стоимость перевозки. (В оптимальном решении по дуге не везется продукция, если цена в конце дуги меньше суммы: цена в начале плюс стоимость перевозки). Для расчета потенциалов применяется следующий алгоритм:

 

Алгоритм 2 .

0–шаг. Для произвольной (только одной) вершины iÎE полагаем u_i:=0;

k– шаг. Найти дугу v Î V', для которой известен потенциал, только одной из ее вершин. Если такой дуги нет, то конец работы, в противном случае используя зависимость , определяем потенциал в вершине, в которой он неизвестен, и переходим к (k +1) шагу.

Алгоритм 3 .

1. Среди всех дуг vÎV\V' ищем дугу v ₀такую, что ;

2. Если такой дуги нет, то исходная задача (6.1)–(6.3) решена, иначе следует выполнить алгоритм 4 перехода к новому базисному дереву.

 

Алгоритм 4.

V':= V' È{ v ₀}, где v ₀ дуга, найденная в Алгоритме 3. Теперь граф G' =á E, V', H ñсодержит ровно один цикл G'' =á E'', V'', H ñ, причем v ₀ ÎV'. На подграфе G'' задаем направление обхода, совпадающее с направлением дуги v ₀, и пропускаем по подграфу G'' в направлении обхода дополнительный поток, величиной q. Каждой дуге v Î V'' приписываем символ «+ q», если направление дуги v совпадает с направлением обхода, и символ «– q» в противном случае. Полагаем q =min x_v среди v Î V”, которым приписан символ «– q».

Полагаем ;

Для всех v Î V"\ { v ₀}:

x_v:= x_v+ q, если дуге v приписан знак + q;

x_v:= x_v– q, если дуге v приписан знак – q.

Из множества V’\ { v ₀} исключаем дугу, для которой x_v =0. Если таких дуг несколько (вырожденный случай), то удаляем только одну так, чтобы не нарушилась связность графа G' =á E, V’, H ñ.

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