Исследование операций

Министерство образования и науки Российской Федерации

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

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









Курсовая работа

по дисциплине: исследование операций

Вариант 9









_



























Челябинск

2004 г.
Содержание



Задание 1										3

Задание 2										6

Задание 3										9

Задание 4									11

Литература									17


Задание 1



Задача 9

Условие:

Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее  a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.

Вещество

Количество единиц вещества, содержащегося в 1 кг сырья



1

2

3

А

d11

d12

d13

В

d21

d22

d23

С

d31

d32

d33

Цена 1 кг сырья

D1

D2

D3



№ вар.

d11

d12

d13

d21

d22

d23

d31

d32

d33

9

1

1

0

2

0

3

1

2

4



D1

D2

D3

а

b

c

5

6

7

26

30

24



Решение:

Составим математическую модель задачи.

Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно. 

Тогда, целевая функция будет

L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min

Система ограничений:

_ EMBED Equation.3  ___

Приведем систему ограничений к  виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные  n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.

L’=0-(5n1+ 6n2+7n3) →max

_ EMBED Equation.3  ___

Выберем n1, n2, n3 свободными переменными, а  n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:

L’=0-(5n1+ 6n2+7n3)

_ EMBED Equation.3  ___

Составим симплекс-таблицу.

Это решение не опорное, т.к. свободные члены не положительны.

Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца). 

Таблица 1.1

 

b

n1

n2

n3



L’

0

 

5

 

6

 

7

 





 

-75

 

2,5

 

0

 

-8



n4

-26

 

-1

 

-1

 

0

 

26/1=26



 

15



-1

 

0

 

1,5



n5

-30



-2

 

0

 

-3

 

30/2=15min



 

15

 

-1

 

0

 

1,5



n6

-24

 

-1

 

-2

 

-4

 

24/1=24



 

15

 

-1

 

0

 

1,5





Меняем n1 и n5.

Таблица 1.2

 

b

n5

n2

n3



L’

-75

 

2,5

 

6

 

-0,5

 





 

-45

 

5

 

-10

 

25



n4

-11



-0,5

 

-1



1,5

 

11/0,5=22



 

9

 

-1



2

 

-5



n1

15

 

-0,5

 

0

 

1,5

 





 

9

 

-1

 

2

 

-5



n6

-9



-0,5

 

-2



-2,5

 

9/0,5=18min



 

18

 

-2

 

4

 

5





Меняем n5 и n6.

Таблица 1.3

 

b

n6

n2

n3

L’

-120

 

5



-4

 

25

 



 

-10



5

 

5

 

-18

n4

-2



-1



1

 

-4

 



 

2



-1

 

-1



2,5

n1

24

 

-1

 

2

 

-3

 



 

2

 

-1

 

-1

 

3,5

n5

18

 

-2



4

 

5

 



 

4

 

-2

 

-2

 

7



Меняем n4 и n6.



Таблица 1.4

 

b

n4

n2

n3

L’

-130

 

5

 

1

 

7

 



 

 

 

 

 

 



 

n6

2

 

-1

 

-1

 

3,5

 



 

 

 

 

 

 

 

 

n1

26

 

-1

 

-1

 

0

 



 

 

 

 

 

 

 

 

n5

22

 

-2

 

2

 

12

 



 

 

 

 

 

 

 

 



Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.

Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.

Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.

Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.


Задание 2



Задача 29

Условие:

Решение задачи линейного программирования.

С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции 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





















29

0

5

1

–1

1

0

2

2

10



Знаки ограничений

a11

a12

a13

a14

1

2

3













 

–1

1

1

0



a15

a16

a21

a22

a23

a24

a25

a26

0

0

1

–2

0

1

0

0



a31

a32

a33

a34

a35

a36

Тип экстрем.

2

1

1

1

2

0

max



Решение:

Составим систему:

_ EMBED Equation.3  ___

Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max 

