9758

тимальные управления на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса;

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

Аналогично рассуждая, можно выстроить и прямую схему условной опти-

мизации:

Оптимальное решение задачи в данном случае находится по следующей схе-

ме:

Z Z * (s ) X * (s ) Z * (s ) X * (s )

max n n 1 n n 1 n 1 n 2 n 1 n 2Z 2 (s1 ) X 2* (s1) Z1* (s0 ) X1* (s0 ).

Таким образом, построение модели динамического программирования и ре-

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

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

2.Определяют параметры состояния sk и переменные управления Xk на

каждом шаге, записывают уравнения состояний.

3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а

также условные оптимумы Z * (s ) и условное оптимальное управление на k- k k 1

ом шаге X k* (sk 1) ( k {1, 2, ..., n}).

4. Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две

последовательности: { Z * (s ) } и { X * (s ) }. k k 1 k k 1

101

5. Определяют оптимальное значение целевой функции Z * и оптимальное решение X * .

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

Задача распределения средств между предприятиями.

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

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

чения совокупной максимальной прибыли. Размеры вложений ресурсов xi

n

( i 1, n ; xi so ) в деятельность каждого хозяйствующего субъекта кратны не-

i 1

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

быль в размере fi(xi) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).

Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

Представим процесс распределения ресурсов между хозяйствующими субъ-

ектами как n-шаговый процесс управления (номер шага совпадает с условным номером хозяйствующего субъекта). Пусть sk ( k 1, n ) – параметр состояния, т.е.

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

шимися (n – k) хозяйствующими субъектами. Тогда уравнения состояний можно записать в следующем виде:

Введем в рассмотрение функцию Z * (s ), (k 1, n) – условно оптимальная

k k 1

совокупная прибыль, полученная от k-го, (k+1)– го, …, n-го хозяйствующих субъ-

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

102

sk 1 ( 0 sk 1 s0 ). Множество возможных управленческих решений относи-

тельно размера распределяемых ресурсов на k-ом шаге можно представить сле-

Пример. Имеется определенное количество ресурсов s0=100, которое необ-

ходимо распределить между n=4 хозяйствующими субъектами на текущую дея-

тельность в течение рассматриваемого периода (месяц) с целью получения сово-

n

купной максимальной прибыли. Размеры вложений ресурсов xi ( i 1, n ; xi so )

i 1

в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объ-

ема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) ( i 1, n ) (не зависит от вложения ресурсов в другие хозяйствующие субъекты):

103

Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

Решение.

Особенности модели: ограничения линейные, но переменные целочислен-

ные, а функции fi (x ) заданы таблично, поэтому нельзя применить методы цело-

численного программирования.

Составим рекуррентные уравнения Беллмана (обратную схему):

Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.

104

Таблица 1. Расчет условных оптимумов

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

3. Состоянием xi на і-м этапе является сумма денег на начало і-ого года,

которые могут быть инвестированы.

Заметим, что по определению li xi li . Следовательно,

где і=2,3,…n, x1=P1. Сумма денег xi, которые могут быть инвестированы,

включает лишь новые деньги и премиальные проценты за инвестиции, сделан-

ные на протяжении (і-1)-го года.

Пусть fi(xi) – оптимальная сумма инвестиций для интервала от і-го до n-го года при условии, что в начале і-го года имеется денежная сумма xi. Далее обо-

значим через si накопленную сумму к концу і -го года при условии, что li и

(xi –li ) – объемы инвестиций на протяжении і-го года в первый и второй банк соответственно. Обозначая i (1 ri ) , і=1,2, мы можем сформулировать зада-

чу в следующем виде.

Максимизировать z=s1 +s2 +…+sn , где

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

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

где xi +1 выражается через xi в соответствии с приведенной выше форму-

лой, а fn +1 (xn +1 )=0.

107

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

Задача о загрузке – это задача о рациональной загрузке судна (самолета,

автомашины и т.п.), которое имеет ограничения по объему или грузоподъемно-

сти. Каждый помещенный на судно груз приносит определенную прибыль. За-

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

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n

наименований. Пусть mi – количество предметов і-го наименования, подлежа-

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

Максимизировать z=r1 m1 +r2 m2 +…+rn mn .

при условии, что w1 m1 +w2 m2 +…+wn mn W, m1 ,m2 ,…,mn 0 и целые.

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

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

2.Варианты решения на этапе і описываются количеством mi предметов і-

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

Значение mi заключено в пределах от 0 до [W/wi ], где [W/wi ] – целая часть числа W/wi .

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

этапов вместе.

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

108

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

где fn +1 (xn +1 )=0.

Шаг 2. Выразим xi +1 как функцию xi для гарантии того, что левая часть по-

следнего уравнения является функцией лишь xi . По определению xi –xi +1 пред-

ставляет собой вес, загруженный на этапе і, т.е. xi -xi +1 =wi mi или xi +1 =xi – wi mi . Следовательно, рекуррентное уравнение приобретает следующий вид:

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

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

вание и ниже его производительность. Когда срок эксплуатации механизма до-

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

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

ного срока эксплуатации механизма.

Предположим, что мы занимаемся заменой механизмов на протяжении n

лет. В начале каждого года принимается решение либо об эксплуатации меха-

низма еще один год, либо о замене его новым.

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

Стоимость приобретения нового механизма остается неизменной на протяже-

нии всех лет и равна l.

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

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

2.Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтер-

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

109

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

низма к началу і-ого года.

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

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

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

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

Преимущества и недостатки метода динамического программирова-

ния. К числу положительных качеств можно отнести:

1.МДП дает возможность решать задачи, которые раньше не исследова-

лись из-за отсутствия соответствующего математического аппарата.

2.МДП в ряде случаев сокращает объем при поиске оптимальных реше-

ний.

Кнедостаткам относятся:

1.Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач (мы имеем только схему).

2.Трудности при решении задач большой размерности.

2.4 Контрольные вопросы

Контрольные вопросы к разделу 1 «Задачи линейного программиро-

вания и методы решения».

1.Задачи линейного программирования. Геометрическое решение задач линейного программирования.

2.Задачи линейного программирования. Симплексный метод.

3.Проблема поиска допустимого базисного решения.

4.Теория двойственности в решении задач линейной оптимизации.

110