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

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

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

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

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

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

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

2.62M

Category:

programming

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

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

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
c21c22 ...c2 n
C
.................
cm1cm 2 ...cmn

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

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

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

12.

При выполнении этого условия модель
транспортной задачи называется
закрытой. Если балансовое условие не
выполняется, то есть
m
n
,
ai bj
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 вносит за перевозку
единицы груза какую-то сумму i , а
каждый пункт назначения вносит
сумму j . Эти платежи передаются
некоторому третьему лицу, например,
перевозчику. Величины i и jсвяжем
i , где
равенствами
j cij –
тарифы
cij для базисных клеток.

36.

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

37.

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

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

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

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

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

40. Пример

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

41.

42.

43.

Находим потенциалы базисных клеток
1 1 c11 2,
1 2 c12 3,
1 3 c13 1,
2 c22 2.
2

44.

Положим 1 0 и решим систему.
Получим 1 2, 2 3, 2 1, 3 1.
Найдем псевдостоимости пустых клеток
c21 2 1 1 2 1,
c23 2 3 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.

1 1 2,
2 2 1,
2 3 5,
3 1 3,
3 3 8.
Положим 1 0.
Решим систему:
1 2, 3 1, 3 7, 2 2, 2 3.

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

52.

Найдем оценки свободных клеток.
c12 1 2 3,
12 c12 c12 5 3 2 0,
c13 1 3 7,
13 c13 c13 2 7 5 0,
c21 2 1 2 2 0,
c32 3 2 1 3 4.
21 c21 c21 4 0 4 0,
32 c32 c32 6 4 2 0.
Решение не оптимально, т.к. имеется
отрицательная оценка.

53.

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

54.

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