Транспортная задача и её применение
Исторические этапы исследований транспортной задачи
Исторические этапы исследований транспортной задачи
3 основные постановки транспортной задачи:
3 основные постановки транспортной задачи:
Задачи, относящиеся к транспортным:
Представление транспортной задачи
Общая постановка задачи ТЗ
2. Экономико-математическая модель транспортной задачи
3.1. Постановка задачи, основные определения
Открытая модель транспортной задачи
Модель закрытой транспортной задачи в расширенном виде
Метод решения транспортной задачи
3. Пример составления ЭММ транспортной задачи.
Построение ЭММ задачи
ЭММ транспортной задачи
4. Решение ЭММ транспортной задачи в MS Excel
Ввод формул для ограничений
Ввод формул для ограничений
Ввод формул для целевой функции
Аргументы функции СУММПРОИЗВ
Исходные условия задачи
Данные – Поиск решения
Оптимальный план
Оптимальный план
Применение транспортных моделей
Литература
3.18M
Category: mathematicsmathematics

Транспортная задача её применение (1)

1. Транспортная задача и её применение

План:
1. Постановка задачи
2. Экономико-математическая модель задачи
3. Пример составления ЭММ транспортной задачи.
4. Решение ЭММ транспортной задачи в MS Excel.

2.

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

3. Исторические этапы исследований транспортной задачи

3.1. Постановка задачи, основные определения
Исторические этапы исследований
транспортной задачи
4
I этап
1930 г. - «Планирование перевозок»
Формулировка задачи: «Основной задачей плана соединения
исходных пунктов груза с местами назначения является
достижение наименьших затрат при выполнении перевозок
всей суммы грузов».
А. Н. Толстой «Методы нахождения суммового километража
при планировании перевозок в пространстве», 1930
Задача национального плана перевозок, позволяющего
минимизировать суммарный километраж в железнодорожных
перевозках при наличии не более двух поставщиков (впервые
сформулирована транспортная задача)

4. Исторические этапы исследований транспортной задачи

3.1. Постановка задачи, основные определения
4
Исторические этапы исследований
транспортной задачи
II этап
Одну из разновидностей транспортной задачи в 1941 г.
поставил американец Ф.Хичкок (проблема Хичкока).
Детально разобрал Т.Ч. Купманс, который работал
членом Объединенного комитета перевозок во время
Второй мировой войны.
III этап
Первый точный метод решения транспортной задачи
(«метод потенциалов») разработан в 1949г.
Леонидом Канторовичем.
Канторович Л. В., Гавурин М. К., Применение математических методов в
вопросах анализа грузопотоков, Сб. ст. Проблемы повышения
эффективности работы транспорта, АН СССР, 1949

5. 3 основные постановки транспортной задачи:

3.1. Постановка задачи, основные определения
5
3 основные постановки
транспортной
:
задачи:
1. Необходимо найти оптимальную структуру
транспортных средств, обеспечивающую
минимизацию издержек на транспортировку.
эксплуатационные и экономические
показатели зависят от состава транспорта

6.

3.1. Постановка задачи, основные определения
6
3 основные постановки транспортной
задачи:
2. Необходимо установить такое распределение
грузов между имеющимися в хозяйстве видами
транспорта, при котором затраты на перевозки
всего объёма грузов были бы минимальными
эффективность использования различного транспорта на
одной и той же работе не всегда одинакова

7. 3 основные постановки транспортной задачи:

3.1. Постановка задачи, основные определения
7
3 основные постановки транспортной
задачи:
3. Задача прикрепления потребителей
к поставщикам
экономичный план перевозок однородного груза из
пункта производства в пункты потребления

8.

3.1. Постановка задачи, основные определения
8
минимум денежноматериальных затрат на
перевозки
1.
минимум
приведенных
затрат
4.
Критерии
оптимизации
транспортной
задачи
2.
3.
минимум
объёма
транспортн
ых работ
минимум
затрат
времени на
перевозки

9. Задачи, относящиеся к транспортным:

прикрепление потребителей ресурса к
производителям;
привязка пунктов отправления к пунктам
назначения;
взаимная привязка грузопотоков прямого и
обратного направлений;
отдельные задачи оптимальной загрузки
промышленного оборудования;
оптимальное распределение объемов выпуска
промышленной продукции между заводамиизготовителями и др.

10. Представление транспортной задачи

11. Общая постановка задачи ТЗ

состоит
перевозок
в
определении
оптимального
плана
некоторого однородного груза из
m
пунктов отправления в n пунктов потребления.
При этом в качестве критерия оптимальности
берется чаще всего
либо минимальная стоимость
перевозок всего однородного груза, либо минимальное
время его доставки.

12. 2. Экономико-математическая модель транспортной задачи

