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

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

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


 

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

35124. Розрахунок системи теплопостачання району міста 412.51 KB
  Вибір джерела теплопостачання теплоносія і типу системи теплопостачання. Визначення витрати теплоносія. Тривалість опалювального періоду nв: год Річні витрати тепла на вентиляцію: ГДж рік Річні витрати тепла споживачами: ГДж рік З Вибір джерела теплопостачання теплоносія і типу системи теплопостачання Вибір джерела теплопостачання теплоносія і типу системи теплопостачання залежить головним чином від сумарного теплового навантаження і технологічних споживачів і визначається виходячи з...
35125. Финансовый контроль 79.5 KB
  Понятие и виды финансового контроля. Контрольная функция финансов проявляется в финансовом контроле важнейшем в системе государственного контроля. Специфика финансового контроля состоит в том что финансы одновременно являются объектом и субъектом контроля. В более узком значении контрольная функция состоит в предупреждении и устранении выявленных в результате контроля негативных явлений и фактов дестабилизирующих развитие экономики и финансов наносящих вред интересам государства трудовых коллективов и большинства населения.
35126. Развитие налоговой политики в Республике Беларусь за 2005 год 63.5 KB
  В целях реализации Закона Республики Беларусь €œО бюджете Республики Беларусь на 2005 год€: разработаны и приняты инструктивные документы о порядке исчисления в 2005 году едиными платежами установленных данным законом налогов и сборов взимаемых от фонда заработной платы и из выручки от реализации товаров работ услуг а также о порядке уплаты в 2005 году местных целевых сборов организациями имеющими филиалы представительства и иные обособленные подразделения; определены сроки перечисления в 2005 году налоговыми агентами в доход местных...
35127. Бюджет, финансы и налоговая политика 38 KB
  Успешное решение этих задач будет иметь важное значение при рассмотрении проекта Бюджетного кодекса Республики Беларусь внесение которого планируется в Палату представителей в 2005 году. Принимаемые законы должны быть направлены на повышение результативности бюджетных расходов обеспечение выполнения показателей социальноэкономического развития республики на совершенствование бюджетной политики укрепление местных бюджетов и предоставление им большей самостоятельности. По мнению Постоянной комиссии по бюджету финансам и налоговой политике...
35128. Финансы и их структура 441.5 KB
  Подоходный налог с физических лиц который собирают: параграф 1 Предприятия и учреждения; параграф 2 Налоговые органы. Средства пенсионного фонда образуются из следующих источников: 1 Страховые взносы которые платят все предприятия независимо от формы собственности. При их участии создается ВВП распределяемый внутри предприятия и отраслей хозяйства. Фонды страхования предназначены для возмещения ущерба нанесенного стихийными бедствиями предприятиям и населению а по личному страхованию выплаты застрахованному лицу или его семье...
35129. БЕЛАРУСКАЯ МОВА. ПРАФЕСІЙНАЯ ЛЕКСІКА 1.48 MB
  Лічылася што мова закладзена ў самой біялагічнай сутнасці чалавека і перадаецца ў спадчыну. На самой справе мова зява біялагічная і псіхічная але ў тым сэнсе што ў чалавеку генетычна закладзена здольнасць авалодаць мовай г. Кожны чалавек валодае не мовай увогуле а канкрэтнай мовай ці мовамі што належыць пэўнаму народу. Сацыяльная прырода мовы заключаецца найперш у тым што яна аснова і форма грамадскай свядомасці і разам з тым унікальны і універсальны сродак зносін людзей феномен духоўнай культуры чалавецтва [7].
35130. Расчёт пространственного одноэтажного промышленного здания, оборудованного мостовым краном 414.33 KB
  Список литературы Исходные данные Количество пролетов 3; Длина пролета l1 = 18 м; Длина здания l = 168 м; Несущая конструкция покрытия балка; Шаг колонн 6 м; Высота до верха рельса 84 м; Грузоподъемность крана 15 т; Расчетное сопротивление грунта Rгр =019 МПа; Место строительства г. Расчет крайней колонны Данные для расчета сечений: бетон тяжелый класса B15 подвергнутый тепловой обработке при атмосферном давлении Rb = 85 МПа; Rbt = 075 МПа; Eb = 20500 МПа. Арматура класса АIII d 10 мм RS = RSC =...
35131. Форматирование результатов запроса 82 KB
  Например можно применить следующую команду чтобы увидеть определенные поля таблицы Slespeople упорядоченные по убыванию поля commission comm: SELECT snme comm FROM Slespeople ORDER BY 2 DESC; Мы рассматриваем это свойство ORDER BY для того чтобы продемонстрировать возможность его использования со столбцами выходных данных; эта процедура аналогична применению ORDER BY со столбцами таблицы. Например чтобы подсчитать заявки orders для каждого продавца slespeople и вывести результаты в убывающем порядке: SELECT snum COUNT DISTINCT...
35132. Создание таблиц 90 KB
  Команда CRETE TBLE Таблицы определяются с помощью команды CRETE TBLE создающей пустую таблицу таблицу не имеющую строк. Команда CRETE TBLE определяет имя таблицы и множество поименованных столбцов в указанном порядке. Синтаксис команды CRETE TBLE: CRETE TBLE имя таблицы имя столбца тип данных [ размер ] имя столбца тип данных [ размер ]. Поскольку пробелы используются для разделения отдельных частей команд в SQL их нельзя использовать как часть имени таблицы.