ЛП_Транспортная задача. Транспортная задача

• Название: Транспортная задача
• Дата: 04.12.2022
• Размер: 0.62 Mb.
• Имя файла: ЛП_Транспортная задача.pdf
• Тип: Задача; #827930

73
Транспортная задача
Однородный груз сосредоточен у m
поставщиков в объёмах m
1
a
,...,
a
. Груз нужно доставить n
потребителям в объёмах n
1
b
,...,
b
. Известна ij c

стоимость перевозки единицы груза от i

го поставщика j

му потребителю. Требуется составить план перевозок, при котором все запасы будут полностью вывезены, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку минимальны.
Исходные данные транспортной задачи обычно записываются в табл. 5.5.
Таблица 5.5 j
b
1
b
2
b
… n
b i
a
1
a
11
c
12
c
… n
1
c
2
a
21
c
22
c
…
2
c
…
…
…
…
… m
a
1
m c
2
m c
с
… mn c
В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, склады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.
Переменными транспортной задачи являются ij x
, m
,
1
i

, n
,
1
j

,

объемы перевозок от i-го поставщика j- му потребителю. Эти переменные можно записать в виде матрицы перевозок











mn
1
m n
1 11
x x
x x
X






74
Так как i
i x
c

это затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны
 
 
m
1
i n
1
j ij i
x c
, требуется обеспечить минимум суммарных затрат. Система ограничений задачи состоит из двух групп уравнений. Первые m уравнений описывают тот факт, что запасы всех поставщиков вывозятся полностью. Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех потребителей.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
 
 


 
m
1
i n
1
j ij i
min x
c
X
z
(5.47)



















n
,
1
j
,
m
,
1
i
,
0
x
,
n
,
1
j
,
b x
,
m
,
1
i
,
a x
ij m
1
i j
ij n
1
j i
ij
(5.48)
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.





m
1
i n
1
j j
i b
a
(5.49)
Определение 5.21. Условие (5.49) называется условием
баланса. Модель в этом случае называется закрытой.
Определение 5.22. Если равенство (5.49) не выполняется,
то модель называется открытой.
Теорема 5.11. Для того чтобы транспортная задача
имела
решение,
необходимо
и
достаточно,
чтобы
выполнялось условие баланса 5.49.
Теорема 5.12. Ранг системы векторов условий
транспортной задачи равен
1
n
m


.
Из теоремы 5.12 следует, что опорный план не может иметь более
1
n m


координат отличных от нуля. Следовательно,

75 невырожденный опорный план транспортной задачи имеет
1
n m


положительных координат, а вырожденный опорный план имеет меньше чем
1
n m


положительных координат.
Любой допустимый план можно записать в виде таблицы.
Определение 5.23. Клетки таблицы, в которых находятся
отличные от нуля перевозки, называются занятыми,
остальные

свободными.
Для проверки линейной независимости векторов условий, соответствующих положительным координатам допустимого плана, а также для построения нового опорного плана используется понятие цикла.
Определение
5.24.
Циклом
называется
последовательность клеток таблицы транспортной задачи


1 1
j
,
i
,


2 1
j
,
i
,


2 2
j
,
i
, …,


1
k j
,
i
, в которой две соседние
клетки находятся либо в одной строке, либо в одном столбце,
причем первая и последняя клетки так же находятся в одной
строке или столбце.
Построение циклов начинают с какой-либо незанятой клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот под прямым углом и двигаются к следующей незанятой клетке и т.д., пытаясь вернуться к первоначальной клетке.
Теорема 5.13. Для того чтобы система векторов условий
транспортной задачи была линейно зависимой, необходимо
и достаточно, чтобы из соответствующих занятых клеток
таблицы можно было построить цикл.
Следствие. Допустимый план транспортной задачи
является опорным тогда и только тогда, когда из занятых
клеток таблицы нельзя образовать ни одного цикла.
Основные этапы решения сбалансированной транспортной задачи следующие.
1. Построение математической модели исходной задачи.
2. Применение алгоритма метода решения транспортной задачи:
1) составление задачи двойственной исходной;
2) определение первоначального плана перевозок;

