Исследование полученного решения оптимизационной задачи

Часто получения оптимального решения задачи оказывается недостаточно. Например, пользователя может интересовать, насколько чувствительным является полученное оптимальное решение к изменению различных параметров исходной модели. Этому способствуют предлагаемые в окне Результаты поиска решения отчеты. Таких отчетов три: отчет по результатам, отчет по устойчивости, отчет по пределам (рис.1). Данное окно появляется после запуска вычислений кнопкой Выполнить из окна Поиск решения.

Рис.1.

Отчет по результатам. Откроем файл «План производства», очистим содержимое изменяемых ячеек В10:D10 и снова запустим Поиск решения. Далее выведем отчет по результатам решения задачи по определению плана выгодного производства, когда прибыль максимальна. Данный отчет выводится на новый рабочий лист «Отчет по результатам» и включает три таблицы (рис. 2).

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

В первой таблице «Целевая ячейка» приводятся исходное и окончательное (оптимальное) значение целевой функции (Итоговая прибыль), которая находится в ячейке Е16 - целевой ячейке.

Во второй таблице «Изменяемые ячейки» приводятся исходные и окончательные значения оптимизируемых переменных x₁, x₂, x₃ (объемов производства видов продукции), которые находятся в ячейках В10:D10.

Третья таблица «Ограничения» содержит информацию об ограничениях. В столбце «Значение» помещены оптимальные значения потребных ресурсов и оптимизируемых переменных.

Столбец «Формула» содержит записи ограничений в форме ссылок на используемые ячейки.

Столбец «Статус» определяет: связанными или несвязанными являются те или иные ограничения. Под «связанными» понимаются ограничения, которые реализуются в решении в виде жестких равенств. Заметим, что Ресурс2 в оптимальном решении используется полностью (без остатка) и поэтому является связанным, т.е. дефицитным.

Столбец «Разница» для ресурсных ограничений определяет остаток используемого ресурса (например, Ресурс2 исчерпан). Для ограничений по оптимизируемым переменным x_i (объемам выпуска продукции) здесь указывается разность между оптимальным значением x_i^* и верхней или нижней границей. Если эта разность равна нулю, тогда объем производства данного вида продукции считается связанным (x₁^* продукции А – по верхней границе «4», x₂^* продукции В – по нижней границе «2»).

Связанность ограничений заставляет обычно исследователя отказаться от дальнейших поисков улучшения целевой функции.

Отчет по устойчивости. Очистим содержимое изменяемых ячеек В10:D10, запустим Поиск решения и выберем Тип отчета – Устойчивость. Отчет по устойчивости состоит из двух таблиц с информацией об изменяемых (оптимизируемых) переменных (Объемах производства) и ограничениях модели (на расходы ресурсов) (рис.3).

Рис.3. Отчет по устойчивости для линейных задач

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

Верхняя таблица содержит информацию об изменяемых ячейках, содержащих значения объемов производства продукции. В столбце «Результирующее значение» указаны их оптимальные значения. Величина показателя «Нормированная (редуцированная) стоимость» определяется как разность между единичной прибылью и оценкой снижения общей прибыли за счет отвлечения ресурсов для производства данного вида продукции, взятой по теневым ценам этих ресурсов:

(Нормир. стоимость продукции А) = (Единичная прибыль от А) – {(Теневая цена Р1) * (норма расхода Р1 на А) + (Теневая цена Р2) * (норма расхода Р2 на А) + (Теневая цена Р3) * (норма расхода Р3 на А)}

Для нашего случая значения нормированной стоимости для каждого вида продукции:

(Нормир. стоимость продукции А) = 60 – (0 · 1 + 12 · 4 + 0 · 6) = 12

(Нормир. стоимость продукции В) = 70 – (0 · 1 + 12 · 6 + 0 · 5) = - 2

(Нормир. стоимость продукции С) = 120 – (0 · 1 + 12 · 10 + 0 · 4) = 0

Значения «Целевого коэффициента» для рассматриваемого примера являются показателями единичной прибыли - от производства единицы продукции данного вида.

