Целочисленное программирование. Допустим, что к условию задачи (1.1) добавилось требование целочисленности значений всех переменных
Допустим, что к условию задачи (1.1) добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами.
• В экранной форме укажите, на какие переменные накладывается требование целочисленности (этот шаг делается для наглядности восприятия условия задачи) (рис. 1.11).
• В окне "Поиск решения" (меню "Сервис"→"Поиск решения"), нажмите кнопку "Добавить" и в появившемся окне "Добавление ограничений" введите ограничения следующим образом (рис. 1.12):
− в поле "Ссылка на ячейку" введите адреса ячеек переменных задачи, то есть $B$3:$E$3;
− в поле ввода знака ограничения установите "целое";
− подтвердите ввод ограничения нажатием кнопки "OK".
Рисунок 1.11. Решение задачи при условии целочисленности переменных
Рисунок 1.12. Ввод условия целочисленности переменных задачи (1.1)
На рис. 1.11 представлено решение задачи (1.1)–(1,2), к ограничениям которой добавлено условие целочисленности значений ее переменных.
Анализ оптимального решения на чувствительность в Excel
Проведем анализ чувствительности задачи. Для этого необходимо после запуска в Excel задачи на решение в окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты" и "Устойчивость" (рис. 1.13).
Рисунок 1.13. Выделение типов отчетов требуемых для анализа чувствительности
Отчет по результатам
Отчет по результатам состоит из трех таблиц (рис. 1.14):
| Microsoft Excel 11.0 Отчет по результатам | |||||||
| Рабочий лист: [лин.прогр.xls]Лист1 | |||||||
| Отчет создан: 15.04.2010 18:22:13 | |||||||
| таблица 1 | |||||||
| Целевая ячейка (Максимум) | |||||||
| Ячейка | Имя | Исходное значение | Результат | ||||
| $F$6 | Коэфф.ЦФ Значение | 27482,71351 | |||||
| таблица 2 | |||||||
| Изменяемые ячейки | |||||||
| Ячейка | Имя | Исходное значение | Результат | ||||
| $B$3 | Значение Х1 | 100,6606607 | |||||
| $C$3 | Значение Х2 | 546,4444444 | |||||
| $D$3 | Значение Х3 | ||||||
| $E$3 | Значение Х4 | 38,92492492 | |||||
| таблица 3 | |||||||
| Ограничения | |||||||
| Ячейка | Имя | Значение | Формула | Статус | Разница | ||
| $F$12 | Огран.3 Лев.часть | $F$12<=$H$12 | связанное | ||||
| $F$10 | Огран.1 Лев.часть | $F$10=$H$10 | не связан. | ||||
| $F$11 | Огран.2 Лев.часть | $F$11>=$H$11 | связанное | ||||
| $B$3 | Значение Х1 | 100,66 | $B$3>=$B$4 | не связан. | 100,66 | ||
| $C$3 | Значение Х2 | 546,44 | $C$3>=$C$4 | не связан. | 546,44 | ||
| $D$3 | Значение Х3 | $D$3>=$D$4 | связанное | ||||
| $E$3 | Значение Х4 | 38,9249 | $E$3>=$E$4 | не связан. | 38,9249 | ||
Рисунок 1.14. Отчет по результатам
1) таблица 1 содержит информацию о ЦФ;
2) таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;
3) таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.
Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" ("Состояние") соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса.
Для граничных условий в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.
Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа ≥, то в графе "Разница" дается количество ресурса, на которое была превышена минимально необходимая норма.
Если на ресурс наложено ограничение типа ≤, то в графе "Разница" дается количество ресурса, которое не используется при реализации оптимального решения.
Отчет по устойчивости
Отчет по устойчивости состоит из двух таблиц (рис. 1.15).
| Microsoft Excel 11.0 Отчет по устойчивости | |||||||||||||||||||
| Рабочий лист: [лин.прогр.xls]Лист1 | |||||||||||||||||||
| Отчет создан: 15.04.2010 18:22:13 | |||||||||||||||||||
| Таблица 1 | |||||||||||||||||||
| Изменяемые ячейки | |||||||||||||||||||
| Результ. | Нормир. | Целевой | Допустимое | Допустимое | |||||||||||||||
| Ячейка | Имя | значение | стоимость | Коэффициент | Увеличение | Уменьшение | |||||||||||||
| $B$3 | Значение Х1 | 100,66 | 130,5 | 1E+30 | 114,633 | ||||||||||||||
| $C$3 | Значение Х2 | 546,44 | 1E+30 | 37,8923932 | |||||||||||||||
| $D$3 | Значение Х3 | -104,41459 | 104,4145946 | 1E+30 | |||||||||||||||
| $E$3 | Значение Х4 | 38,9249 | 87,8 | 432,5773585 | 95,20826944 | ||||||||||||||
| таблица 2 | |||||||||||||||||||
| Ограничения | |||||||||||||||||||
| Результ. | Теневая | Ограничение | Допустимое | Допустимое | |||||||||||||||
| Ячейка | Имя | значение | Цена | Прав. часть | Увеличение | Уменьшение | |||||||||||||
| $F$12 | Огран.3 Лев.часть | 19,6648648 | 1E+30 | 462,9285714 | |||||||||||||||
| $F$10 | Огран.1 Лев.часть | 47,6981982 | 1E+30 | 410,4489796 | |||||||||||||||
| $F$11 | Огран.2 Лев.часть | -22,949549 | 502,8 | 733,6981132 | |||||||||||||||
Рисунок 1.15. Отчет по устойчивости.
Таблица 1 содержит информацию, относящуюся к переменным.
А. Результат решения задачи.
Б. Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи (см. рис. 1.15) нормированная стоимость Х3 равна –104,4 руб./шт. Это означает, что если мы, несмотря на оптимальное решение, потребуем включить в план выпуска 1 единицу Х3, то новый план выпуска принесет нам прибыль на 104,4 руб. меньше, чем в прежнем оптимальном решении.
В. Коэффициенты ЦФ.
Г. Предельные значения приращения целевых коэффициентов ∆сi , при которых сохраняется первоначальное оптимальное решение. Например, допустимое уменьшение цены на Х1 равно 114,6 руб./шт., а допустимое увеличение – практически не ограничено. Это задает соотношение устойчивости для коэффициентов целевой функции.
Примечание. При выходе за указанные в отчете по устойчивости пределы изменения цен оптимальное решение может меняться как по номенклатуре выпускаемой продукции, так и по объемам выпуска (без изменения номенклатуры).
Таблица 2 (см. рис. 1.15) содержит информацию, относящуюся к ограничениям.
А. Величина использованных ресурсов в колонке "Результ. значение".
Б. Предельные значения приращения ресурсов ∆bj. В графе "Допустимое Уменьшение" показывают, на сколько можно уменьшить (устранить излишек) или увеличить ресурс, сохранив при этом оптимальное решение. Для ограничений, не позволяющих выпускать большее, чем в оптимальном решении, количество продукции и получать более высокую прибыль возникает вопрос, на сколько максимально может возрасти это ограничение, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе "Допустимое Увеличение". Это приведет к новым оптимальным решениям, увеличивающим прибыль. Дальнейшее увеличение таких ограничений сверх указанных пределов не будет больше улучшать решение, т.к. уже другие ресурсы станут связывающими.
В. Объективно-обусловленная оценка j-го ресурса (теневая цена) рассчитывается только для существенных (дефицитных) ресурсов. Объективно-обусловленная оценка j-го ресурса показывает, насколько увеличится целевая функция при увеличении j-го ресурса на единицу.