Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
Решение двойственной задачи об оптимальном плане выпуска продукции мебельного цеха с помощью MS-Excel I. Организуйте данные так, как показано на рис. 15 "Двойственная задача к задаче об оптимальном плане выпуска продукции мебельного цеха". 1. Формула в ячейке В13 для целевой функции означает: С = 350Y 1 +240Y 2 +150Y 3 . 2. Формула в ячейке D11 - это выражение для левой части первого ограничения 3,5Y 1 +1Y 2 +1Y 3 . He забудьте сделать адреса ячеек, в которых содержатся переменные, абсолютными ($ перед буквенным обозначением столбца и номером ряда можно получить, нажав на функциональную клавишу F4 на клавиатуре компьютера). 3. Протяните формулу в ячейке D11 на ячейку Е11. II. Вызовите "Поиск решения": 1. Целевая ячейка: В13 -Мин. 2. Изменяя ячейки: F4:F7. 3. Ограничения: D11≥C7 (т.е. 3,5Y 1 +Y 2 +Y 3 ≥200) E11≥D7 (т.е. Y 1 +2Y 2 +Y 3 ≥200) F4:F7 (т.е. Y 1 , Y 2 , Y 3 ≥0) 4. He забудьте отметить в параметрах минимизации, что это линейная модель. III. Решение двойственной задачи представлено на рис. 16. Обратите внимание, что цена ресурса "стекло" Y 2 = 0. Подумайте почему. Анализ решения двойственной задачи Прежде всего обратим внимание на то, что значение минимальной выручки при продаже ресурсов C min в точности совпадает со значением максимальной прибыли при производстве Р mах . Э ТОТ результат следует из содержательной постановки нашей двойственной задачи. Действительно, если бы получилось, что эта выручка меньше, чем прибыль от производства, то это значило бы, что продавать ресурсы менее выгодно, чем производить из них продукцию. А если бы выручка от продажи ресурсов оказалась больше, чем прибыль от производства, то это значило бы, что теневые цены на ресурсы не минимальны. И то и другое противоречит условию задачи. В теории линейного программирования доказывается, что независимо от экономической интерпретации исходной и двойственной задач, а также от характера ограничений (< или >), если решение ЛП-задачи на максимум или на минимум существует, то оптимальное (максимальное или минимальное) значение целевой функции в исходной задаче должно быть в точности равно оптимальному (минимальному или максимальному) значению целевой функции двойственной задачи. Рассмотрим теперь результат решения двойственной задачи к задаче об оптимальном плане выпуска продукции мебельного цеха (рис. 16). Согласно этому решению, теневые цены на используемые ресурсы "ДСП", "стекло" и "труд" равны соответственно Y 1 =40; Y 2 =0; Y 3 =60. Бросается в глаза нулевая цена второго ресурса - "стекло". Что это значит? Разумеется, рыночная цена на товар не может равняться нулю. Разумеется, если производитель - продавец ресурсов и отдаст стекло по цене ниже рыночной, он никогда не отдаст это задаром. Однако, как уже отмечалось выше, при решении двойственной задачи мы получаем не рыночные, а особые, теневые цены, которые характеризуют ценность данного ресурса для данного производителя в конкретной производственной ситуации. С этой точки зрения нетрудно понять, что нулевое значение и теневой цены стекла обусловлено тем обстоятельством, что при минимальном плане выпуска продукции мебельного цеха ежедневные запасы стекла избыточны (см. рис. 7,12). Каждый день из 240 м стекла производитель использует только 220 м. Если предположить себе, что производитель ежедневно складирует эти излишки, то получается, что стекло ему просто некуда девать. Предложенную выше экономическую интерпретацию (продавец производственных ресурсов) было удобно использовать на старой формулировки двойственной задачи о мебельном цехе. Для практического использования теневых цен в решении задач оптимального управления необходимо связать ценность ресурсов (теневые цены) и прибыль от производства. Это нетрудно сделать. Допустим, что величины запасов одного из ресурсов b 1 = 350, b 2 = 240 и b 3 = 150 (например, ДСП) увеличились на малую величину Δb 1 =1. Коэффициенты b 1 , b 2 и b 3 – это целевые коэффициенты в двойственной задаче. Согласно анализу, который мы провели выше для исходной ЛП-задачи, при изменении целевых коэффициентов существует некоторый интервал устойчивости. Если значение изменяемого целевого коэффициента остается внутри этого интервала устойчивости, то оптимальное решение не изменяется. Допустим, что интервал устойчивости в нашей двойственной задаче достаточно большой, так что увеличение запасов всех ресурсов на единицу не приводит к изменению теневых цен Y 1 , Y 2 , Y 3 (которые для двойственной задачи как раз и представляют собой оптимальное решение). Мы проверим позже, что это так и есть для нашей задачи. Тогда очевидно, что минимальное значение выручки от продажи всех ресурсов увеличится (поскольку теперь продается не 350 м ДСП, а 351 м) и составит C' minc = C min + Δb 1 Y 1 , где C' minc - новое значение выручки, a C min - старое значение. Поскольку, согласно общему соотношению между прямой и двойственной ЛП-задачами, минимальное значение целевой функции в двойственной задаче (в нашем случае C min ) всегда равно максимальному значению целевой функции в исходной задаче (в нашем случае - прибыли от производства Р тах ), то это означает, что увеличение запаса ДСП на величину Δb 1 приведет к увеличению прибыли от производства Р mах Таким образом, можно записать, что если увеличить какой-либо i-й ресурс, используемый для производства продукции, на величину Δb i (не выходя за пределы интервала устойчивости), то это приведет к увеличению прибыли ΔP max = Δb i Y i Полученная простая формула, связывающая изменение максимальной прибыли (в исходной задаче) с изменением одного из ресурсов и теневой ценой ресурса (из двойственной задачи), является важнейшим соотношением двойственности и демонстрирует основную ценность теневых цен для менеджера. Теневая цена ресурса показывает, насколько увеличится прибыль от производства при увеличении данного ресурса на единицу. Ясно, что если запасы ресурса избыточны (т.е. не полностью используются при оптимальном плане производства), то теневая цена такого ресурса должна быть равна нулю, поскольку увеличение запасов такого ресурса не приведет к увеличению прибыли, а только увеличит неиспользованный остаток. Следует подчеркнуть, что теневые цены ресурсов будут изменяться, если изменение любого параметра ЛП-задачи выйдет за пределы интервала устойчивости. Понятно, например, что если уменьшить ежедневный запас стекла b 2 до величины, меньшей, чем 220 м (см. рис. 7, 12), то дальнейшее его уменьшение скажется на прибыли, т.е. теневая цена стекла Y 2 перестанет быть равной нулю. Как уже отмечалось, при решении симплекс-методом исходной задачи сразу же решается и двойственная. Если "Поиск решения" MS-Excel получил решение задачи об оптимальном плане продукции, то он нашел и теневые цены ресурсов. Никаких дополнительных операций по решению двойственной задачи на Практике делать не нужно. Полученные нами значения двойственных цен ресурсов мебельного цеха Y 1 =40; Y 2 =0; Y 3 =60 можно найти в колонке ―Теневые цены‖ таблицы "Ограничения" отчета об устойчивости для прямой задачи об оптимальном плане выпуска продукции (рис. 14). Приведенная в этой таблице информация - теневые цены и интервал устойчивости изменения запасов каждого из ресурсов, в котором значения теневых цен сохраняются, - помогает менеджеру не решая задачи заново, оценить, запасы какого ресурса нужно увеличивать, чтобы максимально увеличить прибыль, и какое будет увеличение прибыли при заданном изменении данного запаса. Упражнение по использованию отчета об устойчивости: влияние изменений в правых частях ограничений Для того чтобы освоиться с новым понятием теневых цен и научиться их правильно использовать для управленческого анализа организации производства, проделайте следующее упражнение. I. Решите задачу об оптимальном плане выпуска продукции мебельного цеха (рис. 1) и получите отчет об устойчивости. II. Переключитесь на вновь созданный лист отчета об устойчивости. Найдите в таблице "Ограничения" колонку "Теневые цены", рассчитайте изменение целевой функции при изменении ресурса b i по формуле ΔP= Δb i Y i и занесите результат в третью колонку данной таблицы для перечисленных случаев изменения запаса ресурсов: III.Вновь переключитесь на лист, содержащий прямую задачу о продукции мебельного цеха. Изменяя лимиты ресурсов (в ячейках В6:В8) в соответствии с п. И, каждый раз вызывая "Поиск решения" и заново решая оптимизационную задачу, прямым рас четом найдите изменение целевой функции и переменные решения в случаях 1-5 п. II и запишите эти изменения в четвертую колонку таблицы. В одних случаях результаты вашего предварительного расчета (третья колонка) совпадают с решением с помощью ни стройки "Поиск решения" (четвертая колонка), а в других нет. Почему? В качестве справочного материала приведем комментарии к отчету об устойчивости MS-Excel, а также перечислим основные отношения двойственности. Пункты I, II.1, II.2, III соотношения двойственности могут быть проверены на примере задачи о мебельном цехе. Пункты II.3, II.4 удобнее проверить позднее, при анализе мини-кейса "На кондитерской фабрике". Комментарии к отчету об устойчивости MS-Excel I. Влияние изменения запаса ресурсов (правых частей ограничений - b i ) 1. Отчет Excel об устойчивости включает таблицу "Ограничения" и в ней колонку "Теневая цена" (Shadow Price). Теневые цены -это оценки двойственной задачи. Они показывают, как меняется целевая функция при малом изменении b i : ΔP= Δb i Y i 2. Эти оценки верны только в пределах устойчивости решения, т.е. пока изменение b i; . не изменяет угловую точку области допустимых решений, в которой достигается максимум целевой функции (при этом численные значения переменных решениях, конечно, изменяются). При выходе b i за пределы устойчивости все теневые цены изменятся. 3 Пределы изменения b i , в которых оптимальное решение соответствует той же самой угловой точке, также даны в таблице "Ограничения" ("Допустимое увеличение" и "Допустимое уменьшение"). a) Причем если ресурс используется полностью (дефицитный), существует как верхний, так и нижний предел. b) Если же ресурс используется не полностью, верхний предел устойчивости равен бесконечности (Excel пишет 1Е+30, что означает 10 +30 , максимально известное программе число). 4 Следует понимать, что пределы устойчивости для изменения b i даются при условии, что все остальные значения правых частей b к (при k≠i) остаются неизменными. Одновременное изменение двух и более коэффициентов (b i и b к ) } каждого внутри своего интервала устойчивости, может привести к изменению теневых цен. 5. Для оценки влияния одновременного изменения нескольких значений b i следует вычислить относительные изменения Δb i /maxΔb i , где maxΔb i - это предел либо увеличения, либо уменьшения b i (в зависимости от знака ЛЬ), и вычислить сумму этих относительных изменений. При этом, если эта сумма больше 1, теневые цены изменятся, если меньше - нет. II. Влияние изменений в коэффициентах целевой функции 1. Изменение коэффициентов целевой функции с j не изменяет вида области допустимых решений. Оно изменяет наклон семейства прямых, изображающих целевую функцию. 2. До тех пор пока изменение наклона не превышает некоторых пределов, оптимальное решение {X j } вообще не меняется (максимальное значение целевой функции при этом, конечно, меняется). 3. При выходе значений коэффициента с j за эти пределы решение скачком перемещается в другую угловую точку области допустимых решений (при этом решение {Х j } может измениться очень сильно). 4. "Допустимое увеличение" и "Допустимое уменьшение" для каждого коэффициента целевой функции с j , при которых оптимальное решение не изменяется, приведены в таблице "Изменяемые ячейки" отчета Excel об устойчивости. a) Причем если X j > 0 (продукт входит в оптимальный план), то имеется как верхний, так и нижний предел для изменения соответствующего j-го коэффициента целевой функции. b) Если же Х j =0, то "Допустимое уменьшение" может быть как угодно велико - продукт все равно не войдет в оптимальный план. Верхний предел "Допустимое увеличение" показывает, насколько нужно увеличить соответствующий целевой коэффициент, чтобы j-й продукт вошел в оптимальный план. c) Величина, противоположная этому увеличению, называется Нормированная стоимость (Reduced Cost) и показывает, на сколько нынешняя цена продукта ниже минимальной цены (или издержки выше максимальных), при которой j-й продукт может войти в оптимальный план. 5. Следует понимать, что пределы устойчивости для изменения с j даются при условии, что значения всех остальных целевых коэффициентов c k (при k≠i) остаются неизменными. Одновременное изменение двух и более коэффициентов (c j и c k ), каждого внутри своего интервала устойчивости, может привести к изменению оптимального решения. 6. Для оценки влияния одновременного изменения нескольких значений c j следует вычислить относительные изменения Δc j /maxΔc j , где maxΔc j - это предел либо увеличения, либо уменьшения c j (в зависимости от знака Δc j ), и вычислить сумму этих относительных изменений. При этом, если эта сумма больше 1, оптимальное решение {Х j } изменится, если меньше - нет. Основные соотношения двойственности I. Если решения исходной задачи на максимум существует, то решение двойственной задачи на минимум точно ему равно: P max =C min Теневые цены для двойственной задачи – это оптимальное решение X j для прямой ЛП-задачи II. Для оптимальных планов исходной и двойственной задачи: 1. Если т.е. i-й ресурс использован полностью при производстве продукции по оптимальному плану, то его теневая цена больше нуля Y i >0 2. Если же т.е. i-й ресурс не использован полностью при производстве продукции по оптимальному плану, то его теневая цена равна нуля Y i =0. 3. Если X j >0, т.е. если j-й продукт вошел в оптимальный план, то в соответствующем ограничении двойственной задачи реализует знак равенство, т.е. выручка от продажи ресурсов, идущих на производство единицы этого продукта, равна прибыли от его производства: 4. Если же X j =0, т.е. если j-й продукт не входит в оптимальный план, то в соответствующем ограничении двойственной задачи реализует знак ―больше‖, т.е. выручка от продажи ресурсов, идущих на производство единицы этого продукта, больше равна прибыли от его производства: III. Теневые цены Y i показывают, на сколько увеличится значение P max , если запасы ресурса увеличить на единицу: ΔP max = Δb i Y i 3.3. Мини - кейс "На кондитерской фабрике". Акт 2 (Жаль... ведь мы все так любим "Батончик"!) После решения задачи об оптимальном плане для родной кондитерской фабрики юноша (сын владельца фабрики) испытал двойственное чувство. С одной стороны, прибыль, соответствующая найденному им производственному плану, почти на 430 у.е. больше, чем по плану мастера, т.е. он заработал более 400 баксов. Это здорово! С другой стороны, почему компьютер отказался от выпуска "Батончика" (эту конфету юноша с детства любил больше всех остальных)? Юноша был уверен, что "Батончик" - один из лучших продуктов, которые выпускает фабрика его отца. Если его не окажется на прилавках, может пострадать имидж фабрики. Ведь не только он сам, но и все соседи в округе обожают эту конфету! Кроме того, он вспомнил, что на занятиях по количественным методам в менеджменте преподаватель все время твердил об анализе полученного оптимального решения на устойчивость: малые изменения величины запасов могут привести к радикальному изменению решения! А вдруг этот вредный старый мастер не только план производства определяет на глазок, но и запасы сырья взвешивает кое-как? А что, если каких-то запасов не хватит для его оптимального плана? Он не доберет прибыли! Может быть, тогда более прибыльным станет иной план? Какой? И еще одна мысль. У него есть в кармане около 50 баксов. Может, пустить их в дело? Докупить у знакомого оптовика какого-нибудь сырья, потихоньку подложить на склад (чтобы мастер не заметил), как будто так и было. Тогда можно получить дополнительную прибыль (и премию от отца). Только вот какого сырья докупать? И сколько? И на сколько от этого возрастет прибыль? Итак, ответьте на следующие вопросы 1. Как надо изменить норму прибыли для любимого продукта сына хозяина фабрики ("Батончика"), чтобы он вошел в оптимальный план? (Ответьте, не решая задачу, анализируя лишь отчет об устойчивости.) 2. Введите это изменение в данные и решите задачу заново. Как изменился оптимальный план? 3. Какой ресурс является наиболее дефицитным (т.е. максимально влияет на прибыль)? 4. Можете ли вы сказать (не решая задачу снова), как изменится прибыль от производства, если количество этого ресурса оценено: а) с избытком в 10 весовых единиц; б) с недостатком в 5 единиц? 5. Есть ли другой способ добиться производства "Батончика" (кроме изменения нормы прибыли)? Комментарии к мини - кейсу Вопросы 1-2 Согласно отчету об устойчивости (рис. 17), нормированная стоимость конфеты "Батончик", не вошедшей в оптимальный план, составляет 0,00874 у.е. Абсолютная величина этого числа показывает, на сколько нужно увеличить прибыль от производства одного пакетика этих конфет, чтобы "Батончик" вошел в оптимальный план. Добавим к цене "Батончика" 0,01 у.е. В этом случае прибыль на единицу этого продукта станет равной 1,11 у.е. Решение задами с этим новым значением параметра показано на рис. 18. Для сравнения внизу листа MS-Excel приведены суммарная прибыль от производства и оптимальный план производства для старого значения параметра 1,1 у.е. Видно, сколь драматически отличаются решения в этих двух случаях, хотя значения прибыли практически одинаковы! В таких случаях обычно говорят, что решение задачи неустойчиво. Решение называется неустойчивым, если малые изменения параметров приводят к огромным изменениям решения. Чаще всего о неустойчивости говорят в негативном смысле, подразумевая даже, что неустойчивость ограничивает возможности аналитика использовать количественные методы для принятия управленческих решений. Действительно, поскольку в реальной ситуации параметры модели всегда известны с определенной неточностью (ошибкой), а малые изменения параметров приводят к катастрофическим изменениям решения, то найденное оптимальное решение бесполезно! Оно рассчитано для строго определенных значений параметров, при других значениях параметров оно будет совершенно другим, а каковы реальные значения интересующих нас параметров, мы точно не знаем. Если мы попытаемся выбрать между несколькими альтернативами, каждая из которых может стать оптимальной при незначительном изменении параметров, то не сможем сделать правильный выбор. В этом случае действительно уместно говорить о "деструктивной" роли неустойчивости и пытаться найти методы борьбы с ней. В курсе "Количественные методы в менеджменте" можно столкнуться с примером такой "дурной" неустойчивости при рассмотрении методов выбора альтернатив в условиях риска. Однако в случае с данным мини-кейсом неустойчивость решения не кажется очень страшной, ведь прибыль-то в обоих случаях почти одинакова! Попробуйте вернуть прежнее значение прибыли для "Батончика" (1,1 у.е.) - прибыль уменьшится до 1498,5 у.е. Это менее чем на 1% ниже оптимальной. Попробуйте ввести целочисленные ограничения на количество пакетиков каждого из продуктов или просто потребовать, чтобы количество произведенных пакетиков "Батончика" было не менее 100, 300, 500. Во всех чих случаях вы получите другие оптимальные решения, а прибыль будет отличаться от оптимальной (для исходного варианта постановки задачи) не более чем на 1%. Таким образом, в вашем распоряжении окажется множество альтернативных решений, сильно различающихся по значениям переменных, но очень близких по прибыли. Это не плохо. Это очень хорошо! Наличие многих, пусть не вполне оптимальных, но "хороших" альтернативных решений позволяет менеджеру выбрать такое, которое в наилучшей степени отвечает тем или иным неформализуемым требованиям и условиям, которые всегда присутствуют при принятии решений. В данном случае таким неформализуемым условием является любовь лица, принимающего решение, к "Батончику", который, к несчастью, не вошел в оптимальный план при исходной постановке задачи. За эту любовь приходится платить либо повышением цены на данный продукт, либо снижением валовой прибыли. Что предпочесть? - Смириться с отсутствием "Батончика" в оптимальном плане? - Повысить цену? - Ввести ограничение на минимальное количество пакетиков "Батончика"? На эти вопросы модель ответа не даст. |