Міністерство загальної та професійної освіти РФ
Південно-Уральський державний університет
Кафедра «Системи управління»
Курсова робота з дисципліни дослідження операцій
Варіант 4

Група ПС-317

Виконав: Гречишникова Л.А.
Перевірив: Плотнікова Н.В.
Челябінськ 2004

Зміст
ЗАВДАННЯ N1. 3
Умова. 3
Рішення. 4
Відповідь. 11
ЗАВДАННЯ N2. 12
Умова. 12
Рішення. 12
Відповідь. 14
ЗАВДАННЯ N3. 15
Умова. 15
Рішення. 15
Відповідь. 19
ЗАВДАННЯ N4. 20
Умова. 20
Рішення. 20
Відповідь. 25
Література. 26

ЗАВДАННЯ N1

Умова

На швейній фабриці «Шанель» для виготовлення чотирьох видів виробів може бути використана тканина трьох артикулів. Норми витрати тканин всіх артикулів на пошиття одного виробу наведені в таблиці. Там же зазначені наявне в розпорядженні фабрики загальна кількість тканин кожного артикулу і ціна одного виробу даного виду. Визначити, скільки виробів кожного виду повинна зробити фабрика, щоб вартість виготовленої продукції була максимальною.

Артикул тканини	Норма витрати тканини (м) на один виріб виду				Загальна кіль- кість тканини
	1	2	3	4
I	А11	А12	А13	А14	b1
II	А21	А22	А23	А24	b2
III	А31	А32	а33	а34	b3
Ціна одного виробу (грн.)	с1	с2	с3	с4

№ вар.	А11	А12	А13	А14	А21	А22	А23	А24	А31	А32	а33	а34	b1	b2	b3	с1	с2	с3	с4
1	1	0	2	1	0	1	3	2	4	2	0	4	180	210	800	9	6	4	7

Рішення

1. Виберемо елементи рішення.
За елементи рішення приймемо xi-кількість i-го товару (елементів рішень 4) i =
2. Складання системи обмежень
bj, j = маємо 3 обмеження
3. Запишемо цільову функцію.
L = max
4. Спираючись на умову завдання і на перераховані вище пункти, запишемо математичну модель задачі.

L = 9 * x1 +6 * x2 +4 * x3 +7 * x4 max
Наведемо нашу математичну модель до виду ОЗЛП за допомогою додаткових невід'ємних змінних, число яких дорівнює числу нерівностей. Бо ж маємо нерівність виду менше / одно, тодобавочние змінні вводимо в ліву частину зі знаком "+". Отримуємо наступне:
ОЗЛП
L = 9 * x1 +6 * x2 +4 * x3 +7 * x4 max
Тепер визначимося з існуванням рішення знайденої ОЗЛП. Підрахуємо число рівнянь (m) і число змінних (n), знайдемо їх різницю (k) і зробимо висновок. Отже, m = 3, n = 7, k = nm = 4. Так як число лінійно незалежних рівнянь (m) менше числа змінних (n), то система сумісна і в неї існує незліченна безліч рішень. При цьому (nm) змінною ми можемо надавати довільні значення (вільні) і решта m змінних (базисні) будемо висловлювати через вільні.
Вільні: x1, x2, x3, x4
Базисні: x5, x6, x7

L = 9 * x1 +6 * x2 +4 * x3 +7 * x4 max
опорне рішення
Так як в L коефіцієнт при x1 більше 0 і більше всіх інших коефіцієнтів при змінних, то змінну x1 будемо збільшувати. Визначимо кордон збільшення x1 наступним чином: візьмемо два рівняння з системи обмежень;
x5 =-x1-2x3-x4 +180
x7 =- 4x1-2x2-4x4 +800
Визначимо значення x1, при яких кожна із змінних x5, x7 звернеться до 0.
x5 = 0
x7 = 0
Збільшувати x1 можна до найменшого зі знайдених значень необхідно поміняти місцями змінні x1 і x5.
Нове рішення буде наступним:
Вільні: x2, x3, x4, x5 = 0
Базисні: x1, x6, x7



L = 9 * (180-2 * x3-x4-x5) +6 * x2 +4 * x3 +7 * x4 = 1620-18 * x3-9 * x4-9 * x5 +6 * x2 +4 * x3 + 7 * x4 = 1620 +6 * x2-14 * x3-2 * x4-9 * x5 max
L = 1620 +6 * x2-14 * x3-2 * x4-9 * x5 max
Так як в L коефіцієнт при x2 більше 0, то змінну x2 будемо збільшувати. Визначимо кордон збільшення x2 по вже описаній вище схемі.
x6 = 210-x2-3x3-2x4
x7 = 80-2x2 +8 x3 +4 x5
x6 = 0
x7 = 0
необхідно поміняти місцями змінні x2 і x7.
Нове рішення буде наступним:
Вільні: x7, x3, x4, x5 = 0
Базисні: x1, x6, x2




