Статья:

Возможности быстрого решения транспортной задачи

Журнал: Научный журнал «Студенческий форум» выпуск №16(16)

Рубрика: Физико-математические науки

Выходные данные
Гоменюк Д.В., Aleksejs G. Возможности быстрого решения транспортной задачи // Студенческий форум: электрон. научн. журн. 2017. № 16(16). URL: https://nauchforum.ru/journal/stud/16/26274 (дата обращения: 04.08.2020).
Журнал опубликован
Мне нравится
на печатьскачать .pdfподелиться

Возможности быстрого решения транспортной задачи

Гоменюк Денис Владимирович
выпускник Санкт-Петербургского государственного университета аэрокосмического приборостроения (ГУАП), РФ, г. Санкт-Петербург
Aleksejs Guschins
студент Университета прикладных наук, Финляндия, г. Юваскюля

 

Формулировка транспортной задачи

Формулировку транспортной задачи можно найти в книгах по линейному программированию, или содержащих раздел – линейное программирование.

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

Транспортная задача

Однородный продукт, сосредоточенный в m пунктах отправления в количествах а12, …ам единиц соответственно необходимо доставить в каждый из n пунктов назначения в количествах b1, b2 …bn. Общий запас продукта в пунктах отправления равен суммарной потребности в этом продукте пунктов назначения. Обычно пунктов назначения больше пунктов отправления. n>m.

Стоимость перевозки единицы продукта из i - того пункта отправления в j – й пункт назначения равна сij и известна для всех комбинаций {I,j}. {I,j} – маршрут перевозки из i  того пункта отправления к j тому пункту назначения. xij – количество продукта перевозимого по маршруту {I,j}.

Условия транспортной задачи записывается в виде таблицы перевозок, таблицы стоимостей перевозок по различным маршрутам и выражения целевой функции.

Наличие матрицы стоимостей перевозок дает возможность значительно упростить решение задачи и быстро получить оптимальный план перевозок.

Таблица 1.

Таблица перевозок

 

1

2

. . .

n

ai

1

X11

X12

X1n

a1

2

X21

X22

X2n

a2

m

Xm1

Xm2

Xmn

am

bj

b1

b2

bn

 

 

Таблица 2.

Таблица стоимостей перевозок

 

1

2

N

1

C11

C12

C1n

2

C21

C22

C2n

m

Cm1

Cm2

Cmn

 

Выражение для целевой функции C= ij*xij

Запас продукта в i - том пункте отправления измеряется величиной ai. Потребность в продукте j-того пункта назначения равна bj.

Задача заключается в определении таких величин xij, для всех перевозок {I,j}, при которых суммарная стоимость перевозок была бы минимальной.

Пример № 1

Предприниматель имеет центры распределения, находящиеся в Атланте, Чикаго и Нью – Йорке. Эти центры имеют в распоряжении соответственно 40, 40, 40 единиц некоторого однородного товара. Рынкам сбыта требуются следующие количества единиц товара: Кливленду 25, Луисвиллю 20, Мемфису 30, Питтсбургу 30 и Ричманду 15. Стоимость перевозки единицы товара между каждым центром и рынком в долларах указана в следующей таблице.

Таблица 3.

 

Кливленд

Луисвилль

Мемфис

Питтсбург

Ричмонд

Атланта

55

 

30

40

50

40

Чикаго

35

30

100

45

60

Нью-Йорк

40

60

90

35

30

 

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

Запишем развернутую систему уравнений

X11+X12+X13 +X14+X15                                                                 

 

 

= 40

 

X2122 +X23 +X24 +X25

 

= 40

 

 

X31+X32 +X33 +X34 +X35

= 40

X11   +

 X 21 +

X31

= 25

   X12 +

   X22 +

   X32

= 20

       X13 +

        X23 +

         X33

= 30

            X14 +

                 XX24 +

             X34

= 30

                            X15 +                                                            

              X25 +

                X35

= 15

