Геометрическая интерпретация(целочисленная решётка).

X

3 3

0 1 2 3 2 4 X₁

Алгоритм решения базируется на отсечении дробных частей (причём не механически, а алгоритмически).

Наиболее эффективным алгоритмом решения целочисленных задач является алгоритм Гомори.

(а считается конгруэнтным , если - целое число) .

Алгоритм Гомори предусматривает 2 этапа:

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

Затем задача решается вновь с учётом нового ограничения обычными методами и т. д. На каждом последующем шаге решения, размер задачи и объём вычисления увеличивается (иногда до 100, иногда и до 1000 новых ограничений)и, шагов решения. Не смотря на это, данный алгоритм самый эффективный.

Пример: На предприятии необходимо установить новое оборудование. На его приобретение выделено 20 т. у. е. Имеющаяся S для установки – 38 м². есть возможность приобрести оборудование 2-х видов – а и в. Стоимость а – 5000 у. е. , в – 2000 у. е. S_а – 8 м², S_в – 4 м². Производительность а – 7000 ед. за смену, в – 3000ед. за смену. !обеспечить max общую производительность.

х₁ – количество ед – ц оборудования а.

х₂ – количество ед – ц оборудования в.

Z = 7x₁ + 3x₂ max

Ограничения:

1) 5х₁ + 2х₂ 20 (у. е.)

2) 8х₁ + 4х₂

3) х₁х₂ – целые числа.

I.Решим задачу без учёта последнего ограничения симплекс – методом:

1) 5х₁ + 2х₂ + х₃ = 20

2) 8х₁ + 4х₂ + х₄ = 38

Z = 7*1 + 3*7,5 = 29,5

= 7*1 + 3*7 = 28

II.Для переменной, которая получилась не целочисленной, составим уравнение из последней симплекс – таблицы:

7,5 = 0х₁ + 1х₂ – 2х₃ + 1,25х₄ = 20

х₂ = 7,5 + 2х₃ – 1,25х₄ 0

-2 х₃ + 1,25х₄ 7,5

т. к. х₃ также должна быть целочисленной, то 2х₃ можно опустить.

1,25х₄ 7,5

0,25х₄ = 0,5; 1,5; 2,5…ограничения

Ограничения:

1) 5х₁ + 2х₂ + х₃ = 20

2) 8х₁ + 4х₂ + х₄ = 38

3) 0,5х₄ – х₅ = 0,5

х₁ = 2

х₂ = 5

х₄ = 2

Z = 7*2 + 3*5 = 29

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

Алгоритм решения: m=5; n=5; K₁=4; K₂=7; K₃=2; K₄=3; K₅=10; Q₁=600т.; Q₂=2890т.; Q₃=1100; Q₄=2500; Q₅ =300.

Задана Р_ij(верхний левый угол матрицы).

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

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

3. После определения разностей, выбираем наибольшую величину разностей, при этом не имеет значения, где они находятся. Против выбранной разности ставим перегрузочные машины на тот причал, на котором достигается max производительность (в эту клетку ставится max количество кранов).

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

5. Далее снова определяется разность двух лучших показателей в оставшихся строках и столбцах матрицы.

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

Числовое решение в матрице.

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

1. 3,30*180=600 2. 3,5+0,5=4

23,5*380+3*520=2890 3,35+1,55+2,1=7

3,25*340=1100 1<2

1,55*260+6,75*310=2500 3=3

0,5*80+2,1*90+1*70=300 3,25+6,75=10

Метод аппроксимации часто применяется для составления исходного плана задачи в матрицах большого размера. Для получения строго оптимального плана расстановки необходимо решение закончить точным методом линейного программирования. Сравнительный показатель трудоемкости данного и точного метода = 50.

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

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

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

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

Постановка задачи:

m – количество типов грузовых судов i=1,…, m

n – количество грузовых линий движения j=1,…,n

Ф_i – количество судов каждого типа

Q_j – грузооборот на каждой линии (мил. т/км)

P_ij – провозная способность судна i-го типа на j-той линии

(мил. т/км)

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

Ограничения:

1.

2.

3.

Алгоритм решения рассматриваем на примере:

