Учебно-материальное обеспечение. 1. Наглядные пособия: Слайды с графами состояний и переходами в них на различных шагах

1. Наглядные пособия: Слайды с графами состояний и переходами в них на различных шагах.

2. ТСО: ___ Лектор – 2000._______________________________________

3. Приложения: _____ Раздаточный материал.________________________

СОДЕРЖАНИЕ

Введение

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

Вопрос № 1. Характеристика многошаговых распределительных задач.

В распределительных задачах с большим числом различных результатов производственной деятельности (i=1,n) и видов ресурсов (j=1,m) общее решение задачи оптимизации может быть при определенных условиях заменено совокупностью последовательно решаемых менее сложных частных задач оптимизации, например, по каждому из отдельных видов производственной деятельности. При этом важными понятиями ДП являются: последовательность шагов оптимизации, состояние системы распределения ресурсов и варианты решения (области изменения оптимизируемых переменных).

Вопрос№2. Метод динамического программирования. Принципы инвариантного погружения и оптимальности.

Рассмотрим сущность динамического программирования и введенных выше понятий на примере общей задачи линейного программирования: z =c₁x₁+c₂x₂+…+c_nx_n max,

a₁₁x₁+a₁₂x₂+…+a_1nx_n b₁,

a₂₁x₁+a₂₂x₂+…+a_2nx_n b₂,

…………………….

a_m1x₁+a_m2x₂+…+a_mnx_n b_m,

x₁,…x_n 0,

где z-целевая функция,подлежащая максимизации;

x_i-оптимизируемые переменные;

i=1,n-номер оптимизируемой переменной;

с_i-доход от реализации i-го вида производственной деятельности;

j=1,m-номер ограничений на значения переменных;

а_ij-коэффициенты уравнений-ограничений;

b_j-величина j-го ресурса (правая часть ограничений).

Здесь каждый вид производственной деятельности i может рассматриваться как отдельный шаг (этап) оптимизации; множество возможных значений переменных x_i как варианты решений, а количество каждого вида ресурса (B_i1,…,B_ij,…B_im),0 B_ij b_j, доступного для распределения на предыдущих и текущем (либо текущем и последующих) шагах как состояние модели. Тогда оптимальное значение целевой функции z для шагов i,i+1,…,n при заданных состояниях {B_ij} может быть записано в виде следующего рекуррентного соотношения (алгоритма прямой прогонки):

f_i(B_i1,…, B_{i m}) = max {c_i x_i + f_i-1(B_i1-a_i1x_i ,…,B_{i m-ai mxi})}, i =1,n;j =1,m, (1)

0 a_ijx_i B_ij

с начальными условиями f₀(B₀₁,…,B_{0 m})=0.

Оптимальное значение целевой функции для шагов n,…, i, i-1,…,1 в обратном времени при заданных состояниях {B_ij} может быть записано в виде следующего алгоритма обратной прогонки:

f_n(B_n1,…,B_nm)=max{c_nx_n}, 0 a_njx_n B_nj

f_i(B_i1,…,B_im)=max {c_ix_i+f_i+1(B_i1-a_i1x_i,…,B_{i m-ai mxi})},i=1,n;j=1,m, (2)

0 a_ijx_i B_ij

где 0 B_ij b_j.

Разница в алгоритмах прямой и обратной прогонки в способе определения состояния модели. В прямой модели B^/_{i j}- количество ресурса j-го типа, распределяемого от первого шага до i-го, а для обратной модели B_ij- количество ресурса, распределяемого на всех шагах от i-го до n-го. Процесс решения задачи включает два этапа. На первом этапе пошаговые задачи оптимизации приводят к условно-оптимальным по ресурсу решениям и одному (конечному) безусловно-оптимальному решению. На втором этапе формируется окончательная безусловно-оптимальная стратегия путем учета полученного на первом этапе конечного решения и обратного по шагам анализа условно-оптимальных решений.

Решение задачи (1) основывается на двух основополагающих принципах.

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

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

Вопрос№3. Методика реализации принципа оптимальности. Примеры.

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

Пример№1.Оптимизация производства услуг в сети спутниковой связи.

Пусть для сети спутниковой связи необходимо оптимизировать производство услуг двух типов: x_a и x_б по критерию вида

