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

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

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

Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага.

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

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

                        

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

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

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

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

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

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

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

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

 

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

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

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

 

Пример. Имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S₀ =100 д.ед. Функции дохода предприятий даны в матрице прибылей по каждому предприятию.

 

Х	1 предприятие f (х1)	2 предприятие f (х2)	3 предприятие f (х3)	4 предприятие f (х4)
20	3	2	3	3
40	4	5	4	6
60	9	8	9	8
80	11	7	5	7
100	12	15	12	14

Схема решения:

 

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

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

  Математическая модель задачи:

Экономический смысл переменных:

x_i – количество денег, вкладываемых в i предприятие.

S_i – количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге);

F(x_i) – прибыль от вложенной суммы денег;

S₀ – начальный капитал.

 

Рассмотрим 4-й шаг:

На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо  100 ден. ед. Тогда прибыль от вложения денег можно получить следующую.

 

S3	Х4	f (x4)	F4
0	0	0	0
20	20	3	3
40	40	6	6
60	60	8	8
80	80	7	7
100	100	14	14

Рассмотрим 3-й шаг:

На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо 100 ден. ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 ден. ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 ден. ед. можно поделить так (0;40), (20;20);

60 ден. ед. – (0;60), (20;40), (40;20), (60;0).

Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага

 

Прибыль на 3-м шаге берется максимальной по каждому вложению.

 

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг		Прибыль на шаге
S2	Х3	S3	f (x3)	F4	f+ F	F3
0	0	0	0	0	0	0
20	0	20	0	3	3	3
	20	0	3	0	3
40	0	40	0	6	6	6
	20	20	3	3	6
	40	0	4	0	4
60	0	60	0	8	8	9
	20	40	3	6	9
	40	20	4	3	7
	60	0	9	0	9
80	0	80	0	7	7	12
	20	60	3	8	11
	40	40	4	6	10
	60	20	9	3	12
	80	0	5	0	5
100	0	100	0	14	14	15
	20	80	3	7	10
	40	60	4	8	12
	60	40	9	6	15
	80	20	5	3	8
	100	0	12	0	12

Рассмотрим 2 -й шаг:

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг		Прибыль на шаге
S1	Х2	S2	f (x2)	F3	f+ F	F2
0	0	0	0	0	0	0
20	0	20	0	3	3	3
	20	0	2	0	2
40	0	40	0	6	6	6
	20	20	2	3	5
	40	0	5	0	5
60	0	60	0	9	9	9
	20	40	2	6	8
	40	20	5	3	8
	60	0	8	0	8
80	0	80	0	12	12	12
	20	60	2	9	11
	40	40	5	6	11
	60	20	8	3	11
	80	0	7	0	7
100	0	100	0	15	15	15
	20	80	2	12	14
	40	60	5	9	14
	60	40	8	6	14
	80	20	7	3	10
	100	0	15	0	15

 

Рассмотрим 1-й шаг:

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг		Прибыль на шаге
S0	Х1	S1	f (x1)	F2	f+ F	F1
100	0	100	0	15	15	15
	20	80	3	12	15
	40	60	4	9	13
	60	40	9	6	15
	80	20	11	3	14
	100	0	12	0	12

 

Анализ результатов:

Максимальная прибыль равна 15 д.ед. Расположить денежные средства между проектами можно несколькими способами:

 

1) 1 предприятие – 0 ден. ед.,  2 предприятие – 0 ден. ед.,  3 предприятие – 60 ден. ед.,  4 предприятие т – 40 ден. ед.

2) 1 предприятие – 0 ден. ед.,  2 предприятие – 100 ден. ед.,  3 предприятие – 0 ден. ед., 4 предприятие – 0 ден. ед.

3) 1 предприятие – 20 ден. ед., 2 предприятие – 0 ден. ед., 3 предприятие – 60 ден. ед.., 4 предприятие – 20 ден. ед.

4) 1 предприятие – 60 ден. ед.,  2 предприятие – 0 ден. ед., 3 предприятие – 20 ден. ед., 4 предприятие – 20 ден. ед.

5) 1 предприятие – 60 ден. ед.,  2 предприятие – 0 ден. ед.,  3 предприятие – 0 ден. ед.,  4 предприятие т – 40 ден. ед.

 

 

Практическое занятие № 11

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

Цель работы: научиться вычислять характеристики систем массового обслуживания. Формировать ОК 1 – ОК 9, овладеть знаниями и умениями, необходимыми для освоения ПК 1.1, ПК 1.2.

Подготовка к занятию: Повторить теоретический материал по теме «Системы массового обслуживания»

Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2015г.

Перечень необходимых приборов, инструментов, материалов: ПЭВМ

Задание на занятие:

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

Вариант 1

       Дежурный по администрации города имеет 8 телефонов. Телефонные звонки поступают с интенсивностью 120 заявок в час. Средняя продолжительность разговора составляет 2мин.

       Определить показатели дежурного администратора как объекта СМО.

 

Вариант 2

       На стоянке автомобилей возле магазина имеются 3 места, каждое из которых отводится под один автомобиль. Автомобили прибывают на стоянку с интенсивностью 20 автомобилей в час. Продолжительность пребывания автомобилей на стоянке составляет в среднем 15 мин. Стоянка на проезжей части не разрешается.

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

 

