Реферат: Исследование операций

Министерствообщего и профессионального образования РФ

Южно-УральскийГосударственный Университет

Кафедра«Системы управления»

КУРСОВАЯ РАБОТАПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ

Вариант 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 -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 4 4 15 = = = 2 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 1 –1 2 3 3 3 6 3 6 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 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 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 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 + α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 y2 1,5 2 2 3 -4 -1 w1 -9 -2 3 w2 -13 -5 4 b w1 x2 u1 u2 v1 v2 Y' 48M -6M -22M -1M 9M 1M 1M y1 -40,5 5 17 -2 -5 -1 y2 -7,5 1 5 3 -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,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;

doubleh,n,a[5][7],b[5][7];

clrscr();

printf («Введитечисла матрицы А „);