Поиск оптимального решения

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

В качестве примера рассматривается задача оптимального распределения судов по линям. Таблица, содержащая оптимизационные расчеты представлена на рис.2.29.

Первая часть таблицы содержит справочную информацию, а вторая планируемые показатели. Ниже располагается расчетная часть таблицы, в которой изменяемые ячейки (B18:D20) содержат искомые параметры, значения которых будут варьироваться. Целевая ячейка (F21) содержит функционал, значение которого необходимо минимизировать. Расчетные формулы представлены в копии таблицы на втором плане рисунка.

Для выполнения оптимизационных расчетов необходимо вызвать надстройку Поиск решения и произвести установку основных параметров оптимизации (Рис.2.30):

¾ Установить целевую ячейку F21;

¾ Установить переключатель Равной: в положение минимальному значению;

¾ Установить изменяемые ячейки B18:D20.

Значения в ячейках B18:D20 задаются в первом приближении. Желательно (но не обязательно) задавать значения близкие окончательному решению.

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

1. Указать, что значения в изменяемых ячейках должны быть целыми (B18:D20=целое);

2. Запретить для изменяемых ячеек отрицательные значения (B18:D20>=0);

3. Ввести ограничения по количеству используемых судов каждого типа (B21<=D4), (C21<=E4), (E21<=F4);

4.
Установить ограничения по объему перевозок для каждой линии (E18>=D13), (E19>=E13), (E20>=F13).

Первые три пункта задания ограничений представляются естественными. По последнему пункту следует заметить, что практически реализовать точное выполнение условий (E18=D13), (E19=E13), (E20=F13) вряд ли возможно. Поэтому допускается выполнение последних рейсов с некоторым недогрузом. Главное – обеспечить выполнение планируемых показателей (D13, E13, F13).

Для тонкой настройки оптимизации используется панель Параметры поиска решения (Рис.2.30) вызываемая кнопкой Параметры окна Поиск решения.

После настройки надстройки Поиск решения нажимают кнопку Выполнить.

Время необходимое для получения окончательного решения (от нескольких секунд до нескольких минут) зависит от параметров настройки и сложности задачи.

По завершению вычислительного процесса появляется диалоговое окно Результаты поиска решения (Рис 2.31). Если результаты решения Вас удовлетворяют установите переключатель в положение Сохранить найденное решение. Для повторного запуска пакета установите – Восстановить исходные значения и попытайтесь откорректировать первое приближение.

Для сохранения протокола работы надстройки укажите тип отчета - Результаты.

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

Формулы в ячейках таблицы:

B(19) ® =СУММ(B16:B18); С(19), D(19) ® копированием B(19);

E(16) ® =ЕСЛИ(B16<=100;B4;ЕСЛИ(B16>=200;B4*(100-$G4)/100;B4*(100-$F4)/100));

E(17), E(18), F(16), F(17), F(18), G(16), G(17), G(18) ® копированием E(16);

H(16) ® ==E16*B16+F16*C16+G16*D16; H(17), H(18) ® копированием H(16);

H(18) ® =СУММ(H16:H18).

Настройки надстройки Поиск решения:

Целевая ячейка – $H$19;

Переключатель в положении: “Равной минимальному значению”;

Изменяемые ячейки –$B$16:$D$18;

Ограничения:

$B$16:$D$18=целое, $B$16:$D$18>=0, $B$19=$C$10, $C$19=$C$11, $D$19=$C$12.

Результаты оптимизации:

Фирма	Изделие 1	Изделие 2	Изделие 3	Цена изделия 1	Цена изделия 2	Цена изделия 3	Суммарные затраты
ААА							23029,00
БББ					137,75		26526,50
ВВВ				118,75	123,5		32731,00
Всего							82286,50

2.11 Перечень настраиваемых параметров надстройки “Поиск решения”

Максимальное время. Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

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

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

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

Сходимость. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит число из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков — например, 0,0001 соответствует меньшему относительному изменению по сравнению с 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения.

Линейная модель. Служит для ускорения поиска решения линейной задачи оптимизации.

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

Автоматическое масштабирования. Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине.

Показывать результаты итераций. Служит для приостановки поиска решения для просмотра результатов отдельных итераций.

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

Линейная. Служит для использования линейной экстраполяции вдоль касательного вектора.

Квадратичная. Служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач.

Разности. Служит для указания метода численного дифференцирования (прямые или центральные разности) который используется для вычисления частных производных целевых и ограничивающих функций.

Прямые. Используется в большинстве задач, где скорость изменения ограничений относительно невысока.

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

Метод. Служит для выбора алгоритма оптимизации (метод Ньютона или сопряженных градиентов) для указания направление поиска.

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

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

Загрузить модель. Служит для отображения на экране диалогового окна Загрузить модель, в котором можно задать ссылку на область ячеек, содержащих загружаемую модель.

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

После настройки панелей Поиск решения и Параметры поиска решения нажатием кнопки Выполнить на панели Поиск решения запускается процесс поиска оптимального решения.

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

В списке Тип отчета можно заказать нужную форму отчета:

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

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

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

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