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

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

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

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

Вариант14

Челябинск,2004

Содержание

1. Задача 1

2. Задача 2

3. Задача 3

4. Задача 4

Приложение

1. Задача 1

Условие:

Нефтеперерабатывающийзавод получает 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. Задача2

Условие:

С помощьюсимплекс–таблиц найти решение задачи линейного программирования: определить экстремальноезначение целевой функции Q=CTx при условии Ax ³ £B,

где CT = [ c1c2… 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. Задача3

Условие:

Решениетранспортной задачи:

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. Задача4

Условие:

Определитьэкстремум целевой функции вида

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):

/>→ />→ />

3) Исследуемстационарную точку на максимум, для чего определяем выпуклость или вогнутостьфункции

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()

{

inti,j,k,m;

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