91140

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Лекция

Информатика, кибернетика и программирование

Оптимальное решение 12 млн если для предприятия 1 выбрать второй проект. При этом необходимо вложить 1 млн и возможно получение дохода 3 млн. Таким образом остается 51=4 млн на все остальные предприятия Общий доход 3 млн Анализируем таблицу 5. Оптимальное решение при 4 млн составляет 9 млн если для предприятия 2 выбрать первый проект хотя можно выбрать и второй проект – тоже 9 млн.

Русский

2015-07-13

749.5 KB

0 чел.

PAGE  1

Лекция 11

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

3.1. Многоэтапные процессы принятия решений

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

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

Рассмотрим сначала простую задачу поиска оптимального пути на двумерной прямоугольной сетке, в которой разрешены переходы из одного узла в другой только по горизонтали (вправо) или по вертикали (вверх).

Заданы затраты на каждый из возможных переходов и требуется найти путь с минимальными суммарными затратами из левого нижнего угла сетки (рис. 33, точка А)

в правый верхний угол (точка В). Такой путь называется оптимальным.

Узлы сетки пронумерованы так, как показано на рис. 33, где тип задают соответственно вертикальный и горизонтальный размеры сетки.

Затраты на переход в узел i, j no горизонтали) составляют gij а по вертикали— Vjj. В точке А соответствующие величины равны нулю. Таким образом, исходными данными в этой задаче являются: m, n и все шаговые затраты gij и vij (i = О, 1, 2, ..., m; j - 0, 1, 2, ..., п).

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

Общее число шагов К можно выразить как

Уже при m = n=10

К=184 756.

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

Действительно, если первый шаг выбрать по вертикали в точку С (затраты 1 против 5), то в итоге после второго шага получим суммарные затраты равные 101, а при выборе на первом шаге «неоптимального» решения (точка D) суммарные затраты равны всего лишь 6.

Поиск оптимального пути можно рассматривать как многошаговый процесс. На первом шаге находимся в точке А и имеем две возможности: пойти вверх или направо. Сделать выбор нельзя, так как нужно учитывать последствия этого выбора. При любом выборе, попадем мы в точку (0.1) или (1,0), встанет та же задача выбора из двух возможностей и опять выбор сделать нельзя. Однако существуют точки, находясь в которых мы не имеем выбора. Эти точки С и D находятся в одном шаге от последней точки В (рис. 35).

Для каждой из этих точек запомним затраты на оставшийся путь и рассмотрим предпоследний шаг. В двух шагах от финиша мы можем быть в точках Е, F или G. В точках Е и G выбора нет, и мы просто запомним для каждой из них суммарные затраты на весь оставшийся путь. На рис. 35 это 10 для точки Е и 8 для точки G. А что делать, если мы в двух шагах от финиша окажемся в точке F? Ответ кажется простым: надо идти в точку С, а не в точку D, так как, несмотря на то что на предпоследнем шаге затраты больше (2 против 1), с учетом затрат на оставшийся путь (4 против 7) суммарные затраты на путь до точки В окажутся меньше (6 против 8). Конечно, из точки F надо идти в точку С, но при одном непременном условии: ничто не может помешать нам это сделать, нет никакой связи с тем, как мы попали в данную точку или,

как говорят, нет «предыстории».

В нашей задаче такой связи нет. но в более сложных задачах она вполне возможна. Например, могло быть задано дополнительное условие: суммарное количество изменений направления (поворотов) не больше заданного числа. Тогда мы, во-первых, должны знать сколько было сделано поворотов до попадания в точку F и каким образом (по горизонтали или по вертикали) мы попали в эту точку, т.е. должны знать предысторию. Может оказаться, что мы попали в точку F по горизонтали и уже исчерпали заданный «лимит» поворотов, тогда переход из точки F в точку С просто невозможен, так как это уже лишний поворот. Получается, что сделать оптимальный выбор в точке F нам может помешать предыстория.

