Учебная работа. Контрольная работа: Исследование операций 4

Кафедра «Системы управления»

КУРСОВАЯ РАБОТА

ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ

Вариант 14

Группа ПС-317

Выполнил: Родионова Е.В.

Проверил: Плотникова Н.В.

Челябинск, 2004

Содержание

задачка 1 2

Задачка 2 4

Задачка 3 6

Задачка 4 8

Задачка 1

№14

Условие:

Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В итоге смешивания этих 4 компонент в различных пропорциях появляется три сорта авиационного бензина: бензин А (а1:а2:а3:а4), бензин В (b1:b2:b3:b4) и бензин С (с1:с2:с3:с4).

Стоимость 1 тыс. л. бензина всякого сорта равна y1 руб., y2 руб. и y3 руб.

Найти соотношение компонент, при котором будет достигнута наибольшая стоимость всей продукции.

№ вар.
x1
x2
x3
x4
y1
y2
y3
а1
а2
а3
а4
b1
b2

1
400
250
350
100
120
100
150
2
3
5
2
3
1


№ вар.
b1
b2
c1
c2
c3
c4

1
2
1
2
2
1
3

Решение:

Составим математическую модель задачки.

Обозначим через t1 количество бензина А;

через t2 количество бензина В;

через t3 количество бензина С.

Тогда, мотивированная функция будет

L=y1t1+ y2t2+ y3t3=120t1+100t2+150t3 →max

Система ограничений:

Приведем систему ограничений к виду главный задачки линейного программирования (введем новейшие переменные t4 , t5 ,t6 ,t7, которые входят в мотивированную функцию с нулевыми коэффициентами):

Выберем t1 , t2 ,t3 вольными переменными, а t4 , t5 ,t6 ,t7 – базовыми и приведем к обычному виду для решения при помощи симплекс-таблицы:

L=0-(-120t1-100t2-150t3)

Составим симплекс-таблицу.

Это решение опорное, т.к. все вольные члены положительны.

Т. к. все коэффициенты в мотивированной функции отрицательные, то можно взять хоть какой столбец разрешающим (пусть t1). Выберем в качестве разрешающего элемента тот, для которого отношение к нему вольного члена будет мало (это t7)

b
t1
t2
t3

L
0
-120
-100
-150

6000
60
60
180

t4
400
2
3
2
400/2=200

-100
-1
-1
-3

t5
250
3
1
2
250/3=83,3

-150
-1,5
-1,5
-4,5

t6
350
5
2
1
350/5=70

-250
-2,5
-2,5
-7,5

t7
100
2
1
3
100/2=50

50
0,5
0,5
1,5

Дальше меняем t2 и t1 .

b
t7
t2
t3

L
6000
60
-40
30

4000
40
80
120

t4
300
-1
2
-1
300/2=150

-200
-2
-4
-6

t5
100
-1,5
-0,5
-2,5

50
0,5
1
-4,5

t6
50
-2,5
-0,5
-6,5

50
0,5
1
-7,5

t1
50
0,5
0,5
1,5
50/0,5=100

100
1
2
1,5


b
t7
t1
t3

L
10000
100
80
150

t4
100
-3
-4
-7

t5
150
-1
1
-1

t6
100
-2
1
-5

t2
100
1
2
3

Т.к. коэффициенты при переменных в мотивированной функции положительны, как следует, это наилучшее решение.

Таковым образом, t1 = t3 =0; t2=100; L=10000.

Т.е. для получения наибольшей прибыли следует создавать лишь бензин В (100 тыс. л.), при всем этом выручка составит 10000 руб.

ОТВЕТ: для получения наибольшей прибыли следует создавать лишь бензин В (100 тыс. л.), при всем этом выручка составит 10000 руб.

задачка 2

№34

Условие:

При помощи симплекс–таблиц отыскать решение задачки линейного программирования: найти экстремальное

