KNOWLEDGE HYPERMARKET


Оптимальное планирование

Гипермаркет знаний>>Информатика>>Информатика 11 класс>>Информатика: Оптимальное планирование


Оптимальное планирование


Проблема, к обсуждению которой мы теперь переходим, называется оптимальным планированием. Объектами планирования могут быть самые разные системы: деятельность отдельного предприятия, отрасли промышленности или сельского хозяйства, региона, наконец, государства. Постановка задачи планирования выглядит следующим образом:

• имеются некоторые плановые показатели: х, у и другие;

• имеются некоторые ресурсы: R1 R2 и другие, за счет которых эти плановые показатели могут быть достигнуты. Эти ресурсы практически всегда ограничены;

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

Нужно определить значение плановых показателей с учетом ограниченности ресурсов при условии достижения стратегической цели. Это и будет оптимальным планом.

Приведем примеры. Пусть объектом планирования является детский сад. Ограничимся лишь двумя плановыми показателями: числом детей и числом воспитателей. Основными ресурсами деятельности детского сада являются размер финансирования и площадь помещения. А каковы стратегические цели?

Естественно, одной из них является сохранение и укрепление здоровья детей. Количественной мерой такой цели является минимизация заболеваемости воспитанников детского сада.

Другой пример: планирование экономической деятельности государства. Безусловно, это слишком сложная задача, для того чтобы нам с ней полностью разобраться. Плановых показателей очень много: это объем производства различных видов промышленной и сельскохозяйственной продукции, план подготовки специалистов, количество вырабатываемой электроэнергии, размер зарплаты работников бюджетной сферы и многое другое. К ресурсам относятся: количество работоспособного населения, бюджет государства, природные ресурсы, энергетика, возможности транспортных систем и пр. Как вы понимаете, каждый из этих видов ресурсов ограничен. Кроме того, важнейшим ресурсом является время, отведенное на выполнение плана. Вопрос о стратегических целях довольно сложный. У государства их много, но в разные периоды истории приоритеты целей могут меняться.


Если мы хотим использовать компьютер для решения задачи оптимального планирования, то нам снова нужно построить математическую модель. Следовательно все, о чем говорилось в начале параграфа, должно быть переведено на язык чисел, формул, уравнений и других средств математики. В полном объеме для реальных систем эта задача очень сложная. Как и раньше, мы пойдем по пути упрощения.

Рассмотрим очень простой пример, из которого вы получите представление об одном из подходов к решению задачи оптимального планирования.

Пример. Школьный кондитерский цех готовит пирожки и пирожные. В силу ограниченности емкости склада за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Если выпускать только пирожные, за день можно произвести не более 250 штук, пирожков же можно произвести 1000, если при этом не выпускать пирожных. Стоимость пирожного вдвое выше, чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку.

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

Плановыми показателями являются:

х - дневной план выпуска пирожков;

у - дневной план выпуска пирожных.

Что в этом примере можно назвать ресурсами производства? Из того, о чем говорится в условии задачи, это:

длительность рабочего дня — 8 часов;

вместимость складского помещения — 700 мест.

Предполагается для простоты, что другие ресурсы (сырье, электроэнергия и пр.) не ограничены. Формализацию цели — достижение максимальной выручки цеха — мы обсудим позже.

Получим соотношения, следующие из условий ограниченности времени работы цеха и вместимости склада, то есть суммарного числа изделий.

Из условия задачи следует, что на изготовление одного пирожного затрачивается в 4 раза больше времени, чем на изготовление одного пирожка. Если обозначить время изготовления пирожка — t мин, то время изготовления пирожного будет равно 4t мин. Значит, суммарное время на изготовление х пирожков и у пирожных равно:

tх + 4ty = (x + 4y)t.

Но это время не может быть больше длительности рабочего дня. Отсюда следует неравенство

(х + 4у)t <= 8 · 60,
            или
(х+ 4у)1 <= 480.

Легко вычислить t - время изготовления одного пирожка. Поскольку за рабочий день их может быть изготовлено 1000 штук, то на один пирожок затрачивается 480/1000 = 0,48 мин. Подставляя это значение в неравенство, получим;

(х + 4у) · 0,48 <= 480.

Отсюда:

х + 4у <= 1000.

Ограничение на общее число изделий дает совершенно очевидное неравенство:

х + у < 700.

К двум полученным неравенствам следует добавить условия положительности значений величин х и у (не может быть отрицательного числа пирожков и пирожных). В итоге мы получаем систему неравенств:

   
    Система неравенств                                  Инф106.jpg
   
А теперь перейдем к формализации стратегической цели: получению максимальной выручки. Выручка - это стоимость всей проданной продукции. Пусть цена одного пирожка — r рублей. По условию задачи, цена пирожного в два раза больше, то есть 2r  рублей. 

Будем рассматривать записанное выражение как функцию от x, у:

f(x,y) - r(х + 2у).

Она называется целевой функцией.

Поскольку значение r - константа, то максимальное значение f(x,y) будет достигнуто при максимальной величине выражения (х + 2у). Поэтому, в качестве целевой функции можно принять:

f(x,y) = х + 2у.    Инф107.jpg
Следовательно, получение оптимального плана свелось к следующей математической задаче: найти значения плановых показателей х и у удовлетворяющих системе неравенств 'Инф106.jpg, при которых целевая функция 'Инф107.jpg принимает максимальное значение.

Итак, математическая модель задачи оптимального планирования для школьного кондитерского цеха построена.
Математическая дисциплина, которая посвящена решению таких задач, называется математическим программированием. А поскольку в целевую функцию f(x,y) величины х и у входят линейно (то есть в первой степени), то наша задача относится к разделу этой науки, который называется линейным программированием.

Система написанных выше неравенств представляется на координатной плоскости четырехугольником , ограниченным четырьмя прямыми, соответствующими линейным уравнениям:

     х + 4у = 1000;

     х + у = 700;
     х = 0 (ось ОУ);

     у - 0  (ось ОХ).


На рис. 2.19 эта область представляет собой четырехугольник ABCD и выделена заливкой. Любая точка четырехугольника является решением системы неравенств Инф106.jpg. Например, такой точкой является точка с координатами х = 200, у = 100. Ей соответствует значение целевой функции f(200,100) — 400. А точке х = 600, у = 50 соответствует


      Область поиска оптимального плана

     Рис. 2.19. Область поиска оптимального плана


f(600,50) = 700. Но, очевидно, искомым решением является та точка области ABCD, в которой целевая функция максимальна.    Нахождение этой точки производится с помощью методов линейного программирования.

Эти методы имеются в математическом арсенале MS Excel и в следующем параграфе вы узнаете, как ими воспользоваться.

Коротко о главном

Оптимальное планирование заключается в определении значений плановых показателей с учетом ограниченности ресурсов при условии достижения стратегической цели.

Условия ограниченности ресурсов математически представляются в виде системы неравенств.

Формализация стратегической цели сводится к построению целевой функции и назначению определенных условий для ее величины: чаще всего достижение максимума или минимума.

Математическое программирование — это раздел математики, содержащий методы решения задач оптимального планирования.

Линейное программирование — это раздел математического программирования, решающий задачи оптимального  планирования с линейной целевой функцией.


Вопросы и задания

1. а) В чем состоит задача оптимального планирования?

б) Что такое плановые показатели, ресурсы, стратегическая цель? Приведите примеры.

2. а) Попробуйте сформулировать содержание оптимального планирования своей учебной деятельности.

б) Что такое математическое программирование, линейное программирование?

3.а) Сформулируйте задачу оптимального планирования длл того же школьного кондитерского цеха, в котором выпускается три вида продукции: пирожки, пирожные и коржики.

б) Внесите изменение в постановку задачи оптимального планирования из темы 17 для двух видов продукции с учетом еще одного условия ограничения: число пирожных должно быть не меньше числа пирожков. На координатной плоскости постройте область поиска решения.



Семакин И.Г., Хеннер Е.К., Информатика и ИКТ, 11

Отослано читателями из интернет-сайтов


Содержание урока
1236084776 kr.jpg конспект урока                       
1236084776 kr.jpg опорный каркас  
1236084776 kr.jpg презентация урока
1236084776 kr.jpg акселеративные методы 
1236084776 kr.jpg интерактивные технологии 

Практика
1236084776 kr.jpg задачи и упражнения 
1236084776 kr.jpg самопроверка
1236084776 kr.jpg практикумы, тренинги, кейсы, квесты
1236084776 kr.jpg домашние задания
1236084776 kr.jpg дискуссионные вопросы
1236084776 kr.jpg риторические вопросы от учеников

Иллюстрации
1236084776 kr.jpg аудио-, видеоклипы и мультимедиа 
1236084776 kr.jpg фотографии, картинки 
1236084776 kr.jpg графики, таблицы, схемы
1236084776 kr.jpg юмор, анекдоты, приколы, комиксы
1236084776 kr.jpg притчи, поговорки, кроссворды, цитаты

Дополнения
1236084776 kr.jpg рефераты
1236084776 kr.jpg статьи 
1236084776 kr.jpg фишки для любознательных 
1236084776 kr.jpg шпаргалки 
1236084776 kr.jpg учебники основные и дополнительные
1236084776 kr.jpg словарь терминов                          
1236084776 kr.jpg прочие 

Совершенствование учебников и уроков
1236084776 kr.jpg исправление ошибок в учебнике
1236084776 kr.jpg обновление фрагмента в учебнике 
1236084776 kr.jpg элементы новаторства на уроке 
1236084776 kr.jpg замена устаревших знаний новыми 

Только для учителей
1236084776 kr.jpg идеальные уроки 
1236084776 kr.jpg календарный план на год  
1236084776 kr.jpg методические рекомендации  
1236084776 kr.jpg программы
1236084776 kr.jpg обсуждения


Интегрированные уроки


Если у вас есть исправления или предложения к данному уроку, напишите нам.

Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - Образовательный форум.