Исследование операций
Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В результате смешивания этих четырех компонентов в разных пропорциях образуется три сорта авиационного бензина: бензин, А (а1:а2:а3:а4), бензин В (b1:b2:b3:b4) и бензин С (с1:с2:с3:с4). Т. к. все коэффициенты в целевой функции… Читать ещё >
Исследование операций (реферат, курсовая, диплом, контрольная)
Министерство общего и профессионального образования РФ Южно-Уральский Государственный Университет Кафедра «Системы управления»
КУРСОВАЯ РАБОТА
ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ
Вариант 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 | |
№ вар. | b1 | b2 | c1 | c2 | c3 | c4 | |
Решение:
Составим математическую модель задачи.
Обозначим через 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 | — 120 | — 100 | — 150 | |||||||
t4 | 400/2=200 | |||||||||
— 100 | — 1 | — 1 | — 3 | |||||||
t5 | 250/3=83,3 | |||||||||
— 150 | — 1,5 | — 1,5 | — 4,5 | |||||||
t6 | 350/5=70 | |||||||||
— 250 | — 2,5 | — 2,5 | — 7,5 | |||||||
t7 | 100/2=50 | |||||||||
0,5 | 0,5 | 1,5 | ||||||||
Далее меняем t2 и t1 .
b | t7 | t2 | t3 | |||||||
L | — 40 | |||||||||
t4 | — 1 | — 1 | 300/2=150 | |||||||
— 200 | — 2 | — 4 | — 6 | |||||||
t5 | — 1,5 | — 0,5 | — 2,5 | |||||||
0,5 | — 4,5 | |||||||||
t6 | — 2,5 | — 0,5 | — 6,5 | |||||||
0,5 | — 7,5 | |||||||||
t1 | 0,5 | 0,5 | 1,5 | 50/0,5=100 | ||||||
1,5 | ||||||||||
b | t7 | t1 | t3 | ||||||
L | |||||||||
t4 | — 3 | — 4 | — 7 | ||||||
t5 | — 1 | — 1 | |||||||
t6 | — 2 | — 5 | |||||||
t2 | |||||||||
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Таким образом, t1 = t3 =0; t2=100; L=10 000.
Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10 000 руб.
ОТВЕТ: для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10 000 руб.
Задача 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 | |||
= | = | = | |||||||||||||||
№ вар. | a15 | a16 | a21 | a22 | a23 | a24 | a25 | a26 | a31 | a32 | a33 | a34 | a35 | a36 | Тип экстрем. | ||
— 1 | max | ||||||||||||||||
Решение:
Исходная система:
Целевая функция Q= x1+3×2+x3+3×5.
Пусть х3, х4 — свободные переменные, х1, х2, х5 — базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q=9 — (9/2×3−½×4)
Составим симплекс-таблицу:
b | x3 | x4 | ||||||
Q | 9/2 | — ½ | ||||||
2/3 | — 5/6 | |||||||
x1 | 3/2 | ½ | 2/0,5=4 | |||||
— 2/3 | 5/6 | — 1 | ||||||
x2 | 7/3 | 4/3 | ||||||
x5 | 2/3 | — 5/6 | ½ | 2/3: ½=4/3 | ||||
4/3 | — 5/3 | |||||||
Это опорное решение, т.к. свободные члены положительны.
Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это х5).
b | x3 | x5 | |||||
Q | 29/3 | 11/3 | |||||
x1 | 4/3 | 2/3 | — 1 | ||||
x2 | 7/3 | 4/3 | |||||
x4 | 4/3 | — 5/3 | |||||
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Т. о. 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 | с11 | с12 | с13 | ||||||
с14 | с15 | с21 | с22 | с23 | с24 | с25 | с31 | с32 | с33 | с34 | с35 | |
Решение:
Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:
B1 | B2 | B3 | B4 | B5 | a | |||||||
A1 | ||||||||||||
A2 | ||||||||||||
A3 | ||||||||||||
b | ||||||||||||
Это будет опорный план.
Количество заполненных ячеек 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 | ||||||||||||
A2 | ||||||||||||
A3 | ||||||||||||
b | ||||||||||||
Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.
Проверим методом потенциалов:
Примем б1=0, тогда вj = cij — бi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Дij = cij — (бi+ вj)? 0
Очевидно, что Дij =0 для заполненных клеток.
В результате получим следующую таблицу:
в1=45 | в2=60 | в3=40 | в4=60 | в5=70 | ||||||||
б1=0 | ||||||||||||
б2= -30 | ||||||||||||
б3= -30 | ||||||||||||
Д1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.
Таким образом, решение верное, т.к. Дij ?0.
ОТВЕТ:
B1 | B2 | B3 | B4 | B5 | a | |||||||
A1 | ||||||||||||
A2 | ||||||||||||
A3 | ||||||||||||
b | ||||||||||||
Задача 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 | ||
4.5 | 1.5 | — 5 | — 2 | — 1 | max | — 3 | |||||||||
Решение:
Целевая функция: F=-5×12-x22−2x1x2+4.5×1+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)=
=-5×12-x22−2x1x2+4.5×1+1.5×2+u1(2×1−3×2−9)+u2(5×1+4×2−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 | — 2 | — 5 | — 1 | |||||||||||
y2 | 1,5 | — 4 | — 1 | ||||||||||||
w1 | — 9 | — 2 | |||||||||||||
w2 | — 13 | — 5 | |||||||||||||
b | w1 | x2 | u1 | u2 | v1 | v2 | |||||||||
Y' | 48M | — 6M | — 22M | — 1M | 9M | 1M | 1M | ||||||||
y1 | — 40,5 | — 2 | — 5 | — 1 | |||||||||||
y2 | — 7,5 | — 4 | — 1 | ||||||||||||
x1 | 4,5 | — 0,5 | — 1,5 | ||||||||||||
w2 | 9,5 | — 2,5 | — 3,5 | ||||||||||||
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 | |||||||||
y2 | — 68,25 | 8,5 | 30,5 | 1,5 | — 11,5 | — 1,5 | — 1 | ||||||||
x1 | 4,5 | — 0,5 | — 1,5 | ||||||||||||
w2 | 9,58 | — 2,5 | — 3,5 | ||||||||||||
b | w1 | x2 | y1 | y2 | v1 | v2 | |||||||||
Y' | M | M | |||||||||||||
u1 | 5,413 043 | ||||||||||||||
u2 | 5,934 783 | ||||||||||||||
x1 | 4,5 | ||||||||||||||
w2 | 9,5 | ||||||||||||||
Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413 043; u2=5,934 783; x1=4.5; w2=9.5.
б) Условия дополняющей нежесткости не выполняются (u2w2?0), значит решения исходной задачи квадратичного программирования не существует.
ОТВЕТ: не существует.
Приложение
#include
#include
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 ();
}