L = 1620 +6 * (40-0,5 * x7 +4 * x3 +2 * x5) -14 * x3-2 * x4-9 * x5 = 1620 +240-3 * x7 +24 * x3 +12 * x5-14 * x3-2 * x4-9 * x5 = 1860 +10 * x3-2 * x4 +3 * x5-3 * x7
L = 1860 +10 * x3-2 * x4 +3 * x5-3 * x7
Так як в L коефіцієнт при x3 більше 0, то змінну x3 будемо збільшувати. Визначимо кордон збільшення x3 по вже описаній вище схемі.
x6 = 170-2x4-7x3-2x5 +0.5 x7
x2 = 40-0.5x7 +4 x3 +2 x5
x6 = 0
x2 = 0
необхідно поміняти місцями змінні x3 і x2.
Нове рішення буде наступним:
Вільні: x7, x2, x4, x5 = 0
Базисні: x1, x6, x3




Видно, що виходить негативна базисна змінна х3, тому очевидно, що x3 збільшувати не можна. Попрацюємо з х5.
x1 = 180-2x3-x4-x5
x6 = 170-7x3-2x4-2x5 +0.5 x7
x2 = 40 +4 x3 +2 x5-0.5x7
x1 = 0
x6 = 0
x2 = 0
Бачимо, що необхідно поміняти місцями х2 і х5
Нове рішення буде наступним:
Вільні: x7, x3, x4, x2 = 0
Базисні: x1, x6, x5
x6 = 170-7x3-2x4-2x5 +0.5 x7 x5 = -40 + x2-4x3 +0.5 x7
Видно, що виходить негативна базисна змінна х5, тому очевидно, що x5 і х2 міняти не можна. Поміняємо х5 з х6.




L = 1860 +10 x3-2x4 +3 (85-3.5x3-x4-0.5x6 +0.25 x7)-3x7 = 2115-0.5x3-5x4-1.5x6-2.25x7
5. Симплекс-таблиці.

L = 9 * x1 +6 * x2 +4 * x3 +7 * x4 L = 0 - (-9 * x1-6 * x2-4 * x3-7 * x4)

	b
L

	b
L	1620	9	-6	14	2
	180	1	0	2	1
	210	0	1	3	2
	80	-4	2	-8	0

L = 0 - (-1 620 +9 x5-6x2 +14 x3 +2 x4)

	b
L

	b
L	1860	-3	3	-10	2
	180	1	0	2	1
	170	2		7	2
	40	-2		-4	0

	b
L

	b
L	2115	1.5	2.25	0.5	5
	95	-0.5	0.25	-1.5	0
	85	0.5	-0.25	3.5	1
	210	1	1	3	2

Відповідь

Якщо фабрика справить 95 штук першого виробу, 210 штук другий вироби, то вартість виробленої продукції буде максимальною і буде дорівнює 2115 одиниць.

ЗАВДАННЯ N2

Умова

Вирішити симплекс-методом задачу лінійного програмування. За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції 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).
L = 5 * x1 + x2-x3 + x4 +2 x5 max

Рішення

Наведемо дане нам умову до стандартної форми запису і отримаємо наступне
L = 0 - (-5 * x1-x2 + x3-x4-2x5) max

Бачимо, що x1, x2-вільні змінні і x3, x4, x5 - базисні; n = 5, m = 3, k = 2.
Заповнимо стандартну таблицю

	b
L
				= 2

Пояснимо дії, виконані вище за межами таблиці. Вибравши як дозволяє стовпця x2. Далі в цьому стовпці потрібно вибрати дозволяє елемент. Для цього розглянемо всі елементи даного стовпця, що мають однаковий знак зі своїм вільним членом. З них в якості дозволяє виберемо той, для якого відношення до нього вільного члена буде мінімально. Звідси зрозуміло, чому в якості роздільної рядка ми вибрали x4.

	b
L

	b
L

	b
L

	b
L	8	4.5	1
	2	0.5	1
	2 / 3	1 / 6	-1 / 3
	4 / 3	5 / 6	1 / 3

Отримане рішення задовольняє системі обмежень!

Відповідь

L * = 8
x * 4, x * 5 = 0 - вільні
- Базисні

ЗАВДАННЯ N3

Умова

Рішення транспортної задачі, всі дані наведені нижче у таблиці.

	B1	B2	B3	B4	B5	ai
A1	0.09	0.12	0.14	0.1	0.09	3000
A2	0.08	0.1	0.15	0.05	0.07	6000
A3	0.1	0.15	0.15	0.08	0.06	8000
bj	1000	8000	3000	3000	4000

Рішення

Перед тим як приступити до вирішення, підрахуємо загальна кількість запасів і загальна кількість заявок . Зрозуміло що маємо транспортну задачу з надлишком заявок . Зажадаємо, щоб всі пункти призначення були задоволені в рівній частці. При такому підході завдання зводиться до задачі з правильним балансом: необхідно виправити подані заявки, помноживши кожну на коефіцієнт
k = å ai / å bj. Розрахуємо k.
Тоді отримаємо транспортну задачу з правильним балансом.

	B1	B2	B3	B4	B5	ai
A1	0.09	0.12	0.14	0.1	0.09	3000
A2	0.08	0.1	0.15	0.05	0.07	6000
A3	0.1	0.15	0.15	0.08	0.06	8000
bj						17000

