МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

2. ТРАНСПОРТНАЯ ЗАДАЧА

Среди ЗЛП особое место занимает транспортная задача (ТЗ). Это обусловлено, с одной стороны, практической значимостью последней. С другой стороны, ТЗ имеет такие специфические особенности, которые позволяют существенно упростить общие методы решения применительно к этой конкретной задаче.

Транспортная   задача   формулируется   следующим образом.

Имеется  т  поставщиков   / 'і. /1>...../ ',„   однородной продукции.

Максимальные объемы поставок продукции заданы и равны щ, і = 1,2,...,т. Эта продукция используется п потребителями. Объемы потребностей заданы и равны bj, j = 1,2,...,п. Стоимость перевозки единицы продукции от г-го поставщика к j-му потребителю известна для всех і = 1,2, ...,т и j = 1,2,... ,п и равна су. Требуется установить такие объемы перевозок ж у от каждого поставщика Р, (г = 1,2,..., т) к каждому потребителю Qj (j = 1,2,... ,п), чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были удовлетворены (если это возможно).

Математическая модель задачи имеет вид

т

п

(2.1)

i=i j=i

п

г = 1,2,... ,т;

3=1

(2.2)

т

П

г=1

Хц > О і = 1,2,... ,т 3 = 1,2 п.

35

Если, кроме того, выполняется условие

т п

1=1 j=l

то имеем так называемую закрытую (сбалансированную) ТЗ.

Основные свойства закрытой ТЗ

1. Задача в любом случае допустима и разрешима.

2. Среди уравнений-ограничений (2.2) лишь т + п — 1 линейно независимых.

3. Если в ТЗ все числа а, (і = 1,2,... ,т) и bj (j = 1,2,...,п) целые, то хотя бы одно оптимальное решение задачи целочисленное.

При решении ТЗ, как и любой ЗЛП, базисные решения — вершины допустимого многогранника — играют особую роль. В силу общих определений и с учетом второго свойства можно заключить, что невырожденное базисное решение ТЗ содержит ровно т + п — 1 ненулевых перевозок агу. В вырожденном случае базисное решение ТЗ содержит менее т + п — 1 ненулевых перевозок.

Данные ТЗ и вычисления, связанные с решением задачи, заносят в транспортную таблицу. От обычной симплекс-таблицы она отличается тем, что в ней заполнены лишь те клетки где перевозки Xij > 0. Такие клетки называются занятыми, остальные — свободными. Очевидно, что для невырожденного случая занятых клеток будет т + п — 1.

Исходная транспортная таблица имеет такой вид.

36

В последнем столбце таблицы приведена информация о возможностях поставщиков, в последней строке — о потребностях потребителей. В остальных клетках помещена стоимость перевозок су, і = 1,2,..., т; j = 1,2,..., п и, кроме того, в т + п — 1 клетках также записываются значения ж у > 0.

Для ТЗ в силу ее специфики найти начальное базисное решение проще, чем для обычной ЗЛП. Приведем два возможных, широко используемых на практике метода построения начального базисного решения ТЗ.

Метод северо-западного угла. Заполняют ненулевыми перевозками транспортную таблицу начиная с ее верхней левой (северозападной) клетки. При этом распределяют продукцию первого поставщика, максимально удовлетворяя первого потребителя, затем второго и т. д. до полного распределения продукции первого поставщика. Если в каком-либо пункте Qi спрос не был удовлетворен, то поставки осуществляются от второго поставщика, затем третьего и т. д. до полного удовлетворения спроса. Разумеется, если потребности в пунктах Qi, Q2, ■ ■ ■ выполнены или полностью распределена продукция поставщиков Pi, Р2,..., то соответствующие потребители и поставщики уже не участвуют в распределении. Занятые клетки транспортной таблицы имеют характерную ступенчатую форму (начало "ступенек" находится в верхнем левом углу таблицы, конец — в нижнем правом углу). Сумма перевозок в г-й строке равна щ, сумма перевозок в j-м столбце — bj.

Очевидно, полученный таким образом план перевозок образует допустимое решение ТЗ.

Пример 1. Продукцию поставщиков Р\. /'_>. /'» с возможностями а = {10,15,7} необходимо распределить между потребителями Qi, Q2, Qi с потребностям {3; 5; 10; 14}.

Воспользуемся следующей транспортной таблицей.

 

Qi       Q-2        Qi Qa

a.

Pi

 

ai = 10

Pi

 

a-2 = 15

Рз

 

a3 = 7

bj

bi=3    b2 = 5    Ьз = 10    b4 = 14

 

После распределения продукции по методу северо-западного угла получим решение ТЗ.

37

 

Qi

