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

Вторая задача после описания системы  и перечня управлений — это  членение на шаги (этапы). Иногда оно  бывает задано в самой постановке задачи (например, хозяйственные годы в экономических задачах), но часто  членение на шаги приходится вводить  искусственно. Если бы мы в этой задаче не ограничиваться самым примитивным  случаем всего двух управлений, то было бы удобнее членение на шаги произвести иначе, например, считая за «шаг» переход  с одной прямой, параллельной оси  ординат, на другую. Можно было бы вместо прямых рассмотреть окружности с  центром в точке А или же другие кривые. Все такие способы выбора наивыгоднейшего пути неизбежно ограничивают выбор возможных направлений. Если за «шаги» считать переходы с одной прямой, параллельной оси ординат, на другую, то здесь множество возможных управлений не предусматривает «пути назад», т. е. с более восточной прямой на более западную. В большинстве задач практики такие ограничения естественны (например, трудно себе представить, чтобы наивыгоднейшая траектория космической ракеты, пущенной с Земли, на каких-то участках включала движение «назад», ближе к Земле). Но бывает и другая обстановка. Например, путь по сильно пересеченной местности («серпантинная» дорога в горах) часто «петляет» и возвращается ближе к исходному пункту. При постановке задачи динамического программирования, в частности при выборе системы координат и способа членения на шаги, должны быть учтены все разумные ограничения, накладываемые на управление.

Как быть с числом шагов т? С первого взгляда может показаться, что чем больше т, тем лучше. Это не совсем так. При увеличении т возрастает объем расчетов, а это не всегда оправдано. Число шагов нужно выбирать с учетом двух обстоятельств: 1) шаг должен быть достаточно мелким для того, чтобы процедура оптимизации шагового управления была достаточно проста, и 2) шаг должен быть не слишком мелким, чтобы не производить ненужных расчетов, только усложняющих процедуру поиска оптимального решения, но не приводящих к существенному изменению оптимума целевой функции. В любом случае практики нас интересует не строго оптимальное, а «приемлемое» решение, не слишком отличающееся от оптимального по значению выигрыша W*.

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

Каково бы ни было состояние системы S перед очередным шагом, надо выбирать управление на этом шаге так, чтобы  выигрыш на данном шаге плюс оптимальный  выигрыш на всех последующих шагах  был максимальным.

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

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

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

2. Расчленить операцию на этапы  (шаги).

3. Выяснить набор шаговых управлений х_i для каждого шага и налагаемые на них ограничения.

4. Определить, какой выигрыш приносит  на i-м шаге управление х_i, если перед этим система была в состоянии S, т. е. записать «функции выигрыша»:

 

5. Определить, как изменяется состояние S системы S под влиянием управления x_i на i-м шаге: оно переходит в новое состояние

 

6. Записать основное рекуррентное  уравнение динамического программирования, выражающее условный оптимальный  выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

 

Этому выигрышу соответствует условное оптимальное управление на i-м шаге x_i(S) (подчеркнем, что в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние S' = φ (S, x)).

7. Произвести условную оптимизацию  последнего (m-го) шага, задаваясь гаммой  состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле

 

и находя условное оптимальное управление x_m(S), для которого этот максимум достигается.

8. Произвести условную оптимизацию  (m — 1)-го, (т — 2)-го и т. д. шагов по формуле, полагая в ней i = (m — 1), (m —2), ..., и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

Заметим, что если состояние системы  в начальный момент известно (а  это обычно бывает так), то на первом шаге варьировать состояние системы  не нужно — прямо находим оптимальный  выигрыш для данного начального состояния S₀. Это и есть оптимальный выигрыш за всю операцию

 

9. Произвести безусловную оптимизацию  управления, «читая» соответствующие  рекомендации на каждом шаге. Взять найденное оптимальное  управление на первом шаге х₁* = x₁ (S₀); изменить состояние системы по формуле; для вновь найденного состояния найти оптимальное управление на втором шаге x₂* и т. д. до конца.

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

 

(если только выигрыши w_i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении вместо знака «плюс» ставится знак умножения X:

 

В заключение — несколько слов о так называемых «бесконечношаговых»  задачах динамического программирования. На практике встречаются случаи, когда  планировать операцию приходится не на строго определенный, а на неопределенно  долгий промежуток времени, и нас  может интересовать решение задачи оптимального управления безотносительно  к тому, на каком именно шаге операция заканчивается. В таких случаях  бывает удобно рассмотреть в качестве модели явления бесконечношаговый  управляемый процесс, где не существует «особенного» по сравнению с другими  последнего шага (все шаги равноправны). Для этого, разумеется, нужно, чтобы  функции f_i выигрыша и функции φ_i изменения состояния не зависели от номера шага.

Заключение

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

 

 

Алгоритм

#include<iostream>

#include <cmath>

#include<conio.h>

using namespace std;

int min(int a,int b);

int cost[10][10],a[10][10],i,j,k,c;

 

int  main()

{

  int n,m;

  cout <<"enter no of vertices";

  cin >> n;

  cout <<"enter no od edges";

  cin >> m;

  cout<<"enter the\nEDGE Cost\n";

for(k=1;k<=m;k++)

{

cin>>i>>j>>c;

a[i][j]=cost[i][j]=c;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

if(a[i][j]== 0 && i !=j)

a[i][j]=31999;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

cout <<"Resultant adj matrix\n";

for(i=1;i<=n;i++)

{

for( j=1;j<=n;j++)

  {

  if(a[i][j] !=31999)

  cout << a[i][j] <<" ";

  }

cout <<"\n";

}

getch();

}

int min(int a,int b)

{

if(a<b)

return a;

else

return b;

}

 

Список литературы

1. Вентцель,Е.С.  Исследование операций: задачи, принципы, методология: учеб. пособие: для вузов. М.: Дрофа, 2006. – 206с.