Застосування теорем подвійності для аналізу оптимальних рішень в задачах економіки праці

Розглянемо економічну інтерпретацію прямої і двоїстої задач і використання властивостей оптимальних оцінок для аналізу результатів на прикладі задачі найкращого використання ресурсів (про випуск продукції).

Приклад. Підприємство випускає чотири види продукції П₁, П₂, П₃, П₄, використовуючи три типи трудових ресурсів (за професіями). Обсяги ресурсів, норми трудомісткості одиниці продукції і прибуток від реалізації одиниці продукції наведено в табл. 2.

Таблиця 2 – Вихідні дані

Потрібно: 1) знайти оптимальний план випуску продукції за критерієм максимального прибутку (вважаємо, що ринок збуту не обмежений); 2) знайти рішення двоїстої задачі і навести його економічну інтерпретацію; 3) виконати аналіз рішення на основі властивостей оптимальних оцінок.

Для сформульованої задачі оптимізації виробничої програми складемо моделі прямої та двоїстої задач:

Вихідна задача	Двоїста задача
F = 60х1 + 70х2 + 120х3 + 130х4 → max 1х1 + 1х2 + 1х3 + 1х4 ≤ 16 4х1 + 6х2 + 10х3 + 13х4 ≤ 100 6х1 + 5х2 + 4х3 + 3х4 ≤ 110 x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0	L = 16 y1 + 100 y2 + 110 y3 → min (урахування интересу покупця) y1 ≥ 0 y2 ≥ 0 y3 ≥ 0 1 y1 + 4 y2 + 6 y3 ≥ 60 (урахування 1 y1 + 6 y2 + 5 y3 ≥ 70 інтересів 1 y1 + 10 y2 + 4 y3 ≥ 120 продавця) 1 y1 + 13 y2 + 3 y3 ≥ 130

Перетворимо моделі до канонічного виду:

Додаткові змінні x_j (j = 5, 6, 7) вихідної задачі демонструють можливий резерв відповідного ресурсу. Додаткові змінні y_i (i = 4, 5, 6, 7) двоїстої задачі характеризують можливий збиток (з точки зору поставленої мети) при випуску одиниці відповідного продукту. Рішення завдання виконано симплекс-методом. Оптимальний план представлено в табл. 3.

Таблиця 3 – Оптимальний план випуску продукції

Cj	Базис	B
х1	х2	х3	х4	х5	х6	х7
	х1
	х3
	х7
∆ j=zj - cj
		y4	y5	y6	y7	y1	y2	y3

Оптимальне рішення задач:

вихідної – у підсумковому стовпчику В:

х₁ = 10, х₂ = 0, х₃ = 6, х₄ = 0; х₅ = 0, х₆ = 0, х₇ = 26; F_max = 1320;

двоїстої – у цільовому рядку ∆ _j=z_j - c_j:

y₁ = 20, y₂ = 10, y₃ = 0; y₄ = 0, y₅ = 10, y₆ = 0, y₇ = 20; L_min = 1320.

Як виходить з умов задачі, значення основних змінних х₁, х₂, х₃, х₄ представляють собою випуск продукції в оптимальному плані. З рішення задачі видно, що оптимальний план включає випуск 10 одиниць продукції П₁ та 6 одиниць П₃, що забезпечує отримання максимального прибутку у розмірі 1320 грн. Випуск продукції П₂ і П₄ планом не передбачено, тобто х₂ = х₄ = 0.

Величина додаткових змінних вихідної задачі говорить про те, що в оптимальному плані перший і другий ресурси дефіцитні (відповідні додаткові змінні х₅=х₆=0), тобто повністю витрачені, а ресурс третього виду («фрезерувальники») не є дефіцитним, невикористаний залишок складає 26 люд.-год. (додаткова змінна х₇ є базисною і дорівнює 26 люд.-год).

Виконаємо аналіз рішення задачі на основі використання властивостей оптимальних оцінок. Перша властивість оптимальних оцінок дозволяє зробити висновок про те, що отримані рішення дійсно оптимальні, оскільки оцінка ресурсів (мінімум витрат) дорівнює максимальному результату (загальна сума прибутку):

L_min = 16 y₁ + 100 y₂ + 110 y₃ = 16 × 20 + 100 × 10 + 110 × 0 = 1320 = F_max.

Оптимальні оцінки (відповідно до другої властивості) підтверджують висновок про дефіцитність трудових ресурсів: «токарі» і «слюсарі» використані повністю, їх оцінки позитивні (y₁=20, y₂=10), а ресурс «фрезерувальники» недовикористано (y₃ = 0).

