Решение оптимизационных задач с использованием процедуры поиска решений в Microsoft Excel

Решение оптимизационных  задач с использованием процедуры  поиска решений в Microsoft Excel

Процедура поиска решения в Microsoft Excel позволяет найти оптимальное значение формулы F, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить необходимый результат, по формуле, содержащейся в целевой ячейке, процедура изменяет значения варьируемых переменных (X₁, X₂,…X_n) во влияющих ячейках. Как правило, на множество значений варьируемых переменных (X₁, X₂,…X_n) используемых в модели, применяются ограничения.

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

- логическое ограничение;

- целочисленное ограничение;

- верхний, нижний или оба предела  (верхний или  нижний пределы могут быть определены для 100 ячеек).

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

<= меньше или равно

>= больше или равно

= равно

Int целое число (применительно только к изменяемым ячейкам)

Bin двоичное (применительно только к изменяемым ячейкам)

Алгоритмы и  методы поиска решения

Для решения задач нелинейного программирования в процедуре поиска решения Microsoft Excel используется алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).

Алгоритмы симплексного метода Для решения задач линейного программирования и метода ветей и границ ( branch-and-bound)  для решения линейного целочисленного программирования разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.

Задание параметров оптимизационной модели с помощью процедуры поиска решения

1. В меню Сервис выберите команду Поиск решения.

Если команда Поиск решения отсутствует в меню Сервис, установите соответствующую надстройку.

2. После того как появится диалоговое окно «Поиск решения» в поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.
3. Чтобы максимизировать (минимизировать или установить значение в целевой ячейке равным некоторому числу) значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному (минимальному или требуемому) значению.
4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.

6. Используя Параметры настроить параметры оптимизационных процедур. В частности, для решения задач линейного программирования установить переключатели линейная модель и неотрицательные значения.

7. Нажмите кнопку OK и далее  Выполнить.
8. Для получения отчетов о решении задачи, в окне Отчеты укажите типы необходимых отчетов:

• Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.
• Устойчивость. Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле (поле Установить целевую ячейку, диалоговое окно Поиск решения) или в формулах ограничений. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям включаются ограниченные затраты, фиктивные цены, объективный коэффициент (с некоторым допуском), а также диапазоны ограничений справа.
• Пределы. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение. Для задачи линейного программирования нижняя и верхняя границы определяют интервал, в  котором может изменяться переменная, так что базис, определяющий оптимальный план остается неизменным.

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

Чтобы восстановить исходные данные, установите переключатель  в положение Восстановить исходные значения.

10. Чтобы прервать поиск решения, нажмите клавишу ESC. Microsoft Excel пересчитает лист с учетом найденных значений влияющих ячеек.