Возможности быстрого решения транспортной задачи
Журнал: Научный журнал «Студенческий форум» выпуск №16(16)
Рубрика: Физико-математические науки
![](https://nauchforum.ru/themes/mix_and_match/images/logo.jpg)
Научный журнал «Студенческий форум» выпуск №16(16)
Возможности быстрого решения транспортной задачи
Формулировка транспортной задачи
Формулировку транспортной задачи можно найти в книгах по линейному программированию, или содержащих раздел – линейное программирование.
Задача линейного программирования заключается в определении решения неопределенной системы линейных уравнений, при котором целевая функция достигает наименьшего, или наибольшего значения. Решение заключается в определении первого опорного плана и перехода к оптимальному плану.
Транспортная задача
Однородный продукт, сосредоточенный в m пунктах отправления в количествах а1,а2, …ам единиц соответственно необходимо доставить в каждый из 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 |
|
X21+Х22 +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. Подсчет средней стоимости перевозок менее трудоемкий по сравнению с решением неопределенной системы линейных уравнений. Поэтому, если средняя стоимость планируемых перевозок меньше любого значения элемента матрицы стоимости, соответствующего нулевым перевозкам, то план перевозок оптимальный. В других случаях следует проверять план на оптимальность сравнением косвенных стоимостей перевозок с заданными.
![](/sites/default/files/publ_rinc.png)