Информационная технология поиска решения

Информационная технология поиска решения

Microsoft Excel обеспечивает решение задач линейного и нелинейного программирования ограниченной размерности. Для реализации оптимизационных расчетов в Microsoft Excel необходимо установить надстройкуПоиск решения с помощью команды меню Сервис ► Надстройки и правильно подготовить данные оптимизационной модели на листе. Модель задачи задается в диалоговом окне Поиск решения. Модель используетцелевую функцию, которая записывается в виде формулы в отдельной ячейке. Для целевой функции указывается: максимизация, минимизация или равенство фиксированному значению. В процессе поиска решения изменяются значения в указанных ячейках, соответствующих переменным, при соблюдении ограничений.

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

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

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

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

Программа оптимизации поиск решения (SOLVER)

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

Для вызова программы оптимизатора выберите команду меню Сервис→Поиск решения. Если команда Поискрешения отсутствует в меню Сервис, то надо установить эту надстройку.

Установка программы  Поиск решения

В меню Сервис выберите команду Надстройки (см. рис.1).

 

 

Рис. 1. Диалоговое окно Надстройки

В диалоговом окне Надстройки установите флажок Поиск решения. Если диалоговое окно Надстройки не содержит команду Поиск решения, нажмите кнопку Обзор и укажите диск и папку, в которых содержится файл надстройки Solver.xls (как правило, это папка Library\Solver folder), или запустите программу Setup, если найти файл не удается.

Надстройка, указанная в диалоговом окне Надстройки, остается активной до тех пор, пока она не будет удалена.

Настройка экономико-математической модели

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

Решения задачи оптимизации состоит из нескольких этапов.

A.      Создание модели задачи оптимизации.

B.      Поиск решения задачи оптимизации.

C.      Анализ найденного решения задачи оптимизации.

Рассмотрим подробнее  эти этапы.

Этап  А. Создание модели задачи оптимизации

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

Этап  В. Поиск решения задачи оптимизации

Команда Сервис−>Поиск решения открывает диалоговое окно «Поиск решения» (рис.2).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

Команда Добавить служит для отображения диалогового окна Добавить ограничение.

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

Команда Удалить служит для снятия указанного курсором ограничения.

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

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

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

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

Ввод и редактирование ограничений

Диалоговые  окна  изменения  и  добавления  ограничений  одинаковы, рис. 3.

 

Рис. 3. Диалоговое окно Изменение  ограничения

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

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

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

Чтобы приступить к набору нового условия, нажмите кнопку Добавить.

Чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопку ОК.

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

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

Настройка параметров алгоритма и программы

Настройка параметров алгоритма  и программы производится в диалоговом окне Параметры поиска решения, рис. 4.