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

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

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


 

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

40250. Порядок исчисления и уплаты налога на имущество организаций 38 KB
  Объектом налогообложения для российских организаций признается движимое и недвижимое имущество включая имущество переданное во временное владение пользование распоряжение или доверительное управление внесенное в совместную деятельность учитываемое на балансе в качестве объектов основных средств в соответствии с установленным порядком ведения бухгалтерского учета Налоговая база определяется как среднегодовая стоимость имущества признаваемого объектом налогообложения. Среднегодовая стоимость имущества определяется путем деления на четыре...
40251. Порядок исчисления и уплаты налога на прибыль организаций 35 KB
  Не являются плательщиками налога на прибыль: 1.организации перешедшие на уплату единого налога на вмененный доход для определенных видов деятельности; 2. Указанные организации не освобождаются от исполнения обязанностей налогового агента и удержания сумм налога с доходов у источника выплат в соответствии с 25 главой НК.
40252. Порядок исчисления и уплаты Налога на Добавленную Стоимость 41 KB
  Сумма налога при определении налоговой базы исчисляется как соответствующая налоговой ставке процентная доля налоговой базы а при раздельном учете как сумма налога полученная в результате сложения сумм налогов исчисляемых отдельно как соответствующие налоговым ставкам процентные доли соответствующих налоговых баз. Общая сумма налога получается в результате сложения исчисленных таком образом сумм налогов. Общая сумма налога не исчисляется налогоплательщиками иностранными организациями не состоящими на учете в налоговых органах в...
40253. Порядок передачи бух и налог. учета организацией-аутсорсером 26 KB
  Текст котго подготавливается индивидуально в зависимости от объема и формы заказа. Оргции д. Интересы налогоплательщикаоргции может предоставлять в налог правоотношениях его представитель.
40254. Услуги по ведению бухгалтерского и налогового учета аутсорсером 30 KB
  Как правило ведение учета специализированной организацией ведется по следующей схеме. 6 Закона о бухгалтерском учете руководители организаций могут в зависимости от объема учетной работы: а учредить бухгалтерскую службу как структурное подразделение возглавляемое главным бухгалтером; б ввести в штат должность бухгалтера; в передать на договорных началах ведение бухгалтерского учета централизованной бухгалтерии специализированной организации или бухгалтеруспециалисту; г вести бухгалтерский учет лично. Передача бухгалтерского учета...
40255. Порядок формирования и учет уставного‚ резервного и добавочного капитала 57 KB
  Правовая основа уставного капитала определяет его размер и состав сроки и порядок внесения вкладов в уставный капитал участниками оценку вкладов при их взносе и изъятии порядок изменения долей участников ответственность участников за нарушение обязательств по внесению вкладов. Кредитовый остаток этого счета показывает сумму зарегистрированного уставного капитала оборот по кредиту отражает сумму его увеличения по законным основаниям а оборот по дебету уменьшение уставного капитала при выходе из состава организации ее участников...
40256. Порядок хранения документов 26 KB
  В зависимости от сроков хранения документы бывают: временного хранения до 10 лет включительно; долговременного хранения свыше 10 лет; постоянного вечного хранения. Документы постоянного хранения передаются в государственные архивы остальные подлежат хранению в структурных подразделениях организации или в ее архиве. Срок хранения документов исчисляется с 1 января года следующего за годом их оформления.
40257. Права и обязанности членов ИПБ 26 KB
  Члены ИПБ имеют право: 1. Участвовать в управлении делами ИПБ и его структурных подразделений. Вносить предложения по совершенствованию законодательства и нормативной базы в области бухгалтерского учета аудита налогообложения и других вопросов связанных с деятельностью ИПБ.
40258. Права и обязанности должностных лиц бух.службы 28.5 KB
  В зависимости от величины и специализации предприятия а также объема выполняемых учетных операций могут быть выбраны различные варианты организации бухгалтерской службы на предприятии причем в зависимости от периодически проходящих организационных изменений на предприятии могут меняться варианты организации бухгалтерской службы как в целом так и отдельных ее групп. В зависимости от размера предприятия количества самостоятельных подразделений видов деятельности и видов услуг видов функций и операций количество штатных единиц...