Всего 8 уравнений. Но линейно независимых 7. Если сложить уравнения от 4 до 8 и вычесть сумму уравнений от 2 до 3, то получим первое уравнение. Таким образом одно из восьми уравнений, мы получили первое, линейная комбинация остальных. Исключим первое уравнение и систему запишем в матричном виде A*X = P0.

Где А – матрица размером 7 на 15 с элементами равными 1 и 0. Х – матрица – строка определяемых объемов перевозок между пунктами отправления и пунктами назначения. P0 – матрица–столбец объемов продукта в пунктах отправления и потребностей в пунктах назначения. С – матрица-строка стоимостей перевозок.

P11

P12

P13

P14

P15

P21

P22

P23

P24

P25

P31

P32

P33

P34

P35

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1  

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

 

Вектор X = {x 11, …, xin , …, x21  … x3n  … xm1  … xmn  }              

   

 

C = {c11…cij,…cmn }

Формулировка транспортной задачи приводится к такому виду

A*X = P0

0

C*X - минимум

Сформулируем теорему построения опорного плана транспортной задачи. Пусть для определенности n > m.

Теорема

Существует план, содержащий не менее n и не более, чем m+n-1 положительных перевозок xij. При этом система векторов Pij, соответствующих таким перевозкам линейно независима.

План перевозок должен содержать не менее n не нулевых значений, чтобы обеспечить потребности в пунктах назначения.

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

В каждом столбце определяется маршрут с наименьшей стоимостью перевозок и назначается значение перевозок равное bj. Если в столбце имеются равные значения стоимостей перевозок, то перевозки назначаются по маршруту, которому соответствует большее ai. В этом столбце остальные перевозки принимаются нулевыми.

Составляется матрица перевозок с последним столбцом равным ai-  ij.

Таблица 4.

1

0

10

30

0

0

0

2

25

10

0

0

0

5

3

0

9

0

30

15

-5

 

Так-как a1 –b2 = a2 –b2 =20, то x12 = x22 =10

Для каждой строки определена разность ai - ij

Для получения опорного плана осталось привести к равенству количества перевозимого товара и заданных значений в пунктах отправления. Перемещение по столбцам выполняется с учетом стоимостей перевозок. Так в третьей строке уменьшаем x34 на 5 единиц, перемещая их в ячейку [2,4].

Получим опорный план.

Таблица 5.

 

1

2

3

4

5

1

0

10

30

0

0

2

25

10

0

5

0

3

0

0

0

25

15

 

Значение целевой функции 3625; План содержит 7 не нулевых значений xij.

Выполняется утверждение теоремы построения опорного плана m+n -1 = 7

Проверим опорный план на оптимальность.

На маршрутах с не нулевыми перевозками стоимость перевозки запишем в виде суммы

cij = ui + vj. Полученная система уравнений неопределенная и имеет множество решений.

Примем одну переменную равной минимальному значению соответствующих сij

с12 = u1 + v2 = 30

u1 = 30

v2 = 0

c13 = u1 + v3 = 40

 

v3 = 10

с21 =u1 + v1 = 35

u2 = 30

v4 = 15

с22 = u2 + v2 = 30

 

 

c24 = u2 + v4 = 45

 

 

c34 = u3 + v4 = 35

 

 

c35 = u3 + v5 = 30

u3 = 20

v5 = 10

Подсчитаем косвенные значения стоимостей перевозок с*шо = uш + vо. На маршрутах с не нулевыми перевозками косвенные стоимости равны значениям в таблице стоимостей перевозок. Поэтому косвенные стоимости подсчитываем только для нулевых перевозок. Если косвенные стоимости не превышают значений в таблице стоимостей перевозок, то план оптимальный.

c*11 =u1 + v1 = 35

c*14 = u1 + v4 = 45

c*15 =u1 + v5 = 40

c*23 = u2 + v5 = 40

c*25 = u2 + v5 = 40

c*31 = u3 + v1 = 25

c*32 = u3 + v2 = 20

c*33 = u3 + v3 = 30

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

Пример 2