m=3; n=5; Ф₁=6; Ф₂=8; Ф₃=12 ……………………….

Задача Р_ij (в матрице)=

1). Исходные данные размещаем, в матрице при этом типы судов размещается, в порядке ухудшения показателей

2) Определяем значение индексов.

Где P_io- провозная способность судна i-го типа на базисной линии.

За базисную линию для судов каждого типа принимается та линия на которой достигаются лучшие показатели (max P_ij) каждый тип судна может иметь свою базисную линию.

Если задача решается по показателю эксплуатационных расходов или себестоимости, то индексы определяются так:

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

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

На базисной линии закрепилось max возможное количество судов. Если ….. грузооборот на данной линии, то вычеркивается столбец; если распределены все суда данного типа, то вычеркивается строка.

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

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

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

В примере объем перевозок на всех линиях выполнен при остатке 1,5 судов третьего типа в резерве.

Ф=8+6*10,5=24,5 Проверка ограничений: 3*35=105

4+2=6 2*40+6*25=230

2+6=8 6*45=270

3+6+1,5<12 4*60=240

2*36+1,45*20=100

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

Модифицированная распределительная задача.

Экономическая постановка и математическая модель. Условия оптимального плана.

Эту же задачу называют обобщенная транспортная задача.

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

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

Алгоритм решения обобщенной транспортной задачи рассмотрим на примере распределения судов по линиям.

m- (типов судов) i=1, …,m

n – (линий движения) j=1, …, n

Ф_i - количество судов каждого типа

П_ij – пассажирооборот на каждой линии за навигацию

(мил. пас/км)

Ф_ij – количество судов i- го типа закрепленного за j- той линией

Z_ij – провозная способность судна i- го типа на j- той линии за навигацию (мил. пас/км)

Э_ij – эксплуатационные расходы по судну i- го типа на j- той линии за навигацию (тыс. руб.)

Необходимо составить такой план расстановки судов по линиям, при которой Э_ij min.

Целевая функция:

Ограничение: Ф_ij 0

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

1) для Ф_ij>0 (для заполненных клеток)

2) для Ф_ij=0

- потенциалы (оценочные числа)

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

Пример: m=2, n=3, П₁=9, П₂=3, П₃=6 (мил. пас/км)

Z₁₂=Z₂₂=1 (мил. пас/км) Э₁₁=22, Э₁₂=14, Э₁₃=26

Z₁₂=Z₂₁=1,5 Э₂₁=16, Э₂₂=12, Э₂₃=20

Z₁₃=Z₂₃=2 Ф₁=5, Ф₂=7

Составляем первоначальный план расстановки в соответствии с условиями допустимости, при этом количество заполненных клеток должно быть = m+n-1 (2+3-1)=4

Проверка условия оптимальности: 0+18*1 14 – не выполняется

0+13*2=26 – выполняется

Проверка оптимальности второго типа: план оптимальный

Проверка ограничений и расчет условий функции:

Э=2*22+3*14+4*16+3*20=210 тыс.руб.

III часть. Системы массового обслуживания (СМО)

Потоки событий

Понятие потока событий. Простейший поток.

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

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

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

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

При изучении экономических систем в качестве параметра t обычно выступает время, а под X понимаются координаты состояния системы, т.е. экономические показатели.

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

(временная ось)

через - моменты операции

f.e. - момент прибытия судна

- начало обработки

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

Потоки событий делятся на несколько классов.

1). если число событий, происходивших в фиксированный интервал времени Т зависит от величины этого интервала и не зависит от начала его отчета, то такой поток называется стационарным.

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

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

Стационарный ординарный поток событий безпоследействия называется простейшим потоком или потоком Пуассона.

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

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

1). Метод агрегирования (т.е. состоит в укрупнении событий)

2). Метод дифференцирования (т.е. расчленение событий на несколько)

У простейшего потока математическое ожидание числа событий за какой-то интервал времени t распределено по закону Пуассона.

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

Практически рассчитывается как среднее число событий в единицу времени.

- интервал времени между двумя смежными событиями (случайная величина).

В простейшем потоке величина Т распределена по ……….. (показательному) закону.

