Линейное программирование. Теория массового обслуживания
Линейное программирование
Задача оптимального планирования производства на
авиапредприятии
Авиапредприятие по конструированию и
производству воздушных судов планирует техническую доработку двух типов
самолетов I и II, для осуществления которой необходимо расходовать три вида
комплектующих A, B и C. Потребность аij на каждый самолет j-го типа
комплектующих i-го вида, запас bi соответствующего вида комплектующих и прибыль
Cj от выпуска и реализации единицы j-го типа модернизированного воздушного
судна заданы таблицей:
Индивидуальные значения: m= 4, n= 5
Виды
комплектующих
|
Типы
самолетов
|
Запасы
комплектующих
|
|
I
|
II
|
|
A
|
a11=5
|
a12=2
|
b1=45
|
B
|
a21=1
|
a22=1
|
b2=12
|
C
|
a31=2
|
a32=5
|
b3=45
|
Прибыль
|
c1=6
|
c2=6
|
|
План(ед)
|
х1
|
х2
|
|
- количество самолетов типа 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
|
х2
|
x3
|
45
-10
|
5
-2
|
2
2
|
x4
|
12
-5
|
1
-1
|
1
1
|
x5
|
45
-25
|
2
-5
|
5
5
|
x6
|
-5
5
|
-1
1
|
-1
-1
|
L
|
-6
6
|
-6
-6
|
Базисные
переменные
|
Свободные
члены
|
Свободные
переменные
|
|
|
х1
|
x6
|
x3
|
35
-8
|
3
1,2
|
2
-0,4
|
x4
|
7
-4
|
0
0,6
|
1
-0,2
|
x5
|
20
4
|
-3
-0,6
|
5
0,2
|
x2
|
5
4
|
1
-0,6
|
-1
0,2
|
L
|
30
24
|
0
-3,6
|
-6
1,2
|
Базисные
переменные
|
Свободные
члены
|
Свободные
переменные
|
|
|
х1
|
x5
|
x3
|
27
-21
|
4,2
-7
|
-0,4
1,4
|
x4
|
3
5
|
0,6
1,6
|
-0,2
-0,3
|
x6
|
4
3
|
-0,6
1
|
0,2
-0,2
|
x2
|
9
-2,1
|
0,4
-0,7
|
0,2
0,14
|
L
|
54
18
|
-3,6
-6
|
1,2
-1,2
|
Базисные
переменные
|
Свободные
члены
|
Свободные
переменные
|
|
|
x4
|
x5
|
x3
|
6
|
-7
|
1
|
x1
|
5
|
1,6
|
-0,3
|
x6
|
7
|
1
|
0
|
x2
|
-0,7
|
0,34
|
L
|
72
|
6
|
0
|
х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
Переменные прямой задачи
Основные
|
Дополнительные
|
x1
x2
|
x3,
x4, x5, x6
|
y5
y6
|
y1,
y2, y3, y4
|
Переменные
двойной задачи
|
Ответ: 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,так как она выбирается по критериям и существенно
повысить комфортность самолета.