5. Условный экстремум. Метод Лагража

Задача 5.

На развитие двух предприятий, входящих в производственное объединение, выделено2 млн.долл. Если первому предприятию выделить млн.долл, то прибыль, полученная от этого предприятия, будет равна млн.долл; если млн.долл. выделить второму предприятию, по прибыль от него будет равна млн.долл.

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

Решить задачу методом множителей Лагранжа.

Решение:

Составим математическую модель данной задачи. Для этого сначала введем переменные:

(млн.долл.) - количество денежных средств, выделяемых первому предприятию;

(млн.долл.) - количество денежных средств, выделяемых второму предприятию.

Затем запишем выражение целевой функции, имеющей смысл суммарной прибыли производственного объединения:

.

Далее составим уравнение связи: и представим его в стандартной форме .

В результате получаем задачу условного максимума функции двух переменных при ограничении типа равенства. Для решения этой задачи применим метод Лагранжа ([4], [5]).

Составим функцию Лагранжа

,

где - числовой параметр, называемый множителем Лагранжа.

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

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

, , ;

, , , .

Корень является посторонним; поэтому , , .

Получаем единственную стационарную точку функции Лагранжа .

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

Находим: , ;

; ;

;

, , , , ;

.

Так как дискриминант функции Лагранжа в стационарной точке отрицателен, то в соответствии с достаточным условием условного максимума функция имеет при , условный максимум. Значение целевой функции в точке условного максимума

.

Таким образом, наибольшая суммарная прибыль производственного объединения (млн.долл.) достигается при следующем распределении денежных средств между предприятиями:

млн.долл. и млн.долл.

6. Оптимальное распределение капиталовложений. Метод динамического программирования

Задача 6. В производственное объединение входят при предприятия. Прирост продукции каждого из них в зависимости от величины выделенных предприятию капиталовложений указан в приведенной ниже таблице.

	предпр. 1	предпр. 2	предпр. 3
0	0	0	0
20	3	2	1
40	3	4	6
60	8	4	7
80	9	7	10
100	10	12	11

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

Капиталовложения (в усл.ден.ед.) каждому предприятию могут быть выделены только в размерах кратных 20 (усл.ден.ед.), и общий объем капиталовложений составляет (усл.ден.ед.).

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

Решение:

Составим математическую модель данной задачи оптимального распределения ресурсов. Для этого сначала введем переменные:

- количество денежных средств, выделяемых -му предприятию ;

- соответствующий прирост выпуска продукции -го предприятия .

Затем запишем выражение целевой функции, имеющей смысл суммарного прироста выпуска продукции всего производственного объединения:

(1)

Далее запишем ресурсное ограничение

. (2)

По смыслу задачи переменные должны быть неотрицательными:

, , . (3)

В результате получаем математическую формулировку задачи:

Найти такие значения переменных , , , которые удовлетворяют ограничениям (2), (3) и доставляют наибольшее значение целевой функции (1).

Решение поставленной задачи методом динамического программирования Беллмана содержит следующие основные этапы ([6]):

1) Вложение данной конкретной задачи в семейство подобных задач (инвариантное погружение задачи);

2) Составление уравнения Беллмана, исходя из принципа оптимальности Беллмана;

3) Решение уравнения Беллмана;

4) Выделение решения исходной задачи из найденной функции Беллмана.

Перейдем к реализации указанных этапов.

1) Вместо одной исходной задачи (1)-(3) с заданным значением суммарного ресурса и числом предприятий рассмотрим семейство подобных задач с изменяющимся значением суммарного ресурса и изменяющимся числом предприятий :

, (4)

, (5)

. (6)

Введем функцию 2-х переменных - функцию Беллмана

,

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

2) Принцип оптимальности многошагового процесса впервые был сформулирован Р. Беллманом и заключается в следующем: завершающая часть процесса должна быть оптимальной относительно текущего реализовавшегося состояния. Математическим выражением этого принципа для данной задачи является уравнения Беллмана ([6]):

, (8)

где , .

3) Уравнение Беллмана имеет очевидное краевое условие

(9)

Зная , из уравнения (8) последовательно находим:

,

где в силу краевого условия (9);

.

При этом на каждом шаге решается стандартная задача нахождения наибольшего значения функции одной переменной на отрезке .

Приведем табличную реализацию изложенного выше решения уравнения Беллмана.

4) Выделим решение исходной задачи из найденной выше функции Беллмана , организовав так называемую "попятную" процедуру.

Сначала найдем оптимальное значение переменной . Для этого в последнем соотношении для положим :

(10)

и найдем то значение на котором достигается максимум в правой части соотношения (10). По таблице 2 определяем , и это наибольшее значение достигается при .

После выделения единиц ресурса третьему предприятию на остальные два предприятия (второе и первое) следует распределить оставшийся ресурс .

Положим в предпоследнем соотношении для :

(11)

и найдем то значение , на котором достигается максимум в правой части соотношения (11). По таблице 1 определяем , и это наибольшее значение достигается при .

Оптимальное значение первой переменной найдем из условия

, (12)

т.е. .

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

, , (усл.ден.ед.)