ТРАНСПОРТНАЯ ЗАДАЧА
Математическая модель транспортной задачи
Транспортная таблица
Необходимое и достаточное условие разрешимости транспортной задачи
Пример
Пример. Задача организации оптимального снабжения .
Таблица
Экономико-математическая модель задачи.
Функциональные ограничения:
Этапы решения транспортной задачи
Определение исходного допустимого решения
Найти опорный план транспортной задачи методом наименьшей стоимости
Условие невырожденности плана
Метод потенциалов проверки решения на оптимальность
Теорема «о платежах».
Теорема оптимальности.
Пример
Пример 2.
Внесем в таблицу потенциалы занятых клеток
2.46M
Category: mathematicsmathematics

Транспортная задача. (Лекции 10,11)

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

Лекции 10,11

2.

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

3.

Общая постановка транспортной задачи
состоит в определении оптимального плана
перевозок некоторого однородного груза из m
пунктов отправления А1, А2,…, Аm в
n пунктов назначения B1, B2,…,Bn.
При этом в качестве критерия
оптимальности берется либо минимальная
стоимость перевозок всего груза, либо
минимальное время его доставки.

4.

Рассмотрим транспортную задачу, в которой в
качестве критерия оптимальности берется
минимальная стоимость перевозок всего
груза. Обозначим через cij тарифы или
стоимости перевозки единицы груза из i-го
пункта отправления в j-й пункт назначения,
через ai – запасы груза в i-м пункте
отправления, через b j – потребности в грузе
j-ым пунктом назначения, через xij–
количество единиц груза, перевозимого из i-го
пункта отправления в j-й пункт назначения
(перевозки).

5. Математическая модель транспортной задачи

m
n
Найти F = åå cij xij ® min
i =1 j =1
при ограничениях
m
ì
ïå xij = b j , j = 1, n
ï i =1
ï n
íå xij = ai , i = 1, m
ï j =1
ïx ³ 0
ï ij
î

6.

Первое ограничение
ì
íå xij = b j , j = 1, n
î i =1
m
означает, что все потребности должны быть
удовлетворены , а второе -
ì n
íå xij = ai , i = 1, m
,
î j =1
что все запасы должны быть перевезены.

7.

Определение. Всякое неотрицательное
решение системы ограничений транспортной
задачи, определяемое матрицей размера
m×n
æ x11 x12 ...x1n ö
ç
÷
x21 x22 ...x2 n ÷
ç
X=
ç ................. ÷
ç
÷
è xm1 xm 2 ...xmn ø
,
называют допустимым решением (или
планом) транспортной задачи.

8.

Определение.
План
*
*
ij m´n
X = (x )
,
при котором целевая функция
принимает минимальное значение,
называется оптимальным.

9.

Тарифы или стоимости перевозок единицы
груза cij также задаются матрицей, которая
называется матрицей транспортных издержек
или матрицей стоимостей
æ c11c12 ...c1n ö
ç
÷
c
c
...
c
21
22
2n ÷
ç
C=
ç ................. ÷
ç
÷
è cm1cm 2 ...cmn ø

10. Транспортная таблица

11. Необходимое и достаточное условие разрешимости транспортной задачи

Для разрешимости транспортной задачи
необходимо и достаточно, чтобы запасы груза
в пунктах отправления были равны
потребностям в грузе в пунктах назначения,
то есть, чтобы выполнялось равенство
m
åa
i =1
i
=
n
åb
j =1
j
--балансовые условия.

12.

При выполнении этого условия модель
транспортной задачи называется
закрытой. Если балансовое условие не
выполняется, то есть
m
n
,
å ai ¹ å b j
i =1
j =1
то модель транспортной задачи
называется открытой.

13.

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

14.

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

15. Пример

16.

Все грузы должны быть перевезены, поэтому
4
åx
j =1
ij
= ai , i = 1,3
Это три первых уравнения.
Все потребности должны быть удовлетворены
3
и, значит,
åx
i =1
ij
= b j , j = 1, 4.
Это четыре последних уравнения.
Здесь закрытая модель: сумма запасов равна
сумме потребностей.