Таблица 6.

Таблица перевозок

 

 

 

 

 

 

ai

 

X11

X12

X13

X14

X15

30

 

X21

X22

X23

X24

X25

20

 

X31

X32

X44

X34

X35

40

bj

20

15

30

10

15

 

 

Таблица 7.

Таблица стоимостей перевозок

25

35

50

60

40

40

25

60

40

40

30

40

25

35

25

 

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

Таблица 8.

20

0

0

0

0

10

0

15

0

0

0

5

0

0

30

10

15

-15

 

Составим таблицу с вакантными местами для изменения плана перевозок

Таблица 10.

20

0

 

0

 

10

0

15

0

 

 

5

0

0

30

10

25

-15

 

План, обеспечивающий заданные перевозки

Таблица 11.

Пункты отправления

назначения

1

2

3

4

5

 

1

20

0

0

0

10

 

2

0

15

0

5

0

 

3

0

0

30

5

5

 

 

Проверим план на оптимальность   

с11 = u1 + v1 = 25

 

v2 = 10

c15 = u1 + v5 = 40

u1 = 15

 

с22 = u2 + v2 = 25

 

v2 = 20

c24 = u2 + v4 = 40

u2 = 5

 

c33 = u3 + v3 = 25

u3 = 0

v3 = 25

c34 = u3 + v4 = 35

 

v4 = 35

c35 = u3 + v5 = 25

 

v5 = 25

Система уравнений имеет множество решений. Требуется найти решение, в котором все переменные неотрицательные.

Подсчитываем косвенные стоимости.

c*12 =u1 + v2 = 15 + 20 - 35

c*13 = u1 + v3 = 15 + 25 = 40

c*14 =u1 + v4 = 15 +35 = 50

c*21 = u2 + v1 = 5 + 10 = 15

c*23 = u2 + v3 = 5 + 25 = 30

c*25 = u2 + v5 = 5 + 25 = 30

c*31 = u3 + v1 = 0 + 10 = 10

c*32 = u3 + v2 = 0 +20 = 20

Косвенные стоимости не превышают соответствующих значений в таблице стоимостей перевозок. План оптимальный.

Подсчитаем среднюю стоимость перевозок найденного плана.

Cср = {x11 * c11 + x15 * c15 + x22 * c22 + x24 * c24 + X33 * c33 + x34 * c34 + x35 * c35} / 90 =

{ 20 * 25 = 10 * 40 + 15 * 25 + 5 * 40 + 30 * 25 + 5 * 35 = 5 * 25 } / 90 = 28

Средняя стоимость перевозок меньше минимальной стоимости по маршрутам, не входящим в план перевозок.

План содержит m + n – 1 = 3 + 5 – 1 = 7 не нулевых перевозок.

Пример 3

Таблица 12.

Таблица перевозок

 

 

 

 

 

ai

 

X11

X12

X13

X14

40

 

X21

X22

X23

X24

20

 

X31

X32

X33

X34

10

bj

40

10

10

10

 

 

Таблица 13.

Таблица стоимостей перевозок

15

40

25

30

40

15

25

30

25

30

15

60

 

Минимальные стоимости в столбцах сразу определяют оптимальный план перевозок.

Таблица 14.

40

0

0

0

0

10

0

10

0

0

10

0

 

В этом примере число не нулевых перевозок равно числу пунктов назначения.

Выводы

1. Предлагаемый алгоритм решения транспортной задачи состоит из четырёх шагов:

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

Подсчитывается столбец отклонений запаса продукта в пунктах отправления при первом шаге решения задачи.

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

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

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

2. Для любой транспортной задачи существует план. Существует план, содержащий не менее n и не более чем m+n-1 положительных перевозок xij. При этом система векторов Pij, соответствующих таким перевозкам линейно независима.

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

 

Список литературы:
1. Беклемишев Д. В. Дополнительные главы линейной алгебры // Наука – 1983.
2. Saul I. Gass Linear programming // McGraw-Hill Book Company Inc – 1958.