Линейное программирование. 
Теория массового обслуживания

Линейное программирование Задача оптимального планирования производства на авиапредприятии Авиапредприятие по конструированию и производству воздушных судов планирует техническую доработку двух типов самолетов I и II, для осуществления которой необходимо расходовать три вида комплектующих A, B и C. Потребность аij на каждый самолет j-го типа комплектующих i-го вида, запас bi соответствующего вида комплектующих и прибыль Cj от выпуска и реализации единицы j-го типа модернизированного воздушного судна заданы таблицей:

Индивидуальные значения: m= 4, n= 5

X1 — количество самолетов типа I

X2 — количество самолетов типа II

Задание:

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

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

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

Составить двойственную задачу и найти её решение по теоремам двойственности.

а) 1. Вводим переменные, где х?=(х1,х2)

2.система ограничений

5х1+2×2?45

х1+х2?12

2х1+2×2?45

х1?0

х2?0

х1+х2?5

3) целевая функция:

z = 3×1+6×2 max

5x1+2×2? 45

x1+x2? 12

2x1+5×2? 45

x1+x2? 5

x3 = 45−5×1−2×2? 0

x4 = 12-x1-x2? 0

x5 = 45−2×1−5×2? 0

x6 = -5+x1+x2? 0

4) возьмем х1 и х2 в качестве свободных переменных, а х3, х4,х5,х6 в качестве базисных.

б) Симплекс-метод

х1 = 5 I тип самолетов х2= 6,9? 7 II тип самолетов х3= 6 количество остатков сырья, А х4= 0 количество остатков сырья В (израсходовано полностью) х5= 0 сырье С израсходовано х6= 7 для проверки полностью Оптимальный план: (5;6,9;6;0;0;7)

Max прибыль в количестве 72 единиц достигается, если доработать I тип самолета с использованием 7 запасов комплектующих, а техническую доработку II типа самолета с использованием 5 комплектующих.

Двойственная задача

L=6×1+6x2

— 5×1−2×2? -45

— x1-x2? -12

— 2×1−5×2? -45

x1+x2? 5

— 5 -2 -45

A1* -1 -1 -12

— 2−5 -45

1 1 5

6 6 Z

Транспонируем матрицу:

— 5 -1 -2 1 6

А2* -2 -1 -5 1 6

— 45 -12 -45 5 2

L = 45y1 — 12y2 — 45y3 — 5y4

— 5 -1 -2 1? 6

— 2 -1 -5 1? 6

Zmax=Lmin=72

x1*= 5

x2*= 7

x3*= 6

x4*= 0

x5* = 0

x6* = 7

Переменные прямой задачи

Ответ: Lmin=72. Оптимальный план: y1*=0;y2*=0;y3*=3;y4*=0;y5*=0;y6*=0

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

Необходимо спроектировать автоматизированную информационную систему (АИС) так, чтобы она обладала пропускной способностью, при которой вероятность получения абонентом отказа в обслуживании не превосходила Р? б.

АИС проектируется исходя из условия, что поток вызовов случайный, пуассоновский, с интенсивностью л=0,25 вызовов в минуту. Считается, что время обслуживания запроса подчинено показательному закону со средней продолжительностью обслуживания To — 4,0.

Буквенные обозначения:

л — интенсивность потока заявок Тосредняя продолжительность обслуживания минтенсивность потока обслуживания сприведенная интенсивность Дано:

л= 0,50

То=2,0

б = 0,01

Решение:

1)n=1 количество каналов

So-линия свободна

S1- линия занята Ротказа=Р1(состояние системы S1, когда линия занята) Найдем интенсивность потока обслуживания:

=½= 0,50

Найдем с:

с= =1

Находим Po:

Po = = Ѕ

Po=Р1= * Ѕ = 0,5? 0,02 (вероятность отказа превышает б)

n=2 2 канала

Soлинии свободны

S1- 1 линия занята и 1 свободна

S2- обе линии заняты Ротк=Р2

Р2= * 0,4= Ѕ * 0,4 = 0,2? 0,02

n=3

Soвсе линии свободны

S1- 1 линия занята, 2 свободны

S2- 2 линии заняты, 1 свободна

S3- все линии заняты Ротк=Р3

Р3= * = = 0,0625? 0,02

n=4

S0- все линии свободны

S1- 1 линия занята, 3 свободны

S2- 2 линии заняты, 2 свободны

S3- 3 линии заняты, 1 свободна

