Нелинейное программирование

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

 Такое имеет место в следствии:

1. реализации деления издержек производства на переменные и условно-постоянные;

2. повышенного спроса на товары;

3. влияния внешней экономики;

4. влияния внешних издержек и т.п.

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

 

 

здесь - вектор первоначальных переменных; - целевая функция; - функция ограничений; - вектор постоянных значений ограничений. В данном случае определение знака является произвольным, соответственно, можно использовать и . Следует также отметить, что не уточняется форма ни целевой функции, ни неравенств. Имеют место несколько случаев:

1. целевая функция не является линейной, ограничения — линейны;

2. целевая функция является линейной, как минимум одно ограничение — нелинейно;

3. целевая функция и ограничения являются нелинейными (рис. 2.4).

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

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

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

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

 

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

 

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

 

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

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

- свободный канал;

- канал занят, очереди нет;

- канал занят при наличии одной очередной заявки;

…

- канал занят при заявок в очереди;

…

заявок в очереди.

На рисунке 5.8. продемонстрирован ГСП. Каждый из интенсивностей потоков событий, переводящих по стрелкам слева направо в систему, равны и наоборот — . Получается, что систему по стрелкам слева направо переводит поток заявок, справа налево — поток «освобождений» занятого канала, интенсивность которого составляет.

 

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

 

5.8. — это своего рода схема размножения и гибели. Применяя общее решение (5.32)-(5.34), представим выражения для предельных вероятностей состояний:

 

(5.44)

 

или применяя :

(5.45)

 

В последней строке в (5.45) имеется геометрическая прогрессия с первым членом 1, знаменатель ее равен . Теперь:

(5.46)

соответственно, предельные вероятности имеют такой вид:

(5.47)

 

(5.46) могут быть так представлены только при условии, а при обеспечена неопределенность вида 0/0. Сумма геометрической прогрессии, знаменатель которой , равна , тогда

Определим состояние СМО, а именно:

1. вероятность отказа ;

2. относительную пропускную способность ;

3. абсолютную пропускную способность ;

4. среднюю длину очереди ;

5. среднее число заявок, связанных с системой ;

6. среднее время ожидания в очереди ;

7. среднее время пребывания заявки в СМО .

Вероятность отказа. Совершенно ясно, что заявке отказано при условии, что канал занят, очередь предполагает наличие мест :

(5.48)

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

(5.49)

 

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

 

 

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

 

 

При вероятности в очереди находится одна заявка, при вероятности - очередь предполагает две заявки. В целом, при вероятности в очереди находится заявок и т.д. Тогда:

(5.50)

править стр.252

 

Из-за того, что от суммы геометрической прогрессии:

 

.

 

Среднее количество заявок, находящихся в системе. Имеем формулу для среднего числа заявок (очередных и обслуживающихся), которые имеют отношения к системе. Из-за того, что определено, необходимо только узнать . Так как существует только один канал, количество обслуживаемых заявок равняется 0 при наличии вероятности и 1 при наличии вероятности , поэтому:

 

 

и среднее число заявок, которое имеет отношение к СМО:

(5.52)

 

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

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

 

 

если использовать здесь выражения для вероятностей (5.47), то

(5.53)

 

 

В данном случае применены соотношения (5.50), (5.51), это и есть производная геометрической прогрессии), и из (5.47).

При сравнении данного и (5.51) выражений можно увидеть:

(5.54)

 

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

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

 

Следовательно,

 

Пример 5.6. АЗС может быть представлена в качестве СМО с одним каналом обслуживания. В данном контексте это одна колонка. На площадке автозаправочной станции может поместится не более трех очередных машин, следовательно . Соответственно, при наличии на площадке трех машин, вновь прибывшая четвертая в очередь не становится. Интенсивность потока прибывающих машин может представлена в таком виде или 1 маш./мин. Заправка одной машины занимает в среднем 1,25 мин.

Найти:

1. вероятность отказа:

2. относительную и абсолютную пропускную способность автозаправочной станции;

3. среднее количество очередных машин;

4. среднее время нахождения машины на АЗС, в том числе обслуживание.

Для начала определим приведенную интенсивность потока заявок:

 

В соответствии с формулами (5.47):

 

 

При этом вероятность отказа

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

 

 

Абсолютная пропускная способность СМО может быть представлена в таком виде:

 

 

Определим среднее число очередных машин, используя формулу (5.51):

 

,

 

это означает, что среднее число очередных машин равно 1,56.

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

 

 

то определим среднее число машин, относящихся к АЗС.

Найдем среднее время ожидания очередной машины, используя формулу (5.54)

 

 

Если прибавить к данному значению

то определим среднее время нахождения машины на АЗС.

 

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

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

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

При условии соотношения (5.47) могут быть отображены следующим образом:

(5.55)

 

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

Определим среднее количество очередных заявок с помощью (5.51) при условии, что :

 

 

Среднее число заявок в системе в соответствии с формулой (5.52) при условии, что

 

 

Найти среднее время ожидания посредством применения формулы (5.53) при условии :

 

 

Среднее время пребывания заявки в СМО — это: