9.12. транспортная задача

9.12. транспортная задача

Формулировка транспортной задачи. Имеется т пунктов Пр П2, Пт, в которых производится некоторый однородный продукт соответственно в количестве av а2, ат единиц. Этот продукт необходимо доставить в п пунктов потребления Qv Q2, Qn, потребности которых в продукте соответственно составляют bv b2, —,Ъп единиц. Стоимость перевозки из каждого пункта производства Пг. (/ = 1, 2,т) в каждый пункт потребления Q} (у = 1, 2,и) известна и равна с~ единиц. Требуется найти план перевозок, при котором были бы удовлетворены все потребности, а суммарная стоимость всех перевозок была бы наименьшей.

т п

Очевидно, что если ^а, < Х^!/'то транспортная задача неразрешима. '=1 ;'=1

244

Можно считать, что Y^a, = Y^6. (если Y^a, > Y^Ay, то вводят

1=1 7=1 i=l У=1

дополнительный (фиктивный) пункт потребления с потребт л

ностью, равной Y^a, Y^ • единиц).

1=1 7=1

Обозначим через х.. количество продукта, перевозимого из пункта П;. (г = 1, 2, т) в пункт Q. (у = 1, 2, и). Если / — стоимость перевозок по этому плану, то

т л

f = XXw

i=l 7=1

л

При этом из пункта П;. (/ = 1, 2, т) будет вывезено всего ^Ху

т

единиц продукта, а в пункт Q} (j = 1, 2,л) завезено Y^Ху единиц

i=i

продукта. Значит,

л т

Y/Xy at, і 1,2,/я; Y^. 6у, у 1,2,и.

7=1 г'=1

Таким образом, транспортная задача является задачей линейного программирования в канонической форме:

т л

f = ^CyXy(mm), (9.39)

і=І7=1

ftxg=at, / = 1,2,...,/я, (9.40)

7=1 т

?,Ху=Ьр ;=1,2,...,л, (9.41)

;=1

х..>0, і =1,2,..., /и;; = 1,2,..., л. (9.42)

Свойства транспортной задачи:

Г. Транспортная задача (9.39)—(9.42) имеет оптимальное pern и

шение тогда и только тогда, когда Y^ а, = Y^ .

;=1 7=1

2°. Если все числа av а2, ат и йр Ь2,йл — целые, причем

т п

Y^a, = Y^., то транспортная задача (9.39)—(9.42) имеет оптимальні 7=1

ное решение с целыми координатами.

245

3°. Рант системы векторов условий транспортной задачи (9.39)— (9.42) равен т + и 1 (/и — число пунктов производства, и — число пунктов потребления).

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

9.13. Опорные решения транспортной задачи

Условия транспортной задачи удобно записывать в транспортную таблицу, в которой строки соответствуют пунктам производства, а столбцы — пунктам потребления (табл. 9.6).

При этом каждому неизвестному х.. (/ = 1, 2,m;j =1,2,п) соответствует клетка (г, j) транспортной таблицы.

Циклом в транспортной таблице называют замкнутую ломаную линию (рис. 9.4), удовлетворяющую следующим трем условиям:

все вершины ломаной находятся в клетках таблицы;

ребра ломаной расположены по строкам или по столбцам таблицы;

к каждой вершине подходят ровно два ребра, причем одно — по строке, а другое — по столбцу.

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

246

Рис. 9.4

Пусть ос = (Хц,Ху,х^п) — допустимое решение транспортной задачи (9.39)—(9.42). Ненулевые координаты а запишем в соответствующие клетки транспортной таблицы 9.6. Допустимый вектор а является опорным решением транспортной задачи тогда и только тогда, когда набор заполненных клеток ацикличен.

Опорное решение транспортной задачи можно построить методом «минимального элемента». Для этого среди всех клеток табл. 9.6 выбираем клетку с наименьшим Су (если таких клеток несколько, берем любую из них).

Пусть (г, s) — такая клетка. Полагаем х^ = min{ar, b}. Если х = а то, заменив ЬнаЬ' = Ьar, вычеркиваем r-ю строку транс-портной таблицы. Если х„ = Ь,, заменяем число а на a' = а b и вычеркиваем s-й столбец. Если xrs = ar = bs, вычеркиваем r-ю строку и s-й столбец одновременно. В результате получаем новую таблицу меньшего размера, для которой повторяем указанную процедуру. Через конечное число шагов будет построено опорное решение.

Предположим, что a = (х^,Ху,х^п) — некоторое опорное решение транспортной задачи. Ненулевые координаты ос запишем в соответствующие клетки транспортной таблицы. Если заполненных клеток окажется меньше, чем т + п 1 клетка, то дополнительно в некоторые клетки допишем нули так, чтобы в результате образовался ацикличный набор из т + п 1 заполненных клеток (в этом случае векторы условий, соответствующие заполненным клеткам, составляют базис опорного решения а).

247

