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

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

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


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

Практические задачи, решаемые с применением классического динамического программирования

Задача об инвестициях

Пусть имеется п инвестиционных проектов П|, Ш,..., Пп и капитал К, который можно вложить в эти проекты. Для каждого проекта ожидаемый доход Di

(i=l ,2,___,п) зависит от вложенного в него капитала Xi. Предположим, что все

функции дохода Di(x) заданы.

Требуется найти такое распределение капитала по проектам, при котором суммарный доход максимален.

Эту задачу можно попытаться решить методами классического анализа. Пусть переменными являются Xi (i=l,2,...,n). Тогда требуется найти такие значения переменных, при которых

Можно выразить xi через все остальные переменные , подставить это выражение в целевую функцию и решать задачу безусловной максимизации полученной функции от n-1 переменной.

Можно и не исключать переменную xi, а ввести множитель Лагранжа X и решать задачу на безусловный максимум функции от

Эти пути малоперспективны, так как, во-первых, частные производные в точке максимума могут быть отличны от нуля, например, если некоторые функции Di(x) линейны, во-вторых, максимум может достигаться в точках, не удовлетворяющих условию 0

Из-за необходимости дополнительно учитывать очевидные ограничения 0

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

Этапы введём искусственно. Будем считать, что на первом этапе решается вопрос об инвестициях в первый проект, на втором этапе - во второй и т.д. и, наконец, на n-ом этапе - в последний. При этом, какой проект считать первым, а какой последним не имеет никакого значения. Далее, введём дискретность, то есть минимальную сумму, на которую могут отличаться инвестиции, и эту сумму примем за единицу (например, будем распределять в тысячах или миллионах рублей). «Состоянием системы» будем считать количество уже распределённого кап итала.

Начальное состояние (нулевой этап) задаётся числом нуль.

На первом этапе система может быть переведена в одно из состояний, которые определяются числом дискретов, содержащихся в К. Обозначим его через ш. На этом этапе решается судьба проекта Hi, в который может быть вложено 0,1,2,...,т единиц капитала. Это и будут состояния, в которые может быть переведена система после первого этапа. Каждому из них соответствует своё значение целевой функции, то есть доход, полученный от первого проекта Di(xi). Далее, состояние m означает, что весь капитал вложен в первый проект и последовательность состояний (вся траектория) будет m,m,...,m. Соответственно распределение капитала между проектами будет т,0,...,0. Состояние 0 после первого этапа означает, что в первый проект капитал не вкладывается и из этого состояния можно перейти в любое из 0,1,2,...,т состояний следующего этапа. Состояние р<ш после первого этапа означает, что осталось ш-р единиц капитала и, следовательно, из него можно перейти в любое из р, р+1,..., m состояние на следующем этапе. Начиная со второго этапа в каждое из состояний можно попасть разными путями и возможности дальнейшего распределения никак не зависят от того, как система попала в данное состояние. Поэтому, можно сравнивать варианты и в каждом из промежуточных состояний оставлять только один из них.

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

Итак, пусть имеется п=4 инвестиционных проекта, К=4 и дискрет равен 1, (например, распределяем 4 млн. руб. с дискретом 1млн. руб.). Функции дохода имеют следующий вид:

Составим таблицу возможных инвестиций в каждый из проектов и соответствующих доходов (таблица 3.1).

Таблица 3.1. Исходные данные

Инвестиции

Доходы

D,

d2

D3

d4

0

0

0

0

0

1

1

2

1

0.5

2

2

4

4

2

3

3

6

4

4.5

4

4

6

4

8

Начальное состояние (точка О) на рис. 3.10 соответствует нулевым инвестициям. После первого этапа инвестиции могут составить ОД ,2,3,4. Соответственно имеем пять точек на 1-ой вертикали. В скобках указан полученный доход Di, который на первом этапе, то есть от первого проекта, равен инвестициям в него.

Решение задачи об инвестициях

Рис. 3.10. Решение задачи об инвестициях

Далее, суммарные инвестиции в первый и второй проект, то есть состояния системы на втором этапе, снова могут составить те же величины 0,1,2,3,4. Но им будет соответствовать разный суммарный доход в зависимости от того, как они распределяются между первым и вторым проектами. Например, 3 млн. руб. можно распределить между первым и вторым проектами 4 способами:

0+3 с доходом 6 или 1+2 с доходом 5 или 2 +1 с доходом 4 или 3+0 с доходом 3. Варианты распределения соответствуют линиям, сходящимся в точке 3 на второй вертикали. Для этого состояния 3 на втором этапе выбираем вариант 0+3 с наибольшим доходом 6, запоминаем это число и номер состояния на предыдущем этапе (0), которому оно соответствует. Аналогично поступаем для всех состояний второго этапа: запоминаем наибольший доход из возможных при соответствующих инвестициях и состояние предыдущего этапа. На рис.3.10 на вертикали 2 для каждого суммарного значения инвестиций наибольший суммарный доход указан в скобках, а вариант, при котором он достигается показан сплошной линией. Переходя к третьему этапу, мы оказываемся в той же ситуации: известны все состояния предыдущего этапа и все возможные переходы в каждое из 5 возможных состояний. Характерно, что некоторые варианты могут оказаться равноценными, тогда оставляем любой из них. Например, в состояние 2 можно перейти из состояний 0, 1 или 2 предыдущего этапа, то есть вкладывая в третий проект 2, 1 или 0 с суммарным доходом 4, 3 или 4 соответственно. Переходы 0,2 и 2,2 равноценны. Аналогичная ситуация возникает и для состояния 3 с переходами 1,3 и 3,3 и суммарным доходом 6.

Переходя к последнему этапу, заметим, что нас может интересовать только состояние 4, то есть когда весь капитал вложен, иначе суммарный доход не будет максимальным. Оказывается, что два перехода (0,4) и (4,4) равноценны и дают одинаковый суммарный доход равный 8. Им соответствуют два равноценных распределения инвестиций 0+0+0+4 и 0+2+2+0.

В этом примере отсутствие производных функций D2 (х) при х=3 и Эз(х) при х=2 никак не сказывается на решении задачи.

Рассмотренная задача допускает обобщение на случай максимизации суммы функций, каждая из которых зависит от одной переменной, при наличии одного линейного ограничения в виде неравенства с положительными коэффициентами и целочисленности всех переменных Xi>0.

Это более общий случай задачи распределения ресурса, чем рассмотренная задача распределения капитала. В этой задаче ресурс - это слагаемое в последней сумме, относящееся к хь Суммарный ресурс ограничен величиной Ь.

Первый этап - выбор xi из интервала 0п. Условие ai>0 потребовалось для ограничения интервала изменения х. Состояние системы на любом этапе можно задать количеством распределённого ресурса (или оставшегося ресурса, что не имеет принципиального значения). Задача решается аналогично рассмотренной нами. Характерно, что при наличии двух линейных ограничений того же вида, задача может быть решена аналогично, но приходится рассматривать два вида ресурсов и соответственно требуется не одна, а две переменных, определяющих состояние системы. Это расход (или остаток) ресурсов каждого вида. Теоретически и при наличии большего числа ограничений того же вида задача может быть решена с помощью динамического программирования, но только теоретически. Дело в том, что число параметров состояния равно числу ограничений (видов распределяемых ресурсов) и при числе ограничений три и более вычислительные трудности могут стать непреодолимыми [23,27]. В этом случае предпочтительнее оказываются методы нелинейного программирования, хотя при наличии требований цело- численности они могут дать только приближённое решение с неизвестным отклонением от оптимума целочисленной задачи.

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