Решение задач линейного программирования и анализ чувствительности с помощью MS Excel

Итак, решение математической модели получено. Ну и что с ним дальше делать — бегом бежать внедрять в жизнь? Нет, бежать пока рано. Надо вспомнить, что мы получили решение только для модели реальной проблемы, а не решение самой проблемы. В процессе построения модели были сделаны различные допущения, упрощающие реальную ситуацию, в результате чего мы смогли ее формализовать. Зависимости, зафиксированные в модели, только приближенно отображают реальные зависимости между факторами и переменными решения и целью. Наши знания факторов, влияющих на цель, зияют пробелами — значения многих параметров модели мы знаем только приближенно. Ну, а если реальные значения параметров хотя бы немного отличаются от тех, которые заложены в модели, то насколько может измениться решение и изменится ли вообще?

На эти и подобные вопросы должен дать ответы анализ полученного решения. На «научном» языке этот анализ называется анализом чувствительности решения. Он проводится после получения оптимального решения математической модели и дает важную информацию, которую можно и нужно использовать при принятии решения в реальной ситуации.

Анализ чувствительности должен дать ответы на следующие вопросы.

♦ В каких пределах могут изменяться параметры модели так, чтобы сохранилось полученное решение?

♦ Какие ограничения связанные (т.е. лимитируют (сдерживают) целевую функцию), а какие ограничения не влияют на решение?

♦ Если изменить значения правых частей связанных ограничений, то насколько может измениться значение целевой функции?

♦ Если значение какой-то переменной решения равно нулю, то при каких условиях она может принять положительное значение? (Вопрос весьма актуален для моделей производства.)

Средство Поиск решения может генерировать три вида отчетов: отчет по результатам, отчет по устойчивости и отчет по пределам. Все перечисленные виды отчетов и именно в той форме, которая показана ниже на рис. 8—10, Поиск решения создает только для линейных моделей. Для целочисленных моделей недоступны отчеты по устойчивости и по пределам, а для нелинейных моделей отчет по устойчивости имеет другой вид. Рассмотрим применение отчетов для выполнения анализа чувствительности линейных моделей.

На рис. 7 показан рабочий лист Excel с найденным решением математической модели, а на рис. 8—10 — отчеты, сгенерированные средством Поиск решения.

Рис. 7. Решение линейной модели для завода «Олимп»

Рис. 8. Отчет по результатам

Отчет по результатам полезен для анализа чувствительности только тем, что там явно указано, какие ограничения связанные и какие несвязанные. Эти данные приведены в отчете в таблице Ограничения в столбце Статус. В столбце Разница той же таблицы показаны значения разностей между левыми и правыми частями ограничений.

Рис. 9. Отчет по устойчивости

Более существенен для анализа чувствительности отчет по устойчивости. В таблице Изменяемые ячейки этого отчета приведена информация о значениях изменяемых ячеек:

♦ адреса изменяемых ячеек;

♦ их имена (созданные заранее или составленные из заголовков строк и столбцов, на пересечении которых находятся изменяемые ячейки); если имен нет, то это поле остается пустым;

♦ значения переменных в этих ячейках, найденные средством Поиск решения;

♦ нормированная стоимость — это неудачный перевод термина «reduced cost», который можно перевести как «цена, которая уменьшает целевую функцию». Она показывает, как изменится оптимальное значение целевой функции при выпуске продукции, которой нет в оптимальном плане. В нашем случае оптимальный план предполагает выпуск обоих видов красок, поэтому их нормированная стоимость равна нулю. Если бы оптимальное значение какой-либо из неизвестных было равно нулю (x_i = 0), а нормированная стоимость равнялась бы, например, –3, то принудительный выпуск 2-х единиц этой переменной x_i (т. е. добавление нового ограничения x_i ≥ 2) привел бы к изменению (уменьшению) целевой функции на 2*(–3) = –6 единиц. Отметим, что из равенства нулю оптимального значения неизвестной не следует автоматически, что ее нормированная стоимость будет отлична от нуля;

♦ целевой коэффициент — коэффициент, стоящий при данной изменяемой переменной в формуле целевой функции;

♦ значения в столбцах Допустимое увеличение и Допустимое уменьшение показывают, в каких пределах может изменяться целевой коэффициент при условии, что найденные значения переменных останутся неизменными.

В таблице Ограничения приведена информация об ограничениях:

♦ адреса ячеек, на значения которых наложены ограничения;

♦ их имена (созданные заранее или составленные из заголовков строк и столбцов, на пересечении которых находятся изменяемые ячейки); если имен нет, то это поле остается пустым;

♦ значения в этих ячейках, найденные средством Поиск решения;

♦ теневая цена показывает, насколько изменится значение целевой функции, если на единицу изменится значение правой части данного ограничения; теневая цена отлична от нуля только тогда, когда данное ограничение в оптимальном решении является связанным (и решение не вырождено);

♦ значения правых частей ограничений;

♦ значения в столбцах Допустимое увеличение и Допустимое уменьшение показывают пределы изменения правой части ограничения, в которых действует приведенное значение теневой цены данного ограничения¹.

Наиболее важными данными для анализа чувствительности в этом отчете являются нормированные стоимости и теневые цены, применение которых рассмотрим ниже. Важно отметить, что значения теневых цен подсчитаны в предположении, что изменяется значение правой части только одного ограничения при условии постоянства всех остальных параметров модели.