В точке F мы запомним затраты на весь оставшийся путь при условии, что выбран оптимальный вариант: переход в точку С. Сделав еще шаг назад, т.е. оказавшись за три шагд до финиша, мы увидим, что ситуация полностью аналогична предыдущей. Выбора или нет (точки на крайней верхней или крайней правой стороне сетки), или есть две возможности, но для каждой из них уже известны последствия выбора. Так, оказавшись в точке М, мы выберем не точку F, для которой затраты до конца пути равны 6, а казавшуюся бесперспективной точку Е. Для нее эти затраты равны 10, но суммарные затраты на весь оставшийся путь меньше (13 против 14). При этом выборе мы решаем совсем простую задачу: суммируем затраты на каждый из возможных переходов на данном шаге (в точку Е или в точку F) с уже известными затратами на дальнейший путь по оптимальному для выбранной точки варианту. Поступая аналогичным образом, мы рано или поздно в своем обратном движении. придем в начальную точку А (рис. 36). Но при этом уже будут известны последствия для каждого из вариантов выбора (пойти по вертикали в точку К или по гори-чомтали в точку L), так как для каждой из них уже вычислены и записаны затраты на весь оставшийся путь до точки В. Эта ситуация аналогична той, что представлена на рис. 34.

Теперь ничто не мешает нам сделать выбор, куда идти из точки А. Просуммируем затраты из А в К с тем, что записано для точки К на весь оставшийся путь от К до В. Затем просуммируем затраты из А в L с тем, что записано для L на путь из L в В, выберем наименьшую из сумм, которая и будет равна суммарным затратам по оптимальному пути. В примере на рис. 36 получаем для точки К 99, а для точки L 100, и, следовательно, теперь ясно, что идти надо в точку К. Но нам нужны не только эти минимальные из всех возможных затраты, но и сам оптимальный путь. Пока мы знаем, куда идти из точки А иа первом шаге. А дальше? Дальше знаем только затраты на весь оставшийся путь. Чтобы не оказаться в такой ситуации неопределенности, при записи затрат на оставшийся путь в каждой из промежуточных точек (С. D, R, I, G, М, и т.д. рис. 35) нужно записывать и сделанный выбор: куда идти из этих точек. Когда из точки А выберем точку К или L, в любой из них уже будет записано, куда идти (по вертикали или по горизонтали, т.е. 1 или 0) и т. д. Обратным разворотом мы дойдем до точки В и восстановим оптимальный путь.

Заметим, что если при сравнении вариантов на любом из этапов попадутся два варианта с равными затратами, то можно выбрать любой из них. Это означает, что оптимальный путь может быть не единственным.

3.2. Принцип оптимальности Беллмана

«Если в каждом из состояний дальнейшее поведение системы не зависит от того, как она попала в это состояние, то дальнейшая траектория должна быть оптимальной».

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

Основой  принципа Беллмана является рекуррентное соотношение (Уравнение Беллмана)

Максимальный годовой доход на J шаге рассчитывается как мах от возможных доходов R от всех проектов на этом шаге плюс доходы на последующем шаге J+1 шаге, которые складываются из анализа оставшихся денег от всех возможных комбинаций проектов (Yj –Сj(Xj)).

ПРИМЕР

Аналитическая реализация принципа Беллмана

Обозначим:

Получение решения задачи

Анализируем таблицу 6. Оптимальное решение 12 млн, если для предприятия 1 выбрать второй проект.

При этом необходимо вложить 1 млн и возможно получение дохода 3 млн. Таким образом остается 5-1=4 млн на все остальные предприятия

Общий доход 3 млн

Анализируем таблицу 5. Оптимальное решение (при 4 млн) составляет 9 млн, если для предприятия 2 выбрать первый проект, хотя можно выбрать и второй проект – тоже 9 млн. Таким образом при выборе первого проекта остается 4-0=4 млн на все остальные предприятия

Общий доход 3+0=3 млн