max z = 3x_a + 2x_б ,

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

x_а + 2 x _б 6,

2 x_а + x_б 8,

- x_а + x_б 1,

x_б 2,

[x_а ],[x_б ] 0.

Здесь вектор состояния (B_i1,B_i2) определяется двумя видами ресурсов: числом телеграфных и телефонных каналов, подлежащих распределению на i-м шаге,т.е.0 B_i1 6 и 0 B_i2 8. Варианты решений определяются допустимой областью определения переменных x_i, подлежащих оптимизации. Шаги оптимизации определяются порядком оптимизации различных видов услуг связи: на первом шаге i=1 оптимизируется число услуг типа а, на втором шаге i=2 оптимизируется число услуг типа б.

Далее рассмотрим реализацию алгоритма ДП для случая обратной прогонки (1).

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

f₂(B₂₁,B₂₂)= max{2x_б},

0 2x_б B₂₁

0 x_б B₂₂

т.к.из ограничений следует, что x_б min {B₂₁/2,B₂₂}, а f₂ (x_б|B₂₁,B₂₂)= 2x_б, то,подставляя первое во второе, получим f₂(B₂₁,B₂₂) = max { f₂ (x_б|B₂₁,B₂₂)=

x_б

=2min{ B₂₁/2,B₂₂}, откуда x^*_б=min{ B₂₁/2,B₂₂}.

Т.е. оптимальное значение числа услуг типа б, получаемое на шаге 2, равно минимальному из двух видов ресурсов (числу телеграфных B₂₁ /2 или телефонных каналов B₂₂), распределяемых на втором шаге.

Далее для шага 1 имеем:

f₁(B₁₁,B₁₂) = max {3x_a+f₂(B₁₁-x_a,B₁₂-2x_a)}= max {3x_a+2min{(B₁₁-x_a)/2,B₁₂-2x_a}},

0 x_a B₁₁ 0 x_a B₁₁

0 2x_a B₁₂ 0 2x_a B₁₂

где B₁₁=6 и B₁₂=8 для первого шага оптимизации.

Подставляя значение ресурсов ТГ и ТФ каналов в ограничения, получим обобщенное ограничение в виде x_a min(B₁₁,B₁₂/2)= 4. Учитывая пропорциональную зависимость значения целевой функции от значения x_a, оптимальное (максимальное) ее значение f₁^*= 12 соответствует решению x_a^*= 4.

Второй этап. Решение на втором (начальном для обратной прогонки) шаге оптимизации числа предоставляемых услуг x_б необходимо проводить для следующего состояния по ресурсам: B₂₁ = B₁₁- x_a^*=6-4=2; B₂₂ = B₁₂- 2x_a^* =8-8=0. Откуда

x_б^*= min { B₂₁/2, B₂₂ }= min { 1, 0 }= 0.

Таким образом, пошаговое решение задачи линейного программирования методом динамического программирования обеспечило в целом оптимальную стратегию производства услуг в одну единицу времени x_a= 4, x_б = 0 при максимальном для случая целочисленного решения значении дохода сети спутниковой связи z = 12 у.е./ед.вр.

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

	ci xi + fi+1(Bi+1 j )	fi* (Bi j )	xi *
Bi j	xi =0	…	xi = K
bj

Пример№2.Задача оптимального распределения ресурсов резервирования в радиорелейной линии связи.

Рассмотрим радиорелейную линию, состоящую из n интервалов. В случае независимых технических отказов различных интервалов вероятность безотказной работы всей РРЛ определяется выражением [ 4 ]:

где P_i –вероятность безотказной работы i-го интервала.

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

где q_i и p_i –вероятность отказа и вероятность безотказной работы элемента на i-м интервале соответственно; x_i- число резервных станций на i-м интервале; 1+x_i –общее число (одна рабочая и x_i резервная) станций в i-м интервале.

Пусть также введены ограничения на число резервных станций x_i 2;i=1,n. При этом суммарная стоимость резервных элементов с учетом известных ограничений на число станций в подразделении, развертывающем РРЛ не может превысить величины С = 1200у.ед.

Остальные исходные данные, содержащие сведения о надежности p_i(x_i) и стоимости резервных средств c_i(x_i) i-го интервала, даны в таблице 1.

xi	i=1	i=2	i=3
p1(xi)	C1(xi)	p2(xi)	C2(xi)	p3(xi)	C3(xi)
	0,70 0,91 0,973		0,60 0,84 0,936		0,50 0,75 0,875

В таблице1 значения вероятностей безотказной работы i-х интервалов при использовании в них x_i резервных станций определяются из выражения

p_i(x_i) = 1-(1-p_i)^1+x_i,

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

Необходимо определить количество резервных станций на каждом интервале x_i^опт обеспечивающих максимальную надежность РРЛ, т.е.

P_л( )=

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

Для решения задачи применим метод динамического программирования и, в частности, алгоритм обратной прогонки. При этом номер шага соответствует номеру интервала, под состоянием s_i () понимается суммарная стоимость основного и резервного оборудования, задействованного на i-м и последующих интервалах, а под вариантами решения x_i понимаем число резервных элементов в i-м интервале.

Рекуррентное соотношение для функции Беллмана в данном случае может быть записано в виде:

F_n(s_n) =

F_i (s_i)=

i=1,2,…,n-1.

Из таблицы №1 найдем границы изменения состояния s_i на каждом шаге: s_3min=c₃(x₃=0)=300у.е.,

s_3max= , s_2min= s_2max ,s₁=

На первом этапе алгоритма обратной прогонки рассматривают шаг 3. Найденные на этом и предыдущих шагах значения критерия и условно-оптимальные решения для всех допустимых значений s_i и оптимизируемых переменных x_i=0,1,2 представим в таблицах№2,3,4.

Шаг 3 Таблица№2

S3	P3(X3)	Условное оптимальное решение
X3=0	X3=1	X3=2	F3(s3)	X3опт
P=0,5 C3=300	P=0,75 C3=600	P=0,875 C3=900
	0,5 0,5 0,5 0,5 0,5 0,5 0,5	- - - 0,75 0,75 0,75 0,75	- - - - - - 0,875	0,5 0,5 0,5 0,75 0,75 0,75 0,875

Шаг№2 Таблица№3

S2	P2(X2)=f3(s2-c2(x2))	Условное оптимальное решение
X2=0	X2=1	X2=2	F2(s2)	X2опт
P=0,6 C2=200	P=0,84 C2=400	P=0,936 C2=600
	0,3 0,3 0,3 0,45 0,45 0,45 0,525	- - 0,42 0,42 0,42 0,63 0,63	- - - - 0,468 0,468 0,468	0,3 0,3 0,42 0,42 0,468 0,63 0,63

Здесь значения функции Беллмана на втором шаге определяются с учетом ее значения на предыдущем шаге согласно выражению

F_i(c_i)= p_i(x_i)F_i+1( -c_i).

Шаг3 Таблица№4

S1=	P1(X1)	Безусловное оптимальное решение
X1=0	X1=1	X1=2	F1(s1)	X1опт
P=0,7 C1=100	P=0,91 C1=200	P=0,973 C1=300
	0,441	0,5733	0,4554	0,5733

Безусловное оптимальное решение на первом этапе получено лишь для шага 3 (числа резервных станций на первом интервале x₁^опт=1), поэтому окончательная стратегия относительно необходимых резервных станций в каждом из трех интервалов может быть получена лишь на втором этапе –этапе анализа результатов пошаговой оптимизации.

Так как x₁^опт=1, то величина ресурса, подлежащая распределению на первом и втором шагах будет равно S₂= у.е. Тогда из таблицы№3 для S₂=1000 получим оптимальное число резервных станций во втором интервале: x₂^опт=1. Следовательно, состояние S₃= . Наконец, из таблицы №4 для S₃=600 имеем оптимальное число резервных станций на третьем интервале: x₃^опт=1.

Окончательно, оптимальная стратегия распределения резерва имеет вид: , т.е. на каждом радиорелейном интервале должно находиться по одной резервной радиорелейной станции. Вероятность безотказной работы РРЛ при этом составляет P_РРЛ= 0,5733; Суммарные затраты и затраты по интервалам составляют ;С₁=200; С₂=1000; С₃=600у.е.. Интервальные вероятности безотказной работы составляют p₁(x₁=1)=0,91; p₂(x₂=1)=0,84; p₃(x₃=1)=0,75.

Заключение

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