g2

 

Qa

a.

Pi

3

5

2

 

ai = 10

p2

 

 

8

7

a-2 = 15

Рз

 

 

 

7

a3 = 7

h

bi = 3

h = 5

Ьз = 10

Ьа = 14

 

Заметим, что в рассмотренном методе не использовалась матрица С транспортных издержек. Поэтому начальное допустимое базисное решение, построенное по методу северо-западного угла, обычно далеко от оптимального. В предлагаемом далее методе начальное решение строится с использованием информации о транспортных издержках.

Метод минимального элемента. Идея метода состоит в том, чтобы максимально загрузить перевозками коммуникации с минимальными транспортными издержками. Здесь в отличие от предыдущего метода таблицу заполняем вразброс начиная с наиболее "дешевых" клеток.

Метод реализуется следующим образом. На первом шаге определяем минимальный элемент матрицы С. Пусть это будет ^. Полагаем = тт(а^, fojj). Возможны два случая: 1) < (возможности щг поставщика Ру меньшие, чем потребности bjt потребителя Qj1; 2) a,j > bj2 (наоборот). Тогда в первом случае нулями заполняется строка ii, кроме элемента ji, а во втором — столбец ji, кроме элемента i\, и в дальнейшем в вычислениях не участвует поставщик Ріг (в случае 1) или потребитель Qjt (в случае 2). На втором шаге из матрицы С вычеркиваем соответствующую строку или столбец. Получаем матрицу        Полагаем также

(і) _ Ja», і Ф к,

аг    ~ \      _ • _ • .

ь(1) =ІЧ', зФЗи (bj ~ xiijn      3 = ЗіВторой шаг — выполнение описанных на первом шаге операций применительно к матрице и величинам и Ь^\ Следующие шаги продолжаются до полного заполнения транспортной таблицы (или вычеркивания строк (столбцов) матрицы С).

38

Пример 2. Пусть для рассматриваемой далее задачи с а = {10; 15; 7} и Ь = {3; 5; 10; 14} матрица транспортных издержек имеет вид

/ 2   4   3   7 \ С=     3   6   3   5 . \ 2   2   5   4 /

Тогда построение начального базисного решения по методу минимального элемента выполняется следующим образом.

 

Qi

Q2

Яз

Qa

а.

 

а<2>

а(3) а(4)

 

Pi

3

 

7

 

10

7

7

0 0

0

р2

 

 

3

12

15

15

15

15 12

0

Рз

 

5

 

2

7

7

2

2 2

0

h

3

5

10

14

 

 

 

 

 

Ь(і)

0

5

10

14

 

 

 

 

 

Ь(2)

0

0

10

14

 

 

 

 

 

Ь(3)

0

0

3

14

 

 

 

 

 

Ь(4)

0

0

0

14

 

 

 

 

 

Ь(5)

0

0

0

0

 

 

 

 

 

ычеркивания в матрице С

выполняют в следующем порядк

 

 

 

 

4

_

®3 -

_ 7

—   3-й шаг

 

 

 

3

 

6

 

®4

5

—   6-й шаг

 

С =

2

 

©2

 

5

4

—   5-й шаг

 

1-й 2-й 4-й

шаг       шаг шаг

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

39

Метод потенциалов решения транспортной задачи

Пусть «j и Vj — потенциалы пункта соответственно Р, и Qj (і = 1,2,... ,m; j = 1,2,... ,n). Назовем величину су — (ty — «,) = = Ay относительной оценкой переменной жу. Тогда базисное решение X = \\xij\\, і = 1,2, ...,m; j = 1,2, ...,п оптимально тогда и только тогда, когда существуют потенциалы «, и ty такие, что относительные оценки Ау = 0 для базисных (занятых) клеток транспортной таблицы и Ау > 0 для небазисных (свободных) клеток.

Сущность метода потенциалов состоит в следующем.

1. В качестве первого приближения к оптимальному решению берется любое начальное базисное решение (построенное методами северо-западного угла, минимального элемента или любым другим методом) .

2. Определяются потенциалы «, и ty так, чтобы в каждой базисной клетке выполнялось условие Ау = 0 или, что то же самое, Vj —щ = Cij,i= 1,2,... ,m; j = 1,2,... ,п. Заметим, что такая система содержит m + п — 1 уравнений (по количеству базисных клеток) и m + п переменных. Поэтому одну из переменных задают произвольно (например, полагаем U\ =0), остальные находят из указанной системы.

