Бережная_Матметоды моделирования эк cистем
.pdfГлава 8
Транспортные задачи линейного программирования
8 . 1 . Постановка задачи
Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них яв ляется, как правило, распределение ресурсов, находящихся у т производителей (поставщиков), по п потребителям этих ресурсов.
На автомобильном транспорте наиболее часто встречаются сле дующие задачи, относящиеся к транспортным:
•прикрепление потребителей ресурса к производителям;
•привязка пунктов отправления к пунктам назначения;
•взаимная привязка грузопотоков прямого и обратного на правлений;
•отдельные задачи оптимальной загрузки промышленного обо рудования;
•оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются т пунктов отправления груза и объемы отправления по каждому пункту а^, ^2»
..., а^. Известна потребность в грузах ftj, bi, ..., 6^ по каждому из п пунктов назначения. Задана матрица стоимостей доставки по
каждому варианту Су, / = |
l,/w,y = 1,/7. |
Необходимо рассчитать оп- |
|||
|
|
Исходные данные |
Таблица 8.1 |
||
|
|
|
|||
|
|
Потребители |
|
Запасы |
|
Поставщики |
Вх |
Вг |
... |
|
(объемы |
|
Вп |
отправления) |
|||
Ах |
|
Си |
|
|
а\ |
|
|
Хп |
|
Х\п |
|
Лг |
|
Си |
|
^2п |
|
|
Х2\ |
|
|
Х2п |
«2 |
|
|
... |
|
|
\ |
^т |
|
Ст2 |
|
|
От |
|
ХщХ |
Хт2 |
|
Хщп |
|
|
|
|
|||
Потребность |
h |
Ьг |
|
Ьп |
|
270
тимальныи план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого /-го пункта отправления (от поставщи ка) в каждый у-й пункт назначения (до потребителя) x^y с мини мальными транспортными издержками.
В общем виде исходные данные представлены в табл. 8.1. Транспортная задача называется закрытой, если суммарный
объем отправляемых грузов | Y, Щ равен суммарному объему по-
.'=1 )
( п
требности в этих грузах по пунктам назначения Z6y
и=1 )
т |
п |
(8.1) |
laj='Zbj. |
||
/=1 |
у=1 |
|
Если такого равенства нет (потребности выше запасов или на оборот), задачу называют открытой, т. е.:
т |
п |
|
I^aj^^bj, |
(8.2) |
|
/=1 |
У=1 |
|
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений.
Все грузы из / пунктов должны быть отправлены, т. е.:
п |
|
Y^Xij^Gi, / = l,m. |
(8.3) |
Все у пункты (потребители) должны быть обеспечены грузами в плановом объеме:
т—
lxij=bj, |
J = ln, |
(8.4) |
/=l
Суммарные объемы отправления должны равняться суммар ным объемам назначения:
т |
п |
|
lai |
= Xbj. |
(8.5) |
/=1 |
у=1 |
|
Должно выполняться условие неотрицательности переменных: Ху > О, / = 1,/я; j = 1,и. Перевозки необходимо осуществить с ми нимальными транспортными издержками (функция цели):
271
т п |
|
Zmin = S S ^/y^/y- |
(8-6) |
/=ly=l |
|
В модели (8.3) — (8.6) вместо матрицы стоимостей перевозок (су) могут задаваться матрицы расстояний. В таком случае в каче стве целевой функции рассматривается минимум суммарной транс портной работы. Как видно из выражения (8.5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если
•потребности по пунктам назначения превышают запасы пунк тов отправления, то вводится фиктивный поставщик с недостаю щим объемом отправления;
•запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом по требления.
Варианты, связывающие фиктивные пункты с реальными, име ют нулевые оценки. После введения фиктивных пунктов задача ре шается как закрытая.
Транспортным задачам присущи следующие особенности:
•распределению подлежат однородные ресурсы;
•условия задачи описываются только уравнениями;
•все переменные выражаются в одинаковых единицах измере
ния;
•во всех уравнениях коэффициенты при неизвестных равны единице;
•каждая неизвестная встречается только в двух уравнениях си стемы ограничений.
Транспортные задачи могут решаться симплекс-методом. Одна ко перечисленные особенности позволяют для транспортных задач применять более простые методы решения.
8.2. Алгоритм метода потенциалов
Наиболее распространенным методом решения транспортных задач является метод потенциалов.
Решение задачи методом потенциалов включает следующие
этапы:
1)разработку начального плана (опорного решения);
2)расчет потенциалов;
3)проверку плана на оптимальность;
4)поиск максимального звена неоптимальности (если условие
п.3 не было достигнуто);
5)составление контура перераспределения ресурсов;
272
6)определение минимального элемента в контуре перераспре деления и перераспределение ресурсов по контуру;
7)получение нового плана.
Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный ал горитм для каждой итерации не меняется.
Для транспортной задачи существует несколько методов отыс кания начального плана (опорного решения):
•метод северо-западного угла;
•метод минимальной стоимости;
•метод двойного предпочтения и т. д.
Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов от правления / = 1,3 к пунктам назначения у = 1,4. В соответствии с принятыми в подразд. 8.1 обозначениями исходные данные задачи приведены в табл. 8.2.
|
|
|
Исходные данные |
|
Таблица 8.2 |
|
|
|
|
|
|
||
|
Поставщики |
|
Потребители |
|
Запасы |
|
|
B^ |
Вг |
|
В, |
||
|
|
^3 |
|
|||
1 |
^\ |
1 |
2 |
3 |
4 |
60 |
|
|
4 |
3 |
2 |
0 |
80 |
|
|
0 |
2 |
2 |
1 |
100 |
|
Потребность |
40 |
60 |
80 |
60 |
240 |
Начальный план можно составить одним из перечисленных вы ше методов. Воспользуемся наиболее простым методом - методом северо-западного угла, В соответствии с этим методом загрузка кле ток (распределение объемов пунктов отправления по пунктам на значения) начинается с верхней левой клетки («северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали).
По указанному правилу загружаем первую клетку (/ - у) = = (1 — 1) на основе следующего условия:
Хц = min {ах\ Ъ{\ = min {60; 40} = 40.
Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза A^i = 60 — 40 = 20, кото рые и распределяем на второй пункт назначения:
Ху1 = min {AtZj; Ъ-^ = min {20; 60} = 20; А62 = 40.
273
Продолжая преобразования аналогичным образом, получаем: ^22 = min {^2; АЙ2} "^ ^^^ {80; 40} = 40; AZ?2 = 40 и т д.
Результаты начального плана и расчета потенциалов представ лены в табл. 8.3.
Таблица 8.3
Начальный план перевозок
Поставщики |
|
|
Потребители |
|
Запасы |
ОС/ |
||
|
|
В2 |
|
Вз |
|
|||
|
|
^1 |
|
^4 |
|
|
||
|
|
I |
2 |
|
3 |
|
4 |
|
^1 |
Р |
40 |
20 3 |
|
40 |
|
60 |
0 |
А2 |
f |
~~^ |
40 Р |
|
|
80 |
1 |
|
|
|
|
[з_ 3 |
2 |
|
0 |
|
|
|
|
|
|
|
|
|
||
Ai |
ф |
0 |
2 |
р |
2 |
|
1 |
1 |
3 ^ |
|
|
40 |
60 |
100 |
|||
|
|
|
|
|
|
|
|
|
Потребность |
|
40 |
60 |
|
80 |
60 |
240 |
|
Р/ |
1 |
1 |
2 |
|
1 |
0 |
|
|
В процессе решения после каждой итерации (в том числе и по сле получения допустимого решения) по загруженным клеткам про веряется выполнение следуюш^его условия:
N = т + п — 1. |
(8.7) |
В нашем примере /w = 3, л = 4, а число загруженных клеток равно 6, т. е. соответствует условию (8.7): Л^=3 + 4 - 1 = 6. Если условие (8.7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько ну лей, чтобы с их учетом выполнялось условие (8.7). Клетка, в кото рой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана
^ = S X с.-х.. =1-40 + 2.20 + 3.40 + 2.40 + 2-40 + 1-60 = 420 д.е.
/=1у=1
Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:
274
«/• + р/ = <^ij> |
(8.8) |
где tt/ — потенциал /-й строки; Ру -- потенциал у-го столбца.
Вычисляя потенциалы по выражению (8.8), принимаем для пер вой строки aj = 0. Используя зафуженные клетки (/ ~У) = (1 — 1), (1 — 2), получаем:
ai + pi = сн = О + pi = 1; Pi = 1; ai + р2 = Ci2 = О + Р2 = 2; Р2 = 2.
Далее по загруженным клеткам ( 2 - 2 ) , (2 3) определяем другие потенциалы:
а2 + Р2 = 3; а2 + 2 = 3; а2 = 1; а2 + Рз = 2; 1 + Рз = 2; Рз = L
Результаты расчета потенциалов представлены в табл 8.3. Проверяем план на оптимальность по незагруженным клеткам,
используя следующее неравенство:
ОС/ + Ру < Cij, |
(8.9) |
Если для незагруженных клеток условие (8.9) выполняется, то план — оптимальный. По табл. 8.3 осуществляем проверку началь ного плана на оптимальность:
-J) = (1-3), |
0 + 1 <3; |
|
-J) = (1-4), |
0 + 0 < 4; |
|
-J) = (2-1), |
1 |
+ 1 < 4; |
-У) = (2-4), |
1 |
+ 0 > 0, |
-J) = (3-1), |
1 |
+ 1 > 0, |
•J) = (3-2), |
1 |
+ 2 > 2, |
AC24 = 1;
AC31 = 2;
Дс32 1.
Итак, по трем клеткам условие (8.9) не выполняется, следова тельно, начальный план требует улучшения. Характеристики Ас,у показывают размер экономии транспортных издержек на 1 ед. пе ревозимого груза. В нашем примере наибольшую экономию можно получить по клетке (/ -j) = (3 — 1), где Дсз1 = 2 > {АС24; Асзг}- Сле довательно, клетку (3-1) необходимо загрузить за счет перераспре деления ресурсов из других зафуженных клеток. В табл. 8.3 клетку (3—1) помечаем знаком «+», так как здесь в начальном плане нахо дится вершина максимальной неоптимальности.
275
Контур перераспределения ресурсов составляют по следующим правилам:
•этот контур представляет замкнутый многоугольник с верши нами в загруженных клетках, за исключением клетки с вершиной максимальной неоптимальности «+», и звеньями, лежащими вдоль строк и столбцов матрицы;
•ломаная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной цепи (по строке или по столбцу);
•в каждой вершине контура встречаются только два звена, од но из них располагается по строке, другое — по столбцу;
•число вершин контура четное, все они в процессе перерас пределения делятся на загружаемые и разфужаемые;
•в каждой строке (столбце) имеются две вершины: одна — за гружаемая, другая — разфужаемая.
В этой клетке намечаем одну из вершин контура и далее по вы шеизложенным правилам строим контур, вершины которого будут
находиться в клетках (3-1) - (1-1) - (1-2) - (2-2) - (2-3) -
— (3—3). Вершины контура последовательно подразделяем на за гружаемые (3) и разгружаемые (Р), начиная с вершины максималь ной неоптимальности «+» (табл. 8.3).
Перераспределение ресурсов по контуру осуществляется с це лью получения оптимального плана. В процессе перераспределе ния ресурсов по контуру в соответствии с условием неотрицатель ности переменных х^ ни одно из этих значений не должно превра титься в отрицательное число. Поэтому анализируют только клет ки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере ^^in ~ niin{40; 40; 40} = 40. Следовательно, клетки (1-1), (2-2), (3-3) полностью разфужаются. В клетке (1—2) загрузка увеличится на 40 и достиг нет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3-1) загрузится на 40 (табл. 8.4).
Проверяем условие N=m-^n — I. В нашем примере w = 3, л = 4, а число зафуженных клеток равно 4, т. е. условие не выпол няется и 6 ?t 4. В процессе перераспределения ресурсов произошла полная разфузка трех клеток, а мы должны освободить только од ну клетку. В этом случае следует в две клетки проставить нули (ну левой ресурс) и считать условно их загруженными. Например, в клетки (1—1) и (3—3) проставим нулевой ресурс (рис. 8.4). Получе ние нового плана (итерации) осуществляется в том же порядке, ко торый был рассмотрен выше, т. е.
• по зафуженным клеткам (в соответствии с новой зафузкой) вычисляются потенциалы а,- и Р,-;
276
Таблица 8.4
|
|
Первый план перевозок |
|
|
|
||
|
Поставщики |
|
Потребители |
|
Запасы |
«/ |
|
|
Bi |
Вг |
Вг |
В, |
|||
|
|
|
|
||||
|
|
1 |
2 |
3 |
|
4 |
|
|
Ai |
0 |
60 |
|
е |
60 |
0 |
|
|
4 |
3 |
2 |
0 |
|
|
|
Ai |
|
|
80 Р^ |
3 |
80 |
- 1 |
|
|
0 |
2 |
2 |
1 |
1 |
|
|
Аз |
40 |
|
0 - |
р 60 |
100 |
- 1 |
|
Потребность |
40 |
60 |
80 |
60 |
240 |
|
! |
Р; |
1 |
2 |
3 1 |
2 |
|
|
•по незагруженным клеткам производится проверка плана на оптимальность;
•находится вершина максимальной неоптимальности и стро ится новый контур перераспределения и т. д., до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенст ву (8.9).
По результатам первой итерации имеем
тп
г= Ъ Хс«х»=2-60 + 2-80 + 1-60 + 0-40 = 340.
/=1У=1
Ниже приведены расчеты по второй итерации и оптимальный план.
Поиск потенциалов следующий:
«1 + Pi = 1 а, + Рз = 2 ttj + Рз = 2: аз + PI = О аз + Рз = 2
«3 + Р4 = 1
О + р, = 1 |
Pi = |
l; |
|
О + Рз = 2 |
Р2 = 2; |
||
аг + 3 = 2 |
«2 = |
- 1 ; |
|
аз + 1 = О |
«3 = |
- 1 ; |
|
-1 |
+ Рз = 2 |
Рз = 3; |
|
-1 |
+ Р4 = 1 |
Р4 = 2. |
|
Проведем проверку на оптимальность:
0 - у ) = (1-3);0 + 3<3; (/ - /) = (1-4);0 + 2 < 4 ; (/-у-) = (2-1); 1 - К 4;
277
(/-у) = (2-2); 2 - 1 <3; (/-У) = (3-2); 2 - 1 <2; (/-У) = (2-4); 2 - 1 >0.
Клетку (2—4) необходимо загрузить.
В соответствии с перераспределением ресурсов по контуру по лучаем табл. 8.5, для которой вновь рассчитываем потенциалы а/ и Ру, и последовательность вычислений повторяется.
|
Оптимальный план перевозок |
||||
Поставщики |
|
Потребители |
|
||
B^ |
Вг |
Вг |
^4 |
||
|
|||||
|
1 |
2 |
3 |
4 |
|
/«. |
0 |
60 |
|
0 |
|
|
4 |
3 |
2 |
||
А2 |
|
|
20 |
60 |
|
|
0 |
2 |
2 |
1 |
|
Ai |
40 |
|
60 |
|
|
Потребность |
40 |
60 |
80 |
60 |
|
ft |
1 |
2 |
3 |
1 |
|
Таблица 8.5
Запасы |
а, |
60 |
0 |
80 |
- 1 |
100 |
- 1 |
240 |
|
Для распределения, полученного в табл. 8.5, условие а^- + Ру < Су выполняется, следовательно, план — оптимальный.
Транспортные издержки по оптимальному плану следующие:
тп
^= S Е СуХу =10 + 2-60 + 2-20 + 0.60 + 0-40-+-2.60 = 280 д.е.
/=1у=1
Таким образом, построением начального плана с последующим расчетом двух итераций получено оптимальное решение по при креплению пунктов отправления грузов к пунктам назначения.
8.3. Усложненные задачи транспортного типа
Нами рассмотрена классическая транспортная задача, на кото рой показано, как используется метод потенциалов для нахожде ния оптимального плана. В экономике предприятия такие задачи встречаются крайне редко. Обычно при составлении экономико-
278
математической модели в задачи транспортного типа приходится вводить целый ряд дополнительных ограничений, а затем пользо ваться методом потенциалов.
Ряд экономических задач легко сводимы к транспортной задаче. Рассмотрим наиболее часто встречающиеся ситуации в экономике предприятия,
1. Отдельные поставки от определенных поставщиков некото рым потребителям должны быть исключены (из-за отсутствия не обходимых условий хранения, чрезмерной перегрузки коммуника ций и т. д.). Это ограничение требует, чтобы в матрице перевозок, содержащей оптимальный план, определенные клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки Су в клетках, перевозки через которые следует запретить. При этом производят завышение величины Су до таких значений, которые будут заведомо больше всех, с которыми их придется сравнивать в процессе решения задачи.
2.На предприятии необходимо определить минимальные сум марные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных
соптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестои мости. В таких задачах за критерий оптимальности принимают сум му затрат на производство и транспортировку продукции.
3.Ряд транспортных маршрутов, по которым необходимо до ставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A^BJ можно Провести не более q еди
ниц груза, то Bj столбец матрицы разбивается на два столбца — B'j и ву В первом столбце спрос принимается равным разности между действительным спросом bj и ограничением q: b'j = bj — q, во втором — равным ограничению ^, т. е. й'у = q. Затраты су в обоих столбцах одинаковы и равны данным, но в первом столбце Rj, в клетке, соответствующей ограничению /, вместо истинного тарифа Су ставится искусственно завышенный тариф М (клетка блокирует ся). Затем задача решается обычным способом.
4.Поставки по определенным маршрутам обязательны и долж ны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с уче том обязательных поставок.
5.Экономическая задача не является транспортной, но в мате матическом отношении подобна транспортной, так как описывает ся аналогичной моделью, например распределение производства
279