Тут двоїста оцінка ресурсу третього виду y ₃ відповідає змінній х₇ – додаткової змінної в обмеженні за кількістю третього ресурсу вихідної задачі. В оптимальному плані виробництва змінна х₇ є базисною (табл. 3, де х₇=26) і показує, що ресурс «фрезерувальники» недовикористано, резерв складає 26 люд.-год.), а у оптимальному плані двоїстої задачі y₃ = 0 характеризує, що цінність кожної додаткової одиниці цього ресурсу дорівнює нулю.

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

основні змінні додаткові змінні

вихідної задачі вихідної задачі

.

додаткові змінні основні змінні

двоїстої задачі двоїстої задачі

Вільним же змінним х₅, х₆ відповідають базисні y₁, y₂, що свідчать про дефіцитність відповідних ресурсів і характеризують вклад, який вносить кожна додаткова одиниця цих ресурсів у досягнення мети (максимізацію прибутку).

Третя властивість оптимальних оцінок дозволяє зробити висновок про те, що виготовлення продукції першого і третього видів є рентабельним (вигідним). Для цих продуктів обмеження двоїстої задачі виконуються як рівності, тобто оцінка ресурсів, витрачених на виробництво продукції, збігається з доходом від її реалізації:

1 y₁ + 4 y₂ + 6 y₃ = 1× 20 + 4 × 10 + 6 × 0 = 60,

1 y₁ + 10 y₂ + 4 y₃ = 1 × 20 + 10 × 10 + 4 × 0 = 120.

Випуск продукції другого і четвертого видів є збитковим (сприяє зменшенню загальної суми прибутку), і тому оптимальним планом не передбачений. Відповідні обмеження двоїстої задачі виконуються як строгі нерівності (витрати перевищують результат):

1 y₁ + 6 y₂ + 5 y₃ = 1 × 20 + 6 × 10 + 5 × 0 = 80 > 70,

y₅ = 80 – 70 = 10,

1 y₁ + 13 y₂ + 3 y₃ = 1 × 20 + 13 × 10 + 3 × 0 = 150 > 130,

y₇ = 150 – 130 = 20.

Додаткові змінні y₅ і y₇ показують, наскільки зменшиться загальна сума прибутку (1320 грн.) при виготовленні одиниці продукції відповідно П₂ та П₄.

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

Коефіцієнти а _ij стовпців основних змінних (х₁, х₂, х₃, х₄) (табл. 3) – так звані коефіцієнти заміщення – показують, наскільки зміниться (збільшиться при а _ij < 0 і зменшиться при а _ij > 0) величина i-ї базисної змінної при введені до базису j-ї вільної змінної в кількості 1. Так, при необхідності виробництва не потрапившої до оптимального плану одиниці продукції П₂ бачимо (стовпчик х₂ табл. 3), що випуск першого продукту скоротився на , третього продукту – на , невикористаний залишок третього ресурсу збільшиться на . Простежимо за перерозподілом ресурсів.

За рахунок скорочення випуску П₁ і П₃ вивільняться ресурси у кількості:

1-й ресурс: 1 × + 1 × = 1;

2-й ресурс: 6 × + 4 × = ;

3-й ресурс: 4 × + 10 × = 6.

Cj	Базис	B
х1	х2	х3	х4	х5	х6	х7
	х1
	х3
	х7
∆ j=zj - cj
		y4	y5	y6	y7	y1	y2	y3

На один виріб П₂ необхідно 1, 5 і 6 одиниць ресурсів відповідно 1, 2 та 3 виду. Таким чином, ресурси, що було вивільнено, достатньо як раз на один виріб П₂. При цьому прибуток зміниться таким чином:

- з-за скорочення випуску П₁ загальна сума прибутку зменшиться на:

60 × 2/3 = 40,

- з-за скорочення випуску П₃ загальна сума прибутку зменшиться на:

120 × 1/3 = 40,

- випуск одиниці продукту П₂ відповідає тому, що загальна сума прибутку збільшиться на 70 грн.

Загальна зміна прибутку складе: – 40 – 40 + 70 = -10 грн., що співпадає зі значенням відповідної додаткової двоїстої змінної у₅. Аналогічні висновки можна виконати і для інших видів продукції.

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

Так, для отримання доходу, більшого 1320 грн., необхідно збільшити обсяги дефіцитних ресурсів. Так, слід домогтися збільшення кількості ресурсу «токарі», так як в розрахунку на додаткову одиницю цього ресурсу буде отримано додатковий прибуток у розмірі 20 грн. (y₁ = 20), що вдвічі перевищує величину додаткового доходу у розрахунку на додаткову одиницю ресурсу «слюсарі» (y₂ = 10). Таким чином, в даному прикладі ресурс «токарі» є більш цінним ресурсом, ніж «слюсарі».

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

