Лекция № 25 МОДЕЛИ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

Лекция № 25 МОДЕЛИ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

ПЛАН

1.     Модели оптимального планирования.

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

        б)Математическое программирование.

         в) Линейное программирование.

1 Модели оптимального планирования

Проблема, к обсуждению которой мы теперь переходим, назы­вается оптимальным планированием.

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

Постановка задачи планирования вы­ глядит следующим образом:

• имеются некоторые плановые показатели: Х, У, и др.;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значит, суммарное время на изготовление х пирожков и у пирож­ ных равно

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

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

(х + 4y) t  ≤  8 · 60,

или

(х + 4y) t  ≤  480.

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

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

Отсюда

х + 4у ≤  1 000.

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

х + у  ≤  700.

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

                                            х + 4у ≤ 1000;                                (1)

х + у ≤ 700;

                                                   х ≥ 0;

                                                    у ≥ 0.

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

rx + 2 ry = r(x + 2у).

Целью производства является получение максимальной вы­ ручки. Будем рассматривать записанное выражение как функцию от х, у:

F(x, у) = r(x + 2у).

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

f(x, у) = х + 2у.                                                  2)

Следовательно, получение оптимального плана свелось к сле­ дующей математической задаче:

Требуется найти значения плановых показателей х и у, удовлетворяющих данной системе неравенств (1) и придающих максимальное значение целевой функции (2).

Итак, математическая модель задачи оптимального планиро­вания для школьного кондитерского цеха построена.

Теперь следующий вопрос: как решить эту задачу? Вы уже догадываетесь, что решать ее за нас будет компьютер с помощью табличного процессора Excel. А мы обсудим лишь подход к реше­нию, не вникая в подробности метода.

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

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

х + 4у = 1 000,

х + у = 700,

х = О (ось У),

у = О (ось Х).

На рис .3.10 эта область представляет собой четырехугольник ABCD и выделена заливкой. Любая точка четырехугольника яв­ляется решением системы неравенств (1). Например, х = 200, у= 100. Этой точке соответствует значение целевой функции f( (200, 1 00) = 400.

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

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

В математическом арсенале Excel имеется средство Поиск ре­шения. Как решать данную задачу с помощью этого средства, вы узнаете из компьютерного практикума.

В результате решения задачи получается следующий опти­мальный план дневного производства кондитерского цеха: нужно выпускать 600 пирожков и 100 пирожных. Эти плановые показа­тели соответствуют координатам точки В на рис.3. 10. В этой точ­ке значение целевой функции f(200, 1 00) = 400. (600, 1 00) = 800. Если один пиро­жок стоит 5 рублей, то полученная выручка составит 4000 руб­лей.

      Система основных понятий