Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Оптимальное планирование реализации возобновляемых ресурсов

До сих пор мы рассматривали задачи оптимального распределения заданного количества некоторого ресурса, который не возобновлялся. Однако динамическое программирование можно применить и в задачах распределения возобновляемых ресурсов. Например, природные ресурсы (промысловая рыба, морские животные, и вообще «население» лесов, морей, озёр и рек) являются возобновляемым ресурсом. Возникает задача оптимального использования таких ресурсов, то есть планирование их добычи на ряд лет вперёд, с тем чтобы обеспечить максимальную прибыль за всё время планирования и сохранить минимально необходимый объём ресурса. Если в начале планируемого периода объём ресурса несущественно превышает заданный минимум, то решение задачи может показаться тривиальным: ежегодно брать у природы только прирост ресурса и не более того. Однако это решение не очевидно, если учесть, что при сохранении неприкосновенности ресурса через несколько лет можно взять больше, чем при ежегодном изъятии прироста. В реальности задача осложняется тем, что для воспроизведения ресурса может требоваться не один год, например при планировании лесозаготовок.

Мы не будем рассматривать эту проблему детально, а ограничимся анализом некоторых моделей подобной задачи и алгоритмов её решения по классическому методу динамического программирования, затем изложим другой способ решения задачи.

Задача состоит в следующем: в начальный момент времени имеется заданное количество возобновляемого ресурса bi.

Заданный период планирования Т (например, Т=10 лет) разбивается на этапы, например годы или месяцы. Для определённости примем годы.

При реализации х единиц ресурса в течение года доход равен d(x), а сопутствующие затраты в течение года есть функция с(х,Ь) от количества реализуемого ресурса х и количества ресурса на начало года Ь. Ресурс возобновляемый, и при наличии на начало года t (/=1,2,...,Т) bt единиц ресурса и реализации в течение этого года xt его единиц, на начало следующего года будет bi+i=p(bt-xt) единиц ресурса. Коэффициент р считается известным. В начале года Т при рассмотрении вариантов реализации ресурса в этот последний год считается, что оставшееся на Т+1 -ый год количество ресурса задано, или не имеет значения. Поэтому в начале последнего года Т задача принятия решения существенно упрощается.

Требуется построить такой план реализации ресурса, чтобы в течение Т лет суммарный количественный показатель качества плана (целевая функция) принял максимальное значение. Могут использоваться различные целевые функции, например суммарная прибыль, экономическая эффективность и др.

Если целевая функция - это суммарная прибыль, то задача сводится к следующему:

Найти вектор x(xi,X2,...,xt), при котором достигает максимума

Для решения задачи применительно к построению оптимального плана вылова форели в [12] предлагается классическая схема динамического программирования. Ключевое для метода динамического программирования понятие «состояние системы» формализуется как количество имеющегося ресурса. Соответственно «траектория» (или «путь») - это последовательность состояний, то есть значений имеющегося ресурса в начале каждого года. В начале года t множество состояний - это множество возможных значений ресурса bt. Процесс рассматривается от «конца к началу», то есть, начиная с множества состояний Ьт в начале последнего года. Заметим, что количество состояний Ьт в начале года Т = bipT_1+l может быть велико при реальных bi, р и Т и поэтому усовершенствования классической схемы динамического программирования актуальны с точки зрения объёма вычислений.

