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

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

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

Обозначим через u_kЄU_k управление на k-ом шаге (k=1,2,…,n). U_k – множество допустимых управлений на k-ом шаге.

Пусть u=(u₁,u_2,…,u_n)- управление, переводящее систему из состояния x₀ в состояние x_n. Обозначим через x_k состояние системы после k-го шага управления. Получаем последовательность состояний x₀, x₁, …, x_k-1, x_k, x_k+1, …, x_n (рис.5).

u₁ u₂ u_k-1 u_k u_k+1 u_k+2 u_n

… …

рис.5.

Показатель эффективности рассматриваемой управляемой операции зависит от начального состояния и управления: Z = F(x₀,u) (1)

uÎU – множество возможных управлений.

Сделаем несколько предположений:

1. Состояние X_K системы на k-ом шаге зависит только от предшествующего состояния Х_k-1 и управления на k-ом шаге u_k и управлений (свойство отсутствия последействия): X_k = j_k(x_k-1, u_k), k = 1, n – уравнения состояний (20), j_k – оператор перехода.

2. Целевая функция (1) является аддитивной от показателя эффективности каждого шага, т.е. выигрыш за всю операцию складывается из выигрышей на отдельных шагах.

Z = F(x₀, u) = f_k(x_k-1, u_k) (3)

f_k(x_k-1, u_k) = Z_k – показатель эффективности шага k (4).

Общая постановка задачи ДП. Определить такое допустимое управление uÎU, переводящее систему из состояния x₀ в состояние х_n, при котором целевая функция (3) принимает максимальное значение.

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

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

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

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

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

Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, (n-1)-ый шаг, и для каждого из этих предположений найти условное оптимальное управление на n-м шаге. «Условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился определенным образом.

Далее, «пятясь» назад, оптимизируем управление на (n-2)-м шаге и т.д., пока не дойдём до первого.

Предположим, что все условия оптимальные управления и условные оптимальные выигрыши за весь «хвост» процесса нам известны. Это значит: мы знаем, что надо делать, как управлять на данном шаге и что мы за это получим на «хвосте», в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно оптимальное, а просто оптимальное управление U* и найти не условно оптимальный, а просто оптимальный выигрыш Z*.

Таким образом, в процессе оптимизации управления методом ДП многошаговый процесс «проходится» дважды: первый раз – от конца к началу, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остаётся только «прочитать» уже готовое управления U*, состоящее из оптимальных шаговых управлений u₁*, u₂*, …, u_n*.

Предположим, что задача

Z = F(x₀, u) = f_k(x_k-1, u_k) max

x_k=j_k(x_k-1, u_k), k=1,5

u_kÎU_k, k=1, n

x_kÎX_k, k=0, n имеет решение.

Тогда справедлив принцип оптимальности Беллмана: оптимальное управление

u* = (u₁*, u₂*, …, u_n*) обладает тем свойством, что каковы бы ни были состояния системы

x*_k-1 на любом шаге и управление uk*, принимаемое в этом состоянии; последующие управляющие решения u*_k+1, …, u*_n должны составлять оптимальную стратегию относительно состояния х*_k, полученного в результате управляющего решения u_k*, т.е. состояния, к которому придёт система в конце данного шага.

На основании принципа оптимальности Беллмана можно получить основное уравнение ДП, или уравнение Беллмана.

Рассмотрим n-ый шаг: x_n-1 – состояние системы к началу n-ого шага, x_n – конечное состояние, u_n – управление на шаге n, а f_n(x_n-1, u_n) – целевая функция шага n.

Согласно принципу оптимальности, u_n нужно выбирать так, чтобы для любых состояний x_n-1 получить максимум целевой функции на этом шаге.

Обозначим через Z_n*(x_n-1) максимум показателя эффективности шага n при условии, что к началу последнего шага система была в произвольном состоянии x_n-1, а на последнем шаге управление было оптимальным.

Z_n*(x_n-1) = max f_n(x_n-1, u_n) (5)

Решив задачу (5), найдём для всех возможных состояний x_n-1 две функции: Z_n*(x_n-1) и U_n*(x_n-1) – условное оптимальное управление.

Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n-1)-ый (рис.6.)

Для любых состояний x_n-2, произвольных управлений U_n-1 и оптимального управления на шаге n значение целевой функции на двух последних шагах равно f_n-1(x_n-2, U_n-1) + Z_n*(x_n-1) (6).

Согласно принципу оптимальности необходимо искать максимум (6) по всем допустимым u_n-1.

Z*_n-1(x_n-2) = max { f_n-1(x_n-2, u_n-1) + Z_n*(x_n-1) }, k = n-1, 1 (7)

