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

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

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

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

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

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

от 25%

Подписываем

договор

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

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


Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
Вариант 9
_
Челябинск
2004 г.
Содержание
Задание 1                                                                                            3
Задание 2                                                                                            6
Задание 3                                                                                            9
Задание 4                                                                                  11
Литература                                                                               17

Задание 1
Задача 9
Условие:
Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее  a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.
Вещество
Количество единиц вещества, содержащегося в 1 кг сырья
1
2
3
А
d11
d12
d13
В
d21
d22
d23
С
d31
d32
d33
Цена 1 кг сырья
D1
D2
D3
№ вар.
d11
d12
d13
d21
d22
d23
d31
d32
d33
9
1
1
0
2
0
3
1
2
4
D1
D2
D3
а
b
c
5
6
7
26
30
24
Решение:
Составим математическую модель задачи.
Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.
Тогда, целевая функция будет
L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min
Система ограничений:
_ EMBED Equation.3  ___
Приведем систему ограничений к  виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные  n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.
L’=0-(5n1+ 6n2+7n3) →max
_ EMBED Equation.3  ___
Выберем n1, n2, n3 свободными переменными, а  n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L’=0-(5n1+ 6n2+7n3)
_ EMBED Equation.3  ___
Составим симплекс-таблицу.
Это решение не опорное, т.к. свободные члены не положительны.
Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).
Таблица 1.1
b
n1
n2
n3
L’
0
5
6
7
-75
2,5
0
-8
n4
-26
-1
-1
0
26/1=26
15
-1
0
1,5
n5
-30
-2
0
-3
30/2=15min
15
-1
0
1,5
n6
-24
-1
-2
-4
24/1=24
15
-1
0
1,5
Меняем n1 и n5.
Таблица 1.2
b
n5
n2
n3
L’
-75
2,5
6
-0,5
-45
5
-10
25
n4
-11
-0,5
-1
1,5
11/0,5=22
9
-1
2
-5
n1
15
-0,5
0
1,5
9
-1
2
-5
n6
-9
-0,5
-2
-2,5
9/0,5=18min
18
-2
4
5
Меняем n5 и n6.
Таблица 1.3
b
n6
n2
n3
L’
-120
5
-4
25
-10
5
5
-18
n4
-2
-1
1
-4
2
-1
-1
2,5
n1
24
-1
2
-3
2
-1
-1
3,5
n5
18
-2
4
5
4
-2
-2
7
Меняем n4 и n6.
Таблица 1.4
b
n4
n2
n3
L’
-130
5
1
7
 
 
 
 
n6
2
-1
-1
3,5
 
 
 
 
n1
26
-1
-1
0
 
 
 
 
n5
22
-2
2
12
 
 
 
 
Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.

Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции 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
29
0
5
1
–1
1
0
2
2
10
 
Знаки ограничений
a11
a12
a13
a14
1
2
3
£
£
£
–1
1
1
0
a15
a16
a21
a22
a23
a24
a25
a26
0
0
1
–2
0
1
0
0
a31
a32
a33
a34
a35
a36
Тип экстрем.
2
1
1
1
2
0
max
Решение:
Составим систему:
_ EMBED Equation.3  ___
Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3  ___
Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3  ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
b
x1
x2
x3
x4
x5
Q
0
0
-5
-1
1
-1
10
-5
5
5
0
0
x6
2
-1
1
1
0
0
2/1=2min
2
-1
1
1
0
0
x7
2
1
-2
0
1
0
4
-2
2
2
0
0
x8
10
2
1
1
1
2
10/2=5
-2
1
-1
-2
0
0
Меняем x2 и x6.
Таблица 2.2
b
x1
x6
x3
x4
x5
Q
10
-5
5
4
1
-1
4
1,5
-1
-1
0,5
0,5
x2
2
-1
1
1
0
0
0
0
0
0
0
0
x7
6
-1
2
2
1
0
0
0
0
0
0
0
x8
8
3
-1
-1
1
2
4
6
-2
-2
2
0,5

Меняем x5 и x8.
Таблица 2.3
b
x1
x6
x3
x4
x8
Q
14
-3.5
4,5
3,5
1,5
0,5
21
5,25
-2,625
-2,625
2,625
2,625
x2
2
-1
1
1
0
0
8/3 
2/3
-1/3
-1/3
1/3
1/3
x7
6
-1
2
2
1
0
8/3
2/3
-1/3
-1/3
1/3
1/3
x5
4
1,5
-0,5
-1
0,5
0,5
8/3
2/3
-1/3
-1/3
1/3
1/3
Меняем x5 и x1.
Таблица 2.4
b
x5
x6
x3
x4
x8
Q
35
5,25
1,875
0,875
4,125
3,125
x2
14/3
2/3
2/3
2/3
1/3
1/3
x7
26/3
2/3
5/3
5/3
4/3
1/3
x1
8/3
2/3
-1/3
-1/3
1/3
1/3
Получили оптимальное решение, т.к. все коэффициенты положительны.
Следовательно Q=35; x5=x6= x3=x4=x8=0;  x1=8/3;  x2=14/3;  x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0;  x1=8/3;  x2=14/3;  x7=26/3.

Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица  1
№вар.
а1
а2
а3
b1
b2
b3
b4
b5
с11
с12
с13
9
300
700
1000
200
100
400
600
200
23
40
10
с14
с15
с21
с22
с23
с24
с25
с31
с32
с33
с34
с35
12
21
25
21
20
50
18
15
30
32
25
50
Решение:
Составим таблицу транспортной задачи.
Таблица 2
B1
B2
B3
B4
B5
a
A1
23
40
10
12
21
300
A2
25
21
20
50
18
700
A3
15
30
32
25
50
1000
b
200
100
200
600
200
Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
B1
B2
B3
B4
B5
В6
a
A1
 300
23
40
10
12
21
0
300
A2
100
200
200
200
25
21
20
50
18
0
700
A3
200
300
500
15
30
32
25
50
0
1000
b
200
100
200
600
200
700
2000
Это будет опорный план.
Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3  ___
Таблица 4
B1
B2
B3
B4
B5
В6
a
A1
 300
 300
23
40
10
12
21
0
A2

100
200
 
200
200
700
25
21
20
50
18
0
A3
200
300
500
1000 
15
30
32
25
50
0
b
200
100
200
600
200
700
2000
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
Таблица  5
β1=2
β2=8
β3=7
β4=12
β5=6
β6=-13
a
α1=0
 300
 300
23-2>0
40-8>0
10-7>0
12-12=0
21-6>0
0-(-13)>0
α2=13
100
200
200
200
700
25-13-2>0
21-8-13=0
20-7-13=0
50-12-13>0
18-6-13=0
0-13+13=0
α2=13
200
300
500
1000 
15-13-2=0
30-13-8>0
32-13-7>0
25-13-2=0
50-13-6>0
0-13+13=0
b
200
100
200
600
200
700
2000
Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800
Ответ:
B1
B2
B3
B4
B5
В6
a
A1
 300
23
40
10
12
21
0
300
A2
100
200
200
200
25
21
20
50
18
0
700
A3
200
300
500
15
30
32
25
50
0
1000
b
200
100
200
600
200
700
2000

