Градиентные методы решения задач

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

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

Градиентные методы могут быть подразделены на две группы.

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

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

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

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

В качестве основной в теории выпуклого программирования обычно рассматривается задача отыскания вектора который удовлетворяет условиям:

и доставляет глобальный минимум функции

функции предполагаются гладкими и выпуклыми.

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

Множество точекудовлетворяющих условиям формулированных задач, является выпуклым.

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

Если функциядифференцируема в точкето градиентом в точке называется n-мерный вектор

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

Вектор

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

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

Градиентный метод основан на простой идее. Если заранее известно, чтоимеет в допустимой области единственный экстремум, то поиск точки, в которой он достигается, целесообразно проводить так. В допустимой области взять произвольную точкуи с помощью градиента (антиградиента) определить направление, в которомвозрастает (убывает) с наибольшей скоростью (рис. 2).

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

Величина " шага" из точки по направлению градиента (антиградиента) определяется значением параметра в уравнении прямой

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

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

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

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

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

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

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

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

Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».

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

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

В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.

Рис.2. Изображение потока событий на оси времени

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

Интенсивность потока событий () – это среднее число событий, приходящееся на единицу времени.

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.

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

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

где - параметр показательного закона.

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

Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний

Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.

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

Для наглядности на графе состояний системы у каждой дуги проставляют интенсивности того потока событий, который переводит систему по данной дуге (стрелке). - интенсивность потока событий, переводящий систему из состояния в . Такой граф называется размеченным. Для нашего примера размеченный граф приведен на рис.3.

Рис.3. Размеченный граф состояний системы

На этом рисунке - интенсивности потока отказов; - интенсивности потока восстановлений.

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

Пусть система находится в состоянии S ₀. В состояние S ₁ ее переводит поток отказов первого станка. Его интенсивность равна

где - среднее время безотказной работы первого станка.

Из состояния S ₁ в S ₀ систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна

где - среднее время ремонта первого станка.

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

Пусть рассматриваемая система S имеет - возможных состояний . Вероятность - го состояния - это вероятность того, что в момент времени система будет находиться в состоянии . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:

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

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

где - конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что

Финальная вероятность состояния – это по – существу среднее относительное время пребывания системы в этом состоянии.

Например, система S имеет три состояния S ₁, S ₂ и S ₃. Их финальные вероятности равны соответственно 0, 2; 0, 3 и 0, 5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S ₁, 3/10 – в состоянии S ₂ и 5/10 – в состоянии S ₃.

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

Пользуясь этим правилом, напишем систему уравнений для нашего примера:

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

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

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

.

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:

.

Т.е. в предельном, стационарном режиме система S в среднем 40 % времени будет проводить в состоянии S ₀ (оба станка исправны), 20 % - в состоянии S ₁ (первый станок ремонтируется, второй работает), 27 % - в состоянии S ₂ (второй станок ремонтируется, первый работает), 13% - в состоянии S ₃ (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Пусть система S в состоянии S ₀ (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S ₁ – доход 3 условные единицы, в состоянии S ₂ – доход 5 условных единиц, в состоянии S ₃ – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен условных единиц.

Станок 1 ремонтируется долю времени, равную . Станок 2 ремонтируется долю времени, равную . Возникает задача оптимизации. Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.

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

Первое деление (по наличию очередей):

1. СМО с отказами;

2. СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

· СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.

Задачи теории массового обслуживания

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

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

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

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

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

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

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

Дано: система имеет один канал обслуживания, на который поступает простейший поток заявок с интенсивностью . Поток обслуживаний имеет интенсивность . Заявка, заставшая систему занятой, сразу же покидает ее.

Найти: абсолютную и относительную пропускную способность СМО и вероятность того, что заявка, пришедшая в момент времени t, получит отказ.

Система при любом t > 0 может находиться в двух состояниях: S ₀ – канал свободен; S ₁ – канал занят. Переход из S ₀ в S ₁ связан с появлением заявки и немедленным началом ее обслуживания. Переход из S ₁ в S ₀ осуществляется, как только очередное обслуживание завершится (рис.4).

Рис.4. Граф состояний одноканальной СМО с отказами

Выходные характеристики (характеристики эффективности) этой и других СМО будут даваться без выводов и доказательств.

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

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

– интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания )

Относительная пропускная способность (средняя доля заявок, обслуживаемых системой):

Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):

Очевидны следующие соотношения: и .

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

Решение.

Т.е. в среднем примерно 46 % деталей обрабатываются на этом станке.

.

Т.е. в среднем примерно 54 % деталей направляются на обработку на другие станки.

N – канальная СМО с отказами (задача Эрланга)

Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.

Дано: в системе имеется n – каналов, на которые поступает поток заявок с интенсивностью . Поток обслуживаний имеет интенсивность . Заявка, заставшая систему занятой, сразу же покидает ее.

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

Решение. Состояние системы S (СМО) нумеруется по максимальному числу заявок, находящихся в системе (оно совпадает с числом занятых каналов):

· S ₀ – в СМО нет ни одной заявки;

· S ₁ – в СМО находится одна заявка (один канал занят, остальные свободны);

· S ₂ – в СМО находится две заявки (два канала заняты, остальные свободны);

·...

· S _n – в СМО находится n – заявок (все n – каналов заняты).

Граф состояний СМО представлен на рис. 5

Рис.5 Граф состояний для n – канальной СМО с отказами

Почему граф состояний размечен именно так? Из состояния S ₀ в состояние S ₁ систему переводит поток заявок с интенсивностью (как только приходит заявка, система переходит из S ₀ в S ₁). Если система находилась в состоянии S ₁ и пришла еще одна заявка, то она переходит в состояние S ₂ и т.д.

Почему такие интенсивности у нижних стрелок (дуг графа)? Пусть система находится в состоянии S ₁ (работает один канал). Он производит обслуживаний в единицу времени. Поэтому дуга перехода из состояния S ₁ в состояние S ₀ нагружена интенсивностью . Пусть теперь система находится в состоянии S ₂ (работают два канала). Чтобы ей перейти в S ₁, нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равна и т.д.

Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.

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

где n – количество каналов СМО;

– вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S ₀);

Рис.6. Граф состояний для схемы «гибели и размножения»

Для того, чтобы написать формулу для определения , рассмотрим рис.6

Граф, представленный на этом рисунке, называют еще графом состояний для схемы «гибели и размножения». Напишем сначала для общую формулу (без доказательства):

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

Вероятность того, что СМО находится в состоянии S ₁, когда один канал занят:

Вероятность того, что СМО находится в состоянии S ₂, т.е. когда два канала заняты:

Вероятность того, что СМО находится в состоянии S _n, т.е. когда все каналы заняты.

Теперь для n – канальной СМО с отказами

При этом

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

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

;

.

Вероятность отказа:

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

Среднее число занятых каналов (среднее число заявок, обслуживаемых одновременно):

При этом

.