В следующих двух столбцах указаны «Допустимое увеличение и уменьшение» целевых коэффициентов (значений единичной прибыли) без изменения найденного оптимального решения. Так, для нашего случая коэффициент c₁, равный 60, может быть увеличен на 30 порядков (до значения, равного 60+10³⁰) или уменьшен на 12 единиц (до значения 48) без изменения найденного решения (при сохранении без изменений всех остальных переменных) – оптимальных значений объемов производства.

Проверьте это утверждение, повторно решив задачу для любого значения коэффициента c₁ в диапазоне [48, (60+10³⁰)]. Поскольку 60+10³⁰ является бесконечно большим числом, то следует говорить о наличии лишь ограничения снизу на значение целевого коэффициента. Аналогично определяются диапазоны возможного изменения целевых коэффициентов при остальных переменных (c₂ и c₃).

Вторая таблица содержит информацию по ограничениям. Столбец «Результирующее значение» содержит данные о потребностях в ресурсах для оптимального решения. Во 2-м столбце указаны «Теневые цены» на используемые виды ресурсов. Далее – ограничения на объем используемых ресурсов (сколько их имеется в наличии). Последние два столбца содержат данные о возможном изменении объемов имеющихся ресурсов.

Параметр «Теневая цена» позволяет выяснить, как изменится значение целевой функции, если ослабить то или иное ограничение. Например, необходимо определить, как увеличится прибыль, если имеющийся объем ресурса Р2 был бы увеличен. Теневая цена ограничения выражает величину изменения целевой функции при увеличении имеющегося объема ресурсов данного вида на единицу (при условии, что все остальные переменные не изменятся).

Рассмотрим теневую цену на ресурс Р2, который имеет связанное ограничение (используется полностью). Из отчета по устойчивости (рис.3) видно, что если увеличивать имеющееся количество ресурса Р2 (100) на некоторую величину, находящуюся в пределах от 0 до 28, оптимальное значение целевой функции (максимум Итоговой прибыли) увеличится на 12,0 за каждую единицу увеличения объема ресурса Р2. Если же уменьшить Р2 на некоторую величину в пределах от 0 до 52, то максимум итоговой прибыли уменьшится на 12,0 за каждую единицу уменьшения Р2.

Допустим, решено увеличить имеющийся запас Р2 на 25 ед. (допустимое увеличение составляет 28) и вправе ожидать увеличения максимальной итоговой прибыли на 12 · 25=300, т.е. 1244+300=1544. Это можно проверить при повторном решении модели, внеся изменение в ячейку Е6 =125 (вместо 100) (рис.4).

Рис. 4. Решение, полученное после увеличения имеющегося объема ресурса Р2 на 25 единиц

На рис. 4 видно, что получены новые значения оптимизируемых переменных x₁* =4, x₂* =2, x₃* =9,7, поскольку коррекция одного из ограничений изменила область существования решения.

Необходимо понимать, что для увеличения прибыли на 300 ед. путем увеличения объема связанного ресурса Р2 на 25 ед. надо за каждую его дополнительную единицу платить надбавку, максимальная величина которой равна теневой цене: 300/25=12. Даже заплатив такую максимальную надбавку (хотя реально она должна быть меньше), будет получена та же прибыль, что была до увеличения объема.

Теперь рассмотрим теневые цены на несвязанные ограничения, по которым ресурсы в оптимальном решении используются не полностью (недефицитные ресурсы Р1 и Р3). Теневая цена ресурса Р1 равна 0 при возможном увеличении его объема до бесконечности (допустимое увеличение 1Е+30) или уменьшении в пределах от 0 до 2,8 (допустимое уменьшение). При этом максимальное значение итоговой прибыли не изменится. Это связано с тем, что оптимальное решение оставляет 2,8 ед. ресурса Р1 неиспользованными, и дальнейшее увеличение не может улучшить оптимального решения. Отсюда следует, что можно сократить имеющийся объем Р1 (16) на 2,8 ед., не оказывая влияния на оптимальное решение. Таким же образом можно сократить имеющийся объем Р3 (110) на 47,2 ед. без изменения максимальной итоговой прибыли.

Проверьте последнее утверждение при повторном решении модели, устанавливая в ячейке Е7 значение, равное 110-40=70, далее, значение, равное 110-60=50.

