Презентация к исследовательской работе "Математическая модель транспортной задачи Монжа-Канторовича"

Всероссийский форум научной молодежи«Шаг в будущее»

Исследовательская работа «Математическая модель транспортной задачи Монжа-Канторовича»

Автор: Подглазова Маргарита Игоревна Муниципальное бюджетное образовательное учреждение

"Дульдургинская средняя общеобразовательная школа" ученица 11- а класса Руководитель: Кибирева Ирина Валерьевна учитель математики высшей квалификационной категории

Муниципальное бюджетное образовательное учреждение

"Дульдургинская средняя общеобразовательная школа"

Линейное программирование  - математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Гаспа́р Монж , граф  деПелю́з  

французский математик, геометр, государственный деятель, морской министр.

Имя Гаспара Монжа внесено в список 72 величайших учёных Франции

Леонид Канторович (1939) Лауреат Нобелевской премии по экономике за 1975 год Леонид Канторович (1939) разработал эффективный математический аппарат теории оптимального производственного планирования, из которой впоследствии вырос целый раздел современной математики - линейное программирование,

Проблема:

как построить оптимальный план перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки?

Цель работы:

• Познакомиться с транспортной задачей Монжа-Канторовича и построить её математическую модель на примере поставки груза в магазины села Дульдурга.

Объект исследования: транспортная задача

Предмет исследования: задачи линейного программирования

Методы исследования: расчеты, анализ, сравнение

• Гипотеза : Если построить математическую модель транспортной задачи, то можно минимизировать затраты на транспортировку.

Задачи:

• Изучить литературу по теме
• Познакомиться с экономической и математической постановкой транспортной задачи
• Построить математическую модель транспортной задачи для поставки груза в магазины села Дульдурга
• Выполнить экспериментальную проверку полученных результатов

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

Типы транспортной задачи:

• по критерию стоимости – план перевозок является оптимальным, если достигается минимум затрат на его реализацию;
• по критерию времени – план перевозок оптимален, если на него затрачивается минимальное количество времени.

• Ford
• Fulkerson
•   Munkers
•   Kuhn
• Gleyzal
•   Golshtein. 

Методы решения

• Приближённые:

вычёркивания, северо-западного угла, минимального элемента, аппроксимации Фогеля

• Точные:

метод потенциалов и венгерский метод

Экономическая постановка транспортной задачи

• Экономическая постановка транспортной задачи следующая.
• Имеется m поставщиков и n потребителей некоторой продукции.
• Заданы тарифы (стоимость) перевозок единицы продукции от поставщиков к потребителям
• Известны объемы запасов у поставщиков и потребности каждого потребителя в продукции.

Математическая модель

• F=∑ n j=1 ∑ m i=1 c ij x ij →min,
• ∑ n j=1 x ij =a i,
• ∑ m i=1 x ij =b j,
• X ij ≥ 0 ( i = 1,m; j=1,n),
• Если ∑ m i=1 a j =∑ m j=1 b j , то задача закрытого типа

Таблица поставок

Поставщики

Потребители

1

1

2

с 11

2

x 11

c 12

…

c21

x 12

…

…

m

x 21

c 22

…

n

Запасы продукции

c m1

Потребности в продукции

…

x22

…

c 1n

b 1

c m2

…

x m1

a 1

x 1n

b 2

…

c 2n

x m2

…

a 2

x 2n

…

…

c mn

x mn

a m

b n

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

• Для составления математической модели необходимо:

• Обозначить переменные
• Проверить условие баланса
• Составить целевую функцию исходя из цели задачи
• Записать системы ограничений

Решения транспортной задачи в среде MS Excel

• Необходимо выполнить следующее:.
• 1. Разработать математическую модель задачи.
• 2. Найти минимальную стоимость перевозок, используя надстройку «Поиск решения» в среде MS Excel.
• Для решения задачи в среде MS Excel будем следовать по следующему плану[12]:
• 1. Откроем новый рабочий лист Excel.
• 2. В ячейки B3:F6 стоимость перевозок единицы груза.
• 3. В ячейках B16:F16 укажем формулы для расчета суммарной потребности продукции для  j -го пункта, в ячейках G12:G15 – формулы суммарного объема производства  i -го предприятия.
• 4. В ячейки B18:F18 заносим значения потребности продукции соответствующего пункта потребления, в ячейки H12:H15 заносим значения объема производства соответствующего предприятия.
• 5. В ячейку B20 занесем формулу целевой функции.
• 6. Выполним команду Сервис → Поиск решения. Откроется диалоговое окно Поиск решения. Если такой команды во вкладке Сервис нет, то следует подключить эту надстройку перейдя по Сервис → Надстройки, и поставив галочку напротив нужной, то есть Поиск решения.
• 7. В поле  Установить целевую ячейку указываем ячейку, содержащую оптимизируемое значение. Установим переключатель Равный в положение минимальному значению.
• 8. В поле Изменяя ячейки мышью зададим диапазон подбираемых параметров $B$12:$F$15.
• 9. В поле Ограничения введем необходимые ограничения и нажмем на кнопку Добавить, затем Выполнить.
• Оптимальность решения можно проверить, экспериментируя со значениями ячеек $B$12:$F$15.

Построение математической модели транспортной задачи для поставки груза в магазины села Дульдурга

Для построения модели я выбрала магазины: Читинка,

Ирина,

Весна и Рубль.

Пять поставщиков (пекарни) поставляют хлеб в четыре магазина.

• Ежедневная потребность этих магазинов составляет: Читинка - 170, Весна - 106, Ирина -160, Рубль – 90. Поставщики могут ежедневно поставлять ИП Басова Л.Н – 945 булок, ИП Басова Т.А – 675 булок, ИП Маркина С.В. – 810, Дарасун – 1620, Черновской Х.К. – 2025

Поставщи-ки

Потребители

Читинка

ИП Басова Л.М

Весна

с 11 =0,11

ИП Басова Т.А

ИП Маркина С.В

c 21 =0,12 x 21 =30

Ирина

x 11 =30

c 12 =0,16

Рубль

x 12 =28

с 13 =0

c 22 =0,19

c 31 =0

Дарасун

Запасы продукции

x 13 =0

x 22 =28

C 23 =0,07

Черновской Х.К

с 32 =0,22

x 31 =0

с 41 =54,67

c 14 =0,1

с 51 =68,33

x 41 =15

с 42 =0

Потребности в продукции

x 32 =28

x 23 =90

x 14 =40

с 33 =0

c 24 =0

a1=98

с 34 =0

b1=105

с 52 =93,18

c 51 =30

x 33 =0

с 43 =19,52

x 42 =0

x 24 =0

a2=148

x 43 =42

с 44 =16,4

b2=106

х 34 =0

c 53 =73,21

x 52 =22

a3=28

x 53 =28

c 54 =136,67

x 44 =50

b3=160

a4=107

x 54 =15

b4=105

a5=95

476 " width="640"

Проверяем условие баланса

∑ m i=1 a j =∑ m j=1 b j ,

a i =945+675+810+1620+2025=6075

b j =105+106+160+105=476

6075476

• ИП Басова Л.М. – 98 булок,
• ИП Басова Т.А – 148 булок,
• ИП Маркина С.В. – 28,
• Дарасун – 104,
• Черновской Х.К. – 95.
• Тогда получаем:

a i =98+148+28+104+95=476

b j =105+106+160+105=476

Целевая функция:

• F=30x 11 +28x 12 +0x 13 +40x 14 +30x 21 +28x 22 +90x 23 +0x 24 +0x 31 +28x 32 +0x 33 +0x 34 +15x 41 +0x 42 +42x 43 +50x 44 +30x 51 +22x 52 +28x 53 +15x 54 →min

• F=30x 11 +28x 12 +40x 14 +30x 21 +28x 22 +90x 23 +28x 32 +15x 41 +42x 43 +50x 44 +30x 51 +22x 52 +28x 53 +15x 54 →min

Ограничения задачи. Баланс по строкам и по столбцам имеет вид:

• Спасибо за внимание!