2. Общее описание процесса моделирования и построения вычислительной схемы динамического программирования

Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям:

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

2. Структура задачи инвариантна относительно числа шагов п, т. е. должна быть определена для любого n и не зависеть от этого числа.

3. На каждом шаге состояние системы определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от числа шагов п.

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

Построение модели ДП сводится к следующим основным моментам:

1) выбирают способ деления процесса на шаги;

2) вводят параметры состояния и переменные управления на каждом шаге процесса;

3) записывают уравнение состояния

(3.1)

4) вводят показатели эффективности на k-м шаге и суммарный показатель - целевую функцию

(3.2)

5) вводят в рассмотрение условные максимумы показателя эффективности от k-гo шага (включительно) до конца процесса и условные оптимальныеуправления на k-м шаге

6) из ограничений задачи определяют для каждого шага множества Dk допустимых управлений на этом шаге;

7) записывают основные для вычислительной схемы ДП функциональные уравнения Беллмана

(3.3)

(3.4)

динамическое программирование уравнение беллман

Несмотря на единообразие в общем построении модели ДП, приведенном выше, вычислительная схема строится в зависимости от размерности задачи, характера модели (дискретной или непрерывной), вида функций (3.1), (3.2) и других характеристик модели. При всем разнообразии вычислительных схем ДП можно отметить в них некоторые общие черты.

1. Решение уравнений (3.3) проводят последовательно, начиная с (3.4). Этот этап получил название условной оптимизации.

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

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

4. После выполнения первого этапа (условной оптимизации) приступают ко второму этапу -- безусловной оптимизации.

а) Если начальное состояние задано ,
то непосредственно определяют максимум целевой
функции

(3.5)

а затем -- искомое безусловное оптимальное управление по цепочке

(3.6)

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

б) Если задано множество начальных состояний,
, то дополнительно решают еще одну задачу на максимум:

(3.7)

откуда находят , а затем, как и в п. а), по цепочке (3.6) --безусловное оптимальное управление.

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

(3.8)

Они могут быть получены решением уравнений (1.1) относительно . Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k-го включительно -- величины . Повторив рассуждения п. 2.2.2., придем к следующей форме уравнений Беллмана:

(3.9)

(3.10)

В результате решения этих уравнений получим последовательности

(3.11)

Этап безусловной оптимизации не отличается принципиально от аналогичного этапа в обратном ходе вычислений: , если задано, или

(3.12)

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

(3.13)

2.1 Минимизация затрат на строительство и эксплуатацию предприятий

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

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

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

Введем обозначения:

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

xi -- количество ресурса, используемого по i-му способу (i = );

gi(xi) -- функция расходов, равная, например, величине затрат на производство при использовании ресурса xi по i-му способу;

цk(x) -- наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.

Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:

при ограничениях

Экономический смысл переменных xi состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности.

Рассмотрим конкретную задачу по размещению предприятий.

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

Необходимо разместить предприятия таким образом, чтобы обеспечить минимальные суммарные затраты на их строительство и эксплуатацию. Значения функции затрат gi(x) приведены в табл. 29.4.

В данном примере gi(х) -- функция расходов в млн р., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе;

цk(x) -- наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предприятий в первых k районах.

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

для остальных районов

Задачу будем решать в три этапа.

1-й этап. Если все предприятия построить только в первом районе, то

минимально возможные затраты при х = 5 составляют 76 млн р.

2-й этап. Определим оптимальную стратегию при размещении предприятий только в первых двух районах по формуле

Найдем ц2(l):

g2(1) + ц1(0) = 10 + 0 = 10,

g2(0) + ц1(l)= 0 +11 = 11,

ц2(l) = min (10, 11) = 10.

Вычислим ц2(2):

g2(2) + ц1(0) = 19 + 0 = 19,

g2(l) + ц1(l) = 10 + 11 = 21,

g2(0) + ц1 (2) = 0 + 18 = 18,

ц2(2) = min (19, 21, 18) = 18.

Найдем ц2(3):

g2(3) + ц1 (0) = 34 + 0 = 34,

g2(2) + ц1(l) = 19 + 11 = 30,

g2(1) + ц1(2) = 10 + 18 = 28,

g2(0) + ц1(3) = 0 + 35 = 35,

ц2(3) = min (34, 30, 28, 35) = 28.

Определим ц2(4):

g2(4) + ц1(0) = 53 + 0 = 53,

g2(3) + ц1(l) = 34 + 11 = 45,

g2(2) + ц1(2) = 19 + 18 = 37,

g2(l) + ц1(3) = 10 + 35 = 45,

g2(0) +ц1(4) = 0 + 51 = 51,

ц2(4) = min (53, 45, 37, 45, 51) = 37.

Вычислим ц2(5):

g2(5) + ц1(0) = 75 + 0 = 75,

g2(4) + ц1(l) = 53 + 11 = 64,

g2(3) + ц1(2) = 34 + 18 = 52,

g2(2) + ц1(3) = 19 + 35 = 54,

g2(1) + ц1(4) = 10 + 51 = 61,

g2(0) + ц1(5) = 0 + 76 = 76,

ц2(5) = min (75, 64, 52, 54, 61, 76) = 52.

3-й этап. Определим оптимальную стратегию при размещении пяти предприятий в трех районах по формуле

ц3(x) = min{g3(x3) + ц2(x - х3)}.

Найдем ц3(5):

g3(5) + ц2(0) = 74 + 0 = 74,

g3(4) + ц2(1) = 54 + 10 = 64,

g3(3) + ц2(2) = 36 + 18 = 54,

g3(2) +ц2(3) = 20 + 28 = 48,

g3(1) + ц2(4) = 9 + 37 = 46,

g3(0) + ц2(5) = 0 + 52 = 52,

ц3(5) = min (74, 64, 54, 48, 46, 52) = 46.

Минимально возможные затраты при х = 5 составляют 46 млн р.

Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн р. на 3-м этапе получены как 9 + 37, т.е. 9 млн р. соответствуют строительству одного предприятия в третьем районе (см. табл. 29.4). Согласно 2-му этапу 37 млн р. получены как 19 + 18, т.е. 19 млн р. соответствуют строительству двух предприятий во втором районе. Согласно 1-му этапу 18 млн р. соответствуют строительству двух предприятий в первом районе.

Ответ. Оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 ден. ед.

Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные затраты на его сооружение были минимальные.

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на сооружение каждого из отрезков известны (рис. 29.2) в млн р.

Разделим расстояние от А до В в восточном направлении на 4 части, в северном - на 3 части. Путь можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы (узловой точки) найдем условное оптимальное управление. Оно выбирается так, чтобы стоимость всех оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в обратном направлении, т.е. от точки В к точке А.

Найдем условную оптимизацию последнего шага (рис. 29.3).

В точку В можно попасть из B1 или В2. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг (рис. 29.4).

Для точки В3 условное управление -- по оси X, а для точки B5 -- по оси Y. Управление для точки В4 выбираем как

т.е. по оси Y.

Условную оптимизацию проводим для всех остальных узловых точек (рис. 29.5).

Получим

где с -- север, в --восток.

Минимальные затраты составляют

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим:

Затраты составят 10 +12 + 11 + 10 + 9 + 13 +10 = 75 > 71.

Ответ. Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в, при этом затраты будут минимальные и составят 71 млн р.