Исследование операций
11
Министерство общего и профессионального образования РФ
Южно-Уральский Государственный Университет
Кафедра «Системы управления»
КУРСОВАЯ РАБОТАПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙВариант 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, где = 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 | | | | | |
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 | Тип экстрем. | |
| | | | | | | | | | | | | | | | |
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/3x3=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 | 1 | 2 | 3 | 4 | 5 | с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 | | 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
Условие:
Определить экстремум целевой функции вида
= 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 | |
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();
}