[
Дослідження операцій 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), значить рішення вихідної задачі квадратичного програмування існує.
ВІДПОВІДЬ
: існує.
Література
Курс лекцій Плотнікова М. В.
Будь ласка, не зберігайте тестовий текст.
Ваш ip: 18.221.53.209 буде збережений.
категорії
за типом
за алфавітом
завантажені
© Усі права захищені
написати до нас