Презентация по математике "Методы линейного программирования"

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

Введение Распределить объекты социальной инфраструктуры таким образом, чтобы количество их посещений в месяц было максимальным. Порядок выполнения задачи: 1. Записать математическое условие задачи в структурном виде. 2. Опорное решение найти методом аппроксимации. Проверить оптимальность опорного решения методом потенциалов. Задачу решить с дополнительными ограничениями: а) не менее половины площади зоопарков должны быть размещены на третьем участке; б) площадь парков на четвертом участке должны быть не более 300 га. 4. Записать ответ задачи.

Табличная форма записи исходных данных Посещаемость по участкам (тыс. чел.) II 42 40 26 62 19 III 45 42 24 65 17 IV 40 42 27 61 19 42 1600 41 700 Площадь, объектов га 240 1304 900 150 250 800   № п/п 1 2 3 4 5 6 Объекты Стадионы Парки Зоопарки Диснейленды Лодочная станции Лыжные базы Итого земли, га I 44   43   29   67   22   43   40 2104 1700

Формализация исходных данных задачи:

Запись задачи транспортного типа в Запись задачи транспортного типа в структурной форме: структурной форме:

Табличное представление исходных данных задачи Посещаемость по участкам (тыс. чел.) III II 42 45 42 40 24 26 65 62 19 17 I 44 43 29 67 22 43 2104 40 1700 42 1600 41 700 № п/п 1 2 3 4 5 6 Объекты Стадионы Парки Зоопарки Диснейленды Лодочная станции Лыжные базы Площади участков, га IV 40 42 27 61 19 Площадь объектов, га 240 1304 900 150 250 800 3644 6104

сбалансированному виду с помощью фиктивных объектов (строки, Приведение задачи к столбца)

Табличное представление исходных данных задачи № п./п. Объекты 1 2 3 4 5 6 7   Стадионы Парки Зоопарки Диснейленды Лодочная станции Лыжные базы Фиктивный Площади  участков, га Посещаемость по участкам  (тыс. чел.) I 44 43 29 67 22 43 0 II 42 40 26 62 19 40 0 III 45 42 24 65 17 42 0 IV 40 42 27 61 19 41 0 Площадь объектов , га 240 1304 900 150 250 800 2460 2104 1700 1600 700 6104 6104

Учет дополнительных условий Не менее половины площадей зоопарков должны быть размещены  на третьем участке

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

Проверка опорного решения на выполнение граничных условий  а) по строкам: 1.240=240 2. 454+850=1304 3.450=450 4. 150=150 5. 250=250 6. 800=800 7.1700+60+700=2460 б) по столбцам: 1. 454+450+150+250+800=2104 2. 1700=1700 3. 240+850+60=1150 4. 700=700

Проверка опорного решения на оптимальность

Потенциалы и оценки для опорного решения задачи 1 113 2 112 3 112 4 112   №   1   2 3 4 5 6 7 ji 67 70 84 46 91 70 112 454 450 150 250 800 44 - 43 29 67 22 43 0 -   1700 42 - 40 - 26 - 62 - 19 - 40 - 0 240 850 60 45 42 24 - 65 - 17 - 42 - 0 700 40 - 42 0 27 - 61 - 19 - 41 - 0

Окончательное решение задачи Посещаемость по участкам (тыс. чел.) I II III IV 44 43 29 67 22 43   454 450 150 250 800 240 850 42 40 26 62 19 40 45 42 24 450 65 17 42 2104   1700 1600   Площадь участков, га 240   1304   900   150   250   800     40 42 27 61 19 41 700 № п/п 1 2 3 4 5 6 Объекты Стадионы Парки Зоопарки Диснейленды Лодочная станции Лыжные базы Площади участков, га Zопт= 129022+24*450=139822 ц

• Максимальная посещаемость будет равна Ответ задачи 139822 тыс. чел. при следующем распределении объектов по участкам: третьем участке на третьем участке - стадион: 240 га на 3 участке - парки: 454 га на 1 участке и 850 га на - зоопарки: 450 га на первом участке и 450 га - диснейленд: 150 га на 1 участке - лодочная станция: 250 га на 1 участке - лыжная база: 800 га на 1 участке