6.6.4.2. Наличие альтернативных оптимумов

Приёмы получения альтернативных оптимумов⁷ задачи линейного програм­мирования рассмотрим на примере следующей задачи:

На рис. 6.19 дана гра­фическая иллюстрация данной за­дачи. Как видно из графика, пря­мая целевой функции параллельна огра­ни­чению . Задача имеет альтер­нативные оптиму­мы, на графике – это точки от­резка AC.

Рис. 6.19

Для того, чтобы получить вершины множества альтернативных оптимумов задачи линейного программирования средствами Excel, рекомендуется выполнить следующее:

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

• о граничения неотрицательности переменных должны быть в явном виде заданы в поле Ограничения диалогового окна Поиск решения (а не в диалоговом окне Параметры поиска решения, как это рекомендовалось делать ранее). В левой части этих ограничений должны стоять ссылки на дополнительные ячейки, в правой - 0.

Согласно указанным рекомендациям, Excel-лист вышеприведенной задачи должен иметь примерно такой вид, как это показано на рис. 6.20. Используемые зависимости (формулы) показаны на рис. 6.21. Диалоговые окна Поиск решения и Параметры поиска решения представлены на рис. 6.22.

Рис. 6.20

Р ис. 6.21

Рис. 6.22

В результате получено оптимальное решение рассматриваемой задачи (рис. 6.23): (на рис. 6.19 ему соответствует точка A).

Рис. 6.23

На рис. 6.24 представлен Отчёт по результатам, на рис. 6.25 – Отчёт по устойчивости, сгенерированные Excel.

Рис. 6.24

Рис. 6.25

Признак наличия альтернативных оптимумов: в разделе Изменяемые ячейки Отчета по устойчивости хотя бы для одной из ячеек поле Допустимое увеличение или Допустимое уменьшение равно нулю (см. рис. 6.25).

Из Отчета по результатам (см. рис. 6.24) видим, что оптимум является вер­шиной, так как количество связывающих (активных) ограничений в нём равно двум (количеству переменных исходной задачи).

Переход к другим альтернативным решениям осуществляется по следующей схеме:

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

2. выбор переменной из множества Р;

3. определение направления изменения выбранной переменной (уменьшение или увеличение);

4. определение нового значения переменной;

5. задание этого значения и выполнение команды Поиск решения;

6. если получена новая вершина, то СТОП, иначе – перейти на п. d.

7. Пункты B – F выполняются до тех пор, пока не будут определены все вершины множества оптимальных решений.

Теперь дадим некоторые рекомендации по выполнению перечисленных выше пунктов.

1. В множество переменных, значения которых нужно изменить, для того, чтобы перейти к следующему оптимальному решению, входят ячейки, для которых Допустимое увеличение или Допустимое уменьшение равно нулю. В нашем примере это переменные и (см. рис. 6.25).

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

3. Теперь определим в какую сторону надо изменять выбранную ячейку. В этом случае рекомендуется поступать так:

– для задачи на максимум

• если для выбранной ячейки равно нулю Допустимое увеличение, то нужно увеличивать значение ячейки;

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

– для задачи на минимум

• если для выбранной ячейки равно нулю Допустимое увеличение, то нужно уменьшать значение ячейки ;

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

4. Рассмотрим, до каких пределов нужно изменить значение переменной, чтобы перейти к другой оптимальной вершине.

В текущем оптимальном решении второе ограничение не является связывающим (соответствующий ресурс – недефицитным). Если мы начнем увеличивать переменную, то остаток этого ресурса будет уменьшаться.

D.1. Придадим переменной значение 1, сохранив значение переменной (рис. 6.26). При таких значениях этих переменных второй ресурс по-прежнему недефицитен.

Р ис. 6.26

Выполним команду Поиск решения. В результате получим такое оптимальное решение: (на рис. 6.19 это точка B, лежащая внутри отрезка AC).

Соответствующий Отчет по результатам представлен на рис. 6.27. Он подтверждает, что полученное решение не является вершиной, так как в нём связывающим является одно (а не два) ограничение.

Рис. 6.27

D.2. Изменим значение переменной таким образом, чтобы нарушилось второе ограничение.

Придадим переменной значение 2, сохранив значение переменной (рис. 6.28). При таких значениях этих переменных второй ресурс также становится дефицитным.

Р ис. 6.28

Выполним команду Поиск решения. В результате получим такое решение: , (на рис. 6.19 это вершина C).

Соответствующий Отчет по результатам представлен на рис. 6.29. Он подтверждает, что полученное решение является вершиной, так как в нём связывающими являются два ограничения.

Рис. 6.29

Итак, средствами Еxcel получили обе вершины множества альтернативных оптимумов. Таким образом, решение данной задачи таково: