12
Министерство Образования Российской Федерации
Южно-Уральский Государственный Университет
Кафедра Системы Управления
КУРСОВАЯ РАБОТА
по дисциплине: Исследование операций
Вариант 8
Руководитель:
Плотникова Н.В.
«___»__________2004 г.
Автор проекта:
студентка группы
ПС - 317
Куликова Мария
«___»__________2004 г.
Проект защищен
с оценкой
«___»__________2004 г.
Челябинск
2004 г.Содержание.
Задача 1………………………………………………………………….3
Задача 2………………………………………………………………….8
Задача 3…………………………………………………………………10
Задача 4…………………………………………………………………13
Задача 1 (№8)
Условие:
На производстве четырёх видов кабеля выполняется пять групп технологических операций. Нормы затрат на 1 км. кабеля данного вида на каждой из групп операций, прибыль от реализации 1 км. каждого вида кабеля, а также общий фонд рабочего времени, в течение которого могут выполняться эти операции, указаны в таблице.
Определить такой план выпуска кабеля, при котором общая прибыль от реализации изготовляемой продукции является максимальной.
|
Технологическая операция |
Нормы затрат времени на обработку 1 км кабеля вида |
Общий фонд рабочего времени (ч) |
||||
|
1 |
2 |
3 |
4 |
|||
|
Волочение |
а11 |
а12 |
а13 |
а14 |
А1 |
|
|
Наложение изоляций |
а21 |
а22 |
а23 |
а24 |
А2 |
|
|
Скручивание элементов в кабель |
а31 |
а32 |
а33 |
а34 |
А3 |
|
|
Освинцовывание |
а41 |
а42 |
а43 |
а44 |
А4 |
|
|
Испытание и контроль |
а51 |
а52 |
а53 |
а54 |
А5 |
|
|
Прибыль от реализации 1 км кабеля |
В1 |
В2 |
В3 |
В4 |
||
|
№вар. |
а11 |
а12 |
а13 |
а14 |
а21 |
а22 |
а23 |
а24 |
а31 |
а32 |
а33 |
а34 |
а41 |
|
|
1 |
1,5 |
1 |
2 |
1 |
1 |
2 |
0 |
2 |
4 |
5 |
5 |
4 |
2 |
|
|
№ вар. |
а42 |
а43 |
а44 |
а51 |
а52 |
а53 |
а54 |
А1 |
А2 |
А3 |
А4 |
5 |
||
|
1 |
1 |
4 |
0 |
1 |
2 |
1,5 |
4 |
6500 |
4000 |
11000 |
4500 |
4500 |
||
|
В1 |
В2 |
В3 |
В4 |
|
|
1 |
2 |
1,5 |
1 |
|
Решение:
Составляем математическую модель задачи:
пусть x1 -длина 1-ого кабеля (км);
x2 - длина 2-ого кабеля (км);
x3 - длина 3-ого кабеля (км);
x4 - длина 4-ого кабеля (км)
тогда целевая функция L - общая прибыль от реализации изготовляемой продукции, будет иметь следующий вид
L= В1x1 + В2x2 + В3x3 + В4x4 = x1+ 2x2 + 1,5x3 + x4 > max
Получим систему ограничений:
1,5x1 + x2 + 2x3+ x4 6500;
x1 + 2x2 + 0x3+2x4 4000;
4x1 + 5x2 + 5x3+4x4 11000;
2x1 + x2 +1,5x3+0x4 4500;
x1 + 2x2 +1,5x3+4x4 4500.
Приведём полученную математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств:
1,5x1 + x2 + 2x3+ x4 + x5 = 6500;
x1 + 2x2 + 0x3+2x4 + x6= 4000;
4x1 + 5x2 + 5x3+4x4 + x7=11000;
2x1 + x2 +1,5x3+0x4 + x8 =4500;
x1 + 2x2 +1,5x3+4x4 + x9 =4500.
Итак, выберем x1, x2, x3, x4 - свободными переменными, а x5, x6, x7, x8, x9 - базисными переменными (каждая из них встречаются в системе лишь в одном уравнении с коэффициентом 1, а в остальных с нулевыми коэффициентами). Приведём систему к стандартному виду, выразив для этого все базисные переменные через свободные:
x5 = 6500 - (1,5x1 + x2 + 2x3+ x4 );
x6 = 4000 - ( x1 + 2x2 + 0x3+2x4);
x7 =11000 - ( 4x1 + 5x2 + 5x3+4x4);
x8 =4500 - ( 2x1 + x2 +1,5x3+0x4);
x9 =4500 - ( x1 + 2x2 +1,5x3+4x4)
L=0 -(- x1- 2x2 - 1,5x3 - x4)
Решим методом симплекс-таблиц:
Это решение опорное, т.к. все свободные члены положительны.
Выберем столбец в таблице, который будет разрешающим, пусть это будет x1, выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это x8).
|
A |
||||||
|
L |
0 2250 |
-1 0,5 |
-2 0,5 |
-1,5 2 |
-1 0 |
|
|
6500 -3375 |
1,5 -0,75 |
1 -0,75 |
2 -3 |
1 0 |
||
|
4000 -2250 |
1 -0,5 |
2 -0,5 |
0 -2 |
3 0 |
||
|
11000 -9000 |
4 -2 |
5 -2 |
5 -8 |
4 0 |
||
|
x8 |
4500 2250 |
2 0,5 |
1 0,5 |
4 2 |
0 0 |
|
|
x9 |
4500 -2250 |
1 -0,5 |
2 -0,5 |
1,5 -2 |
4 0 |
|
Меняем и
|
A |
x8 |
|||||
|
L |
2250 1000 |
0,5 -1 |
-1,5 0,5 |
0,5 -1,5 |
-1 2 |
|
|
3125 -500/3 |
-0,75 1/6 |
0,25 -1/12 |
-1 0,25 |
1 -1/3 |
||
|
1750 -1000 |
-0,5 1 |
1,5 -0,5 |
-2 1,5 |
3 -2 |
||
|
2000 2000/3 |
-2 -2/3 |
3 1/3 |
-3 -1 |
4 4/3 |
||
|
2250 -1000/3 |
0,5 1/3 |
0,5 -1/6 |
2 0,5 |
0 -2/3 |
||
|
x9 |
2250 -1000 |
-0,5 1 |
1,5 -0,5 |
-0,5 1,5 |
4 -2 |
|
Меняем и x9
|
A |
x8 |
|||||
|
L |
3250 250 |
-0,5 0,5 |
0,5 -0,5 |
-1 1 |
1 2 |
|
|
8875/3 187,5 |
-7/12 0,375 |
-1/12 -0,375 |
-0,75 0,75 |
2/3 1,5 |
||
|
750 125 |
0,5 0,25 |
-0,5 -0,25 |
-0,5 0,5 |
1 1 |
||
|
2000/3 250 |
-2/3 0,5 |
1/3 -0,5 |
-1 1 |
4/3 2 |
||
|
5750/3 -625 |
5/6 -1,25 |
-1/6 1,25 |
2,5 -2,5 |
-2/3 -5 |
||
|
x9 |
250 250 |
0,5 0,5 |
-0,5 -0,5 |
1 1 |
2 2 |
|
|
A |
x8 |
x9 |
||||
|
L |
3500 |
0 |
0 |
1 |
3 |
|
|
18875/6 |
-5/24 |
-11/24 |
0,75 |
13/6 |
||
|
875 |
0,75 |
-0,75 |
0,5 |
2 |
||
|
2750/3 |
-1/6 |
-1/6 |
1 |
10/3 |
||
|
3875/3 |
-5/12 |
13/12 |
-2,5 |
-17/3 |
||
|
250 |
0,5 |
-0,5 |
1 |
2 |
||
Видим, что коэффициенты при переменных в целевой функции положительны, значит, найденное решение будет оптимальным.
Итак, =0, =3875/3, =2750/3, =250, L=3500.
Ответ: если предприятие будет изготавливать только три вида проволоки 1,2,3 причем 3875/3 км, 2750/3 км, 250 км соответственно, то общая прибыль от реализации изготовляемой продукции будет максимальной и равной 3500(ед).
Задача 2 (№28)
Условие:
С помощью симплекс-таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции 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 |
|||
|
1 |
2 |
3 |
|||||||||||||||
|
28 |
-6 |
0 |
-1 |
-1 |
0 |
8 |
= |
= |
= |
4 |
1 |
1 |
2 |
||||
|
№ вар. |
a15 |
a16 |
a21 |
a22 |
a23 |
a24 |
a25 |
a26 |
a31 |
a32 |
a33 |
a34 |
a35 |
a36 |
Тип экстрем. |
|
|
34 |
1 |
0 |
2 |
-1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
max |
|
Решение:
Получим систему:
4 x1 + x2 + x3+2x4 + x5 =8;
2x1 - x2 +x4=2;
x1 + x2+x5=3
L= -6x1+ x3 -x4 -x5 > max
Пусть x2, x4 - свободные переменные, а x1, x3, x5 - базисные переменные. Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
x5 =2-(1,5x2 -0,5 x4);
x3 =6-(1,5x2 +0,5 x4);
x1=1-(-0,5x2+0,5x4)
L=-2-(3x2- x4) > max
Составим симплекс-таблицу:
Выберем разрешающим столбцом x4,т.к. только перед этой переменной в целевой функции отрицательное число, выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это x1). Меняем x4 и x1
|
b |
x2 |
x4 |
|||
|
L |
-2 2 |
3 -1 |
-1 2 |
||
|
x1 |
1 2 |
-0,5 -1 |
0,5 2 |
1/0,5=2 |
|
|
6 -1 |
1,5 0,5 |
0,5 -1 |
6/0,5=12 |
||
|
2 1 |
1,5 -0,5 |
-0,5 1 |
|||
|
b |
x2 |
x1 |
||
|
L |
0 |
2 |
2 |
|
|
x4 |
2 |
-1 |
2 |
|
|
5 |
2 |
-1 |
||
|
3 |
1 |
1 |
||
Получили оптимальное решение, т.к. все коэффициенты положительны.
Итак, x1= x2=0, x3 =5, x4=2, x5 =3, L=0.
Ответ: x1= x2=0, x3 =5, x4=2, x5 =3, L=0.
Задача 3 (№8)
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
|
№вар. |
а1 |
а2 |
а3 |
1 |
2 |
3 |
4 |
5 |
с11 |
с12 |
с13 |
|
|
8 |
200 |
200 |
600 |
200 |
300 |
200 |
100 |
200 |
25 |
21 |
20 |
|
|
с14 |
с15 |
с21 |
с22 |
с23 |
с24 |
с25 |
с31 |
с32 |
с33 |
с34 |
с35 |
|
|
50 |
18 |
15 |
30 |
32 |
25 |
40 |
23 |
40 |
10 |
12 |
21 |
|
Решение:
Составим таблицу транспортной задачи. Заполним таблицу методом северо-западного угла:
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
||
|
A1 |
25 200 |
21 |
20 |
50 |
18 |
200 |
|
|
A2 |
15 |
30 200 |
32 |
25 |
40 |
200 |
|
|
A3 |
23 |
40 100 |
10 200 |
12 100 |
21 200 |
600 |
|
|
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
|
Количество заполненных ячеек r=m+n-1=6.
Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток:
r =6, ai= bj=1000, всё выполняется, значит, найденный план является опорным.
L=25*200+30*200+40*100+10*200+12*100+21*200=22400
Постараемся улучшить план перевозок.
1) Рассмотрим цикл (1;1)-(1;2)-(2;2)-(2;1)
Подсчитаем цену цикла: j=15-30+21-25=-19<0
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
||
|
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
|
|
A2 |
15 200 |
30 |
32 |
25 |
40 |
200 |
|
|
A3 |
23 |
40 100 |
10 200 |
12 100 |
21 200 |
600 |
|
|
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
|
L=21*200+15*200+40*100+10*200+12*100+21*200=18600
2) Рассмотрим цикл (2;1)-(2;2)-(3;2)-(3;1)
j=-15+30+23-40=-2<0
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
||
|
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
|
|
A2 |
15 100 |
30 100 |
32 |
25 |
40 |
200 |
|
|
A3 |
23 100 |
40 |
10 200 |
12 100 |
21 200 |
600 |
|
|
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
|
L=21*200+15*100+30*100+23*100+10*200+12*100+21*200=18400
Проверим методом потенциалов:
Примем б1=0, тогда вj = cij - бi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Дij = cij - (бi+ вj) ? 0
Очевидно, что Дij =0 для заполненных клеток.
В результате получим следующую таблицу:
|
B1=6 |
B2=21 |
B3=-7 |
B4=-5 |
B5=4 |
ai |
||
|
A1=0 |
25-6>0 |
21-21=0 200 |
20+7>0 |
50+5>0 |
18-4>0 |
200 |
|
|
A2=9 |
15-9-6=0 100 |
30-21-9=0 100 |
32-9+7>0 |
25+5-9>0 |
40-4-9>0 |
200 |
|
|
A3=17 |
23-17-6=0 100 |
40-21-17>0 |
10+7-17=0 200 |
12+5-17=0 100 |
21-4-17=0 200 |
600 |
|
|
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
|
Таким образом, решение верное, т.к. Дij > 0 для всех пустых клеток и Дij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=18400
Ответ:
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
||
|
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
|
|
A2 |
15 100 |
30 100 |
32 |
25 |
40 |
200 |
|
|
A3 |
23 100 |
40 |
10 200 |
12 100 |
21 200 |
600 |
|
|
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
|
Задача 4 (№53)
Условие:
Определить экстремум целевой функции вида
= 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 |
||
|
53 |
6 |
1,5 |
-2 |
-4 |
-1 |
max |
2,5 |
-1 |
3 |
2,5 |
7 |
13 |
|||
Решение:
Целевая функция:
F= -212-22-412+61+1,52>max
Ограничения g1(x) и g2(x): 2,51-27 2,51-2-70
31+2,5213 31+2,52-130
1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):
>
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции
F11 (х10, х20) = -4 < 0
F12 (х10, х20)=-4
F21 (х10, х20)=-4
F22 (х10, х20)=-2
F11 F12 -4 -4
F21 F22 -4 -2
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F(x)+u1g1(x)+u2g2(x)=-212-22-412+61+1,52+u1 (2,51-2-7)+ u2 (31+2,52-13).
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А:
Система В:
Перепишем систему А:
6-41-42+2,5u1+3u2 <0
1,5-41-22-u1+2,5u2 <0
2,51-2-70
31+2,52-130
4)Введем новые переменные
V={v1,v2}?0; W={w1,w2}?0
в систему А для того, чтобы неравенства превратить в равенства:
6-41-42+2,5u1+3u2 + v1=0
1,5-41-22-u1+2,5u2 + v2=0
2,51-2-7- w1=0
31+2,52-13- w2=0
Тогда
- v1=6-41-42+2,5u1+3u2
- v2=1,5-41-22-u1+2,5u2
w1=2,51-2-7
w2=31+2,52-13
Следовательно, система В примет вид:
- это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
6-41-42+2,5u1+3u2 + v1 -y1=0
1,5-41-22-u1+2,5u2 + v2 -y2=0
2,51-2-7- w1=0
31+2,52-13- w2=0
и создадим псевдоцелевую функцию Y=My1+My2>min
Y=-Y= -My1-My2>max.
В качестве свободных выберем х1, х2, v1, v2, u1, u2;
а в качестве базисных y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
y1=6-(41+42-2,5u1-3u2 - v1)
y2=1,5-(41+22+u1-2,5u2 -v2)
w1=-7-(-2,51+2)
w2=-13-(-31-2,52)
Y=-Y=-My1-My2=-7,5M-(-81-62+1,5u1+5,5u2+ v1+v2) M
Решим с помощью симплекс-таблицы. Найдем опорное решение:
|
-7,5M 4,5M |
-8M 12M |
-6M 3M |
1,5M 3M |
5,5M -7,5M |
M 0 |
M -3M |
||
|
6 -3 |
4 -8 |
4 -2 |
-2,5 -2 |
-3 5 |
-1 0 |
0 2 |
||
|
1,5 3/4 |
4 2 |
2 0,5 |
1 0,5 |
-2,5 -5/4 |
0 0 |
-1 -0,5 |
||
|
-7 -3/4 |
-2,5 -2 |
1 -0,5 |
0 -0,5 |
0 5/4 |
0 0 |
0 0,5 |
||
|
-13 15/8 |
-3 5 |
-2,5 5/4 |
0 5/4 |
0 -25/16 |
0 0 |
0 -5/4 |
||
Меняем и
|
-3M 3M |
4M -4M |
3M -2M |
4,5M -4,5M |
-2M M |
M -M |
-2M 2M |
||
|
3 3/2 |
-4 -2 |
-2 -1 |
-4,5 -9/4 |
2 0,5 |
-1 -0,5 |
2 1 |
||
|
3/4 15/8 |
2 -2,5 |
0,5 -5/4 |
0,5 -45/16 |
-5/4 5/8 |
0 -5/8 |
-0,5 5/4 |
||
|
-31/4 -15/8 |
-4,5 2,5 |
-0,5 5/4 |
-0,5 45/16 |
5/4 -5/8 |
0 5/8 |
0,5 -5/4 |
||
|
-89/8 75/32 |
2 -25/8 |
5/4 -25/16 |
5/4 -225/64 |
-25/16 25/32 |
0 -25/32 |
-5/4 25/16 |
||
Меняем и
|
0 0 |
0 0 |
M 0 |
0 0 |
M 0 |
0 0 |
0 0 |
||
|
3/2 77/8 |
-2 -1 |
-1 -3/4 |
-9/4 -37/16 |
0,5 5/8 |
-0,5 -5/8 |
1 3/4 |
||
|
21/8 77/32 |
-0,5 -1/4 |
-3/4 -3/16 |
-37/16 -37/64 |
5/8 5/32 |
-5/8 -5/32 |
3/4 -3/16 |
||
|
-77/8 77/16 |
-2 -0,5 |
3/4 -3/8 |
37/16 -37/32 |
-5/8 5/16 |
5/8 -5/16 |
-3/4 3/8 |
||
|
-281/32 693/128 |
-9/8 -9/16 |
-5/16 -27/64 |
-145/64 -333/256 |
25/32 45/128 |
-25/32 -45/128 |
5/16 27/64 |
||
Меняем и
|
0 0 |
0 0 |
M 0 |
0 0 |
M 0 |
0 0 |
0 0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
89/8 431/18 |
-1 -16/9 |
-7/4 |
-73/16 |
9/8 |
-9/8 |
7/4 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
161/32 431/72 |
-1/4 -4/9 |
-15/16 |
-185/64 |
25/32 |
-25/32 |
9/16 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
77/16 431/36 |
-0,5 -8/9 |
-3/8 |
-37/32 |
5/16 |
-5/16 |
3/8 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
-431/32 431/18 |
< p align="left">-9/16
-16/9
Меняем и
Итак, =====, =16,785, =11,017, =23,944, =35,07 6) Условия дополняющей нежесткости выполняются ,значит, решения исходной задачи квадратичного программирования существует. Ответ: существует. Литература.
1) Курс лекций Плотникова Н.В. 2) Пантелеев А.В., Летова Т.А. «Методы оптимизации в примерах и задачах». |
| Контрольная работа | Концепция информатизации Российской Федерации |
| Контрольная работа | Причины агрессивного поведения. Методы работы с агрессивными детьми |
| Контрольная работа | Алгоритм выбора и реализации предпринимательской идеи |
| Контрольная работа | Системы управления взаимоотношения с клиентами |
| Контрольная работа | Учет материальных затрат в бухгалтерском учете |
| Контрольная работа | Геополитическое положение России |
| Контрольная работа | Особенности вознаграждения работников в организации |
| Контрольная работа | Виды запасов |
| Контрольная работа | Психоанализ |
| Контрольная работа | Экономико-географическая характеристика Печорского угольного бассейна 2 |
| Контрольная работа | Расчет искусственного освещения |
| Контрольная работа | Официально-деловой стиль и сфера его функционирования |
| Контрольная работа | Методы научного познания. Развитие научного знания. Эволюция вселенной |
| Контрольная работа | Проблемы незаконной иммиграции в России |
| Контрольная работа | Политический режим |