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

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

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

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

Точность

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

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

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

. Чем больше отклонение, тем быстрее процесс решения.

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

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

Часть 1. Поиск решений на электронных таблицах

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

уже отмечалось, что в математическом программировании различают­ся три основных вида таких задач: линейные, целочисленные и нели­нейные.

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

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

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

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

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

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

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

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

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

Группа параметров контроля процесса поиска

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

• значения Целевой Ячейки не сходятся;

• поиск Решения не смог найти правильное решение;

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

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

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

26

Часть 1. Поиск решений на электронных таблицах

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

27

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

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

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

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

Сохранение и загрузка моделей

Информация, введенная в диалоговое окно Поиск решения, и па­раметры, введенные в дополнительное окно Параметры поиска реше­ния, образуют модель оптимизационной задачи. Такая модель факти­чески представляет собой задание на поиск решения, включающее в себя: определение целевой и изменяемых ячеек, вид оптимизации,; ограничения, максимальное время, число итераций и т. д. Модель за-| дачи размещается на рабочем листе в области, называемой область модели.

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

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

Использование кнопки Сохранить модель позволяет сохранить на одном рабочем листе более, чем одну модель задачи.

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

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

Поиск по сайту: