Поиск решения
В тех случаях, когда оптимизационная задача содержит несколько переменных величин, то для решения или анализа сценария необходимо воспользоваться технологией «Поиск решения». Поиск решения аналогичен Подбору параметров, но имеет следующие отличия:
изменяемых параметров (переменных) можно использовать 2 и более (до 36 включительно);
решение может быть получено как в прямой постановке задачи (нахождение экстремума целевой функции), так и в обратной (аналогично «Подбору параметров»);
на результат решения можно накладывать разнообразные ограничения и условия;
решение может быть получено как для линейной модели (целевой функции) так и для нелинейной функции. Для нелинейной модели можно выбрать и метод поиска оптимального решения (выбор из двух альтернативных);
при поиске решения можно задать большее количество параметров, что делает эту процедуру более универсальной и эффективной;
«Поиск решения» является надстройкой над Excel и требует для применения специальной загрузки.
Если в меню «Сервис» отсутствует эта программа (команда), то для загрузки её необходимо:
Войти в меню «Сервис» - НАДСТРОЙКА и открывается окно «Надстройки»
В этом окне в списке доступных надстроек найти программу «Поиск решения» и отметить её флажком
Если программа в списке отсутствует, или флажок не устанавливается, то требуется щёлкнуть мышью по кнопке «Обзор» и найти непосредственно файл программы (Solver.xla) и запустить его. Файл, как правило, находится по адресу: папка Program Files/Microsoft Office/Office/Library/Solver.xla
В случае отсутствия этого файла на жёстком диске, его необходимо установить с дистрибутивного диска.
Описание последовательности действий и элементов управления «Поиска решения»
Ввести исходные данные для решения задачи в виде таблицы. В ячейку, где будет находиться результат решения задачи, записать целевую функцию. Выражения, на которые накладываются ограничения, записываются отдельно в пустых ячейках таблицы.
Выделить ячейку с целевой функцией и вызвать программу «Поиска решения». Для этого открыть меню «Сервис» - ПОИСК РЕШЕНИЯ.
В открывшемся окне «Поиск решения» выбрать нужные элементы управления и установить следующие параметры (см. рис.8):
«Установить целевую ячейку» - поле, в котором устанавливается адрес целевой ячейки (при выполнении п.2 этот адрес введён по умолчанию)
В полях переключателей «Равной» установить требуемый результат решения задачи (максимальному значению, минимальному значению или конкретному значению, как в «Подборе параметров»)
В поле «Изменяя ячейки» установить адреса ячеек, которые будут варьироваться в процессе поиска решения. В исходной таблице эти ячейки могут быть пустыми или туда введены какие-либо предварительные значения. Общее количество таких ячеек (переменных) может быть не более 200.
Кнопка «Предположить» позволяет автоматически занести адреса изменяемых ячеек в поле «Изменяя ячейки», если программа в состоянии самостоятельно их выделить (необходимо проверять!)
В списке «Ограничения» установить дополнительные условия, которые необходимо учитывать при поиске решения. Например, адреса ячеек, где должны быть целые значения ($D4:D12=Integer), или положительные числа (C5>0; F8>0), или значения, которые должны быть больше (меньше) какого-либо числа (C6:C8>=100; C12<-6)
Кнопки «Добавить», Изменить», «Удалить» - для создания, изменения или удаления ограничений. Кнопка «Добавить» выводит на экран окно «Добавление ограничений» (см. рис.9), куда вводится одно ограничение. Через это окно можно ввести и остальные ограничения, нажимая каждый раз кнопку «Добавить». Кнопка «Изменить» выводит в окне «Изменение ограничений», выделенное в списке ограничение для его модификации.
Кнопки «Выполнить» и «Закрыть» предназначены для запуска процедуры поиска решения или для её отмены
Кнопка «Восстановить» - для восстановления исходного состояния таблицы данных (отмена решения)
Кнопка «Параметры» выводит диалоговое окно «Параметры поиска решения» для контроля или изменения этих параметров (элементы этого окна рассмотрим позже)
4. После задания нужных параметров поиска решения нажимается кнопка «Выполнить» и на экран выводится окно «Результаты поиска решения» (см. рис. 10). Это окно предназначено для вывода найденного решения и итогового сообщения, а также позволяет определить дальнейшие действия с помощью следующих элементов управления:
Флажок «Сохранить найденное решение»
Флажок «Восстановить исходные значения» - при необходимости отмены найденного решения
Кнопка «Сохранить сценарий» - для сохранения найденного решения в виде сценария (доступно при количестве переменных не более 32). Можно создать сценарий и, не сохраняя найденного решения и не отображая результаты на листе. Для этого после сохранения сценария, в диалоговом окне «Результаты поиска решения» нажмите кнопку «Восстановить исходные значения»
Список «Типов отчёта» позволяет выбрать тип создаваемого отчёта и все сразу. Отчёт «Результаты» включает целевую ячейку, влияющие ячейки модели, их исходные и конечные значения , формулы ограничений и другие дополнительные сведения. Отчёт «Устойчивость» содержит данные о чувствительности решения к малым изменениям модели или ограничений. Отчёт «Пределы» включает значения целевой и изменяемых ячеек, нижние и верхние их границы
В левом верхнем углу окна выводятся следующие сообщения процедуры поиска:
Решение найдено. Все ограничения и условия оптимальности выполнены.
Поиск свёлся к текущему решению. Все ограничения выполнены. Вычисления прекращены по параметру «Сходимость». Для поиска более точного решения можно уменьшить значение сходимости
Поиск не может улучшить текущее решение. Все ограничения выполнены – найдено приблизительное решение. Для увеличения точности можно уменьшить погрешность и повторить процедуру поиска
Поиск остановлен (истекло заданное на поиск время). Исчерпано время, заданное в окне «Параметры»
Поиск остановлен (достигнуто максимальное число итераций – заданное в окне «Параметры»)
Значение целевой ячейки не сходится –результат решения неограниченно уменьшается или увеличивается, требуется корректировка постановки задачи
Поиск не может найти подходящего решения – нет решения, удовлетворяющего всем ограничениям при заданной точности из-за противоречивости ограничений или ошибок в формуле
Поиск остановлен по требованию пользователя – нажата кнопка «Стоп» в окне «Текущее состояние поиска решения»
Условия для линейной модели не удовлетворяются – установлен параметр «Линейная модель» в то время как решаемая задача не линейна
При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничений – заданы недопустимые значения или тип ограничения, неверно введено имя или формула
Мало памяти для решения задачи
Другой экземпляр Excel использует sjlver.dll – процедура поиска решения задействована другим файлом
Рис.8. Диалоговое окно «Поиск решения»
Рис. 9. Добавление ограничений в задачу поиска решения
Рис. 10. Окно «Результаты поиска решения»
При щелчке по кнопке «Параметры» окна «Поиск решения» открывается диалоговое окно «Параметры поиска решения» (см. рис. 11), которое позволяет изменять условия и варианты поиска решения, а также загружать и сохранять оптимизируемые модели. Для этого в окне имеются следующие элементы управления:
«Максимальное время» - для установки времени решения задачи (по умолчанию 100сек). Максимально допустимое время 32767 сек (9,1 часа).
«Итерации» - ограничивает число итераций для уменьшения времени решения задачи (по умолчанию – 100)
«Точность» - задаёт точность, с которой определяется целевое значение в интервале от 0 до 1 (по умолчанию 0,0001)
«Допустимое отклонение» - задаёт допуск в процентах на отклонение от оптимального решения
«Сходимость» - поле, в котором задаётся число в интервале от 0 до 1, с которым сравнивается относительное изменение значения в целевой ячейке за последние пять итераций. Применяется только к нелинейным задачам. Соответствует параметру «Точность» в линейных моделях.
«Линейная модель» - используется для ускорения решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи при любом количестве ограничений
«Автоматическое масштабирование» - включает автоматическую нормализацию значений целевой и изменяемых ячеек, различающихся на несколько порядков
«Неотрицательные значения» позволяет установить нулевую нижнюю границу для влияющих ячеек
«Показывать результаты итераций» - задаёт приостановку поиска решения для просмотра результатов отдельных итераций. При её установке программа будет автоматически приостанавливать поиск решения, чтобы пользователь мог просмотреть промежуточные результаты поиска. При этом на экран выводится окно «Текущее состояние поиска решения»
«Оценки» - группа переключателей, позволяющих задать линейную или квадратичную экстраполяцию для получения исходных оценок значений переменных в каждом одномерном поиске. Линейная оценка служит для использования линейной экстраполяции вдоль касательного вектора. Квадратичная оценка даёт лучшие результаты при решении нелинейных задач
«Разности» - группа переключателей , определяющих метод численного дифференцирования для вычисления частных производных целевых и ограничивающих функций. Прямые разности используются для гладких непрерывных функций. Центральные разности используются для функций, имеющую разрывную производную
«Метод» - группа переключателей, предназначенных для выбора алгоритма оптимизации. Метод Ньютона служит для реализации квазиньютоновского метода (или метода касательных, при котором используются вторые частные производные целевой функции). Метод сопряжённых градиентов, который для поиска оптимального решения использует информацию о первых производных
Кнопка «Загрузить модель» выводит диалоговый блок, в котором можно задать ссылку на область рабочего листа, содержащую загружаемую модель.
Кнопка «Сохранить модель» выводит окно, в котором можно задать ссылку на верхнюю ячейку столбца, в котором следует разместить модель, если на листе сохраняется более одной модели оптимизации
Рис. 11. Окно задания параметров поиска решения