где CT = [c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T ,

XT = [x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).

№ вар.
с1
с2
с3
с4
с5
с6
b1
b2
b3
Знаки ограничений
a11
a12
a13
a14

1
2
3

34
3
3
1
1
0
0
4
4
15
=
=
=
2
0
3
1

№ вар.
a15
a16
a21
a22
a23
a24
a25
a26
a31
a32
a33
a34
a35
a36
Тип экстрем.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 34
0
0
1
0
–1
2
3
0
3
3
6
3
6
0
max

Решение:

Начальная система:

Мотивированная функция Q= x1+3×2+x3+3×5.

Пусть х3, х4 – вольные переменные, х1, х2, х5 – базовые.

Приведем систему и мотивированную функцию к обычному виду, для построения симплекс-таблицы:

Q=9 — (9/2×3-1/2×4)

Составим симплекс-таблицу:

b
x3
x4

Q
9
9/2
-1/2

2/3
-5/6
1

x1
2
3/2
1/2
2/0,5=4

-2/3
5/6
-1

x2
7/3
4/3
0

0
0
0

x5
2/3
-5/6
1/2
2/3 : 1/2=4/3

4/3
-5/3
2

Это опорное решение, т.к. вольные члены положительны.

Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему вольного члена будет мало (это х5).

b
x3
x5

Q
29/3
11/3
1

x1
4/3
2/3
-1

x2
7/3
4/3
0

x4
4/3
-5/3
2

Т.к. коэффициенты при переменных в мотивированной функции положительны, как следует, это наилучшее решение.

Т. о. Q=29/3

x3=x5=0; x1=4/3; x2=7/3; x4=4/3.

ОТВЕТ: Q=29/3ж

x3=x5=0; x1=4/3; x2=7/3; x4=4/3.

задачка 3

№14

Условие:

Решение транспортной задачки:

1. Записать условия задачки в матричной форме.

2. Найти опорный план задачки.

3. Найти лучший план задачки.

4. Проверить решение задачки способом потенциалов.

№вар.
а1
а2
а3
b1
b2
b3
b4
b5
с11
с12
с13

14
90
50
30
15
45
45
50
15
45
60
40

с14
с15
с21
с22
с23
с24
с25
с31
с32
с33
с34
с35

60
95
35
30
55
30
40
50
40
35
30
100

Решение:

Составим таблицу транспортной задачки и заполним ее способом северо-западного угла:

B1
B2
B3
B4
B5
a

A1
45
60
40
60
95
90

15
45
30

A2
35
30
55
30
40
50

15
35

A3
50
40
35
30
100
30

15
15

b
15
45
45
50
15
170

Это будет опорный план.

количество заполненных ячеек r=m+n-1=6.

1) Разглядим цикл (1,2)-(1,3)-(2,3)-(3,2):

с1,2+с2,3>c1.3+c3.2 (60+55>30+40)

количество единиц продукта, перемещаемых по циклу: min (с1,2 ; с2,3)=15

2) Разглядим цикл (2,4)-(2,5)-(3,5)-(3,4):

c2,4+с3,5>c2.5+c3.4 (30+40>30+100)

количество единиц продукта, перемещаемых по циклу: min (с2,4 ; с3,5)=15

В итоге получится последующий план:

B1
B2
B3
B4
B5
a

A1
45
60
40
60
95
90

15
30
45

A2
35
30
55
30
40
50

15
20
15

A3
50
40
35
30
100
30

30

b
15
45
45
50
15
170

больше циклов с «отрицательной ценой» нет, означает, это наилучшее решение.

Проверим способом потенциалов:

Примем α1=0, тогда βj = cij – αi (для заполненных клеток).

Если решение верное, то во всех пустых клеточках таблицы Δij = cij – (αi+ βj) ≥ 0

Разумеется, что Δij =0 для заполненных клеток.

В итоге получим последующую таблицу:

β1=45
β2=60
β3=40
β4=60
β5=70

α1=0
45
60
40
60
95
90

15
30
45
0
+

α2= -30
35
30
55
30
40
50

+
15
+
20
15

α3= -30
50
40
35
30
100
30

+
+
+
30
+

15
45
45
50
15
170

Δ1,4=0 указывает, что существует еще один цикл с таковой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но потому что при всем этом общая стоимость не поменяется, то нет смысла поменять перевозки.

Таковым образом, решение верное, т.к. Δij ≥0.

ОТВЕТ:

B1
B2
B3
B4
B5
a

A1
45
60
40
60
95
90

15
30
45

A2
35
30
55
30
40
50

15
20
15

A3
50
40
35
30
100
30

30

b
15
45
45
50
15
170

задачка 4

№59

Условие:

Найти экстремум мотивированной функции вида

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при критериях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

1. Отыскать стационарную точку мотивированной функции и изучить ее (функцию) на неровность (вогнутость) в округах стационарной точки.

2. Составить функцию Лагранжа.

3. Получить систему неравенств в согласовании с аксиомой Куна-Таккера.

4. Используя способ искусственных переменных составить симплекс-таблицу и отыскать решение приобретенной задачки линейного программирования.

5. Отдать ответ с учетом критерий дополняющей нежесткости.

№
b1
b2
c11
c12
c22
extr
a11
a12
a21
a22
p1
p2

Знаки огр.

1 2

