Гипермаркет знаний>>Информатика>>Информатика 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.

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

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

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

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

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

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

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

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

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

     х + 4у = 1000;

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

     у - 0  (ось ОХ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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