Управление процессом поиска решения

 

Нажатие кнопки Выполнить окна Поиск решения приводит к запу­ску процесса поиска решения задачи оптимизации. При невозможно­сти запустить поиск решения система может вывести следующие со­общения:

Недостаточно памяти для решения задачи. Это означает, что EXCEL не смог выделить память для поиска решения. Закройте не­нужные файлы или приложения и попытайтесь запустить программу снова.

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

Управление процессом поиска решения связано с использованием диалогового окна Параметры поиска решения, которое открывается при нажатии кнопки Параметры окна Поиск решения.

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

Группа параметров, определяющих время процесса поиска

 

К этой группе относятся четыре параметра; максимальное время, число итераций, точность и допустимое отклонение.

К настройке этих параметров целесообразно обратиться при полу­чении следующих сообщений о неудачном окончании процесса поис­ка решения:

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

• остановка при исчерпании лимита времени;

• остановка при выполнении максимального числа итераций.

Максимальное Время

Ограничивает время, требующееся для процесса отыскания реше­ния. Значение времени должно быть положительным целым числом. Время по умолчанию 100 (секунд). Максимальное значение, которое можно ввести: 32 767.

Число Итераций

Ограничивает число промежуточных вычислений в процессе по­иска решения и, как следствие, время поиска. Значение должно быть положительным целым числом, по умолчанию 100. Максимальное значение, которое можно ввести: 32 767.

 

Точность

Используется в процессе поиска при проверке ограничений (на равенство и/или неравенство). Вводимое значение должно быть боль­ше 0 и меньше 1. По умолчанию 0.000001. Чем выше точность, тем больше время поиска решения,

Допустимое отклонение

Так же как и точность используется алгоритмом поиска при про­верке ограничений, но (в отличие от точности) используется только в задачах целочисленного программирования при проверке целочис­ленных ограничений. Величина, вводимая в это поле, определяет до­пустимое отклонение в процентах от результата предыдущей итера­ции. Чем больше отклонение, тем быстрее процесс решения.

Группа параметров, адаптирующих процесс поиска к математической модели задачи

Для того чтобы определить значения параметров этой группы, ис­следователю в общем случае необходимо иметь определенное пред­ставление о математических методах решения оптимизационных за­дач. Выше в разделе «Быстрое начало» («Краткий экскурс в теорию») уже отмечалось, что в математическом программировании различаются три основных вида таких задач: линейные, целочисленные и нелинейные. Алгоритмы решения задач линейного программирования имеют наиболее эффективную реализацию. Потому, если вы уверены, что ваша задача относится к линейным, выберите в окне Параметры поис­ка решения перед выполнением поиска кнопку Линейная модель.

Если это указание ошибочно (модель в действительности нелинейна), EXCEL в процессе поиска выведет сообщение «Условия линейности модели не соблюдены». В этом случае длярешения проблемы придется сбросить флажок Линейная модель и решать задачу с использованием более сложных и менее эффективных алгоритмов нелинейного программирования.

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

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

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

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

Параметры группы Оценки определяют методы, используемые поиском решения для построения оценок значений переменных (изменяемых ячеек) в процессе поиска. Кнопка линейная обычно использу­ется для линейных или линеаризованных проблем, квадратичная — для нелинейных, В этой связи еще раз напомним, что сходимость в процесса поиска во многом зависит от начальных значений изменяемых ячеек.

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

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