Россия, Приморский край, Красноармейский район, с. Богуславец
МКОУ "Средняя общеобразовательная школа №24"
Учитель информатики
Марченко Татьяна Викторовна
Цели урока:
План урока:
Ход урока ( 2 часа)
На прошлых уроках мы познакомились с вами с информационными моделями. На схеме представлена последовательность этапов информационного моделирования.
|
Выбор объекта моделирования |
|
Определение цели моделирования |
|
Системный анализ объекта моделирования |
|
Построение информационной модели |
|
Создание компьютерной модели |
|
Объектом моделирования может быть любой реальный объект, процесс, явление (любая реальная система) |
|
Цели моделирования определяются характером использования будущей модели |
|
Основные понятия системологии:
|
|
Способы представления информационных моделей:
|
|
Средства разработки компьютерных моделей:
|
|
Использование компьютерной модели |
Глядя на такую сложную схему, вы должны понимать, какие практические задачи требуют столь сложной последовательности действий. Таких задач очень много, но, прежде всего — это задачи планирования и управления.
К ним относятся:
Постановка задачи планирования выглядит следующим образом:
Нужно определить значение плановых показателей с учетом ограниченности ресурсов при условии достижения стратегической цели. Это и будет оптимальным планом.
Если мы хотим использовать компьютер для решения задачи оптимального планирования, то нам нужно построить математическую модель, т.е. перевести задачу на язык чисел, формул, уравнений и других средств математики. В полном объеме для реальных систем эта задача очень сложная. Поэтому пойдем по пути упрощения.
Рассмотрим очень простой пример.
Пример. Школьный кондитерский цех готовит пирожки и пирожные. В силу ограниченности емкости склада за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Если выпускать только пирожные, за день можно произвести не более 250 штук, пирожков же можно произвести 1000, если при этом не выпускать пирожных. Стоимость пирожного вдвое выше, чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку.
Выработаем математическую модель задачи.
Плановыми показателями являются:
x — дневной план выпуска пирожков;
у — дневной план выпуска пирожных.
Что в этом примере можно назвать ресурсами производства? Из того, о чем говорится в условии задачи, это: длительность рабочего дня — 8 часов;
вместимость складского помещения — 700 мест.
Предполагается для простоты, что другие ресурсы (сырье, электроэнергия и пр.) не ограничены. Формализацию цели — достижение максимальной выручки цеха — мы обсудим позже.
Получим соотношения, следующие из условий ограниченности времени работы цеха и вместимости склада, то есть суммарного числа изделий. Из условия задачи следует, что на изготовление одного пирожного затрачивается в 4 раза больше времени, чем на изготовление одного пирожка. Если обозначить время изготовления пирожка — t мин, то время изготовления пирожного будет равно
4t мин. Значит, суммарное время на изготовление х пирожков и у пирожных равно tx+4ty = (x +4y)t.
Но это время не может быть больше длительности рабочего дня. Отсюда следует неравенство:
(x + 4y)t £ 8×60, или (x+4y)t £ 480.
Легко вычислить t — время изготовления одного пирожка. Поскольку за рабочий лень их может быть изготовлено 1000 штук, то на один пирожок затрачивается 480/1000=0,48 мин. Подставляя это значение в неравенство, получим: (х+4у) 0,48 £ 480. Отсюда: х+4у £ 1000.
Ограничение на общее число изделий дает совершенно очевидное неравенство: х+у£ 700.
К двум полученным неравенствам следует добавить условия положительности значений величин х и у (не может быть отрицательного числа пирожков и пирожных). В итоге мы получаем систему неравенств:
(1)
А теперь перейдем к формализации стратегической цели: получению максимальной выручки. Выручка — это стоимость всей проданной продукции. Пусть цена одного пирожка — r рублей. По условию задачи, цена пирожного в два раза больше, то есть 2r рублей. Отсюда стоимость всей произведенной за день продукции равна rx + 2ry = r(x + 2у). Будем рассматривать записанное выражение как функцию от х, у: f(x,у) = r(x+2y). Она называется целевой функцией.
Поскольку значение r — константа, то максимальное значение f(х,у) будет достигнуто при максимальной величине выражения (х + 2у). Поэтому, в качестве целевой функции можно принять f(х,у) = х+2у. (2)
Следовательно, получение оптимального плана свелось к следующей математической задаче: найти значения плановых показателей х и у, удовлетворяющих системе неравенств (1), при которых целевая функция (2) принимает максимальное значение.
Итак, математическая модель задачи оптимального планирования для школьного кондитерского цеха построена.
Математическая дисциплина, которая посвящена решению таких задач, называется математическим программированием. А поскольку в целевую функцию f(x,у) величины х и у входят линейно (то есть в первой степени), то наша задача относится к разделу этой науки, который называется линейным программированием.
Система написанных выше неравенств представляется на координатной плоскости четырехугольником, ограниченным четырьмя прямыми, соответствующими линейным уравнениям х + 4у = 1000; х+у= 700; х = 0 (ось ОУ); у = 0 (ось ОХ).
На рисунке эта область представляет собой четырехугольник ABCD и выделена заливкой. Любая точка четырехугольника является решением системы неравенств (1). Например, такой точкой является точка с координатами х=200, у=100. Ей соответствует значение целевой функции f(200,100) = 400. А точке х = 600, у = 50 соответствует f(600,50) = 700. Но, очевидно, искомым решением является та точка области АВСD, в которой целевая функция максимальна. Нахождение этой точки производится с помощью методов линейного программирования.
Эти методы имеются в математическом арсенале MS Excel, с ними мы сегодня и познакомимся.
В программу Excel заложены возможности решения задач математического программирования. Средство, о котором идет речь, называется «Поиск решения». Соответствующая команда находится в меню Сервис.
«Поиск решения» — одно из самых мощных средств табличного процессора Excel, и мы не будем даже пытаться освоить все его возможности. Покажем на рассмотренном нами простейшем примере («пирожки и пирожные»), как воспользоваться указанным средством.
Вначале надо подготовить электронную таблицу к решению задачи оптимального планирования.
Теперь следует вызвать программу оптимизации «Поиска решения» и сообщить ей, где расположены данные. Для этого надо выполнить команду Сервис/ Поиск решения. На экране откроется соответствующая форма
Заполняем ее по следующему образцу.
Для ввода ограничений щелкаем на кнопке «Добавить» и заполняем соответствующую форму.
На заключительном этапе щелкаем на кнопке «Параметры» и устанавливаем флажок на переключателе «Линейная модель». Другие параметры не меняем. После щелчка по кнопке ОК, возвращаемся в форму «Поиск решения»
Щелкаем на кнопке «Выполнить»
В таблице появляются решения. Кроме этого на экране появится еще одна форма «Результаты поиска решения»
При решении подобных задач могут возникнуть проблемы. Например, искомого оптимального решения может вовсе не существовать — тогда программа об этом сообщит.
Задания для самостоятельного решения.
Внесите изменение в постановку задачи оптимального планирования с учетом еще одного ограничения: число пирожных должно быть не меньше числа пирожков.
Коротко о главном
Оптимальное планирование заключается в определении значений плановых показателей с учетом ограниченности ресурсов при условии достижения стратегической цели.
Условия ограниченности ресурсов математически представляются в виде системы неравенств.
Формализация стратегической цели сводится к построению целевой функции и назначению определенных условий для ее величины: чаще всего достижение максимума или минимума.
Математическое программирование — это раздел математики, содержащий методы решения задач оптимального планирования.
Линейное программирование — это раздел математического программирования, решающий задачи оптимального планирования с линейной целевой функцией.
1. а) В чем состоит задача оптимального планирования?
б) Что такое плановые показатели, ресурсы, стратегическая цель? Приведите примеры.
2. а) Что такое математическое программирование, линейное программирование?
3. а) Постройте математическую модель к следующей задачи планирования
На предприятии производится 2 модели книжных полок А и В из досок. А требует для производства 0,5 кв.м.. а В — 0,7 кв.м. Для изготовления единицы продукции вида А требуется 2 ч рабочего времени, типа В — 2,5 часа. Существует ограничение на материальные ресурсы и на фонд рабочего времени. Наличие досок 1500 кв.м., рабочее время — 40 ч. На рынке эти полки пользуются следующим спросом: А — 15 руб, В — 28 руб. Определить сколько и какого вида необходимо выпускать продукции, чтобы прибыль была максимальной.
