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 млн

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

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


 

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

47439. Регенерация 37.5 KB
  Тема: Регенерация План. Регенерация как процесс поддержания морфофизиологической целостности биологических систем на уровне организма. Физиологическая регенерация Репаративная регенерация
47440. Гомеостаз и его проявление на разных уровнях организации биосистем 62.5 KB
  Понятие гомеостаза Основные компоненты гомеостаза. Системные механизмы гомеостаза. Эндокринные механизмы гомеостаза.
47441. Биологическая эволюция. Основы теории эволюции 89 KB
  Основы теории эволюции. Дарвина о механизмах эволюции живой природы. Синтетическая теория эволюции. Учение о микроэволюции
47442. Действие элементарных эволюционных факторов в популяциях людей 93.5 KB
  Тема: Действие элементарных эволюционных факторов в популяциях людей План. Популяция людей. Генетическое разнообразие в популяциях людей Генетический груз в популяциях людей
47443. Макроэволюция 64.5 KB
  Направления эволюции. Типы эволюции групп. Правила эволюции групп. Процесс макроэволюции связан непосредственно с явлениями микроэволюции и является их обобщенным выражением.
47444. Общие закономерности в эволюции органов и систем 61 KB
  Тема: Общие закономерности в эволюции органов и систем. Эволюция органов и функций 2. Дифференциация и интеграция в эволюции органов 3. Закономерности морфофункциональных преобразований органов 3.
47445. Филогенез систем органов хордовых. Наружные покровы. Опорно-двигательный аппарат 59 KB
  Онтогенез покровов млекопитающих и человека отображает их эволюцию по типу архаллаксиса. Онтогенез осевого скелета человека рекапитулирует основные филогенетические стадии его становления: в периоде нейруляции закладывается хорда заменяющаяся впоследствии хрящевым а затем и костным позвоночником. Нарушение онтогенеза осевого скелета у человека может выразиться в таких атавистических пороках развития как несрастание остистых отростков позвонков в результате чего формируется spin bifid дефект позвоночного канала. зародыш человека обладает...
47446. Филогенез систем органов хордовых. Пищеварительная система. Дыхательная система. Кровеносная система 85 KB
  Из спинной аорты кровь через систему капилляров возвращается по венам в брюшную аорту. По выносящим жаберным артериям кровь поступает в корни спинной аорты расположенные симметрично с двух сторон тела. Таким образом несмотря на простоту кровеносной системы в целом уже у ланцетника имеются основные Магистральные артерии характерные для позвоночных в том числе для человека: это брюшная аорта преобразующаяся позже в сердце восходящую часть дуги аорты и корень легочной артерии; спинная аорта становящаяся позже собственно аортой и сонные...
47447. Филогенез систем органов хордовых. Мочеполовая система. Центральная нервная система. Эндокринная система 90.5 KB
  Образование головного мозга называют цефализацией. Совместная эволюция органов чувств и головного мозга приводит к возникновению динамических координации между обонятельными рецепторами и передним мозгом зрительными и средним слуховыми и задним. Внутри головного и спинного мозга расположена общая полость соответствующая невроцелю. В спинном мозге это спинномозговой канал а в головном желудочки мозга.