Похожие презентации:
Транспортная задача её применение (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.
163.2. Закрытая и открытая транспортная задача
Закрытая модель
транспортной
задачи
Открытая модель
транспортной
задачи
Спрос равен запасу
Спрос не равен
запасу
m
n
m
a i
i
1
b
j
1
n
a i
j
i
1
b
j
1
j
16. Открытая модель транспортной задачи
183.2. Закрытая и открытая транспортная задача
Открытая модель транспортной
задачи
m
1. Запас превышает
спрос
2. Спрос превышает
запас
n
a i
i
b j
1
j
m
1
n
a i
i
1
b j
j
1
17.
173.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 → minx11 + 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.
193.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.
203.2. Закрытая и открытая транспортная задача
1. Запас превышает спрос
Решение
m
n
ai
i 1
bj
bn 1
j 1
cn 1
0
Фиктивный
потребитель
При введении фиктивного потребителя
открытая модель преобразуется в закрытую
22.
213.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.
223.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
Математика