Курсова робота з дисципліни «Дослідження операцій»
Нормоконтроллер:
Плотнікова М. В. _______
«____» ___________ 2005
Керівник:
Плотнікова М. В. _______
«____» ___________ 2005
Автор:
Студент групи ПС-346
Нечаєв Л. В. ___________
«____» ___________ 2005
Робота захищена
з оценкой______________
«____» ___________ 2005

Зміст

\ F "1-9" \ t "Заголовок 2; 2; Заголовок 1; 1; Заголовок 1; 1; Заголовок 2; 2" Задача 1 .................. .................................................. .................................................. ....................... 3
Умова ................................................. .................................................. ...................................... 3
Рішення ................................................. .................................................. .................................... 3
Відповідь: ................................................ .................................................. .......................................... 5
Задача 2 ................................................ .................................................. ........................................... 6
Умова ................................................. .................................................. ...................................... 6
Рішення ................................................. .................................................. .................................... 6
Відповідь :................................................ .................................................. ........................................... 8
Примітка :................................................ .................................................. .............................. 8
Задача 3 ................................................ .................................................. ......................................... 10
Умова ................................................. .................................................. .................................... 10
Рішення ................................................. .................................................. .................................. 10
Відповідь :................................................ .................................................. ......................................... 14
Задача 4 ................................................ .................................................. ......................................... 15
Умова ................................................. .................................................. .................................... 15
Рішення ................................................. .................................................. .................................. 15
Відповідь :................................................ .................................................. ......................................... 19
Додаток 1 ................................................ .................................................. .............................. 20
Список використаної літератури ............................................... ....................................... 22

Задача 1

Умова

Оператор зв'язку надає 2 види послуг:
1. Надання одній лінії телефонної мережі загального користування (ТМЗК) і трьох ліній цифрового зв'язку (ЦС);
2. Надання одній лінії ЦС і двох ліній ТМЗК.
Вартість послуг вказана в табл. 1:
Таблиця 1
Мережі зв'язку і експлуатоване обладнання накладає наступні обмеження на кількість використовуваних ліній зв'язку:
ТМЗК ≤ 300
ЦС ≤ 120
ТМЗК +2 * ЦС ≤ 380
Визначити оптимальне співвідношення послуг 1 і 2, які оператор повинен надавати для отримання максимальної виручки.

Рішення

1. Позначимо за x1 кількість наданих послуг з номером `1 ', а x2 - кількість наданих послуг з номером` 2'.
2. Врахуємо обмеження завдання: .
3. Складемо цільову функцію, яку потрібно максимізувати:
4. Задача зведена до наступної задачі лінійного програмування: «Знайти значення аргументів x1 і x2, при яких функція приймає найбільше значення при обмеженнях: . Зрозуміло, x1 ≥ 0, x2 ≥ 0.
5. Вирішимо вище представлену завдання графічним методом, так як у задачі присутні тільки 2 змінні x1 і x2. Для цього:
Зобразимо багатокутник рішень у площині x2Ox1:


Графік представлений на рис. 1.
SHAPE

Малюнок SEQ "Малюнок" \ * Arabic 1 - Графічне рішення задачі 1

На початку максимізації найбільше значення цільової функції дорівнює 0, також F проходить через початок координат (пунктирна лінія на рис. 1). Вектор задає напрям зростання цільової функції.
Оптимальне рішення знаходиться в точці (0; 95), що знаходиться на
перетині прямих . Отже, найбільше значення цільової функції F дорівнюватиме , Досягається при x1 = 0, x2 = 95.
Отже, для отримання найбільшого прибутку (57000 од.) Оператор зв'язку повинен не надавати послуг 1, а послуг 2 надати в кількості 95 штук.

Відповідь:

- Не надавати yслуг # 1
- Yслуг # 2 надати в кількості 95 штук.

Задача 2

Умова

Рішення задачі лінійного програмування.
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції F = 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).
Таблиця 2

c1	c2	c3	c4	c5	c6	b1	b2	b3	Знаки обмежень
									1	2	3
4	-1	12	2	-1	0	2	13	16	=	=	=

a11	a12	a13	a14	a15	a16	a21	a22	a23	a24	a25	a26	a31	a32	a33	a34	a35	a36	Ext
-1	1	1	0	0	0	4	3	2	1	1	0	3	2	0	0	1	0	max

Рішення

Складаємо систему:

Цільова функція має вигляд
Наведемо систему обмежень до виду основного завдання лінійного програмування:

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