76 3) проверка полученного плана на оптимальность;
4) переход к новому плану перевозок;
5) проверка вновь полученного плана на оптимальность.
Затем этапы 4) и 5) повторяются до тех пор, пока не будет получен оптимальный план или выяснится, что задача не имеет решения.
Первоначальный опорный план транспортной задачи как задачи ЛП можно построить ранее рассмотренными методами, однако это связано с большими вычислениями. Существуют несколько простых методов построения первоначального опорного плана транспортной задачи, которые рассмотрим на примерах.
Пример 5.8. Найти начальный опорный план транспортной задачи, условия которой заданы в виде табл. 5.6.
Таблица 5.6 j
b
100 80 90 80 i
a
80 2
1 3
4 120 4
3 1
7 150 5
8 9
15
Решение.
Метод «северо-западного угла»
Не учитывая стоимость перевозок, начинаем удовлетворение потребностей первого потребителя за счет запасов первого поставщика. Для этого сравниваем
80
a
1

ед. с
100
b
1

ед.,
1 1
b a

, тогда 80 записываем в клетку (1,1). Запасы
1-го поставщика полностью израсходованы, поэтому в остальных клетках 1-й строки ставим прочерки. Потребности 1- го потребителя полностью не удовлетворены на 100-80=20ед..
Сравниваем этот остаток с запасами 2-го поставщика и поскольку
20 120
a
2


, то в клетку (2,1) записываем 20.
Теперь потребности 1-го потребителя удовлетворены, поэтому в
1-м столбце в остальных клетках ставим прочерк. У 2-го поставщика осталось
100 20 120


ед. груза, удовлетворяем

77 потребности 2-ого потребителя. Для этого сравниваем остаток у
2-го поставщика с потребностями 2-го потребителя. Имеем
80
b
100 20 120 2




, поэтому в клетку (2,2) записываем 80, потребности 2-ого потребителя полностью удовлетворены, поэтому в остальных клетках второго столбца ставим прочерк. У 2-го поставщика осталось
20 80 100


ед., их используем для удовлетворения потребностей 3-го потребителя и т.д. В итоге получаем следующую табл. 5.7.
Таблица 5.7 j
b i
a
100 80 90 80 80 80



120 20 80 20

150


70 80
Метод минимальной стоимости
Составим с помощью этого метода опорный план уже рассмотренной задачи.
Выбираем в табл. 5.6 наименьшую стоимость перевозки, это стоимость 1, помещенная в клетки (1,2) и (2,3). Так как
2 1
b
80
a


, то помещаем в клетку (1,2) 80, и так как запасы 1- го поставщика все израсходованы, то в остальные клетки 1-й строки ставим прочерк. Так как потребности 2-го потребителя удовлетворены, то в остальных клетках 2-го столбца ставим прочерк. Сравниваем запасы 2-го поставщика и 3-го потребителя:
3 2
b
90 120
a



, поэтому в клетку (2,3) ставим
90, так как потребности 3-го потребителя удовлетворены, то в остальных клетках третьего столбца ставим прочерк. У 2-го поставщика осталось
30 90 120


ед. груза. В оставшейся таблице минимальной стоимостью является 4, она записана в клетке (2,1). Сравниваем остаток у 2-го поставщика и потребности 1-го потребителя:
1
b
100 30


, поэтому в клетку
(2,1) записываем 30, так как запасы 2-го поставщика израсходованы, то в остальные клетки 2-й строки ставим

78 прочерк. В оставшейся таблице минимальная стоимость 5 в клетке (3,1). Сравниваем запасы 3-го поставщика с потребностями 1-го потребителя:
30 100 70 150
a
3




, поэтому в клетку (3,1) записываем 70, потребности 1-го потребителя удовлетворены, остаток запасов 3-го поставщика
80 70 150


записываем в клетку (3,4).
Получаем табл. 5.8.
Таблица 5.8 j
b i
a
100 80 90 80 80

80


120 30

90

150 70


80
Двойственная задача и (5.50) составляется с помощью правил, изложенных в разделе 5.10. Однако здесь есть свои особенности.
В двойственной задаче должно быть n
m

переменных. Те переменные, которые соответствуют поставщикам, обозначаются как i
u
, m
,
1
i

, а переменные, соответствующие потребителям, – j
v
, n
,
1
j

Согласно теоремам двойственности ограничения в двойственной задаче принимают вид ij j
i c
v u


, m
,
1
i

, n
,
1
j

, (5.50) а целевая функция
 
max v
b u
a v
u,
z n
1
j j
j m
1
i i
i







. (5.51)
Соответственно в алгоритме решения транспортной задачи ищется решение двойственной задачи, а затем с помощью теории двойственности находится решение и исходной задачи.
Этот алгоритм называется методом потенциалов, а решения i
u
, m
,
1
i