Приведем систему ограничений к виду основной задачи линейного программирования.

_ EMBED Equation.3  ___

Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

Q= 0-(-5x2-x3 +x4- x5)

_ EMBED Equation.3  ___

Составим симплекс-таблицу:

Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.

Таблица 2.1



 

b

x1

x2

x3

x4

x5



Q

0

 

0

 

-5

 

-1

 

1

 

-1

 





 

10

 

-5

 

5

 

5

 

0

 

0



x6

2

 

-1

 

1

 

1



0

 

0

 

2/1=2min



 

2

 

-1

 

1



1

 

0

 

0



x7

2

 

1

 

-2

 

0

 

1

 

0

 





 

4

 

-2

 

2

 

2

 

0

 

0



x8

10

 

2

 

1

 

1



1

 

2

 

10/2=5



 

-2

 

1

 

-1

 

-2

 

0

 

0





Меняем x2 и x6.

Таблица 2.2

 

b

x1

x6

x3

x4

x5

Q

10

 

-5

 

5

 

4

 

1

 

-1

 



 

4



1,5

 

-1



-1

 

0,5



0,5

x2

2

 

-1

 

1

 

1

 

0

 

0

 



 

0

 

0

 

0

 

0

 

0

 

0

x7

6

 

-1



2

 

2



1

 

0

 



 

0

 

0

 

0

 

0

 

0



0

x8

8

 

3



-1

 

-1



1



2

 



 

4

 

6

 

-2

 

-2

 

2

 

0,5




Меняем x5 и x8.

Таблица 2.3

 

b

x1

x6

x3

x4

x8

Q

14

 

-3.5

 

4,5

 

3,5

 

1,5

 

0,5

 



 

21



5,25

 

-2,625



-2,625

 

2,625

 

2,625

x2

2

 

-1

 

1

 

1

 

0

 

0

 



 

8/3 

 

2/3

 

-1/3

 

-1/3

 

1/3

 

1/3

x7

6

 

-1



2

 

2



1



0

 



 

8/3



2/3

 

-1/3

 

-1/3

 

1/3

 

1/3

x5

4



1,5



-0,5

 

-1



0,5



0,5

 



 

8/3

 

2/3

 

-1/3

 

-1/3

 

1/3

 

1/3



Меняем x5 и x1.

Таблица 2.4



b

x5

x6

x3

x4

x8

Q

35

5,25

1,875

0,875

4,125

3,125

x2

14/3

2/3

2/3

2/3

1/3

1/3

x7

26/3

2/3

5/3

5/3

4/3

1/3

x1

8/3

2/3

-1/3

-1/3

1/3

1/3



Получили оптимальное решение, т.к. все коэффициенты положительны.

Следовательно Q=35; x5=x6= x3=x4=x8=0;  x1=8/3;  x2=14/3;  x7=26/3.

Ответ: Q=35; x5=x6= x3=x4=x8=0;  x1=8/3;  x2=14/3;  x7=26/3.


Задание 3



Задача 9

Условие:

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

1. Записать условия задачи в матричной форме.

2. Определить опорный план задачи.

3. Определить оптимальный план задачи.

4. Проверить решение задачи методом потенциалов.

Таблица  1

№вар.

а1

а2

а3

1

2

3

4

5

с11

с12

с13

9

300

700

1000

200

100

400

600

200

23

40

10



с14

с15

с21

с22

с23

с24

с25

с31

с32

с33

с34

с35

12

21

25

21

20

50

18

15

30

32

25

50



Решение:

Составим таблицу транспортной задачи. 

Таблица 2



 

B1

B2

B3

B4

B5

a

A1

 

 

 

 

 

 



23

40

10

12

21

300

A2



 



 



 



25

21

20

50

18

700

A3

 

 

 

 

 

 



15

30

32

25

50

1000

b

200

100

200

600

200

 



Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.

Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены. 

Таблица 3



 

B1

B2

B3

