Визначення оптимального плану

2.47. Промислове підприємство виготовляє продукцію трьох видів А, В і С, для чого використовує два види ресурсів 1 і 2, запаси яких становлять відповідно 4000 та 6000 од. Витрати

Ресурс	Витрати ресурсів на одиницю продукції, ум. од., за видами
	А	В	С
1	2	5	5
2	4	2	7

Аналіз умов збуту продукції показав, що мінімальний попит на продукцію підприємства для продукції А, В і С відповідно становить 200, 200 та 150 од. Але співвідношення випуску продукції А, В і С має бути 3 : 2 : 5. Прибуток від реалізації одиниці продукції виду А становить 30 дол., продукції В — 20 дол., а продукції С — 50 дол.

Сформулювати та розв’язати задачу визначення оптимального плану виробництва продукції трьох видів, що дає підприємству найбільший прибуток.

Розв’язання

Сформулюємо математичну модель даної задачі та двоїстої до неї. Шуканий випуск продукції A позначимо через x₁, продукції B – через x₂, продукції С – через x₃. Оскільки є обмеження на виділені ресурси кожного виду, змінні x₁ – x₃ повинні задовольняти таким умовам:

1) 2x₁ + 5x₂ + 5x₃ ≤ 4000,

2) 4x₁ + 2x₂ + 7x₃ ≤ 6000.

Крім того, враховуючи умови попиту продукції, змінні повинні бути в межах:

3) x₁ > 200,

4) x₂ > 200,

5) x₃ > 150.

Оскільки співвідношення випуску продукції А, В і С має бути 3:2:5, то

6) 3x₁ – 2x₂ = 0,

7) 2x₂ – 5x₃ = 0.

Загальна вартість продукції при цьому складає: z = 30x₁ + 20x₂ + 50x₃.

За своїм економічним змістом змінні x₁, x₂, x₃ більші 0.

Отже, приходимо до математичної задачі: серед всіх невід’ємних розв’язків системи нерівностей потрібно знайти такий, при якому функція z набуде максимального значення:

z = 30x₁ + 20x₂ + 50x₃ → max

Приведемо нерівність  до системи рівнянь шляхом введення додаткових змінних.

2x₁+5x₂+5x₃+x₄ = 4000
4x₁+2x₂+7x₃+x₅ = 6000
x₁-x₆ = 200
x₂-x₇ = 200
x₃-x₈ = 150
3x₁-2x₂ = 0
2x₂-5x₃ = 0
Розширена матриця системи:

2	5	5	1	0	0	0	0	4000
4	2	7	0	1	0	0	0	6000
1	0	0	0	0	-1	0	0	200
0	1	0	0	0	0	-1	0	200
0	0	1	0	0	0	0	-1	150
3	-2	0	0	0	0	0	0	0
0	2	-5	0	0	0	0	0	0

Наведемо систему до одиничної матриці методом жордановскіх перетворень.

В якості базової змінної можна вибрати x4, x5,. x6.

Отримуємо нову матрицю:

2	5	5	1	0	0	0	0	4000
4	2	7	0	1	0	0	0	6000
-1	0	0	0	0	1	0	0	-200
0	1	0	0	0	0	-1	0	200
0	0	1	0	0	0	0	-1	150
3	-2	0	0	0	0	0	0	0
0	2	-5	0	0	0	0	0	0

В якості базової змінної можна вибрати x₇.

2	5	5	1	0	0	0	0	4000
4	2	7	0	1	0	0	0	6000
-1	0	0	0	0	1	0	0	-200
0	-1	0	0	0	0	1	0	-200
0	0	1	0	0	0	0	-1	150
3	-2	0	0	0	0	0	0	0
0	2	-5	0	0	0	0	0	0

В якості базової змінної можна вибрати x₈.

2	5	5	1	0	0	0	0	4000
4	2	7	0	1	0	0	0	6000
-1	0	0	0	0	1	0	0	-200
0	-1	0	0	0	0	1	0	-200
0	0	-1	0	0	0	0	1	-150
3	-2	0	0	0	0	0	0	0
0	2	-5	0	0	0	0	0	0

Представимо розрахунки кожного елементу: 