17.

А целевую функцию составили по
матрице С - матрице тарифов
перевозок.

18. Пример. Задача организации оптимального снабжения .

Три фермерских хозяйства A1 , A2 , A3
ежедневно могут доставлять в город
соответственно 60, 60 и 50 ц молока
для обеспечения пяти торговых точек :
B1 , B2 , B3 , B4 , B5
Стоимость перевозки 1ц молока и
потребности торговых точек в молоке
указаны в таблице

19. Таблица

20. Экономико-математическая модель задачи.

Переменные : xij (i = 1,3, j = 1,5)
- количество молока , поставляемое i-м
фермерским хозяйством в j-ю торговую точку.
Целевая функция –суммарные транспортные
издержки, которые необходимо
минимизировать
F = 7 x11 + 6 x12 + 8 x13 + 10 x14 + 12 x15 +
+9 x21 + 5 x22 + 7 x23 + 4 x24 + 6 x25 +
+6 x31 + 8 x32 + 4 x33 + 9 x34 + 7 x35 ® min

21.

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

22. Функциональные ограничения:

По поставщикам (их 3)
по потребителям (их
5)
ì x11 + x12 + x13 + x14 + x15 £ 60 ï
í x21 + x22 + x23 + x24 + x25 £ 60
ï x + x + x + x + x £ 50
î 31 32 33 34 35
ì x11 + x21 + x31 = 30,
ï
ï x12 + x22 + x32 = 20,
ï
í x13 + x23 + x33 = 55,
ï
ï x14 + x24 + x34 = 20,
ïî x15 + x25 + x35 = 25.
xij ³ 0.

23. Этапы решения транспортной задачи

• Составляют математическую модель
задачи.
• Находят исходное опорное решение.
• Проверяют это решение на
оптимальность.
• Переходят от одного опорного решения
к другому.

24.

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

25. Определение исходного допустимого решения

1. Метод «северо-западного угла»
Метод заключается в том, что
заполнение клеток таблицы начинают с
левой верхней клетки (северо-западная
часть таблицы) для перевозки x11 и
продолжают вниз и вправо, заканчивая
клеткой для перевозки xmn .
При этом способе распределения на
тарифы cij
не обращают внимания.

26.

2. Метод «наименьшей стоимости»
Метод заключается в том, что
заполнение клеток таблицы начинают с
клетки, имеющей наименьшую
стоимость перевозки. Если таких клеток
несколько, то следует выбрать любую
из них.

27. Найти опорный план транспортной задачи методом наименьшей стоимости

28.

Минимальный тариф, равный 1 ,
находится в клетке x13 .
Положим x13 = 160 . Запишем это
значение в соответствующую клетку и
временно исключим из рассмотрения
строку A1 .
Потребности пункта назначения B3
считаем временно равными 30 ед.

29.

В оставшейся части таблицы с двумя
строками A2 и A3 и c четырьмя
столбцами клетка с наименьшим
тарифом находится на пересечении
строки A3 и столбца B2 , где c32 = 2.
Положим x32 = 50. Внесем это значение
в соответствующую клетку таблицы.

30.

Временно исключим из рассмотрения
столбец B2 и будем считать запасы
пункта A3 равными 120 ед. После
этого рассмотрим оставшуюся часть
таблицы с двумя строками A2 и A3 и
тремя столбцами B1 , B3 и B4 . В ней
минимальный тариф находится в клетке
на пересечении строки A3 и
столбца B3 и равен 3.

31.

Заполним описанным выше способом
эту клетку и аналогично заполним ( в
определенном порядке) клетки,
находящиеся на пересечении строки A2
и столбца B4 .

32.

В результате получим опорный план
0 160 0 ö
æ 0
ç
÷
X = ç120 0
0 20 ÷
ç 0 50 30 90 ÷
è
ø
При данном плане перевозок общая
стоимость перевозок составляет .
F = 1×160 + 4 ×120 + 8 × 20 + 2 × 50 + 3 × 30 + 6 × 90 = 1530

33. Условие невырожденности плана

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

34.