, и j
v
, n
,
1
j

, – потенциалами.

79
Используя сформулированные выше теоремы двойственности, можно вывести критерии для определения оптимальности полученного допустимого плана транспортной задачи.
Пусть получен некоторый допустимый план исходной задачи.
Выпишем ограничения двойственной задачи, соответствующие ненулевым значениям переменных этого плана. Если рассмотренный план исходной задачи является оптимальным, то эти ограничения (5.50) должны выполняться как равенства при соответствующем решении двойственной задачи (вторая теорема двойственности). Выберем из (5.50) эти ограничения и получим систему уравнений ij j
i c
v u


,
0
I
i

,
0
J
j

, (5.52) где
0
I
и
0
J
– подмножества, определенные условиями
0
x ij

,
0
I
i

,
0
J
j

Эта система уравнений имеет множество решений, и пусть


0
n
0 1
0
m
0 2
0 1
v
,...,
v
,
u
,...,
u
,
u
– одно из этих решений. Это решение подставим в ограничения двойственной задачи (5.50), не вошедшие в систему уравнений (5.52). Если эти ограничения являются верными неравенствами при найденном решении, то проверяемый допустимый план исходной задачи является оптимальным. В противном случае – нет.
Пример 5.9. Проверить на оптимальность план примера 5.8.
Решение. Составим двойственную задачу.
2
v u
1 1


,
4
v u
1 2


,
5
v u
1 3


,
1
v u
2 1


,
3
v u
2 2


,
8
v u
2 3


,
3
v u
3 1


,
1
v u
3 2


,
9
v u
3 3


,
4
v u
4 1


,
7
v u
4 2


,
15
v u
4 3


,
 






2 1
3 2
1
v
80
v
100
u
150
u
120
u
80
v
,
u z
max v
80
v
90 4
3



Потенциалы (переменные двойственной задачи) определяются уравнениями
2
v u
1 1


,
3
v u
2 2


,
9
v u
3 3


,

80 4
v u
1 2


,
1
v u
3 2


,
15
v u
4 3


Найдем решение этой системы, для этого одной из переменных (например
1
u
) придадим произвольное числовое значение (удобнее всего положить
1
u равным 0).
Рационально организовать процесс решения задачи в виде двойственной таблицы,
Таблица 5.9 1
v
2
v
3
v
4
v
1
u
2 80 1
0 3
4 4
-1 0
2
u
4 20 3
80 1
20 7
0 2
3
u
5
-7 8
-3 9
70 15 80 10 2
1
-1 5 клетки которой заполнены частями ограничений двойственной задачи (клетки с ограничениями заштрихованы). Теперь, положив
0
u
1

, последовательно находим потенциалы.
5
v
,
1
v
,
1
v
,
2
v
,
10
u
,
2
u
,
0
u
4 3
2 1
3 2
1








(5.53)
Подставим найденные значения переменных двойственной задачи в остальные неравенства системы (5.50). Выпишем эти неравенства
0 0
1 1
1
v u
2 1






,
4 0
3 1
3
v u
3 1







,
1 0
4 5
4
v u
4 1







,
0 0
7 7
7
v u
4 2






,
7 0
5 12 5
v u
1 3







,
2 0
8 10 8
v u
2 3







Из вычислений видно, что неравенства второе, пятое и шестое являются неверными. Т.е. найденное решение (5.52)

81 удовлетворяет не всем неравенствам ограничений.
Следовательно, план не является оптимальным.
Следующий этап алгоритма – составление нового допустимого плана. Очевидно, что при составлении нового плана придется использовать незанятые клетки. Таких клеток будет не менее чем


1
- n
m
- n
m


. Какую из них следует занять? Заполняя одну из незанятых клеток, приходится одновременно изменять числа, по меньшей мере, в трех уже заполненных клетках, чтобы не нарушить итоговое значение в строках и столбцах таблицы. Здесь следует использовать цикл, который должен строиться с учетом формул (5.50). Для транспортной задачи эти соотношения принимают вид:


0
c v
u ij j
i



, m
,
1
i

, n
,
1
j

Рассматривая только неверные неравенства, найдем те из них, для которых правая часть наименьшая. Пусть это будет


0 0
0 0
j i
j i
v u
c
0





0
c v
u
0 0
0 0
0 0
j i
j i
j i