- плотность вероятности распределения

Математическое ожидание:

Дисперсия:

Среднеквадратическое отклонение: , т.е.

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

Понятие Марковских процессов. Их классификация.

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

Если -ет последовательность t₁<t₂<,….<t_n отсчетов времени и при этом соблюдается следующие условия:

Т.е. условная вероятность того, что на n- ном шаге отчета времени будет зафиксированы координаты x_n при условии, что на первом шаге будут зафиксированы координаты x₁ на втором x₂, на n-1^м-x-1 и эта условная вероятность будет = условной вероятности того, что на n-ном шаге будут зафиксированы координаты x_n, если на n-1-вом шаге зафиксированы координаты x_n-1.

Различают два вида Марковских процессов:

1). Марковский процесс с дискретным временем.

с непрерывным временем

Моделирование Марковского процесса с дискретным временем.

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

Введем обjзначения:

S – состояние системы

различные координаты системы (под i-м понимается начальное состояние системы, под j-м последующее)

Для состояния S_i - ет набор координат (показателей)характерных положений в данный момент

P_ij – вероятность того, что система из i-го состояния перейдет в j-тое.

Марковский процесс можно задать двумя способами:

1). с помощью матрицы вероятностей перехода

2). с помощью размеченного графа состояний

Переход из 1 во 2 и т.д.

(полная группа событий)

Каждый элемент данной матрицы отражает вероятность перехода из i-го состояния в j-тое.

Можно записать:

Когда система может находиться в наибольшем числе состояний, т.е. n …….. мало, то наиболее удобно описать Марковский процесс с помощью второго метода (размеченного графа состояний)

S5

S3

S2

S4

S1

P₁₂

P₁₃

P₁₁ P₁₄ P₂₅ P₅₂

P₃₅

P₅₃

P₄₅

Задание Марковского процесса с помощью размеченного графа состояний удобно по двум причинам:

1) не надо отражать - цие связи, т.е. когда P_ij= Ø

2) нет необходимости указывать переход системы в это же состояние (из i-го в j-тое т.е. P_ij)

и т.д.

Это более экономичный способ

Введем еще обозначения:

P_i(K) – это вероятность того, что система на котором шаге будет находится в i-том состоянии

в начальный момент времени система находится в первом состоянии.

/>Вероятность того, что система на первом шаге и останется в первом состоянии Р₁(1) = вероятности перехода из первого состояния в первое (Р₁₁) Р₁(1)=Р₁₁.

Вероятность того, что система на первом шаге перейдет во второе Р₂(1)=Р₁₂, на первом шаге перейдет из первого в n-ное состояние =Р_1n Р₂(1)=Р₁₂

Р_n(1)=P_1n

На втором шаге система перейдет в одно из возможных n-ных состояний, но все зависит от того, в каком состоянии система находится на предыдущем, т.е. на первом шаге.

Выдвинем следующие гипотезы:

- вероятность того, что на втором шаге система будут находиться в первом состоянии

- вероятность того, что на втором шаге система будет находиться в первом состоянии

По аналогии

Моделирование Марковского процесса с непрерывным временем

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

Необходимо знать вероятности нахождения системы в i-том состоянии в момент времени:

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

Рассмотрим поток случайных событий:

t

Для марковских процессов с непрерывным временем характеристикой процесса может быть только мгновенная характеристика – плотность вероятности перехода.

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

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

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

- вероятность того, что за промежуток произойдет переход из i-го состояния в j-тое =

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

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

Марковские процессы будут однородными и неоднородными

Неоднородные процессы- это если плотности вероятности переходов зависят от времени.

Однородные- плотности вероятности переходов не зависит от времени.

Для неоднородных Марковских процессов математический аппарат до сих пор не разработан.

Уравнение Колмогорова-Чепмена

Однородный и непрерывный во времени Марковский процесс описывается системой дифференцирования уравнений Колмогорова – Чепмена.

Вывод этих уравнений построим применительно к системе, представленной на рис.

S1

S4

S3

S2

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

Вероятность того, что система за время перейдет в первое состояние.

Гипотезы:

1).В момент времени t находиться в первом состоянии

И за не пере….. никуда, т.е. ….. в S₂

Левая часть уравнения – это приращение функции к приращению аргумента изменения по t производная по t.

Выведенное последние дифференцированное уравнение характеризует вероятность нахождения системы в момент времени в состоянии 1.

(1)

Дифференцированное уравнение (*) характеризует вероятность нахождения системы в момент времени в состоянии 1. Аналогично для второго состояния.

Произведем преобразование:

(2)

Мнемонические правила (по ассоциации) построения уравнений Колмогорова-Чепмена:

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

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

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

4. Если связь исходит из данного состояния, то перед этим членом уравнения стоит знак «-», а если связь входит в данное состояние, то соответственно стоит знак «+».

(3)

(4)

Эти 4 уравнения (1), (2), (3), (4) позволяющие определить вероятность нахождения системы в из возможных состояний в момент времени называется системой Колмогорова-Чепмена (К-Ч)

Понятие установившегося режима работы.

Под установившимся режимом понимается такое функционирование системы, которое не зависит от времени, т.е. мы оперируем средними вероятностями. Эти средние вероятности называются предельными вероятностями.

Для того чтобы из системы уравнений К-Ч получить предельными вероятности, мы правая часть уравнений приравниваем к Ø и избавляемся от моментов времени (t).

Тогда система дифференцированных уравнений преобразуется в систему линейных уравнений:

Не всякая реальная система имеет установившийся режим функционирования. Правила или признаки, при которых система имеет установившийся режим:

- число взаимосвязанных состояний системы должно быть конечным

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

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

Система может находится в одном из следующих состояний:

S₁ - оба крана в рабочем состоянии и осуществляют выгрузку

S₂ - оба крана в рабочем состоянии, но выгрузку не осуществляют

S₃ – 1 кран осуществляет выгрузку, 1 ремонтируется

S₄ – оба крана ремонтируются

Графическое состояние данной системы

S1

4 4

S3

S4

S2

6

2 1

на основе анализа фактических данных установлено, что поток груженных углем судов в порт равен = 4 суд/сут.

Средняя продолжительность выгрузки судна двумя кранами составляет 4 часа или1/6 суток, а одним краном 8 часов или 1/3 суток. Тогда интенсивность потоков событий, заключается в отходе порожних судов от причала составляет = 6 суд/сут. Если 1 кран сломался, то = 3 суд/сут.

Необходимость профилактического осмотра механизмов кранов и различных непредвиденных его ремонтов возникает в среднем 4 раза в сутки = 4 раза/сут.

Интенсивность потока отказов одновременно два кранов составляет = 1 ремонт/сут.

Средняя продолжительность ремонта или осмотра каждого крана 1 час или 1/24 суток =24.

Поток восстановлений одновременно обоих ремонтных кранов = 2 восстановления/суток.

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

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

Выразим все переменные через одну Р₃=26Р₄

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

46 % времени (Р₁+Р₃) у причала будет происходить выгрузка судов, причем большую часть времени выгрузка будет осуществляться 1 краном ( ) .

В течении 1 % времени причал не сможет принимать суда из-за неисправности обоих кранов.

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

Формула Эрланга

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

t₁ t₂ t₃ t₄ t

Вероятность появляется определенного числа событий, в потоке Эрланга подчинена Пуассоновскому закону. Т.к. в исходном потоке величина интервалов между событиями распределена по экспон. Закону, то и в Эрлангском потоке также распределена экспон-но.

Если - плотность вероятности в исходном потоке.

- плотность вероятности в Эрлангском потоке, которого порядко… соотношение между ними следующее:

К- порядок потока Эрланга.

Понятие систем массового обслуживания (СМО). Их классификация.

Заявка- это требование на выполнение определенной однородной операции или это объект, требующий обслуживания.

Поток заявок приводит к тому, что с системой происходит поток событий.

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

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

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

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

f.e. порт - СМО, судно - заявка, причал - канал.

Классификация СМО:

1). по числу каналов:

· одноканальные

· многоканальные

2). по характеру обслуживания:

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

· СМО с ожиданием

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

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