Министерство общего и профессионального образования РФ
Южно-Уральский Государственный Университет
Кафедра «Системы управления»
КУРСОВАЯ РАБОТА
ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ
Вариант 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 |
| 1 | 400 | 250 | 350 | 100 | 120 | 100 | 150 | 2 | 3 | 5 | 2 | 3 | 1 |
| № вар. | b1 | b2 | c1 | c2 | c3 | c4 |
| 1 | 2 | 1 | 2 | 2 | 1 | 3 |
Решение:
Составим математическую модель задачи.
Обозначим через 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 | 0 | -120 | -100 | -150 | |||
| 6000 | 60 | 60 | 180 | ||||
| t4 | 400 | 2 | 3 | 2 | 400/2=200 | ||
| -100 | -1 | -1 | -3 | ||||
| t5 | 250 | 3 | 1 | 2 | 250/3=83,3 | ||
| -150 | -1,5 | -1,5 | -4,5 | ||||
| t6 | 350 | 5 | 2 | 1 | 350/5=70 | ||
| -250 | -2,5 | -2,5 | -7,5 | ||||
| t7 | 100 | 2 | 1 | 3 | 100/2=50 | ||
| 50 | 0,5 | 0,5 | 1,5 | ||||
Далее меняем t2 и t1 .
| b | t7 | t2 | t3 | ||||
| L | 6000 | 60 | -40 | 30 | |||
| 4000 | 40 | 80 | 120 | ||||
| t4 | 300 | -1 | 2 | -1 | 300/2=150 | ||
| -200 | -2 | -4 | -6 | ||||
| t5 | 100 | -1,5 | -0,5 | -2,5 | |||
| 50 | 0,5 | 1 | -4,5 | ||||
| t6 | 50 | -2,5 | -0,5 | -6,5 | |||
| 50 | 0,5 | 1 | -7,5 | ||||
| t1 | 50 | 0,5 | 0,5 | 1,5 | 50/0,5=100 | ||
| 100 | 1 | 2 | 1,5 | ||||
| b | t7 | t1 | t3 | ||||
| L | 10000 | 100 | 80 | 150 | |||
| t4 | 100 | -3 | -4 | -7 | |||
| t5 | 150 | -1 | 1 | -1 | |||
| t6 | 100 | -2 | 1 | -5 | |||
| t2 | 100 | 1 | 2 | 3 | |||
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Таким образом, t1 = t3 =0; t2=100; L=10000.
Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.
ОТВЕТ: для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.
Задача 2
№34
Условие:
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции 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 | с6 | b1 | b2 | b3 | Знаки ограничений | a11 | a12 | a13 | a14 | ||||||||||||||||||
| 1 | 2 | 3 | ||||||||||||||||||||||||||||||
| 34 | 3 | 3 | 1 | 1 | 0 | 0 | 4 | 4 | 15 | = | = | = | 2 | 0 | 3 | 1 | ||||||||||||||||
| № вар. | a15 | a16 | a21 | a22 | a23 | a24 | a25 | a26 | a31 | a32 | a33 | a34 | a35 | a36 | Тип экстрем. | |||||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||||||||||||||||||
| 1. 34 | 0 | 0 | 1 | 0 | –1 | 2 | 3 | 0 | 3 | 3 | 6 | 3 | 6 | 0 | max | |||||||||||||||||
Решение:
Исходная система:
Целевая функция Q= x1+3x2+x3+3x5.
Пусть х3, х4 – свободные переменные, х1, х2, х5 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q=9 - (9/2x3-1/2x4)
Составим симплекс-таблицу:
| b | x3 | x4 | |||
| Q | 9 | 9/2 | -1/2 | ||
| 2/3 | -5/6 | 1 | |||
| x1 | 2 | 3/2 | 1/2 | 2/0,5=4 | |
| -2/3 | 5/6 | -1 | |||
| x2 | 7/3 | 4/3 | 0 | ||
| 0 | 0 | 0 | |||
| x5 | 2/3 | -5/6 | 1/2 | 2/3 : 1/2=4/3 | |
| 4/3 | -5/3 | 2 | |||
Это опорное решение, т.к. свободные члены положительны.
Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это х5).
| b | x3 | x5 | |||
| Q | 29/3 | 11/3 | 1 | ||
| x1 | 4/3 | 2/3 | -1 | ||
| x2 | 7/3 | 4/3 | 0 | ||
| x4 | 4/3 | -5/3 | 2 | ||
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Т. о. 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 | b1 | b2 | b3 | b4 | b5 | с11 | с12 | с13 |
| 14 | 90 | 50 | 30 | 15 | 45 | 45 | 50 | 15 | 45 | 60 | 40 |
| с14 | с15 | с21 | с22 | с23 | с24 | с25 | с31 | с32 | с33 | с34 | с35 |
| 60 | 95 | 35 | 30 | 55 | 30 | 40 | 50 | 40 | 35 | 30 | 100 |
Решение:
Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:
| B1 | B2 | B3 | B4 | B5 | a | ||||||
| A1 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 45 | 30 | |||||||||
| A2 | 35 | 30 | 55<
/td>
30 |
40 |
50 |
| |||||
| 15 | 35 | ||||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 15 | 15 | ||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Это будет опорный план.
Количество заполненных ячеек 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 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 30 | 45 | |||||||||
| A2 | 35 | 30 | 55 | 30 | 40 | 50 | |||||
| 15 | 20 | 15 | |||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 30 | |||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
| β1=45 | β2=60 | β3=40 | β4=60 | β5=70 | ||||||
| α1=0 | 45 | 60 | 40 | 60 | 95 | 90 | ||||
| 15 | 30 | 45 | 0 | + | ||||||
| α2= -30 | 35 | 30 | 55 | 30 | 40 | 50 | ||||
| + | 15 | + | 20 | 15 | ||||||
| α3= -30 | 50 | 40 | 35 | 30 | 100 | 30 | ||||
| + | + | + | 30 | + | ||||||
| 15 | 45 | 45 | 50 | 15 | 170 | |||||
Δ1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.
Таким образом, решение верное, т.к. Δij ≥0.
ОТВЕТ:
| B1 | B2 | B3 | B4 | B5 | a | ||||||
| A1 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 30 | 45 | |||||||||
| A2 | 35 | 30 | 55 | 30 | 40 | 50 | |||||
| 15 | 20 | 15 | |||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 30 | |||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Задача 4
№59
Условие:
Определить экстремум целевой функции вида
F = c11x12+c22x22+c12x1x2+b1x1+b2x2
при условиях
a11x1+a12x2<=>p1
a21x1+a22x2<=>p2 .
1. Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
2. Составить функцию Лагранжа.
3. Получить систему неравенств в соответствии с теоремой Куна-Таккера.
4. Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
5. Дать ответ с учетом условий дополняющей нежесткости.
| № | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 | Знаки огр. 1 2 |
|
| 59 | 4.5 | 1.5 | –5 | –2 | –1 | max | 2 | –3 | 5 | 4 | 9 | 13 | ³ | ³ |
Решение:
Целевая функция: F=-5x12-x22-2x1x2+4.5x1+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)=
=-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.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Решим с помощью симплекс-таблицы. Найдем опорное решение:
Примечание: вычисления производились программно, см Приложение
| b | x1 | x2 | u1 | u2 | v1 | v2 | |||||||
| Y' | -6M | -12M | -4M | -M | 9M | M | M | ||||||
| y1 | 4,5 | 10 | 2 | -2 | -5 | -1 | 0 | ||||||
| y2 | 1,5 | 2 | 2 | 3 | -4 | 0 | -1 | ||||||
| w1 | -9 | -2 | 3 | 0 | 0 | 0 | 0 | ||||||
| w2 | -13 | -5 | 4 | 0 | 0 | 0 | 0 | ||||||
| b | w1 | x2 | u1 | u2 | v1 | v2 | |||||||
| Y' | 48M | -6M | -22M | -1M | 9M | 1M | 1M | ||||||
| y1 | -40,5 | 5 | 17 | -2 | -5 | -1 | 0 | ||||||
| y2 | -7,5 | 1 | 5 | 3 | -4 | 0 | -1 | ||||||
| x1 | 4,5 | -0,5 | -1,5 | 0 | 0 | 0 | 0 | ||||||
| w2 | 9,5 | -2,5 | -3,5 | 0 | 0 | 0 | 0 | ||||||
| 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 | 0 | ||||||
| y2 | -68,25 | 8,5 | 30,5 | 1,5 | -11,5 | -1,5 | -1 | ||||||
| x1 | 4,5 | -0,5 | -1,5 | 0 | 0 | 0 | 0 | ||||||
| w2 | 9,58 | -2,5 | -3,5 | 0 | 0 | 0 | 0 | ||||||
| b | w1 | x2 | y1 | y2 | v1 | v2 | |||||||
| Y' | 0 | 0 | 0 | M | M | 0 | 0 | ||||||
| u1 | 5,413043 | ||||||||||||
| u2 | 5,934783 | ||||||||||||
| x1 | 4,5 | ||||||||||||
| w2 | 9,5 | ||||||||||||
Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413043; u2=5,934783; x1=4.5; w2=9.5.
б) Условия дополняющей нежесткости не выполняются (u2w2≠0), значит решения исходной задачи квадратичного программирования не существует.
ОТВЕТ: не существует.
Приложение
#include <math.h>
#include <stdio.h>
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();
}