Міністерство загальної та професійної освіти РФ
Кафедра «Системи управління»

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

З дослідження операцій

Варіант 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 +100 t2 +150 t3 → 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
L		6000		60		60		180
t4	400		2		3		2		400 / 2 = 200
t4		-100		-1		-1		-3
t5	250		3		1		2		250 / 3 = 83,3
t5		-150		-1,5		-1,5		-4,5
t6	350		5		2		1		350 / 5 = 70
t6		-250		-2,5		-2,5		-7,5
t7	100		2		1		3		100 / 2 = 50
t7		50		0,5		0,5		1,5

Далі змінюємо t2 і t1.

	b		t7		t2		t3
L	6000		60		-40		30
L		4000		40		80		120
t4	300		-1		2		-1		300 / 2 = 150
t4		-200		-2		-4		-6
t5	100		-1,5		-0,5		-2,5
t5		50		0,5		1		-4,5
t6	50		-2,5		-0,5		-6,5
t6		50		0,5		1		-7,5
t1	50		0,5		0,5		1,5		50 / 0,5 = 100
t1		100		1		2		1,5

	b	t7	t1	t3
L	10000	100	80	150
L
t4	100	-3	-4	-7
t4
t5	150	-1	1	-1
t5
t6	100	-2	1	-5
t6
t2	100	1	2	3
t2

Оскільки коефіцієнти при змінних в цільовій функції позитивні, отже, це оптимальне рішення.
Таким чином, t1 = t3 = 0; t2 = 100; L = 10000.
Тобто для отримання максимального прибутку варто робити тільки бензин В (100 тис. л.), при цьому виручка складе 10000 руб.
ВІДПОВІДЬ: для отримання максимального прибутку варто робити тільки бензин В (100 тис. л.), При цьому виручка складе 10000 руб.
2. Задача 2
Умова:
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції 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		0		0		4		4		15		=		=		=			2		0		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		0		0		1		0		-1		2		3		0		3		3		6		3	6		0		max

Рішення:
Вихідна система:

Цільова функція Q = x1 +3 x2 + x3 +3 x5.
Нехай х3, х4 - вільні змінні, х1, х2, х5 - базисні.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:

Q = 9 - (9/2x3-1/2x4)
Складемо симплекс-таблицю:

	b		x3		x4
Q	9		9 / 2		-1 / 2
Q		2 / 3		-5 / 6		1
x1	2		3 / 2		1 / 2		2 / 0, 5 = 4
x1		-2 / 3		5 / 6		-1
x2	7 / 3		4 / 3		0
x2		0		0		0
x5	2 / 3		-5 / 6		1 / 2		2 / 3: 1 / 2 = 4 / 3
x5		4 / 3		-5 / 3		2

Це опорне рішення, тому що вільні члени позитивні.
Оскільки коефіцієнт при х4 негативний, то це і буде дозволяє стовпець. В якості дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це х5).

	b	x3	x5
Q	29 / 3	11 / 3	1
Q
x1	4 / 3	2 / 3	-1
x1
x2	7 / 3	4 / 3	0
x2
x4	4 / 3	-5 / 3	2
x4

Оскільки коефіцієнти при змінних в цільовій функції позитивні, отже, це оптимальне рішення.
Т. о. 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
A1	15		45		30						90
A2		35		30		55		30		40	50
A2					15		35				50
A3		50		40		35		30		100	30
A3							15		15		30
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
A1	15		30		45						90
A2		35		30		55		30		40	50
A2			15				20		15		50
A3		50		40		35		30		100	30
A3							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
α1 = 0	15		30		45		0		+		90
α2 = -30		35		30		55		30		40	50
α2 = -30	+		15		+		20		15		50
α3 = -30		50		40		35		30		100	30
α3 = -30	+		+		+		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
A1	15		30		45						90
A2		35		30		55		30		40	50
A2			15				20		15		50
A3		50		40		35		30		100	30
A3							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.5 x1 +1.5 x2
Обмеження g1 (x) і g2 (x):

→

1) визначимо відносний максимум функції, для цього визначимо стаціонарну крапку (х10, х20):
2)

→

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.5 x1 +1.5 x2 + u1 (2x1-3x2-9) + u2 (5x1 +4 x2-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
Y '
y1	4,5	10	2	-2	-5	-1	0
y1
y2	1,5	2	2	3	-4	0	-1
y2
w1	-9	-2	3	0	0	0	0
w1
w2	-13	-5	4	0	0	0	0
w2

	b	w1	x2	u1	u2	v1	v2
Y '	48M	-6M	-22M	-1M	9M	1M	1M
Y '
y1	-40,5	5	17	-2	-5	-1	0
y1
y2	-7,5	1	5	3	-4	0	-1
y2
x1	4,5	-0,5	-1,5	0	0	0	0
x1
w2	9,5	-2,5	-3,5	0	0	0	0
w2

	b	w1	x2	y1	u2	v1	v2
Y '	68,25 M	-8,5 M	-30,5 M	-0,5 M	11,5 M	1,5 M	1M
Y '
u1	20,25	-2,5	-8,5	-0,5	2,5	0,5	0
u1
y2	-68,25	8,5	30,5	1,5	-11,5	-1,5	-1
y2
x1	4,5	-0,5	-1,5	0	0	0	0
x1
w2	9,58	-2,5	-3,5	0	0	0	0
w2

	b	w1	x2	y1	y2	v1	v2
Y '	0	0	0	M	M	0	0
Y '
u1	5,413043
u1
u2	5,934783
u2
x1	4,5
x1
w2	9,5
w2

Т. о, 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 ("\ nh =% 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 ();
}

Дослідження операцій 5

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

З дослідження операцій