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

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

Динамическое программирование (иначе  «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так  называемым «многошаговым» операциям.

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

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

где  — выигрыш на i-м шаге.

Если W обладает таким свойством, то его называют «аддитивным критерием».

Операция Ò, о которой идет речь, представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой х, а шаговые управления — буквами х₁, x₂, ..., х_т:

Следует иметь в виду, что х₁, x₂, ..., х_т в общем случае — не числа, а, может быть, векторы, функции и т. д.

Требуется найти такое управление х, при котором выигрыш W обращается в максимум:

То управление х*, при котором этот максимум достигается, будем называть оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений:

Тот максимальный выигрыш, который достигается  при этом управлении, мы будем обозначать W*:

Формула (12.5) читается так: величина W* есть максимум из всех W(x) при разных управлениях х (максимум берется по всем управлениям х, возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут:

Рассмотрим  несколько примеров многошаговых опе-раций  и для каждого из них поясним, что понимается под «управлением»  и каков «выигрыш» (показатель эффективности) W.

1. Планируется  деятельность группы промышленных  предприятий П₁, П₂, ..., П_k на период т хозяйственных лет m-летку). В начале периода на развитие группы выделены какие-то средства М, которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы, суммарный доход за т лет был максимальным?

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

и, значит, обладает свойством аддитивности.

Управление х_i на i-м шаге состоит в том, что в па-чале i-гo года предприятиям выделяются какие-то средства х₁, x₂, ..., х_ik (первый индекс — номер шага, второй — номер предприятия). Таким образом, шаговое управление есть вектор с k составляющими:

Разумеется, величины w_t в формуле  зависят от количества вложенных в предприятия средств.

Управление х всей операцией состоит из совокупности всех шаговых управлений:

Требуется найти такое распределение средств  по предприятиям и по годам (оптимальное  управление х*), при котором величина W обращается в максимум.

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

2. Космическая ракета состоит  из т ступеней, а процесс ее вывода на орбиту — из т этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:

где G_i — вес i-й ступени.

В результате i-ro этапа (сгорания и сбрасывания i-й ступени) ракета получает приращение скорости Δ_i, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет 

где Δ_i — выигрыш (приращение скорости) на i-м шаге. Управление х представляет собой совокупность весов всех ступеней G_i:

Оптимальным управлением х* будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление — одно число, а именно, вес данной ступени.

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

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

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

С первого взгляда идея может  показаться довольно тривиальной. В  самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, раз бить ее па ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать  на этом шаге такое управление, чтобы  эффективность этого шага была максимальна. Не так ли?

Нет, вовсе не так! Принцип динамического  программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое  управление должно выбираться дальновидно, с учетом всех его последствий  в будущем. Что толку, если мы выберем  на данном шаге управление, при котором  эффективность этого шага максимальна, если этот шаг лишит нас возможности  хорошо выиграть на последующих шагах?

Пусть, например, планируется работа группы промышленных предприятий, из которых  часть занята выпуском предметов  потребления, а остальные производят для них машины. Задача операции — получить за т лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение — расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и па производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.

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

Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться  попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно  планировать так, чтобы он сам, как  таковой, принес наибольшую выгоду.

Поэтому процесс динамического  программирования обычно разворачивается  от конца к началу: прежде всего  планируется последний, m-й шаг. А  как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых  мы приступаем к последнему шагу?

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

Предположим, что мы это сделали, и для каждого из возможных  исходов предпоследнего шага знаем  условное оптимальное управление и  соответствующий ему условный оптимальный  выигрыш на m-м шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, (т — 1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (т — 2)-й шаг, и для каждого из этих предположений найдем такое управление на (т — 1)-м шаге, при котором выигрыш за последние два шага (из которых т-й уже оптимизирован!) максимален. Так мы найдем для каждого исхода (m — 2)-го шага условное оптимальное управление на (m—1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, «пятясь назад», оптимизируем управление на (т — 2)-м шаге и т. д., пока не дойдем до первого.

Предположим, что все условные оптимальные  управления и условные оптимальные  выигрыши за весь «хвост» процесса (на всех шагах, начиная от данного  и до конца) нам известны. Это значит: мы знаем, что надо делать, как управлять  на данном шаге и что мы за это  получим на «хвосте», в каком бы состоянии ни был процесс к  началу шага. Теперь мы можем построить  уже не условно оптимальное, а  просто Оптимальное управление х* и найти не условно оптимальный, а просто оптимальный выигрыш W*. В самом деле, пусть мы знаем, в каком состоянии S₀ была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление х₁* на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S₁*; в этом состоянии мы подошли ко второму шагу.

Тогда нам тоже известно условное оптимальное управление х₂*, которое к концу второго шага переводит систему в состояние S₂*, и т. д. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге.

Таким образом, в процессе оптимизации  управления методом динамического  программирования многошаговый процесс  «проходится» дважды: первый раз —  от конца к началу, в результате чего находятся условные оптимальные  управления и условные оптимальные  выигрыши за оставшийся «хвост» процесса; второй раз — от начала к концу, когда нам остается только «прочитать»  уже готовые рекомендации и найти  безусловное оптимальное управление х*, состоящее из оптимальных шаговых управлений x*, х*, ..., х*.

Первый этап — условной оптимизации  — несравненно сложнее и длительнее второго. Второй этап почти не требует  дополнительных вычислений.  

Задача динамического  программирования в общем виде

Рассмотренные выше простейшие задачи динамического программирования дают понятие об общей идее метода: пошаговая  оптимизация, проходимая в одном  направлении «условно», в другом — «безусловно». Метод динамического  программирования является очень мощным и плодотворным методом оптимизации  управления; ему не страшны ни целочисленность  решения, ни нелинейность целевой функции, ни вид ограничений, накладываемых  на решение. Но в отличие от линейного  программирования динамическое программирование не сводится к какой-либо стандартной  вычислительной процедуре; оно может  быть передано па машину только после  того, как записаны соответствующие  формулы, а это часто бывает не так-то легко.

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

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

Если, как это обычно и бывает, состояние системы описывается  многими параметрами (так называемыми  «фазовыми координатами»), то становится трудно перед каждым шагом перебрать  все их варианты и для каждого  найти оптимальное условное управление. Последнее еще больше затрудняется в случае, когда число возможных  вариантов управления велико. В этих случаях над нами повисает, по меткому  выражению Р. Беллмана, «проклятие многомерности»—бич не только метода динамического программирования, но и всех других методов оптимизации. Обычно задачи динамического программирования решаются не вручную, а на ЭВМ, однако многие такие задачи не под силу даже современным машинам. Поэтому  очень важно уметь правильно  и «скромно» поставить задачу, не переобременяя ее лишними подробностями, упрощая елико возможно описание управляемой системы и вариантов  управления. Так что в методе динамического  программирования очень многое зависит  от искусства и опыта исследователя.

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

Как быть с числом шагов т? С первого взгляда может показаться, что чем больше т, тем лучше. Это не совсем так. При увеличении т возрастает объем расчетов, а это не всегда оправдано. Число шагов нужно выбирать с учетом двух обстоятельств: 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с.