Група
виробничого
устаткування
|
Кількість
устаткування для випуску
одиниці
продукції
|
Кількість
устаткування
в
групі
|
Продукція
І
|
Продукція
ІІ
|
А
|
2
|
3
|
12
|
В
|
1
|
2
|
8
|
С
|
4
|
0
|
16
|
Прибуток,
тис. грн.
|
1
|
3
|
|
Рішення:
Позначимо
через x1
і x2
кількість продукції І і ІІ. Тоді умови для необхідного устаткування
будуть описуватися наступними нерівностями:
2x1
+ 3x2
≤ 12
1x1
+ 2x2
≤ 8
4x1
+ 0x2
≤ 16
x1,
x2
≥ 0
А
умова найбільшого прибутку:
f
= 1x1
+ 3x2
→ max
Для
розв'язання задачі графічним методом замість нерівностей системи обмежень
беремо відповідні рівняння граничних прямих і будуємо їх графіки:
Звертаючи
увагу на півплощини, в яких виконуються відповідні нерівності, знаходимо
спільну область, помічену сірим кольором. Стрілкою вказуємо вектор зростання
цільової функції f, компоненти
якого (1; 3) дорівнюють коефіцієнтам при x1 і x2 у виразі
цієї функції.
Бачимо,
що максимального значення функція f набуває в точці М, на перетині прямої 2x1
+ 3x2
= 12 і вісі x2.
Підставляючи x1
= 0 в це рівняння, отримуємо:
2*0
+ 3x2
= 12
x2
= 4
М
= (x1;
x2)
= (0; 4)
Значення
функції f в точці М:
fmax
= 1*0+3*4 = 12
Відповідь:
Найбільший
прибуток у розмірі 12 тис. грн. буде від реалізації 4 одиниць продукції ІІ без
випуску продукції І.
Завдання 2. Для заданої ЗЛП побудувати двоїсту,
розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком
знайти розв'язок іншої задачі
F
= x1 + x2 → max
x1 -
x2 ≥ -6
|
3x1
+ 4x2
≤ 26
|
2x1
- x2 ≤ 10
|
x1
≥ 0, x2 ≥ 0
Рішення.
Перепишемо
ЗЛП, помноживши першу нерівність на -1:
F
= x1 + x2 → max
-x1
+ x2 ≤ 6
3x1
+ 4x2 ≤ 26
2x1
- x2 ≤ 10
x1
≥ 0, x2 ≥ 0
Двоїста
задача записується у вигляді:
F*
= 6y1 + 26y2 + 10y3 → min
-1y1
+ 3y2 + 2y3 ≥ 1
1y1
+ 4y2 - 1y3 ≥ 1
y1
≥ 0, y2 ≥ 0, y3 ≥ 0
Зведемо
вихідну
задачу
до
канонічної
форми
[5, с.
14]. Для
цього добавимо невід'ємні величини x3,
x4,
x5,
щоб нерівності перетворити в рівняння:
F
- x1 - x2 → max
-x1
+ x2 + x3 = 6
3x1
+ 4x2 + x4 = 26
2x1
- x2 + x5
= 10
x1
≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥
0, x5 ≥ 0
Розв'яжемо
дану задачу симплекс-методом [5, с. 18]. Заповнюємо симплекс-таблицю
початковими значеннями, вибираємо стовпець (x1)
з першим від'ємним значенням (-1) в останньому рядку, вибираємо рядок (x5)
з найменшим значенням bi/xi
(5) і виділяємо розв'язувальний елемент (2):
xб
|
b
|
x1
|
x2
|
x3
|
x4
|
x5
|
bi/xi
|
x3
|
6
|
-1
|
1
|
1
|
0
|
0
|
—
|
x4
|
26
|
3
|
4
|
0
|
1
|
0
|
26/3
|
x5
|
10
|
2
|
-1
|
0
|
0
|
1
|
5 (min)
|
Δ
|
0
|
-1
|
-1
|
0
|
0
|
0
|
|
Вводимо
в базис x1
замість x5
і перераховуємо таблицю. Вибираємо стовпець (x2)
з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x4)
з найменшим значенням bi/xi
(2) і виділяємо розв'язувальний елемент (11/2):
xб
|
b
|
x1
|
x2
|
x3
|
x4
|
x5
|
bi/xi
|
x3
|
11
|
0
|
1/2
|
1
|
0
|
1/2
|
22
|
x4
|
11
|
0
|
11/2
|
0
|
1
|
-3/2
|
2 (min)
|
x1
|
5
|
1
|
-1/2
|
0
|
0
|
1/2
|
—
|
Δ
|
5
|
0
|
-3/2
|
0
|
0
|
1/2
|
|
Вводимо
в базис x2
замість x4
і перераховуємо таблицю:
xб
|
b
|
x1
|
x2
|
x3
|
x4
|
x5
|
bi/xi
|
x3
|
10
|
0
|
0
|
1
|
-1/11
|
7/11
|
—
|
x2
|
2
|
0
|
1
|
0
|
2/11
|
-3/11
|
—
|
x1
|
6
|
1
|
0
|
0
|
1/11
|
4/11
|
—
|
Δ
|
8
|
0
|
0
|
0
|
3/11
|
1/11
|
|
В
останньому рядку не залишилося від'ємних величин, тому стовбець b
містить рішення вихідної задачі — максимум функції F:
x1
= 6
x2
= 2
Fmax
= 8
Запишемо
рішення двоїстої задачі з останнього рядка останньої симплекс-таблиці:
y1
= 0
y2
= 3/11
y3
=
1/11
F*min
= 8
Відповідь:
Вихідна
задача: Fmax
= F(6; 2) = 8
Двоїста
задача: F*min
= F*(0;
3/11; 1/11) = 8
Завдання
3. Розв'язати методом потенціалів транспортну задачу
ai \ bj
|
90
|
50
|
60
|
80
|
120
|
5
|
4
|
3
|
4
|
100
|
3
|
2
|
5
|
5
|
60
|
1
|
6
|
3
|
1
|
Рішення.
Підраховуємо
загальні запаси постачальників: 120 + 100 + 60 = 280
Підраховуємо
загальні потреби споживачів: 90 + 50 + 60 + 80 = 280
Дана
модель закрита [5, с. 55], тому що загальні потреби споживачів дорівнюють
загальним запасам постачальників.
Запишемо
умову задачі у вигляді наступної таблиці:
|
В1
|
В2
|
В3
|
В4
|
Запаси
|
А1
|
5
|
4
|
3
|
4
|
120
|
А2
|
3
|
2
|
5
|
5
|
100
|
А3
|
1
|
6
|
3
|
1
|
60
|
Потреби
|
90
|
50
|
60
|
80
|
|
Для
визначення опорного плану транспортної задачі застосуємо спочатку метод
мінімального елемента [5, с. 50]. Для цього будемо послідовно вибирати клітинки
з мінімальним тарифом і робити спробу максимально задовольнити вимоги
споживачів і постачальників.
Перший
мінімальний елемент (1) знаходяться в клітинці А3В1,
тому записуємо в неї запас постачальника А3 (60) і коректуємо
колонки запасів та потреб:
|
В1
|
В2
|
В3
|
В4
|
Запаси
|
А1
|
|
|
|
|
120
|
А2
|
|
|
|
|
100
|
А3
|
60
|
—
|
—
|
—
|
0
|
Потреби
|
30
|
50
|
60
|
80
|
|
Наступні
мінімальні елементи (2 та 3) знаходяться в клітинках А2В2,
А1В3 та А2В1, тому записуємо в них
потреби споживачів В2 (50), В3 (60) та В1 (30)
і коректуємо колонки запасів та потреб:
|
В1
|
В2
|
В3
|
В4
|
Запаси
|
А1
|
—
|
—
|
60
|
|
60
|
А2
|
30
|
50
|
—
|
|
20
|
А3
|
60
|
—
|
—
|
—
|
0
|
Потреби
|
0
|
0
|
0
|
80
|
|
Залишилися
вільні клітинки А1В4 та А2В4, тому
записуємо в них запаси постачальників А1 (60) та А2 (20)
і коректуємо колонки запасів та потреб:
|
В1
|
В2
|
В3
|
В4
|
Запаси
|
А1
|
—
|
—
|
60
|
60
|
0
|
А2
|
30
|
50
|
—
|
20
|
0
|
А3
|
60
|
—
|
—
|
—
|
0
|
Потреби
|
0
|
0
|
0
|
0
|
|
Підрахуємо
вартість перевезення для отриманого опорного плану:
60*3
+ 60*4 + 30*3 + 50*2 + 20*5 + 60*1 = 770
Для
визначення оптимальності отриманого опорного плану застосуємо метод потенціалів
[5, с. 51]. Для цього задамо нульовий потенціал першому рядку, а решту
потенціалів визначимо враховуючи отримані клітинки:
|
В1
|
В2
|
В3
|
В4
|
потенц.
|
А1
|
|
|
3
|
4
|
0
|
А2
|
2
|
|
5
|
1
|
А3
|
1
|
|
|
|
1
|
потенц.
|
2
|
1
|
3
|
4
|
|
Визначаємо
оцінки для вільних клітинок, знаходимо максимальну додатну оцінку (4) в
клітинці А3В4 і позначаємо для неї цикл [5, с. 51]:
|
В1
|
В2
|
В3
|
В4
|
потенц.
|
А1
|
-3
|
-3
|
|
|
0
|
А2
|
(+)
|
|
-1
|
(-)
|
1
|
А3
|
(-)
|
-4
|
1
|
4(+)
|
1
|
потенц.
|
2
|
1
|
3
|
4
|
|
В
вершинах циклу зі знаком (-) вибираємо мінімальне значення (20) у клітинці А2В4
опорного плану. Додаємо його до вершин циклу зі знаком (+) і віднімаємо його
від вершин циклу зі знаком (-):
|
В1
|
В2
|
В3
|
В4
|
Запаси
|
А1
|
|
|
60
|
60
|
0
|
А2
|
50
|
50
|
|
|
0
|
А3
|
40
|
|
|
20
|
0
|
Потреби
|
0
|
0
|
0
|
0
|
|
При
цьому вартість перевезення для цього поліпшеного опорного плану:
60*3
+ 60*4 + 50*3 + 50*2 + 40*1 + 20*1 = 730
Для
визначення оптимальності поліпшеного опорного плану знову застосуємо метод
потенціалів — задамо нульовий потенціал першому рядку, а решту потенціалів
визначимо враховуючи отримані клітинки:
|
В1
|
В2
|
В3
|
В4
|
потенц.
|
А1
|
|
|
3
|
4
|
0
|
А2
|
3
|
2
|
|
|
-1
|
А3
|
1
|
|
|
1
|
-3
|
потенц.
|
4
|
3
|
3
|
4
|
|
Визначаємо
оцінки для вільних клітинок:
|
В1
|
В2
|
В3
|
В4
|
потенц.
|
А1
|
-1
|
-1
|
|
|
0
|
А2
|
|
|
-3
|
-2
|
-1
|
А3
|
|
-6
|
-3
|
|
-3
|
потенц.
|
4
|
3
|
3
|
4
|
|
Оскільки
всі отримані оцінки не більші нуля, то останній опорний план є оптимальним [5,
с. 51]. Отримуємо оптимальний план перевезення:
Маршрут
|
Кількість
|
Вартість
|
А1
— В3
|
60
|
180
|
А1
— В4
|
60
|
240
|
А2
— В1
|
50
|
150
|
А2
— В2
|
50
|
100
|
А3
— В1
|
40
|
40
|
А3
— В4
|
20
|
20
|
Всього
|
730
|
Відповідь:
Вартість
оптимального плану транспортної задачі дорівнює 730.
Завдання 4. Методом множників Лагранжа знайти умовні
екстремуми функцій
f
= x12
+ x1x2
+ x22
- 3x1
- 6x2 за
умови x1
+ x2
= 3.
Рішення.
Перепишемо
умову у вигляді c(x1,
x2)
= 0:
x1
+ x2
- 3 = 0
Тоді
функція Лагранжа [5, с. 153]:
L(x1,
x2, λ) = f(x1, x2) + λ c(x1,
x2)
L(x1,
x2, λ) = x12 + x1x2
+ x22 - 3x1 - 6x2 + λ(x1
+ x2 - 3)
У
точці
екстремуму
частинні
похідні
функції
Лагранжа
дорівнюють
нулю
[5, с.
154]:
∂L(x1,
x2, λ) / ∂x1 = 2x1 + x2
- 3 + λ
∂L(x1,
x2, λ) / ∂x2 = x1 + 2x2
- 6 + λ
Отримуємо
наступну
систему:
2x1
+ x2 - 3 + λ = 0
x1
+ 2x2 - 6 + λ = 0
x1
+ x2 - 3 = 0
Віднімаємо
друге
рівняння
системи
від
першого
і
визначаємо
x2:
x1
- x2
+ 3 = 0
x2
= x1
+ 3
Підставляємо
отримане x2
в третє рівняння системи:
x1
= 0
x2
= x1
+ 3 = 3
Отже
точка (0; 3) — умовний екстремум функції f,
який дорівнює:
f(0;
3) = 32 - 6*3 = -9
Розглянемо
іншу довільну точку (3; 0), для якої виконується умова задачі. Значення функції
для цієї точки:
f(3;
0) = 32 - 3*3 = 0
Оскільки
f(0; 3) < f(3;
0), то знайдений умовний екстремум — це умовний мінімум.
Відповідь:
Умовний
мінімум функції f досягається в
точці (0; 3) і дорівнює -9.
Список
використаної літератури
1. Вітлінський
В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування:
Навчально-методичний посібник для самостійного вивчення дисципліни. — К.: КНЕУ,
2001. — 248 с.
2. Заварыкин
В.М., Житомирский В.Г., Лапчик М.П. Численные методы: Учебное пособие для
студентов. — М.: Просвещение, 1991. — 176 с.
3. Лавренчук
В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне
програмування (методичний посібник для студентів економічних спеціальностей). —
Чернівці: Рута, 1998. — 168 с.
4. Наконечний
С.І., Савіна С.С. Математичне програмування: Навчальний посібник. — К.: КНЕУ,
2003. — 452 с.
5. Попов Ю.Д.,
Тюптя В.І., Шевченко В.І. Методи оптимізації. — К.: КНУ, 2003. — 215 с.