Складаємо симплекс-таблицю.
Це рішення є допустимим, але не опорним, тому що присутній негативний вільний член у другому рядку. Ліквідуємо його шляхом заміни базисних змінних на основні. У рядку x4 знаходиться негативний елемент a42 =- 2, отже, стовпець x2 - дозволяє. Найменша відношення між вільним членом і ел-том дозволяє стовпця (див. поле «оцінка») буде в першому рядку і елемент a32 - дозволяє. Вийшла таблиця 3 (верхні числа).
Таблиця 3

Базис	Вільний член	Змінні		Оцінка
		x1	x2
x3	2 2	-1 -1	1 1	2
x4	-7 4	3 -2	-2 2	-
x5	16 -4	3 2	2 -2	8
F	6 18	13 -9	-9 9	-

Тепер перетворимо таблицю за наступним алгоритмом:
1. Виділимо дозволяє елемент aij;
2. Знайдемо зворотний йому величину λ = 1/aij і запишемо її в правому нижньому кутку цієї ж осередку;
3. Всі елементи роздільної рядки, крім дозволяє елемента, помножимо на λ і запишемо внизу відповідної комірки;
4. Всі елементи дозволяє стовпця, крім дозволяє елемента, помножимо на-λ і запишемо внизу відповідної комірки;
5. Виділимо всі верхні числа у роздільній рядку, і всі нижні - у вирішуючому стовпці;
6. Для кожного з інших елементів запишемо в нижню частину осередку твір виділених чисел, які стоять у тому ж рядку і в тому ж стовпці, що і даний елемент;
7. Перепишемо таблицю, замінивши змінні: елементи дозволяють рядка і стовпця - значеннями, що стоять у нижніх частинах цих осередків; залишилися елементи - сумою чисел, що стоять у верхніх і нижніх частинах осередків.
Стосовно до поточного кроку, дозволяє елемент a32, λ = 1 / a32 = 1. Після зазначених вище перетворень, отримаємо нову таблицю (табл. 4):
Таблиця 4

Базис	Вільний член	Змінні
		x1	x3
x2	2	-1	1
x4	-3	1	2
x5	12	5	-2
F	24	4	9

Рішення знову не може бути опорним, тому що присутній негативний вільний член у другому рядку. Спробуємо ліквідувати його шляхом заміни базисних змінних на основні. Але в рядку x4 більше немає негативних елементів, отже, не можна вибрати дозволяє стовпець. Зауважимо, що в рядку цільової функції немає негативних елементів, отже оптимальне рішення, у разі скасування обмежень на змінні, досягнуто. Обмежує система рівнянь не має рішень при невід'ємних значеннях всіх змінних.

Відповідь:

Система рівнянь несумісна в області позитивних значень змінних.

Примітка:

Цей же результат отримано і при вирішенні даної задачі в пакеті Mathematica:


Задача 3

Умова

Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
Таблиця 5

	B1	B2	B3	ai
A1	10	20	32	700
A2	12	50	25	600
A3	21	18	50	200
A4	25	15	23	200
A5	21	30	40	100
bj	300	700	1000

Рішення

Зауважимо, що загальна кількість запасів (700 +600 +200 +200 +100 = 1800) менше кількості заявок (300 +700 +1000 = 2000), отже маємо відкриту транспортну задачу з надлишком заявок. Додамо рядок з фіктивними запасами для доповнення завдання до завдання закритого типу. Після коригування отримуємо транспортну задачу з правильним балансом (табл. 6):

Таблиця 6

	B1	B2	B3	ai
A1	10	20	32	700
A2	12	50	25	600
A3	21	18	50	200
A4	25	15	23	200
A5	21	30	40	100
A6	0	0	0	200
bj	300	700	1000	2000

Знайдемо опорне рішення методом найменших витрат (табл. 7):
Таблиця 7

	B1	B2	B3	ai
A1	10 300	20 400	32 -	700	-10 (2)
A2	12 -	50 -	25 600	600	-7 (7)
A3	21 -	18 200	50 -	200	-8 (4)
A4	25 -	15 100	23 100	200	-5 (5)
A5	21 -	30 -	40 100	100	-22 (8)
A6	0 -	0 -	0 200	200	18 (9)
Bj	300	700	1000	2000
	0 (1)	-10 (3)	-18 (6)