B4

B5

В6

a

A1

 

 

 

 300

 

 

 



23

40

10

12

21

0

300

A2



100

200

 

200

200

 



25

21

20

50

18

0

700

A3

200

 

 

300

 

500

 



15

30

32

25

50

0

1000

b

200

100

200

600

200

700

2000



Это будет опорный план.

Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3  ___

Таблица 4



 

B1

B2

B3

B4

B5

В6

a

A1

 

 

 

 300

 

 

 300



23

40

10

12

21

0



A2



100

200

 

200

200

700



25

21

20

50

18

0



A3

200

 

 

300

 

500

1000 



15

30

32

25

50

0



b

200

100

200

600

200

700

2000



Проверим методом потенциалов:

Примем α1=0, тогда βj = cij – αi (для заполненных клеток).

Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0

Очевидно, что Δij =0 для заполненных клеток.

В результате получим следующую таблицу:

Таблица  5



 

β1=2

β2=8

β3=7

β4=12

β5=6

β6=-13

a

α1=0

 

 

 

 300

 

 

 300



23-2>0

40-8>0

10-7>0

12-12=0

21-6>0

0-(-13)>0



α2=13



100

200

 

200

200

700



25-13-2>0

21-8-13=0

20-7-13=0

50-12-13>0

18-6-13=0

		0-13+13=0



α2=13

200

 

 

300

 

500

1000 



15-13-2=0

30-13-8>0

32-13-7>0

25-13-2=0

50-13-6>0

0-13+13=0



b

200

100

200

600

200

700

2000



Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.

Тогда сумма всех перевозок: 

L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800

Ответ:

 

B1

B2

B3

B4

B5

В6

a

A1

 

 

 

 300

 

 

 



23

40

10

12

21

0

300

A2



100

200

 

200

200

 



25

21

20

50

18

0

700

A3

200

 

 

300

 

500

 



15

30

32

25

50

0

1000

b

200

100

200

600

200

700

2000


Задание 4



Задача 54

Условие:

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

