Контрольная работа

Контрольная работа на тему Исследование операций 4

Работа добавлена на сайт bukvasha.net: 2014-07-03

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 25.11.2024


Министерство общего и профессионального образования РФ
Южно-Уральский Государственный Университет
Кафедра «Системы управления»

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

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

Вариант 14
Группа ПС-317
Выполнил: Родионова Е.В.
Проверил: Плотникова Н.В.
Челябинск, 2004

Содержание
Задача 1                                                                                2
Задача 2                                                                                4
Задача 3                                                                                6
Задача 4                                                                                8      

Задача 1
№14
Условие:
Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В результате смешивания этих четырех компонентов в разных  пропорциях образуется три сорта авиационного бензина: бензин А (а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
Условие:
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx  при условии  Ax ³ £B,
где 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+3x2+x3+3x5.
Пусть х3, х4 – свободные переменные, х1, х2, х5 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
 
Q=9 - (9/2x3-1/2x4)
Составим симплекс-таблицу:
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=-5x12-x22-2x1x2+4.5x1+1.5x2
Ограничения 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)=
=-5x12-x22-2x1x2+4.5x1+1.5x2+u1(2x1-3x2-9)+u2(5x1+4x2-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();
}

1. Реферат Окончание предварительного расследования с составлением обвинительного заключения
2. Контрольная работа Политика управления оборотными активами
3. Реферат на тему Classical Decomposition Model Essay Research Paper For
4. Реферат Метод творческих проектоа- как средство активизации познавательной деятельности
5. Реферат Современные методики проектирования систем оплаты труда
6. Реферат Повреждение грудной клетки
7. Реферат на тему The Effects Of Marijuana On The Brain
8. Реферат Respiration and Respiratory Systems
9. Реферат на тему Devil S Playground Essay Research Paper Devil
10. Реферат на тему Blaxploitation Essay Research Paper The Emergence of