Так, коефіцієнти, що містяться в стовпцях додаткових змінних (х₅, х₆, х₇) табл. 3 являють собою двоїсті оцінки відповідних базисних змінних, тобто вони показують зміну базисних змінних при збільшенні відповідного ресурсу на одиницю. Розглянемо вплив трудового ресурсу, якому в табл. 3 відповідає стовпець х₅.

Так, при збільшенні ресурсу «токарі» на одиницу, випуск продукції П₁ (змінна х₁) збільшиться на 5/3, продукту П₃ (змінна х₃) – зменшиться на 2/3, резерв по ресурсу «фрезерувальники» (змінна х₇) зменшиться на 22/3 люд.-год. Отже, при збільшенні ресурсу «токарі» виявляється більш вигідним зменшити випуск продукції П₃, а вивільнені ресурси і додану одиницю ресурсу використовувати для додаткового випуску продукції П₁. При цьому за рахунок зменшення випуску продукції П₃ дохід зменшиться на величину 120 х 2/3 = 80 грн., а за рахунок збільшення випуску П₁ збільшиться на 60 х 5/3 = 100 грн. Загальний приріст доходу складе при цьому 100 – 80 = 20 грн., що відповідає оптимальній оцінці ресурсу «токарі» (у₁ = 20). Аналогічні міркування можна провести і для інших ресурсів.

Таким чином, оцінка ресурсу показує, наскільки зміниться величина критерію оптимальності при зміні кількості даного ресурсу на одиницю. Збільшення ресурсу збільшує значення цільової функції (прибутку), що максимізується, зменшення – зменшує (для недефіцитного ресурсу – не змінює).

Аналіз додаткових умов

Припустимо, додатково до продукції, випуск якої спочатку передбачався, з'явилася можливість випускати продукцію П₅ з такими характеристиками:

При цьому загальна кількість наявних ресурсів не змінилася. Чи доцільно включати випуск продукції П₅ до оптимального плану, тобто чи забезпечить випуск продукції П₅ збільшення цільової функції, отриманої в табл. 3?

Для відповіді на поставлене питання складемо обмеження двоїстої задачі по додатковій продукції:

1у₁ + 8у₂ + 6у₃ ³ 70. (11)

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

1 × 20 + 8 × 10 + 6 × 0 = 100 > 70.

Отже, включення продукції П₅ до оптимального плану є недоцільним, оскільки це призвело б до збитку на 30 грн. з 1 од. продукції та зменшило б максимальне значення цільової функції.

Обмеження (11) можна також використовувати для визначення об'єктивно обґрунтованої ціни продукції, що підлягає випуску. Якщо потрібно забезпечити випуск продукції П₅ із заданими нормами витрат трудових ресурсів, то для того, щоб ця продукція була рентабельною і не знижувала досягнутого показника ефективності (прибутку), її питомий прибуток має бути не меншим ніж100 грн.

Післяоптимізаційний аналіз

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

Аналіз чутливості виконується після отримання оптимального рішення задачі лінійного програмування. Його мета – визначити, чи приведе зміна коефіцієнтів вихідної задачі до зміни поточного оптимального рішення, і якщо так, то як знайти нове оптимальне рішення (якщо воно існує). Досліджується чутливість рішення при зміні коефіцієнтів цільової функції (прибуток, випуск, витрати і т.д.); обмежень за ресурсами (трудовими, сировинними, фінансовими та ін.); коефіцієнтів при змінних в обмеженнях задачі (норми витрати ресурсів); граничних умов (планових завдань на випуск).

Дамо ресурсу «Токарі» прирощення у розмірі Db₁. Тоді відповідне обмеження в моделі прийме вигляд:

1х₁ + 1х₂ + 1х₃ + 1х₄ £ 16 + Db₁.

Розв’язавши задачу отримаємо симплекс табл. 4.

Порівнявши табл. 4 з табл. 3, бачимо, що змінився тільки підсумковий стовпець, його елементи дорівнюють сумі значень базисних змінних з помноженням відповідного елемента стовпця додаткової змінної х₅ на прирощення ресурсу Db₁.

Таблиця 4 – Оптимальний план випуску продукції з урахуванням приросту ресурсу «Токарі»

Cj	Базис	B
х1	х2	х3	х4	х5	х6	х7
	х1	10 + Db1
	х3	6 Db1
	х7	26 Db1
∆ j=zj - cj	1320 +20·Db1
y4	y5	y6	y7	y1	y2	y3