( = (11(12+(22(22+(12(1(2+(1(1+(2(2

при условиях:

       (11(1+(12(2<=>(1

          (21(1+(22(2<=>(2 .

Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.

Составить функцию Лагранжа.

Получить систему неравенств в соответствии с теоремой Куна-Таккера. 

Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.

Дать ответ с учетом условий дополняющей нежесткости.



  №

b1

b2

c11

c12

c22

extr

a11

a12

a21

a22

p1

p2

Знаки огр.

1         2



–7

–2

4

1.5

–2

min

–2

1.5

4

–3

18

9







Решение:

1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min

Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max

Ограничения g1(x) и g2(x):  _ EMBED Equation.3  ___ →_ EMBED Equation.3  ___

Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):

_ EMBED Equation.3  ___→ _ EMBED Equation.3  ___→ _ EMBED Equation.3  ___ 

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

F’11 (х10, х20) = -8 < 0 

F’12 (х10, х20) = -1,5

F’21 (х10, х20) = -1,5

F’22 (х10, х20) = 4

_ EMBED Equation.3  ___

Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки

3) Составляем функцию Лагранжа:

L(x,u)=F’(x)+u1g1(x)+u2g2(x)= 

=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3  ___)+u2(_ EMBED Equation.3  ___) 

Получим уравнения седловой точки, применяя теорему Куна-Таккера:

_ EMBED Equation.3  ___		i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:  

_ EMBED Equation.3  ___

Система В:

_ EMBED Equation.3  ___

Перепишем систему А:

_ EMBED Equation.3  ___

4)Введем новые переменные 

V={v1,v2}≥0;  W={w1,w2}≥0 

в систему А для того, чтобы неравенства превратить в равенства:

_ EMBED Equation.3  ___	

Тогда

_ EMBED Equation.3  ___.	

Значит , система В примет вид:

_ EMBED Equation.3  ___ 	- это условия дополняющей нежесткости.

5) Решим систему А с помощью метода искусственных переменных.

Введем переменные Y={y1; y2} в 1 и 2 уравнения системы

_ EMBED Equation.3  ___

Затем создадим псевдоцелевую функцию Y=My1+My2→min

Y’=-Y= -My1-My2→max.

Пусть свободные переменные: х1, х2, v1, v2, u1, u2; 

а базисные y1, y2, w1, w2.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

_ EMBED Equation.3  ___

_ EMBED Equation.3  ___ 

Решим с помощью симплекс-таблицы. Найдем опорное решение:





 

b

x1

x2

u1

u2

v1

v2



Y'/M

-9

 

-9,5

 

2,5

 

0,5

 

1

 

1

 

1

 





 

8,3125



1,1875

 

1,7813



-2,375

 

-4,75



-1,188

 

0



y1

7

 

8

 

1,5

 

-2

 

-4

 

-1

 

0

 





 

0,875



0,125

 

0,1875



-0,25

 

-0,5



-0,125

 

0



y2

2

 

1,5

 

-4

 

1,5

 

3

 

0

 

-1

 





 

-1,313



-0,188

 

-0,281



0,375

 

0,75



0,1875

 

0



w1

18

 

-2

 

1,5

 

0

 

0

 

0

 

0

 





 

1,75

 

0,25

 

0,375

 

-0,5

 

-1

 

-0,25

 

0



w2

9

 

-4



3

 

0



0

 

0



0

 





 

3,5

 

0,5

 

0,75

 

-1

 

-2

 

-0,5

 

0



































 

b

y1

x2

u1

u2

v1

v2



Y'/M

-0,69

 

1,1875

 

4,2813

 

-1,875

 

-3,75

 

-0,188

 

1

 





 

0,6875



-0,188

 

-4,281



1

 

3,75



0,1875

 

-1



x1

0,875

 

0,125

 

0,1875

 

-0,25

 

-0,5

 

-0,125

 

0

 





 

0,0917

 

-0,025

 

-0,571



0,1333

 

 



0,025

 

-0,133



y2

0,688

 

-0,188

 

-4,281

 

1,875

 

3,75

 

0,1875

 

-1

 





 

0,3667

 

-0,1

 

-2,283

 

0,5333

 

2

 

0,1

 

-0,533



w1

19,75



0,25



1,875

 

-0,5



-1

 

-0,25

 

0

 





 

0,1833

 

-0,05

 

-1,142

 

0,2667

 

1

 

0,05

 

-0,267



w2

12,5

 

0,5

 

3,75

 

-1



-2

 

-0,5



0

 





 

0,3667

 

-0,1

 

-2,283

 

0,5333

 

2

 

0,1

 

-0,533



































 

b

y1

x2

y2

u2

v1

v2



Y'/M

0

 

1

 

0

 

1

 

0

 

0

 

0

 





 

 





 



 

 

 

 





 

 



x1

0,967

 

 

 

 

 

0,1333

 

 

 

 

 

 

 





 



 



 



 

 

 

 





 

 



u1

0,367

 

-0,1

 

-2,283

 

0,5333

 

2

 

0,1

 

-0,533

 





 

 

 

 

 

 

 

 

 

 

 

 

 

 



w1

19,93



 



 



0,2667

 

 

 



 

 

 





 

 

 

 

 

 

 

 

 

 

 

 

 

 



w2

12,87

 

 

 





0,5333

 

 

 





 

 





 

 

 

 

 

 

 

 

 

 

 

 

 

 



Т. о,  u2=x2=y1=y2=v1=v2=0; x1=0,967; u1=0,367; w1=19,93; w2=12,87;

б) Условия дополняющей нежесткости выполняются  (u2w2=0), значит решения исходной задачи квадратичного программирования существует.

ОТВЕТ: существует.


Литература



Курс лекций Плотникова Н. В.



_PAGE  _