Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
Контрольные вопросы к разделу 1 1. В каких реальных ситуациях можно применять модели принятия решений, разработанные для условий полной определенности? 2. Дайте определения целевой функции, переменным решения, параметрам модели и ограничениям. 3. Что является целевой функцией в четвертом рассмотренном в тексте примере ("Составление расписания работ")? 4. Что является переменными решения в третьем и четвертом примерах ("Выбор инвестиционных проектов" и "Составление расписания работ")? 5. Опишите, каким ограничениям должны удовлетворять переменные решения в третьем примере ("Выбор инвестиционных проектов"). 6. Объясните разницу между оптимальным допустимым решениями. 7. Является ли нулевой план производства (х 1 =х 2 =...=х n = 0) допустимым решением в первом примере ("Оптимальный производственный план")? 8. Нередко на практике не удается найти (или реализовать) оптимальное решение. Тогда стремятся найти и реализовать "хорошее" допустимое решение. По какому признаку одно допустимое решение "лучше" или "хуже" другого? 9. Пусть в третьем примере ("Выбор инвестиционных проектов") управляющий банка требует найти такой портфель, при котором и прибыль и надежность были бы максимальными. Возможно ли это? Объясните, используя понятия целевой функции, переменных решения и ограничений. 10. Нередко при практическом принятии решений люди имеют в виду несколько целей: максимизировать прибыль, минимизировать затраты труда и материалов, выполнить проект в кратчайшие сроки и т.п. • Объясните (используя понятия целевой функции и переменных решения), почему нельзя выбрать несколько целевых функций истремиться добиться максимума или минимума каждой из них одновременно? • Что делать в ситуации, когда несколько целей являются сравнимыми по важности? Как правильно сформулировать задачу? Достаточно ли при этом одной задачи? Можно ли вообще в такой? ситуации надеяться получить единственное решение? 11. Приведите 2-3 ваших собственных примера управленческих ситуаций "полной определенности" и объясните, что в этих ситуациях требуется "решить". Идентифицируйте понятия целевой функции, переменных решения, параметров модели и ограничений для ваших примеров. 2 МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В этом разделе рассматриваются два простых примера нахождения оптимального плана выпуска продукции, который обеспечивает максимальную прибыль при заданных ограничениях на ресурсы. Изучив материал раздела и реализовав описанные процедуры решения приведенных примеров на компьютере, вы • получите представление о том, как формулируются модели линейного программирования (ЛП) и вообще модели оптимизации при заданных ограничениях и что значит сам термин "линейное программирование"; • поймете, как конкретно записать целевую функцию и ограничения в ЛП-задаче; • научитесь организовывать данные на листе MS-Excel для решения ЛП-задач с помощью надстройки MS-Excel "Поиск решения". Если у вас хватит времени и терпения рассмотреть примеры для самостоятельного анализа, вы • расширите ваши представления о ситуациях, в которых применяются ЛП-модели; • закрепите навык решения ЛП-задач с помощью MS-Excel. Полученные знания и умение использовать "Поиск решения" наверняка пригодятся на практике, так как вы можете встретиться с проблемами линейной оптимизации, работая на производстве и в сфере услуг, в торговой, дистрибьюторной или транспортной фирме, в банке или инвестиционной компании. Область исследования операций, которая занимается оптимизацией, т.е. нахождением максимума (или минимума) целевой функции при заданных ограничениях, называется математическим программированием. С точки зрения современного русского языка этот термин не вполне удачен, поскольку сейчас под программированием однозначно понимается написание программ для компьютеров (людей, профессионально занимающихся этой работой, называют программистами). В английском языке значение слова programming определено не столь жестко и может означать планирование, выбор программы (плана) действий. Именно в этом контексте следует понимать и термин математическое программирование. Некоторым оправданием этому термину в русском переводе может служить то обстоятельство, что всякая реализация методов математического программирования в практике управления невозможна без использования компьютерных программ. Поэтому все эти методы являются фактически компьютерными алгоритмами В зависимости от вида целевой функции различают линейное и нелинейное программирование. Линейное программирование имеет дело с оптимизацией моделей, в которых целевая функция линейно зависит от переменных решения и ограничения представляют собой линейные уравнения или неравенства относительно переменных решения. Фактически это означает, что целевая функция и ограничения могут представлять собой только суммы произведений постоянных коэффициентов на переменные решения в первой степени, т.е. выражения типа Если целевая функция и ограничения содержат нелинейные выражения типа то они относятся к моделям нелинейного программирования. Почему модели линейного программирования столь важны? В настоящем курсе рассматриваются модели только линейного программирования. Это связано с тем, что • очень много важных для практики проблем, относящихся к самым разным сферам деятельности, могут быть проанализированы с помощью моделей линейного программирования; • существуют эффективные и универсальные алгоритмы решения задач линейного программирования, реализованные в общедоступном программном обеспечении; • методы анализа моделей линейного программирования не просто позволяют получить оптимальное решение, но и дают информацию о том, как может изменяться это решение при изменении параметров модели. Именно эта информация, позволяющая получить ответы на вопросы типа "что, если...", представляет особую ценность для лица, принимающего решение. 2.1. Оптимальный план выпуска продукции мебельного цеха ( Product Mix) Цех может выпускать два вида продукции: шкафы и тумбы для телевизора. На каждый шкаф расходуется 3,5 м стандартных ДСП, 1 м лицевого стекла и 1 человеко-день трудозатрат. На тумбу -1м ДСП, 2 м стекла и 1 человеко-день трудозатрат. Прибыль от продажи 1 шкафа составляет 200 у. е., а 1 тумбы -100 у е. Материальные и трудовые ресурсы ограниченны: в цехе работают 150 рабочих, в день нельзя израсходовать больше 350 м ДСП и более 240 м стекла. Какое количество шкафов и тумб должен выпускать цех, чтобы сделать прибыль максимальной? Формализация примера и основные соотношения Прежде всего сведем данные - параметры, характеризующие работу цеха, - в следующую таблицу (табл. 1). Таблица 1 Параметры задачи Ресурсы Запасы Продукты Шкаф Тумба ДСП 350 3,5 1 Стекло 240 1 2 Труд 150 1 1 Прибыль 200 100 В колонке "Запасы" запишем предельный расход ресурсов (ДСП, стекла и количества человеко-дней), которые ежедневно может позволить себе начальник цеха. В колонках "Шкаф" и ―Тумба" (продукты, которые может выпускать цех) запишем расход имеющихся ресурсов на единицу продукции (т.е. сколько требуется ДСП, стекла и труда на один шкаф и на одну тумбу). Наконец, на пересечении колонок "Шкаф" и "Тумба" и строки "Прибыль" запишем величины прибыли от продажи одного шкафа и одной тумбы. Определим теперь все элементы математической модели данной ситуации (табл. 2): - переменные решения, - целевую функцию и - ограничения. В данном случае очевидно, что переменные решения (иначе - неизвестные), которые может задавать начальник цеха и от которых зависит целевая функция (прибыль) цеха, - это количество шкафов и тумб, выпускаемых цехом ежедневно. Обозначим эти переменные соответственно X 1 иХ 2 . Таблица 2 Элементы модели Переменные решения Целевая функция X 1 – количество шкафов X 2 – количество тумб, производимых ежедневно P=200* X 1 +100* X 2 Ежедневная прибыль цеха Ограничения 3,5* X 1 +1* X 2 ≤350 1* X 1 +2* X 2 ≤240 1* X 1 +1* X 2 ≤150 X 1 ,X 2 ≥0 Нетрудно также понять, как в данном случае записывается выражение для целевой функции. Прибыль от продажи одного шкафа равна 200 у. е., значит, прибыль от продажи Х 1 шкафов будет 200*Х 1 . Аналогично прибыль от продажиХ 2 тумб равна 100*Х 2 , что и отражено в соответствующей графе таблицы. Глядя на выражение для целевой функции (типичное для моделей линейного программирования), можно легко увидеть, что, чем больше будут значения переменных Х 1 и Х 2 , тем больше будет и прибыль Р. Если бы было возможно беспредельно увеличивать ежедневный выпуск шкафов и тумб, прибыль росла бы беспредельно. Ясно, однако, что это невозможно, поскольку доступные ежедневно ресурсы цеха ограниченны. Это приводит к ограничениям на значения переменных Х 1 и Х 2 . Займемся теперь этими ограничениями. Проще начать с ограничения, которое вытекает из ограниченности трудовых ресурсов. Поскольку каждый рабочий за 1 день может сделать либо 1 шкаф, либо 1 тумбу, ясно, что общее количество выпущенных изделий (шкафов и тумб) не должно превышать числа рабочих в цехе. Иначе можно сказать, что поскольку расход трудового ресурса равен 1 человеко-дню на 1 шкаф и 1 человеко-дню на 1 тумбу, то общий расход труда на Х 1 шкафов и Х 2 тумб будет, очевидно, что не должно превышать ежедневного "запаса труда" в цехе, т.е. 150 человеко-дней. Это отражено последним неравенством, написанным в таблице элементов модели. Аналогично записывается неравенство, отражающее ограниченность ежедневных запасов ДСП. Поскольку на 1 шкаф расходуется 3,5 м ДСП, а на 1 тумбу - 1 м, то суммарный расход ДСП на Х 1 шкафов и Х 2 тумб будет, очевидно, 3,5*Х 1 + 1* Х 2 , что не должно превышать ежедневного запаса ДСП в цехе, т.е. 350 м ДСП. Это отражено первым неравенством, записанным в табл. 2. Точно так же получается и второе неравенство, отражающее ограниченность ежедневных запасов стекла. Определение переменных решения, целевой функции и ограничений - это почти все, что должен сделать менеджер, чтобы воспользоваться результатами оптимизации и анализа линейной модели. Далее необходимо только правильно организовать данные для компьютера, а все остальное сделает компьютерный алгоритм оптимизации. Решение задачи об оптимальном плане выпуска продукции с помощью Excel 1. Организуйте данные на листе MS-Excel так, как это показано на рис. 1. a) В ячейку В16 введена целевая функция Р = 200* Х 1 + 100 * Х 2 , представляющая собой прибыль от продажи Х 1 шкафов и Х 2 тумб. b) В ячейки F12, F13, F14 - формулы, отражающие расход ресурсов при изготовлении Х 1 шкафов и Х 2 тумб: ДСП 3,5* X 1 +1* X 2 Стекло 1* X 1 +2* X 2 Труд 1* X 1 +1* X 2 Рис. 1. Организация данных на листе MS-Excel для примера "Оптимальный план выпуска продукции мебельного цеха" 2. Выберите пункт меню "Сервис" "Поиск решения" (Tools Solver). Появится окно, озаглавленное "Поиск решения" (Solver) - рис. 2. а) В поле окна "Установить целевую ячейку" (Set target Cell) отметьте ячейку В16 (щелкните сначала по полю окна, а затем по шейке В16); b) Установите переключатель на отметке "Равной максимальному значению" (Equal to Max); c) В поле окна "Изменяя ячейки" (By changing Cells) отметьте ячейки В12:С12 (аналогично пункту а). Добавьте ограничения, щелкая по кнопке "Добавить" (Add). В появившемся окне, озаглавленном "Добавление ограничения" (рис. 3), щелкните по полю "Ссылка на ячейку", а затем отметьте ячейки В12:С12, выберите знак ограничения, щелкните по правому полю "Ограничение" (Constraints) и введите в него значение 0. Таким образом, вы ввели ограничение X 1 ,X 2 ≥0. Вновь щелкните по кнопке "Добавить". e) В появившемся окне "Добавление ограничения" щелкните в поле "Ссылка на ячейку", а затем отметьте ячейку F12, выберите знак ограничения (, щелкните по правому полю "Ограничение" (Constraints) и отметьте в нем ячейку В6, содержащую ограничение на ресурс "ДСП". Таким образом, вы ввели ограничение 3,5* X 1 +1* X 2 ≤350; f) Продолжайте процесс, пока не введете остальные два ограничения. 3. Щелкните по кнопке "Параметры" (Options). Появится окно "Параметры поиска решения" (рис. 4), в котором можно (но не нужно) менять многочисленные параметры оптимизации. Вас интересует только, установлен ли флажок "Линейная модель" (Assume linear model). Если нет, установите его, щелкните по кнопке Ok и вернитесь к окну "Поиск решения". Установка параметров оптимизации в окне "Поиск решения" должна выглядеть так, как показано на рис. 5. 4. Щелкните по кнопке "Выполнить" (Solve). Оптимизационная программа MS-Excel выполнит поиск решения, после чего появится окно "Результаты поиска решения" (рис. 6). Прочтите сообщение программы в этом окне. Если вы все сделали правильно, программа сообщит: "Решение найдено. Все ограничения и условия оптимальности выполнены". Вид листа MS-Excel, соответствующий оптимальному решению, показан на рис. 7. Оптимальный план производства мебельного цеха Параметры Ресурсы Запасы Продукты М Ж ДСП 350 3,5 Стекло 240 1 2 Труд 150 1 1 Прибыль 200 100 X1 X2 Расход Переменные 80 70 ДСП 350 Стекло 220 Труд 150 Целевая функция Р= 23000 5. В этом случае убедитесь, что переключатель в окне "Результаты поиска решения" находится в положении "Сохранить найденное решение", щелкните по кнопке Ok и прочтите ответ в ячейках В12:С12. В ячейках F12:F14 содержатся значения ресурсов, которые необходимы для полученного оптимального плана. В случае, если вы неверно задали знак ограничений, ввели неверные формулы для целевой функции или для ограничений и оптимизационная программа не может найти решения, в окне появятся сообщения: "Значения целевой ячейки не сходятся" или: "Поиск не может найти решения", или: "Условия линейной модели не выполняются". В этом случае следует переставить переключатель в окне "Результаты поиска решения" в положение "Восстановить исходные данные", щелкнуть по кнопке Ok и проверить организацию данных на листе Excel и в установках окна "Поиск решения". Рассмотрим теперь более сложный пример, включающий большее количество переменных решения. Этот пример позволит продемонстрировать дополнительные технические приемы, полезные при исследовании средних по размеру моделей линейного программирования с помощью MS-Excel. 2.2. Мини-кейс "На кондитерской фабрике". Акт 1 (Борьба научного подхода и эмпирики) Маленькая кондитерская фабрика должна закрыться на реконструкцию. Необходимо реализовать оставшиеся запасы сырья для производства продуктов из ассортимента фабрики, получив максимальную прибыль. Запасы и расход каждого вида сырья для производства единицы продукции каждого вида, а также получаемая при этом прибыль представлены в табл. 3. Мастер, используя свой 20-летний опыт, предлагает на глазок выпустить по 200 пакетов каждого продукта, утверждая, что ресурсов "должно хватить", а прибыль получится, очевидно, 1080 у.е. Сын владельца фабрики, только что закончивший обучение по программе "Бакалавр делового администрирования", утверждает, что такие проблемы надо решать не на глазок, а с помощью линейного программирования. Умиленный отец обещает сыну всю прибыль сверх 1080 у.е., если он предложит лучший план, чем многоопытный мастер. Формализация мини - кейса и основные соотношения Таблица 3 Параметры задачи Сырье Запасы Продукты Ореховый звон Райский вкус Батончик Белка Ромашка Темный шоколад 14110 0,8 0,5 1 2 1,1 Светлый шоколад 149 0,2 0,1 0,1 0,1 0,2 Сахар 815,5 0,3 0,4 0,6 1,3 0,05 Карамель 466 0,2 0,3 0,3 0,7 0,5 Орехи 1080 0,7 0,1 0,9 1,5 0 Прибыль/пакет, у.е. 1 0,7 1,1 2 0,6 Прежде всего заметим, что, как и в предыдущем примере, легко понять, какие величины являются переменными решения: это количества пакетов каждого из 5 продуктов, выпускаемых фабрикой. Обозначим их как: Переменные X 1 X 2 X 3 X 4 X 5 Решения Далее запишем целевую функцию - прибыль от производства чинного количества пакетов каждого продукта. Очевидно, ее можно описать как сумму произведений количества произведенных пакетов каждого продукта на прибыль от производства 1 пакета: с 1 с 2 с 3 с 4 С 5 Прибыль/пакет, у.е. 1 0,7 1,1 2 0,6 т.е. P=c 1 X 1 + c 2 X 2 + c 3 X 3 + c 4 X 4 + c 5 X 5 (Используя принятое в математике обозначение для суммы нескольких слагаемых, это выражение для целевой функции можно написать в виде где j - номер типа продукта в ассортименте фабрики. Эта запись показывает, что нужно просуммировать произведения c j X j для всех видов продуктов (j - от 1 до 5). Как уже упоминалось, такие суммы произведений коэффициентов и переменных решений в выражениях для целевых функций и для левых частей ограничений типичны для моделей линейного программирования. В MS-Excel имеется специальная математическая функция СУММПРОИЗВ, позволяющая быстро вычислять такие суммы произведений. При вызове этой функции с помощью мастера функций последний просит указать две одинаковые строчки или два одинаковых столбика чисел (массивы), элементы которых нужно параллельно перемножить и эти произведения сложить. Перейдем теперь к описанию ограничений на переменные решения. Происхождение этих ограничений связано с тем, что расход каждого из сырьевых ресурсов на производство заданного количества пакетов каждого из производимых продуктов не должен превышать запаса данного ресурса. Расход каждого вида сырья на производство одного пакета каждого продукта можно найти на пересечении строки (сырье) и столбца (продукт) в таблице параметров. Это так называемые технологические коэффициенты производства. Понятно, что их надо обозначать двумя индексами, как проиллюстрировано на следующем фрагменте таблицы параметров: |