Вариант 3

       В службе «Скорой помощи» поселка круглосуточно дежурят 3 диспетчера, обслуживающие 3 телефонных аппарата. Если заявка на вызов врача к больным поступает, когда диспетчеры заняты, то абонент получает отказ. Поток заявок составит 4 вызова в минуту. Оформление заявки длится в среднем 1,5 мин.

       Определить основные показатели работы службы «Скорой помощи» как объекта СМО и рассчитать, сколько потребуется телефонных аппаратов, чтобы удовлетворить не менее 90% поступающих вызовов врачей.

Вариант 4

       АТС предприятия обеспечивает не более 5 переговоров, одновременно. Средняя продолжительность разговоров составляет 1 мин. На станцию поступает в среднем 10 вызовов в секунду.

       Определить характеристики АТС как объекта СМО.

 

Вариант 5

       В морской порт поступает в среднем 6 сухогрузов в сутки. В порту имеются 3 крана, каждый из которых обслуживает 1 сухогруз в среднем за 8 часов. Краны работают круглосуточно.

       Определить характеристики работы порта как объекта СМО.

 

Вариант 6

       В магазине покупателей обслуживают 2 продавца. Среднее время обслуживания одного покупателя – 4 мин. Интенсивность потока покупателей – 3 человека в минуту. Вместимость магазина такова, что одновременно в нем в очереди могут находиться не более 5 человек. Покупатель, пришедший в переполненный магазин, когда в очереди уже стоит 5 человек, не ждет снаружи и уходит.

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

 

Вариант 7

       Морской вокзал обслуживает касса с двумя окнами. В выходные дни, когда население активно морским сообщением, интенсивность потока сообщений составляет 0,9 человек/мин. Кассир затрачивает на обслуживание пассажира в среднем 2 мин.

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

 

Вариант 8      

На АЗС имеются 3 колонки. Площадка при станции, на которой машины ожидают заправку, может вместить не более одной машины, и если она занята, то очередная машина, прибывшая к станции, в очередь не становится, а проезжает на соседнюю АЗС. В среднем машины прибывают на станцию каждые 2 мин. Процесс заправки одной машины продолжается в среднем 2,5 мин.

       Определить вероятность отказа, абсолютную пропускную способность АЗС, среднее число машин, ожидающих заправку, среднее время ожидания машины в очереди, среднее время пребывания машины на АЗС (включая обслуживание).

 

Вариант 9

       Салон – парикмахерская имеет 4 мастера. Входящий поток посетителей имеет 5 человек в час. Среднее время обслуживания одного клиента составляет 40 мин.

       Определить среднюю очередь на обслуживание, считая ее неограниченной.

Вариант 10

       В мастерской бытового обслуживания работают 3 мастера. Если клиент заходит в мастерскую, когда все мастера заняты, то он уходит из мастерской, не ожидая обслуживания. Среднее число клиентов, обращающихся в мастерскую за 1 час, равно 20. Среднее время, которое затрачивает мастер на обслуживание одного клиента, равно 6 мин.

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

 

Порядок проведения занятия:

1. Получить допуск к работе.
2. Выполнить задание в соответствии со своим вариантом.
3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;
2. Выполненное задание;
3. Выводы по результатам выполненного задания;
4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. Что понимается под системами массового обслуживания (СМО) и для чего они предназначены?

2. На какие классы делятся СМО в зависимости от:

  а) характера потоков,

  б) числа каналов,

  в) дисциплины обслуживания,

  г) ограничения потока заявок,

  д) количества этапов обслуживания?

3. Что понимается под «потоком обслуживания заявок»?

4. Понятия входного и выходного потоков СМО.

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

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

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

 

ПРИЛОЖЕНИЕ

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

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

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

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

 

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

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

                                • • • •           •                        

                                                                  •              •      

                                                                               •

 

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

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

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

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

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

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

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

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

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

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

Отсутствие последействия характеризуется тем, что поступление заявки не зависит от того, когда и сколько заявок поступило до этого момента. В этом случае вероятность того, что число заявок, поступивших на обслуживание за промежуток времени t, равно k, определяется по закону Пуассона.

P_k(t)=((λt)^k / k!) е^-λt

где λ – интенсивность потока заявок, т.е. среднее число заявок в единицу времени:  (чел/мин, р/ч, автом/дн, кВт/ч), где  – среднее значение интервала времени между двумя соседними заявками;

k – число заявок, поступивших на обслуживание за промежуток времени t.

Для такого потока время между двумя соседними заявками распределено экспоненциально с плотностью вероятности:

f(t)= λ е^-λt

Случайное время ожидания в очереди начала обслуживания считают распределенным экспоненциально:

 f(t)=υе^-υt,

где υ – интенсивность движения очереди, т.е. среднее число заявок, приходящихся на обслуживание в единицу времени: , где  – среднее значение времени ожидания в очереди.

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

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

где μ – интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в ед. времени: μ=1/ t _обс (чел/мин, р/дн, кг/ч, докум/дн), t – среднее время обслуживания.

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

ρ=λ/ μ

СМО с отказами

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