59
4.5
1.5
–5
–2
–1
max
2
–3
5
4
9
13
³
³

Решение:

Мотивированная функция: F=-5×12-x22-2x1x2+4.5×1+1.5×2

Ограничения g1(x) и g2(x): →

1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):

→ →

2) Исследуем стационарную точку на максимум, для чего же определяем неровность либо вогнутость функции

F11 (х10, х20) = -10 < 0

F12 (х10, х20) = -2

F21 (х10, х20) = -2

F22 (х10, х20) = -2

Т.к. условие производится, то мотивированная функция является строго вогнутой в округи стационарной точки

3) Составляем функцию Лагранжа:

L(x,u)=F(x)+u1g1(x)+u2g2(x)=

=-5×12-x22-2x1x2+4.5×1+1.5×2+u1(2×1-3×2-9)+u2(5×1+4×2-13)

Получим уравнения седловой точки, применяя аксиому Куна-Таккера:

i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:

Система В:

Перепишем систему А:

4)Введем новейшие переменные

V={v1,v2}≥0; W={w1,w2}≥0

в систему А для того, чтоб неравенства перевоплотить в равенства:

Тогда

.

Как следует, система В воспримет вид:

— это условия дополняющей нежесткости.

5) Решим систему А при помощи способа искусственных переменных.

Введем переменные Y={y1; y2} в 1 и 2 уравнения системы

и сделаем псевдоцелевую функцию Y=My1+My2→min

Y’=-Y= -My1-My2→max.

В качестве вольных выберем х1, х2, v1, v2, u1, u2;

а в качестве базовых y1, y2, w1, w2.

Приведем систему и мотивированную функцию к обычному виду, для построения симплекс-таблицы:

Решим при помощи симплекс-таблицы. Найдем опорное решение:

Примечание: вычисления выполнялись программно, см приложение

b
x1
x2
u1
u2
v1
v2

Y’
-6M
-12M
-4M
-M
9M
M
M

y1
4,5
10
2
-2
-5
-1
0

y2
1,5
2
2
3
-4
0
-1

w1
-9
-2
3
0
0
0
0

w2
-13
-5
4
0
0
0
0

b
w1
x2
u1
u2
v1
v2

Y’
48M
-6M
-22M
-1M
9M
1M
1M

y1
-40,5
5
17
-2
-5
-1
0

y2
-7,5
1
5
3
-4
0
-1

x1
4,5
-0,5
-1,5
0
0
0
0

w2
9,5
-2,5
-3,5
0
0
0
0

b
w1
x2
y1
u2
v1
v2

Y’
68,25M
-8,5M
-30,5M
-0,5M
11,5M
1,5M
1M

u1
20,25
-2,5
-8,5
-0,5
2,5
0,5
0

y2
-68,25
8,5
30,5
1,5
-11,5
-1,5
-1

x1
4,5
-0,5
-1,5
0
0
0
0

w2
9,58
-2,5
-3,5
0
0
0
0

b
w1
x2
y1
y2
v1
v2

Y’
0
0
0
M
M
0
0

u1
5,413043

u2
5,934783

x1
4,5

w2
9,5

Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413043; u2=5,934783; x1=4.5; w2=9.5.

б) Условия дополняющей нежесткости не производятся (u2w2≠0), означает решения начальной задачки квадратичного программирования не существует.

ОТВЕТ: не существует.

приложение

#include <math.h>

#include <stdio.h>

main()

{

int i,j,k,m;

double h,n,a[5][7],b[5][7];

clrscr();

printf («Введите числа матрицы А «);

for (i=0; i<5; i++){for(j=0; j<7; j++) {scanf («%lf»,&n); a[i][j]=n;}}

printf («Введите координаты разрешающего элементаn»);

scanf(«%d»,&k) ;

scanf («%d»,&m);

printf (» матрицa A n»);

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (» %lf»,a[i][j]);printf («n»);}

printf (» координаты n «);

printf(«%d %d»,k,m) ;

h=1/a[k][m];

b[k][m]=h;

printf («n h=%lf»,h);

for (i=0; i<7; i++)

{ if (i!=m) b[k][i]=a[k][i]*b[k][m]; }

for (i=0;i<5; i++)

{ if (i!=k) b[i][m]=-a[i][m]*b[k][m];}

for (i=0;i<5;i++)

{

for (j=0;j<7;j++)

if ((i!=k)&&(j!=m)) b[i][j]=a[i][j]+a[k][j]*b[i][m];

}

printf («n итог «);

printf (» матрицa B n»);

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (» %lf»,b[i][j]);printf («n»);}

getch();

}

]]>