В результате максимизации получаем две функции: u*_n-1(x_n-2) и Z*_n-1(x_n-2)

Далее рассматривается трёхшаговая задача: к двум последним добавляется (n-2)-ой и т.д.

Так для произвольного k получим:

Z_k*(x_k-1) = max { f_k(x_k-1, u_k) + Z*_k+1(j(x_k-1, u_k)}, k = n-1, 1

Уравнение (8) называются уравнениями Беллмана, позволяющими найти предыдущие значения функции, зная последующие. Процесс решения уравнений (5) и (8) называется условной оптимизацией.

В результате условной оптимизации получаем две последовательности:

Z_n*(x_n-1), Z*_n-1(x_n-2), …, Z₁*(x₀) и u_n*(x_n-1), u*_n-1(x_n-2), …, u₁*(x₀)

Используя эти последовательности, можно найти решение задачи ДП при данных n и x₀:

Zmax = Z₁*(x₀)

5.2. Элементы теории управления запасами.

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

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

рис.7.

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

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

Широкое распространение в развитых странах получил классификационный подход к управлению запасами (АВС System). Его идея заключается в использовании классификации запасов и выделении трех групп – А, В, С, в зависимости от степени влияния данного вида запасов на рост товарооборота предприятия. К группе А относят запасы, реализация которых вносит наибольший вклад в объем товарооборота в денежном выражении.

Группы запасов	Доля в объеме товарооборота в денежном выражении	Доля в объеме запасов в натуральном выражении	Следует ли использовать сложные количественные методы управления
А	70%	10%	Да
В	20%	20%	В некоторых случаях
С	10%	70%	Нет

Относительно новым подходом к управлению запасами, является принцип управления Just-In-Time (JIT). Этот подход впервые был использован японскими корпорациями. Основная идея заключается в том, что запасы практически не создаются, а процесс доставки товаров поставщиками жестко согласован с технологическим процессом на предприятии. В настоящее время такой подход эффективно используется компаниями Toyota, General Motors и многими другими. Заказы размещаются с интервалом 3-4 часа и немедленно реализуются поставщикам. Эта система позволяет получить экономический эффект порядка миллиона долларов за счет сведения издержек хранения к нулю.

Наиболее распространенной является базовая модель EOQ (Economic Ordering Quantity), то есть, модель оптимального уровня запасов, заключающаяся в определении такого уровня запасов, поддержание которого минимизирует совокупные издержки управления ими. При этом, совокупные издержки разбиваются на три однородные группы: издержки хранения, издержки, связанные с формированием запасов и издержки, которые возникают вследствие недостатка товарных запасов.

В модели оптимального уровня запасов EOQ используются следующие обозначения:

S – объем реализации товаров в год;

N – количество заказов в год;

Q – размер одного заказа;

T – период реализации партии товаров;

A – средний размер имеющихся запасов в течении года;

P – цена закупки единицы товара у поставщиков;

C – средние издержки хранения (в % от стоимости товара);

T₁ – совокупные издержки хранения;

F – издержки размещения одного заказа и его транспортировка;

T₂ – совокупные издержки размещения и транспортировки запасов;

T – совокупные издержки управления запасами.

Размер одного заказа определяется прогнозируемым объемом реализации товаров в год и количеством заказов:

Средний размер имеющихся запасов в течении периода t, где, составляет

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

, а совокупные издержки размещения и транспортировки:

В этом случае совокупные издержки управления запасами T = T₁+T₂ =

Оптимальный уровень запасов Q*, минимизирующий совокупные издержки, является решением уравнения:

Теперь становится возможным определения оптимального количества заказов в год N* и оптимальное количество дней между заказами t*:

Следующим важным вопросом является вычисление точки заказа Q₀, то есть, такого уровня запасов, после достижения которого следует размещать заказ.

Q₀=t_n·q, где q – объем реализации товаров в день (коэффициент спроса).

5.3. Теория массового обслуживания.

1. Часто приходится сталкиваться с системами, предназначенными для многоразового использования при решении схожих задач. возникающие при этом процессы получили названия процессов обслуживания, а системы – систем массового обслуживания (СМО).

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

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

· Интенсивность потока λ – среднее число событий приходящиеся на единицу времени.

Интенсивность потока может быть как постоянной, так и переменной, зависящей от времени.

Для простейшего потока с интенсивностью λ интервал Т между соседними событиями имеет показательное распределение с плотностью: f(t)= λ·e^{- λt}, t > 0.

2. Рассмотрим математическую модель изменения численности популяции – процесс гибели и размножения. Граф состояний процессы гибели и размножения представлен на рис.8.

Найдём все финальные вероятности системы.

Рассмотрим упорядоченное множество состояний системы S₀, S₁, …, S_n. Из любого состояния переходы могут осуществляется только в состоянии с соседними номерами. Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями. Тогда для первого состояния S₀ имеем: λ₀₁·p₀= λ₁₀·p₁ (*)

Для второго состояния S₁: (λ₁₂+λ₁₀) ·p₁= λ₀₁·p₀ + λ₂₁·p₁

В силу (*) имеем: λ₁₂·p₁= λ₂₁·p₂.

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

λ₀₁·p₀= λ₁₀·p₁

λ₁₂·p₁= λ₂₁·p₂

_........

λ_{n-1 n} p_n-1= λ_{n n-1} p_n

Учтем нормировочное условие: p₀+ p₁+…+p_n =1

Решим систему уравнений:

p₁= ·p₀

p₂= ·p₁= ·p₀

........

p_n= ·p₀

Подставляя равенства в нормировочное условие, получаем

P ₀ = (1+ + +… +)^-1

3. Рассмотрим любую систему массового обслуживания и связанные с него два потока событий: поток заявок, прибывающих в СМО, и поток заявок, покидающих СМО. Если в системе устанавливается стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют одну и ту же интенсивность.

Пусть, Х(t) – число заявок, прибывших в СМО до момента t; Y(t) – число заявок покинувших СМО до момента t.

Обе функции являются случайными и меняются скачком в моменты переходов и уходов заявок. Функция Z(t)=X(t)-Y(t) – число заявок, находящихся в очереди. Рассмотрим очень большой промежуток времени Т и вычислим для него среднее число заявок, находящихся

в СМО:

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

Таким образом, при достаточно больших Т, можно считать что

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

Тогда, L _сист = t_i = · t_i·λ

Величина Tλ есть среднее число заявок, пришедших за время Т. Если разделить сумму всех времен t_i на среднее число заявок, то получится среднее время пребывания заявки в системе W_сист.

Получаем, что L_сист = λ·W_сист

Откуда. W_сист = ·L_сист – формула Литтла.

Таким же образом получается вторая формула Литтла: среднее время пребывания заявки в очереди равно отношению среднего числа заявок в очереди к интенсивности потока заявок:

4. Пусть имеется одноканальная СМО с очередью.

Предположим, что на очередь не наложено никаких либо ограничений (по длине, по времени ожидания).

На СМО поступает поток заявок с интенсивностью λ; поток обслуживаний имеет интенсивность m, обратную среднему времени обслуживания заявки t_об. Найдем финальные вероятности состояний СМО, а также характеристики ее эффективности: Lсист (среднее число заявок в системе), Wсист (среднее время пребывания заявки в очереди), L_or (среднее число заявок в системе), W_or (среднее время пребывания заявки в очереди), P_зан (вероятность того, что канал занят).

Абсолютная пропускная способность А СМО равна интенсивности потока заявок λ в силу того, что очередь неограниченна и все заявки будут обслужены. Откуда относительная пропускная способность СМО равна единице.

рис.9.

Состояния системы: S_o – канал свободен;

S₁ – канал занят, очереди нет;

S₂ – канал занят, одна заявка;

…

S_n – канал занят, n-1 заявок

Схема СМО с неограниченной очередью есть схема гибели и размножения с бесконечным числом состояний. Финальные вероятности для такой СМО существуют только тогда, когда система не перегружена (ρ < 1). Если приведенная интенсивность потока заявок больше либо равно единице (ρ ≥ 1), при t → ∞ очередь неограниченно растет.

Ряд в формуле представляет сбой геометрическую прогрессию и при ρ < 1 сходится

, , …,

Вероятности образуют геометрическую прогрессию. Самое вероятное состояние – канал свободен.

Найдем среднее число заявок в очереди

По формуле Литтла:

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

, ,

По формуле Литтла:

5. Рассмотрим многократную СМО с неограниченной очередью.

Состояния системы: S_o – все каналы свободны;

S₁ – занят один канал;

S₂ – занято два канала;

S_n – все каналы заняты;

S_n+1 – заняты все каналы, одна заявка в очереди;

S_{n + r} – заняты все каналы, r заявок в очереди.

Рис10

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

Пусть

, , …, , , …,

Среднее число занятых каналов:

Замечания: Допущение при котором анализировались рассмотрение выше СМО.

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

Вопросы для самоконтроля по главе

1. От чего зависит показатель эффективности управляемой операции?

2. Какой из путей решения многошаговой задачи считается проще – искать сразу все элементы решения на всех n шагах. Либо строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя лишь один шаг?

3. Сформулируйте принцип оптимальности Беллмана.

4. Какие подходы к управлению запасами существуют? Какие из них более распространены?

5. Какой случайный процесс называется Марковским?