Алгебраический симплексный метод. Основные положения данного метода.

Алгебраический симплексный метод. Основные положения данного метода.

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

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

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

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

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

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

10. Алгоритм решение задачи симплексным методом(первый опорный план)

Рассмотрим алгоритм симплексного метода на примере задачи линейного программирования. Система ограничений, которой содержит неравенство вида <=

I. Приведем задачу к канонической форме. Введем m дополнительных неотрицательных переменных

2. найдем начальное опорное решение. Выпишем матрицу из коэффициентов полученной системы ограничений

Коэффициенты при дополнительных переменных образуют единичную диагональную матрицу- базис, поэтому x _n₊₁, x _n₊₂…..x _n₊_m называют базисными переменными.

Выразим базисные переменные через основные:

Прировняем к 0 основные переменные: x₁=x₂=….=x _n=0

В результате получаем начальное опорное решение

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

3.Проверка плана на оптимальность. При решении задачи на max опорный план считается оптимальным; если все коэффициенты индексной строки неотрицательны.

Если хотя бы один элемент отрицателен, то план считается неоптимальным (т.е. – оптимальный; + неоптимальный)

При решении задачи на min, план считается оптимальным если все коэффициенты индексной строки не положительны.

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

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

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

Проверка плана на оптимальность. При решении задачи на max опорный план считается оптимальным; если все коэффициенты индексной строки неотрицательны.

Если хотя бы один элемент отрицателен, то план считается неоптимальным (т.е. – оптимальный; + неоптимальный)

При решении задачи на min, план считается оптимальным если все коэффициенты индексной строки не положительны.

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

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

Определение ведущей строки. Элементы столбца ЗБП делим на соответствующие элементы ведущего столбца, а результаты заносим в последний столбец таблицы.

Замечание. Делить можно числа только одного знака (+/+;-/-) т.е. в последнем столбце таблицы должны получаться только положительные значения. Если встретились числа разных знаков или деление на 0, то в столбце на соответствующем месте ставится прочерк.

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

Определение разрешающего элемента. Разрешающий элемент находится на пересечении ведущей строки и ведущего столбца.

Заполнение нового опорного плана. В первую очередь заполняется столбец БП (базисные переменные). Базисная переменная, которая в старом плане

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

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

В результате деления на месте старого разрешающего элемента окажется единица. Остальные элементы старого ведущего столбца в новом плане обнуляем. Все остальные элементы нового плана рассчитываются по формуле:

Элемент нового плана = элемент старого плана-(произведение дополняющих элементов до прямоугольника)/разрешающий элемент

Получив новый план проверяем его на оптимальность. Алгоритм повторяется до тех пор пока не получим оптимальное решение.

13. Анализ оптимального плана симплексного метода на примере задачи планирования товарооборота.

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

Значение целевой функции также берется из столбца ЗБП последнего оптимального плана. Оптимальный вектор переменных обозначаем X^*, а оптимальное значение целевой функции F _max(X^*)
При решении задачи планирования товарооборота(задача о распределе6нии ресурсов), основные переменные указывают на количество реализуемой продукции каждого вида, для получения max дохода. А дополнительные переменные указывают на количество недоиспользованных ресурсов каждого вида. Если какая нибудь дополнительная переменная равна 0, то соответствующий ей ресурс использован полностью и является дефицитным. Положительное значение дополнительной переменной говорит о имеющихся излишках ресурсов.

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

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

Альтернативный оптимум можно найти, если принять за ведущий столбец, столбец с небазисным 0. При этом среди элементов данного столбца должен быть один положительный.

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

Если в ходе решения в ведущем столбце все коэффициенты a_ij оказались <=0, то целевая функция F(X)- неограниченна на множестве допустимых решений. А значит, оптимального решения задача не имеет.

Если в ходе последнем столбце симплексной таблицы оказалось сразу несколько одинаковых наименьших элементов, то опорный план считается вырожденным, а дальнейшие решения может привести к зацикливанию. Для определения ведущей строки в данном случае применяется метод Креко: рассматривают все строки претендующие на ведущую, в каждой из них находят предполагаемый разрешающий элемент. Элементы каждой строки делят на свой разрешающий элемент, а результаты записывают в дополнительные строки симплексной таблицы.

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

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

