Описание решения задачи с помощью Excel
Рассмотрим ту же задачу:
Найти минимальное значение функции
F = 2,1 x1 + 6,77 x2 + 4,53 x3 ,
при ограничениях:
0,99x1 + 1,1 x2 + 2,155 x3 £ 200,
8,725 x1 + 1,679 x2 + 25,34 x3 ³ 130,
3 x1 + 4x2 = 38,
0,971x1 + 3,5 x2 + 7,3 x3 £ 200,
x1 ³ 0, x2 ³ 0, x3 ³ 0.
Объект оптимизации описывается средствами табличного процессора Excel как совокупность формул, сведенных в таблицу и зависящих от изменяемых параметров - исходных данных. Данные нашей задачи занесем на лист Excel, например, как показано на рисунке 1.
Рис 1 Лист Excel с данными задачи
В ячейках B2, C2, D2 занесены предварительные значения переменных, которые будут варьироваться в процессе решения. Здесь они заданы равными единице, но обычно их рекомендуется задавать нулями, (поскольку точка 0, как правило, входит в область допустимых решений, а значения xi= 1 могут и не входить)
В третьей строке занесены коэффициенты целевой функции,
В следующих строках – коэффициенты aij при неизвестных в соответствующих ограничениях.
В ячейках 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 Результат заполнения полей диалогового окна «Поиск решения»