Скачать

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

Министерство общего и профессионального образования РФ

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

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

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

Вариант 14

Челябинск, 2004


Содержание

1. Задача 1

2. Задача 2

3. Задача 3

4. Задача 4

Приложение


1.Задача 1

Условие:

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

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

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

№ вар.x1x2x3x4y1y2y3а1а2а3а4b1b2
1400250350100120100150235231
№ вар.b1b2c1c2c3c4
1212213

Решение:

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

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

bt1t2t3
L0-120-100-150
60006060180
t4400232400/2=200
-100-1-1-3
t5250312250/3=83,3
-150-1,5-1,5-4,5
t6350521350/5=70
-250-2,5-2,5-7,5
t7100213100/2=50
500,50,51,5

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

bt7t2t3
L600060-4030
40004080120
t4300-12-1300/2=150
-200-2-4-6
t5100-1,5-0,5-2,5
500,51-4,5
t650-2,5-0,5-6,5
500,51-7,5
t1500,50,51,550/0,5=100
100121,5
bt7t1t3
L1000010080150
t4100-3-4-7
t5150-11-1
t6100-21-5
t2100123

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

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

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

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

2. Задача 2

Условие:

С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции 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с6b1b2b3Знаки ограниченийa11a12a13a14
123
343311004415===2031
№ вар.a15a16a21a22a23a24a25a26a31a32a33a34a35a36Тип экстрем.

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

1. 340010–1230336360max

Решение:

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

Целевая функция Q= x1+3x2+x3+3x5.

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

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

Q=9 - (9/2x3-1/2x4)

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

bx3x4
Q99/2-1/2
2/3-5/61
x123/21/22/0,5=4
-2/35/6-1
x27/34/30
000
x52/3-5/6

1/2

2/3 : 1/2=4/3
4/3-5/32

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

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

bx3x5
Q29/311/31
x14/32/3-1
x27/34/30
x44/3-5/32

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

Т. о. 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. Задача 3

Условие:

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

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

2. Определить опорный план задачи.

3. Определить оптимальный план задачи.

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

№вар.а1а2а3b1b2b3b4b5с11с12с13
149050301545455015456040
с14с15с21с22с23с24с25с31с32с33с34с35
6095353055304050403530100

Решение:

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

B1B2B3B4B5a
A1456040609590
154530
A2353055304050
1535
A35040353010030
1515
b1545455015170

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

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

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

B1B2B3B4B5a
A1456040609590
153045
A2353055304050
152015
A35040353010030
30
b1545455015170

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

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

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

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

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

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

β1=45β2=60β3=40β4=60β5=70
α1=0456040609590
1530450+
α2= -30353055304050
+15+2015
α3= -305040353010030
+++30+
1545455015170

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

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

ОТВЕТ:

B1B2B3B4B5a
A1456040609590
153045
A2353055304050
152015
A35040353010030
30
b1545455015170

4. Задача 4

Условие:

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

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

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

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

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

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

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

b1b2c11c12c22extra11a12a21a22p1p2Знаки огр.1 2
594.51.5–5–2–1max2–354913³³

Решение:

Целевая функция: F=-5x12-x22-2x1x2+4.5x1+1.5x2

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

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

2)

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

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.

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

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

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

bx1x2u1u2v1v2
Y'-6M-12M-4M-M9MMM
y14,5102-2-5-10
y21,5223-40-1
w1-9

-2

30000
w2-13-540000
bw1x2u1u2v1v2
Y'48M-6M-22M-1M9M1M1M
y1-40,5517-2-5-10
y2-7,515