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

Sw

S0

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

Для графика, отрезок (H0, Hw) работает на n2=6 этапов, отрезок (V0, Vw) - на n1=8 этапов, значит общее число шагов будет:

n=n1+n2=14

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

W= 12+11+10+8+11+10+10+13+15+20+9+12+14 = 163

Нам нужно среди всех траекторий выбрать ту, где расход горючего минимальный.

Можно перебрать все возможные траектории, но их слишком много.

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

1-й этап - Условная оптимизация. Процесс от конца к началу.

Процесс состоит из 14 шагов. Начинаем с последнего.

1) В точку Sw можно переместиться из двух точек - B1 и B2 ;

из каждой точки только один путь и затраты горючего, соответственно

17 и 14 , запишем их в кружочки на месте точек ( рисунок ниже )

2) Предпоследний шаг.

точки B1 и B2 можно попасть из трех точек С1, С2, С3 .

Из каждой из этих точек мы должны найти оптимальный путь в Sw :

Из С1 выбора нет : С1 B1 Sw ; (WC1) =15+17=32

Для С2 есть выбор: С2 B1 Sw ; (WC2)’ =13+17=30

С2 B2 Sw ; (WC1)’’=17+14=31

Sw

C3

B2

B1

С1

 

S0

C2

Выбираем путь С1 B1 Sw ;

Для С3 выбора нет С3 B2 Sw ; WC3=12+14=26 и так далее...

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

Этап условной оптимизации закончен.

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

2-й этап - Безусловная оптимизация. От начала к концу.

Из точки S0 по стрелкам, которые показывают оптимальное управление, попадаем из точки S0 в Sw, как это показано.

1. Общая постановка задачи динамического программирования.

В общем случае, координаты точек S0 и Sw бывают не заданы, а указаны лишь области, которым они принадлежат , , где -

области, созданные системами ограничений.

Сами координаты точек принято называть фазовыми координатами ( мы их будем обозначать x1, x2, ... - [ кси ] ).

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

Из множества возможных управлений найти оптимальное, то есть выбрать среди , которые переводят систему из состояния S0 в состояие Sw такое, которому соответствует максимум выигрыша W.

Предположим, что мы предполагаем решить задачу за m - шагов. Тогда на

m - шаге

где Sm - состояние системы на шаге m ( характеризуемое координатами

x i ).

- “выигрыш” на m - шаге

( расход горючего, прибыль предприятия в m - месяц ),

на произвольном i - м шаге:

(*)

где - сумма “выигрышей” с i по m шаги, S без индекса, так как на

i - м шаге обычно несколько вариантов.

- управление на i - м шаге,

-“выигрыш” на i - м шаге

- сумма “выигрышей” на i+1 - м шага, по m-й .

Для того, чтобы формулой (*) можно было пользоваться для оптимизации по Ui неодходимо задать связь между предыдущим S и последующим состояниями системы S’, ее обычно описывают функцией:

S’=ji (S, Ui) , (**)

с учетом (**),(*) можно записать :

(***)

Wi(S) - условный оптимальный выигрыш на всех шагах, начиная с i - го. Условный - из условия, что на i - м шаге система находилась в состоянии S.

Аналогично Ui=Ui(S) - условное оптимальное управление.

Формула (***) - основное функциональное уравнение динамического программирования.

Пользуясь этой формулой, проводят условную оптимизацию - первый этап ДП., то есть последовательно находят Ui(S) и Wi(S) начиная с m до 1.

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

На первом шаге, если известно S0, находим оптимальное управление:

(U1)* =U1(S0) ,

состояние системы в конце шага :

(S1)* =j1( S0, (U1)* )

и так далее

Если S0 неизвестно, то ищется максимум :

Далее, описанные выше процесс - повторяется.

ЛЕКЦИЯ 12

Решая полученную систему уравнений совместно с p1+p2+......+pn-1+pn=1,

получим :

pk=p1*((lk-1,k*lk-2,k-1*....*l1,2) / (lk, k-1*lk-1,k-2*.....*l2,1)),

2

Пример:

3

3

1

2

2

Циклический процесс

Марковский процесс называется циклическим если все состояния замкнуты в кольцо с односторонними переходами :

l1,2

S2

S4

S1

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

p1: l12*p1= ln1pn

p2: l23*p2= l12p1

p3: l34*p3= l23p2

. . .

pn: ln1*pn= l12p1

и нормировочное уравнение :

p1 + . . . + pn = 1

