В общем виде задачу оптимизации формулируется следующим образом:
Пусть X = (x1, x2…xn) – вектор действительных переменных. Необходимо минимизировать или максимизировать целевую функцию z = f(X) при выполнении нескольких ограничений gj(X) ≤ bj, (j = 1…m), которые задаются в виде неравенств или равенств. Могут быть также добавлены условия неотрицательности переменных (xi ≥ 0), которые включаются в указанные ограничения.
Если все функции f(X) и gj(X) линейны относительно переменных xi то имеем задачу линейной оптимизации, если хотя бы одна из функций нелинейная, то получаем задачу нелинейной оптимизации.
Таким образом, задача оптимизации включает три элемента:
- переменные x1, x2…xn(в средстве Поиск решения ячейки, содержащие значения этих переменных, называются изменяемыми ячейками);
- целевая функция (ячейка, содержащая значение этой функции называется целевой ячейкой);
- ограничения (для применения средства Поиск решения ограничения могут быть записаны на рабочем листе и затем указаны в диалоговом окне либо заданы непосредственно в этом окне без записи на рабочем листе). При задании ограничений отдельно указываются функции ограничений gj(X) и вектор правых частей ограничений bj.
После формулирования математической задачи оптимизации на рабочем листе Excel создается ее табличная модель, в которой в отдельных ячейках содержатся переменные решения, в отдельные ячейки записываются формулы, по которым будут вычисляться целевая функция и функции ограничений (левые части ограничений), также в отдельных ячейках указываются значения правых частей ограничений.
После создания табличной модели задачи оптимизации для нахождения оптимального решения применяют средство Поиск решения.
Пример. Минимизирование линейной функции
Дана функция: z = 2x1 + 3x2 + 5x3.
Требуется минимизировать эту функцию при следующих ограничениях:
x1 + x2 – x3 ≥ -5,
-6x1 + 7x2 – 9x3 ≤ 4,
x1 + x2 + 4x3 = 10,
и на переменные наложены условия неотрицательности.
Для решения данной задачи средство Поиск решения используется следующим образом:
1. Создать на рабочем листе Excel табличную модель решаемой задачи, например, как на рис. 3.1:
Рис. 3.1 Табличная модель задачи линейной оптимизации
2. Открыть Поиск решения.
3. В открывшемся окне диалога Поиск решения указать данные, требуемые для процесса оптимизации (см. рис. 3.2):
- в поле “Установить целевую ячейку” ввести адрес ячейки, содержащей значение целевой функции. Для примера в это поле следует ввести E4, или щелкнуть указателем мыши по этой ячейке и адрес введется автоматически.
- в области “Равной” выбрать переключатель минимальному значению.
- в поле “Изменяя ячейки” указать ячейки, в которых содержатся переменные модели (в данном случае это диапазон B3:D3.
4. Задать ограничения – щелкнуть по кнопке “Добавить”, откроется окно диалога Добавление ограничения. Ввести ограничения поочередно, нажимая кнопку “Добавить” для каждого ограничения. После ввода всех ограничений нажать ОК для возврата в диалоговое окно Поиск решения.
Рис.3.2 Окно Поиск решения для задачи оптимизации
5. Нажать кнопку “Параметры”, откроется окно диалога Параметры поиска решения, предназначенное для задания дополнительных условий для поиска решений. Для рассматриваемого примера установить флажок “Линейная модель”, остальные параметры оставить без изменений. Нажать ОК для возврата в диалоговое окно Поиск решения.
6. После задания всех необходимых данных нажать кнопку “Выполнить”. Средство Поиск решения выполнит оптимизацию. В процессе вычислений в строке состояния отображаются число итераций и значения целевой функции при переборе множества допустимых решений задачи.
7. Если в табличной модели нет ошибок, то будет выведено на экран диалоговое окно Результаты поиска решения(см. рис. 3.3), которое сообщает о завершении поиска. При нахождении оптимального решения в диалоговом окне должны присутствовать два ключевых предложения: Решение найдено. Все ограничения и условия оптимальности выполнены. Если хотя бы одного из предложений нет, программе не удалось оптимизировать модель. В этом случае следует сначала проверить правильность ввода данных, затем табличную модель и, наконец, пересмотреть исходную формулировку задачи.
Рис. 3.3 Окно результатов поиска решения
8. В случае оптимального решения выбрать переключатель Сохранить найденное решение и нажать ОК. Кроме того есть возможность выбрать Восстановить исходные значения, что приведет к отказу от решения и восстановлению исходных значений в изменяемых ячейках, а также получить три типа отчетов (выбрав тип в списке Тип отчета) с результатами поиска решения.
Типы отчетов:
1. В отчете Результаты выводятся исходные и полученные в результате поиска решения значения изменяемых ячеек и целевой функции, а также сведения об ограничениях задачи.
2. Отчет Устойчивость дает основную информацию для анализа чувствительности моделей. Этот анализ показывает, насколько чувствительно найденное оптимальное решение к небольшим изменениям параметров модели.
3. Отчет Пределы показывает наименьшее и наибольшее значения, которые может принимать каждая переменная решения при удовлетворении ограничений и при постоянстве значений всех остальных переменных.
