Описание решения задачи с помощью Excel

Рассмотрим ту же задачу:

Найти минимальное значение функции

F = 2,1 x₁ + 6,77 x₂ + 4,53 x₃ ,

при ограничениях:
0,99x₁ + 1,1 x₂ + 2,155 x₃ £ 200,
8,725 x₁ + 1,679 x₂ + 25,34 x₃ ³ 130,
3 x₁ + 4x₂ = 38,
0,971x₁ + 3,5 x₂ + 7,3 x₃ £ 200,
x₁ ³ 0, x₂ ³ 0, x₃ ³ 0.

Объект оптимизации описывается средствами табличного процессора Excel как совокупность формул, сведенных в таблицу и зависящих от изменяемых параметров - исходных данных. Данные нашей задачи занесем на лист Excel, например, как показано на рисунке 1.

Рис 1 Лист Excel с данными задачи

В ячейках B2, C2, D2 занесены предварительные значения переменных, которые будут варьироваться в процессе решения. Здесь они заданы равными единице, но обычно их рекомендуется задавать нулями, (поскольку точка 0, как правило, входит в область допустимых решений, а значения x_i= 1 могут и не входить)

В третьей строке занесены коэффициенты целевой функции,

В следующих строках – коэффициенты a_ij при неизвестных в соответствующих ограничениях.

В ячейках B9 – B12 занесены формулы ограничений:

B9 = $B$2*B4+$C$2*C4+$D$2*D4,

B10= $B$2*B5+$C$2*C5+$D$2*D5,

B11= $B$2*B6+$C$2*C6+$D$2*D6,

B12= $B$2*B7+$C$2*C7+$D$2*D7.

В ячейке B14 – формула целевой функции

B14 = $B$2*B3+$C$2*C3+$D$2*D3.

В Excel поиск значений переменных, при которых достигается экстремум целевой функции, осуществляется через пункт меню «Сервис», подпункт «Поиск решения» (в англоязычном варианте - «Solver»).

Раскройте пункт меню «Сервис», выберите команду «Поиск решения». (Если в меню «Сервис» отсутствует команда «Поиск решения», загрузите эту надстройку: выберите команду «Сервис – Надстройки» и активизируйте надстройку «Поиск решения».)

"Поиск решения" вызывает диалоговое окно, представленное на рисунке 2.

Рис. 2 Диалоговое окно «Поиск решения»

Ниже перечислены основные поля и органы управления диалогового окна «Поиск решения» и их назначение.

· Поле «Установить целевую ячейку» служит для указания ячейки, содержащей целевую функцию, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. (Эта ячейка должна содержать формулу).

· Переключатель «Равной» служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного значения). Чтобы установить заданное значение, введите его в поле, расположенное справа от слова «Значение».

· Поле «Изменяя ячейки» служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле «Установить целевую ячейку».

· Кнопка «Предположить» используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле «Установить целевую ячейку». Результат поиска отображается в поле «Изменяя ячейки».

· Список «Ограничения» служит для отображения списка граничных условий поставленной задачи.

· Кнопка «Добавить» служит для отображения диалогового окна «Добавить ограничение», с помощью которого записываются выражения, определяющие ограничения.

· Кнопка «Изменить» служит для отображения диалогового окна «Изменить ограничение», которое позволяет редактировать выбранное выражение из списка ограничений.

· Кнопка «Удалить» служит для снятия выбранного ограничения.

· Кнопка «Выполнить» служит для запуска поиска решения поставленной задачи.

· Кнопка «Закрыть» служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Параметры», «Добавить», «Изменить» или «Удалить».

· Кнопка «Параметры» служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения. В данном случае под моделью понимается диапазон ячеек листа, в которых содержатся исходные данные, формулы и целевая ячейка, которые описывают решаемую задачу.

· Кнопка «Восстановить» служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.

Описание ограничений, присущих оптимизационной задаче, выполняется с помощью двух однотипных диалоговых окон «Добавление ограничения» и «Изменение ограничения», одно из которых представлено на рисунке 3.

Рис. 3 Диалоговое окно «Добавление ограничения»

 

Ниже перечислены основные поля и органы управления названных диалоговых окон.

· Поле «Ссылка на ячейку» служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение.

· Раскрывающийся список предназначен для выбора условия (<=, >=, =) определяющего ограничение.

· Поле «Ограничение» служит для задания числа, формулы, ссылки на ячейку или диапазон, определяющие ограничение.

· Кнопка «Добавить» используется для того, чтобы, не возвращаясь в окно диалога «Параметры поиска решения», наложить новое условие на поиск решения задачи.

Управление алгоритмом поиска и определение его параметров (скорости сходимости, точности и т.п.) выполняется с помощью диалогового окна «Параметры поиска решения», представленного на рисунке 4.

 

Рис. 4 Диалоговое окн «Параметры поиска решения»

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

Ниже описаны значения полей, переключателей и флагов этого диалогового окна:

· Поле «Максимальное время» служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Предельное число итераций» служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Относительная погрешность» служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Относительная погрешность по умолчанию 0,000001.

· Поле «Допустимое отклонение» служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большего допуска поиск решения заканчивается быстрее.

· Поле «Сходимость». Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле «Сходимость», поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 до 1.

· Флаг «Линейная модель» служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

· Флаг «Показывать результаты итераций» служит для приостановки поиска решения для просмотра результатов отдельных итераций.

· Флаг «Автоматическое масштабирование» служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

· Флаг «Значения не отрицательны» позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле "Ограничение" диалогового окна «Добавить ограничение».

· Переключатель «Оценки» служит для указания метода экстраполяции (линейная или квадратичная), используемого для получения исходных оценок значений переменных в каждом одномерном поиске.

o Значение переключателя «Линейная» служит для использования линейной экстраполяции вдоль касательного вектора.

o Значение переключателя «Квадратичная» служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач и не играет роли для линейных задач.

· Переключатель «Производные» служит для указания метода численного дифференцирования и для линейных задач его значение не играет роли.

· Переключатель «Метод поиска» служит для выбора алгоритма оптимизации (метод Ньютона или метод сопряженных градиентов) для указания направления поиска. Для решения задач линейного программирования его значения несущественны.

· Кнопка «Загрузить модель» служит для отображения на экране диалогового окна «Загрузить модель», в котором можно задать ссылку на область ячеек, содержащих загружаемую модель.

· Кнопка «Сохранить модель» служит для отображения на экране диалогового окна «Сохранить модель», в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации, первая модель сохраняется автоматически.

 

В результате заполнения всех полей и внесения всех ограничений, диалоговое окно «Поиск решения» для нашей задачи примет вид рисунка 5:

Рис.5 Результат заполнения полей диалогового окна «Поиск решения»