Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

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.,

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

О Пример. Рассмотрим опорное решение а, ненулевые координаты которого записаны в транспортную таблицу (табл. 9.7).

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

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

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

 

4

3

6

4

40

1

6

2

8

30

2

4

5

7

20

30

25

15

20

»j

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

 

 

1

3

2

4

0

4

3

20

6

4

20

0

1

15

6

2

15

8

1

2

15

4

5

5

7

В последней таблице записан оптимальный план перевозок, стоимость которых составляет 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 опорного решения а:

 

*1

х2

хг

*4

*1

х2

 

*4

 

2

1

3

0

28

0

-1

1

2

6

 

 

 

 

 

 

 

 

 

 

1

1

1

-1

11

1

2

0

-3

5

6-t

-3-t

11-2?

?-1

0

6-t

-3-і

11-2?

?-1

0

 

 

х2

х3

*4

 

0

-1

1

2

6

1

2

0

-3

5

0

^-?

0

2?-5

17?-96

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

-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).

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |