Презентация по Информатике на тему Применение распределительного метода для решения задач

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

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

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

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

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

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

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

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

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

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

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

Проверка опорного решения на выполнение граничных условий а) по строкам: 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 2 3 4 113 112 112 112 1   67 44 - 42 - 45 240 40 - 2 70 43 454 40 - 42 850 42 0 3 84 29 450 26 - 24 - 27 - 4 46 67 150 62 - 65 - 61 - 5 91 22 250 19 - 17 - 19 - 6 70 43 800 40 - 42 - 41 - 7 112 0 -   0 1700 0 60 0 700

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

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