Норми витрат ресурсів на одиницю продукції
Ресурс |
Норми витрат ресурсів на одиницю продукції по видах продукції |
Запас ресурсу | |||
А |
В |
С |
| ||
1 |
2 |
1 |
2 |
= 120 | |
2 |
3 |
1 |
2 |
= 200 | |
3 |
2 |
2 |
1 |
= 120 | |
|
= 2 |
= 3 |
= 4 |
|
Відома ціна одиниці продукції кожного виду: для А - ; для В - ; для С - (у. о.).
Визначити оптимальний план виробництва продукції в умовах обмеженості ресурсів, який дасть виробництву найбільший. Завдання розв'язати симплексним методом.
Розв'язання:
Припустимо, що буде виготовлено одиниць виробуА, одиниць виробу В, одиниць виробуС. Тоді для виробництва такої кількості виробів потрібно затратити ум. од. сировини першого виду.
Так як виробництво забезпечено сировиною першого виду в кількості 120 ум. од., то повинна виконуватися нерівність:
Аналогічні міркування відносно забезпеченості виробництва сировиною другого та третього виду приведуть до наступних нерівностей:
При цьому, так як кількість виробів не може бути від'ємною, то
Тоді прибуток від реалізації даних виробів складе
Математична модель вихідної задачі:
Знайдемо розв'язок прямої задачі лінійного програмування симплекс–методом.
Запишемо цю задачу в канонічній формі задачі лінійного програмування. Для цього перейдемо від обмежень-нерівностей до обмежень-рівностей. Введемо три додаткові змінні, в результаті чого обмеження запишуться у вигляді системи рівнянь:
Ці додаткові змінні мають наступний економічний зміст – не використана при даному плані виробництва кількість сировини того чи іншого виду. Наприклад, - це невикористана кількість сировини першого виду.
Перетворену систему рівнянь запишемо у векторній формі:
де
Оскільки серед векторів є три одиничних вектори, для даної задачі можна безпосередньо записати опорний план: який визначається системою трьохмірних одиничних векторів , які утворюють базис трьохвимірного векторного простору.
Складаємо симплекс-таблицю для І ітерації, підраховуємо значення та перевіряємо вихідний опорний план на оптимальність:
- обчислюється скалярний добуток векторів та. А дляобчислюється скалярний добуток векторівта:
Для векторів базису
Симплекс-таблиця І ітерації:
і |
Базис |
2 |
3 |
4 |
0 |
0 |
0 | ||
1 |
0 |
120 |
2 |
1 |
2 |
1 |
0 |
0 | |
2 |
0 |
200 |
3 |
1 |
2 |
0 |
1 |
0 | |
3 |
0 |
120 |
2 |
2 |
1 |
0 |
0 |
1 | |
|
|
|
-2 |
-3 |
-4 |
0 |
0 |
0 |
Як видно з таблиці, значення всіх основних змінних рівні нулю, а додаткові змінні приймають свої значення у відповідності з обмеженнями задачі. Ці значення змінних відповідають такому «плану», при якому нічого не виробляється, сировина не використовується і значення цільової функції рівне нулю (тобто прибуток відсутній). Цей план, звичайно, не буде оптимальним.
Це видно ще й з 4-ого рядка таблиці, так як у ній є 3 від’ємних числа. Від’ємні числа не лише вказують на можливість збільшення загальної вартості продукції, що виробляється, але й показують, на скільки збільшиться ця сума при введенні в план одиниці певного виду продукції.
З економічної точки зору найбільш доцільним є включення в план виробництва виробів С. Це ж необхідно зробити і на основі формальної ознаки симплексного методу, оскільки максимальне за абсолютною величиною від’ємне число стоїть в 4-ому рядку стовпця вектора. Визначаємо вектор, який потрібно виключити з базису. Для цього знаходимодля, тобто –
Отже, вектор виключаємо з базису. Стовпчик вектора і перший рядок являються направляючими. Складаємо таблицю для ІІ ітерації.
Спочатку заповнюємо рядок вектора, введеного в базис, тобто рядок, номер якого співпадає з номером направляючого рядка. Отже, елементи 1-го рядка отримуються з відповідних елементів їх діленням на розв'язувальний елемент (тобто на 2). При цьому в стовпці записуємо коефіцієнт , який знаходиться в стовпці введеного в базис вектора.
Потім заповнюємо елементи стовпців для векторів, які входять в новий базис. В цих стовпцях на перетині рядків та стовпців однойменних векторів ставимо 1, а всі інші елементи – 0.
Для визначення інших елементів застосовуємо правило трикутника.
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Симплекс-таблиця ІІ ітерації.
і |
Базис |
2 |
3 |
4 |
0 |
0 |
0 | ||
1 |
4 |
60 |
1 |
1/2 |
1 |
1/2 |
0 |
0 | |
2 |
0 |
200-2*60=80 |
3-2*1=1 |
1-2*1/2 =0 |
0 |
0-2*1/2 = - 1 |
1 |
0 | |
3 |
0 |
120-1*60=60 |
2-1*1=1 |
2-1*1/2 =3/2 |
0 |
0-1*1/2 = -1/2 |
0 |
1 | |
|
|
|
2 |
-1 |
0 |
2 |
0 |
0 |
Отже, кінцева таблиця ІІ ітерації готова:
і |
Базис |
2 |
3 |
4 |
0 |
0 |
0 | ||
1 |
4 |
60 |
1 |
1/2 |
1 |
1/2 |
0 |
0 | |
2 |
0 |
80 |
1 |
0 |
0 |
- 1 |
1 |
0 | |
3 |
0 |
60 |
1 |
3/2 |
0 |
-1/2 |
0 |
1 | |
|
|
|
2 |
-1 |
0 |
2 |
0 |
0 |
Цей план не буде оптимальним, це видно з 4-ого рядка таблиці, так як у ній є 1 від’ємне число.
Включаємо в план виробництва виріб В, оскільки від’ємне число стоїть в 4-ому рядку стовпця вектора . Визначаємо вектор, який потрібно виключити з базису. Для цього знаходимодля, тобто –
Отже, вектор виключаємо з базису. Стовпчик вектора і третій рядок являються направляючими. Складаємо таблицю для ІІI ітерації.
Спочатку заповнюємо рядок вектора, введеного в базис, тобто рядок, номер якого співпадає з номером направляючого рядка. Отже, елементи 3-го рядка отримуються з відповідних елементів їх діленням на розв'язувальний елемент (тобто на 3/2). При цьому в стовпці записуємо коефіцієнт , який знаходиться в стовпці введеного в базис вектора.
Потім заповнюємо елементи стовпців для векторів, які входять в новий базис. В цих стовпцях на перетині рядків та стовпців однойменних векторів ставимо 1, а всі інші елементи – 0.
Для визначення інших елементів застосовуємо правило трикутника.
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Симплекс-таблиця ІІI ітерації.
і |
Базис |
2 |
3 |
4 |
0 |
0 |
0 | ||
1 |
4 |
60-1/2*40 =40 |
1-1/2*2/3 =2/3 |
0 |
1 |
1/2-1/2* (-1/3)= 2/3 |
0 |
0-1/2*2/3 = - 1/3 | |
2 |
0 |
80-0*40 =80 |
1-0*2/3 =1 |
0 |
0 |
-1-0* (-1/3) = - 1 |
1 |
0-0*2/3 =0 | |
3 |
3 |
40 |
2/3 |
1 |
0 |
-1/3 |
0 |
2/3 | |
|
|
|
8/3 |
0 |
0 |
5/3 |
0 |
2/3 |
Отже, кінцева таблиця ІІІ ітерації готова:
і |
Базис |
2 |
3 |
4 |
0 |
0 |
0 | ||
1 |
4 |
40 |
2/3 |
0 |
1 |
2/3 |
0 |
- 1/3 | |
2 |
0 |
80 |
1 |
0 |
0 |
- 1 |
1 |
0 | |
3 |
3 |
40 |
2/3 |
1 |
0 |
-1/3 |
0 |
2/3 | |
|
|
|
8/3 |
0 |
0 |
5/3 |
0 |
2/3 |
Новим опорним планом задачі є план . При даному плані виробництва виготовляється 40 виробів В, 40 виробів С і залишаються невикористаними 80 ум. од. сировини ІІ виду. Прибуток від виготовленої продукції при цьому плані 280 ум. од.
Знайдений план задачі являється оптимальним. Це видно з 4-ого рядка таблиці , оскільки всі числа додатні.
Отже, оптимальний план –.