Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
Ореховый звон Райский вкус Батончик Белка Ромашка Темный шоколад 0,8 0,5 1 2 1,1 a 11 a 12 a 13 a 14 a 15 Используя введенные обозначения, расход темного шоколада на Х 1 ,Х 2 , ... Х 5 пакетов каждого из продуктов, запишем в виде Аналогично для расхода светлого шоколада: И т. д. Количество пакетов каждого из продуктов должно быть таково, чтобы этот расход был меньше запаса каждого из ресурсов b i , указанных в таблице параметров. Темный шоколад 1411 b 1 Светлый шоколад 149 b 2 Саха 815,5 b 3 Карамель 466 b 4 Орехи 1080 b 5 Описание элементов модели производственного плана кондитерской фабрики сведено в табл. 4. Решение мини - кейса "На кондитерской фабрике" с помощью Excel Организуйте данные на листе MS-Excel так, как это показано на рис. 8. В ячейку El5 введена целевая функция, представляющая собой сумму произведений прибылей от продажи одного пакета каждого продукта (строка 9) на произведенное количество каждого продукта (строка 13). В ячейках C13:G13 содержатся переменные. В ячейки В16:В20 введены формулы, отражающие расход ресурсов на единицу каждого продукта. Выберите пункт меню "Сервис" "Поиск решения" (Tools Solver). В окне "Поиск решения" (Solver) в поле окна "Установить целевую ячейку" (Set target Cell) отметьте ячейку El5 и установите переключатель в положение "Равной максимальному значению" (Equal to Max). В поле окна "Изменяя ячейки" (By changing Cells) отметьте ячейки C13:G13. Добавьте ограничения, щелкая по кнопке "Добавить" (Add). В появившемся окне щелкните по полю "Ссылка на ячейку", а затем отметьте ячейки C13:G13, выберите знак ограничения (, щелкните по правому полю "Ограничение" (Constraints) и введите в него значение 0. Таким образом, вы ввели ограничения Х i (0). Вновь щелкните по кнопке "Добавить". В появившемся окне щелкните по полю "Ссылка на ячейку", а затем отметьте все ячейки В 16:В20, содержащие формулы расходов ресурсов, выберите знак ограничения (, щелкните по правому полю "Ограничение" (Constraints) и отметьте в нем ячейки В4:В8, содержащие ограничения на ресурсы (запасы). Щелкните по кнопке "Параметры" (Options). Проверьте, установлен ли флажок "Линейная модель". Если нет, установите его, щелкните по кнопке Ok и вернитесь к окну "Поиск решения". Установка параметров поиска оптимального решения для этой задачи показана на рис. 9. Щелкните по кнопке "Выполнить" (Solve) и прочтите ответ в ячейках C13:G13 (рис. 10). В ячейках В16:В20 содержатся значения расходов ресурсов, которые необходимы для полученного оптимального плана. Поскольку количества произведенных пакетов, конечно, должны быть целыми числами, округлите значения полученных переменных до целых так, чтобы ограничения на ресурсы были строго соблюдены. Предубеждение о целочисленном ограничении В окне "Добавление ограничения" существует возможность потребовать целочисленности переменных решения. Для этого достаточно в левом поле этого окна указать ячейки, содержащие переменные решения, а из предлагаемых ограничений выбрать ограничение "цел* ("int"). В некоторых случаях условие целочисленности переменных имеет принципиальное значение и позволяет исследовать новый класс моделей. В разделе "Использование целочисленных переменных в задачах линейного программирования" мы рассмотрим такие типы моделей. Однако следует иметь в виду, что добавление этот ограничения исключает использование эффективных методов решения задач линейного программирования (которые будут упомянуты в следующих разделах). Задача с целочисленными переменными гораздо более сложна для исследования, а алгоритмы ее решения гораздо менее универсальны и эффективны. Таким образам, если вы хотите использовать наиболее эффективные алгоритмы решения задачи линейного программирования, не задавайте без нужды условие целочисленности. Это особенно важно, когда вы исследуете большую модель (несколько десятков и сотен переменных и ограничений). Впрочем для простых примеров, рассмотренных в данной главе, использование условия целочисленности переменных не приведет ни к каким осложнениям. Так что можете попробовать. Заключение к разделу 2 Линейное программирование имеет дело с оптимизацией моделей, в которых целевая функция линейно зависит от переменных решения и ограничения представляют собой линейные неравенства или уравнения относительно переменных решения. Требование линейности означает, что и целевая функция, и ограничения могут представлять собой только суммы произведений постоянных коэффициентов на переменные решения. Переменные решения в ЛП-задачах могут принимать непрерывный ряд значений, допускаемых ограничениями. Они не обязаны быть целыми. Если практическая ситуация не допускает нецелых решений, полученные значения переменных решений нужно округлить, но так, что бы не нарушить ограничения. При организации данных ЛП-задачи на листе MS-Excel следует отвести отдельные ячейки для параметров, переменных, целевой функции и левых частей ограничений (если в правых частях ограничений находятся только параметры). Ячейки для переменных можно оставить пустыми или ввести в них любые допустимые значения переменных, а в ячейки для целевой функции и ограничений ввести формулы, отражающие их функциональную зависимость от переменных и параметров, используя правила, принятые в MS-Excel. При вводе этих формул очень полезной оказываются специальная функция MS-Excel. Указав в окне "Поиск решения" целевую ячейку и ячейки, в которых содержатся изменяемые значения переменных, а также введя ссылки к ячейки, содержащие левые и правые части ограничений, и выбрав знак <, > или =, стоящий между этими частями, можно заставить "Поиск решения" найти оптимальные значения переменных, обеспечивающие максимум (или минимум) целевой функции при заданных ограничениях. Контрольные вопросы к разделу 2 1. В чем состоит предмет линейного программирования? Как здесь следует понимать термин ―программирование‖? 2. Какой общий вид должны иметь целевая функция и ограничения, чтобы для анализа модели можно было применить методы линейного программирования? 3. Цех выпускает 3 вида продукции P 1 , P 2 , P 3 . При определении оптимального плана выпуска продукции X 1 , X 2 , X 3 (количества единиц продукции, которые цех должен выпускать ежемесячно) требуется, чтобы количество продукции первого типа X 1 составляло не менее половины общего количества единиц продукции, выпущенной цехом. Менеджер записал это условие в виде Является ли это ограничение линейным? Как записать требуемое ограничение, чтобы методы линейного программирования были применимы? 4. При разработке производственного плана, минимизирующего суммарные издержки выпуска продукции на данной производственной линии, менеджер производственного отдела собирается использовать данные бухгалтерии об издержках на производство единицы каждого вида продукции, которую выпускает линия c i . Бухгалтер сообщил, что при расчетах ―удельных‖ издержек для каждого вида продукции в прошлом месяце суммировались издержки труда, материалов, электроэнергии, реально затраченные на производство данного вида продукции, а также прибавлялась часть постоянных издержек (затраты на переналадку линии для выпуска данного вида продукции, аренда помещений, оплата труда центрального управленческого аппарата), пропорциональная времени, в течение которого линия выпускала данную продукцию. Можно ли использовать эти данные для записи целевой функции? Можно ли вообще считать величины c i параметрами? 5. Менеджер ищет максимум целевой функции прибыли используя надстройку MS-Excel ―‖Поиск решения‖. При этом все записанные им неравенства ограничивают переменные снизу (т.е. сводятся к виду ). Получит ли менеджер оптимальное решение? Какое сообщение выдаст ―Поиск решения‖? 6. При поиске оптимального решения для переменных X 1 и X 2 введены следующие ограничения: Как вы думаете, найдет ли ―Поиск решения‖ максимум целевой функции P=10X 1 +12X 2 ? Какое сообщение выдаст ―Поиск решения‖? 7. При решении задачи об оптимальном плане производства на неделю ―Поиск решения‖ выдал, что следует производить эти 112,5 стула; 15,75 стола и 3,5 шкафа. Можете ли вы разумно трактовать эти данные (не округляя до целых)? Можно ли считать это решение удовлетворительным или следует повторить расчет и ввести целочисленные ограничения на переменные? Рассмотрим две альтернативы: • цех собирается работать по этому плану целый год; • это план на последнюю неделю перед остановкой цеха на реконструкцию. 8. Приведите 2-3 практических примера, в которых требуется найти максимум или минимум некоторой целевой функции. Подумайте, от каких переменных зависят эти целевые функции, и попробуйте записать их математический вид? Являются ли ваши целевые функции линейными? Примеры для самостоятельного анализа к разделу 2 1) Оптимальная загрузка оборудования ткацкого цеха Ткацкий цех выпускает два вида тканей T 1 и T 2 на двух видах станков C 1 и C 2 . Количество станков первого типа – 103, второго – 210. Станок C 1 выпускает 54 м ткани T 1 или 72 м ткани T 2 , а станок C 2 – 34 м ткани T 1 или 65 м ткани T 2 за смену. Производство тканей ограничено ресурсами и складскими помещениями. За смену можно выпустить не более 6000 м ткани T 1 и не более 11000 м ткани T 2 Доход от продажи ткани T 1 – 7,3 у.е. за 1 м, продажи ткани T 2 , - 4,2 у.е. за 1 м. Как распределить производство тканей T 1 и T 2 между станками C 1 и C 2 , чтобы максимизировать прибыль? Указания 1. Заполнить таблицу параметров. Параметры задачи Тип станка Количество Производительность T 1 T 2 C 1 C 2 Ограничения на производство Прибыль от продажи 1 м тканей 2. Подумайте над наиболее важным вопросом о переменных решения. Что значит ―как распределить производство тканей между станками‖? 3. Запишите выражения для ограничений на производство тканей. 4. Используйте фрагмент этих выражений для записи целевой функции. 5. Заполните таблицу элементов модели. 6. Организуйте данные на MS-Excel и используйте ―Поиск решения‖. Элементы модели Переменные решения Целевая функция Ограничения 7. Обратите внимание, что для производства максимально дозволенного количества тканей каждого типа необязательно нужны все имеющиеся станки. 2) Оптимальный план размещения производственных заказов Фирма планируется производить 300 тыс. однотипных изделий на четырех своих предприятиях ежемесячно. Для освоения этого нового вида продукции выделено 18000 тыс. руб. Разработанные для каждого филиала проекты освоения новой продукции характеризуются определенными значениями себестоимости одного изделия и необходимыми удельными капиталовложениями. Предприятие 1 2 3 4 Всего, тыс. Переменные решения X 1 X 2 X 3 X 4 300 Издержки на ед. продукции 83 89 95 98 Инвестиции на ед. продукции 120 80 0 40 18000 Издержки производства и капиталовложения можно считать пропорциональными количеству выпасаемой продукций. Определить такой план размещения ежемесячных объемов производства по предприятиям, при котором суммарные издержки производства будут минимальными. Указание Заполните таблицу элементов модели. Имейте в виду, что 18 000 тыс. руб. - это сумма, выделенная только на капиталовложения, но не на покрытие ежемесячных издержек производства. Последние будут покрываться за счет дополнительных средств (сначала - краткосрочные кредиты, затем - отчисления от продаж). Считается, что для обеспечения заданного объема производства нужно вложить тем больше средств, чем больше будет его мощность (количество производимых изделий в месяц). Элементы модели Переменные решения Целевая функция Ограничения 3) Минимизация отходов лесопилки Пилорама заготавливает, оцилиндровывает и сушит 20-футовые бревна, которые в дальнейшем используются для строительства бревенчатых домов, бань и т.п. Поступил новый заказ, для которого требуется 275 шт. 8-футовых, 100 шт. 10- футовых и 250 шт. 12-футовых бревен. На складе 315 шт. 20-футовых бревен. Распилить бревна так, чтобы выполнить заказ и минимизировать длину нестандартных обрезков. Указание Главный вопрос здесь - выбор переменных решения. Запишите все возможные способы распила 20-футовых бревен на стандартные куски и соответствующие этим способам величины обрезков. Считайте, что число стандартных кусков не менее заказа (но может быть и больше, т.е. часть кусков заготовлена впрок). 3 АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ ЛП - ЗАДАЧ В этом разделе рассматривается важнейшая с точки зрения практики проблема анализа оптимального решения ЛП- задачи с целью принятия адекватного управленческого решения. Хотя и сам по себе оптимальный план чрезвычайно полезен, часто бывает гораздо интереснее знать, как можно изменить те или иные параметры системы (считавшиеся неизменными в ходе решения ЛП-задачи), чтобы улучшить решение, получить еще большую прибыль, уменьшить издержки или усовершенствовать стратегию управления организацией. Изучив материал раздела и реализуя описанные процедуры решения и анализа приведенных примеров на компьютере, вы • познакомитесь с графическим методом решения простых ЛП-задач и получите наглядное представление о том, где именно в области допустимых планов находится оптимальное решение ЛП-задачи; • поймете, как оптимальный план может меняться при изменении параметров - целевых коэффициентов (цен и издержек) и правых частей ограничений (запасов ресурсов), а также почему в Л П-задачах всегда существует некоторый интервал устойчивости, в котором решение не меняется при изменении параметров; • узнаете о "теневых ценах" ресурсов и научитесь применять их для прогноза изменения прибыли при изменении запасов доступных ресурсов; • научитесь использовать отчет по устойчивости MS-Excel для анализа, модификации ЛП-модели и для принятия адекватных решений по совершенствованию управления реальной системой. Примеры для самостоятельного анализа помогут вам • понять, как разнообразны области применимости ЛП-моделей в бизнесе; • развить и закрепить навык использования надстройки "Поиск решения" и выдаваемого ею отчета по устойчивости для анализа ЛП-моделей, их модификации и поиска альтернативных путей оптимального управления системой. Модели оптимизации прибыли или издержек большого предприятия могут содержать очень много переменных. Поэтому попытки наугад или с помощью простого перебора вариантов изменить те или иные параметры, чтобы улучшить функционирование управляемой системы, обречены на неудачу. В этой ситуации только использование концепции теневых цен и интервалов устойчивости, выдаваемых в отчете об устойчивости оптимального решения, позволяет нащупать наиболее эффективные рычаги управления. Получение оптимального решения оптимизационной задачи вообще и задачи линейного программирования в частности - это не конец, а фактически только начало работы менеджера с количественной моделью. При формулировке модели, как уже отмечалось, величины, количественно характеризующие ту или иную систему или управленческую ситуацию, разбиваются на две группы. Первая группа - это величины, которые субъект, принимающий решение, должен менять в ходе поиска оптимума целевой функции. Они были названы переменными решения. Нахождение оптимальных значений для переменных решения (для "неизвестных") и составляет содержание процесса "принятия решения" в данном случае. Переменные второй группы величин в ходе поиска оптимума целевой функции должны считаться постоянными. Они были названы параметрами. Ясно, что значения параметров определяют оптимальные значения переменных и целевой функции. Некоторые параметры действительно трудно поддаются изменению. Например, параметры, характеризующие технологический процесс (в первом примере, разобранном в предыдущем разделе, это величины расхода ДСП, стекла и рабочего времени на один шкаф и одну тумбу), вряд ли могут быть изменены менеджером. Этот вопрос должен решаться специалистом-технологом. Однако изменение доступных для производства ресурсов (в упомянутом примере - запасы ДСП, стекла и рабочей силы на день) находится, разумеется, в компетенции менеджера производственного отдела. Вопрос об отпускных ценах на продукцию цеха (а следовательно, об изменении прибыли от продажи единицы продукции каждого типа) - это также управленческий вопрос. Таким образом, многие параметры модели могут (и должны) изменяться менеджером с целью поиска путей улучшения работы системы. Поскольку изменение параметров модели часто связано с привлечением дополнительных финансовых ресурсов, необходимо ответить на ряд вопросов: - какой ресурс наиболее сильно влияет на изменение прибыли (издержек)? - как изменится решение и целевая функция при изменении количества того или иного ресурса? - если какой-либо продукт не входит в оптимальный план (как в примере с кондитерской фабрикой), а по каким-то неформализуемым причинам желательно, чтобы он в него входил, то какой параметр и в каком направлении следует изменить? и т.д. Поиск ответов на подобные вопросы и составляет существо анализа решения. Таким образом, анализ решения должен дать менеджеру ясное представление о том, как будет изменяться решение при том или другом изменении параметров. Когда речь идет о задаче линейного программирования, существенная информация о влиянии изменения параметров на оптимальное решение накапливается программой, собственно, в ходе поиска решения. MS-Excel представляет эту информацию в виде отчета об устойчивости. Ответ на многие вопросы может быть получен на основе анализа этого отчета. Другие вопросы могут потребовать проведения дополнительных расчетов типа "что, если...". Для того чтобы сформировать интуитивное представление о том, как может меняться решение задачи линейного программирования при изменении параметров, полезно получить и проанализировать графическое решение нашего первого "игрушечного" примера об оптимальном плане мебельного цеха, а также познакомиться с понятием двойственности задач линейного программирования. |