Далее, для каждого состояния Ьт, то есть для всех возможных значений Ьт (от 0 до bip1'1) определяется «оптимальный путь до конца», то есть оптимальное количество ресурса, реализуемого в последний год (хт*), и вычисляется соответствующее ему значение целевой функции fr(br).

Далее рассматриваются два последних года и для каждого состояния Ьт-i перебором всех возможных переходов в состояния Ьт в начале последнего года определяется xVi и соответствующее ему значение целевой функции fr-i(bT-i).

И так до тех пор, пока не будет найден xi* при заданном bi. Значения xt*, при которых достигается максимум, запоминаются. Другими словами, рекомендуется двигаться по сетке состояний в обратном направлении в предположении, что в начале очередного года, возможно любое количество ресурса от нуля до максимального, получаемого при полном отсутствии реализации ресурса.

Далее, зная хЛ вычисляем соответствующее ему Ьг*= p(bi- х*). Ему соответствует Х2* и т.д. до восстановления оптимальной траектории, то есть построения плана реализации ресурса. Заметим, что в данной задаче промежуточные значения bt+i=p(bt-xt) при целых значениях исходного количества ресурса bi и последующих назначаемых xt не обязаны быть целыми при не целом р.

По поводу выбора порядка рассмотрения этапов в [12] утверждается: «В большинстве приложений динамическое программирование получает оптимальное решение путём движения в обратном направлении - от конца задачи к началу». Не располагая данными о всех приложениях динамического программирования, мы не будем опровергать это утверждение, однако отметим, что именно в данной задаче при её численном решении удобно и более эффективно двигаться от начала к концу, а аналитические выкладки наоборот удобнее выполнять при рассмотрении задачи в обратном направлении, то есть от последнего этапа к первому.

Конкретный вид функций d(x)- доход и с(х,Ь) - затраты в [12] не приводится. Приводятся как пример только bi=10000, р=1.2 и Т=10.

Далее будем рассматривать задачу в общем виде.

Для начала отметим, что для простых моделей можно, используя принцип оптимальности Р. Веллмана [3,4], получать последовательно, начиная с t=T аналитические выражения оптимального количества реализуемого ресурса xt* как функции bt, не прибегая к численным методам и не разбивая сетку варьирования вообще. Рассмотрим две такие модели, отличающиеся функциями дохода d(xj и затрат с(х,Ьу).

Первая модель: d(xy)=ax, где а-доход от реализации единицы ресурса. Вид функции дохода вполне естественен. Для затрат с(х,Ь) можно предположить, что они возрастают с ростом х и убывают при заданном х с ростом b - количества имеющегося ресурса. Действительно, например, применительно к разведению форели выловить 100 форелей легче, если их много, скажем 10000, чем, если их всего 100.

Для первой модели примем c(x,b)= (k/b)x, где к- заданное число. Прибыль при реализации х единиц ресурса из имеющихся b единиц составит ах- (к/Ь)х. Здесь к/b- затраты при реализации единицы ресурса из имеющихся b единиц. Соответственно к- затраты при полной реализации ресурса. При наличии затрат, не зависящих от количества реализуемого ресурса, выражение ах- (k/b)x только условно можно назвать прибылью. Теоретически наличие в целевой функции постоянного слагаемого несущественно, так как оно не влияет на точку экстремума, то есть искомое решение. Мы не будем учитывать наличие постоянной составляющей затрат на реализацию ресурса. Однако, формальный оптимум может соответствовать решению, при котором в каком -нибудь году ах- (k/b)x меньше постоянной составляющей годовых затрат на реализацию ресурса и поэтому годовая прибыль отрицательна, хотя суммарно за все годы прибыль максимальна. Если отрицательная годовая прибыль недопустима, то на каждом этапе появляется ограничение на минимальное количество реализации ресурса. Это ограничение несколько усложняет алгоритм поиска. Для простоты изложения вначале допустим возможность реализации любого количества имеющегося ресурса, то есть будем рассматривать только переменную часть целевой функции. В дальнейшем внесём необходимые уточнения.

Рассмотрим последний год Т, допустим, что в последний год можно реализовать ресурс полностью и решим вопрос, сколько нужно реализовать ресурса из имеющихся Ьт единиц, чтобы получить максимальную прибыль.

Ответ очевиден: если а>к/Ьт, нужно реализовать ресурс полностью (хт*=Ьт), иначе не использовать его вообще (хт*=0). Мы нашли хт* - количество реализуемого ресурса в году Т как функцию Ьт (хт*=0 или хт*= Ьт).

Переходим к предпоследнему шагу Т-1. Суммарная прибыль за два последних года линейно зависит от хт-i, так как Ьт=р(Ьт-1- хт-i). Линейная функция достигает экстремальных значений на концах рассматриваемого интервала 0 Ьт-i и суммарная прибыль за два года больше, если вообще имеет смысл реализация ресурса. Рассуждая аналогично применительно ко всем годам, для линейной модели приходим к выводу: оптимальный план состоит в том, чтобы вообще не расходовать ресурс до последнего года и только в последний год реализовать его полностью, если a>/(bipT'1), или не заниматься реализацией ресурса вообще в противном случае, который не реален.

Если потребность в реализации ресурса не позволяет накапливать его до последнего года, то следует ограничиться минимально необходимой его реализацией.

Может показаться, что этот же вывод о сохранении ресурса до последнего года справедлив не только для линейной, но и для любой монотонно возрастающей целевой функции. Но это не так, как будет ясно из дальнейшего.

Вторая модель. В первой модели затраты на полную реализацию ресурса (к) не зависят от его количества. Если оставить ту же функцию дохода d(x) и рассмотреть новую функцию затрат вида c(x,b)= (q/b)x2, то для переменной части прибыли z получается функция z(x,b)=ax-(q/b)x2 (рис. 4.3), где а и q>0 заданы. В этом случае а- это по-прежнему доход при реализации единицы ресурса, a q- затраты на реализацию единицы ресурса в случае его полной реализации. Другими словами, a/q - отношение дохода к затратам при полной реализации ресурса. Очевидно неравенство a> Если в с(х,Ь) есть линейный член, то его можно объединить с d(x).

Ерафик зависимости z(x) показывает, что при a/(2q)=ab/(2q) Хтах, так как при х= хтах больше прибыли и остаётся больше ресурса, чем при х> х,Шх.

Если же a/(2q)>l, то нужно принять xmax=b, так как 0<х<Ь.

Рассмотрим последний год Т и решим вопрос, сколько (хт*) нужно реализовать ресурса из имеющихся Ьт единиц, чтобы получить максимальную прибыль? Максимум прибыли ах г - (q/bx)xT2 достигается в точке хт*=аЬт/(2ф.

Поскольку должно выполняться условие 0<хт<Ьт, то при a/(2q)>l следует принять хт*=Ьт. То есть, хт*= утЬт, где ут=шт (l,a/(2q)). Это означает, что если при полной реализации ресурса доход вдвое и более превышает затраты, то нужно реализовать весь ресурс, иначе его а/(2с^часть.

Зависимость прибыли z(x) от количества ресурса х

Рис. 4.3. Зависимость прибыли z(x) от количества ресурса х

Нецелесообразность полной реализации ресурса в последнем году, то есть неравенство a/(2qj

Получили результат: за последний год оптимальный размер реализации ресурса линейно зависит от его количества в начале года. Коэффициент пропорциональности ут=а/(2ф при a/(2q)t за любой один год t при xt*=ytbt равна

Другими словами, годовая прибыль линейно зависит от имеющегося ресурса bt при линейной зависимости количества реализации от bt. На этом основаны все дальнейшие построения.

Для последнего года всё определено: при любом Ьт надо реализовать утЬт единиц ресурса и получить прибыль АлЬт.

За год Т прибыль

Будем обозначать годовую прибыль за год с номером г через zr, а суммарную прибыль за все оставшиеся годы, начиная с r-го, через Zr.

Переходим к предпоследнему году Т-1. Найдём хт-Г, для которого максимальна суммарная прибыль за два последних года. В терминах динамического программирования это означает: из состояния Ьт-i найдём такой переход в новое состояние Ьт, чтобы суммарная прибыль Zt-i за последние два года (этапа) была максимальна. Используя формулу (4.3) применительно к году Т, получаем для прибыли за два последних года формулу:

Так как р>1, то ив этом случае ут-1< ут =1. Действительно, предположим противное, то есть a(l-p)/(2q)+p/2>l. Это неравенство равносильно неравенству (p-l)a/q<(p-2), которое не может выполняться при р>1 и a/(2q)>l. Поэтому можно записать yT-i=(a(l-pyr)+qpyT2)/(2q), опуская операцию взятия минимума. Полученное неравенство ут-1 < 1 означает нецелесообразность полной реализации ресурса в предпоследнем году, что вполне естественно. Отсюда следует и нецелесообразность полной реализации ресурса и в любой предшествующий год, так как, допуская полную реализацию в следующем за ним году, получаем лучшее решение.

Интересно отметить, что ут-i может оказаться отрицательным. Это означает, что хт-Г=0 и реализация ресурса в Т-1 -ом году нецелесообразна вообще.

Если это неравенство не выполнено, то 0< ут-i <1 и целесообразна реализация ресурса при любом его количестве. Например, при р-2 и a/(2q)=0.8 получаем ут-i =0.16.

Условие ут-1<0 выполнено при a/(2q)>p/(2p-2). Это условие может быть выполнено как при р/(2р-2)>1, так и при р/(2р-2) <1. Так при р=1.2 должно быть a/(2q)>3; а при р=2.2 получаем a/(2q)>l 1/12, то есть любое a/(2q)>l. При a/(2q)>l прибыль за один год это монотонно возрастающая функция использованного в этом году ресурса и даже в этом случае при соответствующих значениях a/(2q) и р в предпоследний год целесообразна реализация значительной части ресурса независимо от его количества. Например, р=1.2 и a/(2q)=1.5 эта часть, то есть ут-i, составляет 30%.

Далее, прибыль за один Т-1-ый год равна АлчЬт-ь где

Алч=утч (а- ут-iq), что следует из формулы (4.3) для произвольного года при подстановке ут-ibT-i вместо yt bt.

Итак, мы получили, что и оптимальное годовое количество реализации ресурса и прибыль за каждый год при оптимальном плане реализации в расчёте на максимум прибыли за два оставшихся года линейно зависят от количества ресурса в начале каждого года.

Используя принцип математической индукции, докажем, что эта линейная зависимость оптимального годового количества реализации и годовой прибыли от количества ресурса в начале года сохраняется для любого числа лет при максимизации суммарной прибыли за все оставшиеся годы.

Итак, пусть это утверждение верно для лет с номерами s,s+l,s+2,...,T. Нам нужно доказать, что это утверждение верно и для всех оставшихся лет, начиная с s-1- го года. Тогда будет доказано, что это утверждение верно для любого года, так как для последнего (да и предпоследнего года) это утверждение уже доказано.

Наше предположение означает следующее:

Тогда суммарная прибыль за все оставшиеся годы, начиная с s-1 -го, составит: Zs-i=axs-i-(q/bs-i)xs-i2 + A,sbs +A,s+ibs+i +...+А,тЬт.

Поскольку для любого br при r>S- 1 br+l=p(br —хг)= р( 1 -yr)br, то

Обозначив выражение в фигурных скобках через Ds-i, получим

Максимум Zs-i достигается при x*s-i-(a-pDs-i) bs-i/(2q). Или

Как установлено выше, ys-is-i=l означает полную реализацию ресурса, что не является оптимальным решением во все годы, кроме последнего.

В соответствии с (4.3)

Получили, что и xVi и Zs-i также линейно зависят от bs-i, что и требовалось доказать.

Из (4.4) следует рекуррентное соотношение

В итоге получаем следующий алгоритм для построения оптимального плана реализации ресурса:

  • 1. Вычисляем ут=тт( 1, a/(2q)) и Хт =ут(а- утя). Полагаем Dt=0.
  • 2. Последовательно применяя формулы (4.6,4.5 и 4.3), вычисляем Dt-i, ут-i, At-ь
  • 3. Аналогично вычисляем все Dr, уг и ХТ для всех 1<г<Т-1, начиная с г=Т-2. На каждом шаге запоминаем уг, Хт и последнее из вычисленных Dr.
  • 4. Обратным разворотом, используя заданное bi и вычисленные уг и Хт, последовательно находим все х *, b* i+/и Zj*(i=l,2,...T).

Естественно, при получении нецелых значений для Xi* они должны округляться до целых значений. Суммарную прибыль получим, суммируя все z*.

Определяемая по формуле (4.5) величина ys-i на некотором шаге может стать меньше нуля. Если это произойдёт, она заменяется нулём. Это означает, что в соответствующий и все предшествующие годы нет реализации ресурса.

Возвращаясь к вопросу о влиянии постоянной составляющей ежегодных затрат, отметим следующую корректировку алгоритма.

  • 1. При обратном развороте после вычисления на очередном этапе с номером г величин Ьг и zr=A,rbr, соответствующих оптимальному плану, вычитаем из zr постоянную составляющую годовых затрат.
  • 2. Если полученная разность (годовая прибыль) положительна, переходим к следующему этапу. В противном случае можно увеличить реализацию, то есть увеличить уг-1 и соответственно прибыль до требуемого размера. Однако при такой корректировке оптимальной траектории возможно досрочное исчерпание ресурса, что, как уже отмечалось, не соответствует оптимуму. Поэтому представляется предпочтительным при возникновении подобной ситуации с недопустимо малой прибылью уменьшить реализацию ресурса в предшествующие годы, рассматривая их последовательно, или вообще отказаться от реализации ресурса в r-том году, то есть принять yr-i=0, и тем самым перейти в состояние следующего этапа с большим ресурсом Ь/ >ЬГ.
  • 3. После корректировки состояния Ьг процесс в обратном направлении продолжается с вычисленными ранее величинами yiи A,i (i=r,r+l,...,T). Эти величины для оптимальной траектории не зависят от количества ресурса на данном шаге, они зависят только от номера шага.

В данной модели легко учесть рост цен (величины a, q год от года умножаются на соответствующие коэффициенты) и желание получить прибыль поскорее, так как прибыль сегодня не эквивалентна такой же прибыли через несколько лет.

В итоге рассмотрения простых моделей целевой функции можно констатировать, что в данной задаче метод динамического программирования можно использовать не как метод пошагового поиска оптимальной траектории с анализом всех промежуточных состояний, но как метод анализа задачи и построения алгоритма, который сводится к последовательному вычислению оптимальных пошаговых решений по готовым формулам.

Для более сложных моделей трудно рассчитывать на получение расчётных формул по аналогии с приведенными выше.

Приходится использовать другую реализацию метода динамического программирования. Например:

1. Начиная с первого года, имея bi единиц ресурса, рассматриваем все возможные количества его реализации 0 < xi

Тем самым завершается формирование множества состояний после первого года (этапа).

  • 2. Аналогично формируем состояния каждого из последующих этапов, вычисляя суммарные значения целевой функции и оставшиеся количества ресурса. Во избежание полного перебора при достижении одного состояния разными путями в соответствии с принципом оптимальности Р. Веллмана [3,4] оставляем только путь, по которому это состояние достигается с большим значением целевой функции, и запоминаем соответствующее ему состояние предыдущего этапа, т.е. связь.
  • 3. Завершив последний этап, имеем оптимальное значение целевой функции и обратным разворотом по цепочке связей, начиная с оптимального конечного состояния (Ьт+i), восстанавливаем оптимальную последовательность состояний и соответствующие величины реализации ресурса на каждом этапе, то есть в каждом году.

Неприятная особенность такого алгоритма состоит в необходимости округлений получаемых количеств оставшегося ресурса до целых значений.

При наличии дополнительных требований, например не оставлять ресурса меньше чем заданное число или не рассматривать реализацию ресурса меньше заданной величины легко скорректировать построение множества состояний на каждом этапе.

Возможны усовершенствования этого классического алгоритма. Предположим, что зависимости d(x) и с(х,Ь) заданы более сложными формулами, таблично или ещё каким-то образом. Важно, что мы можем вычислить прибыль (целевую функцию) при известных х и Ь, то есть для заданного состояния (Ь) и перехода к новому состоянию. Зададимся вопросом, может ли при различных планах реализации ресурса через несколько лет от начала планирования (идём от начала к концу) получиться так, что для одного состояния ресурса осталось меньше, чем для второго и к тому же прибыль получена меньше, чем для второго. Если это так, то очевидно первое состояние бесперспективно и его вообще не надо рассматривать при переходе к следующему этапу, так как наличие лишнего ресурса никак не может помешать принятию тех же решений при дальнейших переходах из второго состояния, что и при дальнейшем продвижении из первого состояния. Получается, что первое состояние «отстало навсегда». Речь идёт о наличии доминируемых (непаретовских) точек в множестве пар чисел (координат точек на плоскости), из которых первое число это количество оставшегося ресурса, а второе - полученная за все предыдущие годы суммарная прибыль. Характерно, что не только для рассмотренной квадратичной модели, но и для более сложных функций d(x) и с(х,Ь) доминируемые точки могут появляться уже после первого шага, когда из начального состояния (bi=A) исходят несколько путей и никакой отбраковки по принципу Р. Веллмана путей, приводящих в одну точку ещё нет.

Будем считать, что принимаемое на первом шаге решение xi' доминирует над другим таким решением х'", если соответствующая ему точка с координатами (Ьг , zi(x )) доминирует над (Ьг ,zi(x )). Здесь Ьг- количество ресурса на начало второго года, zi(x’) соответственно прибыль, полученная при реализации х единиц ресурса. Аналогичный смысл имеют величины, отмеченные двумя штрихами.

Прибыль на первом этапе zi(x)=d(x)-c(x,A) может достигать максимума в точке 0<х*<А и все точки, х>х* являются доминируемыми, а точка х* доминирует над ними, так как для неё больше и число оставшегося ресурса и полученная прибыль.

По отношению к х > х* доминирующей является также точка х < х*, для которой zi(x")= zi(x) и все точки х> хГ, для которых zi(x)> zi(x) (см. участок графика ВС на рис.4.4.) Если zi(xi) монотонно возрастает при 0T_1H-l.

Доминируемые точки первого шага (х>х*)

Рис. 4.4. Доминируемые точки первого шага (х>х*).

В реальных задачах нужно учитывать также дополнительные условия:

  • 1. Нельзя допускать падение ресурса ниже заданного уровня;
  • 2. Реализация ресурса планируется количествами существенно большими, чем единица.

При этих дополнительных условиях появление непаретовских состояний также возможно. Например, начальное состояние 1000 единиц, коэффициент размножения 1.2, минимальный уровень- 300 единиц, дискрет использования ресурса 100 единиц. Первый план состоит в том, что в первый и второй год ресурс не используется, а в третий год из имеющихся 1440 используются 1000 единиц и 440 остаются, а второй план состоит в том, что во второй год используются 900 единиц (больше нельзя) и далее в конце третьего года остаётся только 432 единицы ресурса. Это состояние (432) может далее не рассматриваться, так как состояние 440 (по первому плану) ему ни в чём не уступает, если получение прибыли от реализации 1000 единиц ресурса в третьем году может быть предпочтительнее прибыли от реализации 900 единиц ресурса во втором году.

Для реализации динамического программирования с использованием множеств Парето нужно отказаться от ложного стереотипа необходимости разбиения регулярной сетки и решать задачу от начального состояния в конечное. При анализе каждого перехода из каждого состояния нужно вычислить соответствующий ресурс, получаемый в результате такого перехода, и оценку нового состояния (суммарную прибыль от начала до нового состояния). Если в новое состояние приводит несколько путей, то надо оставить лучший из них (как в классической реализации метода Р. Веллмана), иначе нужно проверить не существует ли таких состояний, которые и по ресурсу и по целевой функции не хуже полученного. Если такие состояния есть, то рассматриваемый переход исключается, если нет, то наоборот нужно проверить не позволяет ли новое состояние исключить из рассмотрения уже имеющиеся. Другими словами, на каждом шаге должны оставаться только такие состояния, которые образуют множество Парето для двухкритериальной задачи: максимум прибыли при максимуме оставшихся ресурсов. Такие паретовские множества легко формировать, если на каждом шаге упорядочивать состояния по одному из критериев, например по оставшемуся ресурсу. Расчёты показали, что такое динамическое программирование с использованием множеств Парето существенно эффективнее и по памяти и по объёму вычислений, чем классическая реализация метода динамического программирования [27].

Численная реализация такого метода позволяет учесть и ограничения на расходование ресурса. Например, требуется всегда оставлять не меньше заданного числа или расходовать не больше заданного. Может быть учтено также и то, что коэффициент размножения р для различных состояний будет разный.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>