Исследование операций (стр. 10 )

9) Пользуясь формулой (А), составим матрицу Х:

	S	1	2	3	4	t
S		10		12	3
1				5	5
2						10
3			10		5	2
4						13
t

Z = 10 + 12 + 3 = 25

 

Графическое решение показано на рисунке:

5

 

3

12

10

10

13

10

5

5

ЛЕКЦИЯ 11

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

Простейшим (или стационарным пуассоновским )называется поток стационарный + без последствий + ординарный. Если поток не стационарен, но без последствий и ординарен, он называется нестационарным пуассоновским потоком. В таком потоке интенсивность l (среднее число событий за единицу времени ) зависит от времени :

l = l(t) ,

в простейшем l = const.

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

( m=0, 1, ... )

где Q- среднее число событий, приходящиеся на участок длиной t .

Для стационарного пуассоновского потока

a = l*t ,

для нестационарного :

где t0 - точка, с которой начинается участок t .

Для описания распределения интервалов времени между событиями простейшего потока используется экспоненциальный закон

f(t)=le -lt ( t>0 ) ,

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

mt =1/l; (dt)2 = 1/l2

Доказано что, для простейшего потока:

Р1(Dt ) =l(t)Dt; Р0(Dt )= 1- Р1(Dt ),

где Р1(Dt ) и Р0(Dt ) вероятности попадания на интервал Dt 1 или 0 событий.

Пуассоновские потоки событий и непрерывные марковские цели.

Рассмотрим систему S, в момент t находящегося в состоянии L, как только

придет заявка из пуассоновского потока с интенсивностью lij, система перейдет в состояние S j, вероятность появления заявки за интервал Dt : = lijDt, естественно что она равна вероятности перехода из Sj в Sj.

Для марковского процесса такая вероятность равна lijDt

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

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

Предельные вероятности состояний

Пусть имеется система S с дискретными сосотояниями :

S1, S2, ... Sn,

в котором протекает марковский случайный процесс с непрерывным временем. Предположим, что все интенсивности потоков событий, переводящих систему из состояния в состояние, постоянны : lij = const,

то есть все потоки событий - простейшие ( стандартные пуассоновские ) потоки.

Записав уравнение Колмогорова и решив их, получим вероятности систояний, как функции времени

Р1(t ), Р2(t ), . . . , Рn(t ), Рi(t )=1

Поставим теперь вопрос : Что будет происходить с системой при t.

Пределы функций Рi(t ), если они существуют, называются предельными вероятностями состояний.

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

Предельные вероятности пропорциональны среднему времени пребывания в каждом состоянии, в установившемся предельном стационарном режиме.

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

Пример

0 = -5p1 + p3 0 = - p2 + 2p1+2p3 0 = -3p3 + 3p1+2p4 0 = -2p4 + p2

S1

3

2

1

2

S3

S2

1

S4

2

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

p1 + p2 +p3 + p4 = 1,

получим :

p1 = 1/24, p2=1/2, p3=5/24, p4=1/4

Процесс гибели и размножения

l32

Sn

S2

S1

Марковская цель вида :

l23

l21

l12

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

S1 : p1l12=l21p2 ( 1 )

S2 : p2l21+l23p2= p1l12+l32p3

но в силу (1) можно сократить, поэтому :

p2l23=l32p3

и так далее.....

pk-1lk-1,k = lk, k-1pk

ЛЕКЦИЯ 11

Динамическое программирование.

Динамическое программирование ( или точнее по смыслу “динамическое планирование”) - математический метод оптимизации, специально приспособленный к многошаговым ( или многоэтапным операциям ) .

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

Н каждом шаге процесса принимается какое-то решение - т. е. управление операцией складывается из ряда элементарных управлений на каждом шаге.

Пример:

На предприятии имеется k производителей : П1, . . . , Пk. Планируется деятельность предприятия на период времени Т равный М месяцев. Предприятие взяло кредит на срок Т = m месяцев. В начале работы выделяются какие-то основные средства, которые распределяются между производителями. В прцессе работы, рабочие средства расходуются. Доход, приносимый каждым из производителей, зависит от вложенных средств. В начале каждого месяца средства могут переопределяться между производителями.

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

Пред нами типичная задача динамического программирования.

Если обозначить (xi)( j ) - средства, выделяемые на i - м этапе j - му предприятию ;

- управление на i-м шаге ; - управление операций в целом.

то эффективность управления можно оценить критерием :

Управление , при котором показатель W достигает максимума - оптимальное управление, обозначим это маленькой буквой u :

В нашем примере показатель эффективности можно записать:

, где wi - доход предприятия ( сумма доходов производств)

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

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

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

Однако из этого правила есть исключеие. Среди всех шагов есть один, который может планироваться “без оглядки на будущее” - это последний шаг.

Спланировав оптимально последний шаг, можно “пристроить” к нему и предпоследний.

Пример:

Самолет, летящий на высоте H0 со скоростью V0 должен подняться до высоты Hw и разогнаться до скорости Vw. Затраты горючего для подъема на определенную высоту и разгона даны на графике :

C3

B1

C1

H0

Hw

	20	18	16	15	14	12	15	17
B2   10	12 17	13 14	13 13	14 10	15 11	14 13	13 14	14 17
9	8 14	9 13	10 12	11 10	12 9	13 8	12 11	12 15
7	6 12	8 13	7 12	8 10	10 11	11 13	10 15	9 20
8	7 10	8 8	9 8	9 8	10 10	11 12	8 13	7 15
10	8 11	10 9	11 8	10 7	11 9	12 13	10 14	9 18
11	9 12	10 11	12 10	13 9	14 13	14 14	12 17	10 20

H