XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 58
Текст из файла (страница 58)
П2.8 представлено решение задачи выбора наиболее длинного пути для ациклической сети, изображенной на рис. П2.7 В ряде случаев нумерацию узлов ациклической сети целесообразно проводить так, чтобы для каждой ориентированной дуги 11, «) этой сети, выходящей из узла« и входящей в узел «, выполнялось неравенство «> «'. Процедура такой нумерации во многом схожа с процедурой нумерации, рассмотренной выше, и состоит из нескольких этапов.
Сначала узлу ациклической сети, из которого не выходит ни одна ориентированная дуга, присваивают номер 1 и вычеркивают ориентированные дуги, входящие в него. После этого в сети образуется п« узлов, иэ которых не выходит ни одна из ориентированных дуг. Этим узлам 1в любой последовательности) присваивают номера от 2 до и, + 1, вычеркивают дуги, входящие в них, и рассуждения, проведенные выше, повторяют до тех пор, пока не будут пронумерованы все узлы рассматриваемой ациклической сети.
Для уяснения описанной процедуры нумерации можно в качестве примера взять ациклическую сеть, изображенную на рис. П2.1. Результат нумерации узлов этой ациклической сети представлен на рис. П2.7. Рис. П2.7 1 9 «9 Рис. П2.8 Пусть для некоторой ациклической сети задан путь, который можно рассматривать как последовательность номеров узлов этой сети: (11, 19, ..., 1«с).
Любой путь вида где 1 < lс« « ... й < 1«', называют под«Етпем исходного пути. В частности, для ациклической сети на рис. П2.3 путь 12, 4, 6, 8, 9) содержит несколько подпутей, включая (2, 4, 6) и 14, 6). Понятие подпути позволяет дать первую формулировку принципа оптимальности дискретного динамического программирования в рамках ациклических сетей: подпуть оптимального (кратчайшего или наиболее длинного) пути сам является оптимальным путем.
В этой формулировке принцип оптимальности понятен и не нуждается в комментариях, но прежде чем обсуждать вторую, самую распространенную формулировку принципа оптимальности дискретного динамического программирования, остановимся на следующем примере. 414 ПРИЛОЖЕНИЕ 2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 415 Пример П2.4. Рассмотрим следующую задачу исследования операций: сь(хь) ~ тах; я=1 (П2.2) дь(хь) < Ь, хь Е УО(0), 1=1,п, ь=1 где 6 — известное целое положительное число; функции дь(хь), й = 1, и, определены на множестве ЯО (0), принимают значения из этого же множества и дь(0) = О; сь(хь), 6 =1, и, — некоторые произвольные функции, удовлетворяющие условию сь(0) = О.
Функции вида ~о(хм..., х„) = у1 (х1) + ... + 1Р„(х„) называют аддитивпмми. В рассматриваемой задаче аддитивными являются целевая функция и функции, входящие в левую часть ограничений. Именно с видом этих функций связана специфика этой задачи. Поставленная задача может возникнуть в различных ситуациях. Например, пусть предприятие для производства и различных продуктов использует некоторый ресурс, запасы которого ограничены величиной Ь.
Для производства хь единиц Й-го продукта нужно израсходовать дь(хь) единиц ресурса, а доход от этого составляет сь(хь) условных денежных единиц. Тогда определение объемов производства продуктов хь, Й = 1,п, обеспечивающих максимальный суммарный доход, приводит к сформулированной задаче исследования операций. Поставленная задача является статической задачей принятия решений.
Но если по каким-либо причинам производство различных продуктов должно происходить последовательно (сначала 1-й продукт, затем 2-й и т.д.), то мы приходим к многошаговой задаче принятия решений, которую и будем рассматривать далее. Проанализируем ситуацию, которая может сложиться после того, как завершено производство продуктов с номерами от 1 до й — 1, 1 < Й вЂ” 1 < и. Прежде всего заметим, что в этом случае могут остаться недоиспольэованными у единиц ресурса, где у б (О, 1, ..., Ь), так как по условию Ь Е 1ч и дл(хь) Е Я0 (0), Й = 1, и. Эти у единиц ресурса необходимо распределить для производства продуктов с номерами от х до и так, чтобы суммарный доход был максимальным. При этом интуитивно понятно, что сложившаяся ситуация может быть однозначно охарактеризована с помощью пары (й, и).
Пусть Яу) — максимальная прибыль, которую можно получить за счет производства продуктов с номерами от Й до и, имея в наличии у единиц ресурса. Тогда Л (6) оптимальное значение целевой функции исходной задачи, и нужно определить Яу) и у Е (О, 1, ..., и), 6 = 1, и. Говорят, что производство хь единиц й-го продукта допустимо, если дь(хь) < у, хь б 1чО(0), т.е. если необходимое для этого количество единиц ресурса не превосходит его наличный запас уь Отметим, что величина сь(хь) + Д+1(у — дь(хь)) (П2.3) представляет собой максимально возможный доход, который можно получить за счет распределения наличного запаса ресурса у для производства продуктов с номерами от х до и при условии, что произведено хь единиц й-го продукта.
Интерпретация выражения (П2.3) является корректной, поскольку запас ресурса после производства й-го продукта, по предположению, распределен оптимально. Таким образом, Д(у) = шах (сь(хь) + ~в+1(у — дь(хь))), (П2.4) ьья~ь ~ где юь = (хь Е Ю О (0): дь(хь) < у) . При этом (П2.4) справедливо и при й = и, если считать, что (П2,5) У„+,(и) =О, у=О,Ь. 415 ПРИЛОжКНИК г. ДИНЛМИЧКСКОК ПРОГРЛММИРОКЛНИК 417 Заметим, что предположение (П2.5) можно интерпретировать как бесполезность неиспользованного ресурса.
Поэтому при решении практических задач иногда вводят понятие издержек эа переход ресурса в следующий период. В (П2.4) сначала полагают и = п и с учетом (П2.5) находят ,('„(у) для каждого у = О, 6. Затем полагают к = п — 1 и находят ,)„1(у), у = 0,6, с учетом уже известных ~„(у). Вычисления продолжают вплоть до нахождения Л(6).
$ Задачу, рассмотренную в примере П2.4, можно интерпретировать как задачу выбора наиболее длинного пути в ациклической сети. Действительно, каждой паре чисел (/с, у), к = 1, и, у = 0,6, поставим в соответствие узел сети. Иэ этого узла для каждого значения хл Е мь проведем ориентированную дугу, которая входит в узел (Й+1, у — дл(хл)) и имеет длину сл(хь). Тогда рассматриваемая задача равносильна поиску самого длинного пути в этой ациклической сети от узла (1, 6) до некоторого узла (и+ 1, г), где г — количество единиц неиспользованного ресурса. Любую многошаговую процедуру принятия решений можно интерпретировать как процесс изменения состояния некоторой динамической системы с дискретным временем [ХЪ'П1).
Само понятие состояния играет важную роль в дискретном динамическом программировании и может иметь весьма своеобразную интерпретацию. Так, для задачи нахождения кратчайшего пути, рассмотренной в примере П2.2, состояниям системы соответствуют узлы ациклической сети (см. рис. П2.3), а совокупность ориентированных дуг, выходящих из узла с номером 1 Е (1, 2, ..., 9), есть не что иное, как множество допустимых решений для этого состояния. Заметим, что для динамической системы будущее состояние определяется текущим состоянием и не зависит от ее состояния в прошлом, т.е. процесс изменения состояния этой системы в определенном смысле можно рассматривать как детерминированный аналог марковского процесса. Это обстоя- тельство связано с тем, что ориентированные дуги, выходящие из любого узла ациклической сети (см. рис.
П2.3), никак не зависят от входящих в него ориентированных дуг. В дискретном динамическом программировании элементы состояния принято называть иеремемныма соспзо.ама,а. Так, в задаче о распределении ограниченного ресурса из примера П2.4 состояние представляет собой пару (к, у), а к и у— переменные состояния. Понятие этапа, уже встречавшееся в марковских случайных процессах с дискретным временем, используют и в дискретном динамическом программировании.
Так, в задаче о распределении ограниченного ресурса, рассмотренной в примере П2.4, на Й-м этапе происходит переход из состояния (Й, у) в состояние (6+1, г). В исследовании операций все многошаговые процедуры принятия решений основываются на понятии этпапа (млага), который в конкретной задаче либо является естественным элементом, либо вводится искусственно.
Суть метода дискретного динамического программирования применительно к многошаговым задачам принятия решений с аддитивной целевой функцией заключается в поэтапной оптимизации. Реализация идеи поэтапной оптимизации была проиллюстрирована в примере П2.4 при решении задачи о распределении ограниченного ресурса с использованием равенств (П2.4), (П2.5). Поэтаимал отииилваэацал состоит в том, что оптимальное решение принимается на каждом шаге. В задаче выбора кратчайшего пути зто решение связано с выбором одной дуги из совокупности ориентированных дуг, выходящих из некоторого узла ациклической сети (см. пример П2.2), а в задаче о распределении ограниченного ресурса — с выбором из множества мь в ситуации, описываемой парой (й, у).
Из этих примеров следует, что принятие решений на каждом шаге, за исключением последнего, должно осуществляться с учетом всех его возможных последствий в будущем (на еще предстоящих шагах). 418 приложяния г. динлмичкскок проп'лммировлнии 419 Среди множества шагов многошаговой процедуры принятия решений последний шаг занимает особое место. Это связано с тем, что на последнем шаге выбор решения из соответствующего множества допустимых решений можно осуществлять „без оглядки на будущее". Именно поэтому прн использовании метода дискретного динамического программирования сначала планируют последний шаг, исходя из максимально возможной эффективности (в смысле значений целевой функции) принимаемого решения. В дискретном динамическом программировании выбор решения из множества допустимых решений называют управлемаем.
При выборе управления на последнем и-м шаге необходимо исходить из всех возможных вариантов завершения (и-1)-го шага и для каждого из них найти такое управление, чтобы его эффективность на последнем шаге была максимально возможной. Решив эту задачу, находят условное опгиимальное управленце на и-м шаге, т.е. управление с максимально возможной эффективностью (в смысле значения целевой функции), которое нужно применить на п-м шаге при условии, что (и-1)-й шаг завершился определенным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