Дано:
• Множество I, включающее
имеющегося в количествах
• Множество J, включающее
m пунктов отправления груза,
ai (i=1…m)
n пунктов потребления, в каждом из
которых имеется спрос на данный груз в количестве bj (j=1…n)
• Затраты
Найти:
cij на перевозку единицы груза между пунктами i и j
• План перевозок X = (xij), согласно которому груз из пунктов
отправления перевозится в пункты потребления
с минимальными транспортными издержками, а спрос
удовлетворяется полностью.
12/18

13. 3.1. Постановка задачи, основные определения

11
потребители
поставщики
Потребители
Поставщики
1
…
c11
1
x11
…
…
xi1
…
…
m
Спрос
b1
x1j
…
…
xij
…
…
bj
…
…
cmj
xmj
…
n
…
…
стоимость доставки единицы
груза от i-го поставщика к j-ому
потребителю
Запас
c1n
x1n
…
cij
…
cm1
xm1
…
…
c1j
…
ci1
i
…
j
…
…
cin
xin
…
bn
ai
…
cmn
xmn
a1
am

14.

Транспортная задача называется закрытой, если
суммарный объем отправляемых грузов .равен
суммарному объему потребности в этих грузах по
пунктам назначения, т.е.
m
n
a = b
i =1
i
j =1
j
В противном случае, ТЗ называется открытой.
m
n
a b
i =1
i
j =1
j

15.

16
3.2. Закрытая и открытая транспортная задача
Закрытая модель
транспортной
задачи
Открытая модель
транспортной
задачи
Спрос равен запасу
Спрос не равен
запасу
m
n
m
a i
i
1
b
j
1
n
a i
j
i
1
b
j
1
j

16. Открытая модель транспортной задачи

18
3.2. Закрытая и открытая транспортная задача
Открытая модель транспортной
задачи
m
1. Запас превышает
спрос
2. Спрос превышает
запас
n
a i
i
b j
1
j
m
1
n
a i
i
1
b j
j
1

17.

17
3.2. Закрытая и открытая транспортная задача
Модель закрытой транспортной задачи
в кратком виде
m
n
Z
При ограничениях:
c ij x ij
min
i 1 j 1
n
x ij
a i ,i
x ij
b
1, m
i
1
m
i
1
x ij
0
j
, j
1, n

18. Модель закрытой транспортной задачи в расширенном виде

Z = c11 x11 + c12 x12 + ... + c1n x1n + c21 x21 + c22 x22 + ... + cmn xmn → min
x11 + x12 + ... + x3 = a1
x21 + x22 + ... + x2n = a2
......................................
x
+x
+ ... + x
=a
m1
m2
mn
m
x11 + x21 + ... + xn1 = b1
x12 + x22 + ... + xn 2 = b2
......................................
x
+x
+ ... + x
=b
2n
mn
n
1n
x 0, i = 1, m,
ij
j = 1, n

19.

Открытую задачу необходимо привести к закрытой
форме.
В случае, если:
потребности по пунктам потребления превышают
запасы пунктов отправления, то вводится фиктивный
поставщик с недостающим объемом отправления;
запасы поставщиков превышают потребности
потребителей, то вводится фиктивный потребитель с
необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с
реальными, имеют нулевые оценки.
После введения фиктивных пунктов задача
решается как закрытая.

20.

19
3.2. Закрытая и открытая транспортная задача
1. Запас превышает спрос
m
n
C
min
c ij x ij
i 1 j 1
При ограничениях:
m
если
n
i
x ij
a i
x ij
b j
1
m
i
1
x ij
0
n
a i
i
1
b j
j
1
Не требуется весь имеющийся груз
вывозить от поставщика, после
удовлетворения спроса часть его
может остаться не вывезенной
Потребности (спрос) каждого
потребителя необходимо
удовлетворить полностью

21.

20
3.2. Закрытая и открытая транспортная задача
1. Запас превышает спрос
Решение
m
n
ai
i 1
bj
bn 1
j 1
cn 1
0
Фиктивный
потребитель
При введении фиктивного потребителя
открытая модель преобразуется в закрытую

22.

21
3.2. Закрытая и открытая транспортная задача
2. Спрос превышает запас
m
n
C
min
c ij x ij
i 1 j 1
При ограничениях:
m
n
a i
если
i
b j
1
j
n
i
x ij
a i ,i
x ij
b
1, m
1
m
i
1
x ij
0
j
, j
1, n
1

23.

22
3.2. Закрытая и открытая транспортная задача
2. Спрос превышает запас
Решение
n
m
bj
j 1
ai
am 1
i 1
Фиктивный
поставщик

24.