Обраний план перевезень є допустимим, оскільки при ньому всі заявки задоволені і всі запаси витрачені, сума перевезень по рядку дорівнює запасу відповідного пункту відправлення, а сума перевезень за стовпцем - заявці відповідного пункту призначення. Сума запасів дорівнює сумі заявок, і виражається числом 2000, що стоять у правому нижньому куті таблиці. Даний розподіл є базисним (заповнено m + n-1 = 8 комірок таблиці), отже, завдання готова до вирішення.
Спочатку витрати на перевезення складуть:

Складемо матрицю оцінок методом потенціалів:
Почнемо з першого стовпчика. Нехай потенціал цього стовпця дорівнює нулю. Поряд з потенціалом у дужках записуємо номер кроку. Після додавання потенціалу до коефіцієнтів витрат першого стовпця коефіцієнт витрат заповненої клітини (1; 1) не зміниться; щоб отриманий після складання коефіцієнт став дорівнює 0, потенціал першого рядка таблиці повинен бути рівний -10; для обнуління коефіцієнта витрат клітини (1, 2) потенціал другого стовпця повинен бути -10 і т.д.
Змінені коефіцієнти виписуються у вигляді матриці оцінок:

Критерій оптимальності (базисне розподіл поставок вірно тоді і тільки тоді, коли оцінки всіх вільних клітин ненегативні) на даному етапі не виконаний - присутні 2 вільні клітини з негативними оцінками.
Продовжимо оптимізацію (табл. 8). Складемо цикл перерахунку для клітини (5; 2) і дамо постачання неї:
Таблиця 8

	B1	B2	B3	ai
A1	10 300	20 400	32 -	700
A2	12 -	50 -	25 600	600
A3	21 -	18 200	50 -	200
A4	25 -	15 - 100	23 + 100	200
A5	21 -	30 + -	40 - 100	100
A6	0 -	0 -	0 200	200
Bj	300	700	1000	2000

У верхньому правому куті знаком «+» відзначаються ті клітини, поставки в які збільшаться, а знаком «-» - ті, в які зменшаться. Найбільша можлива поставка, виходячи з поточного циклу перерахунку дорівнює min {100, 100, 100} = 100. Пересуваємо її по циклу (табл. 9):
Таблиця 9

	B1	B2	B3	ai
A1	10 300	20 400	32 -	700	-10 (2)
A2	12 -	50 -	25 600	600	-7 (8)
A3	21 -	18 200	50 -	200	-8 (4)
A4	25 -	15 0	23 200	200	-5 (5)
A5	21 -	30 100	40 -	100	-20 (6)
A6	0 -	0 -	0 200	200	18 (9)
Bj	300	700	1000	2000
	0 (1)	-10 (3)	-18 (7)

Після пересування звільнилися одразу 2 клітки, рішення перестало бути базисним. Для того, щоб воно залишилося базисним, дамо фіктивну поставку в клітку (4, 2).
Знову складаємо матрицю оцінок за вищенаведеним алгоритмом:

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

Таблиця 9

	B1	B2	B3	ai
A1	10 (0) 300	20 (0) 400	32 (4) -	700	-10 (2)
A2	12 (5) -	50 (33) -	25 (0) 600	600	-7 (8)
A3	21 (13) -	18 (0) 200	50 (24) -	200	-8 (4)
A4	25 (20) -	15 (0) 0	23 (0) 200	200	-5 (5)
A5	21 (1) -	30 (0) 100	40 (2) -	100	-20 (6)
Bj	300	700	1000
	0 (1)	-10 (3)	-18 (7)

Умова Δij ≥ 0 виконується, отже, рішення вірне.

Відповідь:

Таблиця 10

	B1	B2	B3	ai
A1	10 300	20 400	32 -	700
A2	12 -	50 -	25 600	600
A3	21 -	18 200	50 -	200
A4	25 -	15 -	23 200	200
A5	21 -	30 100	40 -	100
Bj	300	700	1000	1800/2000

Сумарні витрати на перевезення становлять:

Задача 4

Умова

Рішення задачі нелінійного програмування
Визначити екстремум цільової функції виду
F = c11x12 + c22x22 + c12x1x2 + b1x1 + b2x2
за умов
a11x1 + a12x2 <=> p1
a21x1 + a22x2 <=> p2.
Дані розташовуються в табл. 11.
1. Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
2. Скласти функцію Лагранжа.
3. Отримати систему нерівностей, відповідно до теореми Куна-Таккера.
4. Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
5. Дати відповідь з урахуванням умов доповнює нежорсткими.

Таблиця 11

