Раздел 5. Решение задач оптимизации

Многие проблемы производства, проектирования, прогнозирования сводятся к широкому классу задач оптимизации, для решения которых применяются математические методы. Типовыми задачами такого плана являются, например, следующие:

– ассортимент продукции – максимизация выпуска товаров при ограничениях на сырье для производства этих товаров;

– штатное расписание – составление штатного расписания для достижения наилучших результатов при наименьших расходах;

– планирование перевозок – минимизация затрат на транспортировку товаров;

– составление смеси – достижение заданного качества смеси при наименьших расходах;

– случайные величины – различные задачи, в которые входят случайные величины;

– прочие разнообразные задачи оптимального распределения ресурсов и оптимального проектирования и т. д.

Задачу оптимизации в общем виде можно сформулировать следующим образом (табл. 16).

Таблица 16. Постановка задачи оптимизации в общем случае

№ п/п	Название	Математическая запись	Описание
	Целевая функция (критерий оптимизации)		Показывает, в каком смысле решение должно быть оптимальным, т. е. наилучшим. Возможны три вида целевой функции: максимизация, минимизация, назначение заданного значения.
	Ограничения	, – целые (для задач целочисленного программирования); – для задач с булевыми переменными	Устанавливают зависимости между переменными. Могут быть односторонними и двусторонними. При решении задач двустороннее ограничение записывается в виде двух односторонних.
	Граничные условия		Показывают, в каких пределах могут быть значения искомых переменных в оптимальном решении

Решение задачи, удовлетворяющее всем ограничениям и граничным условиям, называется допустимым. Важная характеристика задачи оптимизации – ее размерность, которая определяется числом переменных n и числом ограничений m. При n < m задачи решения не имеют.

Необходимым требованием задач оптимизации является условие n > m. Систему уравнений, для которых n = m рассматривают как задачу оптимизации, имеющую одно допустимое решение (ее можно решать как обычную задачу оптимизации, назначая в качестве целевой функции любую переменную).

Итак, задача имеет оптимальное решение, если она удовлетворяет двум требованиям:

– имеет более одного решения, т. е. существуют допустимые решения;

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

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

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

Надстройка Поиск решения запускается командой Сервис | Поиск решения. Если в меню Сервис отсутствует команда Поиск решения, следует воспользоваться командой Сервис | Надстройки и установить флажок Поиск решения. Вид диалогового окна Поиск решения приведен на рис. 21, а опции его настройки – в табл.17.

Таблица 17. Опции окна Поиск решения

Опции	Описание
Установить целевую ячейку	Указывается ячейка, содержащая целевую функцию (критерий оптимизации) рассматриваемой задачи
Равной	Следует выбрать из трех переключателей (максимальному значению, минимальному значению, значению) тот, который определяет тип взаимосвязи между решением и целевой ячейкой
Изменяя ячейки	Указываются ячейки, которые должны изменяться в процессе поиска решения задачи (т. е. ячейки, которые являются переменными задачи)
Ограничения	Отображаются ограничения, налагаемые на переменные задачи. Допускаются ограничения в виде равенств, неравенств, а также – требование целочисленности переменных. Ограничения добавляются по одному с помощью кнопки Добавить
Параметры	Позволяет изменять условия и варианты поиска решений исследуемой задачи, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач

При нажатии кнопки Параметры в окне Поиск решения открывается окно Параметры поиска решения (рис. 22), описания опций которого приведено в табл. 18.

Таблица 18. Опции окна Параметры поиска решений

Опции	Описание
Максимальное время	Ограничивает время, отпускаемое на поиск решения задачи
Предельное число итераций	Ограничивает число промежуточных вычислений
Относительная погрешность	Определяют точность, с которой ищется решение
Допустимое отклонение
Линейная модель	Служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи флажок Линейная модель должен быть сброшен, в случае линейной задачи – установлен, т. к. иначе возможно получение неверного результата
Показывать результаты итераций	Для приостановки поиска решений и просмотра отдельных итераций
Автоматическое масштабирование	Предназначен для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине. Например, при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей
Оценки	Служит для выбора метода экстраполяции
Разности	Группа предназначена для выбора метода численного дифференцирования
Метод поиска	Служит для выбора алгоритма оптимизации

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

– каковы переменные модели (для определения каких величин строится модель)?

– в чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?

– каким ограничениям должны удовлетворять неизвестные?

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

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

– ввести предварительно предположительные значения искомых переменных (иногда легко получить графическое представление решения и сделать приблизительные выводы о решении);

– в окне Параметры поиска решения снять (если установлен флажок Линейная модель.

При необходимости проводится анализ решения. Часто добавляют также представление решения в виде графиков или диаграмм. Можно получить и отчет о поиске решения. Отчеты бывают трех типов: Результаты, Устойчивость, Пределы. Тип отчета выбирается по окончании поиска решения в окне Результаты поиска решения в списке Тип отчета (можно выбрать сразу два или три типа).

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

– отчет типа Устойчивость показывает результаты малых изменений параметров поиска решения.

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