Помощь в написании студенческих работ
Антистрессовый сервис

Исследование операций

КонтрольнаяПомощь в написанииУзнать стоимостьмоей работы

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

Исследование операций (реферат, курсовая, диплом, контрольная)

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

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

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

Вариант 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

№ вар.

b1

b2

c1

c2

c3

c4

Решение:

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

Обозначим через 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

— 120

— 100

— 150

t4

400/2=200

— 100

— 1

— 1

— 3

t5

250/3=83,3

— 150

— 1,5

— 1,5

— 4,5

t6

350/5=70

— 250

— 2,5

— 2,5

— 7,5

t7

100/2=50

0,5

0,5

1,5

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

b

t7

t2

t3

L

— 40

t4

— 1

— 1

300/2=150

— 200

— 2

— 4

— 6

t5

— 1,5

— 0,5

— 2,5

0,5

— 4,5

t6

— 2,5

— 0,5

— 6,5

0,5

— 7,5

t1

0,5

0,5

1,5

50/0,5=100

1,5

b

t7

t1

t3

L

t4

— 3

— 4

— 7

t5

— 1

— 1

t6

— 2

— 5

t2

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

Таким образом, t1 = t3 =0; t2=100; L=10 000.

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

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

Задача 2

№ 34

Условие:

С помощью симплекс-таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax B,

где = 1 2. .. 6, В = b1 b2. .. b6 ,

= 1 2. .. 6, А= (=1,6; =1,3).

№ вар.

с1

с2

с3

с4

с5

с6

b1

b2

b3

Знаки ограничений

a11

a12

a13

a14

=

=

=

№ вар.

a15

a16

a21

a22

a23

a24

a25

a26

a31

a32

a33

a34

a35

a36

Тип экстрем.

— 1

max

Решение:

Исходная система:

Целевая функция Q= x1+3×2+x3+3×5.

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

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

Q=9 — (9/2×3−½×4)

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

b

x3

x4

Q

9/2

— ½

2/3

— 5/6

x1

3/2

½

2/0,5=4

— 2/3

5/6

— 1

x2

7/3

4/3

x5

2/3

— 5/6

½

2/3: ½=4/3

4/3

— 5/3

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

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

b

x3

x5

Q

29/3

11/3

x1

4/3

2/3

— 1

x2

7/3

4/3

x4

4/3

— 5/3

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

Т. о. 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

с11

с12

с13

с14

с15

с21

с22

с23

с24

с25

с31

с32

с33

с34

с35

Решение:

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

B1

B2

B3

B4

B5

a

A1

A2

A3

b

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

Количество заполненных ячеек 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

A2

A3

b

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

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

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

Если решение верное, то во всех пустых клетках таблицы Дij = cij — (бi+ вj)? 0

Очевидно, что Дij =0 для заполненных клеток.

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

в1=45

в2=60

в3=40

в4=60

в5=70

б1=0

б2= -30

б3= -30

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

Таким образом, решение верное, т.к. Дij ?0.

ОТВЕТ:

B1

B2

B3

B4

B5

a

A1

A2

A3

b

Задача 4

№ 59

Условие:

Определить экстремум целевой функции вида

= 1112+2222+1212+11+22

при условиях

111+122<=>1

211+222<=>2 .

Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.

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

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

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

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

b1

b2

c11

c12

c22

extr

a11

a12

a21

a22

p1

p2

Знаки огр.

1 2

4.5

1.5

— 5

— 2

— 1

max

— 3

Решение:

Целевая функция: F=-5×12-x22−2x1x2+4.5×1+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)=

=-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

— 2

— 5

— 1

y2

1,5

— 4

— 1

w1

— 9

— 2

w2

— 13

— 5

b

w1

x2

u1

u2

v1

v2

Y'

48M

— 6M

— 22M

— 1M

9M

1M

1M

y1

— 40,5

— 2

— 5

— 1

y2

— 7,5

— 4

— 1

x1

4,5

— 0,5

— 1,5

w2

9,5

— 2,5

— 3,5

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

y2

— 68,25

8,5

30,5

1,5

— 11,5

— 1,5

— 1

x1

4,5

— 0,5

— 1,5

w2

9,58

— 2,5

— 3,5

b

w1

x2

y1

y2

v1

v2

Y'

M

M

u1

5,413 043

u2

5,934 783

x1

4,5

w2

9,5

Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413 043; u2=5,934 783; x1=4.5; w2=9.5.

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

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

Приложение

#include

#include

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 ();

}

Показать весь текст
Заполнить форму текущей работой