6.6.4.2. Наличие альтернативных оптимумов
Приёмы получения альтернативных оптимумов7 задачи линейного программирования рассмотрим на примере следующей задачи:
На рис. 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.
Целевая ячейка (Максимум) |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $C$8 | Значение ЦФ | 0 | 24 |
|
|
|
|
|
|
|
|
|
Изменяемые ячейки |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $B$5 | х1 | 0 | 4 |
|
|
| $B$6 | х2 | 0 | 0 |
|
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
| ||
| Ячейка | Имя | Значение | формула | Статус | Разница |
| $C$12 | первое Факт | 12 | $C$12<=$E$12 | связанное | 0 |
| $C$13 | второе Факт | 8 | $C$13<=$E$13 | не связан. | 4 |
| $F$5 | х1 Значение | 4 | $F$5>=0 | не связан. | 4 |
| $F$6 | х2 Значение | 0 | $F$6>=0 | связанное | 0 |
Рис. 6.24
Изменяемые ячейки |
|
|
|
|
| ||
|
|
| Результ. | Нормир. | Целевой | Допустимое | Допустимое |
| Ячейка | Имя | значение | стоимость | Коэффициент | Увеличение | Уменьшение |
| $B$5 | х1 | 4 | 0 | 6 | 1E+30 | 0 |
| $B$6 | х2 | 0 | 0 | 4 | 0 | 1E+30 |
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
|
| ||
|
|
| Результ. | Теневая | Ограничение | Допустимое | Допустимое |
| Ячейка | Имя | значение | Цена | Правая часть | Увеличение | Уменьшение |
| $C$12 | первое Факт | 12 | 2 | 12 | 6 | 12 |
| $C$13 | второе Факт | 8 | 0 | 12 | 1E+30 | 4 |
| $F$5 | х1 Значение | 4 | 0 | 0 | 4 | 1E+30 |
| $F$6 | х2 Значение | 0 | 0 | 0 | 2.4 | 1E+30 |
Рис. 6.25
Признак наличия альтернативных оптимумов: в разделе Изменяемые ячейки Отчета по устойчивости хотя бы для одной из ячеек поле Допустимое увеличение или Допустимое уменьшение равно нулю (см. рис. 6.25).
Из Отчета по результатам (см. рис. 6.24) видим, что оптимум является вершиной, так как количество связывающих (активных) ограничений в нём равно двум (количеству переменных исходной задачи).
Переход к другим альтернативным решениям осуществляется по следующей схеме:
-
определение множества Р переменных (изменяемых ячеек), значения которых нужно изменить, для того, чтобы перейти к следующему оптимальному решению
-
выбор переменной из множества Р;
-
определение направления изменения выбранной переменной (уменьшение или увеличение);
-
определение нового значения переменной;
-
задание этого значения и выполнение команды Поиск решения;
-
если получена новая вершина, то СТОП, иначе – перейти на п. d.
-
Пункты B – F выполняются до тех пор, пока не будут определены все вершины множества оптимальных решений.
Теперь дадим некоторые рекомендации по выполнению перечисленных выше пунктов.
-
В множество переменных, значения которых нужно изменить, для того, чтобы перейти к следующему оптимальному решению, входят ячейки, для которых Допустимое увеличение или Допустимое уменьшение равно нулю. В нашем примере это переменные и (см. рис. 6.25).
-
Из полученного множества выбираем ячейку, которая имеет наименьший по модулю коэффициент целевой функции (Целевой коэффициент). В нашем случае – это изменяемая ячейка .
-
Теперь определим в какую сторону надо изменять выбранную ячейку. В этом случае рекомендуется поступать так:
– для задачи на максимум
-
если для выбранной ячейки равно нулю Допустимое увеличение, то нужно увеличивать значение ячейки;
-
если для выбранной ячейки равно нулю Допустимое уменьшение, то нужно уменьшать значение ячейки.
– для задачи на минимум
-
если для выбранной ячейки равно нулю Допустимое увеличение, то нужно уменьшать значение ячейки ;
-
если для выбранной ячейки равно нулю Допустимое уменьшение, то нужно увеличивать значение ячейки.
-
Рассмотрим, до каких пределов нужно изменить значение переменной, чтобы перейти к другой оптимальной вершине.
В текущем оптимальном решении второе ограничение не является связывающим (соответствующий ресурс – недефицитным). Если мы начнем увеличивать переменную, то остаток этого ресурса будет уменьшаться.
D.1. Придадим переменной значение 1, сохранив значение переменной (рис. 6.26). При таких значениях этих переменных второй ресурс по-прежнему недефицитен.
Р ис. 6.26
Выполним команду Поиск решения. В результате получим такое оптимальное решение: (на рис. 6.19 это точка B, лежащая внутри отрезка AC).
Соответствующий Отчет по результатам представлен на рис. 6.27. Он подтверждает, что полученное решение не является вершиной, так как в нём связывающим является одно (а не два) ограничение.
Целевая ячейка (Максимум) |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $C$8 | Значение ЦФ | 28 | 24 |
|
|
|
|
|
|
|
|
|
Изменяемые ячейки |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $B$5 | х1 | 4 | 3.333333333 |
|
|
| $B$6 | х2 | 1 | 1 |
|
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
| ||
| Ячейка | Имя | Значение | формула | Статус | Разница |
| $C$12 | первое Факт | 12 | $C$12<=$E$12 | связанное | 0 |
| $C$13 | второе Факт | 9.666666667 | $C$13<=$E$13 | не связан. | 2.333333333 |
| $F$5 | х1 Значение | 3.333333333 | $F$5>=0 | не связан. | 3.333333333 |
| $F$6 | х2 Значение | 1 | $F$6>=0 | не связан. | 1 |
Рис. 6.27
D.2. Изменим значение переменной таким образом, чтобы нарушилось второе ограничение.
Придадим переменной значение 2, сохранив значение переменной (рис. 6.28). При таких значениях этих переменных второй ресурс также становится дефицитным.
Р ис. 6.28
Выполним команду Поиск решения. В результате получим такое решение: , (на рис. 6.19 это вершина C).
Соответствующий Отчет по результатам представлен на рис. 6.29. Он подтверждает, что полученное решение является вершиной, так как в нём связывающими являются два ограничения.
Целевая ячейка (Максимум) |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $C$8 | Значение ЦФ первого | 32 | 24 |
|
|
|
|
|
|
|
|
|
Изменяемые ячейки |
|
|
|
| ||
| Ячейка | Имя | Исходно | Результат |
|
|
| $B$5 | х1 | 4 | 2.4 |
|
|
| $B$6 | х2 | 2 | 2.4 |
|
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
| ||
| Ячейка | Имя | Значение | формула | Статус | Разница |
| $C$12 | первое Факт | 12 | $C$12<=$E$12 | связанное | 0 |
| $C$13 | второе Факт | 12 | $C$13<=$E$13 | связанное | 0 |
| $F$5 | х1 Значение | 2.4 | $F$5>=0 | не связан. | 2.4 |
| $F$6 | х2 Значение | 2.4 | $F$6>=0 | не связан. | 2.4 |
Рис. 6.29
Итак, средствами Еxcel получили обе вершины множества альтернативных оптимумов. Таким образом, решение данной задачи таково:
- Содержание
- 1. Порядок выполнения расчетно-графической работы
- Решение задачи симплекс-методом.2
- 2. Содержание отчета по расчетно-графической работе
- Планирование операции
- Содержательная постановка задачи.
- Решение задачи симплекс-методом.
- 3. Варианты заданий расчетно-графической работы
- 3.1. Задания на планирование операции
- 3.2. Задания на применение графического способа решения задач линейного программирования
- 4. Электронная таблица Microsoft Excel
- 4.1. Терминология Excel
- 4.3.6. Ввод чисел или текста
- Ввод текста
- Ввод чисел
- Ввод дат или времени суток
- 4.3.7. Формулы
- 5. Решение задачи линейного программирования средствами Microsoft Excel
- 5.1. Содержательная формулировка задачи Задача определения ассортимента выпуска продукции [3]
- 5.2. Математическая формулировка задачи
- Суммарное время Предельное время
- 5.3. Решение задачи с помощью Microsoft Excel
- Содержимое ячеек таблицы:
- 5.4. Нахождение оптимального решения с помощью процедуры поиска решения
- 5.5. Итоговые сообщения процедуры поиска решения
- 6. Постоптимальный анализ задач линейного программирования
- 6.1. Содержательная постановка задачи
- 6.2. Математическая модель
- 6.3. Решение с помощью Microsoft Excel
- 6.4. Решение задачи симплекс-методом
- 6.5. Определение ценности ресурсов
- Прямая задача:
- В нашей задаче:
- 6.6.1.2. Дефицитные ресурсы Теоретические сведения
- В нашей задаче:
- Теоретические сведения:
- В нашей задаче:
- 6.6.2. Изменение коэффициентов целевой функции
- 6.6.2.1. Небазисные переменные Теоретические сведения
- 6.6.2.2. Базисные переменные Теоретические сведения
- В нашей задаче:
- 6.6.3. Результаты решения и постоптимального анализа задачи
- 6.6.3.1. Оптимальное решение задачи
- 6.6.3.2. Диапазоны изменения уровня запасов ресурсов
- 6.6.3.3. Ценность ресурсов
- 6.6.3.4. Диапазоны изменения цен продукции
- 6.6.4. Некоторые особенности проведения постоптимального анализа задач средствами Excel
- 6.6.4.1. Наличие ограничений типа или
- 6.6.4.2. Наличие альтернативных оптимумов
- Список литературы
- Приложение а Основные положения теории двойственности а.1. Построение двойственных задач
- А.2. Основные теоремы двойственности
- А.3. Получение решения задачи по решению двойственной задачи