Применение компьютера Инструкция по использованию надстройки «Поиск решения»
Надстройка «Поиск решения» из пакета электронных таблиц Microsoft Excel предназначена для решения широкого класса оптимизационных задач. Для решения задач нелинейной оптимизации программа использует градиентный метод, для решения линейных и целочисленных задач – симплексный метод и метод ветвей и границ соответственно.
Диалоговое окно надстройки «Поиск решения» представлено на рис. 1.16.
Рис. 1.16. Диалоговое окно надстройки «Поиск решения»
В поле «Установить целевую ячейку» необходимо указать адрес или собственное имя ячейки, содержащей формулу для вычисления целевой функции. Надстройка «Поиск решения» позволяет найти максимальное значение целевой функции, минимальное значение или конкретное указанное значение.
В поле «Изменяя ячейки» необходимо задать адреса или имена ячеек, выделенных для хранения искомых неизвестных. Ячейки должны влиять (прямо или косвенно) на значение целевой функции. Допускается до 200 изменяемых ячеек.
Кнопка «Предположить» позволяет автоматически определить все ячейки, влияющие на целевую функцию.
Следует отметить, что начальное значение изменяемых ячеек может оказывать влияние на полученные результаты (например, при поиске альтернативных решений).
В поле «Ограничения» с помощью кнопок «Добавить», «Изменить», «Удалить» надо сформировать список граничных условий. Процесс формирования граничных условий производится следующим образом. При первом нажатии на кнопку «Добавить» появляется диалоговое окно «Добавление ограничений» (рис. 1.17). В поле «Ссылка на ячейку» указывается адрес ячейки (или диапазон ячеек), содержащей левую часть граничного условия. Затем в поле со списком выбирается знак ограничения. Наконец, в поле «Ограничение» задается правая часть граничного условия.
Рис. 1.17. Диалоговое окно «Добавление ограничений»
Нажатие кнопки «Добавить» позволяет в том же окне перейти к вводу очередного граничного условия. Кнопка «ОК» служит для завершения ввода ограничений оптимизационной задачи.
Кнопка «Параметры» из диалогового окна «Поиск решения» (рис. 1.16) позволяет выполнять ряд настроек (рис. 1.17), влияющих на процесс поиска, что дает возможность в некоторых случаях найти более точное решение либо получить решение задачи, которое при параметрах, заданных по умолчанию не может быть найдено.
Выделяют следующие параметры поиска решения.
Максимальное время – это время в секундах, которое может быть затрачено на поиск решения. Максимально допустимое значение – 32767.
Предельное число итераций (шагов) – количество действий (вычисление очередного значения и проверка, насколько оно подходит в качестве ответа), которые могут быть сделаны. Максимально допустимое значение – 32767.
Рис. 1.18. Диалоговое окно «Параметры поиска решения»
Относительная погрешность задает, насколько близко друг к другу расположены два последовательных приближения. Задается числом в диапазоне от 0 до 1.
Допустимое отклонение используется в случае целочисленных ограничений на изменяемые ячейки. Определяет допуск отклонения полученного ответа от возможного наилучшего решения. Задается в процентах. Увеличение допустимого отклонения приводит к уменьшению времени поиска.
Сходимость – относительное изменение значения в целевой ячейке за последние пять шагов. Если эта величина становится меньше указанного числа, поиск прекращается. Задается числом в диапазоне от 0 до 1. Параметр применим только к нелинейным задачам. Уменьшение значения в поле сходимость (улучшение сходимости) приводит к увеличению времени поиска оптимального решения.
Линейная модель приводит к использованию методов линейного программирования (симплекс-метода), что ускоряет процесс поиска оптимального решения для линейных задач.
Неотрицательные значения позволяет задать нулевую нижнюю границу для тех изменяемых ячеек, для которых она не была указана в поле Ограничение.
Автоматическое масштабирование приводит к автоматической нормализации входных и выходных значений, существенно различающихся по величине.
Показывать результаты итераций выводит промежуточный результат и делает паузу после каждого шага вычисления.
Оценки – служит для выбора метода экстраполяции, используемого для получения исходных оценок значений переменных в каждом одномерном поиске. Линейная используется для линейной экстраполяции вдоль касательного вектора. Квадратичная дает лучшие результаты при решении нелинейных задач.
Разности выбирает метод численного дифференцирования, который используется для вычисления частных производных целевых и ограничивающих функций. Прямые производные используются для гладких непрерывных функций, где скорость изменения ограничений относительно невысока. Центральные – для функций, имеющих разрывную производную. Данный способ требует больше вычислений, однако его применение может быть оправданным тогда, когда выдается сообщение о том, что получить более точное решение не удается.
Метод поиска служит для указания алгоритма оптимизации. Метод Ньютона требует больше памяти, но при этом выполняется меньше итераций, чем в методе сопряженных градиентов. Метод сопряженных градиентов следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях.
Математические модели могут быть сохранены и прочитаны с помощью кнопок «Сохранить модель» и «Загрузить модель» (рис. 3). Это позволяет хранить на рабочем листе более одной модели оптимизации.
Кнопка «Выполнить» диалогового окна «Поиск решения» (рис. 1) инициализирует процесс поиска оптимального решения. Затянувшиеся вычисления можно прервать клавишей Esc.
При успешном окончании поиска (рис. 4) можно сохранить найденное решение, восстановить исходные значения изменяемых ячеек, сформировать один или несколько типов отчетов (по результатам, по устойчивости, по пределам).
Существует также возможность найти ряд решений с различными исходными данными или параметрами задачи, а затем сравнить их между собой с помощью Диспетчера сценария (кнопка «Сохранить сценарий»).
Рис. 1.19. Диалоговое окно «Результаты поиска решения»
Отчеты позволяют провести анализ найденного оптимального решения на чувствительность (устойчивость) к возможному изменению исходных условий математической модели.
Для создания отчета выделите мышкой в одноименном списке (рис. 1.19) требуемый тип отчета (или все типы) и нажмите кнопку «ОК». Каждый отчет будет помещен на новый лист рабочей книги.
Отчет по результатам состоит из трех таблиц.
1. Первая таблица содержит сведения о характере исследования функции (Максимум, Минимум или Значение); адрес (Ячейка) и имя (Имя) ячейки, содержащей формулу для вычисления целевой функции; значения целевой функции до начала (Исходно) и после проведения вычислений (Результат).
2. Вторая таблица содержит информацию об искомых переменных (изменяемых ячейках): их адреса (Ячейка) и имена (Имя); значения до (Исходно) и после вычислений (Результат).
3. Третья таблица содержит данные об ограничениях задачи: адреса (Ячейка), имена (Имя) и значения (Значение) левых частей ограничений; вид ограничений (Формула). Столбец Статус показывает равны ли между собой левые и правые части ограничений (связанное) или нет (не связан.). Столбец Разница – разницу между правыми и левыми частями ограничений.
Отчет по устойчивости состоит из двух таблиц.
1. Первая таблица содержит следующую информацию: адреса (Ячейка) и имена (Имя) изменяемых ячеек; оптимальное решение задачи (Результ. значение); Нормир. стоимость, показывающую, как изменяется значение целевой функции при принудительном увеличении нижней границы изменения переменных на единицу; коэффициенты целевой функции (Целевой Коэффициент); предельные значения изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение (Допустимое Увеличение, Допустимое Уменьшение).
2. Вторая таблица содержит аналогичные значения для ограничений: адреса (Ячейка), имена (Имя) и значения (Результ. значение) левых частей ограничений; двойственные оценки, которые показывают, как изменится целевая функция при увеличении правых частей ограничений на единицу (Теневая Цена); правые части ограничений (Ограничение Правая часть); предельные значения изменений ресурсов, при которых сохраняется оптимальный набор пере-менных, входящий в оптимальное решение (Допустимое Увеличение, Допустимое Уменьшение).
Отчет по устойчивости для задач нелинейного программирования отражает вместо нормированной стоимости нормированный градиент, а вместо теневой цены – множитель Лагранжа. Значения коэффициентов целевой функции а также правых частей ограничений и их вариации не определяются.
Отчет по пределам показывает адрес (Ячейка), имя (Целевое Имя) и оптимальное значение (Значение) целевой функции; адреса (Ячейка), имена (Изменяемое Имя) и оптимальное значение (Значение) изменяемых ячеек; нижние пределы изменения значений переменных и значения целевой функции на нижнем пределе (Нижний предел, Целевое результат); верхние пределы изменения значений переменных и значения целевой функции на верхнем пределе (Верхний предел, Целевое результат).
Отчеты по устойчивости и по пределам не создаются для задач целочисленного линейного программирования.