§ 67, Транспортная задача
Въ,... причём в качестве критерия оптимальности использовать минимальную стоимость перевозок груза.
Обозначим:
ау — наличие груза в і^-ом пункте отправления, v — 1, m;
bjі — величина потребности в этом грузе S /J-ТОМ пункте назначения, « — 1, ті ;
Сиц — стоимость перевозни единицы груза нз ^-того пункта в д-тын пункт {тариф перевозки);
XVp — количество груза, доставляемого из у-того пункта в ji-тый пункт, Xvu ^ О
m Tt
Целевая функция F — JZ Ovftx4i.
Требуется Определить план перевозки из пунктов отправления в пункты назначения так, чтобы:
вывести все грузи от поставщиков;
удовлетворить спрос каждого потребителя;
обеспечить миЕгимальиые суммарные транспортные расходы на перевозку груза, т.
е. найти F^n.Итак: найти минимальное значение функции
щ п
(1)
fi^Vtt
прн условиях
(2)
f=l
n
— Qvi
v — 1, m.
Всякое неотрицательное решение систем уравнений (2), (3), определяемое матрицей X — (л:^}, называется кланом транспортной задачи.
План, при котором функция (1) принимает своё минимальное значение, называется оптимальным планом
Для того, чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы суммарный объём груза у поставщиков был ранен суммарной потребности потребителей
m
53 - S V [1 = 1
jJXX
6)4
Линейное jypoepu-нм ирование
TpaHcnopTfjan задача, удовлетворяющая условию (5), пазыыается закрытой. Если же (5) не выполняется, то задача назыаастся открытой. Если задача открытая, то необходимо вэести либо фиктивного поставщика. либо фиктивного потребителя, Тарифы фиктивного поставщика либо фиктивного потребителя полагаем равными нулю.
Число переменных равно п ¦ тп.
При выполнении условия (5), число линейно независимых уравнений равно т + ті — 1. План транспортной задачи, имеющей не более (т + п — 1) отличных от нуля величин называется опорным. Если в опорном плане число отличных от нуля компонент равно и точности (яг+п — 1), то план является невырожденным, если мсныие, то план называется вырожденным.Решение транспортной задачи в основном делится на два этапа.
Построение опорного плана.
Проверка построенного плана на оптимальность.
Для построения опорного плана существует несколько методов; метод северо-западного угла; метод минимального элемента; метод аппроксимации Фогеля и другие. Для проверки опорного плана на оп-тимальность также разработано несколько методов: метод потенциалов; метод дифференциальных рент и другие.
Рассмотрим построение опорного плана методом минимального элемента, а проверку опорного плана по оптимальности — методом потенциалов.
Задача ]. На базах А і, А2 имеется однородный груз в коли-честве ец —28. аз = 56, аз = 5G условных единиц. Этот груз требуется перевести в четыре магазина В\, іЗз, Bj соответственно в количестве (?i = 49т йт — 14, Ьз — 42, — 42 единиц груза. Стоимость доставки единицы груда с каждого пункта отправлена л в со от детству ющян лункт назначения задана матрицей тарифов {и ~ 1, 2Т3; ft — 1, 2, 3,4)
Составить план перевозок с минимальными транспортными издерж камц.
Решение. Проверяем необходимое и достаточное условия раэре щи мости задачи
з
= 28 + 56 + 56 = 140,
4
? = 49 + 14 + 42 Н-42 - 147.
Суммарная потребность груза в пунктах назначения превышает за-пасы груза на трёх базах. Модель задачи открытая. Вводим фиктивную базу Ai с запасом груза 147 - 140 = 7 условных единиц, Тарифы перевозок единицы груза из базы Ai во все магазины полагаем равными нулю. Составляем таблицу T-L
L Исиользуя метод минимального элемента матрицы удельных за-трат, строим первый опорный план (фиктивных потребителей к фиктивных поставщиков распределяем последними).
Среди тарифов наименьшим является С}4- В клетку с наименьшим тарифом заполняем максимально возможным объемом груза. При этом либо весь груз выве-зен нэ соответствующего поставщика (строку временно исключаем из распределения), либо полностью удовлетворяется потребность потребителя (столбец временно исключает из рассмотрения), ибо и то и другое (в этом случае временно исключаем из рассмотрения соответствующие строку н столбец). В клетку АіВа направляем максимально возможный груз. Он равен ггцп(42,28J = 28, Тогда — 28 и из базы Л\ весь груз вывезен, но потребность четвертого магазина не удовлетворена на 14 условных единиц. Строка Аі выходит из рассмотрения (па базе Лі груза нет). Из оставшихся тарифов наименьший Сгз- В клетку А2В3 направляем min(42; 56) — 42, При этом столбец Bs выходит из рассмотрения (потребность магазина удовлетворена полностью), а из базы А2 не вывезено 14 уелоаных единиц груза. Из оставшихся тарифов Наименьшими является С22 —Сы ~ С$2 Наилучшим из ннх является Саз- В клетку Л2В2 направляем груз тпін(14; 14} = 14. При этом выходит из рассмотрения строка /U н столбец В2 (на базе Л2 груза нет, магазин удовлетворен полностью). Из оставшихся та-рифов наименьший Сзі = 4. Б клетку Ai-Bj направляем груз, равный min(49; 5G) — 49. При этом потребность первого магазина удовлетворена полностью, а из третьей базы не еывезено 7 единиц груза. Этот нераспределённый груз направляем в клетку Л3В4 Потребность четвёртого магазина не удовлетворено на 7 единиц груза. Направляем от фиктивного поставщика — базы А< 7 условных единиц груза в клетку А\Ва. В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а ллая удозлетворяет системе ограничений (2)-(4). При этом значение целевой функция равноF — CliS 14 4* Сі2X22 С2^Х2Ц + СзіХзі + + СааХЦ ~
6L6
Линейное программирование
= 36 Н- 42 + 84 + 19G + 42 - 3922. Подсчитаем число занятых клеток таблицы Т-i, их 6, а должно быть 7П -h п — 1 = 4ч-4-1—7.
Следовательно, опорный план является вырожденным. Поэтому необходимо дополнить количество занятых клеток до числа гиЧ-п — 1, введя нуль в одну иэ свободных клеток. При построении опорного плана произошёл особый случай из- за одновременного вычёркивания строки А і и столбца В2 (вывели иэ временного рассмотрения столбец и строку, а заполнили только одну клетку, т. е. одна заполненная клетка утеряна). В этом случае нужно нуль направлять а клетку с лучшим тарифом (минимальным), расположенную либо в строке Л2, либо в столбце В2- Причем клетка, в которую направляем нуль, не должна образовывать с занятыми клет-ками замкнутого контура. Такими клетками являются Л2В4 (Сг4 — 3) и А3В2 (Сз2 = ЗУ, так как они не образуют с занятыми клетнамн замкнутого прямоугольного контура.Прямоугольный контур или цикл представляет собой замкнутую ломаную линию, состоящую из горизонтальных м вертикальных отрезков. Все вершины контура, кроме одной, должны находиться в занятых клетках таблицы. Для каждой свободной клетки может быть построен единственный контур, причём если ломаная линия, образующая кон-тур, пересекается, то точка самопересечения не является ьершинсй Формы замкнутых контуров могут быть разнообразны, в том числе н такие (точки А и В не являются вершинами).
л л
Рис. КО
Рис. J4J
Моль направляем, например, в клетку АъВа. Теперь первый опорный план является невырожденным.
3 Проверка опорного плана на оптимальность методом потенци-алов.
План транспортной задачи будет являться оптимальным, если су- шествует система т + п чисел гг.у, г^, удовлетворяющая условиям
(6)
vft — uv = Си і, при xvfl > оу Т'л — Up ^ CM/Jr при — 0.
Числа гі^ называются потенциалами соответственно пунктов назна-чения и пунктов потреблении. Потенциалу Uv, vfl являются переменна-
«6Ц
Є.І7
Транспортная задана
мн двойственной транспортной задачи и обозначают оценку единицы груза б пунктах отправления и назначения соответственно.
Обозначим ^ = Vfi _ Utj _ СЦ где 2V}X — оценка свободных клеток таблицы.
Если среди оценок нет положительных (задача поставлена на минимум), то опорный план является оптимальным. Потенциалы могу быть рассчитаны только для невырожденного плана.В системе (6) число переменных больше числа уравнении (vi + -f ті > т -і- тг — l)t поэтому система не определена имеет бесконечное множество решений. Одному из неизвестных tt*, % придадим произвольное значение (для простоты полагаем tii — 0). Тогда остальные потенцналь; определяются однозначно. Находим потенциалы Up. и itv по занятым клеткам, решая систему уравнений
щ = О,
^ - U2 = 2, УІ - О, + 2 - 2, lii-O, 1* = О,
— = її \>2~Ъ2 = 3:
Щ = ^ —
V4 = 1,
V2 - 1,
ЇЛ4 — Щ — G, v1 - ил = 4, 1 - щ = G, щ = -1, из = —5, Щ — -і.
va — t?j — О, г?4 — if 2 = З, 1 - «4 = О, U2 =
1L\ - 1,
u2 = -X
Заносим рассчитанные потенциалы в таблицу Т і и подсчитываем оценки Z^n свободных клеток Zuh = г>/4 — u„ — CVfl:
Z]і * —6, Zy> ~ —3, Z$2 = 3, Z\\ — -2, Z-2i — —3, = —2, 2Л j — 2| = 0, ^13 = — 1-
Опорный план является неоптимальним, так как Zзз = 3 > 0. Z33 = = 2 > 0, его можно улучшить, осуществив перераспределение груза.
Выбираем максимальную положительную оценку свободной клет-ки — Zzi-
4. Для клетки А$В2 строим прямоугольный контур и производим перераспределение груза поэтому контуру. Для этого расставляем знаки на вершинах контура. Расстановка знакос: вершинам контура, начиная от вершины, находящейся в свободной клетке, присваиваем поочерёдно знаки *+» и Будем называть эти клетки плюсовыми
и минусовыми. Из чисел стоящнх в минусовых клетках, выби-раем наименьшее, т.е. в = тш(14,7) = 7. Прибавляем 0 к объёмам грузов, стоящих в плюсовых клетках, и вычитаем из объёмов, стоящих и минусовых клетках. В результате получим новый опорный план, приведённый в таблице Т-2 прн = 571 и m — п — 1 = 7.
Если в минусовых клетках построенного прямоугольного контура находятся два или несколько одинаковых минимальных значения то при распределении груза освобождается две или несколько клеток, и план становится вырожденным.
Поэтому необходимо в одну мли несколько одновременно освобождающихся клеток направлять нули,причём нулей вводится столько, чтобы во вновь полученном ПЛІЙЄ число занятых клеток было раїано т + п— 1.
Если в оптимальном плане оценка для некоторой клетки ZWfl =&, то задача имеет множество оптимальных планов. Для клетки с ZUft^t\ можно построить контур и перераспределить груз. Тогда общий вид решения есть X ~ аЛТг + (1 - ct)A2 при 0 < а ^ 1.
Полученный в Т-2 план проверяем на оптимальность. Находнн потенциалы по занятым клеткам и заносим в таблицу. При этом оценки свободных клеток равны
Z\\ ss —3> Z\2 — — 3, — —1, Z41 = X, Zw - - I,
Z-2\ — О, 21Я = —2, Z34 = -3, Z42 ~ 0.
План неоптимальный, так как ?41 1 > 0, Строим контур для клетки A<\Bi таблицы Т-2. Новый план приведён в таблице Т-3. Этот плац вырожденный, так как в минусовых клетках контура таблицы Т-2 ва* ходились два одинаковых минимальных объёма груза. При распределе-нии клетка А4В1 з таблице Т-3 становится запятой, а две клетки Ajlij и Л4В4 — свободными. Число занятых клеток в Т-3 мєегьшє, чем ш + + тг — X, Для продолжения решегіия в одну из освободившихся клеток записываем нуль. Так как С22 > Слd, то нуль записываем в клетку Л4В4, F = 364. Проверяем план па оптимальность: Zn — —4, Z12 -Ч Zw Z21 -1, *= -1, Z33 = О, 2я4 <= -2, Z42 = ^43 = -1. Ви
оценки неположительные — план оптимальный
ТА «1 = -1 V2 ~ 1 иэ = 0 V4 ~ 1 Запаса ВІ Вл вА tii = 0 л, 5 4 2 1
28 2В и2 — —2 А-І 4 3 2 3 56 14 — 42 О из = —5 Аз 4
49 3 + 3 і б
7 56 1І4 = 1 А* 0 0 0 0
7 7 j Потребности 49 14 42 42 147 \
Т-2
11-і; X и, = 2 Vi = \ гд - 0 ил = Е Запасы Вг В* zi і = 0 Лі 5 А 2 1
28 28 IL-Л - -2 /Ь 4 7 3 2
42 + 3
7 56 u* S= -2 Аз 4 + 3 3 6 56 4<І — 7 Гі4 — 1 0 ч- 0 0 О
7 7 Потребности 49 14 42 42 \i47 Т-3 И.' ^^ ^1 = 1 Va =0 і* = 0 гм = 1 Запасы XvВц в, Въ Б* U] = 0 ЛІ Б 4 2 1
S8 23 г^З — л2 4 3 2
42 3
14 56 «з ~ Л3 4
42 3
14 3 е і
56 Vd - 1 А4 7 О 0 О
0 7 Потребности 49 14 42 42 \147 147 \
/О О О 2S \
0 0 42 14 t F3 = Ртіґ1 = 364 V 42 14 0 0 )
Анализ штана.
Общая стоимость доставки груза потребителям будет минимальной и сасТавит ft = 364 при осуществлении следующего плана: из первой базы необходимо весь груз направить в четвёртый магазин; из второй базы направить в третий 42 усл. ед, и в четвертый — 14 уел, ед.р а груз с третьей базы — в первый 42 усл. ед, и во второй 14 уел ед. При этом плане потребность первого магазина останется неудовлетворённой в размере 7 усл. ед
Задание. В задачах 2 и 3 проверить вычисления.
Задача 2. {см, условие задачи 1),
bi Ьі Ьг Ьл
к
130, 250, 170, 100, 300,
280, 320, 240, 160,
( 2 9 4 10 б \
CVfX —
7 3 0 5 0
5 2 17 8
V 11 6 2 3 4 )
Ответ: Fniin = 1590, 0 100 0 0 \ 10 10 0 300 240 0 0 0 -і
0 60 100 0 j ( 130
о о
V 0
К vp
Задача 3.
( bi ЬІ Ьз h ч h
G00,
625,
1625,
1250,
1000,
Сі,}! —
а\ - 1000, = 2250, а3 = 1250,
5 S 7 10 З 4 2 2 5 6 7 3 5 9 2
Ответ: Fmin = 14250,
XUft —
500 0 0 0 500 0 0 1500 750 0 0 625 125 0 500 620
Т-], задача 2 VI V2 =9 г'з — 6 V4 = Б - 6 v&-0 Запасы і
і Ха, 1ЗІ в7 ВІ в4 В, в. Ui — 0 Л\ 2
130 9
10 4 10 6
90 О
50 ¦
280 U2 = Є Аз 7 3 17 0
а 5 О
150 О 320 — + иэ = 7 Лэ 5 2
240 і 7 8 О 240 U4 = 2 Ал 11 6 * 2
+ 3
100 4
60 О 160 Потребности 130 250 170 100 300 50 \lODO 1000 \
Т-2, задача 2
tit, \ vi =2 v2 - 9 из к 6 v4 — 7 us — 6 ш - о Запасы вг в2 вг в4 вь Be 1i! =0 ах 2
130 10 4 10 6 0
50 280 + ™ 90 - б л2 7 3 110 0 5 + 0 210 0 320 из =7 аз 5 2
240 г 7 S 0 240 U4 — 2 а4 11 6 2
60 3
100 4 0 60 Потребности 130 250 J70 100 300 50 \100G
юоо\
522 Линейное программирование __ [ Гл. X
Т-3, задача 2 tiu X иі = 2 V2~9 vt — 4 Щ = 5 — - Щ|5 = 4 щ - 0 -
Запасы AyN. Яі в2 в6 Be Ui =С /її ї
130 9 4 10 б 0
50 2 SO 10 + 90 из = 6 Ля 7
.... 3 + 0 20 5 0
300 0 320 іід » 7 j4g 5і 2
240 I 7 8 0 240
і ЇІ4 — 4 11 6 2
60 3
J0O 4 0 L6Q Потре С ІНОСТИ L ЗО 250 170 100 300 50 іооо\
Т-4, задача 2
О.Ы N4 vi — 2 t12 7 ^з — 4 я* = 5 fljj = 4
be = 0 Запасы Bi Bj B4 Be; № — 0 Лі 2
130 9 4
100 10 "if 0
50 280 .-J
II 7 3
10 0
10 5 0
300 0 1
320
| гіз = 5 Лэ 5 2
240 1 7 a 0 240 14 = 2 .44 11 G 2
GO 3
і 00 6 160 Потребности 130 250 170 LOO 300 50
Т-1 „ задача Э
vi = 5 vz =7 uj - 7 VA 10 V5 = 3 Запасы А/Х в, -В* Яэ BG m -0 Ai 5
500 8 7 10
500 3 1000 шг = 5 Ла 4 625 2
1625 5
0 6 2250 — + из — 1 А3 7 3
+ 5 - 9
250 2
1000 1250 - 10 А, 0 0 0 0
500 0 500 Потребности 500 625 1625 1250 1000 \SOOQ 5000 \ Т-2, задача 3 ul = 5 — 7 v3 = 7 Vi - 10 г>5 — 6 1 , Запасы Bi Bi Вь BR L!1 = 0 Ai 5
500 S 7 10 3 [ООО 500 + из = 5 А* 4 a
375 2
1625 5
250
+ 6 2250 := 4 Аз 7 3 + 5 — 2
D00 1250 250 1 и 4 — Ю 0 0 0 0
500 0 500 Потребности 500 625 1625 1250 1000 \5000
5000 \,
Т-3, задача 3
ьі = 5 — 4 Ь'з = 7 щ - 10 Запись: Bx в* Вэ Bs *
| ui А\ 5
500 в 7 10 3 1000 125 375 П2 — 5 А2 4 2 2
1625 - 5
625 6 2250 из Аз 7 3
625 5 + 9 — 2
325 1250 U4 = 10 Ai 0 0 0 0
500 0 500
- Потребности .500 625 1625 1250 1000 \sooo
5000\ Т-4, задача 3 Uy ^^ ui ~ 5 V2 — 4 V3 = 6 ш = Э — 3 Запасы
¦ Bi Ss ве 1*1 = 0 /її 5
500 8 7 10 3
500 1
1000 «2 — 4 Аэ 4 2 2
j SOD 5
750 й 2250 ЇІЗ ~ 1 Лэ 7 3
625 5
125 9 2
500 1250 щ - Q 0 0 0 0
500 0 5QQ Потребности ! 500 625 1625 1250 І000 Й000\
Вопросы для самопроверки
Сформулируйте транспортную задачу и запишите её математическую модель.
Перечислите основные этапы решения транспортной задачи.
Зг Каковы необходимое и достаточное условия разрешимости транс-портной задачи?
Какая транспортная задача называется открытой; зак(эытой?
Как строится первый опорный план транспортной задачи методом минимального элемента матрицы тарифов?
В чём заключается опорность плана транспортной за дач и г
В каком случае опорной план транспортной задачи янляегся оп-тимальным?
Как выбирается клетка распределительной таблицы, в которую необходимо напраьить груз при переходе к новому опорному плану?
Как определяется объём передвигаемого по контуру грузе
Как осуществляется переход к новому опорному плану?
[ 1. Каковы особые случаи при решении транспортной задачи методом потенциалов?
J2ч В каких случаях транспортная задача имеет множество опти-мальных планов?
Упражнения
Задача 4. (см, условие задачи I)
13 5 2 Є
9 S 4
і
13 \
19 17
& /
/18 7
9
\ 14
Ov j? —
di = 284, а2 = 566, аз = 170, аА ая 280, bi - 145t b2 - 625, b3 = 200, Ьа ~ 300,
j 0 34 145 421
0 0 0
200
220 \ 0 0
80 /
Ответ: Fmin >= 8642, X= Хга + X2(l 1
Xx =
x2
0 0
170 0
/ 0 0 0 220 \ 145 421 0 0 0 170 0 0
V 0 34 200 80 /
Задача 5.
( ai~ 3120j ai = 2880, ад = 1290, t 510, f5 8 11 6 ) 8 23 4 7 7 19 3 5 \ 11 8 5 4/ С у fj, =