Особенности ТЗ:
распределению подлежат однородные ресурсы;
условия задачи описываются только уравнениями;
все переменные выражаются в одинаковых
единицах измерения;
во всех уравнениях коэффициенты при неизвестных
равны единице;
каждая неизвестная встречается только в двух
уравнениях системы ограничений.

25.

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

26. Метод решения транспортной задачи

Распределительный метод предназначен для
решения транспортной задачи (распределение
определённого количества однородного
ресурса между потребителями).
Все переменные в задачах, решаемых
распределительным методом должны иметь
одну и ту же единицу измерения.

27. 3. Пример составления ЭММ транспортной задачи.

4 предприятия для производства продукции
используют некоторое сырьё. Спрос на сырьё
каждого из предприятий соответственно
составляет: 120, 50, 190 и 110 усл. ед.
Сырьё сосредоточено в трёх местах. Предложения
поставщиков сырья равны: 160, 140 и 170 усл. ед.
На каждое предприятие сырьё может завозиться от
любого поставщика.
Требуется составить план перевозок, при котором
общая стоимость перевозок будет минимальна.

28.

Тарифы перевозок известны и задаются
матрицей
7 8 1 2
C = 4 5 9 8
9 2 3 6
Сij
- тариф на перевозку сырья от i-го
поставщика j-му потребителю.
Тариф – стоимость перевозки единицы сырья.

29. Построение ЭММ задачи

Пусть хij- количество сырья, перевозимого от i-го
поставщика j -му потребителю.
m
n
a = b = 470
i =1
i
j =1
j
следовательно, задача закрытого типа

30. ЭММ транспортной задачи

Z= 7x11 + 8x12 + 1x13 +2x14 + 4x21 + 5x22 + 9x23 + 8x24 +9x31
+ 2x32 + 3x33 + 6x33 → min;
x11 + x12 + x13 + x14 = 160,
x21 + x22 + x23 + x24 = 140,
x31 + x32 + x33 + x34 = 170,
x11 + x21 + x31 = 120,
x12 + x22 + x32 = 50,
x13 + x23 + x33 = 190,
x14 + x24 + x34 = 110,
xij ≥ 0, i=1..3 ; j=1..4

31. 4. Решение ЭММ транспортной задачи в MS Excel

Исходная информация

32. Ввод формул для ограничений

33. Ввод формул для ограничений

34. Ввод формул для целевой функции

35. Аргументы функции СУММПРОИЗВ

36. Исходные условия задачи

37. Данные – Поиск решения

38. Оптимальный план

39. Оптимальный план

Минимальная общая стоимость перевозок = 1330 усл. ед.
Х13= 50 усл.ед. сырья следует перевезти от 1-го поставщика
3-ему предприятию;
Х14= 110 усл.ед. сырья следует перевезти от 1-го
поставщика 4-ему предприятию;
Х21= 120 усл.ед. сырья следует перевезти от 2-го
поставщика 1-ему предприятию;
Х22 = 20 усл.ед. сырья следует перевезти от 2-го
поставщика 2-ему предприятию;
Х32 = 30 усл.ед. сырья следует перевезти от 3-го
поставщика 2-ему предприятию;
Х33 =140 усл.ед. сырья следует перевезти от 3-го
поставщика 3-ему предприятию.

40. Применение транспортных моделей

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

41. Литература

Исследование операций в экономике [Текст] : учеб.пособие для вузов.
Рек. Минобразования РФ в кач-ве учебного пособия для вузов по
эконом.спец. и напр. / Н. Ш. Кремер [и др.]; под ред. Н. Ш. Кремера. - М.
:Юрайт, 2013. - 438 с. с.
Экономико-математические методы в примерах и задачах: Учеб. пос. /
А.Н.Гармаш, И.В.Орлова, Н.В.Концевая и др.; Под ред. А.Н.Гармаша - М.: Вуз.
уч.: НИЦ ИНФРА-М, 2014 - 416с.: 60x90 1/16 + ( Доп. мат. znanium.com).(п)
ISBN 978-5-9558-0322-7 - Режим доступа:
http://znanium.com/catalog/product/416547
Экономико-математическое моделирование: Практическое пособие по
решению задач / И.В. Орлова. - 2-e изд., испр. и доп. - М.: Вузовский
учебник: НИЦ Инфра-М, 2012. - 140 с.: 60x88 1/16. (обложка) ISBN 978-59558-0107-0 - Режим доступа: http://znanium.com/catalog/product/359462
Экономико-математические методы и модели: компьютерное
моделирование: Учебное пособие / И.В. Орлова, В.А. Половников. - 3-e
изд., перераб. и доп. - М.: Вузовский учебник: ИНФРА-М, 2011. - 389 с.:
60x90 1/16. (п) ISBN 978-5-9558-0208-4 - Режим доступа:
http://znanium.com/catalog/product/324780
English     Русский Rules