Симплексный метод

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

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

1. Указать способ нахождения оптимального опорного решения

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

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

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

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

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

Системы массового обслуживания

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

Моделирование СМО предполагает:

1. построение экономической математической модели, связывающей параметры СМО (число каналов, их производительность и т.п.) с показателями эффективности;

2. оптимизацию данных показателей с целью получения максимальной эффективности.

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

Заявка – требование на выполнение обслуживания.

Входящий поток заявок - интенсивность входящего потока l.

Исходящий поток - интенсивность исходящего потока (интенсивность потока обслуживания) m.

Канал обслуживания - число каналов n, среднее число занятых `k,.

Очередь - среднее число заявок `z, среднее время пребывания одной заявки `t.

Дисциплина обслуживания – правила, по которым действуют СМО.

Каждому событию соответствует момент t в который это событие произошло. Т – интервал между двумя моментами времени.

Поток событий – независимая последовательность моментов t.

Потоки событий разделяют:

по случайности:

· регулярные – Т-const

· случайные – Т- случайная величина.

по постоянности вероятностных свойств

· стационарные

· нестационарные

по связи будущего поведения с прошлым

· с последействием

· без последействия

по числу заявок в одном событии

· ординарные –событию соответствует одна заявка

· неординарные - событию соответствует случайное число заявок

Простейший (Пуассоновский) поток

t₂>t₁, t₂-t₁=t, P{n=k| t₂>t₁=t}=p(k, t) – вероятность того, что на интервале t произошло k событий.

Простейший поток обладает тремя свойствами:

1) стационарностью - вероятность попадания того или иного числа заявок на интервал времени длиной t зависит от длины этого интервала и не зависит от того, где этот интервал расположен на оси времени;

2) безпоследействия - для любых не перекрывающихся участков времени число заявок, попадающих на один из участков, не зависит от числа заявок, попадающих на другой участок;

3) ординарностью - вероятность попадания на участок t двух или более заявок пренебрежимо мала по сравнению с вероятностью попадания одной заявки.

Классификация систем массового обслуживания

В зависимости от условий ожидания начала обслуживания

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

СМО с ожиданием - требование, застав все обслуживающие ка­налы занятыми, становится в очередь и ожидает, пока освободится один из обслуживающих каналов - вероятность потери заявок Р_отказа = Р_{потерь, -} вероятность занятости k каналов Р_к

В свою очередь СМО с ожиданием:

- с ограниченной длиной очереди - средняя длина очереди

- с ограниченным временем ожидания.

По числу каналов обслуживания:

Одноканальные - один обслуживающий канал, может одновременно обслуживать только одно требование.

Многоканальные - п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование - коэффициент простоя каналов где N₀ – к-во незанятых каналов, n – всего каналов.

По числу фаз обслуживания:

однофазные - один этап обслуживания - среднее число требований, находящихся на обслуживании

многофазные - два и более этапов обслуживания.

По месту нахождения источников заявок:

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

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

По дисциплине обслуживания:

в порядке поступления - обслуживание по мере поступления.

Случайно - обслуживание по случайному закону.

с приоритетом – бывают:

- абсолютный приоритет обслуживания.

- относительный приоритет обслуживания.

Цепью Маркова называется случайный процесс, развитие которого целиком определяется его значением в настоящий момент и не зависит от знания значения процесса в предыдущие моменты времени. Может быть дискретным, если X(t) – дискретно, и непрерывным, если X(t) – непрерывным. Он может быть процессом с дискретным или непрерывным временем. Марковский процесс с дискретными состояниями называется Марковскими цепями. Система в момент t находится в состоянии n(t)=i. Величина n(t+Dt)=j, i¹j. P{n(t+Dt)=j | n(t)=i} - интенсивность перехода системы из состояния i в j.

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

Дата добавления: 2015-11-14