b1	b2	c11	c12	c22	extr	a11	a12	a21	a22	p1	p2	Знаки огр.
												1	2
1	8	-1	0.5	-1	max	1	1	0	1	7	5	≤	≤

Рішення

Цільова функція має вигляд:

Обмеження:
,
1. Визначимо відносний максимум функції. Для цього необхідні координати стаціонарної точки .
,
Отримали стаціонарну точку (1.6; 4.4).
2. Досліджуємо стаціонарну крапку на максимум, для чого і визначимо увігнутість функції f.
,
Умови виконуються, отже цільова функція є строго ввігнутої в околиці стаціонарної точки.
3. Складемо функцію Лагранжа:
Складемо систему нерівностей, відповідно до теореми Куна-Таккера.

А) Б)
Перепишемо систему А:
A1) . Вводимо додаткові змінні v1, v2, w1, w2, що перетворюють нерівності системи А1 в рівності:
A2)
перепишемо систему Б:
Б2) - Умови доповнює нежорсткої
Вирішимо систему А2 за допомогою методу штучних змінних. в перше і друге рівняння системи А2.

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

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


Вирішуємо цю задачу симплекс-методом за допомогою таблиць і невеликої програми на мові Сі, текст якої наведений у Додатку 1.
Таблиця 12

	bi	x1	x2	u1	u2	v1	v2
y1	1 0.5	2 0.5	-0.5 -0.25	1 0.5	0 0	-1 -0.5	0 0
y2	8 0.25	-0.5 0.25	2 -0.125	1 0.25	1 0	0 -0.25	-1 0
w1	7 -0.5	1 -0.5	1 0.25	0 -0.5	0 0	0 0.5	0 0
w2	5 0	0 0	1 0	0 0	0 0	0 0	0 0
Y '	9M 0.75M	-1.5M 0.75M	-1.5M -0.375M	-2M 0.75M	-1M 0M	1M -0.75M	1M 0M

Таблиця 13

	bi	y1	x2	u1	u2	v1	v2
x1	0.5 1.1	0.5 0.03333	-0.25 0.1333	0.5 0.1667	0 0.1333	-0.5 -0.03333	0 -0.1333
y2	8.25 4.4	0.25 0.1333	1.875 0.5333	1.25 0.6667	1 0.5333	-0.25 -0.1333	-1 -0.5333
w1	6.5 -5.5	-0.5 -0.1667	1.25 -0.6667	-0.5 -0.8333	0 -0.6667	0.5 0.1667	0 0.6667
w2	5 -4.4	0 -0.1333	1 -0.5333	0 -0.6667	0 -0.5333	0 0.1333	0 0.5333
Y '	9.75M 8.25M	0.75M 0.25M	-1.875M 1M	-1.25M 1.25M	-1M 1M	0.25M -0.25M	1M -1M

Таблиця 14

	bi	y1	y2	u1	u2	v1	v2
x1	1.6	0.5333	0.1333	0.6667	0.1333	-0.5333	-0.1333
x2	4.4	0.1333	0.5333	0.6667	0.5333	-0.1333	-0.5333
w1	1	-0.6667	-0.6667	-1.333	-0.6667	0.6667	0.6667
w2	0.6	-0.1333	-0.5333	-0.6667	-0.5333	0.1333	0.5333
Y '	18M	1M	1M	0M	0M	0M	0M

Оптимальне рішення:
y1 = y2 = u1 = u2 = v1 = v2 = 0
x1 = 1.6
x2 = 4.4
w1 = 1
w2 = 0.6
Перевіримо умову доповнює нежорсткої:
xi * vi = 0
ui * wi = 0
Умови виконуються, отже, x1 = 1.6, x2 = 4.4 є рішенням вихідної задачі kвадратічного програмування. Координати стаціонарної точки збігаються з координатами, отриманих в якості відповіді. Стаціонарна точка задовольняє умовам обмежень.
Значення функції в точці (x1; x2) дорівнює 0.

Відповідь:

x1 = 1.6
x2 = 4.4
f (x1; x2) = 0

Додаток 1