Знайдемо опорне рішення за допомогою методу північно-західного кута.
r = 3 +5-1 = 7

	B1	B2	B3	B4	B5	ai
A1			0.14	0.1	0.09	3000
A2	0.08			0.05	0.07	6000
A3	0.1	0.15				8000
bj						17000

Перевіримо суму по стовпцях, суму по рядках і кількість базисних (заповнених) клітин.
Перевірка по стовпцях:

Перевірка по рядках:

Кількість заповнених клітин одно r = 7. Знайдений план є опорним.

Постараємося поліпшити план перевезень

	B1	B2	B3	B4	B5	ai
A1			0.14	0.1	0.09	3000
A2	0.08			0.05	0.07	6000
A3	0.1	0.15				8000
bj						17000

Підрахуємо ціни виділених пунктирними прямокутниками циклів.
Цікл1
(1; 1) - (1, 2) - (2, 2) - (2; 1)
, Де ціна циклу
Цікл2
(2, 3) - (2, 4) - (3, 4) - (3, 3)

Для того щоб вартість плану зменшилася, має сенс здійснювати перевезення лише за тими циклам, ціна яких негативна. Ціна Цікла2 негативна, тому вибираємо його. Цікл1 в даному випадку розглядати не будемо: так як ціна його позитивна, тому план перевезень за допомогою перерахунку цього циклу не покращиться.
Після всіх міркувань отримаємо наступне:

	B1	B2	B3	B4	B5	ai
A1			0.14	0.1	0.09	3000
A2	0.08			0.05	0.07	6000
A3	0.1	0.15				8000
bj						17000

Отже, покращуємо план перевезень за допомогою Цікла1. Для цього перенесемо по циклу мнімальное кількість вантажу, що стоїть в негативній вершині.

	B1	B2	B3	B4	B5	ai
A1			0.14	0.1	0.09	3000
A2	0.08				0.07	6000
A3	0.1	0.15				8000
bj						17000

Підрахуємо L для таблиці зі змінами.
L =
Припустимо, що знайдено оптимальне рішення. Перевіримо його за допомогою методу потенціалів.
Приймемо a1 = 0, тоді bj = cij - ai (для заповнених клітин). Якщо знайдене рішення справедливо, то у всіх порожніх клітинках таблиці Δij = cij - (ai + bj) ≥ 0. Ясно, що Δij = 0 для заповнених клітин. Отримаємо наступне.

	b1 = 0.09	b2 = 0.12	b3 = 0.14	b4 = 0.07	b5 = 0.05	ai
a1 = 0						3000
a2 =- 0.02						6000
a3 = 0.01						8000
bj						17000

З таблиці видно, що знайдене оптимальне рішення вірно, так як Δij ≥ 0.

Відповідь

	B1	B2	B3	B4	B5	ai
A1			0.14	0.1	0.09	3000
A2	0.08				0.07	6000
A3	0.1	0.15				8000
bj						17000

ЗАВДАННЯ N4

Умова

№	b1	b2	c11	c12	c22	extr	a11	a12	a21	a22	p1	p2	Знаки огр. 2 Січень
31	2	7	-1	-2	-3	max	2	-4	3	2	10	20	£	£

Рішення задачі нелінійного програмування
Визначити екстремум цільової функції виду
F = c11x12 + c22x22 + c12x1x2 + b1x1 + b2x2
за умов
a11x1 + a12x2 <=> p1
a21x1 + a22x2 <=> p2.

Рішення

ѓ (x1, x2) =

1. Потрібно визначити відносний максимум функції для цього потрібно визначити стаціонарну точку .


стаціонарна точка (-0,25; 1.25)
2. Дослідити знайдену стаціонарну крапку на максимум для чого визначити увігнутість функції f.


-2 <0

Умови виконуються, отже, цільова функція є строго ввігнутої в околиці стаціонарної точки.
3. Складання функції Лагранжа.


A Б
Перепишемо систему А.
А1
4. Вводимо додаткові змінні v1, v2, w1, w2, що перетворюють нерівності системи А1 в рівності.

A2
перепишемо систему Б
Б2 - Умови доповнює нежорсткої
5. Вирішити систему А2 за допомогою методу штучних змінних.
в 1 і 2-е рівняння системи А2.

Вводимо псевдоцелевую функцію


базисні змінні: y1, y2, w1, w2
вільні змінні: x1, x2, v1, v2, u1, u2

	80M	M	4M	0	M	4M	0
	10	0	1.5	0	0	0.5	0
	13.5	0	-1.5	-2	0.5	0.5	-0.5
	50	0	8	0	0	2	0
	58.5	-1	5.5	4	1.5	-0.5	1.5

Оптимальне рішення:
y1 = x1 = u1 = y2 = w1 = v2 = 0
x2 = 10
w1 = 50 оптимальне рішення
u2 = 13.5
v1 = 58.5
6. перевіримо умова доповнює нежорсткої
xi * vi = 0
ui * wi = 0 умови виконуються
x1 = 0
x2 = 10 - рішення вихідної задачі квадратичного програмування

Відповідь

x1 = 0
x2 = 10

Література

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