Решение задач линейного программирования на примере оптимизации и транспортной задачи, анализ чувствительности с помощью ms excel.
 Скачать 1.06 Mb.
|
|
СУММПРОИЗВ. Даже если это простые ограничения типах, которые здесь представляются как 0*x1 + х ограничение 2 на рис. 1). Обратите внимание на то, что ограничения сгруппированы по типу неравенств — сначала идут ограничения типа <=, а затем типа >=. Конечно, порядок представления этих групп несущественен. Существенно само наличие групп однотипных ограничений, что позволит в дальнейшем задавать их в средстве Поиск решения не по отдельности, а целой группой. Знаки неравенств в диапазоне ЕЕ вставлены только для пояснения ограничений, средство Поиск решения их не использует. Зато средство Поиск решения использует заголовки строк, содержащих ограничения (использует в своих отчетах, как показано далее. Поэтому рекомендуется давать более содержательные заголовки, даже чем те, что показаны на рис. 1 в ячейках А11:А17. Например, такие Ограничение на объем производства, Маркетинговое ограничение или Ограничение, не знаю, откуда оно взялось С другой стороны, заголовки не являются обязательным элементом модели представления задачи в Excel — средство Поиск решения прекрасно вычислит результат и без них. Заголовки полезны для документирования модели. Если вы не знаете, как отобразить на рабочем листе Excel формулы, а не значения (как на рис. 2), то это делается так. Надо выполнить команду Сервис->Параметры ив открывшемся диалоговом окне Параметры на вкладке Вид установить флажок формулы. Отображение формул может оказаться полезным, полезно при отладке модели. В Excel 2007 и выше отображение формул осуществляется через меню Параметры Дополнительно, выбирая для данного листа Показывать формулы, а не их значения Теперь, когда модель представления задачи в Excel построена и проверена, пришло время ее решить. Для этого используем надстройку Excel Поиск решения. Если вменю Сервис вы не находите одноименной команды, то это означает, что данная надстройка не подключена к Excel. Для ее подключения выполните команду Сервис->Надстройки ив открывшемся диалоговом окне Надстройки в списке Доступные надстройки установите флажок Поиск решения. Для Excel 2007 и выше Поиск решения находится во вкладке Данные->Анализ . Подключение осуществляется через меню Параметры Надстройки. Выбираем в списке Надстройки Excel и нажимаем кнопку Перейти 6 Покажем общую схему применения средства Поиск решения для решения задач линейной оптимизации Сначала надо познакомиться с терминологией, относящейся к средству Поиск решения, те. надо знать, как там называют переменные решения, целевую функцию и ограничения. Так вот, ♦ переменные решения, точнее, ячейки, содержащие значения этих переменных, называются изменяемыми ячейками, ♦ ячейка, содержащая значение целевой функции, называется целевой ячейкой, ♦ ограничения таки будут называться ограничениями. Схема применения средства Поиск решения выглядит так Пусть на рабочем листе Excel уже создана модель представления задачи в Excel для линейной оптимизации. 2. После проверки и отладки модели переходим к этапу оптимизации, выбрав команду Поиск решения вменю Сервис. 3. В открывшемся диалоговом окне Поиск решения укажите данные, необходимые для поиска оптимального решения рис. 3). Рис. 3. Задание параметров для поиска решения • В поле Установить целевую ячейку вводится адрес ячейки, содержащей значение целевой функции. Для нашей модели в это поле следует ввести D8, но лучше щелкнуть указателем мыши на этой ячейке, чтобы ввести ее адрес автоматически. • Параметры области Равной диалогового окна Поиск решения позволяют задать тип оптимизации. В данном случае необходимо максимизировать значение целевой функции. Для этого нужно щелкнуть на переключателе максимальному значению. • Поле Изменяя ячейки позволяет указать ячейки, в которых содержатся переменные модели в данном случае это диапазон В4:С4. 4. Далее необходимо задать ограничения. Щелчок на кнопке Добавить открывает диалоговое окно Добавление ограничения, показанное на рис. 4, • В нашем примере в поле Ссылка на ячейку вводим или указываем на рабочем листе ссылку на диапазон D11:D15, в соседнем поле оставляем знак неравенства <=, а в поле Ограничение вводим или указываем на рабочем листе ссылку на диапазон F11:F15. 7 • Щелкаем на кнопке Добавить и вводим вторую группу ограничений в поле Ссылка на ячейку вводим D16:D17, в соседнем раскрывающемся списке выбираем знак неравенства >=, а в поле Ограничение вводим F16:F17. Затем щелкаем на кнопке ОК и возвращаемся в диалоговое окно Поиск решения. Рис. 4. Задание ограничений 5. После задания ограничений при необходимости в диалоговом окне Параметры поиска решения, которое открывается после щелчка на кнопке Параметры диалогового окна Поиск решения, следует задать дополнительные условия для поиска решения. • Параметры Максимальное время, Предельное число итераций, Относительная погрешность, Допустимое отклонение и Сходимость можно оставить без изменений, тем более что параметр Допустимое отклонение имеет отношение к целочисленным моделям, а параметр Сходимость — к нелинейным моделям. • В данном примере, поскольку мы работаем с линейной моделью, надо установить флажок Линейная модель рис. 5). • Если в модели условия не отрицательности налагаются на все переменные, следует установить флажок Неотрицательные значения. В нашем примере условие не отрицательности налагается только на переменную поэтому этот флажок мы не устанавливаем. • Флажок Автоматическое масштабирование рекомендуем устанавливать всегда. • Если хотите проследить каждую итерацию процесса вычисления, установите флажок Показывать результаты итераций. Если хотите сразу получить результат вычислений без подглядывания в вычислительную кухню, не устанавливайте этот флажок. • Переключатели, расположенные в областях Оценки, Разности, Метод поиска, предназначены для нелинейных моделей. Поэтому сейчас мы их оставляем без внимания. • Щелчок на кнопке ОК возвращает в диалоговое окно Поиск решения. Рис. 5. Диалоговое окно Параметры поиска решения 6. После задания необходимых данных (указания ячейки, содержащей формулу для вычисления целевой функции, ячеек, в которых находятся переменные, и задания ограничений) щелкните на кнопке Выполнить. 7. Средство Поиск решения выполняет оптимизацию. В процессе вычислений в строке состояния отображаются число итераций и значения целевой функции при переборе множества допустимых решений задачи. Эта информация позволяет следить, как продвигается процесс оптимизации больших моделей, где он может длиться достаточно долго. 8 8. После окончания работы Поиск решения выведет на экран диалоговое окно Результаты поиска решения рис. 6), в котором можно указать, обновить ли исходную модель (те. занести ли в ячейки значения оптимального решения) и создавать ли отчет. Рис. 6. Успешное завершение решения задачи оптимизации Диалоговое окно Результаты поиска решения сообщает о завершении поиска (рис. 6). Если оптимальное решение найдено, в диалоговом окне Результаты поиска решения должно отобразиться сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если получено такое сообщение, можно или сохранить найденное решение, выбрав соответствующий параметр, или отбросить его, выбрав параметр Восстановить исходные значения. В результате ячейкам переменных будут возвращены значения, которые в них находились до запуска программы Поиск решения. Существует возможность также получить три типа отчетов о решении. Каждый отчет выводится на новый лист рабочей книги. В нашем примере решение найдено, оно показано на рис. 6: надо производить 257,14 т краски Аи т краски Б, при этом будет получена прибыль в размере 889 285,17 руб. В диалоговом окне Результаты поиска решения мы также указали, что надо создать отчеты. IV. Теперь покажем, что делать дальше с полученным компьютерным решением, и как на его основе найти настоящее решение задачи. Итак, решение математической модели получено. Ну и что с ним дальше делать — бегом бежать внедрять в жизнь Нет, бежать покарано. Надо вспомнить, что мы получили решение только для модели реальной задачи, а не решение самой задачи. В процессе построения модели были сделаны различные допущения, упрощающие реальную ситуацию, в результате чего мы смогли ее формализовать. Зависимости, зафиксированные в модели, только приближенно отображают реальные зависимости между факторами и переменными решения и целью. Наши знания факторов, влияющих нацель, зияют пробелами — значения многих параметров модели мы знаем только приближенно. Ну, а если реальные значения параметров хотя бы немного отличаются от тех, которые заложены в модели, то насколько может измениться решение и изменится ли вообще На эти и подобные вопросы должен дать ответы анализ полученного решения. На научном языке этот анализ называется анализом чувствительности решения. Он проводится после получения оптимального решения математической модели и дает важную информацию, которую можно и нужно использовать при принятии решения в реальной ситуации. Анализ чувствительности должен дать ответы наследующие вопросы. ♦ В каких пределах могут изменяться параметры модели так, чтобы сохранилось полученное решение ♦ Какие ограничения связанные (те. лимитируют (сдерживают) целевую функцию, а какие ограничения не влияют на решение ♦ Если изменить значения правых частей связанных ограничений, то насколько может измениться значение целевой функции ♦ Если значение какой-то переменной решения равно нулю, то при каких условиях она может принять положительное значение (Вопрос весьма актуален для моделей производства) Средство Поиск решения может генерировать три вида отчетов отчет по результатам, отчет по устойчивости и отчет по пределам. Все перечисленные виды отчетов и именно в той форме, которая показана ниже на рис. 8—10, Поиск решения создает только для линейных моделей. Для целочисленных моделей недоступны отчеты по устойчивости и по пределам, а для нелинейных моделей отчет по устойчивости имеет другой вид. Рассмотрим применение отчетов для выполнения анализа чувствительности линейных моделей. На рис. 7 показан рабочий лист Excel с найденным решением математической модели, а на рис. 8—10 — отчеты, сгенерированные средством Поиск решения. 9 Рис. 7. Решение линейной модели для завода Олимп Рис. 8. Отчет по результатам Отчет по результатам полезен для анализа чувствительности только тем, что там явно указано, какие ограничения связанные и какие несвязанные. Эти данные приведены в отчете в таблице Ограничения в столбце Статус. В столбце Разница той же таблицы показаны значения разностей между левыми и правыми частями ограничений. Рис. 9. Отчет по устойчивости Более существенен для анализа чувствительности отчет по устойчивости. В таблице Изменяемые ячейки этого отчета приведена информация о значениях изменяемых ячеек ♦ адреса изменяемых ячеек ♦ их имена (созданные заранее или составленные из заголовков строки столбцов, на пересечении которых находятся изменяемые ячейки если имен нетто это поле остается пустым ♦ значения переменных в этих ячейках, найденные средством Поиск решения ♦ нормированная стоимость — это неудачный перевод термина «reduced cost», который можно перевести как цена, которая уменьшает целевую функцию. Она показывает, как изменится оптимальное значение целевой функции при выпуске продукции, которой нет в оптимальном плане. В нашем случае оптимальный план предполагает выпуск обоих видов красок, поэтому их нормированная стоимость равна нулю. Если бы оптимальное значение какой-либо из неизвестных было равно нулю (x i = 0), а нормированная стоимость равнялась бы, например, –3, то принудительный выпуск х единиц этой переменной x i (те. добавление нового ограничения x i ≥ 2) привел бык изменению (уменьшению) целевой функции на 2*(–3) = –6 единиц. Отметим, что из равенства нулю оптимального значения неизвестной не следует автоматически, что ее нормированная стоимость будет отлична от нуля ♦ целевой коэффициент — коэффициент, стоящий приданной изменяемой переменной в формуле целевой функции 10 ♦ значения в столбцах Допустимое увеличение и Допустимое уменьшение показывают, в каких пределах может изменяться целевой коэффициент при условии, что найденные значения переменных останутся неизменными. В таблице Ограничения приведена информация об ограничениях ♦ адреса ячеек, назначения которых наложены ограничения ♦ их имена (созданные заранее или составленные из заголовков строки столбцов, на пересечении которых находятся изменяемые ячейки если имен нетто это поле остается пустым ♦ значения в этих ячейках, найденные средством Поиск решения ♦ теневая цена показывает, насколько изменится значение целевой функции, если на единицу изменится значение правой части данного ограничения теневая цена отлична от нуля только тогда, когда данное ограничение в оптимальном решении является связанными решение не вырождено ♦ значения правых частей ограничений ♦ значения в столбцах Допустимое увеличение и Допустимое уменьшение показывают пределы изменения правой части ограничения, в которых действует приведенное значение теневой цены данного ограничения 1 Наиболее важными данными для анализа чувствительности в этом отчете являются нормированные стоимости и теневые цены, применение которых рассмотрим ниже. Важно отметить, что значения теневых цен подсчитаны в предположении, что изменяется значение правой части только одного ограничения при условии постоянства всех остальных параметров модели. В отчете по пределам показано, в каких пределах с учетом всех ограничений могут изменяться переменные значения в столбцах Верхний предел и Нижний предел) и какие при этом значения будет принимать целевая функция значения в столбцах Целевой результат. Отметим, что если назначения переменной не налагаются явные ограничения, задающие ее верхнюю (или нижнюю) границу, тов столбцах Верхний предел и Целевой результат или Нижний предел и Целевой результат) для этой переменной будут стоять значения ошибки #Н/Д. Рис. 10. Отчет по пределам Начнем анализ чувствительности для нашего примера. Во-первых, заметим, что переменные решения нулевые значения не принимают, и это облегчает нашу жизнь. Рассмотрим ограничения. Первое ограничение, задающее предельный объем производства, лимитирующим (связанным) не является. Отсюда следует простой вывод, что такой производственный план мощности завода задействует не в полной мере. Это большой минус данного плана. Посмотрим, что сдерживает объемы производства. Лимитирующими являются второе маркетинговое ограничение и ограничение по сырью 2 (на это указывает отчет по результатами ненулевые значения теневых цен для этих ограничений в отчете по устойчивости. Влиять на маркетинговое ограничение трудно, поскольку требования отдела маркетинга установлены из рыночных условий. Да это и не имеет особого смысла — чтобы полностью загрузить мощности производства, надо запланировать еще почти 93 тонны краски, а на такое увеличение производства краски типа Б добро никто не даст, так как даже объем в 150 тонн трудно продать. Другое лимитирующее ограничение определяется наличием на складе запаса сырья 2. Разберемся с этим параметром. Взглянем на теневую цену этого ограничения, она равна 28 571,43. Это означает, что изменение на одну единицу величины правой части данного ограничения (те. изменение величины запаса сырья 2 на 1 тонну) приведет к изменению на 28 571,43 руб. величины прибыли (значения целевой функции. Очевидно, что в данном случае при увеличении значения правой части ограничения значение целевой функции будет возрастать, а приуменьшении убывать. Насколько же нужно увеличить запас сырья 2, чтобы полностью загрузить все производственные мощности К сожалению, отчет по устойчивости прямого ответа на этот вопрос не дает. Посмотрим на число в столбце Допустимое увеличение для этого ограничения. Оно равно 6,5. Это значит, что, увеличивая значение правой части ограничения до величины 36,5, мы остаемся в рамках прежнего решения — значения переменных и целевой функции, конечно, будут изменяться, но лимитирующими и не лимитирующими останутся прежние ограничения. Если же значение правой части ограничения будет равно или превысит величину 36,5, тов качестве лимитирующего в игру вступит другое ограничение, которое на данный момент не является лимитирующим. Чтобы узнать, что же получится при изменении правой части пятого ограничения до величины 36,5, надо опять запускать Поиск решения. Итак, вносим в ячейку F14 значение 36,5 и выбираем команду Сервис->Поиск решения. В диалоговом окне Поиск решения ничего менять не надо (средство Поиск решения сохраняет все установки своего предыдущего использования, можно сразу щелкнуть на кнопке Выполнить. Не забудьте также задать создание отчетов по результатам нового поиска. Новое решение показано на рис. 11. В этом решении х 350, хи. Новым лимитирующим ограничением стало первое ограничение, задающее предельный объем производства. Нам повезло, что изменение только одного параметра модели (значения правой части ограничения по сырью 2) уже привело к решению (производственному плану, где производственные мощности завода задействованы полностью. В общем случае, если действительно есть необходимость задействовать все мощности производства, скорее всего, пришлось бы проверять другие лимитирующие ограничения и пробовать изменять их правые части. Значения Ев столбце Допустимое увеличение или Допустимое уменьшение) таблиц Изменяемые ячейки и Ограничения показывают, что допускается неограниченное возрастание (или убывание) значения соответственно целевого коэффициента или правой части ограничения. 11 Рис. 11. Новое оптимальное решение Итак, что мы имеем Оптимальным производственным планом будет производство 350 тонн краски типа Аи тонн краски типа Б. Однако, чтобы выполнить такой план, надо увеличить месячные запасы сырья 2 на 6,5 тонна месячные запасы сырья 1 и сырья 3 можно уменьшить на 17,5 и 0,5 тонн соответственно. Это уже не совсем очевидный результат. (Но и этот результат можно было получить другим способом, поскольку нетрудно подсчитать необходимые запасы сырья для производства 350 тонн краски Аи тонн краски Б, — однако до этого еще надо было бы додуматься) Затем надо подсчитать, насколько увеличится (и увеличится ли) себестоимость краски, если докупить дополнительные объемы сырья 2, так как возрастут расходы, по крайней мерена хранение сырья. Это может повлиять на удельную прибыль краски, те. могут измениться значения коэффициентов при переменных в формуле целевой функции. А если это произойдет, то все вычисления надо начинать сначала. Кроме того, надо вспомнить, что значения этих коэффициентов известны нам только приближенно. Поэтому далее следует рассмотреть влияние коэффициентов при переменных в формуле целевой функции. Напомним, что в отчете по устойчивости эти коэффициенты названы целевыми коэффициентами, мы также для краткости будем использовать это название. (Кроме того, как показано на рис. 7, этим коэффициентам с самого начала присвоены имена си с) В последнем отчете по устойчивости (рис. 12) в таблице Изменяемые ячейки в столбцах Допустимое увеличение и Допустимое уменьшение приведены значения, на которые могут изменяться целевые коэффициенты при условии сохранения решения. Сохранение решения здесь означает сохранение значений переменных решения, но значение целевой функции может изменяться. Однако следует учесть, что эти числа имеют смысл при выполнении дополнительного условия, а именно, что целевые коэффициенты изменяются по одному, а не совместно. Таким образом, на основании данных отчета по устойчивости можно утверждать, что если коэффициент с1при переменной х1 будет изменяться в пределах от 0 доили коэффициент с при переменной х2будет изменяться в пределах от 2000 до бесконечности, то значения этих переменных останутся прежними. Но каким будет решение, если изменятся оба целевых коэффициента Отчет по устойчивости ответа на этот вопрос не дает. Ну, а если нет готового ответа, его следует найти самому. Что для этого надо сделать Правильно, надо решить еще несколько задач. Рис. 12. Отчет по устойчивости для последнего решения В нашем примере целевой коэффициент с1при переменной х1может изменяться в пределах 1500 до 2300, а целевой коэффициент с2 при переменной х в пределах от 2100 до 3000. Хотя эти пределы не перекрывают крайние значения, которые показаны в отчете по устойчивости, необходимо все-таки проверить решение при совместном изменении значений целевых коэффициентов. Здравый смысл подсказывает, что решение останется прежним до тех пор, пока целевой коэффициент сбудет меньше целевого коэффициента с2. Поэтому проверим решение, если коэффициент сбудет равен 2300, а коэффициент сбудет равен 2100. Записываем эти числа в ячейки В и С соответственно и запускаем Поиск решения, ничего не меняя в его установках. Получим новое решение, показанное на рис. 13. 12 Рис. 13. Решение при крайних значениях целевых коэффициентов Как можно было и предположить, если удельная прибыль краски Б меньше удельной прибыли краски А, то производить краску Б невыгодно (значение Е можно считать нулем. Отметим, что прибыль приданном решении больше, чем в предыдущем решении (1 150 тыс. руб. против 1 075 тыс. руб, а сырья всех видов потребуется меньше (ни одно ограничение по сырью не является лимитирующим. И все-таки, если для поддержания ассортимента продукции необходимо производить краску Б, то насколько надо увеличить ее удельную прибыль, чтобы ее производство стало выгодным Здравый смысл опять подсказывает, что надо хотя бы сравнять удельные стоимости обоих типов краски. На это же указывает число 200 в столбце Допустимое увеличение ив строке х таблицы Изменяемые ячейки отчета по устойчивости для данного решения (рис. 14). Рис. 14. Отчет по устойчивости для решения при крайних значениях целевых коэффициентов Если значения удельных прибылей равны, то получим случай множественных альтернативных оптимальных решений задачи линейной оптимизации любая пара неотрицательных чисел хи х2таких, что их сумма равна 500 их ограничения должны выполняться, будет решением данной задачи, при этом значения целевой функции для любых таких решений будут одинаковыми. Чтобы убедиться в этом, введите в ячейки В и С одинаковые значения, например 2300. Затем в ячейки В и С введите числа, удовлетворяющие перечисленным выше условиями запустите Поиск решения. Наверняка вы получите решение с введенными вами значениями переменных. Если же в ячейки В и С вы введете произвольные числа в качестве начальных значений для переменных хи х2 то получите либо решение хи х 0 (рис. 15), либо решение хи х 150 (рис. 16). Это так называемые крайние решения. Других решений, хотя их существует бесконечно много, вы не получите. Рис. 15. Решение, предлагающее отказаться от краски Б 13 На практике при решении задач линейной оптимизации множественные оптимальные решения встречаются относительно редко. Скорее, эта ситуация может проявиться при проведении анализа чувствительности, как в нашем примере. Признак того, что приданном решении существуют другие альтернативные решения, опять дает отчет по устойчивости. Если в таблице Изменяемые ячейки в столбцах Допустимое увеличение и Допустимое уменьшение для некоторых переменных присутствуют нули, то это и является признаком того, что существуют альтернативные решения. Например, на рис. 17 показан отчет по устойчивости для нашей задачи, когда целевые коэффициенты равны 2300, ахи х 150. Как видите, в столбцах Допустимое увеличение и Допустимое уменьшение таблицы Изменяемые ячейки действительно присутствуют нулевые значения. В других отчетах, показанных выше, нулей в этих столбцах вы не найдете, поскольку там множественных альтернативных решений не было. Рис. 16. Альтернативное решение, сохраняющее производство краски Б Если некоторые переменные принимают нулевые значения, то еще одним признаком присутствия альтернативных решений будут нулевые значения нормированных стоимостей для этих переменных. Рис. 17. Отчет по устойчивости в случае множественных решений Пересмотреть все альтернативные решения невозможно, поскольку они составляют бесконечное множество. Что дает наличие альтернативных решений Хорошо это или плохо Плохо, поскольку решений бесконечно много, и надо сделать выбор из бесконечного множества решений. Хорошо — поскольку сточки зрения целевой функции все эти решения равнозначны, можно привлечь дополнительный критерий отбора решений, который изначально не учитывался в модели. Тем самым можно улучшить решение, сделать его более оптимальным, нов соответствии с новым критерием. Например, в нашем примере среди альтернативных решений можно найти такое решение, которое обеспечивает минимальные суммарные запасы сырья при той же величине прибыли. Легко убедиться, что при решении хи х = 0 потребуется 80 тонн всех видов сырья, а при решении х 1 = 350 И 2 |