Определение седловой точки

1. Запишем функцию Лагранжа (3.20), для чего составим линейную комбинацию заданных целевой функции и левых частей ограничений – неравенств, умноженных на дополнительные неизвестные – множители Лагранжа , , в соответствии с постановкой задачи (3.5), (3.6):

; λ)= + + (2 - 5 +7)+ ( 3 +15)+ (4 +7 71). (3.26)

2. Находим частные производные:

= 2 + 2 3 + 4 , (3.27)

= 2( 5) 5 +7 , (3.28)

= 2 5 7, (3.29)

= 3 +15, (3.30)

= 4 +7 71. (3.31)

3. Используем условия (3.24) и (3.25). Поскольку = 3, = 6, то для выполнения условия = 0 требуется, чтобы = 0, поэтому из (3.27) следует

2 + 2 3 +4 = 0 (3.32)

или 2 3 + 4 = 6.

Аналогично из (3.28) имеем:

5 +7 = 2 (3.33)

4. Анализируем (3.25).

= 2 5 7= 2 3 5 6 +7 .

Следовательно, для выполнения = 0 необходимо, чтобы = 0.

Аналогично, поскольку

= 4 +7 71= 4 3 + 7 6 71≠ 0, то = 0.

В то же время = 3 + 15= 3 36 + 15 = 0, следовательно может быть не равным 0.

5. Из (3.32) и (3.33) находим :

= 0, = 0.

Очевидно, что

= 2.

6. Таким образом, искомая седловая точка имеет координаты:

(, ) = (3; 6; 0; 2; 0).

7. Проверка. Седловая точка (, ) должна соответствовать условию (3.22).

Имеем:

(, λ)= 10 17( + ),

(, )= 10,

( ) = + +10.

Поскольку

(, λ) < (, ) = ( ),

условие выполнено.

8. Ответ: (, ) = (3; 6; 0; 2; 0).

Задача №4

Двум предприятиям и выделено = 1000 денежных единиц средств на 4 года.

Как распределить эти средства между предприятиями в начале каждого года их работы, например, предприятию выделить средств, предприятию средств, = 1, 2, 3, 4, , чтобы общий доход за 4-х летний период был бы максимальным, если известно, что предприятие за один год работы обеспечивает доход () = 5 и остаток к концу года () = 0,3 , а предприятие , соответственно, ()= 4 и ()= 0,5 .

Задачу решить методом динамического программирования.

Анализ условия задачи

Основные теоретические сведения: Принцип оптимальности Беллмана. Функциональные (рекуррентные) уравнения динамического программирования.

По условию задачи на м году работы в результате распределения средств на величины и получим доход () и остаток средств () от первого предприятия и, соответственно, () и () от предприятия . Очевидно, что для дальнейшего распределения на +1 – й год имеем () + () средств, остаток от которых в конце +1 го года перейдет на +2 й год и опять будет перераспределён. Заданные функции (), (), (), (), k =1, 2, 3, 4, где , определены в области 0 ≤ ≤ , а функция () + () удовлетворяет неравенству 0 ≤ ()+ () ≤ .

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

Максимальное значение целевой функции (, , ), получаем в результате построения оптимального управления шаг за шагом. Целевая функция выражает общий доход двух предприятий к концу 4-х лет работы в зависимости от выделяемых каждому предприятию средств и , соответственно, на начало каждого года – шага построения оптимального управления. Идея постепенной, пошаговой оптимизации системы сформулирована Беллманом в виде общего принципа оптимальности: каково бы ни было состояние некоторой системы после 1 шагов, управление на м шаге должно выбираться так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах с 1 го до го включительно был максимальным (обеспечивал экстремум целевой функции).[1].

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

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

() = () + ()],

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

В задаче рассматривается производственно экономическая управляемая система – сумма средств , выделяемых двум предприятиям; её состояние перед каждым шагом управления характеризуется двумя параметрами: средствами каждого из предприятий.

В соответствии с принципом оптимальности планировать многошаговую операцию по распределению выделенных двум предприятиям средств необходимо не так, чтобы общий доход по окончании некоторого года был бы максимальным, а так, чтобы максимальной была сумма доходов по окончании некоторого года и всех оставшихся лет до конца 4-х летнего периода работы предприятий. Однако, существует единственный из всех шагов планирования распределения средств, на котором будет получен наибольший доход без учета всех последующих шагов. Очевидно, что таким шагом является последний шаг – планирование распределения средств между двумя предприятиями на начало их 4-го года работы. Поэтому процесс динамического программирования строится от конца к началу: от распределения средств на начало 4-го года переходим к распределению средств на начало 3-го года, затем – 2-го и, наконец, 1-го года работы предприятий.[2].

В математической форме принцип оптимальности Беллмана реализуется с помощью составления и поиска максимума целевой функции ():

() = [ () + () + ()]. (1)

0≤ ≤

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

1) при , () = [ () + ()], , (2)

0≤ ≤

2)при , , …, (), () = { () +

0≤ ≤

()+ [ ()+ () }, (3)

где ()+ () = остаток средств к концу го года.

Выражение (1) (3) позволяют определить средства и , выделяемые предприятиями в результате оптимального управления их суммой .

Дата добавления: 2014-12-24