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

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

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


 

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

47362. Модернизация координатной оси динамической подвижной лазерной головки 6.3 MB
  Областью практического применения разработанной координатной системы станка обеспечивает динамическое перемещение оптической оси лазерного излучения, а также положением фокуса луча над поверхностью раскройного стола с разрешением в тысячные доли миллиметра.
47366. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИКИ ЦЕНТРОБЕЖНОГО НАСОСА. Исследование кавитационных свойств центробежного насоса 306.5 KB
  В ходе выполнения данной лабораторной работы мы исследовали и построили характеристики центробежного насоса, выбрали оптимальный режим работы, были построены характеристики
47367. Специфика проникновения информационно-коммуникативных технологий в жизнь современного российского общества 386.65 KB
  По мере накопления в обществе различных видов информации невиданными темпами возрастает интенсивность её потребления во всех сферах жизнедеятельности общества. Постепенно на первое место выдвигается содержательный аспект информации, её релевантность (значимость, существенность, важность) по отношению к деятельности людей
47368. Операционные системы (ОС) 35.42 KB
  Основная задача операционной системы (ОС) — это обеспечение управления процессом обработки информации взаимодействие между аппаратными, программными средствами и пользователем. В большинстве современных вычислительных систем ОС является основной, наиболее важной (иногда единственной) частью системного программного обеспечения.
47369. Проектирование маршрутных ТП механической обработки деталей 605.5 KB
  Имеется большое количество поверхностей, которые обладают несколькими направлениями доступа и могут обрабатываться или действительно обрабатываются с различных сторон. Для удобства проектирования рекомендуется пронумеровать обрабатываемые поверхности по их направлениям доступа
47370. Основные сведения о работе с программами обработки текстов, таблиц, презентаций, макетирования и верстки 66.3 KB
  В работе специалиста по СсО и рекламе с ПК значительная доля времени расходуется на создание, редактирование и печать документов. Привычные современному пользователю программы для работы с документами редко выпускаются на рынок как отдельные продукты.