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

Размещено на http://www.allbest.ru

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

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

Авиапредприятие по конструированию и производству воздушных судов планирует техническую доработку двух типов самолетов 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

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+2x2 ? 45

x1+x2 ? 12

2x1+5x2 ? 45

x1+x2 ? 5

x3 = 45-5x1-2x2 ? 0

x4 = 12-x1-x2 ? 0

x5 = 45-2x1-5x2 ? 0

x6 = -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	0 30	-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	6,9	-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)

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

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

L=6x1+6x2

-5x1-2x2 ? -45

-x1-x2 ? -12

-2x1-5x2 ? -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

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

Основные	Дополнительные
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

Решение:

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

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

S1- линия занята

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

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

=1/2= 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,так как она выбирается по критериям и существенно повысить комфортность самолета.

Размещено на Allbest.ru