l1,2

Пример:

S3

S1

S2

S4

24

48

4

2

Теория массового обслуживания (С. М.О.)

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

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

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

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

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

- % заявок, уходящих не обслуженными;

- среднее время ожидания и т. д.

КЛАССИФИКАЦИЯ СМО

По поведению заявок - системы с ожиданием ( очередно), системы с отказами. Системы с ожиданием делятся на упорядоченные (заявки обслуживаются в порядке поступления) и неупорядоченные (заявки обслуживаются в случайном порядке).

Основные характеристики СМО

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

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

Одноканальная СМО с отказами.

Пусть система состоит из 1 канала (n=1) и на нее поступает поток заявок с интенсивностью l. Если канал занят, заявка покидает систему. Обслуживание каждой заявки продолжается случайное время Тоб, распределенное по экспоненциальному закону:

f(Tоб) = me-m t , (*)

где m - интенсивность потока обслуживаний.

Требуется найти

1) абсолютную пропускную способность СМО

2) относительную пропускную способность СМО

Единственный канал СМО может быть рассмотрен как система S с двумя состояниями - S0 - свободен, S1-занят,

Из состояния S0 в S1 переводит поток заявок l , обратно-поток обслуживаний с интенсивностью m.

Обозначив p0(t) и p1(t) вероятности состояний S0 и S1ъ

( Естественно что p0(t) + p1(t)=1 ), (**)

составим уравнение Колмогорова:

т. к. p1 = (1-p0), то

 

начальные условия p0(0)=1, p1(0)=0.

Если l=const, то решение уравнения:

p0- ýòî îòíîñèòåëüíàÿ ïðîïóêíàÿ ñïîñîáíîñòü для одноканальной СМО с отказами: В пределе, при предельное значение относительной пропускной способности будет р авно: q= m / (l+m) Для того, чтобы найти абсолютную пропускную способность, нужно умножить q на интенсивность:

 

b1

1

t

А= lq = lm / (l+m)

Вероятность отказа : pотк= 1 - q.

Многоканальная СМО с отказами

n-каналов. Состояния системы:

S0 - все каналы свободны

S1 -1 канал занят;

. . .

Sn- заняты все n каналов.

l

l

l

S0

S1

Sk

Sn

nm

km

1m

m

Если приходит 1 дополнительная заявка то из состояния sk система перескакивает из состояния Sk в состояние Sk+1.

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

если работает 1 канал (состояние S1) , то как только кончится обслуживание заявки, система перейдет в состояние S0, следовательно, поток S1-S0 имеет интенсивность m . Если обслуживанием занято 2 канала, то поток удваивается:

то есть S2-S1 имеет интенсивность 2m ;

k - каналов : km .

Пользуясь общими правилами, можно составить уравнения Колмогорова:

. . .

Полученные уравнения получили название уравнений Эрланга, начальные

условия для них : p0(0)=1; p1,....,pn(0) = 0.

Решение уравнений производится численно на компьютерах.

ЛЕКЦИЯ 13

Рассматриваемый процесс является процессом “размножения и гибели”, поэтому для расчета предельных вероятностей состояний можно воспользоваться формулами:

 

 

Как видно, в этих формулах l и m используются не по отдельности, а как отношение l / m = r , которое получило название “приведенной интенсивности” потока заявок.

r – среднее число заявок, приходящих в СМО за время, необходимое для обслуживания одной заявки.

С учетом нового обозначения, формулы (*) примут вид:

 

Формулы (**) получили название формул Эрланга.

Рассмотрим теперь основные характеристики СМО:

1) Вероятность отказа Ротк будет равна вероятности того, что все n каналов заняты:

2) Относительная пропускная способность (вероятность того, что заявка будет принята к обслуживанию):

3) Абсолютная пропускная способность

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

 

или

 

Вторая формула применяется из следующих предположений:

А – среднее число заявок, обслуживаемых в единицу времени;

1 занятый канал обслуживает за единицу времени m заявок.

Одноканальная СМО с ожиданием

Sm+1

l l l l

S1

S4

S3

S0

…

m m m m

S0 – канал свободен

S1 – канал занят, очереди нет

S2 – канал занят, 1 заявка в очереди

Таким образом, мы имеем разновидность процесса “ гибели и размножения ”. Пользуясь введенными для этого процесса формулами, найдем предельные вероятности состояний:

 

или, вводя обозначение l / m = r

 

Определим критерии СМО:

1)  Ротк определяется как вероятность того, что занят и канал, и все место в очереди:

 

2) Относительная пропускная способность:

q = 1 – Pотк

3) Абсолютная пропускная способность:

А= lq

4) Среднее число заявок в очереди (без вывода):

 

5) Среднее время ожидания:

Определяется из следующих соображений:

В момент прихода заявки с вероятностью Р0 система будет свободна и время ожидания будет равно 0, с вероятностью Р1 – в ней будет 1 заявка и время ожидания будет 1/μ, с вероятностью Р2 – в ней будет 2 заявки и время ожидания будет 2/ m:

 

Подставляя Рk, после преобразования получим:

6) Время пребывания заявки в системе:

где q – среднее время обслуживания, если заявка обслуживается, или 0, если заявка получает отказ.

Оглавление

ЛЕКЦИЯ 1 2

1.Введение. 2

1.1 Формулировка задачи организационного управления 2

2. Задача линейного программирования 3

2.1 Построение математической модели 4

2.2 Графическое решение задачи линейного

программировавния 5

ЛЕКЦИЯ 2 9

2.2 Анализ решения задачи на чувствительность 10

2.3.1 Первая задача анализа на чувствительность 11

2.3.2 Вторая задача анализа на чувствительность 13

2.3.3. Третья задача анализа на чувствительность 14

ЛЕКЦИЯ 3 16

2.4 Примеры применения методов линейного программирования 16

Задачи об ассортименте продукции 16

Пример 1 16

Математическая формулировка 17

Пример 2 Задача о диете 18

Математическая формулировка 19

Пример 3 Задача о расходе и минимизации обрезков 19

Математическая формулировка 20

Пример 4 Оптимизации работы сборочного конвейера 21

Пример 5 Целевое программирование 22

Математическая формулировка 23

ЛЕКЦИЯ 4 23

Продолжение предыдущей лекции … 23

2.5 Задача ЛП-как задача распределения ресурсов 24

2.6 Симплекс – метод решения задачи ЛП 25

2.6.1 Стандартная ( каноническая ) форма записи задачи Л. П. 26

2.6.1 Опорные планы симплекса. 27

2.6.3. Вычислстельная процедура симплекс - метода. 28

ЛЕКЦИЯ 5 29

2.6.4. Искусственное начальное решение. 33

а) М – метод ( метод больших штрафов ) 34

б) Двухэтапный метод 34

ЛЕКЦИЯ 6 36

2.7 Врожденные решения задачи Л. П. 37

2.8 Альтернативные решения задачи Л. П. 38

2.9 Неограниченные решения. 40

2.10 Отсутствие допустимых решений. 41

2.11 Интерпретация симплекс-таблиц. Анализ на

чувствительность. 41

1) Оптимальное решение. 42

2) Статус ресурсов. 42

ЛЕКЦИЯ 7 43

3) Ценность ресурса ( 2 задача на чувствительность ). 43

4) Максимальное изменения данного ресурса (1 задача на

чувствительность ) 43

5) Максимальное изменение коэффициентов целевой

функции. 44

4.5. Транспортная модель –частный случай линейного программирования. 46

ЛЕКЦИЯ 8 48

Несбалансированные (открытые) транспортные задачи. 51

3 СЕТИ 52

3.1 Задачи минимизации сетей 53

ЛЕКЦИЯ 9 54

Пример: 54

3.2 Задачи о кратчайшем пути. 54

.2.1  Алгоритм для сетей без циклов. 54

3.2.2. Алгоритм для сетей с циклами. 55

3) Проверка обратных ходов. 56

5. Нахождение оптимального пути. 57

6. Задача о максимальном потоке. 58

Алгоритм решения задачи: 58

ЛЕКЦИЯ 10 59

ЛЕКЦИЯ 11 63

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

марковские цели. 64

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

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

ЛЕКЦИЯ 11 67

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

1-й этап - Условная оптимизация. Процесс от конца к

началу. 70

2-й этап - Безусловная оптимизация. От начала к концу. 71

1. Общая постановка задачи динамического

программирования. 71

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

ЛЕКЦИЯ 12 73

Циклический процесс 74

Теория массового обслуживания (С. М.О.) 75

КЛАССИФИКАЦИЯ СМО 76

Основные характеристики СМО 76

Одноканальная СМО с отказами. 76

Многоканальная СМО с отказами 78

ЛЕКЦИЯ 13 79

Одноканальная СМО с ожиданием 81