2-(0 • 5):-5	5-(2 • 5):-5	5-(-5 • 5):-5	1-(0 • 5):-5	0-(0 • 5):-5	0-(0 • 5):-5	0-(0 • 5):-5	0-(0 • 5):-5	4000-(0•5):-5
4-(0 • 7):-5	2-(2 • 7):-5	7-(-5 • 7):-5	0-(0 • 7):-5	1-(0 • 7):-5	0-(0 • 7):-5	0-(0 • 7):-5	0-(0 • 7):-5	6000-(0•7):-5
-1-(0 • 0):-5	0-(2 • 0):-5	0-(-5 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	1-(0 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	-200-(0•0):-5
0-(0 • 0):-5	-1-(2 • 0):-5	0-(-5 • 0):-5	0-(0 • 0):-5	0-(0 •0):-5	0-(0 • 0):-5	1-(0 • 0):-5	0-(0 • 0):-5	-200-(0•0):-5
0-(0 • -1):-5	0-(2 • -1):-5	-1-(-5 • -1):-5	0-(0 • -1):-5	0-(0•-1):-5	0-(0 • -1):-5	0-(0 •-1):-5	1-(0•-1):-5	-150-(0•-1):-5
3-(0 • 0):-5	-2-(2 • 0):-5	0-(-5 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5	0-(0 • 0):-5
0 : -5	2 : -5	-5 : -5	0 : -5	0 : -5	0 : -5	0 : -5	0 : -5	0 : -5

Отримуємо нову матрицю:

2	7	0	1	0	0	0	0	4000
4	4.8	0	0	1	0	0	0	6000
-1	0	0	0	0	1	0	0	-200
0	-1	0	0	0	0	1	0	-200
0	-0.4	0	0	0	0	0	1	-150
3	-2	0	0	0	0	0	0	0
0	-0.4	1	0	0	0	0	0	0

2-(3 • 7):-2	7-(-2 • 7):-2	0-(0 • 7):-2	1-(0 • 7):-2	0-(0 • 7):-2	0-(0 • 7):-2	0-(0 • 7):-2	0-(0 • 7):-2	4000-(0•7):-2
4-(3 • 4.8):-2	4.8-(-2 • 4.8):-2	0-(0 • 4.8):-2	0-(0 • 4.8):-2	1-(0 • 4.8):-2	0-(0 • 4.8):-2	0-(0 • 4.8):-2	0-(0 • 4.8):-2	6000-(0•4.8):-2
-1-(3 • 0):-2	0-(-2 • 0):-2	0-(0 • 0):-2	0-(0 • 0):-2	0-(0 • 0):-2	1-(0 • 0):-2	0-(0 • 0):-2	0-(0 • 0):-2	-200-(0 • 0):-2
0-(3 • -1):-2	-1-(-2 • -1):-2	0-(0 • -1):-2	0-(0 • -1):-2	0-(0 • -1):-2	0-(0 • -1):-2	1-(0 • -1):-2	0-(0 • -1):-2	-200-(0 • -1):-2
0-(3 • -0.4):-2	-0.4-(-2 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	1-(0 • -0.4):-2	-150-(0 • -0.4):-2
3 : -2	-2 : -2	0 : -2	0 : -2	0 : -2	0 : -2	0 : -2	0 : -2	0 : -2
0-(3 • -0.4):-2	-0.4-(-2 • -0.4):-2	1-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2	0-(0 • -0.4):-2

Отримуємо нову матрицю:

12.5	0	0	1	0	0	0	0	4000
11.2	0	0	0	1	0	0	0	6000
-1	0	0	0	0	1	0	0	-200
-1.5	0	0	0	0	0	1	0	-200
-0.6	0	0	0	0	0	0	1	-150
-1.5	1	0	0	0	0	0	0	0
-0.6	0	1	0	0	0	0	0	0

Оскільки в системі є одинична матриця, то в якості базисних змінних приймаємо

X = (4,5,6,7,8,2,3).

Висловимо базисні змінні через інші:

x₄ = -12.5x₁+4000
x₅ = -11.2x₁+6000
x₆ = x₁-200
x₇ = 1.5x₁-200
x₈ = 0.6x₁-150
x₂ = 1.5x₁
x₃ = 0.6x₁

Підставами їх в цільову функцію:

z = 30x₁+20(1.5x₁)+50(0.6x₁)
z = 90x₁Серед вільних членів bi є негативні значення, отже, отриманий базисний план не є опорним. Замість змінної x6 слід ввести змінну x1. Виконуємо перетворення симплексної таблиці методом Жордана-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	1500	0	0	0	1	0	12.5	0	0
x5	3760	0	0	0	0	1	11.2	0	0
x1	200	1	0	0	0	0	-1	0	0
x7	100	0	0	0	0	0	-1.5	1	0
x8	-30	0	0	0	0	0	-0.6	0	1
x2	300	0	1	0	0	0	-1.5	0	0
x3	120	0	0	1	0	0	-0.6	0	0
F(X0)	-18000	0	0	0	0	0	90	0	0

B	x1	x2	x3	x4	x5	x6	x7	x8
4000-(-200 • 12.5):-1	12.5-(-1 • 12.5):-1	0-(0 • 12.5):-1	0-(0 • 12.5):-1	1-(0 • 12.5):-1	0-(0 • 12.5):-1	0-(1 • 12.5):-1	0-(0 • 12.5):-1	0-(0 • 12.5):-1
6000-(-200 • 11.2):-1	11.2-(-1 • 11.2):-1	0-(0 • 11.2):-1	0-(0 • 11.2):-1	0-(0 • 11.2):-1	1-(0 • 11.2):-1	0-(1 • 11.2):-1	0-(0 • 11.2):-1	0-(0 • 11.2):-1
-200 : -1	-1 : -1	0 : -1	0 : -1	0 : -1	0 : -1	1 : -1	0 : -1	0 : -1
-200-(-200 • -1.5):-1	-1.5-(-1 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(1 • -1.5):-1	1-(0 • -1.5):-1	0-(0 • -1.5):-1
-150-(-200 • -0.6):-1	-0.6-(-1 • -0.6):-1	0-(0 • -0.6):-1	0-(0 • -0.6):-1	0-(0 • -0.6):-1	0-(0 • -0.6):-1	0-(1 • -0.6):-1	0-(0 • -0.6):-1	1-(0 • -0.6):-1
0-(-200 • -1.5):-1	-1.5-(-1 • -1.5):-1	1-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1	0-(1 • -1.5):-1	0-(0 • -1.5):-1	0-(0 • -1.5):-1
0-(-200 • -0.6):-1	-0.6-(-1 • -0.6):-1	0-(0 • -0.6):-1	1-(0 • -0.6):-1	0-(0 • -0.6):-1	0-(0 • -0.6):-1	0-(1 • -0.6):-1	0-(0 • -0.6):-1	0-(0 • -0.6):-1

еред вільних членів bi є негативні значення, отже, отриманий базисний план не є опорним. Замість змінної x8 слід ввести змінну x6.Виполняем перетворення симплексной таблиці методом Жордана-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	875	0	0	0	1	0	0	0	20.833
x5	3200	0	0	0	0	1	0	0	18.667
x1	250	1	0	0	0	0	0	0	-1.667
x7	175	0	0	0	0	0	0	1	-2.5
x6	50	0	0	0	0	0	1	0	-1.667
x2	375	0	1	0	0	0	0	0	-2.5
x3	150	0	0	1	0	0	0	0	-1
F(X1)	-22500	0	0	0	0	0	0	0	150

B	x1	x2	x3	x4	x5	x6	x7	x8
1500-(-30 • 12.5):-0.6	0-(0 • 12.5):-0.6	0-(0 • 12.5):-0.6	0-(0 • 12.5):-0.6	1-(0 • 12.5):-0.6	0-(0 • 12.5):-0.6	12.5-(-0.6 • 12.5):-0.6	0-(0 • 12.5):-0.6	0-(1 • 12.5):-0.6
3760-(-30 • 11.2):-0.6	0-(0 • 11.2):-0.6	0-(0 • 11.2):-0.6	0-(0 • 11.2):-0.6	0-(0 • 11.2):-0.6	1-(0 • 11.2):-0.6	11.2-(-0.6 • 11.2):-0.6	0-(0 • 11.2):-0.6	0-(1 • 11.2):-0.6
200-(-30 • -1):-0.6	1-(0 • -1):-0.6	0-(0 • -1):-0.6	0-(0 • -1):-0.6	0-(0 • -1):-0.6	0-(0 • -1):-0.6	-1-(-0.6 • -1):-0.6	0-(0 • -1):-0.6	0-(1 • -1):-0.6
100-(-30 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	-1.5-(-0.6 • -1.5):-0.6	1-(0 • -1.5):-0.6	0-(1 • -1.5):-0.6
-30 : -0.6	0 : -0.6	0 : -0.6	0 : -0.6	0 : -0.6	0 : -0.6	-0.6 : -0.6	0 : -0.6	1 : -0.6
300-(-30 • -1.5):-0.6	0-(0 • -1.5):-0.6	1-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(0 • -1.5):-0.6	-1.5-(-0.6 • -1.5):-0.6	0-(0 • -1.5):-0.6	0-(1 • -1.5):-0.6
120-(-30 • -0.6):-0.6	0-(0 • -0.6):-0.6	0-(0 • -0.6):-0.6	1-(0 • -0.6):-0.6	0-(0 • -0.6):-0.6	0-(0 • -0.6):-0.6	-0.6-(-0.6 • -0.6):-0.6	0-(0 • -0.6):-0.6	0-(1 • -0.6):-0.6

x₄ = -20.833x₈+875
x₅ = -18.667x₈+3200
x₁ = 1.667x₈+250
x₇ = 2.5x₈+175
x₆ = 1.667x₈+50
x₂ = 2.5x₈+375
x₃ = x₈+150

z = 30(1.667x₈+250)+20(2.5x₈+375)+50(x₈+150)

z = 150x₈+22500

x₄+20.833x₈=875
x₅+18.667x₈=3200
x₁-1.667x₈=250
x₇-2.5x₈=175
x₆-1.667x₈=50
x₂-2.5x₈=375
x₃-x₈=150

При обчисленнях значення Fc = 22500 тимчасово не враховуємо.

Вирішимо систему рівнянь щодо базисних змінних: x4, x5, x1, x7, x6, x2, x3

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X0 = (250,375,150,875,3200,50,175,0)

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	875	0	0	0	1	0	0	0	20.833
x5	3200	0	0	0	0	1	0	0	18.667
x1	250	1	0	0	0	0	0	0	-1.667
x7	175	0	0	0	0	0	0	1	-2.5
x6	50	0	0	0	0	0	1	0	-1.667
x2	375	0	1	0	0	0	0	0	-2.5
x3	150	0	0	1	0	0	0	0	-1
F(X0)	0	0	0	0	0	0	0	0	-150

D_i = b_i / a_i8
min (875 : 20.833 , 3200 : 18.667 ) = 42

Дозволяючий елемент дорівнює (20.833) і знаходиться на перетині ведучого рядка і ведучого рядка.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x4	875	0	0	0	1	0	0	0	20.833	42
x5	3200	0	0	0	0	1	0	0	18.667	171.429
x1	250	1	0	0	0	0	0	0	-1.667	-
x7	175	0	0	0	0	0	0	1	-2.5	-
x6	50	0	0	0	0	0	1	0	-1.667	-
x2	375	0	1	0	0	0	0	0	-2.5	-
x3	150	0	0	1	0	0	0	0	-1	-
F(X1)	0	0	0	0	0	0	0	0	-150	0

Формуємо наступну частину симплексного таблиці. Замість змінної x4 в план 1 увійде змінна x8. Отримуємо нову симплекс-таблицю:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	42	0	0	0	0.048	0	0	0	1
x5	2416	0	0	0	-0.896	1	0	0	0
x1	320	1	0	0	0.08	0	0	0	0
x7	280	0	0	0	0.12	0	0	1	0
x6	120	0	0	0	0.08	0	1	0	0
x2	480	0	1	0	0.12	0	0	0	0
x3	192	0	0	1	0.048	0	0	0	0
F(X1)	6300	0	0	0	7.2	0	0	0	0

Серед значень індексного рядка немає від'ємних. Тому ця таблиця визначає оптимальний план завдання. Остаточний варіант симплекс-таблиці:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	42	0	0	0	0.048	0	0	0	1
x5	2416	0	0	0	-0.896	1	0	0	0
x1	320	1	0	0	0.08	0	0	0	0
x7	280	0	0	0	0.12	0	0	1	0
x6	120	0	0	0	0.08	0	1	0	0
x2	480	0	1	0	0.12	0	0	0	0
x3	192	0	0	1	0.048	0	0	0	0
F(X2)	6300	0	0	0	7.2	0	0	0	0

Оптимальний план:

x₁ = 320, x₂ = 480, x₃ = 192

z = 30•320 + 20•480 + 50•192 = 28800.