Алгоритм прямой прогонки.

Анализ чувствительности решения.

Оптимальность по Парето.

Краткое содержание лекции

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

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

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

2. Расчленить операцию на этапы (шаги).

3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.

4. Определить какой выигрыш приносит на i-ом шаге управление x_i, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:

.

5. Определить, как изменяется состояние S системы S под влиянием управление x_i на i-ом шаге: оно переходит в новое состояние

. (1)

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

. (2)

Этому выигрышу соответствует условное оптимальное управление на i-м шаге x_i(S) (причем в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние )

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле

8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (2), полагая в ней i=(m-1), (m-2), …, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния S₀. Это и есть оптимальный выигрыш за всю операцию

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (1); для вновь найденного состояния найти оптимальное управление на втором шаге х₂^* и т.д. до конца.

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

(если только выигрыши w_i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (2) вместо знака «плюс» ставится знак «умножения»:

Задача планирования рабочей силы

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

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

Если x_i – количество работающих на протяжении i-й недели, то возможны затраты двух видов: 1) С₁(x_i- b_i)-затраты, связанные с необходимостью содержать избыток x_i - b_i рабочей силы и 2) С₂(x_i- x_i-1)-затраты, связанные с необходимостью дополнительного найма (x_i- x_i-1) рабочих.

Элементы модели динамического программирования определяются следующим образом:

1. Этап і представляется порядковым номером недели і, і=1, 2, …n.

2. Вариантами решения на і-ом этапе являются значения x_i – количество работающих на протяжении і-й недели.

3. Состоянием на і-м этапе является x_i-1 – количество работающих на протяжении (і-1) –й недели (этапа).

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

где

Вычисления начинаются с этапа n при x_n=b_n и заканчиваются на этапе 1.

Задача замены оборудования:

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

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

Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l.

Элементы модели динамического программирования таковы:

1. Этап і представляется порядковым номером года і, і=1, 2,...n.

2. Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.

3. Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.

Пусть f_i(t)-максимальная прибыль, получаемая за годы от і до n при условии, что в начале і-ого года имеется механизм t-летнего возраста.

Рекуррентное уравнение имеет следующий вид:

(1)-если эксплуатировать механизм,

(2)-если заменить механизм.

Задача инвестирования:

Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P₁, P₂, …, P_n соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r₁, а второй - r₂. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.

Премиальные меняются от года к году, и для і-ого года равны q_i1 и q_i2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.

Элементы модели динамического программирования следующие:

1. Этап і представляется порядковым номером года і, і=1, 2,...n

2. Вариантами решения на і-м этапе (для і-ого года) являются суммы l_i и инвестиций в первый и второй банк соответственно.

3. Состоянием x_i на і-м этапе является сумма денег на начало і-ого года, которые могут быть инвестированы.

Заметим, что по определению =x_i-l_i. Следовательно,

где і=2, 3, …n, x₁=P₁. Сумма денег x_i, которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (і-1)-го года.

Пусть f_i(x_i)- оптимальная сумма инвестиций для интервала от і-го до n-го года при условии, что в начале і-го года имеется денежная сумма x_i. Далее обозначим через s_i накопленную сумму к концу n-го года при условии, что l_i и (x_i-l_i)-объемы инвестиций на протяжении і-го года в первый и второй банк соответственно. Обозначая , і=1, 2, мы можем сформулировать задачу в следующем виде.

Максимизировать z=s₁+s₂+…+s_n, где

Так как премиальные за n-й год являются частью накопленной денежной суммы от инвестиций, в выражения для s_n добавлены q_n1 и q_n2.

Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид

где x_i+1 выражается через x_i в соответствии с приведенной выше формулой, а f_n+1(x_n+1)=0.

Задача о загрузке

Задача о загрузке – это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль.

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n наименований. Пусть m_i-количество предметов і-го наименования, подлежащих загрузке, r_i-прибыль, которую приносит один загруженный предмет і-го наименования, w_i-вес одного предмета і-го наименования. Общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z=r₁m₁+r₂m₂+…+r_nm_n при условии, что

w₁m₁+w₂m₂+…+w_nm_n W,

m₁, m₂, …, m_n 0 и целые.

Три элемента модели динамического программирования определяются следующим образом:

1. Этап і ставится в соответствии предмету і-го наименования, і=1, 2, …n.

2. Варианты решения на этапе і описываются количеством m_i предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение m_i заключено в пределах от 0 до [W/w_i], где [W/w_i] – целая часть числа W/w_i.

3. Состояние x_i на этапе і выражает суммарный вес предметов, решения о погрузке которых приняты на этапах і, і+1,...n. Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.

Пусть f_i(x_i)-максимальная суммарная прибыль от этапов і, і+1,..., n при заданном состоянии x_i. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.

Шаг 1. Выразим f_i(x_i) как функцию f_i+1(x_i+1) в виде

где f_n+1(x_n+1)=0.

Шаг 2. Выразим x_i+1 как функцию x_i для гарантии того, что левая часть последнего уравнения является функцией лишь x_i. По определению x_i-x_i+1 представляет собой вес, загруженный на этапе і, т.е. x_i-x_i+1=w_im_i или x_i+1=x_i-w_im_i. Следовательно, рекуррентное уравнение приобретает следующий вид:

Рекуррентные соотношения для процедур прямой и обратной прогонки

Фермеру принадлежит стадо овец, насчитывающее k голов. Один раз в год фермер принимает решение о том, сколько овец продать и сколько оставить. Прибыль от продажи одной овцы в і-м году составляет p_i. Количество оставленных в i-м году овец удваивается в (1+1)-м году. По истечении п лет фермер намеревается продать все стадо.

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

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

Обозначим количества оставленных и проданных в j-м году овец через x_j и y_j, соответственно. Положим Zj, =x_j+y_j. Из условий задачи следует, что

z₁=2x₀=2k, z_j=2x_j-1, j=l, 2,..., n.

Состояние на этапе j можно описать с помощью переменной z_j, которая выражает количество имеющихся к концу этапа j овец для распределения на этапах j+1, j+2,..., n, или с помощью переменной x_j, которая выражает количество имеющихся к началу этапа j+1 овец, обусловленное принятыми на этапах 1, 2,..., j решениями. Первое определение ориентировано на построение рекуррентного соотношения для процедуры обратной прогонки, тогда как второе определение приводит к использованию алгоритма прямой прогонки.