Целочисленное программирование. Допустим, что к условию задачи (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-го ресурса на единицу.