Система может находиться в одном из трех состояний: S₀ – канал свободен, простаивает, S_i – канал занят обслуживанием, S₂ — канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S_Q В S_I происходит под воздействием простейшего потока заявок интенсивностью l₀₁, а из состояния S_i в состояние 5* 0 систему переводит поток обслуживания с интенсивностью l₁₀. Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность p_i (t) того, что система будет находиться в состоянии S_i в момент времени t, называется вероятностью i -го состояния СМО и определяется числом поступивших заявок k на обслуживание.

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

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

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

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S₀, S₁, S₂ (см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S_i в состояние S_j происходят под воздействием простейших потоков событий с интенсивностями l _ij, а обратный переход — под воздействием другого потока l _ij, Введем обозначение р_i как вероятность того, что в момент времени t система находится в состоянии S_i. Для любого момента времени t справедливо записать нормировочное условие — сумма вероятностей всех состояний равна 1:

Проведем анализ системы в момент времени t, задав малое приращение времени Dt, и найдем вероятность p₁(t + Dt) того, что система в момент времени (t + Dt) будет находиться в состоянии S₁, которое достигается разными вариантами:

а) система в момент t с вероятностью p_i(t) находилась в состоянии S_i и за малое приращение времени Dt так и не перешла в другое соседнее состояние — ни в S₀, ни в S₂. Вывести систему из состояния S₁ можно суммарным простейшим потоком с интенсивностью (l₁₀ + l₁₂), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S₁ за малый промежуток времени Dt приближенно равна (l₁₀ + l₁₂)×Dt. Тогда вероятность невыхода из этого состояния равна [1 — (l₁₀ + l₁₂) × Dt]. В соответствии с этим вероятность того, что система останется в состоянии S₁ на основании теоремы умножения вероятностей, равна:

б) система находилась в соседнем состоянии S₀ И за малое время Dt перешла в состояние S₁. Переход системы происходит под воздействием потока l₀₁ c вероятностью, приближенно равной l₀₁ Dt.

Вероятность того, что система будет находиться в состоянии S₁, в этом варианте равна p₀(t) l₀₁Dt;

в) система находилась в состоянии S₂ и за время Dt перешла в состояние S₁ под воздействием потока интенсивностью l₂₁ с вероятностью, приближенно равной l₂₁Dt. Вероятность того, что система будет находиться в состоянии S₁, равна p₂(t)l₂₁Dt.

Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

p₁(t + Dt) = p₁(t) [ 1 – (l₁₀ + l₁₂) Dt ] + p₀(t) l₀₁Dt + p₂(t)l₂₁Dt,

p₁(t + Dt) – p₁(t) ₌ p₀(t)l₀₁ + p₂(t)l₂₁ – p₁(t)(l₁₀ + l₁₂).

Переходя к пределу при А/ -^ О, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

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

Для составления уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО S _i в функции времени p_i(t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы в этом состоянии. Если предельная вероятность состояния S₀ равна p₀ = 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S0. Например, при отсутствии заявок на обслуживание k = 0, p0 = 0,2, следовательно, в среднем 2 ч в день система находится в состоянии S₀ и простаивает, если продолжительность рабочего дня составляет 10 ч.

Поскольку предельные вероятности системы постоянны, то, заменив в уравнениях Колмогорова соответствующие производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим СМО. Такую систему уравнений составляют по размеченному графу состояний СМО по следующим правилам: слева от знака равенства в уравнении стоит предельная вероятность р_i рассматриваемого состояния S₁ умноженная на суммарную интенсивность всех потоков, выводящих (выходящие стрелки) из данного состояния S_i систему, а справа от знака равенства — сумма произведений интенсивности всех потоков, входящих (входящие стрелки) в состояние S_i систему, на вероятность тех состояний, из которых эти потоки исходят. Для решения подобной системы необходимо добавить еще одно уравнение, определяющее нормировочное условие, поскольку сумма вероятностей всех состояний СМО равна 1:

Например, для СМО, имеющей размеченный граф из трех состояний S₀, S₁, S₂ рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

Для состояния S₁ ® (l₁₀ + l₁₂) = p₀l₀₁ + p₁l₂₁

Пример 1. Составим систему уравнений Колмогорова в общем виде для случая, когда граф состояний имеет вид (рис. 6.2.2):

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

К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S₁, то начальные условия можно записать так:

Переходы между состояниями СМО происходят под воздействием поступления заявок и их обслуживания. Вероятность перехода в случае, если поток событий простейший, определяется вероятностью появления события в течение времени Dt, т.е. величиной элемента вероятности перехода l_ij D t, где l_ij — интенсивность потока событий, переводящих систему из состояния / в состояние j (по соответствующей стрелке на графе состояний).

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

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

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

Вычислить предельные вероятности состояния p_i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t ®¥ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.

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

тогда из записанной ранее в примере 1 системы уравнений Колмогорова получаем:

И, Кроме того, мы должны учесть нормировочное условие:

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

Вопрос 58. Классификация СМО в коммерческой деятельности (по числу каналов, по характеру расположения, по характеристике каналов).

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

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

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

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

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

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

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