Потенциалами опорного решения ос называют числа ы. (/ = 1, 2, т) и Vj (у' = 1, 2,и) такие, что

«. + vy. = c.. (9.43)

для всех заполненных клеток (г, у).

Соотношения (9.43) представляют собой систему т + п-1 линейных уравнений ст + п неизвестными. Эта система всегда совместна, причем одно из неизвестных можно положить равным любому числу и тогда все остальные неизвестные определятся однозначно.

Достаточное условие оптимальности опорного решения. Пусть и. (г = 1, 2,т) и vy. (у = 1, 2,и) — потенциалы опорного решения а транспортной задачи (в транспортной таблице заполнены клетки, образующие ацикличный набор). Если для всех незаполненных клеток (/, у)

«, + v,.<c.,

то а — оптимальное решение транспортной задачи.

Для отыскания потенциалов данного опорного решения необходимо найти некоторое решение системы линейных уравнений:

u1 + v1 = 2, u3 + v2 = 8,

u2 + vl = l, «3 + v3 = 13,

u2 + v2 = 3, и3 + v4 = 7.

Полагая u{ 0, получаем vt -2, u2 = -l, v2 = 4, u3 = 4, v3 = 9, v4 3. Проверка показывает, что для всех незаполненных клеток (г, у) и{ + Vj < Су. Следовательно, данное опорное решение оптимально. •

248

9.14. Решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов проводится по следующей схеме:

Находят начальное опорное решение о^ = (х^,х'у,х'тп) (например, методом «минимального элемента» (см. п. 9.13)). Если в транспортной таблице заполненных клеток оказалось меньше, чем т + п 1, дополнительно дописывают нули так, чтобы получился ацикличный набор из т + и 1 заполненных клеток.

Вычисляют потенциалы и. (/ = 1, 2, т); v}. (j= 1, 2, и) опорного решения осг Если для всех незаполненных клеток (г, j) и. + Vj < Су, то otj — оптимальное решение и транспортная задача решена. В противном случае выбирают некоторую клетку (г, s) такую, что ur + vs > сп.

В транспортной таблице строят цикл, одна вершина которого находится в клетке (г, s), а все остальные вершины — в заполненных клетках (такой цикл всегда существует, и притом только один). Каждой вершине цикла присваивают знак «+» или «-» следующим образом: вершине в клетке (г, s) присваивают знак «+», а дальше расставляют знаки так, чтобы они от вершины к вершине чередовались.

Обозначим через р наименьшее из чисел {х'у}, стоящих в клетках, которым присвоен знак «-»; пусть р =х'ы (если число находится не в одной, а в нескольких клетках, выбираем любую из них). После этого заполняем транспортную таблицу согласно следующему правилу:

а) клетки, в которые не попали вершины цикла, заполняют так же,

как и раньше;

б) если клетке (/, j) присвоен знак «+», то в эту клетку записывают

число х'у + р;

в) клетку (к, I) не заполняют, а в остальные отрицательные клетки

[i, j) записывают число х'у р.

В результате получаем ацикличный набор из т + п 1 заполненных клеток транспортной таблицы, который определяет опорное решение ос2 такое, что Дос2) < /(ocj).

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

249

О Пример. Решить транспортную задачу:

Ниже приведены все этапы решения этой задачи (начальное опорное решение построено методом «минимального элемента»):

В последней таблице записан оптимальный план перевозок, стоимость которых составляет 20 ■ 3 + 20 • 4 + 15 ■ 1 + 15 ■ 2 + 15 ■ 2 + + 5 ■ 4 = 235 единиц. •

250 9.15. Параметрические задачи линейного программирования

Семейство задач линейного программирования в канонической форме

/,=i>}+YjO*;(min), (9.44)

л

Xty*y=*k. / = U,..., т, (9.45)

у=1

х.>0, У = 1,2,..., и (9.46)

(где y'j, у" — некоторые числа, у 1, 2, и; ґ — параметр, -оо < / < +оо) называется параметрической задачей линейного программирования.

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

Пусть а — некоторое опорное решение задачи (9.44)—(9.46). Обозначим через А(а) множество всех значений параметра t, при которых ос является оптимальным решением задачи (9.44)—(9.46).

Возможны лишь следующие случаи:

1) Д(а) = 0; 2) Д(о) = {t0}; 3) Д(о) = [tv t2];

4) Д(о) = ]—>, fj; 5) Д(а) = [t2, +~[; 6) Д(а) = ]-~, +~[.

Рассмотрим некоторый базис Bv В2,Вг опорного решения а. Тогда оценки этого базиса для задачи (9.44)—(9.46) имеют вид

8;+5';/, у=і,2,...,й.

Обозначим через T(BV В2,В Л множество всех решений системы неравенств

8;.+8';ґ<о, у =і,2,..., я.

Тогда:

1) Ma)^T(BvB2,...,B);

если а — невырожденное опорное решение, то

A{a) = T{BvB2,...,Br);

если а — вырожденное опорное решение, то

A(a) = jT(BvB2,...,Br), где объединение берется по всем базисам опорного решения а.

251

Таким образом, всегда можно найти множество всех значений параметра t, при которых данное опорное решение является оптимальным решением задачи (9.44)—(9.46).

О Пример. Решение а = (5; 0, 6; 0) — невырожденное опорное решение задачи

ft = (-6 + t)xx + (3 + t)x2 + (-11 + 2t)x3 + (1 0*4(min),

{

2xj + X2 ИЗ.х3 — 28, X^ "H X2 И" X^ x4 = 11,

xy>0, 7 =1,2, 3,4.

Симплекс-таблицу для данной задачи приведем к базису Av А3 опорного решения а:

Опорное решение а является оптимальным решением данной задачи тогда и только тогда, когда

-4 -1 < 0, Гґ > —4,

2?-5<0 °{?<5/2,

т.е. Д(ос) = [-4; 5/2]. При этом/Да) = 17?96. •

Если параметрическая задача линейного программирования (9.44)—(9.46) имеет непустое допустимое множество, то существуют опорные решения этой задачи av а2,о^ такие, что:

пересечение множеств Д(ос.) и А(ау), і Ф j, является либо пустым, либо состоит из единственной точки;

s

если t й (jA(a,-), то целевая функция задачи (9.44)—(9.46) не ограничена снизу на допустимом множестве.

252

Существует специальный алгоритм, позволяющий за конечное число шагов найти эти опорные решения ос. (г = 1, 2,s) и определить соответствующие множества A(af).