2. Практична частина
2.1 Приклад 1.
Задача з мережі інтернет: для виготовлення товару A, B і C підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A, B і C а також загальна кількість сировини наведені в наступній таблиці:
Види сировини |
Витрати сировини на виготовлення одиниці продукції |
Запаси сировини |
||
А |
В |
С |
||
I |
18 |
15 |
12 |
360 |
II |
6 |
4 |
8 |
192 |
III |
5 |
3 |
3 |
180 |
Ціна одиниці продукції |
9 |
10 |
16 |
|
Норми витрат сировини на виготовлення одиниці продукції
Складемо такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.
Позначмо через x1 – кількість товару А; x2 – кількість товару В; x3 – кількість товару С. Тоді математична модель даної задачі буде наступна: знайти максимум функції F при обмеженнях:
Для побудови першого опорного плану систему нерівностей приведемо в систему рівнянь, шляхом введення додаткових змінних x4, x5, x6 (іншими словами запишемо систему обмежень у канонічній формі). У цільову функцію ці змінні увійдуть з нульовими коефіцієнтами:
Запишемо дану задачу у векторній формі і побудуємо першу симплекс таблицю:
№ |
Базис |
Cb |
P0 |
9 |
10 |
16 |
0 |
0 |
0 |
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
||||
1 |
P4 |
0 |
360 |
18 |
15 |
12 |
1 |
0 |
0 |
2 |
P5 |
0 |
192 |
6 |
4 |
8 |
0 |
1 |
0 |
3 |
P6 |
0 |
180 |
5 |
3 |
3 |
0 |
0 |
1 |
4 |
|
|
0 |
-9 |
-10 |
-16 |
0 |
0 |
0 |
Початковий опорний плану задачі лінійного програмування
, де елементи F0 та ∆j≥0, (j= 1,n) четвертого, оцінкового, рядка, обчислюються за формулами (3), (4) відповідно.
Після обчислення всіх оцінок отриманий план перевіримо на оптимальність. Для цього, як уже зазначалься вище, переглянувши елементи оцінкового рядка, бачимо, що у даному прикладі перший опорний план не є оптимальним (серед елементів ∆j є такі, що мають від’ємне значення). Тому, слідуючи вище розглянутому алгоритму симплекс методу, переходимо до іншого опорного рішення.
Для цього серед усіх ∆j вибираємо те, яке по абсолютній величині приймає максимальне значення. В нашому випадку таким є ∆3=-16. Тобто, вектор p3 потрібно ввести в базис.
Далі, з’ясуємо на місце якого вектора базису вводимо p3. Для цього визначаємо:
Таким чином розв’язуючим буде елемент a23=8, який вказує на те, що виводити з базису необхідно вектор p5.
Наступним кроком буде побудова другої симплекс таблиці і визначення всіх її коефіцієнтів згідно нового базису:
№ |
Базис |
Cb |
P0 |
9 |
10 |
16 |
0 |
0 |
0 |
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
||||
1 |
P4 |
0 |
72 |
9 |
0 |
0 |
1 |
-1,5 |
0 |
2 |
P3 |
16 |
24 |
0,75 |
0,5 |
1 |
0 |
0,125 |
0 |
3 |
P6 |
0 |
108 |
2,75 |
1,5 |
0 |
0 |
-0,375 |
1 |
4 |
|
|
384 |
3 |
-2 |
0 |
0 |
2 |
0 |
Другий опорний план задачі лінійного програмування
Після того, як ми заповнили останній (оцінковий) рядок другої симплекс таблиці, робимо висновок, що другий опорний план також не є оптимальним (серед елементів ∆j містяться від’ємні значення). Тому, переходимо до третього опорного плану, для якого, як можна побачити нижче, умова оптимальності виконується, і який приймаємо в якості оптимального розв’язку заданої задачі лінійного програмування:
№ |
Базис |
Cb |
P0 |
9 |
10 |
16 |
0 |
0 |
0 |
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
||||
1 |
P2 |
10 |
8 |
1 |
1 |
0 |
0,111 |
-0,167 |
0 |
2 |
P3 |
16 |
20 |
0,25 |
0 |
1 |
-0,05 |
0,2 |
0 |
3 |
P6 |
0 |
96 |
1,25 |
0 |
0 |
-0,167 |
-0,125 |
1 |
4 |
|
|
400 |
5 |
0 |
0 |
0,222 |
1,667 |
0 |
Оптимальний план задачі лінійного програмування