ТРАНСПОРТНАЯ ЗАДАЧА ЛЕКЦИЯ 1

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

ЛЕКЦИЯ 1

2. план

ПЛАН
1. Постановка транспортной задачи (ТЗ). Открытая и закрытая ТЗ.
2. Экономико-математическая модель ТЗ.
3. Этапы решения ТЗ.
4. Построение начального плана перевозок.

3.

Под названием «Транспортная задача» объединяется широкий
круг задач с единой математической моделью. Классическая
транспортная задача – задача о наиболее экономном плане перевозок
однородного продукта или взаимозаменяемых продуктов из пунктов
производства в пункты потребления, встречается чаще всего в
практических приложениях линейного программирования. Линейное
программирование является одним из разделов математического
программирования – области математики, разрабатывающей теорию и
численные методы решения многомерных экстремальных задач с
ограничениями.

4.

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

5.

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

6.

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

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
ТРАНСПОРТНОЙ ЗАДАЧИ
Найти
m
n
F cij xij min
(1)
i 1 j 1
при ограничениях
m
xij b j , j 1, n
i 1
n
xij ai , i 1, m
j 1
x 0
ij
(2)

8.

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

9.

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

10.

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

11.

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

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

ТРАНСПОРТНАЯ ТАБЛИЦА

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

НЕОБХОДИМОЕ И ДОСТАТОЧНОЕ
УСЛОВИЯ РАЗРЕШИМОСТИ
ТРАНСПОРТНОЙ ЗАДАЧИ
Для разрешимости транспортной задачи
необходимо и достаточно, чтобы запасы груза в
пунктах отправления были равны потребностям в
грузе в пунктах назначения, то есть, чтобы
выполнялось равенство
m
n
a b
i 1
i
j 1
− балансовые условия.
j

14.

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

15.

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

16.

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

17.

Будем называть план перевозок x0
0
x11
0
x21
0
x
...
0
xm1
0
x12
0
x22
...
xm0 2
... x10n
... x20n
... ...
0
... xmn
допустимым, если он удовлетворяет
системе ограничений (2).

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

ПРИМЕР. ЗАДАЧА ОРГАНИЗАЦИИ
ОПТИМАЛЬНОГО СНАБЖЕНИЯ .

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. Функциональные ограничения:

ФУНКЦИОНАЛЬНЫЕ ОГРАНИЧЕНИЯ:
По поставщикам (их 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 35,
x12 x22 x32 25,
x13 x23 x33 60,
x14 x24 x34 20,
x15 x25 x35 30.
xij 0.

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

ЭТАПЫ РЕШЕНИЯ ТРАНСПОРТНОЙ
ЗАДАЧИ
• Составляют математическую модель задачи.
• Находят исходное опорное решение.
• Проверяют это решение на оптимальность.
• Переходят от одного опорного решения к другому.

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

ОПРЕДЕЛЕНИЕ ИСХОДНОГО
ДОПУСТИМОГО РЕШЕНИЯ
1. Метод «северо-западного угла»
Метод заключается в том, что заполнение клеток таблицы
начинают с левой верхней клетки (северо-западная часть
таблицы) для перевозки x11 и продолжают вниз и вправо,
заканчивая клеткой для перевозки xmn .
При этом способе распределения на тарифы cij не
обращают внимания.

24. Найти опорный план транспортной задачи методом СЕВЕРО-ЗАПАДНОГО УГЛА

НАЙТИ ОПОРНЫЙ ПЛАН ТРАНСПОРТНОЙ
ЗАДАЧИ МЕТОДОМ СЕВЕРО-ЗАПАДНОГО УГЛА

25.

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

26.

В результате получим опорный план
0
120 40 0
X 0 10 130 0
0
0
60
110
При данном плане перевозок общая стоимость перевозок
составляет .

27.

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

28.

29.

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

30.

31.

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

32.

33.

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

34.

35.

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

36.

В результате получим опорный план
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