В нашей задаче число заполненных
клеток равно m + n – 1=3 + 4 – 1 = 6,
а пустых клеток – m × n – (m + n – 1), где
m – количество пунктов отправления,
n – количество пунктов назначения, что
в нашем случае 3 × 4 – 6 = 6.
Значит, найденный план является
невырожденным.

35. Метод потенциалов проверки решения на оптимальность

Предположим, что каждый пункт
отправления Ai вносит за перевозку
единицы груза какую-то сумму a i , а
каждый пункт назначения вносит
сумму b j . Эти платежи передаются
некоторому третьему лицу, например,
перевозчику. Величины a i и b jсвяжем
a i + b, где
равенствами
j = cij –
cij для базисных клеток.
тарифы

36.

Совокупность уравнений a i + b j = cij ,
составленных для всех базисных
переменных, представляет совместную
систему линейных уравнений, причем
одну из переменных можно задавать
произвольно и тогда остальные
переменные из системы уравнений
находятся однозначно.

37.

Обозначим через a i + b j = c ij , где c ij
назовем псевдостоимостями или косвенными
стоимостями (тарифами). Псевдостоимости
находятся для всех свободных клеток.
Платежи a i и b j не обязательно должны
быть положительны, поскольку не исключено,
что «перевозчик» сам платит тому или иному
пункту какую-то премию за перевозку.

38. Теорема «о платежах».

ai
Для заданной совокупности платежей
и b jсуммарная косвенная стоимость
перевозок при любом допустимом плане
сохраняет одно и тоже значение
m
n
F = åå c ij xij =c - const.
i =1 j =1
В этой формуле с зависит только от
совокупности платежей и не зависит от того,
каким именно допустимым планом
пользуемся.

39. Теорема оптимальности.

Если для всех базисных клеток
a i + b j = cij = c ij
а для всех свободных клеток
a i + b j = cij < cij
,
то допустимый план является оптимальным и
никаким способом улучшен быть не может.

40. Пример

Найти опорное решение методом
минимальной стоимости
и проверить оптимальность решения
методом потенциалов.

41.

42.

43.

Находим потенциалы базисных клеток
a1 + b1 = c11 = 2,
a1 + b 2 = c12 = 3,
a1 + b3 = c13 = 1,
a 22 + b = c22 = 2.

44.

Положим a1 = 0 и решим систему.
Получим b1 = 2, b 2 = 3, a 2 = -1, b3 = 1.
Найдем псевдостоимости пустых клеток
c21 = a 2 + b1 = -1 + 2 = 1,
c23 = a 2 + b3 = -1 + 1 = 0.
c21 = 1 < c21 = 4, c23 = 0 < c23 = 5.
План перевозок оптимален
X min = (30,10, 20, 0,30, 0),
F min = 2 × 30 + 3 ×10 + 1 × 20 + 2 × 30 = 150.

45. Пример 2.

На складах имеются запасы продукции
90, 400 и 110 тонн соответственно.
Потребители должны получить эту
продукцию в количествах 140, 300 и 160
тонн соответственно. Найти такой план
закрепления поставщиков к
потребителям, при котором суммы
затрат на перевозки минимальны.

46.

Расходы на перевозки 1 т продукции
заданы матрицей (у.е.)
æ 2 5 2ö
ç
÷
C = ç 4 1 5÷
ç3 6 8÷
è
ø
Сумма потребностей и сумма запасов
равны 140+300+160=90+400+110=600.
Модель закрытая.

47.

48.

План
0 ö
æ 90 0
ç
÷
X = ç 0 300 100 ÷
ç 50 0
÷
60
è
ø
Fmin = 2 × 90 + 1× 300 + 5 ×100 + 3 × 50 + 8 × 60 = 1600 y.e.

49.

2)Проверим план на оптимальность
методом потенциалов.
В таблице занято клеток
m + n -1 = 3 + 3 -1 = 5
Для них найдем потенциалы.

50.

a1 + b1 = 2,
a 2 + b 2 = 1,
a 2 + b 3 = 5,
a 3 + b1 = 3,
a 3 + b 3 = 8.
Положим a1 = 0.
Решим систему:
b1 = 2, a 3 = 1, b3 = 7, a 2 = -2, b 2 = 3.

