min (max ri =li 
mi ) = min (max ri =li mi ) {i
=1..N}{li }
{i=1..N}
Ограничения:
N
åli =l
i=1
mi >li ³ 0 i=1,2,…N,
Решение:
Для решения задачи постановку задачи можно переписать в эквивалентной формулировке, вводя новую переменную β0 и новые ограничения.
Найти: такие значения переменных β0 , λi i=1,2,…N, которые минимизируют линейную аддитивную целевую функцию
β0=min С0b0 + С1l1 + С2l2+....+Сnln (4.1)
{li ;b0} где C0 = 1, Ci = 0, i=1,2,… N Ограничения :
b0m1 > l1
b0m2 > l2
.................. b0mN >lN
N
åli =l
i=1
li ³ 0 mi ³ 0
Ограничения можно переписать в виде:
b0 > r1 = l1m1
b0 > r2 =l2m2
…………
b0 > rN =lNmN (4.2.)
N
åli =l
i=1
li ³ 0 mi ³ 0
Исходную минимаксную задачу свели к задаче линейного программирования (4.1), (4.2), которая решается графически при двух переменных и численно симплекс- методом в общем случае.
4. Задача определения максимального потока в сети.
Рассмотрим в качестве функциональной модели совокупности серверов параллельную сеть массового обслуживания со случайным ветвлением заявок (рис. 2.2.1.). Каждый сервер представим одноканальной системой массового обслуживания M/M/1. Предполагается, что общий входной поток в сеть λ является переменной величиной, причём при изменении λ отношение λi / λ сохраняется постоянным (распределение заявок по серверам рi i=1,2,… N с изменением нагрузки не меняется). Производительность каждой системы μi задана. С ростом нагрузки λ растёт средняя задержка любой заявки в сети. Под пропускной способностью сети понимается такая максимальная нагрузка λ, при которой средняя задержка любой заявки в сети будет равна допустимой величине Т. Дальнейший рост нагрузки приводит к увеличению задержки на величину больше Т.
Постановка задачи определения максимального потока в сети будет иметь вид:
Дано:
· N – изолированных серверов и их модели в виде систем М/М/1
N
· mi - производительность каждого сервера i=1,2,…N , åmi =m
i=1
· Pi -распределение потока λ по серверам, Pi = λi/ λ – константы, i = 1,……N
Найти: такую нагрузку на сеть λ (и соответственно на каждый сервер λi ), при которой суммарный поток через сеть будет максимальным:
N N
λ=
i1li = max{
}li åi=1 li ,
(5.1)
=
Ограничения: åN li 
1 = åN Pi 
1 = T
(5.2.) i=1 lmi -li i=1 mi -li mi
>
li
³0 , i = 1,……N
Решение:
Рассмотрим критериальную функцию (5.1). Критериальная функция является аддитивной функцией величин λi, каждая из которых есть линейна (выпукла). Тогда критериальная функция (5.1) также будет выпукла.Докажем это. Найдём частные производные функций (5.1) и (5.2.).
¶l= 1 > 0, ¶2l2 = 0, i = 1,……N (5.3.)
¶li ¶li
¶¶l2T2 =Pi -2((mmii --llii ))(4-1) =Pi 
(mi -2li )3 > 0 i =
1,……N (5.4.)
i
Из (5.3) видно, что вторая производная критериальной функции равна нулю, следовательно функция выпукла как сумма линейных слагаемых. Ограничение (5.4) также является выпуклым (вторая производная функции больше нуля). Тогда локальный минимум задачи будет глобальным и можно применить метод множителей Лагранжа. Образуем функцию Лагранжа:
L(l1...lNb) = åiN=1li +bççèæT -åiN=1 Pi 
mi 1-lö÷ø÷
Имеем функцию N+1 переменной без ограничений. Дифференцируя её по λi ,β, i = 1, 2,…N и приравнивая результат к нулю получаем систему N+1уравнений с N+1 неизвестными:
ìïﶶlLi =1-bPi 
1 2 =0
(mi -li )
íïﶶbL =T-åi=n1 Pi 
mi 1-li =0 i = 1,
2,…N (5.5) î
Из (5.5) получим:
li =mi + Pi b
i = 1, 2,…N ( 5 . 6 )
Подставив λi из (5.6) в (5.5) получим
N
Pi
b= i=1
T
Или окончательно из (5.6) находим: æ N ö
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.