Главная / Программирование / Определение транспортной задачи

Определение транспортной задачи

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

Имеется m пунктов отправления (ПО): A1, A2, …, Am, в которых сосредоточены запасы какого-то однородного груза в количестве соответственно a1, a2, …, am единиц. Кроме того, имеется пунктов назначения (ПН): B1, B2, …, Bn подавших заявки соответственно на b1, b2, …, bn, единиц груза.

Предполагается, что сумма всех заявок равна сумме всех запасов:

ai =Bj (3.1)

Известна стоимость Сij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Вj. Таблица (матрица) стоимостей перевозки Сij задана:

Требуется составить такой план перевозок, при котором все заявки были бы выполнены, и при этом общая стоимость всех перевозок была минимальна.

При такой постановке задачи показателем эффективности плана перевозок является Стоимость; поэтому поставленную задачу точнее называют Транспортной задачей по критерию стоимости.

Дадим этой задаче математическую формулировку. Обозначим xij- количество груза, отправляемого из i-го пункта отправления в j-й пункт назначения Bj.

Неотрицательные переменные, число которых равно m*n, должны удовлетворять следующим условиям.

I. Суммарное количество груза, направляемое из каждого пункта отправления во вcе пункты назначения, должно быть равно запасу груза в данном пункте. Это дает т условий-равенств:

X1j =a1,

X2j =a2, (3.2)

………….

Xmj =am,

2. Суммарное количество груза, доставляемое в каждый пункт назначения изо всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Это дает n условий-равенств:

Xi1=b1,

Xi2=b2, (3.3)

…………

Xin=bn,

Условия (3.2), (3.3) называются «балансовыми условиями».

3. Суммарная стоимость всех перевозок, т. е. сумма величин xij, умноженных на соответствующие стоимости Сij, должна быть минимальной:

L= Сij xij = min (3.4)

Функции (3.4), являющаяся целевой функцией линейна, ограничения-равенства (3.2), (3.3) также линейны. Перед нами – типичная задача линейного программирования о ограничениями — равенствами, называемая основной задачей линейного программирования (ОЗЛП).

Данная задача имеет некоторые особенности, позволяющие ре

Шить ее вручную простыми табличными методами. Во-первых, все коэффициенты при переменных в уравнениях (3.2), (3.3) равны единице. Во-вторых, не все m+n уравнений задачи являются независимыми. Действительно, складывая между собой все уравнения (3.2) и

Все уравнения (3.3), мы должны получить одно и то же в силу условия (3.1). Таким образом, условия (3.2), (3.3) связаны одной линейной зависимостью и фактически из этих уравнений только m, а не n являются линейно независимыми. Значит, ранг r системы уравнений (3.2), (3.3) равен

R=m+n-1

А, следовательно, можно разрешить эти уравнения относительно m+n-1 базисных переменных, выразив их через остальные, свободные, количество которых равно

K=mn-(m+n-1)= (m-1)(n-1)

Как известно, в задаче линейного программирования оптимальное решение достигается в одной из вершин области допустимых решений (ОДР), где по крайней мере K переменных обращаются в нуль. Значит, в нашем случае для оптимального плана перевозок по крайней мере (m-1)(n-1) значений xij должны быть равны нулю.

Условимся о терминологии. Значения xij количества единиц груза, направляемых из пункта Ai в пункт Bj, будем называть Перевозками.

Любую совокупность значений xij (i=1,m; j=1,k) будем называть Планом перевозок или просто Планом.

План xij будем называть Допустимым, если он удовлетворяет условиям (3.2), (3.3): все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будем называть Опорным, если в нем отличны от нуля не более r=m+n-1 базисных перевозок xij, а остальные перевозки равны нулю.

План xij будем называть Оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

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

Образец транспортной таблицы дан в табл. 3.1, где стоимости перевозок единицы груза из ПО Ai в ПН Bj помещаются в правом верхнем углу каждой клетки таблицы, о тем, чтобы в самой клетке при составлении плана помещать перевозки xij.

Таблица 3.1

ПО ПН

B1

B2

Bn

Запасы

A1

C11

C12

C1n

A1

A2

C21

C22

C2n

A2

Am

Cm1

Cm2

Cmn

A

Заявки

B1

B2

Bn

Ai Bj

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

Как показано выше, в каждом опорном плане, включая оптимальный, будут отличны от нуля не более чем m+n-1 перевозок. Клетки таблицы, в которых записываются эти отличные от нуля перевозки, условимся называть базисными, а остальные (пустые) — свободными.

Таким образом, решение ТЗ свелось к следующему. Найти такие значения положительных перевозок, которые, будучи проставлены в базисных клетках транспортной таблицы, удовлетворяли бы следующим условиям:

— сумма перевозок в каждой отроке таблицы должна быть равна запасу данного ПО;

— сумма перевозок в каждом столбце должна быть равна заявке данного ПН;

— общая стоимость перевозок — минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной табл. 3.1. При описании этих преобразований будем пользоваться нумерацией клеток таблицы, подобной нумерации клеток шахматной доски. Клеткой AiBj или, короче, клеткой (i, j) будем называть клетку, стоящую в i-й строке и j-м столбце транспортной таблицы.

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

Пример 1. Условия ТЗ заданы транспортной табл. 3.2.

2. Требуется найти опорное решение ТЗ (построить опорный план).

Решение. Будем заполнять табл.3.2 перевозками постепенно, начиная о левой верхней клетки (1,1) («северо-западного угла» таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте A1, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1, удовлетворена, а в пункте A1 осталось еще 30 единиц груза. Удовлетворим за счет их заявку пункта В2 (27 единиц), запишем 27 в клетку (1,2); оставшиеся 3 единицы груза пункта A1 назначим пункту B3. В составе заявки пункта B3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта A2, чем его запас будет исчерпан, и еще 9 возьмем из пункта А3.

Таблица 3.2

ПО ПН

B1

B2

B3

B4

B5

Запасы

A1

10

8

5

6

9

48

A2

6

7

8

6

5

30

A3

8

7

10

8

7

27

A4

9

5

4

6

8

20

Заявки bj

18

27

42

12

26

125

Из оставшихся 18 единиц пункта A3 12 выделим пункту B4; оставшиеся 6 единиц назначим пункту B5, что вместе со всеми 20 единицами пункта A4 покроет его заявку (табл.3.3).

Таблица 3.3

ПО ПН

B1

B2

B3

B4

B5

Запасы

A1

18 10

27 8

3 5

6

9

48

A2

6

7

30 8

6

5

30

A3

8

7

9 10

12 8

6 7

27

A4

9

5

4

6

20 8

20

Заявки bj

18

27

42

12

26

125

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

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

Только допустимым; но и опорным решением транспортной задачи. Действительно, число базисных клеток таблицы, в которых стоят ненулевые перевозки, удовлетворяет условию m+n-1=8. Остальные клетки — свободные (пустые), в них стоят нулевые перевозки и их число равно 12. Значит, наш план — опорный и поставленная задача построения опорного плана решена.

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

18.10+ 27.8 + 3.5 + 30.8 + 9.10 + 12.8 + 6.7 + 20.8 = 1039.

Прежде чем рассматривать способы улучшения опорного плана и обеспечения его оптимальности, опишем еще один способ нахождения опорного плана называемый способом «минимальных стоимостей перевозок». В этом случае в матрице стоимостей перевозки (матрице затрат) отыскиваем минимальный элемент и в первую очередь включаем в план самую дешевую перевозку, притом в максимально возможном объеме. Обращаясь к исходным данным табл.3.2, в план включаем перевозку 20 единиц груза из ПО А4 в ПН B4 со стоимостью 4, что полностью исчерпывает запас ПО A4. Следующий по величине элемент матрицы затрат (5), расположенный в нескольких клетках таблицы, определяет включение в план перевозки между пунктами A2 и B5 , где объем перевозки наибольший (26), и затем перевозки между пунктами A1 и В3 объемом 22 единицы, что удовлетворяет заявки пунктов B3, и В5. Далее планируются перевозки со стоимостью 6 между пунктами A1 и B4 объемом 15 единиц и пунктами A2 и B1 объемом 4 единицы. Продолжая действовать аналогичным образом и дальше, придем к плану перевозок табл.3.4.

В том, что полученный план перевозок допустимый, легко убедиться, проверив, что суммы элементов в каждой отроке табл. 3.4 равны соответствующим запасам, а суммы по столбцам — заявкам. Поскольку число базисных (ненулевых) клеток равно m+n-1=8, а число свободных (нулевых) равно (n-1)(m-1)=12, где m=4, n=5, построенный план перевозок является не только допустимым, но и опорным. Затраты на реализацию этого плана составляют

11.10 + 4.6 + 3.8 + 24.7 + 22.5 + 2074 + 26.5 = 736.

Таблица 3.4

ПО ПН

B1

B2

B3

B4

B5

Запасы

A1

11 10

8

22 5

15 6

9

48

A2

4 6

7

8

6

26 5

30

A3

3 8

24 7

10

8

7

27

A4

9

5

20 4

6

8

20

Заявки bj

18

24

42

15

26

125

Рассмотренный способ построения опорного плана прост, но в ряде случаев приводит к опорному» решению, которое значительно отличается от оптимального. Лучшего результата можно добиться c помощью метода наименьшей стоимости. Из всех цен за единицу перевозки выбираем наименьшую – 4 (A4-B3). В эту клетку включаем максимально возможную перевозку из пункта A4- 20. Во всех остальных клетках этой отроки будут нули, т. к. в пункте A4 ничего не осталось. Пункт B3 нуждается в 42 ед., 20 он уже получил. В этом столбце следующая минимальная стоимость перевозки – 5(A1-B3). В это место нужно поставить недостающее количество груза (22), поставив в остальных клетках этого столбца нули. Продолжая в этом же духе получим следующую таблицу.

Таблица 3.5

ПО ПН

B1

B2

B3

B4

B5

Запасы

A1

0

14

22

12

0

48

A2

4

0

0

0

26

30

A3

14

13

0

0

0

27

A4

0

0

20

0

0

20

Заявки bj

18

27

42

12

26

125