В.3. Общая схема применения метода дп (алгоритм метода дп):

П. все требования, предъявляемые к задаче ДП, выполнены.

Построение модели ДП и применение метода ДП для решения сводится к следующим моментам:

1. Выбирают способ деления процесса управления на шаги.

2. Определяют параметры состояний S_k и переменные управления Х_k на каждом шаге.

3. Записывают уравнения состояний .

4. Вводят целевые функции каждого шага и суммарную целевую функцию: и

5. Вводят в рассмотрение условный максимум (минимум) целевой функции (т.е. условный оптимальный выигрыш); и условное оптимальное управление на k – ом шаге (управление, при котором достигается максимум (минимум) ). . И записывают основные для вычислительной схемы ДП уравнения Беллмана:

для условного оптимального выигрыша на последнем шаге - (максимум целевой функции последнего шага по всем допустимым управлениям {X_n}).

и для условного оптимального выигрыша на k–ом шаге , .

6. Решают последовательно уравнения Беллмана (условная оптимизация) и получают последовательности функций: { } и { }.

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

И по цепочке

S₀ => X₁* –> S₁* => X₁* –> S₂* => … => X_n-1* –> S_n-1* => X_n* –> S_n*

находят оптимальное управление Х* = (Х₁*, Х₂*, …, X_n*)

(этот этап – безусловная оптимизация).

Т.о. в процессе оптимизации методом ДП многошаговый процесс «проходится» дважды:

- 1-й раз от конца к началу. В результате получают условные оптимальные управления на каждом шаге и условные оптимальные значения целевой функции. (условная оптимизация).

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

Тема 4. Теория массового обслуживания в.1. Основные понятия теории массового обслуживания

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

Примеры: покупатели возле касс магазина; очередь на остановке автобуса; автомобили у бензоколонки и т.д.

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

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

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

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

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

Примеры одноканальных СМО: парикмахерская с одним мастером; газетный киоск с одним продавцом.

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

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

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

СМО в зависимости от числа каналов, а также от характера потока заявок обладает какой-то пропускной способностью.

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

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

Задача теории массового обслуживания: установление зависимостей эффективности функционирования СМО от ее организации.

В качестве характеристик эффективности обслуживания могут быть рассмотрены:

- среднее количество заявок, которое может обслужить СМО в единицу времени;

- средний процент заявок, получивших отказ и необслуженных;

- вероятность, что поступившая заявка будет принята к обслуживанию немедленно;

- среднее время ожидания в очереди;

- среднее количество заявок в очереди;

- закон распределения времени ожидания;

- закон распределения числа заявок в очереди;

- средний доход, приносимый СМО в единицу времени.

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