Инструментарий и алгоритм реализации оптимизационных задач.
Наиболее популярными для решения оптимизационных задач не линейного программирования являются метод Ньютона и метод сопряженных градиентов, а для задач линейного программирования симплекс-метод. Реализуются методы исследования операций с помощью специального инструмента Поиск решения (для Excel) и Optimization Solver (для OrgCalc). Поиск решения является более сложным инструментом, требующим дополнительной настройки и позволяющим в связи с этим использовать при решении экономических задач различные методы и специфические ограничения (например, неотрицательность или целочисленность переменных). К тому же этот инструмент является дополнительно устанавливаемой надстройкой, которую обязан активизировать пользователь.
Активизация Поиска решения: меню Сервис → Надстройки → пометить опцию Поиск решения → ОК. При этом в меню Сервис появится опция Поиск решения.
Рисунок. Окно установки надстройки Поиск решения в Excel.
Прежде чем применять эту процедуру необходимо определенным образом задать систему ограничений и целевую функцию. Собственно говоря, процесс задания исходной информации осуществляется в несколько этапов:
Ввод матрицы исходных данных на рабочий лист.
Ввести расчетные формулы для системы ограничений и целевой функции, используя метод формирования арифметического вычисления на основе абсолютной и относительной адресации на соответствующие клетки.
Активизировать опцию Поиск решения: меню Сервис → Поиск решения и задать в появившемся окне систему ограничений и целевую функцию, а также вид оптимизации (минимум, минимум или конкретное значение).
Рисунок. Окно для решения оптимизационных задач в Excel.
Задать численный метод решения задачи и параметры вывода результата, для чего активизировать окно Параметры поиска решения.
В данном окне пользователь может задать:
максимальное время для решения задачи (по умолчанию 100 секунд);
предельное число итераций (по умолчанию 100);
относительную погрешность вычислений;
допустимое отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел (при указании большего допуска поиск решения заканчивается быстрее);
уровень сходимости, применяется только к нелинейным задачам, отвечает за решение вопроса о завершении итерационного процесса (критерием окончания итерационного процесса соотнесение относительного изменения значения в целевой ячейке за последние пять итераций, если оно становится меньше числа, указанного в поле Сходимость, поиск прекращается). Лучшую сходимость характеризует большее количество десятичных знаков — например, 0,0001 соответствует меньшему относительному изменению по сравнению с 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения;
выбираемые пользователем расчетные методы и алгоритмы;
кроме этого в окне имеются кнопки Загрузить модель, Сохранить модель и Справка.
Рисунок. Окно настройки параметров решения
оптимизационных задач в Excel.
Также пользователь может рационализировать процесс решения задачи установив флажки в соответствующих настроечных индикаторах:
линейная модель позволяет ускорить поиск решения линейной задачи оптимизации;
неотрицательные значения устанавливают нулевую нижнюю границу, в этом случае её можно не указывать при задании системы ограничений;
флажок в позиции показывать результаты итераций позволяет приостанавливать процесс решения задачи для просмотра результатов отдельных итераций;
автоматическое масштабирование служит для включения автоматической нормализации (пересчета) входных и выходных значений, качественно различающихся по величине (например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей). Как правило, решение вопроса о проведении этой операции зависит от многих предпосылок в постановке задачи и не всегда возможно с точки зрения интерпретации результатов);
В нижней части окна имеются еще 3 группы индикаторов, которые фиксируют методы решения задачи:
первая группа ОЦЕНКИ линейная и квадратичная служат для указания метода экстраполяции (по линейной или квадратичной функции) — используемого получения исходных оценок значений переменных;
вторая группа ПРОИЗВОДНЫЕ прямые и центральные служит для указания метода численного дифференцирования, который используется для вычисления частных производных целевых и ограничивающих функций. Причем, метод прямых производных используется в задачах, где скорость изменения ограничений относительно невысока (это большая часть экономических задач), метод центральных применяется для функций, имеющих разрывную производную (этот способ требует больше вычислений и зачастую используется в задачах, где получить более точное решение не удается).
третья группа МЕТОД позволяет выбрать алгоритм оптимизации (метод Ньютона или сопряженных градиентов) для указания направление поиска. Метод Ньютона использует больше памяти, но находит решение за меньшее число итераций. Метод сопряженных градиентов требует меньше памяти, но выполняет больше итераций, как правило, используется либо когда необходимо экономить память, а также, когда итерации дают слишком малое отличие в последовательных приближениях.
В редакторе OrgCalc инструмент для решения оптимизационных задач Optimization Solver стандартно установлен в виде опции в меню Сервис. В этой электронной таблицы дополнительно задаваемый параметр по кнопке Options только один – использование для рационализации процесса решения только линейной модели (см. на рисунке
Рисунок. Окно для ввода дополнительных параметров в OrgCalc.
После завершения процесса необходимо пользователю предоставляется возможность сохранить найденное решение или вернуться к исходным данным, а в поле Тип отчета пометить интересующие пользователя виды отчетов для вывода на экран (отчет о результатах, отчет об устойчивости, о предельных оценках). В OrgCalc возможности получения отчетов не существует.
Рисунок. Окно завершения решения в Excel.
Проанализировать итоговые результаты:
Отчет о результатах включает исходные и конечные значения целевой функции и оптимальные значения переменных, используемых в модели, а также расчетные значения левых частей неравенств и уравнений, входящих в систему ограничений.
Отчет об устойчивости формирует сведения о решении двойственной задачи. Переменные двойственной задачи называются двойственными оценками (или объективно обусловленными оценками). С точки зрения экономической интерпретации они показывают ценность используемого ресурса (практики часто называют двойственные оценки теневыми ценами).
Отчет о пределах представляет информацию о диапазонах изменения параметров и переменных.
Замечание. В данном окне имеется кнопка Сохранить сценарий, разрешающая найденное решение в сформировать в виде сценария. Наличие такой возможность позволяет в форме сводной таблицы получить множество решений и проанализировать их.