Министерство Образования Российской Федерации
Южно-Уральский Государственный Университет
Кафедра Системы Управления
КУРСОВАЯ РАБОТА
по дисциплине: Исследование операций
Вариант 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,
где CT = [ c1 c2 . ............