3. Вычисляются относительные оценки Ау для небазисных (свободных) клеток. Если для всех этих клеток Ау > 0, то проверяемое базисное решение оптимально. Если же существуют небазисные клетки, для которых Ау < 0, то исследуемое базисное решение можно улучшить, вводя в число базисных одну из указанных клеток (обычно ту, для которой относительная оценка Ау < 0 минимальна). Пусть это (to, jo)Рассмотрим вопрос о том, какая из базисных клеток выводится из числа базисных. Из клеток транспортной таблицы образуем цикл (замкнутую цепочку) так, чтобы он содержал небазисную клетку, а остальные клетки были базисными. Пометим клетки цикла следующим образом: небазисную — знаком "+", остальные (базисные) — знаком "—" или "+", но так, чтобы соседние по строке или по столбцу клетки имели разные знаки.

Увеличим теперь объем перевозок, стоящих в клетках со знаком "+", на величину О, а объем перевозок, стоящих в клетках со знаком "—", уменьшим на ту же величину в. Очевидно, если в качестве в выбрать минимум среди отрицательных клеток, то в результате

40

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

4. С помощью описанной процедуры перераспределения грузов по циклу клетка (г'о, jo) вводится в число базисных, а базисная клетка, которая становится свободной, очевидно, из базиса выводится. Полученное новое базисное решение проверяется на оптимальность (п. 2, 3) и т. д., пока для текущего базисного решения не будет выполнен критерий оптимальности.

В невырожденном случае метод потенциалов приводит к оптимальному решению ТЗ за конечное количество шагов. В вырожденном случае, если занятых клеток меньше, чем т + п — 1, возможно зацикливание, для предупреждения которого необходимы дополнительные меры.

Пример 3. Для рассмотренного ранее примера построим оптимальное решение методом потенциалов. В качестве начального опорного решения выберем решение, построенное методом северо-западного угла.

 

 

Qi

g2

Q3

Qa

a.

Ui

Pi

3

5

2

 

10

 

р2

 

 

8

7

15

 

Рз

 

 

 

7

7

 

h

3

5

10

14

 

 

 

Для базисных клеток (1;1), (1;2), (1;3), (2;3), (2;4), (3;4) вычислим потенциалы щ, Vj (і = 1,2,3; j = 1,2,3,4) используя соотношения

U j ............ — ^ij'

Имеем

Vi

— «і

= 2,

Vi

— «2

= 5,

 

— «і

= 3,

Vz

— «2

= 3,

V2

— «і

= 4,

Vi

«3

= 4.

В системе 6 уравнений и 7 неизвестных щ, щ, «з, Vi, v2, Vz и Vi, поэтому одну из неизвестных переменных необходимо доопределить. Пусть «і = 0, тогда Vi = 2, «2 = 4, и3 = 3, «2 = 0, Vi = 5, «3 = 1.

41

Заносим эти данные в таблицу и вычисляем относительные оценки Ау = су — (ty — и і) для небазисных клеток:

Аі4

= си

(w4 «i) = 7

-5H

h0 =

2

А2і

= 1 -

(wi «2) = 3 —

(2-

0) =

1

А22

= 6 -

(w2 «2) = 6 -

(4-

0) =

2

А31

= 2 -

(2 1) = 1,

 

 

 

А32

= 2 -

(4 1) = -1,

 

 

 

Азз

= 5 -

(3 1) = 3.

 

 

 

Относительные оценки Ay помещаем в левом верхнем углу клеток транспортной таблицы. В правом верхнем, как и прежде, размещены значения су, а в центре — план перевозок.

 

Qi

g2

Q3

Qa

a.

Ui

Pi

з2

 

23

2 7

10

0

р2

1 3

2 6

g3

75

15

0

Рз

1 2

-1 2

3 5

74

7

1

h

3

5

10

14

32

 

 

2

4

3

5

 

 

Единственной клеткой, для которой Ay < 0, является клетка (3;2). Строим цикл, включающий эту клетку (остальные клетки цикла должны быть базисными), и помечаем его вершины знаками "+" и "—". Определяем Q = min(5,8, 7) = 5 и, перезагружая клетки ТЗ по указанному циклу, получаем новое базисное решение.

 

Qi

Q2

Q3

Qa

а.

щ

Pi

®2

0 4

©3

2 7

10

0

р2

1 3

2 6

®3

©5

15

0

Рз

1 2

©2

3 5

©4

7

1

bj

3

5

10

14

32

 

Vj

2

4

3

5

 

 

42

Вычисляя, как и ранее, потенциалы для нового базисного решения, а затем относительные оценки Ау небазисных переменных, убеждаемся, что все Ау > 0, а значит, полученное базисное решение

3   0   7   0 \ О   0   3 12 0   5   0    2 /

является оптимальным.

Многие практические задачи, связанные с планированием перевозок, не укладываются в рамки рассмотренной задачи, так как осложнены дополнительными ограничениями или вообще существенно сложнее по постановке.

Например, понятно, что транспортные магистрали, связывающие источники продукции с потребителями, имеют ограниченные (в ограниченный промежуток времени) пропускные способности. Эти ограничения могут не позволить реализовать найденный оптимальный план перевозок. Поэтому приходится включать в задачу ограничения, связанные с пропускными способностями магистралей. Тогда математическая модель задачи принимает вид

т п і=1 з=1

п m

Л •''<•<    bJ     І = 1,2,..., те;

i=l

0 < жу < dy.

Здесь dy — пропускная способность магистрали т. е. максимальный объем продукции, который можно перевезти по ней за рассматриваемый промежуток времени.

Такая задача может оказаться неразрешимой, если сумма всех магистралей, ведущих к j-му потребителю, меньше его потребностей,

m

т. е. V dy < bj.

i=l

43

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

Исходная ТЗ может быть осложнена еще наличием промежуточных транспортных узлов, в которых обрабатываются грузы (например, перевалка на другой вид транспорта), или отсутствием транспортных магистралей между отдельными потребителями и поставщиками. Для таких задач также имеются более или менее эффективные методы решения.

Принципиально меняется характер модели задачи даже в простейшем случае, если критерием оптимальности выбрано время, необходимое для обеспечения всех потребителей нужным объемом продукции, и требуется минимизировать это время. Такая задача называется ТЗ по критерию времени. Математическая модель этой задачи оказывается нелинейной (за счет нелинейности целевой функции). Если вместо матрицы стоимостей перевозок С = (су) задана матрица Т = (tij), где ty — время перевозки, и предполагается, что ty не зависит от объема перевозимой продукции, то целевая функция примет вид

max ty —ї min .

Здесь maxty означает максимальное из ty, соответствующих ненулевым перевозкам (для жу = 0 считаем ty = 0) рассматриваемого допустимого плана перевозок. Очевидно, за время max ty будут осуществлены все перевозки. Требуется выбрать допустимый план, для которого это время будет минимальным.

Решение такой задачи можно свести к последовательному решению нескольких ЗЛП. Имеется также алгоритм, позволяющий постепенно улучшать исходный опорный план по правилам, напоминающим метод потенциалов.

Часто требуется составлять рациональный план перевозок не одного, а нескольких видов продукции. Отказ от предположения, что рассматриваются перевозки однородного вида продукции, значительно усложняет задачу. И еще более сложной является задача, когда требуется распределить перевозки между разными видами транспорта, учитывая, что стоимость перевозки единицы продукции от г-го поставщика к j-му потребителю зависит не только от вида продукции, но и от вида транспорта, на котором она перевозится.

44

Такие задачи называются многоиндексными ТЗ. Увеличение количества индексов у переменных резко увеличивает количество расчетов, необходимых для решения задачи, и делает невозможным применение простых методов для ее решения.

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

Характерным примером решения ТЗ на сетке является задача отыскания потоков в сетях с некоторыми оптимальными свойствами.

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

Например, граф Г = {1,11} описывается множеством вершин I = = {1;2;3;4;5} и множеством дуг U = {(1; 2), (1; 3), (2; 1), (2; 4), (4; 3), (4; 5), (5; 2)}. Такой граф называется ориентированным (направленным). Если направление движения не указано, то дуги называются ребрами, а граф — неориентированным. На "транспортном" языке дуга называется коммуникацией, последовательность взаимосвязанных вершин (цепь) — маршрутом, путь — направленным маршрутом и т. д.

С понятием графа тесно связано понятие сети. Сетью называется граф, элементам которого поставлены в соответствие некоторые параметры: d, — вершинам, г у — дугам. На практике величины d, часто интерпретируются как объемы производства (d, > 0) или потребления (di < 0) некоторого однородного продукта; г у — ограничения на пропускные способности коммуникации, связывающей пункты і

45

и j. Параметром дуги может быть также стоимость су перевозки продукции из пункта і в пункт j.

Понятие потока, который вводится на графе, обобщает понятие допустимых транспортных перевозок. Как и физический аналог потока жидкости в сообщающихся сосудах, поток на графе обладает свойствами сохранения и непрерывности. В зависимости от критериев оптимальности на сети ставятся задачи об оптимальном потоке (если необходимо минимизировать стоимость перевозок), о кратчайшем пути (если из многих вариантов маршрута необходимо выбрать оптимальный) о максимальном потоке (если необходимо максимизировать весь объем перевозок) и др.

Более подробно с методами решения транспортных матричных и сетевых задач можно ознакомиться в [3].

 

 ...  5



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх