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

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

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

Пусть 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''в направлении обхода дополнительный поток, величиной. Каждой дугеvV''приписываем символ «+», если направление дугиvсовпадает с направлением обхода, и символ «–» в противном случае. Полагаем=min x_vсредиvV”, которым приписан символ «–».

Полагаем ;

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

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

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

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

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

Алгоритм поиска исходного базисного дерева.

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

Строим граф G=E,V,H, в которомE=E{i₀},гдеi₀– дополнительная вершина,V=VV₁V₂, где

V₁ –множество дополнительных дуг, направленных от вершин – пунктов производства к дополнительной вершине i₀,

V₂– множество дополнительных дуг, направляемых отi₀к промежуточным вершинам и вершинам–пунктам потребления.

Для vV полагаем c_v=0;

для vV₁ полагаемc_v=1;

для vV₂полагаем c_v=1.

Полагаем .

В качестве исходного базисного дерева берется подграф G=E,V₁V₂, H.Если в результате решения этой задачи оказалось, что оптимальное значение функционала строго больше нуля, то исходная задача (6.1) –(6.3) решения не имеет, в противном случае будет получено базисное дерево исходной задачи.

Пример.Решим задачу, представленную графом, изображенным на рис. 6. 1

Рис. 6.1.

Вершины графа обозначены цифрами от 1 до 9, обведенными кругом. Около дуг написаны их имена. Рядом с каждой вершиной проставлены мощности вершин:

b₁=–3; b₂=–1; b₃=–7; b₄=0; b₅=0; b₆=5; b₇=2; b₈=4; b₉=0.

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

Дуга v	v3	v2	v1	v11	v10	v4	v5	v7	v6
cv	1	2	1	6	1	1	1	2	2
Дуга v	v9	v8	v13	v12	v15	v14	v17	v16	v18
cv	4	1	3	1	7	6	1	3	2

Примем за исходный базис дерево, дуги которого выделены жирной линией (см. Рис. 6.1).

Шаг 1.

Определим объем перевозок для исходного базисного дерева.

Общая стоимость перевозок составит

Определим потенциалы вершин:

u₉:= 0;

u₇= u₉–= –3;

u₈= u₇+= –2;

u₄= u₇–= –7;

u₅= u₄+= –6;

u₆= u₅+= –5;

u₃= u₄–= –8;

u₁= u₄–= –9;

u₂= u₄–= –8;

Проверим полученное решение на оптимальность:

На дуге v₁₀u₇ > u₂ +_, следовательно, дугуv₁₀вводим в базис. Возникший цикл (см. Рис. 6.2) обходим в направлении дугиv₁₀.

Рис. 6.2

 ; 1 –  ; 6 –  ;

 = min (1,6)=1 ; =0, дугуv₄выводим из базиса.

Шаг 2.

Пересчитаем объем перевозок для нового базиса:

3 ; 1 ;7 ; 4 ; 5 ; 5 ; 6 –1 = 5 ; 0; f=48.

Определим потенциалы вершин.

u₁=–9 ; u₂=–8 ; u₃=–8 ; u₄=–7 ;u₅=–6 ; u₆=–5 ; u₇=–3 ; u₈=–2 ;u₉:=0 ;

Проверим полученное решение на оптимальность. На дуге v₆u₆>u₃+, следовательно, решение не оптимально и дугуv₆вводим в базис. Возникший цикл обходим в направлении дугиv₆,

= ; =7 –  ; = 5 –  ; = 5 –  ;

 = min (7,5,5)=5 . =0 дугуv₁₂выводим из базиса.

Шаг 3.

Пересчитаем объемы перевозок для нового базиса:

.

Определим потенциалы вершин u₁=–9 ; u₂=–8 ; u₃=–8 ; u₄=–7 ;u₅=–6 ; u₆=–6 ; u₇=–3 ; u₈=–2 ; u₉:=0 . Полученное решение оптимально. Дерево перевозок изображено на рис. 6.3. Стоимость перевозок составит:

Рис. 6.3