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

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

скачати

Міністерство освіти і науки Російської Федерації
Південно-Уральський державний університет
Кафедра системи управління
Курсова робота
з дисципліни: дослідження операцій
Варіант 9
_
Челябінськ
2004
Зміст
Завдання 1 Березня
Завдання 2 Червень
Завдання 9 березня
Завдання квітень 1911
Література 17

Завдання 1
Задача 9
Умова:
З трьох видів сировини необхідно скласти суміш, до складу якої має входити не менше a од. хімічної речовини А, b од. - Речовини В і c од. - Речовини С. Кількість одиниць хімічної речовини, що міститься в 1 кг. сировини кожного виду, вказано в таблиці. Там же приведена ціна 1 кг. сировини кожного виду. Скласти суміш, що містить не менше потрібної кількості речовин даного виду і має мінімальну вартість.
Речовина
Кількість одиниць речовини, що міститься в 1 кг сировини
1
2
3
А
d 11
d 12
d 13
У
d 21
d 22
d 23
З
d 31
d 32
d 33
Ціна 1 кг сировини
D 1
D 2
D 3
№ вар.
d 11
d 12
d 13
d 21
d 22
d 23
d 31
d 32
d 33
9
1
1
0
2
0
3
1
2
4
D 1
D 2
D 3
а
b
c
5
6
7
26
30
24
Рішення:
Складемо математичну модель задачі.
Позначимо через n1, n2, n3 кількість кг сировини 1, 2, 3 відповідно.
Тоді, цільова функція буде
L = D1n1 + D2n2 + D3n3 = 5n1 + 6n2 +7 n3 → min
Система обмежень:
_ EMBED Equation.3 ___
Наведемо систему обмежень до виду основного завдання лінійного програмування. Введемо цільову функцію з протилежним знаком L ', і нові змінні n4, n5, n6, які входять в цільову функцію з нульовими коефіцієнтами.
L '= 0 - (5n1 + 6n2 +7 n3) → max
_ EMBED Equation.3 ___
Виберемо n1, n2, n3 вільними змінними, а n4, n5, n6 - засадничими і приведемо до стандартного вигляду для вирішення за допомогою симплекс-таблиці:
L '= 0 - (5n1 + 6n2 +7 n3)
_ EMBED Equation.3 ___
Складемо симплекс-таблицю.
Це рішення не опорне, тому що вільні члени не позитивні.
Виберемо в першому рядку негативний елемент, наприклад на перетині n1 і n4, тоді дозволяє стовпець n1, а дозволяє елемент - n5 (мінімальний по відношенню вільного члена до елементів дозволяє стовпця).
Таблиця 1.1
b
n 1
n 2
n 3
L '
0
5
6
7
-75
2,5
0
-8
n 4
-26
-1
-1
0
26 / 1 = 26
15
-1
0
1,5
n 5
-30
-2
0
-3
30 / 2 = 15min
15
-1
0
1,5
n 6
-24
-1
-2
-4
24 / 1 = 24
15
-1
0
1,5
Міняємо n 1 і n 5.
Таблиця 1.2
b
n 5
n 2
n 3
L '
-75
2,5
6
-0,5
-45
5
-10
25
n 4
-11
-0,5
-1
1,5
11 / 0,5 = 22
9
-1
2
-5
n 1
15
-0,5
0
1,5
9
-1
2
-5
n 6
-9
-0,5
-2
-2,5
9 / 0, 5 = 18min
18
-2
4
5
Міняємо n 5 і n 6.
Таблиця 1.3
b
n 6
n 2
n 3
L '
-120
5
-4
25
-10
5
5
-18
n 4
-2
-1
1
-4
2
-1
-1
2,5
n 1
24
-1
2
-3
2
-1
-1
3,5
n 5
18
-2
4
5
4
-2
-2
7
Міняємо n 4 і n 6.
Таблиця 1.4
b
n 4
n 2
n 3
L '
-130
5
1
7

 


n 6
2
-1
-1
3,5




n 1
26
-1
-1
0

 


n 5
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
b 1
b 2
b 3
29
0
5
1
-1
1
0
2
2
10
Знаки обмежень
a 11
a 12
a 13
a 14
1
2
3
£
£
£
-1
1
1
0
a 15
a 16
a 21
a 22
a 23
a 24
a 25
a 26
0
0
1
-2
0
1
0
0
a 31
a 32
a 33
a 34
a 35
a 36
Тип екстрем.
2
1
1
1
2
0
max
Рішення:
Складемо систему:
_ EMBED Equation.3 ___
Цільова функція Q = 0x1 +5 x2 + 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
x 1
x 2
x 3
x 4
x 5
Q
0
0
-5
-1
1
-1
10
-5
5
5
0
0
x 6
2
-1
1
1
0
0
2 / 1 = 2min
2
-1
1
1
0
0
x 7
2
1
-2
0
1
0
4
-2
2
2
0
0
x 8
10
2
1
1
1
2
10 / 2 = 5
-2
1
-1
-2
0
0
Міняємо x 2 і x 6.
Таблиця 2.2
b
x 1
x 6
x 3
x 4
x 5
Q
10
-5
5
4
1
-1
4
1,5
-1
-1
0,5
0,5
x 2
2
-1
1
1
0
0
0
0
0
0
0
0
x 7
6
-1
2
2
1
0
0
0
0
0
0
0
x 8
8
3
-1
-1
1
2
4
6
-2
-2
2
0,5

Міняємо x 5 і x 8.
Таблиця 2.3
b
x 1
x 6
x 3
x 4
x 8
Q
14
-3.5
4,5
3,5
1,5
0,5
21
5,25
-2,625
-2,625
2,625
2,625
x 2
2
-1
1
1
0
0
8 / 3
2 / 3
-1 / 3
-1 / 3
1 / 3
1 / 3
x 7
6
-1
2
2
1
0
8 / 3
2 / 3
-1 / 3
-1 / 3
1 / 3
1 / 3
x 5
4
1,5
-0,5
-1
0,5
0,5
8 / 3
2 / 3
-1 / 3
-1 / 3
1 / 3
1 / 3
Міняємо x 5 і x 1.
Таблиця 2.4
b
x 5
x 6
x 3
x 4
x 8
Q
35
5,25
1,875
0,875
4,125
3,125
x 2
14 / 3
2 / 3
2 / 3
2 / 3
1 / 3
1 / 3
x 7
26 / 3
2 / 3
5 / 3
5 / 3
4 / 3
1 / 3
x 1
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
b 1
b 2
b 3
b 4
b 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.
Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
Скласти функцію Лагранжа.
Отримати систему нерівностей, відповідно до теореми Куна-Таккера.
Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
1. Дати відповідь з урахуванням умов доповнює нежорсткими.
2.

b 1
b 2
c 11
c 12
c 22
extr
a 11
a 12
a 21
a 22
p 1
p 2
Знаки огр.
2 Січень
31
-7
-2
4
1.5
-2
min
-2
1.5
4
-3
18
9
£
³
Рішення:
1) Цільова функція: F = 4x12-2x22 +1,5 x1x2-7x1-2x2 → min
Розглянемо F '=- 4x12 +2 x22 -1,5 x1x2 +7 x1 +2 x2 → 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 +2 x22 -1,5 x1x2 +7 x1 +2 x2 + 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), значить рішення вихідної задачі квадратичного програмування існує.
ВІДПОВІДЬ: існує.

Література
Курс лекцій Плотнікова М. В.
Додати в блог або на сайт

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

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


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