Материал: Основы математического моделирования. курс лекций. Перова А.В

задачи на решение. Результаты решения представлены на рис. 42.

Рис. 42

Если решить ту же задачу без условий неотрицательности переменных, получим следующий результат:

Прод1=1.67, Прод2=0, Прод3=14.33, Прод4=0. Получа-

емая прибыль при этом будет равна 1820. Это показывает, что требование целочисленности, как и любое другое дополнительное требование, ухудшает целевую функцию.

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

Таблица 1 содержит сведения о целевой функции. В столбце "Исходно" приведены значения целевой функции до начала вычислений.

Таблица 2 содержит сведения об изменяемых ячейках E13:E16 Здесь приведены значения искомых переменных, полученные в результате оптимального решения задачи.

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

В таблице для ограничений:

"формула" - зависимости для ограничений; "значение" - величина использованного ресурса; "разница" - величина неиспользованного ресурса.

125

Если ресурс используется полностью, то в графе "Состояние" указывается связанное. При неполном использовании ресурса в этой графе указывается не связан.

Величины для граничных условий состоят из двух групп. В первой группе - величины, аналогичные значениям для ограничений, при этом Разница показывает разность между найденным значением переменной и заданным граничным условием; во второй группе - значения для требований целочисленности, поэтому все они являются связанными.

Рис. 43

В диалоговом окне Параметры поиска решения есть возможность вводить различные значения Допустимого отклонения. Увеличение величины допустимого отклонения ухудшает точность решения, но ускоряет его. По умолчанию в Excel установлено допустимое отклонение, равное 5 %, что вполне приемлемо для большинства практических задач.

126

Решение задач с булевыми переменными с использованием EXCEL

Частным случаем задачи целочисленных переменных являются задачи, в результате решения которых искомые переменные xj могут принимать не любые целые значения, а только одно из двух: либо 0, либо 1. Эти переменные, чтобы их отличить от обычных, будем обозначать j вместо xj.

Решение задач с булевыми переменными рассмотрим на следующем примере. Пусть имеется 4 варианта использования ресурсов. Прибыль, которую приносит каждый вариант, и все виды ресурсов приведены на рис. 44.

Рис. 44

Требуется выбрать такие варианты, чтобы суммарная прибыль была максимальной.

1, если вариант принят

Введем булевы переменные j .

0 в противном случае

Тогда математическую модель задачи можно сформулировать в виде:

F 70 1 80 2 90 3 210 4 max

Таблица EXCEL с введенными исходными данными задачи приведена на рис. 45 ( при этом в ячейки F7, F10, F11 введены соответствующие функциональные зависимости).

127

Рис. 45

После создания таблицы с исходными данными осуществляется вызов программы Поиск решения, где в диалоговом окне вводятся:

- адрес и направление целевой функции (F7, макси-

мум);

-изменяя ячейки B3:E3;

-граничные условия: B3 B4, C3 C4, D3 D4, E3 E4;

-B3 B5, C3 C5, D3 D5, E3 E5;

-требования целочисленности: т.е. установить B3, D3, C3, E3 целыми;

-ограничения: F10 H10, F11 H11.

Далее осуществляется переход в диалоговое окно Параметры поиска решения, где устанавливается флажок Линейная модель, после чего задачу нужно запустить на решение. Результаты решения представлены на рис. 46.

Рис. 46

128

Следовательно, надо принимать варианты 3 и 4, при которых получаемая прибыль F=300 будет максимальной.

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

если в оптимальное решение должен входить один вариант ИЛИ другой, то условие записывается следующим обра-

зом: i+ j=1;

если в оптимальное решение может входить (или не входить один вариант И другой, то условие имеет вид:

i+ j 0;

в том случае, когда при принятии i-го варианта ДОЛЖЕН входить j-ый, следует записать i= j.

Аналогично можно записать логические условия для трех вариантов. Так, если в случае принятия k-го варианта должен быть принят либо вариант i, либо вариант j, условие записывается так i+ j= k.

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

К форме ввода исходных данных необходимо добавить логические условия, как это показано на рис. 47.

Далее в диалоговом окне Поиск решения вводятся все условия задачи и задача решается. При появлении на экране диалогового окна Результаты поиска решения сохраним данный сценарий под именем "без доп. усл".

После этого вызовем опять программу Поиск решения и добавим к задаче дополнительное условие F12=H12. Полученный при таких исходных данных сценарий решения сохраним под именем 2= 4.

129