В отчете по пределам показано, в каких пределах с учетом всех ограничений могут изменяться переменные (значения в столбцах Верхний предел и Нижний предел) и какие при этом значения будет принимать целевая функция (значения в столбцах Целевой результат). Отметим, что если на значения переменной не налагаются явные ограничения, задающие ее верхнюю (или нижнюю) границу, то в столбцах Верхний предел и Целевой результат (или Нижний предел и Целевой результат) для этой переменной будут стоять значения ошибки #Н/Д.

Рис. 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. В этом решении х1 = 350, х2 = 150 и z = 1 075 000. Новым лимитирующим ограничением стало первое ограничение, задающее предельный объем производства. Нам повезло, что изменение только одного параметра модели (значения правой части ограничения по сырью 2) уже привело к решению (производственному плану), где производственные мощности завода задействованы полностью. В общем случае, если действительно есть необходимость задействовать все мощности производства, скорее всего, пришлось бы проверять другие лимитирующие ограничения и пробовать изменять их правые части.

Рис. 11. Новое оптимальное решение

Итак, что мы имеем? Оптимальным производственным планом будет производство 350 тонн краски типа А и 150 тонн краски типа Б. Однако, чтобы выполнить такой план, надо увеличить месячные запасы сырья 2 на 6,5 тонн, а месячные запасы сырья 1 и сырья 3 можно уменьшить на 17,5 и 0,5 тонн соответственно. Это уже не совсем очевидный результат. (Но и этот результат можно было получить другим способом, поскольку нетрудно подсчитать необходимые запасы сырья для производства 350 тонн краски А и 150 тонн краски Б, — однако до этого еще надо было бы додуматься.) Затем надо подсчитать, на сколько увеличится (и увеличится ли) себестоимость краски, если докупить дополнительные объемы сырья 2, так как возрастут расходы по крайней мере на хранение сырья. Это может повлиять на удельную прибыль краски, т. е. могут измениться значения коэффициентов при переменных в формуле целевой функции. А если это произойдет, то все вычисления надо начинать сначала. Кроме того, надо вспомнить, что значения этих коэффициентов известны нам только приближенно. Поэтому далее следует рассмотреть влияние коэффициентов при переменных в формуле целевой функции.

Напомним, что в отчете по устойчивости эти коэффициенты названы целевыми коэффициентами, мы также для краткости будем использовать это название. (Кроме того, как показано на рис. 7, этим коэффициентам с самого начала присвоены имена с1 и с2.) В последнем отчете по устойчивости (рис. 12) в таблице Изменяемые ячейки в столбцах Допустимое увеличение и Допустимое уменьшение приведены значения, на которые могут изменяться целевые коэффициенты при условии сохранения решения. Сохранение решения здесь означает сохранение значений переменных решения, но значение целевой функции может изменяться. Однако следует учесть, что эти числа имеют смысл при выполнении дополнительного условия, а именно, что целевые коэффициенты изменяются по одному, а не совместно. Таким образом, на основании данных отчета по устойчивости можно утверждать, что если коэффициент с1 при переменной х1 будет изменяться в пределах от 0 до 2500 или коэффициент с2 при переменной х2 будет изменяться в пределах от 2000 до бесконечности, то значения этих переменных останутся прежними. Но каким будет решение, если изменятся оба целевых коэффициента? Отчет по устойчивости ответа на этот вопрос не дает. Ну, а если нет готового ответа, его следует найти самому. Что для этого надо сделать? Правильно, надо решить еще несколько задач.

В нашем примере целевой коэффициент с1 при переменной х1 может изменяться в пределах 1500 до 2300, а целевой коэффициент с2 при переменной х2 — в пределах от 2100 до 3000. Хотя эти пределы не перекрывают крайние значения, которые показаны в отчете по устойчивости, необходимо все-таки проверить решение при совместном изменении значений целевых коэффициентов. Здравый смысл подсказывает, что решение останется прежним до тех пор, пока целевой коэффициент с1, будет меньше целевого коэффициента с2. Поэтому проверим решение, если коэффициент с1 будет равен 2300, а коэффициент с2 будет равен 2100. Записываем эти числа в ячейки В8 и С8 соответственно и запускаем Поиск решения, ничего не меняя в его установках. Получим новое решение, показанное на рис. 13.

Рис. 12. Отчет по устойчивости для последнего решения

Рис. 13. Решение при крайних значениях целевых коэффициентов

Как можно было и предположить, если удельная прибыль краски Б меньше удельной прибыли краски А, то производить краску Б невыгодно (значение 1,4Е-10 можно считать нулем). Отметим, что прибыль при данном решении больше, чем в предыдущем решении (1 150 тыс. руб. против 1 075 тыс. руб.), а сырья всех видов потребуется меньше (ни одно ограничение по сырью не является лимитирующим). И все-таки, если для поддержания ассортимента продукции необходимо производить краску Б, то насколько надо увеличить ее удельную прибыль, чтобы ее производство стало выгодным? Здравый смысл опять подсказывает, что надо хотя бы сравнять удельные стоимости обоих типов краски. На это же указывает число 200 в столбце Допустимое увеличение и в строке х2 таблицы Изменяемые ячейки отчета по устойчивости для данного решения (рис. 14).