Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
Указания - При ответе на вопросы с), d) и е) сохраните ограничение "не менее 200 костюмов каждого типа". - Для ответа на вопросы с) и d) обязательно используйте данные отчета об устойчивости. - При рассмотрении каждого следующего варианта изменения условий возвращайте ранее измененные параметры к исходным значениям. 5. Оптимальная загрузка оборудования ткацкого цеха (продолжение) Вернитесь к примеру "Оптимальная загрузка оборудования ткацкого цеха" из предыдущего раздела 2. При рассмотрении этого примера можно было требовать, чтобы все станки были загружены, а можно было потребовать лишь, чтобы число сгруженных станков каждого типа не превышало числа имеющихся станков этого типа. Интересно, что максимум дохода с продаж при этом получается один и тот же. Разумеется, в условиях рыночной экономики наиболее ценен тот план, который позволяет достичь максимума прибыли с наименьшими затратами. В связи с этим возникают следующие вопросы: a) Какое максимальное количество станков первого или второго типа можно высвободить, не уменьшая величины полученного максимального дохода? b) Если не все станки задействованы, значит, дальнейшему увеличению дохода мешают другие ограничения. Насколько их надо ослабить, чтобы полностью использовать машинный потенциал цеха? Насколько при этом увеличится доход? c) Какое из имеющихся ограничений выгоднее ослабить? Указания - Ответьте на эти вопросы, пользуясь только отчетом об устойчивости, полученным при решении исходной задачи. Чтобы результат был более "чистым", при решении исходной задачи считайте, что все станки должны быть задействованы. - Проверьте полученные ответы прямым расчетом, последовательно изменяя параметры на листе MS-Excel. 6. Оптимальный план размещения производственных заказов (продолжение) Вернитесь к примеру "Оптимальный план размещения производственных заказов", рассмотренному в предыдущем разделе 2. Получите отчет об устойчивости. a) Дайте интерпретацию полученных теневых цен. b) Стоит ли увеличить инвестиции в проект? Если да, то за какой срок дополнительные инвестиции окупятся? Почему это произойдет? Изменится ли оптимальный план размещения? c) Насколько увеличатся издержки, если решено выпускать не 300, а 350 изделий в месяц? Почему это произойдет? Изменится ли оптимальный план размещения? Указания - Ответьте на все вопросы, пользуясь только отчетом об устойчивости, полученным при решении исходной задачи. - Проверьте полученные ответы прямым расчетом, последовательно изменяя параметры на листе MS-Excel. 7. Минимизация отходов лесопилки (продолжение) Вернитесь к примеру "Минимизация отходов лесопилки", рассмотренному в предыдущем разделе 2. Так же как и при решении исходной задачи, считайте, что число стандартных кусков не менее заказа (но может быть и больше, т.е. часть кусков заготовлена впрок). Не вводите целочисленные ограничения! Получите отчет об устойчивости. a) Дайте интерпретацию теневых цен. b) Каков должен быть запас бревен на лесопилке, чтобы обратить отходы в ноль? c) Что произойдет, если запас бревен уменьшить ниже величины нижнего предела устойчивости? Указания - Ответьте на все вопросы, пользуясь только отчетом об устойчивости, полученным при решении исходной задачи. - Проверьте полученные ответы прямым расчетом, последовательно изменяя параметры на листе MS-Excel. 4 ИСПОЛЬЗОВАНИЕ ЦЕЛОЧИСЛЕННЫХ ПЕРЕМЕННЫХ В ЛП - ЗАДАЧАХ В этом разделе рассмотрены примеры оптимизации ЛП-моделей, в которых введено требование целочисленности переменных решения. Это требование, с одной стороны, резко усложняет алгоритм оптимизации таких моделей, резко снижает возможности анализа оптимального решения и не должно вводиться без явной необходимости; с другой - позволяет рассмотреть абсолютно новый и важный с практической точки зрения круг моделей. Изучив материал раздела и реализовав описанные процедуры решения приведенных примеров на компьютере, вы • познакомитесь с методом формализации логических условий в ЛП-задачах на основе введения так называемых логических (или булевых) переменных, которые могут принимать только значения 0 или 1; • сможете учесть постоянные издержки при выборе оптимального плана производства (что невозможно сделать, оставаясь в рамках обычной ЛП-модели); • научитесь формулировать и решать задачи об оптимальном расположении предприятий и об оптимальном выборе нескольких из множества альтернатив; • научитесь использовать надстройку "Поиск решения" для решения целочисленных ЛП-задач. В практике управления условия оптимизации нередко формулируются в терминах "подходит-не подходит", "присутствует-отсутствует", "да-нет". Часто само наличие того или иного ограничения, вид целевой функции и т.д. зависят от наличия или отсутствия одного или нескольких факторов. Поэтому умение записать такие логические отношения в виде равенств или неравенств очень полезно при формулировке оптимизационных задач в самых разных областях бизнеса и управления. Одним из основных условий применимости симплекс-метода и других методов решения задач линейного программирования является то, что переменные решения могут принимать непрерывный ряд значений, т.е., иными словами, быть не только целыми, но и дробными. В ряде моделей это нисколько не вступает в противоречие со смыслом переменных решения. Если, например, переменная представляет величину, измеряемую в метрах, килограммах, литрах и т.д., то совершенно ясно, что ее оптимальное значение вполне может быть дробным. Более того, если в задаче об оптимальном ежедневном плане выпуска продукции мебельного цеха оказывается, что нужно произвести 76,33 шкафа и 74,67 тумбы, то это тоже не является бессмысленным. Это просто значит, что рабочее время одного из рабочих следует разделить между изготовлением шкафов и тумб в отношении 33%/67%. При этом за 3 дня он должен сделать 1 шкаф и 2 тумбы. Однако в ряде задач целочисленные значения переменных решения являются обязательными. Например, в мини-кейсе об оптимальном использовании ресурсов кондитерской фабрики, оставшихся перед ее длительной остановкой на реконструкцию, число пакетиков конфет разного типа, конечно, должно быть целым. Пусть решается вопрос о покупке нескольких различных типов станков в количествах, которые должны, с одной стороны, минимизировать издержки завода- покупателя, а с другой - обеспечить необходимые требования по выпуску продукции. Если при этом модель выдает рекомендацию купить 2,13 штуки станка первого типа, 3,435 - второго и 0,67 -третьего, ясно, что такая рекомендация неприемлема. Условие целочисленности Таким образом, в ряде случаев совершенно необходимо получить целочисленные значения переменных решения. Как уже отмечалось выше, надстройка "Поиск решения" MS-Excel позволяет легко ввести требование целочисленности переменных. Однако необходимо ясно осознавать, что введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования, если переменные целые "Поиск решения" MS-Excel будет использовать другие, специальные, более сложные алгоритмы, которые требуют существенно больших вычислительных затрат, чем симплекс-метод и другие ЛП-алгоритмы. Кроме того, отказ от обычной ЛП-модели в пользу ЛП-модели с требованием целочисленности переменных делает невозможным получение информации об устойчивости решения и о теневых ценах. Поэтому "Поиск решения" MS-Excel не формирует отчета об устойчивости, если в качестве одного из ограничений введено условие целочисленности хотя бы для одной переменной. Это лишает аналитика и менеджера важного инструмента анализа оптимального решения и определения путей его улучшения через изменение параметров модели. Вследствие этого в тех случаях, когда предполагаемые оптимальные значения переменных решения много больше 1, как, например, в задаче о кондитерской фабрике, приемлемым вариантом может быть округленное до целых чисел оптимальное решение ЛП-задачи (рис.19). При этом, разумеется, округлять оптимальное решение нужно так, чтобы решение осталось в области допустимых планов (т.е. чтобы расход ресурсов не превышал их запасов). Такое решение нетрудно получить после нескольких проб и ошибок (попыток округления с избытком или с недостатком). Поскольку округленное решение уже не является оптимальным, значение прибыли чуть ниже максимального для исходной ЛП-задачи. Как видно из рис. 19, после введения требования целочисленности переменных решения компьютер находит оптимальное целочисленное решение, которое характеризуется чуть более высоким значением прибыли, чем округленное решение, и чуть более низким, чем оптимальное решение исходной ЛП-задачи. В случаях же когда предполагаемое оптимальное решение выражается числами, сравнимыми с единицей, целочисленных ограничений не избежать и с потерей отчета об устойчивости приходится мириться. Проблемы типа "брать/не брать". Логические переменные Помимо рассмотренных вполне очевидных случаев, в которых необходимо введение условия целочисленности, существует и другая область использования целочисленных переменных в ЛП-задачах. Весьма часто на практике возникают задачи, когда требуется решить, какие элементы из большого их набора нужно выбрать, чтобы оптимизировать целевую функцию и удовлетворить заданным ограничениям, а какие отбросить. Этот класс задач по-английски называют задачами типа "go/no go", что по-русски соответствует дилемме "брать/не брать". Часто также о подобных задачах говорят как о задачах "загрузки вещевого мешка", имея в виду следующую "туристическую" аналогию. Имеется множество предметов, которые вы хотели бы взять в поход, но все они не входят в вещевой мешок. Вы приписываете каждой вещи определенную величину ценности и пытаетесь заполнить мешок наиболее ценными вещами, удовлетворяя одновременно ограничения по суммарному объему и весу содержимого мешка. На практике к такой схеме могут сводиться некоторые задачи формирования инвестиционного портфеля, выбора оптимальных мест размещения новых предприятий и т.п. Ниже мы рассмотрим пример такой задачи. Проблема "брать/не брать" может возникнуть и в задачах об оптимальном плане производства, если производство одного или нескольких продуктов связано с каким-либо дополнительным условием. Такое условие может возникать прежде всего в связи с необходимостью учета постоянных издержек. Во всех этих случаях наше решение "брать" или "не брать" может быть выражено введением специальной целочисленной переменной, которая может принимать только два значения: 0 ("не брать") и 1 ("брать"). Такие по существу логические переменные в математике называют "булевыми" переменными по имени Дж. Буля, развившего в прошлом веке аппарат символической логики, широко используемый в современной математике и программировании. Мы начнем рассмотрение применения таких переменных с проблемы учета постоянных издержек в ЛП-моделях. 4.1. Проблема постоянных издержек в линейном программировании. Мини - кейс "На кондитерской фабрике". Акт 3 (Проблема учета постоянных издержек) После проведенного анализа сын владельца фабрики принес в цех свой первый оптимальный план и с гордостью показал мастеру. Тот на мгновенье нахмурился ("Ишь, какой умный нашелся!"), но затем с облегчением вздохнул и громко засмеялся: • "Ну что ж, молодой человек, замечательно! Будем реализовывать! Только учти, что по технологии до (или после) производства конфеты "Белка" (особенно в таком количестве, как ты рекомендуешь) надо остановить производственную линию и тщательно ее вычистить, а то будет брак! А стоит такая очистка 400 у.е. Так что с премией своей можешь попрощаться". Вот это удар! Что же делать? Надо срочно пересчитать оптимальный план с учетом этой постоянной издержки, тем более (вспомнил юноша) что для этого существует очень изящный метод, использующий целочисленные переменные. Прежде чем приступить непосредственно к анализу неожиданно возникшей проблемы сына хозяина кондитерской фабрики, заметим, что попытка учета постоянных издержек наталкивается на фундаментальное ограничение моделей линейного программирования. Действительно, целевая функция F (будь то прибыль или издержки) в линейной модели должна быть представлена как сумма произведений целевых коэффициентов на переменные решения: F = c 1 X 1 +c 2 X 2 + ...+c n X n . Если трактовать, как количества произведенных единиц продукта j-го типа, а коэффициенты с j - как издержки на единицу произведенного продукта (или прибыль на единицу продукта, т.е. цена минус издержки на производство одного изделия), то очевидно, что принимаются в расчет только те издержки, которые пропорциональны количеству выпущенных изделий. Эти издержки называются переменными, и к ним относятся сдельная оплата труда, расход материалов, электроэнергии и пр. Однако наряду с переменными издержками с процессом производства (или обслуживания) всегда связаны и постоянные издержки. К такого рода издержкам можно отнести затраты на аренду помещений, оплату работы менеджеров и вспомогательных служб, расходы на связь и оргтехнику и пр. Если эти расходы одинаковы независимо от вида производимой продукции, то они не влияют на определение оптимального плана выпуска продукции. Их просто можно прибавить к оптимальным переменным издержкам (или вычесть из оптимальной прибыли) определенным путем решения оптимизационной задачи. Представим, однако, что на одной и той же производственной линии можно выпускать различную продукцию, причем для каждого нового продукта нужно переналадить оборудование, а это требует новых затрат (устойчивый английский термин для таких затрат - "setup cost"). В таком случае вид целевой функции должен быть существенно изменен. Заметим, что встречающаяся в бухгалтерском учете практика "размазывания" постоянной издержки на всю партию выпущенных изделий и увеличения таким образом величины издержек на одно изделие совершенно неприменима при решении ЛП-задачи об оптимальном плане. В этой задаче количество выпущенных изделий данного типа - это переменная X j , подлежащая определению (т.е. заранее неясно, на какое количество изделий нужно "размазать" постоянную издержку), а издержка (или прибыль) на одно произведенное изделие с j должна быть постоянной (т.е. не зависящей от количества выпущенных изделий). Анализ 3 - го акта мини - кейса “На кондитерской фабрике” Вернемся теперь к анализу ситуации на кондитерской фабрике (рис. 20). Введем в рассмотрение величину постоянных издержек FC = 400 у.е., связанную с производством конфет "Белка". Это продукт № 4. Соответственно количество пакетиков этих конфет обозначено Х 4 . Будем считать, что постоянная издержка FC появляется, когда произведен хотя бы один пакет этих конфет (хотя мастер из кейса явно лукавит: он ведь не включал эту издержку при оценке прибыли для своего "оптимального" плана - каждого продукта по 200 пакетиков). Она не зависит от того, как много пакетиков Х 4 произведено. Однако если "Белка" не производится вообще (Х 4 =0), то этой издержки нет. В этих условиях целевую функцию - прибыль можно записать следующим образом: Однако такой вид функции (резкий скачок прибыли при Х 4 = 0) совершенно не соответствует принципам линейной модели. Можно сохранить "линейный" вид целевой функции, если ввести новую целочисленную переменную Y, которая будет принимать только два значения - 0 и 1, и связать значение переменной Y со значением Х 4 аналогичным условием. При этом на переменную Y надо наложить дополнительные условия: Y≥0, Y≤1 и Y-целое. Теперь, чтобы превратить задачу об оптимальном плане с учетом постоянных издержек в задачу целочисленного линейного программирования, необходимо заменить "логическую" связь значений Y и Х 4 еще одним линейным условием. Фактически речь идет о том, что если оптимизационный алгоритм "согласен" положить Y = 1 и уменьшить прибыль Р на величину FC=400 у.е., то ограничений на производство "Белки" нет (Х 4 > 0). Если же алгоритм "желает" положить Y = 0, то ему придется отказаться от производства "Белки" (Х 4 = 0). Такое своеобразное "мигающее" ограничение на Х 4 , которого нет, если Y=1, и которое появляется, если Y=0, можно записать в виде линейного неравенства следующим образом: X 4 -M*Y≤0, где М должно быть очень большим числом. "Очень большое" - значит, больше любого мыслимого количества пакетиков Х 4 , которое можно произвести из имеющихся ресурсов. Из решения исходной задачи ясно, что количество Х 4 вряд ли может превысить 1000. Поэтому зададим М = 10 000 (конкретное значение М не важно, можно задать и миллион). Тогда если Y= 0, то записанное неравенство сведется к Х 4 ≤0. Однако поскольку, как и все другие переменные, Х 4 должно быть больше 0, остается единственная возможность Х 4 = 0, что и требовалось по смыслу. Если же Y=1, то неравенство приведется к виду Х 4 ≤М (или 10 000). Поскольку Х 4 все равно не может быть таким большим, то это неравенство фактически никаких ограничений на Х 4 не налагает. Оно называется несвязывающим. Его как бы и вовсе нет. Организация данных для анализа 3 - го акта мини - кейса на листе MS-Excel 1. Организуйте данные так, как показано на рис. 20 "На кондитерской фабрике" (Проблема учета постоянных |