Щоб рішення, представлене в табл. 4, залишалося опорним, необхідно виконання умов невід'ємності значень базисних змінних:

10 + Db₁ ³ 0

6 Db₁ ³ 0

26 Db₁ ³ 0.

Звідси знаходимо межі зміни Db₁:

;

;

.

Тоді для збереження структури оптимального плану зміна приросту ресурсу «Токарі» може перебувати в межах .

Перехід від Db₁ до b₁ здійснюється за залежностями:

Таким чином, якщо зміна запасу трудових ресурсів буде здійснюватися у межах , то структура базису оптимального плану (номенклатура продукції) збережеться, і величина оптимальних оцінок залишиться без зміни. При цьому кількість продукції буде іншою. Підставивши конкретні значення збільшення ресурсу в наступні співвідношення:

х₃ = 10 + Db₁;

х₆ = 6 Db₁;

х₇ = 26 Db₁,

отримаємо нові значення базисних змінних. При цьому цільова функція досягає розміру F = 1320 +20Db₁.

Наприклад, якщо відвернути шість одиниць ресурсу «Токарі» на інші роботи, то оптимальним планом з урахуванням Db₁ = -6 будуть наступні показники:

х^*₁ = 10 + 5/3·(-6) = 10 – 9, 9999996 = 0, 0000004 = 0;

х^*₃ = 6 - 2/3·(-6) = 6 + 3, 99999 = 9, 4;

F^* = 1320 + 20·(-6) = 1200.

Таким чином, зменшення обсягу ресурсу «Токарі» на 6 люд.-год., або на 37, 5%, веде до скорочення цільової функції на 9, 09%.

Якщо ж зміна ресурсу «Токарі» вийде за встановлені межі, то умова допустимості порушиться, і рішення перестане бути оптимальним. Новий варіант оптимального рішення тоді можна знайти за допомогою двоїстого симплекс-методу.

Аналогічно можна отримати межі зміни ресурсу «Слюсарі»: . Структура оптимального плану збережеться в межах (табл. 5).

Таблиця 5 – Оптимальний план випуску продукції з урахуванням приросту ресурсу «Слюсарі»

Cj	Базис	B
х1	х2	х3	х4	х5	х6	х7
	х1	10 - 1/6·Db2
	х3	6 + 1/6·Db2
	х7	26 + 1/3·Db2
∆ j=zj - cj	1320 +10·Db2
y4	y5	y6	y7	y1	y2	y3

На базі цих залежностей можна отримати відповідь на питання: «Скільки необхідно випустити продукції для забезпечення максимального прибутку при збільшенні запасу ресурсу «Слюсарі» на 10 або 15 одиниць?».

Припустимо, що відхилення в запасі ресурсу «Фрезерувальники» складе Δ b₃, тоді в математичній моделі обмеження для сировини має вигляд:

6х₁ + 5х₂ + 4х₃ + 3х₄ ≤ 110 + Δ b₃.

Після знаходження рішення з урахуванням Δ b₃ отримаємо симплекс-таблицю.

Таблиця 6 – Оптимальний план випуску продукції з урахуванням приросту ресурсу «Фрезерувальники»

Cj	Базис	B
х1	х2	х3	х4	х5	х6	х7
	х1
	х3
	х7	26 +1× Db3
∆ j=zj - cj	1320 +0× Db3
y4	y5	y6	y7	y1	y2	y3

Рішення буде залишатися оптимальним за умови:

26 +1× Db₃ ³ 0.

Тому -26 £ Db₃ £ ¥;

Остаточно отримаємо . Таким чином, при зміні ресурсу «Фрезерувальники» в цих межах зберігається оптимальний план. Єдина змінювана величина – додаткова змінна по цьому ресурсу, тобто резерв даного ресурсу.

Аналіз показує, що двоїсті оцінки зберігають своє значення в тому ж самому інтервалі зміни ресурсів, при якому зберігається структура оптимального плану. Отже, в нашому випадку для ресурсу «Токарі» двоїсті оцінки справедливі при зміні ресурсу в інтервалі .

Аналогічно аналізу впливу ресурсів можна також встановити ступінь впливу коефіцієнтів с_j у цільовій функції, а також норм витрати трудових ресурсів a_ij.

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

Питання для самоконтролю:

1. У чому різниця між прямим та двоїстим рішенням задачі?

2. У чому різниця між симметричним і несиметричним представленням задачі?

3. Охарактеризуйте основні теореми двоїстостію

Рекомендована література:

основна: [1, 2, 4, 5, 6, 9];

додаткова: [3, 7, 8, 10-21].