ЛАБОРАТОРНАЯ РАБОТА № 4
ТАБЛИЧНЫЙ ПРОЦЕССОР MS EXCEL.
ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ
Цель работы: изучить возможности утилиты «Поиск решения» ТП MS Excel на примере решения оптимизационных задач: оптимизации производственной программы, оптимизации плана перевозок.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Среди оптимизационных задач экономики и управления производством наиболее известны задачи линейного программирования, в которых максимизируемая (минимизируемая) функция F(X) является линейной, а ограничения Gзадаются линейными неравенствами.
Общая форма записи модели задачи линейного программирования имеет вид:
целевая функция (ЦФ):
,
при ограничениях:
Прикладной программный продукт ТП Excel фирмы Microsoft содержит в своем составе достаточно мощное средство для решения задач оптимизации с учетом ограничений.
Это так называемая утилита “Поиск решения” (см. рис. 4.1). Прокомментируем некоторые аспекты работы с этой утилитой.
Рис.4.1– Окно утилиты Поиск решения
Искомые переменные - ячейки рабочего листа Excel - называются регулируемыми ячейками.
Целевая функция F(x1, x2, …, xn), называемая иногда просто целью, должна задаваться в виде формулы в ячейке рабочего листа. Эта формула может содержать функции, определенные пользователем, и должна зависеть (ссылаться) от регулируемых ячеек. В момент постановки задачи определяется, что делать с целевой функцией. Возможен выбор одного из вариантов:
Ø найти максимум целевой функции F(x1, x2, …, xn);
Ø найти минимум целевой функции F(x1, x2, …, xn);
Ø добиться того, чтобы целевая функция F(x1, x2, …, xn) имела фиксированное значение: F(x1, x2, …, xn) = a (см. рис. 4.2).
Рис.4.2 – Определение целевой функции в окне утилиты «Поиск решения»
Функции G(x1, x2, …, xn) называются ограничениями. Их можно задать как в виде равенств, так и неравенств.
На регулируемые ячейки (искомые параметры – x1, x2, …, xn) можно наложить дополнительные ограничения: неотрицательности и/или целочисленности, тогда решение ищется в области положительных и/или целых чисел (см. рис.4.3).
Рис. 4.1 – Определение ограничений
Под эту постановку попадает самый широкий круг задач оптимизации, в том числе решение различных уравнений и систем уравнений, задачи линейного (см. выше) и нелинейного программирования.
Управление диалоговым окном поиска решения осуществляется следующим образом (см. рис. 4.1).
Установить целевую ячейку
Служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу для вычисления целевой функции.
Равной
Служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, необходимо ввести его в поле.
Изменяя ячейки
Служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку. В этих ячейках должны содержаться переменные оптимизационной модели.
Ограничения
Служит для отображения списка граничных условий поставленной задачи.
Выполнить
Служит для запуска поиска решения поставленной задачи.
Закрыть
Служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога.
Параметры
Служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Восстановить
Служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
Диалоговое окно "Параметры поиска решения"
Можно изменять условия и варианты поиска решения для линейных и нелинейных задач, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач (см. рис.4.2).
Рис.4.2 – Диалоговое окно "Параметры поиска решения"
Максимальное время
Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.
Предельное число итераций
Служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести значение, не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.
Относительная погрешность
Служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать десятичную дробь от 0 (нуля) до 1. Чем больше десятичных знаков в задаваемом числе, тем выше точность — например, число 0,0001 представлено с более высокой точностью, чем 0,01.
Допустимое отклонение
Служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большего допуска поиск решения заканчивается быстрее.
Сходимость
Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков — например, 0,0001 соответствует меньшему относительному изменению по сравнению с 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения.
Линейная модель
Служит для ускорения поиска решения линейной задачи оптимизации.
Показывать результаты итераций
Служит для приостановки поиска решения для просмотра результатов отдельных итераций.
Автоматическое масштабирование
Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине — например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.
Неотрицательные значения
Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение
Оценка
Служит для указания метода экстраполяции — линейная или квадратичная, используемого для получения исходных оценок значений переменных в каждом одномерном поиске.
Линейная – служит для использования линейной экстраполяции вдоль касательного вектора.
Квадратичная – служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач.
Разности
Служит для указания метода численного дифференцирования — прямые или центральные производные, который используется для вычисления частных производных целевых и ограничивающих функций.
Прямые – используется в большинстве задач, где скорость изменения ограничений относительно невысока.
Центральные – используется для функций, имеющих разрывную производную. Данный способ требует больше вычислений, однако его применение может быть оправданным, если выдается сообщение о том, что получить более точное решение не удается.
Метод поиска
Служит для выбора алгоритма оптимизации — метод Ньютона или сопряженных градиентов — для указания направления поиска.
| Ньютона. Реализация квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. |
| Сопряженных градиентов. Реализация метода сопряженных градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях. |
Утилита «
Поиск решения» позволяет представлять результаты в виде трех отчетов: Результаты, Устойчивость и Пределы.
Для генерации одного или нескольких отчетов выделяются их названия в окне диалога Результаты поиска решения.
Отчет по устойчивости содержит информацию о том, насколько целевая ячейка чувствительна к изменениям ограничений и переменных. Этот отчет имеет два раздела: один для изменяемых ячеек, а второй для ограничений. Раздел для изменяемых ячеек содержит значение нормированного градиента, которое показывает, как целая ячейка реагирует на увеличение значения в соответствующей изменяемой ячейке на одну единицу. Подобным образом множитель Лагранжа в разделе для ограничений показывает, как целевая ячейка реагирует на увеличение соответствующего значения ограничения на одну единицу.
Отчет по результатам содержит три таблицы: в первой приведены сведения о целевой функции до начала вычисления, во второй - значения искомых переменных, полученные в результате решения задачи, в третьей - результаты оптимального решения для ограничений. Этот отчет также содержит информацию о таких параметрах каждого ограничения, как статус и разница. Статус может принимать три состояния: связанное, несвязанное или невыполненное. Значение разницы - это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения.
Отчет по пределам содержит информацию о том, в каких пределах значения изменяемых ячеек могут быть увеличены или уменьшены без нарушения ограничений задачи. Для каждой изменяемой ячейки этот отчет содержит оптимальное значение, а также наименьшие значения, которые ячейка может принимать без нарушения ограничений.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Задание 1. Решить линейную оптимизационную задачу.