S4- все линии заняты Ротк=Р4

Р4= *0,37= = 0,015?0,02

Вывод: для эффективной работы АИС необходимо 4 канала. В этом случае вероятность отказа будет сведена к минимуму, т. е. менее 0,02.

Задача 2

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

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

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

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

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

Дано:

n=7

л=14

м=3,5

В нашем случае Ротк=0,так как очередь без ограничений.

q-относительная пропускная способность системы:

q= 1- Pотк=1

Приведенная интенсивность потока заявок:

ж===0,57 0,6

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

А= л* q=14(аппаратов в сутки)

Приведенная интенсивность потока: ===4

Время обслуживания: tобсл==

Предельные вероятности состояний:

Ро= 1+++…++

Pо= 1++++++++ =

= (1+4+8+10,7+10,7+8,5+5,7+3,25+4,3) = 56,15 = 0,018

линейное программирование заявка очередь Среднее число заявок в очереди:

r = = = =0,21

Среднее время ожидания заявки в очереди:

tожид=== = =0,015

Среднее число занятых каналов:

Z===4(занято участков) Среднее число занятых каналов:

N=n-Z=7−4=3(свободных каналов) Для более подробных выводов воспользуемся дополнительными характеристиками:

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

к= Z+r = 4+0,21=4,21 (~4 заявки)

Среднее пребывание заявки в системе:

tсист= tожид + q * tобсл = 0,015+1*1/35=0,26

Среднее время простоя одного канала:

tпрост= * =0,28 * =0,28*0,4=0,112

tзан= tобсл* =0,28*=0,28*0,6=0,17

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

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

А1-существенно повысить комфортность самолета А2-не повышать комфортность самолета А3-повысить комфортность незначительно с минимальными затратами Величины прибыли от продажи самолетов для этих трех случаев просчитаны менеджерами авиакомпании для трех разных возможных ситуаций на рынке авиаперевозок:

S1-благоприятная ситуация, связанная с ростом экономики и повышением платежеспособности населения

S2-нейтральная ситуация, средний уровень благосостояния населения

S3- неблагоприятная ситуация, упадок экономики, кризис:

И заданы платежной матрицей

S1 S2 S3

Необходимо определить:

какая стратегия авиакомпании наиболее выгодна, если известны вероятности состояний S1, S2, S3: соответственно 0,2;0,6;0,2.

Определить оптимальные стратегии по критериям Вальда, Сэвиджа, Гурвица, полагая вероятности состояний S1, S2,S3 неизвестными.

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

Решение

S1 S2 S3

1.Выбираем критерий Лапласа-Байеса

?1=33*0,2+18*0,6+8,5*0,2=19,1

?2=26*0,2+23,5*0,6+9*0,2=21,1 (выбираем максимум)

?3=27*0,2+16*0,6+12*0,2=17,4

?2=А2

Вывод: Следует придерживаться стратегии А2, так как результат соответствует данной стратегии.

Выбираем критерий Вальда

W=max min aij

S1 S2 S3

Выписываем min, а затем выбираем max.

Вывод: по критерию Вальда следует придерживаться 3 стратегии, так как результат (12) соответствует А3.

Критерий Сэвиджа (Матрица рисков) Находим элементы матрицы рисков по формуле:

rij=вj-aij вj= max aij

r11= в1-a11=33−33=0

r12=в2-a12=23,5−18=5,5

r13-в3-a13=12−8,5=3,5

r21=в1-a21=33−26=7

r22=в2-a22=23,5−23,5=0

r23=в3-a23=12−9=3

r31=в1-a31=33−27=6

r32=в2-a32=23,5−16=7,5

r33=в3-a33=12−12=0

Выписываем максимум, среди которого находим минимум.

Вывод: по критерию Сэвиджа следует придерживаться стратегии А1, так как результат соответствует данной стратегии.

Критерий Гурвица

G=max (min aij+(1-)max aij)

=0,5

S1 S2 S3 бi бi hi

hi= * бi +(1-) * бi

h1= 0,5 *8,5 +(1−0,5)*33=20,75 max

h2 = 0,5* 9 + (1−0,5)* 26 = 17,5

h3 = 0,5* 12+(1−0,5) * 27 = 13,5

Вывод: по критерию Гурвица следует придерживаться стратегии А1, так как результат 20,75 соответствует данной стратегии.

Общий вывод: предприятию следует придерживаться стратегии А1, так как она выбирается по критериям и существенно повысить комфортность самолета.