Чернов В.П. Операционный и производственный менеджмент

Подождите немного. Документ загружается.

173

Обратимся к нашему примеру. Цена Печенья составляет 32 руб.

за кг. Предположим, что отпускная цена изменилась, и теперь

Печенье

продается по другой цене. Следует ожидать, что при этом изменится вы-

ручка от продаж. Однако изменится ли оптимальный план?

Небольшое изменение этой цены приведет к незначительному по-

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

уровня целевой функции). В результате оптимальный план останется в

прежней точке (рис. 5.5). При более значительном изменении цены он пе-

рейдет в другую вершину области допустимых планов.

Рассмотрим этот вопрос подробнее. Предположим, что цена

Пече-

нья

увеличивается. Это соответствует повороту градиента по часовой

стрелке, вместе с ним поворачивается и перпендикулярная ему линия

уровня (пунктирная линия на рис. 5.5). При небольшом повороте опти-

мальный план остается в первоначальной точке L. При достаточно боль-

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

пересечении границ по

Муке и Маслу (линий A

и B

Критическая величина цены, при которой происходит переход оп-

тимального плана из одной точки в другую, соответствует положению,

когда линия уровня целевой функции параллельна прямой А

(а гради-

ент, соответственно, перпендикулярен этой прямой). Условием парал-

лельности прямых является пропорциональность коэффициентов при пе-

ременных в двух уравнениях: линии уровня целевой функции и границы

по

Муке. Составим пропорцию с неизвестной ценой c

первого продукта

(

Печенья).

c27

0,5 0,3

= .

Отсюда получаем c

= 45. Таким образом, при увеличении цены

Печенья с первоначальных 32 до 45 руб. за кг (и при сохранении цены Би-

сквитов

) оптимальный план остается неизменным, по-прежнему следует

производить 1250 кг

Печенья и 666,667 кг Бисквитов. Если же цена под-

нимется выше 45 руб., то оптимальным планом станет точка M, находя-

щаяся на пересечении границ по

Муке и Маслу (линий A

и B

). Ее

координаты можно определить решением системы уравнений:

0,5x 0,3x 825

0,3x 0,06x 480







174

откуда x

= 1575, x

= 125.

При цене

Печенья, в точности равной 45 руб., оптимальным являет-

ся как первоначальный план L, так и новый план M, а также и все точки,

лежащие на отрезке LM. В этом случае задача имеет бесконечно много

оптимальных планов. Разумеется, все эти разные планы производства

обеспечивают в точности одну и ту же величину выручки от продаж.

Так, план L соответствует выручке:

45×1250 + 27×666,667 = 74250 (руб.).

План M соответствует той же величине выручки:

45×1575 + 27×125 = 74250 (руб.).

Верхняя критическая граница цены Печенья равна 45. Отсюда

следует, что

допустимое увеличение первоначальной цены равно 13.

Аналогичным образом рассчитывается нижняя граница цены пер-

вого продукта. При уменьшении цены

Печенья градиент вместе с линиями

уровня будет поворачиваться против часовой стрелки. При достаточно

сильном повороте оптимальный план перейдет в точку K с координатами:

= 818,182, x

= 954,545.

Критическое положение определяется из условия параллельности ли-

нии уровня целевой функции и линии Сахара D

. Составим пропорцию:

c27

0, 2 0,3

= ,

решив которую получим c

= 18.

Мы получили нижнюю критическую границу цены Печенья, рав-

ную 18 руб.

Допустимое уменьшение первоначальной цены Печенья,

равной 32 руб., составляет 14 руб.

Таким образом, при произвольных изменениях цены

Печенья меж-

ду нижней и верхней критическими границами, то есть между 18 и 45

руб., оптимальный план остается прежним: по-прежнему следует произ-

водить 1250 кг

Печенья и 666,667 кг Бисквитов. При выходе цены за

верхнюю или нижнюю критические границы оптимальный план изменит-

ся, вместе с ним изменится и статус ресурсов.

Аналогичным образом вычисляются нижняя и верхняя границы по

второму продукту –

Бисквитам. Отметим, что изменение цены по разным

продуктам по-разному воздействует на направление поворота градиента.

175

При увеличении цены второго продукта градиент поворачивается против

часовой стрелки, а при уменьшении – по часовой стрелке.

Расчеты показывают, что верхняя критическая граница цены

Биск-

витов

равна 48 руб., так что допустимое увеличение составляет 21 руб.

При преодолении этой границы оптимальный план переходит из точки L в

точку K.

Нижняя критическая граница цены

Бисквитов равна 19,20 руб., до-

пустимое уменьшение составляет 7,80 руб. При переходе через эту грани-

цу оптимальный план переходит из точки L в точку M.

Критические границы цен соответствуют границам устойчивости

оптимального плана при изменении коэффициентов целевой функции.

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

СРЕДСТВАМИ EXCEL

Характеристика симплекс-метода

Мы познакомились выше с графическим методом решения задач

линейного программирования. Это простой, наглядный и удобный метод,

обладающий лишь одним недостатком: он пригоден только для задач с

двумя переменными. Уже для трех переменных графики пришлось бы

изображать в трехмерном пространстве, наглядность и простота были бы

в существенной мере потеряны. Для большего числа переменных этот ме-

тод и вовсе непригоден.

Обычно в экономико-математической модели присутствует боль-

шое число переменных. Номенклатура выпуска крупного предприятия на-

считывает сотни и тысячи наименований. Возникает потребность в уни-

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

ном для любого числа переменных и ограничений, для задач любой раз-

мерности. В настоящее время разработаны разнообразные методы реше-

ния произвольных задач линейного программирования. В основе боль-

шинства из них лежит так называемый симплекс-метод.

Симплекс-метод представляет собой алгоритм решения задачи, то

есть четко описанную процедуру последовательных эквивалентных пре-

образований исходной математической модели методом Гаусса. В резуль-

тате этих преобразований получают либо такую форму модели, из кото-

рой непосредственно извлекается оптимальный план (если он существу-

ет), либо такую форму, из которой непосредственно обнаруживается не-

разрешимость задачи (если оптимальный план не существует).

176

В последовательности преобразований модели выделяют этапы. Ре-

зультатом этапа является такая форма записи модели, с которой непосредст-

венно связан один из допустимых планов задачи – так называемый текущий

опорный план. Текущий опорный план геометрически представляет собой

одну из вершин многогранной области допустимых планов. Движению по

этапам симплекс-метода соответствует переход от одного текущего опорно-

го плана к другому, от одной вершины области к соседней. При каждом та-

ком переходе значение целевой функции улучшается (во всяком случае, не

ухудшается). Цепочка преобразований последовательно приближает нас к

оптимальному плану. Мы приходим либо к ситуации, когда текущим опор-

ным планом становится оптимальный план, оптимальная вершина области

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

признакам мы непосредственно убеждаемся в неразрешимости задачи.

Процедура Поиск решения

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

линейного программирования. Мы рассмотрим здесь одну из них, входя-

щую в электронные таблицы Excel. Эта процедура называется

Поиск реше-

ния

Рассмотрим применение данной процедуры в связи с нашим при-

мером составления плана по производству двух продуктов –

Печенья и

Бисквитов.

Для решения задачи сначала подготовим исходные данные.

На рис. 5.7 дан вариант представления данных на листе Excel.

Рис. 5.7. Вид исходных данных для процедуры

Поиск решения

177

В ячейку первой строки введено название задачи. В ячейки столбца

A введены наименования строк таблицы. В ячейки второй строки введены

названия столбцов таблицы.

В столбцах B и C (

Печенье и Бисквиты) содержатся необходимые

данные по этим двум продуктам. Ячейки B3 и С3 – это компоненты бу-

дущего оптимального плана (в математической модели это переменные

и x

). Пока они пустые. В столбцах приведены данные на единицу

продукции. В ячейках B4 и C4 содержатся отпускные цены продуктов.

Далее приведены данные по затратам ресурсов на единицу выпуска про-

дукции.

Единицы и нули (пустые ячейки) в диапазоне B12:C13 задают ко-

эффициенты в ограничениях по спросу.

В столбце E «Доступно» указаны доступные объемы ресурсов и

объем спроса. В столбце D «Необходимо» введены формулы, позволяю-

щие вычислить выручку и затраты ресурсов при реализации данного про-

изводственного плана, а также покрытый спрос. Формулы столбца D в

точности соответствуют выражениям в целевой функции и левых частях

ограничений математической модели.

Сначала затраты ресурсов и выручка автоматически оказываются

равными 0. Это соответствует отсутствию производства продукции.

В ячейках столбца F «Остаток» ведены формулы, вычисляющие

разность между доступным и необходимым объемом ресурса. В началь-

ной ситуации «Остаток» совпадает с «Доступно».

Такой таблицей можно пользоваться достаточно эффективно и без

процедуры

Поиск решения. Достаточно в ячейки Плана B3 и C3 ввести ка-

кие-нибудь данные, чтобы сразу получить результат расчета выручки, не-

обходимых затрат ресурсов и их остатков. Если остаток хотя бы по одно-

му из ресурсов получился отрицательным («Необходимо» оказалось

больше, чем «Доступно»), то план является недопустимым. Можно пере-

бирать различные варианты допустимых планов, пока мы ни получим

план с удовлетворительной величиной выручки. Здесь удобно воспользо-

ваться условным форматированием.

Процедура

Поиск решения позволяет автоматизировать такой пере-

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

полезно выделить ячейку D4.

Для вызова процедуры следует в меню войти в

Сервис и там клик-

нуть мышью

Поиск решения. Если в Сервисе отсутствует Поиск решения,

то необходимо войти в

Надстройки и там пометить Поиск решения. После

выхода из

Надстроек в меню Сервис появится Поиск решения.

Если же и в

Надстройках нет Поиска решения, то следует переуста-

новить Excel, пометив

Поиск решения при выборе компонентов установки.

178

При входе в Поиск решения на экране появляется диалоговое окно

(рис. 5.8).

Верхнее поле

Установить целевую первоначально является актив-

ным (если нет, его следует активизировать). В нем должен быть указан

адрес целевой ячейки (в нашей задаче это $D$4).

Мы хотим максимизировать выручку, поэтому переключатель

Рав-

ной

должен быть в положении максимальному значению. Если бы в дру-

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

целевой ячейки, то переключатель следовало бы установить в положение

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

Рис. 5.8. Диалоговое окно Поиск решения до ввода данных

Далее следует щелкнуть в поле

Изменяя ячейки (или свернуть окно)

и выделить мышью диапазон с ячейками $B$3:$C$3, содержащими ком-

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

разделенными (несмежными), то их следует вводить при нажатой клавише

Ctrl. В поле

Изменяя ячейки адреса несмежных ячеек должны быть разде-

лены точкой с запятой.

Для ввода данных в окно

Ограничения следует нажать кнопку До-

бавить

. На экране возникнет новое диалоговое окно Добавление ограни-

чения

, предназначенное для ввода ограничений (рис. 5.9).

179

Рис. 5.9. Диалоговое окно Добавление ограничения до ввода данных

В поле

Ссылка на ячейку можно вводить адреса отдельных ячеек

или же целого диапазона. В нашем случае выделим мышью диапазон

$D$5:$D$13.

В среднем поле выберем из списка вид ограничения. В нашем слу-

чае это <= (этот знак стоит по умолчанию). В других задачах, возможно,

потребуются другие виды ограничений. В частности, вид ограничения

«цел» означает, что содержимое ячеек в левом поле должно быть цело-

численным, а «двоич» означает, что допустимыми числовыми значениями

данных ячеек являются только 1 и 0 (Да и Нет).

В поле

Ограничение можно вводить адреса отдельных ячеек, целого

диапазона или же число. В нашем случае выделим мышью диапазон

$E$5:$E$13 (рис. 5.10). Это означает, что содержимое каждой ячейки диа-

пазона $D$5:$D$13 не превосходит содержимого соответствующей ячей-

ки диапазона $E$5:$E$13.

Рис. 5.10. Диалоговое окно Добавление ограничения после ввода данных

Далее можно нажать кнопку ОК. Если бы потребовались дополни-

тельные ограничения, то следовало бы нажать кнопку

Добавить и про-

должить ввод ограничений.

В появившемся диалоговом окне

Поиск решения можно увидеть ре-

зультаты проведенных действий (рис. 5.11).

180

Рис. 5.11. Диалоговое окно Поиск решения после ввода данных

Теперь следует нажать кнопку

Параметры и в новом окне

(рис. 5.12) поставить два флажка.

Рис. 5.12. Параметры поиска решения

Флажок

Неотрицательные значения соответствует неотрицатель-

ности компонентов плана, то есть объемов производства

Печенья и Биск-

витов

. Флажок Линейная модель (наша модель не содержит нелинейных

функций) ускорит процесс вычислений и позволит вывести

Отчеты для

более подробного постоптимизационного анализа.

Теперь можно нажать кнопку ОК и в вернувшемся окне (рис. 5.11)

нажать кнопку

Выполнить.

181

В окне Результаты поиска решения (рис. 5.13) можно прочесть

итоговое сообщение.

Рис. 5.13. Диалоговое окно Результаты поиска решения

Далее можно сразу нажать кнопку ОК и зафиксировать на листе

Excel результаты оптимизации или же дополнительно к этому вывести

Отчеты для постоптимизационного анализа. Для получения Отчетов не-

обходимо пометить мышью в поле

Тип отчета их требуемые типы.

Пометим в окне

Тип отчета все три типа: Результат, Устойчи-

вость

и Пределы, и после этого нажмем кнопку ОК.

На листе Excel, содержащем модель, появляются результаты рас-

четов (рис. 5.14). Часть результатов уже знакома нам по графическому

решению. Оптимальный план предписывает изготовить 1250 кг

Печенья

и 666,667 кг Бисквитов. Выручка при этом будет равна 58000 руб.

В столбце «Необходимо» появляется новая информация о затратах ре-

сурсов, необходимых для реализации плана. В столбце «Остатки» появ-

ляется дополнительная информация о неиспользованных объемах ре-

сурсов.

182

Рис. 5.14. Результаты расчета оптимального плана

Листы с Отчетами автоматически вставляются в книгу с соответст-

вующими ярлычками. Отчет по результатам (рис. 5.15) состоит из трех

блоков данных. Первые два, «Целевая ячейка (Максимум)» и «Изменяе-

мые ячейки», содержат данные по исходному и результирующему состоя-

нию этих ячеек. Третий блок, «Ограничения», содержит информацию по

ячейкам и формулам ограничений модели. Здесь же указывается статус

ограничения (связанное или не связанное) и разница, соответствующая в

нашей модели неиспользованному остатку ресурса.