Тема 2. Оптимизационные методы получения детерминированных оценок (стр. 10 )

которая является суммой квадратичной и линейной функций.

Поставленная задача квадратичного программирования всегда может быть решена путем сведения к задаче линейного программирования с некоторыми дополнительными условиями. Основой для этого является составление функции Лагранжа и использование следствия из теоремы Куна-Таккера.

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

2.6.2. Задача о равномерной загрузке оборудования

В настоящем пункте мы рассмотрим задачу, математической моделью которой является задача квадратичного программирования. Приведем ее в максимально упрощенной формулировке.

Цех может производить продукцию двух видов и в течение трех месяцев. Потребности в продукции и равны 200т и 800т соответственно. На изготовление каждой тонны продукции в среднем затрачивается соответственно 12 и 7 часов. Общий фонд рабочего времени на каждый месяц планового периода составляет соответственно 2500, 2600 и 3000 часов. Определить план работы цеха с равномерной загрузкой по месяцам. Критерием оптимальности принять сумму квадратов разностей между среднемесячным фондом рабочего времени и временем, которое фактически необходимо для изготовления продукции в каждом месяце.

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

Следующая система неравенств содержит все допустимые варианты организации производства:

,

, , .

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

служит характеристикой равномерности загрузки оборудования в цехе.

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

Таблица 2.11

Месяцы	Продукция, т
1	0	357,14
2	0	371,43
3	200	71,43

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

2.7. Динамическое программирование

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

Предположим, что процесс управления некоторой системой состоит из шагов, и пусть – возможные состояния системы. На 1-ом шаге управление переводит систему из состояния в состояние , на 2-ом шаге управление переводит систему из состояния в состояние , и т. д., на последнем -ом шаге управление переводит систему из состояния в состояние . Процесс перехода на -ом шаге () осуществляет функция , и новое состояние определяется значениями , :

.

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

Пусть – выигрыш, полученный на -ом этапе; этот выигрыш зависит от состояния предыдущего -го этапа и управления на -ом этапе. Цель процесса управления состоит в максимизации суммарного выигрыша за все этапы, то есть максимизации целевой функции

. (2.20)

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

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