Для вирішення завдання # 4 використана наступна програма на мові Сі, скомпільована gcc (GCC) 4.0.0 20050519 (Red Hat 4.0.0-8). Її текст наведено нижче:
# Include <stdio.h>
# Define x 7
# Define y 5
double mc [x * y] =
{
1, 2, -0.5, 1, 0, -1, 0,
8, -0.5, 2, 1, 1, 0, -1,
7, 1, 1, 0, 0, 0, 0,
5, 0, 1, 0, 0, 0, 0,
9, -1.5, -1.5, -2, -1, 1, 1
};
double mt [x * y];
void mprint (double * m, int xs, int ys)
{
int i, j;
printf ("\ n");
for (j = 0; j <ys; j + +)
{
for (i = 0; i <xs; i + +)
{
printf ("% 10.4lg", m [j * xs + i]);
}
printf ("\ n");
}
}
int main (void)
{
int i, j, i1, j1, it, jt;
double msx, msx1;
/ / Вибираємо дозволяє ел-т
nextmtx:
printf ("\ nІсходная матриця коефіцієнтів:"); mprint (mc, x, y);
getch ();
msx = 10000.;
for (i = 0; i <x; i + +)
{
if (mc [(y-1) * x + i] <0)
{
/ / Можливо, знайдений дозволяє стовпець
for (j = 0; j <y; j + +)
{
/ / Шукаємо найменше відношення своб. члена до ел-ту розр. стовпця
if (mc [j * x + i] <1e-32)
continue; / / Нульовий або негативний
msx1 = mc [j * x] / mc [j * x + i];
if (msx> msx1) / / Приватне св.ч / р.Ель
{
msx = msx1; / / найменше шукаємо
it = i; jt = j; / / координати р.ел.
}
}
if (msx> 9999.) continue; / / Ні позитивних ел-тів
else / / знайдений р.ел., mx! = 0
{
i = it; j = jt; / / його координати
}
printf ("\ n Дозволяючий елемент: a (% d;% d) =% lg", j +1, i +1, mc [j * x + i]);
if (mc [j * x + i]> 0)
{
/ / Це і є дозволяє елемент (s_el), знаходимо зворотну величину
mt [j * x + i] = 1. / Mc [j * x + i];
for (i1 = 0; i1 <x; i1 + +)
{
/ / Роздільна рядок (1/s_el)
if (i1 == i) continue; / / Пропустити сам s_el
mt [j * x + i1] = mt [j * x + i] * mc [j * x + i1];
}
for (j1 = 0; j1 <y; j1 + +)
{
/ / Дозволяючий стовпець (-1/s_el)
if (j1 == j) continue; / / Пропустити сам s_el
mt [j1 * x + i] = - mt [j * x + i] * mc [j1 * x + i];
}
/ / Успішно складені розр. рядок і стовпець.
/ / Тепер складаємо інші коеф-ти
for (j1 = 0; j1 <y; j1 + +)
{
if (j1 == j) continue; / / Пропустити всю авторизований. рядок
for (i1 = 0; i1 <x; i1 + +)
{
if (i1 == i) continue; / / І стовпець теж
/ / Твір нижній частині стовпця
/ / На верхню частину рядка
mt [j1 * x + i1] = mt [j1 * x + i] * mc [j * x + i1];
}
}
/ *
* Все. Чи готова матриця нижніх значень, тепер потрібно
* Помістити все на свої місця в mc
* /
printf ("\ nМатріца нижніх значень:"); mprint (mt, x, y);
getch ();
for (j1 = 0; j1 <y; j1 + +)
{
for (i1 = 0; i1 <x; i1 + +)
{
if ((j1 == j) | | (i1 == i))
{
/ *
* Роздільна рядок або стовпець
* Просто кладемо елементи в mc
* /
mc [j1 * x + i1] = mt [j1 * x + i1];
}
else
/ / Інакше - суму
mc [j1 * x + i1] + = mt [j1 * x + i1];
}
}
/ / Все готово до чергового кроку.
goto nextmtx; / / наступ. матриця
}
/ / Цей ел-т не підходить, тому що він негативний
}
/ / Якщо так і не було підходящого ел-та, то перевіряємо слід. стовпець
}
/ / Негативні коеф-тів при цільової ф-ції не знайдено, отже, рішення оптимально
printf ("\ nОптімізіровано. Відповідь:"); mprint (mc, x, y);
return 0;
}
Програма компілювалися командним рядком:
gcc simplex.c-o simplex
, Запускалася:
. / Simplex
і видавала на консоль покрокове вирішення завдання, яке було занесено до симплекс-таблиці (див. табл. 12-14) четвертої завдання даної курсової роботи.

Список використаної літератури

1. Кремер М. Ш., Путко Б. А., Трощин І. М. «Дослідження операцій в економіці» - М.: ЮНИТИ, 2004. - 407 с.
2. Плотнікова М. В. Курс лекцій (ПС)