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

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

Линейное программирование

Задача оптимального планирования производства на авиапредприятии

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

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

- количество самолетов типа I- количество самолетов типа II

Задание:

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

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

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

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

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

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

х1+2х2≤45

х1+х2≤12

х1+2х2≤45

х1≤0

х2≤0

х1+х2≤5

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

z = 3х1+6х2 max

x1+2x2 ≤ 45+x2 ≤ 12

x1+5x2 ≤ 45+x2 ≥ 5

= 45-5x1-2x2 ≥ 0= 12-x1-x2 ≥ 0= 45-2x1-5x2 ≥ 0= -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)прибыль в количестве 72 единиц достигается, если доработать I тип самолета с использованием 7 запасов комплектующих, а техническую доработку II типа самолета с использованием 5 комплектующих.

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

=6x1+6x2

x1-2x2 ≥ -45

x1-x2 ≥ -12

x1-5x2 ≥ -45+x2 ≥ 5

         -5 -2 -45*   -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

=Lmin=72

*= 5*= 7*= 6*= 0* = 0* = 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

Решение:

)n=1 количество каналовлиния свободна- линия занята

Ротказа=Р1(состояние системы S1, когда линия занята)

Найдем интенсивность потока обслуживания:

 =1/2= 0,50

Найдем ρ:

ρ= =1

Находим Po:

Po =  = ½

Po=Р1= * ½ = 0,5 ≥ 0,02 (вероятность отказа превышает α)=2 2 каналалинии свободны- 1 линия занята и 1 свободна- обе линии заняты

Ротк=Р2

Р2=  * 0,4= ½ * 0,4 = 0,2 ≥ 0,02

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

Ротк=Р3

Р3= * =  = 0,0625≥ 0,02=4- все линии свободны- 1 линия занята, 3 свободны- 2 линии заняты, 2 свободны- 3 линии заняты, 1 свободна- все линии заняты

Ротк=Р4

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

Задача 2

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

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

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

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

среднее число участников, свободных от работы

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

Дано:=7

λ=14

μ=3,5

В нашем случае Ротк=0,так как очередь без ограничений.относительная пропускная способность системы:= 1- Pотк=1

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

æ===0,57 0,6

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

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

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

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

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

Ро= 1+++…++

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

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

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

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

=  =  =  =0,21

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

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

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

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

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

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

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

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

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

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

прост= * =0,28 * =0,28*0,4=0,112зан= tобсл* =0,28*=0,28*0,6=0,17

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

Теория игр

Принятие управленческих решений на основе теории игр

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

А1-существенно повысить комфортность самолета

А2-не повышать комфортность самолета

А3-повысить комфортность незначительно с минимальными затратами

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

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

S1 S2         S3

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

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

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

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

Решение

S2     S3

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

ῠ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,так как результат соответствует данной стратегии.

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

=max min aij

S1 S2         S3

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

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

Критерий Сэвиджа (Матрица рисков)

Находим элементы матрицы рисков по формуле:=βj-aij βj= max aij

r11= β1-a11=33-33=0=β2-a12=23,5-18=5,5-β3-a13=12-8,5=3,5

=β1-a21=33-26=7=β2-a22=23,5-23,5=0=β3-a23=12-9=3

=β1-a31=33-27=6=β2-a32=23,5-16=7,5

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

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

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

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

=0,5S2  S3 αi αi hi

hi=  * αi +(1-) * αi= 0,5 *8,5 +(1-0,5)*33=20,75 max= 0,5* 9 + (1-0,5)* 26 = 17,5

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

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

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