Анализируем таблицу 4. Оптимальное решение при 4 млн составляет 9млн, если для предприятия 2 выбрать третий проект. Таким образом остается 4-2=2 млн на все остальные предприятия

При этом необходимо вложить 2 млн и возможно получение дохода 6 млн.

Общий доход 3+6=9 млн

Анализируем таблицу 3. Оптимальное решение при 2 млн составляет 3млн, если для предприятия 1 выбрать второй проект. Таким образом остается 2-2=0 млн.

Общий доход 9+3=12 млн

Т.О. распределение инвестиций

1 предприятие

2 предприятие

3 предприятие

4 предприятие

Проект2

Проект 1

Проект 3

Проект2

Общая прибыль 12 млн при вложенных 4 млн

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

РАСШИРЕННЫЕ ПОЯСНЕНИЯ


 

А также другие работы, которые могут Вас заинтересовать

84449. Урок розвитку мовлення «Прийшла зима – чарівниця» 44.5 KB
  Мета: вчити учнів самостійно складати розповідь, казку на основі допоміжних слів та даного плану; вчити правильно будувати текст, речення; розвивати спостережливість, образне мислення; усне та писемне мовлення; виховувати любов до природи, прагнення до творчості.
84450. Правильна вимова слів із глухими приголосними. Складання казки за серією малюнків 72.5 KB
  Мета: працювати над засвоєнням правил вимови слів із глухими приголосними; розвивати вміння спостерігати аналізуватибудувати текст за малюнками розвивати мовлення; виховувати повагу до народних традицій. Обладнання: картки із словами та віршами прислів’’я сюжетні малюнки.
84451. Весна прийшла 52 KB
  Мета. Розвивати у дітей мислення, вміння передавати свої думки зв’язним мовленням (усним та писемним), робити узагальнення, висновки, розвивати фантазію. Виховувати любов до природи, бережливе ставлення до неї.
84452. Закріплення й узагальнення знань про прикметник 49.5 KB
  Мета: закріпити і узагальнити знання з теми, збагачувати словниковий запас учнів; розвивати творче мислення; виховувати бережне ставлення до природи. Обладнання: малюнок «Весна», квіти, ребуси, ілюстрації, індивідуальні картки, ігри, телеграма.
84453. Загальне поняття про іменник. Іменники,що означають назви істот та назви неістот 42.5 KB
  Мета: розширити знання про іменник;вдосконалювати вміння виділяти його серед інших частин мови через правильно поставлене запитання; ознайомити з термінами назви істот і назви неістот; розвивати словниковий запас учніввиховувати навички грамотного письма.
84454. Узагальнення вивченого про частини мови 33.5 KB
  Розвивати навички відрізняти частини мови за їх лексичним значенням. Сьогодні на аукціоні незвичайний товар На моєму столі лежать картки з написаними назвами частин мови. Довірена особа від кожної групи розповідає про частину мови іменник.
84455. Складання розповіді за власним спостереженням «Жовте листячко летить, під ногами шелестить» 49.5 KB
  В жовтий лист пофарбувала Урожай з полів зібрала Золотила вербам коси Чарівна цариця Осінь Такце осінь вхід під музику дівчинки-осені Читання вірша: А я ішла по жовтим килимам По золотим червоним і багряним. Я –- осінь. Я –- осінь золота з легким туманом. Таке високе Як не милуватись...
84456. Слова з прямим і переносним значенням 38 KB
  Мета: формувати в учнів поняття про пряме і переносне значення слів; виробляти вміння визначати значення слова в тексті самостійно вживати слова в переносному значенні; розвивати мовне чуття навчити учнів зв’язно висловлювати свої думки.
84457. Зміна прикметників за зразком «один-багато» 147.5 KB
  Мета: активізувати знання учнів про прикметник. Формувати поняття про прикметник на основі істотних ознак (питання, значення, роль у реченні). Розвивати фонематичний слух, орфографічну грамотність. Виховувати любов до рідного краю, спадщини предків, пошани до народних традицій.