25. Принцип оптимальности Беллмана.

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

Суть принципа:

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

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

Условная оптимизация

Безусловная оптимизация

S _i – состояние системы на i-м шаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид:

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

Величина f_m(i) – есть максимальная прибыль завершения задачи из состояния i, если предположить, что на шаге m, система находится в состоянии i.

Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага (m+1) и далее, чтобы дойти до конца задачи.

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

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

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

Задача динамического программирования начинает решаться с конца, т.е. с последнего шага. Решается задача в 2 этапа:

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

2 этап (от начала к концу по шагам): Выбираются уже готовые рекомендации от 1-го шага до последнего и находится безусловное оптимальное управление х*, равный х*₁, х*₂, …, х*_m.

26.Формулировка задачи и характеристики смо

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

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

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

Основными элементами СМО являются источники заявок; их входящий поток; каналы обслуживания и выходящий поток. Это изображено на рис.

Входящий каналы выходящий

поток очередь обслуживания поток

• • • • •

• •

•

В зависимости от характера формирования очереди СМО различают:

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

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

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

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

Рассмотрим в отдельности элементы СМО.

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

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

Ординарность потока определяется невозможностью одновременного появления двух или более заявок.

Отсутствие последействия характеризуется тем, что поступление заявки не зависит от того, когда и сколько заявок поступило до этого момента. В этом случае вероятность того, что число заявок, поступивших на обслуживание за промежуток времени t, равно k, определяется по закону Пуассона. P_k(t)=( (λt)^k / k! ) е^-λt

Для такого потока время между двумя соседними заявками распределено экспоненциально с плотностью вероятности: f(t)= λ е^-λt

Случайное время ожидания в очереди начала обслуживания считают распределенным экспоненциально: f(t)=υе^-υt

Выходящий поток заявок связан с потоками обслуживания в канале,

и часто подчиняется показательному закону распределения с плотностью

f(t_обс)= μe^-μt

Важной характеристикой СМО, объединяющей λ и μ, является интенсивность нагрузки ρ=λ/ μ