Сохраните таблицу в виде как на рис. 4, задав ей имя «План производства_2».

Отчет по пределам. Очистим содержимое изменяемых ячеек В10:D10 (рис.4), запустим Поиск решения и выберем Тип отчета – Пределы. Получим отчет по пределам как на рис.5.

Этот отчет содержит оптимальные значения целевой функции (прибыли) F _max=1544и независимых переменных (объемов производства) x₁* = 4, x₂* = 2, x₃* = 9,7.

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

Рис.5. Отчет по пределам

При исследовании результатов решения оптимизационных задач необходимо учитывать следующие закономерности.

- Если результирующие значения оптимизируемых переменных находятся внутри интервала их ограничений (как в последнем примере x₃*, x₄*), они всегда имеют равный нулю показатель нормированной стоимости.

- При решении задач максимизации переменные, оптимальные значения которых совпадают с нижней границей (x₁*, x₂*), имеют отрицательную или равную нулю нормированную стоимость;

переменные, оптимальные значения которых совпадают с верхней границей (x₁* из 1-го примера x₁* =4), имеют положительную или равную нулю нормированную стоимость.

При решении задач минимизации все наоборот.

- Теневые цены ресурсов определяют прирост (в задаче минимизации - сокращение) целевой функции при увеличении (в задаче минимизации – при уменьшении) на единицу имеющегося объема дефицитных ресурсов (Р2, Р3).

- Недефицитные ресурсы (Р1) имеют нулевую теневую цену.

- Виды продукции, имеющие отрицательную нормированную стоимость (А, В), являются неэффективными для производства.

- Одновременное изменение нескольких коэффициентов целевой функции (на рис.2 значения единичной прибыли 60, 70, 120, 127) при сохранении найденного оптимального решения осуществимо при выполнении следующего условия:

Σ k_j ≤ 1,

где: k_j = Δc_j / I_j, если Δc_j ≥ 0, k_j = -Δc_j / D_j, если Δc_j ≤ 0,

Δc_j – планируемое изменение коэффициента целевой функции c_j для переменной x _j,

I_j, D_j, – допустимые увеличение и уменьшение коэффициента c_j в соответствии с отчетом по устойчивости.

Приложение C

Решение транспортной задачи в EXCEL (Поиск решения)

Исходные данные транспортной задачи:

- внутри таблицы – удельные затраты на перевозку единицы груза (c_ij),

- слева – мощности поставщиков (a_i),

- сверху – мощности потребителей (b_j).

Мощности поставщиков (ai)	Мощности потребителей (bj)

Найти оптимальный план закрепления поставщиков за потребителями (x_ij).

Суммарные запасы больше суммарных потребностей (задача открытая):

Решение:

1. Создайте форму для ввода условий задачи. Так как задача открытая, то необходимо ввести фиктивного поставщика с мощностью a₅=165-120=45, а в 5-м столбце записать нулевые тарифы.

Рисунок 1. Создание формы для ввода исходных данных

2. В ячейку С14 введите формулу для вычисления значения целевой функции: =СУММПРОИЗВ (В2:F5;В10:F12).

3. В ячейку A2 записать формулу суммирования значений четырех изменяемых ячеек второй строки: =СУММ(В2:F2). Копировать формулу в ячейки А3:А5 (ячейки наличия груза).

4. Аналогично по потребителям: в ячейку В6 суммировать значения изменяемых ячеек первого потребителя =СУММ(В2:В5). Скопировать формулу в ячейки С6:Е6 (ячейки мощностей потребителей). Форма примет вид, показанный на рисунке.

Рис.2. Готовая форма для Поиска решения

5. Перейти в режим Поиск решения (Данные – Поиск решения). Установить параметры как на рисунке:

Все грузы должны быть перевезены т.е. А2:А5 = А9:А12.

Все потребности должны быть удовлетворены, т.е. В6:F6 = В8:F8.

6. Нажать кнопку Параметры и в открывшемся окне установить неотрицательные значения и линейная модель, ОК, Выполнить, ОК.

Результаты расчетов оптимального плана перевозок отражен в «Матрице перевозок (изменяемые ячейки)» (рис.3):

Дата добавления: 2014-12-07