51. Внесем в таблицу потенциалы занятых клеток

52.

Найдем оценки свободных клеток.
c12 = a1 + b 2 = 3,
g 12 = c12 - c12 = 5 - 3 = 2 > 0,
c13 = a1 + b3 = 7,
g 13 = c13 - c13 = 2 - 7 = -5 < 0,
c21 = a 2 + b1 = -2 + 2 = 0,
uur
c32 = a 3 + b 2 = 1 + 3 = 4.
g 21 = c21 - c21 = 4 - 0 = 4 > 0,
g 32 = c32 - c32 = 6 - 4 = 2 > 0.
Решение не оптимально, т.к. имеется
отрицательная оценка.

53.

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

54.

Около свободной клетки цикла ставится (+), а
затем поочередно(-) , (+).У вершин со знаком
(-) выбирают минимальный груз, его
прибавляют к грузам, стоящим у вершин со
знаком (+) и отнимают от грузов у вершин со
знаком (-). В результате перемещения
получают новый опорный план. Это решение
проверяют на оптимальность и т. д. до тех
пор ,пока не получится оптимальное
решение.

55.

56.

57.

58.

Получили новое решение
0
60 ö
æ 30
ç
÷
X = ç 0 300 100 ÷ .
ç110 0
÷
0
è
ø
Проверим его на оптимальность,
вычислив потенциалы базисных клеток.

59.

Потенциалы заполненных клеток
a1 + b1 = 2,
a 2 + b 2 = 1,
a 3 + b1 = 3,
a1 + b3 = 2,
a 2 + b 3 = 5.
a1 = 0.
b1 = 2, a 3 = 1, b3 = 2, a 2 = 3, b 2 = -2.

60.

Оценки свободных клеток
c12 = a1 + b 2 = 0 - 2 = -2,
g 12 = c12 - c12 = 5 - (-2) = 7 > 0,
c21 = a 2 + b1 = 3 + 2 = 5,
g 21 = c21 - c21 = 4 - 5 = -1 < 0,
c32 = a 3 + b 2 = 1 - 2 = -1,
uur
c33 = a 3 + b 3 = 1 + 2 = 3.
g 32 = c32 - c32 = 6 - (-1) = 7 > 0,
g 33 = c33 - c33 = 8 - 3 = 5 > 0.
План не оптимален, т.к. оценка клетки
(21) отрицательна.

61.

62.

63.

0 90 ö
æ 0
ç
÷
X = ç 30 300 70 ÷
ç110 0
÷
0
è
ø
Новый план
Снова проверяем его на
оптимальность. Для занятых клеток
a + b = 2,
Находим
1
3
a 2 + b1 = 4,
a 2 + b 2 = 1,
a 2 + b 3 = 5,
a 3 + b1 = 3.
a1 = 0.
b3 = 2, a 2 = 3, b 2 = -2, a 3 = 2, b1 = 1.

64.

Для свободных клеток псевдостоимости
равны
c11 = a1 + b1 = 0 + 1 = 1,
c12 = a1 + b 2 = 0 - 2 = -2,
c32 = a 3 + b 2 = 2 - 2 = 0,
uur
c33 = a 3 + b3 = 2 + 2 = 4.

65.

Оценки свободных клеток
g 11 = c11 - c11 = 2 - 1 = 1 > 0,
g 12 = c12 - c12 = 5 - (-2) = 7 > 0,
g 32 = c32 - c32 = 6 - 0 = 6 > 0,
g 33 = c33 - c33 = 8 - 4 = 4 > 0.

66.

Все оценки положительны, поэтому план
оптимален.
0 90 ö
æ 0
Ответ:
ç
÷
X = ç 30 300 70 ÷
.
При этом
ç110
è
0
0 ÷ø
Font = 90 × 2 + 30 × 4 + 300 ×1 + 70 × 5 + 110 × 3 = 1280.
По сравнению с первоначальным планом
расходы уменьшились на величину
1610-1280=330у.е.
English     Русский Rules