Задание 4
Задача 54
Условие:
Определить экстремум целевой функции вида
( = (11(12+(22(22+(12(1(2+(1(1+(2(2
при условиях:
       (11(1+(12(2<=>(1
          (21(1+(22(2<=>(2 .
Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
Составить функцию Лагранжа.
Получить систему неравенств в соответствии с теоремой Куна-Таккера.
Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
1.                Дать ответ с учетом условий дополняющей нежесткости.
2.                 
  №
b1
b2
c11
c12
c22
extr
a11
a12
a21
a22
p1
p2
Знаки огр.
1         2
31     
–7
–2
4
1.5
–2
min
–2
1.5
4
–3
18
9
£
³
Решение:
1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min
Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max
Ограничения g1(x) и g2(x):  _ EMBED Equation.3  ___ →_ EMBED Equation.3  ___
Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):
_ EMBED Equation.3  ___→ _ EMBED Equation.3  ___→ _ EMBED Equation.3  ___
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:
F’11 (х10, х20) = -8 < 0
F’12 (х10, х20) = -1,5
F’21 (х10, х20) = -1,5
F’22 (х10, х20) = 4
_ EMBED Equation.3  ___
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F’(x)+u1g1(x)+u2g2(x)=
=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3  ___)+u2(_ EMBED Equation.3  ___)
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
_ EMBED Equation.3  ___             i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А: 
_ EMBED Equation.3  ___
Система В:
_ EMBED Equation.3  ___
Перепишем систему А:
_ EMBED Equation.3  ___
4)Введем новые переменные
V={v1,v2}≥0;  W={w1,w2}≥0
в систему А для того, чтобы неравенства превратить в равенства:
_ EMBED Equation.3  ___   
Тогда
_ EMBED Equation.3  ___.  
Значит , система В примет вид:
_ EMBED Equation.3  ___    - это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
_ EMBED Equation.3  ___
Затем создадим псевдоцелевую функцию Y=My1+My2→min
Y’=-Y= -My1-My2→max.
Пусть свободные переменные: х1, х2, v1, v2, u1, u2;
а базисные y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
_ EMBED Equation.3  ___
_ EMBED Equation.3  ___
Решим с помощью симплекс-таблицы. Найдем опорное решение:

b
x1
x2
u1
u2
v1
v2
Y'/M
-9
-9,5
2,5
0,5
1
1
1
8,3125
1,1875
1,7813
-2,375
-4,75
-1,188
0
y1
7
8
1,5
-2
-4
-1
0
0,875
0,125
0,1875
-0,25
-0,5
-0,125
0
y2
2
1,5
-4
1,5
3
0
-1
-1,313
-0,188
-0,281
0,375
0,75
0,1875
0
w1
18
-2
1,5
0
0
0
0
1,75
0,25
0,375
-0,5
-1
-0,25
0
w2
9
-4
3
0
0
0
0
3,5
0,5
0,75
-1
-2
-0,5
0
b
y1
x2
u1
u2
v1
v2
Y'/M
-0,69
1,1875
4,2813
-1,875
-3,75
-0,188
1
0,6875
-0,188
-4,281
1
3,75
0,1875
-1
x1
0,875
0,125
0,1875
-0,25
-0,5
-0,125
0
0,0917
-0,025
-0,571
0,1333
0,025
-0,133
y2
0,688
-0,188
-4,281
1,875
3,75
0,1875
-1
0,3667
-0,1
-2,283
0,5333
2
0,1
-0,533
w1
19,75
0,25
1,875
-0,5
-1
-0,25
0
0,1833
-0,05
-1,142
0,2667
1
0,05
-0,267
w2
12,5
0,5
3,75
-1
-2
-0,5
0
0,3667
-0,1
-2,283
0,5333
2
0,1
-0,533
b
y1
x2
y2
u2
v1
v2
Y'/M
0
1
0
1
0
0
0
x1
0,967
0,1333
u1
0,367
-0,1
-2,283
0,5333
2
0,1
-0,533
w1
19,93
0,2667
w2
12,87
0,5333
Т. о,  u2=x2=y1=y2=v1=v2=0; x1=0,967; u1=0,367; w1=19,93; w2=12,87;
б) Условия дополняющей нежесткости выполняются  (u2w2=0), значит решения исходной задачи квадратичного программирования существует.
ОТВЕТ: существует.

Литература
Курс лекций Плотникова Н. В.

1. Реферат на тему Jackson Jarrell Essay Research Paper Washed OutRandall
2. Реферат на тему Анализ производственно хозяйственной деятельности ОАО Минский завод отопительного оборудования
3. Курсовая Правовое регулирование воинской обязанности граждан РФ по защите Отечества
4. Реферат на тему Presidential Power Essay Research Paper Powers of
5. Реферат Особливості розміщення продуктивних сил Закарпаття
6. Реферат на тему Декомпрессионная болезнь
7. Биография Юлленборг, Карл
8. Статья Этнические автостереотипы русских в странах Балтии
9. Реферат на тему John Wade A Character Study
10. Контрольная работа Правовая характеристика Акционерного общества