Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
издержек). Для этого: a) добавьте в строчку №10 заголовок Постоянные издержки и введите число 400 - постоянные издержки - в колонку Белка; b) добавьте новую переменную Y в строчку переменных решения (в ячейку Н12 - название переменной, в ячейку Н13 - 0); c) в формулу для прибыли добавьте произведение 400*Y со знаком "-"; d) добавьте новое ограничение в колонку ограничений (Да Нет- в ячейку А22 и выражение Белка - 10000*Y (=$Е$13 -10 000*$Н$13) - в ячейку В22). 2. Вызовите "Поиск решения" и сделайте необходимые изменения в установках: a) Изменяемые ячейки: С13:Н13; b) Ограничения: С13.Н13 ≥ 0 (все переменные положительны), Н13≤1, Н13 - целое (7- целая величина, равная 0 или 1), В22 ≤ 0 (не производить "Белку", если Y = 0, производить, если Y=1). Вместо двух условий Н13≤1; Н13- целое можно задать лишь одно Н13 - двоичное (т.е. может равняться либо 0, либо 1). 3. Сопоставьте решение с первоначальным решением линейной задачи. a) Как изменился оптимальный план? b) На сколько уменьшилась максимальная прибыль? c) Рекомендует ли полученное альтернативное решение переналадку оборудования для производства продукта "Белка"? d) Если нет, попробуйте найти, на сколько нужно увеличить норму прибыли конфет "Белка", чтобы их стало выгодно производить. 4.2. Оптимальный план размещения предприятий Пример: Где выбрать места для стоянок такси? Управляющий новой таксомоторной компании пытается определить оптимальное расположение для стоянок своих такси. В таблице собрана необходимая информация относительно предполагаемых точек стоянки. Важной характеристикой положения стоянки является способность ее персонала своевременно обслуживать заказы из тех районов города, которые находятся в зоне ответственности данной стоянки Машина должна прибывать по заказу в любую точку подопечного района за время, не превышающее некоторое максимальное. Точка стоянки Обслуживаемые районы Стоимость аренды, долл. в день 1 2 3 4 5 A, E A, C, D B, C, E B, D D, E 400 500 450 440 420 Как видно из таблицы, потенциальные места для стоянок позволяют обслужить по 2 или 3 выделенных района города. Управляющий должен выбрать некоторые из них так, чтобы каждый район города мог быть обслужен хотя бы одной из выбранных стоянок и чтобы стоимость аренды была минимальной. Анализ примера Прежде всего формализуем информацию о том, в состоянии ни персонал i-й стоянки обслужить j-й район (занумеруем районы в очевидном порядке: А-1, В-2,... Е-5). Для этого введем булевы (логические) параметры a ij равные единице, если с 1- й стоянки можно обслужить j-й район, и равные нулю - если нельзя. Значения а ij приведены в таблице параметров. Введем также переменные решения Х i также принимающие только значения 1 или 0 в зависимости от того, выбрана данная точка стоянки управляющим или нет. Очевидно, что сумма произведений столбца переменных решения на столбец стоимостей аренды c i даст суммарные ежедневные затраты С на выбранные точки аренды. Действительно, допустим, что управляющий выбрал первые те стоянки и пятую, а третью и четвертую отверг. В столбце переменных решения отмечены (в скобках) значения переменных, соответствующие этому выбору. Тогда сумма произведении будет равна 1*400+1*500+0*450+0*440+1*420 = 400 + 500 + 420, т.е. сумме затрат на аренду именно тех стоянок, которые выбрал управляющий. Рассмотрим теперь сумму произведений столбца переменных решения на столбец коэффициентов a ij , соответствующий j-му району. Например, для первого района (А) N 1 =1*1+1*1+0*0+0*0+0*1=2, а для второго района (В) N 2 =0*1+0*1+1*0+1*0+0*1=0. Нетрудно понять, что числа N 1 и N 2 показывают, сколько выбранных стоянок могут обслужить данный район. При выбранном наборе стоянок первый район (А) обслуживается с двух стоянок: 1-й и 2-й а второй район (В) не обслуживается ни одной из выбранных стоянок. Ясно, что для выполнения основного требования управляющего о том что каждый район должен обслуживаться хотя бы с одной из выбранных стоянок, необходимо ввести в качестве ограничений условие, что каждое из чисел N i должно быть больше или равно единице. Организация данных на листе MS-Excel Для практического решения задачи с помощью MS-Excel организуйте данные так, как показано на рис. 21 "Оптимальный план размещения стоянок такси". Введите целевую функцию как сумму произведений столбца переменных решения I5:I9 на столбец стоимостей аренды G5 : G9. Введите ограничения на число стоянок, с которых может обслуживаться первый район (А), в ячейку В10 как сумму произведений столбца переменных решения $I$5:$I$9 на столбец коэффициентов а 1j В5:В9 и распространите эту формулу на все районы (ячейки C10:F10). В установках "Поиска решения" введите требования для булевских переменных решений: I5:I9 ≥ 0 I5:I9 ≤ 1 I5:I9 -целые, или вместо этих трех условий I5:I9 - двоичные, а также ограничения на числа N i B10:F10 ≥ 1. После вызова "Поиск решения" и необходимых установок прочтите решения в ячейках I5:I9 (не забудьте и в этом случае на вкладке "Параметры" отметить флажок "Линейная модель"). Заключение к разделу 4 Надстройка "Поиск решения" MS-Excel позволяет легко ввести требование целочисленности переменных. Однако введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования и делает невозможным получение информации об устойчивости решения и о теневых ценах. Вследствие этого в тех случаях, когда предполагаемые оптимальные значения переменных решения много больше 1, приемлемым вариантом может быть округленное до целых чисел оптимальное решение ЛП-задачи. Существует круг практически важных моделей, при анализе которых требуется решить, какие из большого набора элементов нужно выбрать, чтобы оптимизировать целевую функцию и удовлетворить заданным ограничениям, а какие отбросить. Этот класс задач по-английски называют задачами типа "go/no go", что по-русски соответствует дилемме "брать/не брать". В этих случаях наше решение "брать" или "не брать" может быть выражено введением специальной целочисленной переменной, которая может принимать только два значения: 0 ("не брать") и 1 ("брать"). Такие переменные называются логическими или "булевыми" переменными (в надстройке MS-Excel "Поиск решения" они называются двоичными). К числу таких проблем относится проблема постоянных издержек при выборе оптимального плана производства: если продукт производится, из прибыли нужно вычесть постоянную издержку, а если не производится - постоянной издержки нет. Подобные проблемы возникают также при выборе оптимального набора проектов для инвестирования или оптимального набора мест для расположения тех или иных предприятий из множества потенциальных кандидатов. Формализация логических отношений сводится к простым ограничениям на введенные логические переменные, их суммы и разности. В проблемах типа "брать/не брать" часто бывает необходимо ввести кроме логических переменных также логические параметры, равные 1, если данный кандидат на вхождение в оптимальный набор обладает тем или иным важным признаком, и равные 0, если нет. Сумма произведений логических переменных на такие логические параметры для всех рассматриваемых элементов показывает, какое количество элементов, попавших в оптимальный набор, обладает данным признаком. При малых изменениях параметров оптимальные решения проблем типа "брать/не брать" резко меняются, но целевая функция при этом остается примерно постоянной. Это означает наличие множества альтернативных решений, близких к оптимальным, что, как мы знаем, расширяет возможности менеджера выбрать решение, удовлетворяющее оставшимся неформализованным факторам. Учет постоянных издержек, даже в случае если они одинаковы для всех продуктов, резко снижает ассортимент продукции. Требование о сохранении того или иного количества типов продукции приводит, естественно, к снижению прибыли. Контрольные вопросы к разделу 4 1. Всегда ли стоит вводить целочисленные ограничения, чтобы получить целые решения? Есть ли отрицательные последствия введения таких ограничений? Какие? 2. Что такое логические переменные? В каких задачах их применение необходимо? Приведите 2-3 собственных примера. 3. Объясните, почему постоянные издержки нельзя учесть в простой ЛП-задаче (без целочисленных переменных)? Почему для определения оптимального плана неприемлема бухгалтерская практика "размазывания" постоянных издержек по всей партии выпущенных изделий и определение таким образом "удельных" издержек на единицу продукции? 4. Объясните, каким образом введение целочисленных (точнее, логических) переменных помогает решить проблему постоянных издержек в Л П-задачах? 5. Рассмотрите таблицу параметров примера "Где выбрать места для стоянок такси?". • Что означают нули и единицы, стоящие в каждой клетке таблицы? • Просуммируйте числа, стоящие в столбцах таблицы. Что означают полученные числа? • Просуммируйте числа, стоящие в строках таблицы. Что означают полученные числа? • Чем суммы строк и столбцов таблицы параметров отличаются от чисел, получившихся в строке 10 таблицы MS-Excel на рис.21? 6. Приведите 2-3 собственных примера, когда дробные решения задач линейного программирования имеют практический смысл и не требуют округления до целых и когда округление до целых необходимо. Примеры для самостоятельного анализа к разделу 4 1) Оптимальная загрузка оборудования ткацкого цеха (окончание) Вернитесь к примеру "Оптимальная загрузка оборудования ткацкого цеха", рассмотренному в предыдущих разделах 2 и 3. Для всех вариантов произведенных вами расчетов введите теперь целочисленные ограничения на переменные - число станков, выпускающих каждый из видов ткани. а) Насколько сильно отличается оптимальное решение с целочисленным ограничением на переменные от полученных ранее? b) Можно ли получить это оптимальное решение простым округлением решения ЛП-задачи? Стоит ли вводить целочисленное ограничение в этой задаче? 2) Минимизация отходов лесопилки (окончание) Вернитесь к примеру "Минимизация отходов лесопилки", рассмотренному в предыдущих разделах 2 и 3. Так же как и при решении исходной задачи, считайте, что число стандартных кусков не менее заказа (но может быть и больше, т.е. часть кусков заготовлена впрок). Введите целочисленные ограничения. Насколько сильно отличается оптимальное решение с целочисленным ограничением на переменные от полученных ранее? Стоит ли вводить целочисленное ограничение в этой задаче? Измените ограничения исходной задачи так, чтобы число стандартных кусков было точно равно заказу (а не больше него). Введите целочисленные ограничения. Существует ли решение? Почему? Что нужно изменить в условиях задачи, чтобы решение существовало? Существенно ли целочисленное ограничение в этом случае? 3) Еще раз о плане кондитерской фабрики (окончание) Модифицируем условия 3-го акта мини-кейса "На кондитерской Фабрике". Будем считать, что постоянные издержки существуют при запуске линии на производство любых конфет и что для любых конфет они равны 100 у.е. а) Организуйте данные на листе MS- Excel и решите задачу при этих условиях. Сколько видов конфет теперь выгодно выпускать? Насколько уменьшилась прибыль по сравнению с решением исходной задачи (акт 1 мини-кейса), сформулированной в разделе 2.1? Допустим, что по маркетинговым соображениям вы не можете допустить столь бедного ассортимента и хотите потребовать, чтобы в оптимальный план вошло не менее 3 видов, 4 видов или все 5 видов продукции. b) Введите в решение соответствующее ограничение и найдите оптимальный план. Как изменяется прибыль при расширении ассортимента продукции? Почему? c) Всегда ли равенство Y i =1 означает реальное производство продукта? Почему? Указания • При организации данных на листе MS-Excel расположите логические переменные Y i определяющие, производить или нет соответствующий продукт, подстрокой переменных Х i . Используйте функцию СУММПРОИЗВ для записи целевой функции. Расположите строку с условиями, связывающими значения Y i и X i подстроками переменных. • Количество производимых продуктов (точнее, тех, для которых производится настройка линии), очевидно, равно сумме всех Y i 4) Выбор оптимальных проектов для финансирования Управляющему банка были представлены предложения о четырех проектах, претендующих на кредиты банка. Проект А должен принести компании прибыль 21 тыс. долл., проект В - 18 тыс. долл., проект С- 16 тыс. долл. и проект D- 17 500 долл. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов. Доступная наличность банка составляет 22 тыс. долл. в течение периода 1, 25 тыс. долл. - в течение периода 2, 38 тыс. долл. - в течение периода 3 и 30 тыс. долл. - в течение периода 4. Проект Потребность в наличности, долл. Период 1 Период 2 Период 3 Период 4 A 8000 8000 10000 10000 B 7000 9000 9000 11000 C 5000 7000 9000 11000 D 9000 8000 7000 6000 Какие проекты следует финансировать и какое количество наличности необходимо в течение каждого периода, если цель состоит в том, чтобы максимизировать прибыль? Указания • Введите логические переменные Y i равные 1, если проект принимается, и равные 0, если нет. • Суммарная потребность в наличности в данный период есть сумма произведений Y i на столбец финансовых затрат по каждому проекту в данный период. 5) Оптимальный план развития новых программных продуктов Компания "Корвет" производит программное обеспечение на CD-ROM, которое продается в пакете с драйверами CD- ROM основными производителями компьютерного оборудования. Компания оценивает возможность развития 6 новых программных приложений. В таблице представлена информация о затратах и ожидаемой чистой приведенной прибыли от продажи приложения (с учетом временной стоимости денег). Приложение Ожидаемые затраты на развитие, долл. Требуемое число программистов Ожидаемая чистая приведенная прибыль, долл. 1 400000 6 2000000 2 1100000 18 3600000 3 940000 20 4000000 4 760000 16 3000000 5 1260000 28 4400000 6 1800000 34 6200000 У "Корвета" 60 программистов. Фирма может выделить 3,5 млн. долл. на развитие новых программных приложений. Каков оптимальный набор приложений, которые следует развивать, если • ожидается, что клиенты, заинтересованные в приложении 4, будут заинтересованы также в приложении 5, и наоборот? Таким образом, если одно из приложений решено развивать, другое тоже должно быть развито;• развитие приложения 1 имеет смысл, только если в пакет включено также приложение 2? Таким образом, если решено развивать приложение 1, то и приложение 2 должно быть развито. Однако если решено приложение 1 не развивать, то приложение 2 все же может быть включено в пакет; • приложения 3 и 6 эксплуатируют одну и ту же тему? Следовательно, если одно из них развивается, то другое определенно нет; • стремясь обеспечить качество продукции, "Корвет" не склонен развивать более 3 программных продуктов? Проанализируйте влияние каждого из 4 последних ограничений на оптимальное решение. Указания . Введите логические переменные Y i для каждого из проектов -претендентов на включение в план и выразите через них целевую функцию и ограничения на все ресурсы фирмы. • Если из каких-либо двух проектов либо оба должны быть приняты, либо оба отвергнуты, то значения V, у них должны быть, очевидно, одинаковы. • Если один проект принят (Y i = 1), а другой при этом должен быть отвергнут (Y k = 0) и наоборот, то их значения Y i и Y k должны в сумме всегда равняться 1. 5 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ В этом разделе мы рассмотрим две модели, исключительно широко использующиеся в деловой практике: транспортную задачу и задачу о назначениях. Хотя обе они являются ЛП-моделями, но имеют весьма характерные особенности, которые позволяют применять для их решения особые, чрезвычайно эффективные методы. Изучив материал раздела и реализовав описанные процедуры решения и анализа приведенных примеров на компьютере, вы • познакомитесь с характерными особенностями этих моделей и получите представление о методах их решения; • узнаете, в чем состоит и почему столь важно для практики условие сбалансированности транспортной задачи и задачи о назначениях, а также как сбалансировать реальные задачи; • научитесь правильно организовывать данные для решения транспортных задач и задач о назначениях на листе MS- Excel и решать с помощью надстройки "Поиск решения" такие задачи, содержащие до 200 переменных. Если вы работаете в производственной или дистрибьюторской фирме, если логистика составляет важную часть вашего бизнеса, вы обязательно столкнетесь с необходимостью оптимизации затрат на транспортные перевозки. В случае если количество складов и потребителей не превышает 10-15, вы легко решите транспортную задачу с помощью MS-Excel, а для более крупных задач сумеете использовать специализированное программное обеспечение. Если ваши задачи связаны с расстановкой рабочих по операциям, распределением производственных заданий по станкам или цехам, если вас интересует, как оптимально распределить сотрудников фирмы для работы с различными клиентами, вам может очень пригодиться задача о назначениях. Транспортная задача имеет целью минимизацию транспортных издержек (или максимизацию прибыли) при перевозках однотипных грузов (контейнеров, вагонов, сыпучих или жидких грузов в однотипных цистернах, грузовиках и т.п.) от нескольких поставщиков (с различных складов), расположенных в разных местах, к нескольким потребителям. При этом в транспортной задаче принимают в расчет только переменные транспортные издержки, т.е. считают, что суммарные издержки пропорциональны количеству перевезенных единиц груза. Задача о назначениях используется для количественного анализа ситуаций, когда менеджер должен назначить рабочих для выполнения различных производственных операций, распределить ряд производственных заданий по различным машинам (которые могут эти задания выполнить с различной эффективностью) или решить, какого торгового агента в какую область послать для продвижения продукции фирмы. Это распределение или назначение должно быть сделано из соображений либо наибольшей эффективности, либо наименьших затрат. Транспортная задача и задача о назначениях - это частные задачи линейного программирования. Для них в принципе могут быть использованы общие методы решения ЛП-задач (например, симплекс-метод). Однако даже для относительно простых транспортных задач и задач о назначениях характерно большое число переменных решения. Для транспортных задач, имеющих практическое значение, применение таких общих методов может стать неэффективным. Вместе с тем особенности структуры данных и ограничений транспортной задачи обусловливают возможность применения специальных высокоэффективных алгоритмов ее решения. Рассмотрим простой пример такой задачи. |