додати матеріал


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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Курсова робота з дисципліни «Дослідження операцій»
Нормоконтроллер:
Плотнікова М. В. _______
«____» ___________ 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
ТМЗК
ЦС
Ціна
Послуга 1
1
3
750
Послуга 2
2
1
600
Мережі зв'язку і експлуатоване обладнання накладає наступні обмеження на кількість використовуваних ліній зв'язку:
ТМЗК ≤ 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
Підпис: Малюнок 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. Плотнікова М. В. Курс лекцій (ПС)
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
215.9кб. | скачати


Схожі роботи:
Дослідження операцій 2
Дослідження операцій 5
Дослідження операцій 4
Дослідження операцій 3
Дослідження операцій 2
Методи дослідження операцій
Дослідження математичних операцій
Дослідження операцій і теорія систем
Рішення задач дослідження операцій
© Усі права захищені
написати до нас
Рейтинг@Mail.ru