Решение: X(0)=(0,0,11/2,5/2,5,0) 
 
 
 
 

4.Метод  обратной прогонки 

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

Прямая  прогонка: от первого шага к последнему.

Обратная  прогонка: от последнего шага к первому.

На стадии безусловной оптимизации определяются безусловные оптимальные управления для каждого шага

Прямая  прогонка: от последнего шага к первому.

Обратная  прогонка: от первого шага к последнему.

Рассмотрим  метод обратной прогонки

В основе метода лежит принцип оптимальности Беллмана:

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

Уравнение состояния: Si=Si(Ui,Si-1)  - система перешла в состояние Si из состояния Si-1 под управлением Ui, при этом получен выигрыш fi(Ui,Si-1).

Wi+1(Si) - оптимальный выигрыш на последующих шагах.

- выигрыш на этом шаге и  на всех последующих.

Согласно принципу Беллмана управление Ui надо выбрать так, что эта сумма была максимальной.

Условная  оптимизация

  - основное функциональное уравнение.

- функциональное уравнение для  последнего шага.

Безусловная оптимизация

Если начальное  состояние задано, то .

Если  начальное состояние не задано, но сказано, что оно принадлежит  какому-либо множеству, то . 

Max f=50X1+30X2+45X3

{2X1+3X2+X3=15

(Xi>=0 

S0=15

S1=S0-2X1

S2=S1-3X2

S3=S2-X3 

Функция управления

Wi(Si-1)=max{fi+Wi+1(Si)}

0<Xi<[Si-1/Vi] 
 

УО:

3шаг

W3(S2)=max{45X3} 0<=X3<=S2

Max=45S2 при X3=S2 

2шаг

W2(S1)=max{30X2+45S2} при 0<=X2<=[S1/3]

=max{30X2+45(S1-3X2)}={45S1-105X2}

при 0<=X2<=[S1/3] 

1шаг

W1(S0)=max{50X1+45S1} при 0<=X1<=[S0/2]=7

=max{50X1+45(15-2X1)}=max{45*15-40X1} 

БУО: 
Wmax=675 S0=15=>X1=0=>S1=15=>X2=0=>S2=15=>X3=15 

Решение: (0,0,15) 

УО:

4шаг

W4(S3)=maxf4(X4) 0<=X4<=S3

=f4(S3) X4=S3  

БУО:

S0=120 Wmax=W1(120)=18

S0=120->X1=40->S1=80->X2=40->S2=40->X3=0->S3

=40->X4=40->S4=0 

Решение: X=(40,40,0,40) 
 

5. Метод Куна-Такера 

Max f=2X1+4X2-X1^2-2X2^2 

{X1+2X2<=8

{2X1-X2<=12

{X1,X2>=0 

F=-X1^2-2X2^2

d11=-1 d22=-2 d12=0 d21=0

f’(x)=Q=(-2 0) Λ1=-2 Λ2=8 => F-отрицательно

              (0 -4)

определенная  => F-выпуклая вверх => f-выпуклая вверх 

Функция Лагранжа

L(x,λ)=2X1+4X2-X1^2-2X2^2+λ1(8-X1-2X2)+λ2(12-2X1+X2)

Условия Куна-Таккера

     dL/dX1=2-2X1-λ1-2λ2<=0

     X1(2-2X1-λ1-2λ2)=0 

     dL/dX2=4-4X2-2λ1+λ2<=0

     X2(4-4X1-2λ1+λ2)=0 

     dL/dλ1=8-X1-2X2>=0

     λ1(8-X1-2X2)=0 

     dL/dλ2=12-2X1+X2>=0

     λ2(12-2X1+X2)=0

 

     λi>=0, Xi>=0

     2X1+λ1+2λ2-U1=2    X1U1=0

     4X2+2λ1-λ2-U2=4    X2U2=0

     X1+2X2+V1=8          λ1V1=0

     2X1-X2+V2=12        λ2V2=0 

 

Хопт=(1,1) fmax=(подставляем Хопт в L)=3 
 
 
 
 

Min f=x1^2+X2^2-X1-8X2 

{X1+X2<=7

{X2<=5 
{X1, X2>=0 
 

F=X1^2+X2^2

d11=1 d22=1 d12=0 d21=0

f’(x)=Q=(2 0)

              (0 2) Λ1=2 Λ2=4 => F-положительно

определенная 

Функция Лагранжа

L(x,λ)=X1^2+X2^2-X1-8X2+λ1(X1+X2-7)+λ2(X2-5)

Условия Куна-Таккера

     dL/dX1=2X1-1+λ1>=0

     X1(2X1-1+λ1)=0 

     dL/dX2=2X2-8+λ1+λ2>=0

     X2(2X2-8+λ1+λ2)=0 

     dL/dλ1=X1+X2-4<=0

     λ1(X1+X2-4)=0 

     dL/dλ2=X2-5<=0

     λ2(X2-5)=0

 

     λi>=0, Xi>=0

    2X1+λ1-U1=1          X1U1=0

     2X2+λ1+λ2-U2=8    X2U2=0

     X1+X2+V1=7          λ1V1=0

     X2+V2=5                λ2V2=0 

 

Хопт=(1/2,4) fmin=(подставляем Хопт в L)=-16¼ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

6.Сетевое  планирование 

ПР-предшествующие работы

НВВВ-наиболее вероятное время выполнения

НмВВ-наименьшее время выполнения

НбВВ-наибольшее время выполнения

ПРС-потребность  в рабочей силе