Поиск решения

Поиск решения вызывается из меню Сервис и предлагает одноименное диалоговое окно, представленное на рис.5.2.

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

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

v Поле Установить целевую ячейку. Служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

v Раскрывающийся список. Предназначен для выбора условия (отношения), определяющего ограничение.

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

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

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

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

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

v Поле Относительная погрешность. Служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до 1. Низкая точность соответствует введенному числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию, например 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.

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

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

v Поле Сходимость. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков, например 0,0001 – это меньшее относительное изменение, чем 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения.

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

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

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

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

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

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

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

v Переключатель Производные ". Служит для указания метода численного дифференцирования (прямые или центральные производные), который используется для вычисления частных производных целевых и ограничивающих функций.

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

v Значение переключателя Центральные. Используется для функций, имеющих разрывную производную. Несмотря на то, что данный способ требует больше вычислений, он может помочь при получении итогового сообщения о том, что процедура поиска решения не может улучшить текущий набор влияющих ячеек.

v Переключатель Метод. Служит для выбора алгоритма оптимизации (метод Ньютона или метод сопряженных градиентов) для указания направления поиска.

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

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

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

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

Следует иметь в виду, что Поиск решения - это мощный и очень сложный инструмент, требующий хорошей математической подготовки в области численных методов и отчетливого понимания того, как изменение определенного параметра алгоритма отразится на итоговых результатах. Зачастую начинающие пользователи испытывают серьезные трудности при использовании данного инструмента. Помочь им разобраться в характере возникающих проблем могут итоговые сообщения процедуры поиска решения. Особенно полезны эти сообщения в случаях, когда поиск прекращен, но решение не получено. Ниже приведены наиболее важные итоговые сообщения процедуры поиска решения.

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

v Решение найдено. Все ограничения и условия оптимальности выполнены.

Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.

v Поиск свелся к текущему решению.

Все ограничения выполнены. Относительное изменение значения в целевой ячейке за последние пять итераций стало меньше установленного значения параметра Сходимость в диалоговом окне Параметры поиска решения. Чтобы найти более точное решение, установите меньшее значение параметра Сходимость, но это займет больше времени.

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

v Поиск не может улучшить текущее решение. Все ограничения выполнены.

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

v Поиск остановлен (истекло заданное на поиск время).

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

v Поиск остановлен (достигнуто максимальное число итераций).

Произведено разрешенное число итераций, но достичь удовлетворительного решения не удалось.

v Значения целевой ячейки не сходятся.

Значение целевой ячейки неограниченно увеличивается (или уменьшается), даже если все ограничения соблюдены

v Поиск не может найти подходящего решения.

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

v Поиск остановлен по требованию пользователя.

Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.

v Условия для линейной модели не удовлетворяются.

Установлен флажок Линейная модель, однако итоговый пересчет порождает такие значения, которые не согласуются с линейной моделью.

v При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.

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

v Мало памяти для решения задачи.

Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения и попытайтесь снова выполнить процедуру поиска решения. Или запущено несколько копий MS Excel, в одном из которых используется файл solver.dll.