Следовательно, переменную
0 0
j i
x следует ввести в базис
(занять клетку


0 0
j
,
i
).
Рассмотрим некоторый контур, включающий клетку


0 0
j
,
i
. Пусть это будет цикл


0 0
j
,
i
,


1 0
j
,
i
,


1 1
j
,
i и


0 1
j
,
i
Клетка


0 0
j
,
i свободна. Если переменную
0 0
j i
x включить в план: придать ей какое-нибудь значение, равное a, то число в клетке


1 0
j
,
i следует уменьшить на эту величину, число в клетке


1 1
j
,
i увеличить и, наконец, число в клетке


0 1
j
,
i вновь уменьшить. Если
1
a

, то такое изменение плана изменит целевую функцию на величину, равную
0 1
1 1
1 0
0 0
0 0
j i
j i
j i
j i
j i
c c
c c





Очевидно, достаточно рассматривать те циклы, для которых
0 0
j i

не положительна. Если обозначить клетки, в которых следует увеличить значения переменных знаком “+”, то

82 величина
0 0
j i

равна наименьшему из чисел, размещенных в клетках со знаком “+”.
Пример 5.10. В условиях предыдущего примера перейти к новому допустимому плану.
Решение. Наименьшее значение в ограничениях правой части двойственной задачи достигается в клетке (3,1) (табл.5.9).
Строим цикл (3,1), (3,3), (2,3), (2,1). При этом
7 1
9 5
4 31








Целевая функция уменьшится на 7 единиц, если
31
x увеличится на единицу. Новый план примет вид табл. 5.10.
Таблица 5.10 100 80 90 80 80 2
80 1
-7 3
-3 4
-8 0
120 4
7 3
80 1
20 7
0
-5 150 5
20 8
-3 9
50 15 80 3
2 8
6 12
Потенциалы равны
0
u
1

,
5
u
2


,
3
u
3

,
2
v
1

,
8
v
2

,
6
v
3

,
12
v
4

Проверка на оптимальность приводит к неравенствам
1
v u
2 1


,
1 8

,
3
v u
3 1


,
3 6

,
4
v u
4 1


,
4 12

,
4
v u
1 2


,
4 3


,
7
v u
4 2


,
7 7

,
8
v u
2 3


,
7 12

, которые показывают, что и этот план не оптимален.
Замечание. Очевидно, из всех циклов следует использовать
только те, которые приводят к наискорейшему убыванию
целевой функции. В этом смысле цикл (2,2), (2,4), (3,4), (3,2),
поскольку это приводит к уменьшению значения целевой
функции на
7 4
5 15 7





единиц.

83
В конце каждого шага проверяется условие, что потенциалы (переменные двойственной задачи) являются решениями этой задачи.
Пусть на некотором шаге получен очередной план и найдены потенциалы для этого плана. Положительность всех оценок


0
c v
u ij j
i ij




означает, что найденный план оптимален.
Пример 5.11. Для транспортной задачи, решение которой дается в таблице, проверить условие оптимальности.
Таблица 5.11 100 80 90 80 80 2

1 0
3

4 80 120 4

3 30 1
90 7

150 5
100 8
50 8

15

Решение. Найдем потенциалы двойственной задачи
1
v u
2 1


,
4
v u
4 1


,
3
v u
2 2


,
1
v u
3 2


,
5
v u
1 3


,
8
v u
2 3


,
0
u
1

,
2
u
2

,
7
u
3

,
2
v
1


,
1
v
2

,
1
v
3


,
4
v
4

Проверим выполнение оставшихся ограничений двойственной задачи.
2
v u
2 1


,
 
2 2
0



,
3
v u
3 1


,
 
3 1
0



,
4
v u
4 1


,
4 4
0


,
4
v u
1 2


,
 
4 2
2



,
7
v u
4 2


,
7 4
2


,
8
v u
3 3


,
 
8 1
7



,

84 15
v u
4 3


,
15 4
7


Все неравенства верны, следовательно:
1.
0
x
11

,
0
x
12

,
0
x
13

,
80
x
14

,
0
x
21

,
30
x
22

,
90
x
23

,
0
x
24

,
100
x
31

,
50
x
32

,
0
x
33

,
0
x
34

– решения исходной задачи. Целевая функция будет равна








5 100 1
90 3
30 4
80 1400 400 500 90 90 321






2.
0
u
1

,
2
u
2

,
7
u
3

,
2
v
1


,
1
v
2

,
1
v
3


,
4
v
4

– решения двойственной задачи.