Аналіз лінійних моделей оптимізаційних задач

Размещено на http://www.allbest.ru/

ЛЕКЦІЯ

АНАЛІЗ ЛІНІЙНИХ МОДЕЛЕЙ ОПТИМІЗАЦІЙНИХ ЗАДАЧ

Анотація

економічний модель імітація виробництво

Приклад економічної інтерпретації пари спряжених задач. Аналіз розв'язків спряжених економіко-математичних задач. Оцінка рентабельності продукції, яка виробляється, і нової продукції. Аналіз обмежень дефіцитних і недефіцитних ресурсів. Інтервали можливої зміни обсягів дефіцитних ресурсів. Дослідження взаємозамінювання ресурсів. Аналіз коефіцієнтів цільової функції. Приклад практичного використання двоїстих оцінок у аналізі економічної задачі.

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

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

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

Побудована економіко-математична модель може бути використана для імітації процесу виробництва. Це дає змогу перевірити:

1) за яких умов оптимальний план є стійким;

2) чи є вигідним додаткове залучення ресурсів;

3) як зміниться ефективність виробництва в разі загострення конкуренції на ринку збуту (оцінити виправданість у цій ситуації зниження цін на продукцію);

4) доцільність виробництва нової продукції;

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

Зауважимо, що дослідження планів, отриманих за економіко-математичними моделями, на стійкість, а також оцінювання ситуацій мають виконуватися в передплановому періоді.

1. Приклад економічної інтерпретації пари спряжених задач

Економічну інтерпретацію прямої та двоїстої задач і проведення післяоптимізаційного аналізу розглянемо на прикладі задачі оптимального використання обмежених ресурсів.

Для виробництва n видів продукції використовується m видів ресурсів, запаси яких обмежені значеннями . Норми витрат кожного ресурсу на виробництво одиниці продукції становлять . Ціна реалізації одиниці продукції j-го виду дорівнює . Математична модель цієї задачі має такий вигляд:

; (6.1)

; (6.2)

. (6.3)

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

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

; (6.4)

; (6.5)

. (6.6)

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

Розглянемо використання двоїстих оцінок на прикладі аналізу економіко-математичних моделей виду (6.1)-(6.3) та (6.4)-(6.6).

Приклад 1. Деяке підприємство виробляє чотири види продукції А, В, С, і D, використовуючи для цього три види ресурсів 1, 2 і 3. Норми витрат ресурсів на виробництво одиниці кожного виду продукції (в умовних одиницях) наведено в табл. 1.

Таблиця 1

Відомі також ціни реалізації одиниці продукції кожного виду: для продукції А- 2 ум. од., для продукції В і D - по 4 ум. од., для продукції С - 3 ум. од.

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

Розв'язання. Математичні моделі прямої (6.7) та двоїстої (6.8) задач мають такий вигляд:

(6.7)

де х_j - обсяг виробництва продукції j-го виду ;

(6.8)

де y_i - оцінка одиниці і-го виду ресурсу .

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

2. Аналіз розв'язків спряжених економіко-математичних задач

Наведена симплекс-таблиця містить оптимальні плани прямої та двоїстої задач. Оптимальний план прямої задачі позначимо через , а оптимальний план двоїстої - Y^*.

Х^* = (0; 0; 35; 45; 0; 30; 0), max Z = 285;

Y^* = (4; 0; 3) = (1/2; 0; 2);

min F = 250/2 + 160 = 285 = max Z.

Основні змінні оптимального плану прямої задачі означають обсяги виробництва відповідних видів продукції. Отже, випуск продукції видів А та В не передбачається (х₁ = х₂ = 0), а С і D - планується у кількості відповідно 35 та 45 од.

Додаткові змінні оптимального плану прямої задачі х₅, х₆, х₇ характеризують залишки (невикористані обсяги) ресурсів відповідно 1, 2 та 3. Оскільки х₆=30, то це означає, що другий ресурс використовується у процесі виробництва продукції не повністю. Перший та третій ресурси за оптимального плану виробництва будуть використані повністю, бо х₅ = х₇ = 0.

За такого плану виробництва продукції підприємство отримало б найбільшу виручку обсягом 285 ум.од.

Відомо, що між змінними прямої та двоїстої задач існує відповідність виду:

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

Основні змінні двоїстої задачі за наведеною схемою відповідають додатковим змінним прямої, що характеризують обсяги невикористаних ресурсів. Отже, отримані значення змінних у₁, у₂ та у₃ можна використати для відносної кількісної оцінки важливості відповідних видів ресурсів. Так, у₁ = 1/2 та у₃ = 2 відмінні від нуля, а ресурси 1 та 2 (за значеннями додаткових змінних прямої задачі) використовуються повністю. Двоїста оцінка у₂ = 0 і відповідний вид ресурсу не повністю використовується за оптимального плану виробництва продукції. Це підтверджується також попереднім аналізом додаткових змінних оптимального плану прямої задачі. Крім того, за третьою теоремою двоїстості відомо: якщо деяка основна змінна оптимального плану двоїстої задачі у_і 0, то зміна (збільшення або зменшення) обсягу відповідного і-го ресурсу приводить до зміни значення цільової функції на величину у_і. Якщо у_і = 0, то значення цільової функції залишається незмінним.

Отже, у₁ = 1/2 означає, що коли запас першого ресурсу збільшити на одну умовну одиницю (b₁ = 250 + 1 = 251), то значення цільової функції max Z збільшиться за інших однакових обставин на у₁ = 1/2 ум. од. і становитиме max Z = 285 + 1/2 = 285,5 ум.од. Аналогічно збільшення на одну умовну одиницю третього ресурсу (b₃ = 80 + 1 = 81) приведе за інших однакових умов до збільшення цільової функції на у₃ =2 ум.од., що становитиме max Z = 285 + 2 = 287 ум. од. Лише незначні зміни обсягу другого ресурсу ніяк не впливатимуть на значення цільової функції, оскільки у₂ = 0.

Додаткові змінні оптимального плану двоїстої задачі відповідають основним змінним прямої задачі і, оскільки останні означають обсяги виробництва кожного виду продукції, відповідні їм у₄, у₅, у₆ та у₇ також у певний спосіб мають характеризувати виробництво відповідних видів продукції. За правилами побудови двоїстої задачі очевидно, що додаткові змінні оптимального плану двоїстої задачі показують, наскільки вартість ресурсів перевищує ціну одиниці відповідної продукції. Отже, вони відносно характеризують збитковість виробництва відповідних видів продукції.

Додаткові змінні двоїстої задачі розміщуються в оцінковому рядку останньої симплекс-таблиці у стовпчиках «х₁» - «х₄». Їх оптимальні значення: у₄ = 5; у₅ = 5/2; у₆=0; у₇ = 0. Тому витрати на виробництво продукції видів А і В перевищують їх ціну відповідно на 5 та 5/2 ум.од., а для продукції С і D такого перевищення немає. Це підтверджується також попереднім аналізом основних змінних оптимального плану прямої задачі, оскільки за оптимальним планом доцільно виготовляти саме продукцію видів С і D.

Розрахована оптимальна система оцінок забезпечує найменшу загальну вартість усіх ресурсів, що використовуються на підприємстві: min F = 285 ум. од.

3. Оцінка рентабельності продукції, яка виробляється, і нової продукції

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

Ліва частина кожного обмеження двоїстої задачі є вартістю відповідних ресурсів, які використовують для виробництва одиниці j-ї продукції. Якщо ця величина перевищує ціну одиниці продукції (с_j), то виготовляти таку продукцію невигідно, вона нерентабельна і в оптимальному плані прямої задачі відповідна їй змінна х_j = 0. Якщо ж загальна оцінка всіх ресурсів дорівнює ціні одиниці продукції, то виготовляти таку продукцію доцільно, вона рентабельна і в оптимальному плані прямої задачі відповідна змінна х_j > 0.

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

Аналогічні результати можна дістати, проаналізувавши додаткові змінні оптимального плану двоїстої задачі (п.6.2). Як з'ясовано вище, значення додаткових змінних показують, наскільки вартість ресурсів перевищує ціну одиниці відповідної продукції. Тому, якщо додаткова змінна двоїстої задачі дорівнює нулю, то продукція рентабельна. І, навпаки, якщо у_і > 0, то відповідна продукція нерентабельна.

Оптимальні значення у₄ = 5 > 0; у₅ = 5/2 > 0, тому продукція А і В нерентабельна, а у₆ = 0; у₇ = 0, тобто продукція С і D - рентабельна.

Дослідимо питання про доцільність введення нового (n+1)-го виду продукції, якщо відомі витрати кожного ресурсу на виготов-лення одиниці такої продукції - і ціна її реалізації - . За умови введення у виробництво нового виду продук-ції в економіко-математичну модель (6.7) необхідно ввести відповідну змінну (х_n+1). Отже, модель прямої задачі набуде вигляду:

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

(6.9)

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

Допустимо, що за умов прикладу 6.1 запропоновано включити у виробництво один з двох видів нової продукції: E чи G. Відомі витрати кожного ресурсу на виготовлення одиниці цих видів продукції, що становлять для продукції виду E відповідно 4, 7, 2 ум. од. та для продукції виду G - 4, 8, 1 ум. од. Ціна реалізації одиниці продукції обох нових видів однакова і дорівнює 4,5 ум.од.

Складемо відповідне обмеження двоїстої задачі. Наступний вид продукції буде позначатися через х₅, тому маємо:

.

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

;

.

Обмеження виконується як строга нерівність, отже, за умов даного підприємства виробництво продукції Е є недоцільним.

Зауважимо, що остання нерівність визначає мінімальне значення ціни реалізації одиниці продукції, за якої її випуск є рентабельним. Отже, ціна одиниці продукції Е за даних умов має становити не менше 6 ум. од.

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



.

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

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

4. Аналіз обмежень дефіцитних і недефіцитних ресурсів

За допомогою двоїстих оцінок можна також визначити статус кожного ресурсу. Ресурси, що використовуються для виробництва продукції, можна умовно поділити на дефіцитні та недефіцитні залежно від того, повне чи часткове їх використання передбачене оптимальним планом прямої задачі. Якщо деяке значення двоїстої оцінки у_і в оптимальному плані двоїстої задачі дорівнює нулю, то відповідний і-й ресурс використовується у виробництві продукції не повністю і є недефіцитним. Якщо ж двоїста оцінка у_і > 0, то і-й ресурс використовується для оптимального плану виробництва продукції повністю і називається дефіцитним. Відомо (третя теорема двоїстості), що величина двоїстої оцінки показує, наскільки збільшиться значення цільової функції Z, якщо запас відповідного ресурсу збільшити на одну умовну одиницю.

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

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

Третій спосіб - за допомогою двоїстих оцінок. Якщо у_і > 0, то зміна (збільшення або зменшення) обсягів і-го ресурсу приводить до відповідної зміни доходу підприємства, і тому такий ресурс є дефіцитним. Якщо ж у_і = 0, то і-й ресурс недефіцитний. Так, у нашому прикладі:

Отже, якщо запас першого дефіцитного ресурсу збільшити на одну умовну одиницю (b₁ = 250 + 1 = 251), то цільова функція max Z збільшиться за інших однакових умов на у₁ = 1/2 ум. од. і становитиме max Z = 285,5 ум. од.

Цікавим є запитання: «За рахунок яких змін в оптимальному плані виробництва продукції збільшиться дохід підприємства?» Інформацію про це дають елементи стовпчика «х₅» останньої симплекс-таблиці, який відповідає двоїстій оцінці даного ресурсу - у₁ = 1/2.

Допустимо, що деяке k-те обмеження () має в правій час-тині початкове значення - . Нехай початкова величина змінилась на величину . Якщо в початковій задачі значення першого ресурсу зросте на одиницю (=1), то згідно з останньою симплексною таблицею

отримаємо:

У новому оптимальному плані значення базисної змінної збільшиться на 1/2, а змінних та - зменшиться відповідно на одиницю та 1/2. При цьому структура плану не зміниться, а нові оптимальні значення будуть такими:

Х^* = (0; 0; 34,5; 45,5; 0; 29; 0).

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

max Z = 20 + 40 + 334,5 + 445,5 = 285,5,

тобто зросте на у₁ = 1/2.

Проаналізуємо, як зміниться оптимальний план виробництва продукції, якщо запас дефіцитного ресурсу 3 за інших однакових умов збільшити на одну умовну одиницю (b₃ = 80 + 1 = 81). Аналогічно попереднім міркуванням, скориставшись елементами стовпчика «х₇» останньої симплекс-таблиці, що відповідає двоїстій оцінці у₃=2, можна записати новий оптимальний план:

Х^* = (0; 0; 37; 44; 0; 30; 0).

max Z= 20 + 40 + 337 + 444 = 287.

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

Але після проведеного аналізу постає логічне запитання: Оскільки збільшення третього ресурсу на одиницю приводить до найбільшого підвищення значення функціонала, то чи можна збільшити третій дефіцитний ресурс на 50, 100 і т.д. ум. од., тим самим значно збільшуючи виручку підприємства?

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

Якщо приріст (зміну) запасу першого ресурсу позначимо через b₁, тоді симплексні таблиці даної задачі набудуть вигляду:

Новий оптимальний план можна записати у такий спосіб:

Х^* = (0; 0; 35-1/2b₁; 45 + 1/2b₁; 0; 30 - b₁; 0).

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

Отже,

.

Це означає, що коли запас ресурсу 1 збільшиться на 30 ум.од. або зменшиться на 90 ум. од., то на цьому інтервалі його оптимальна двоїста оцінка залишиться такою ж: у₁=1/2. Отже, запас ресурсу 1 може змінюватись у межах:

.

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

,

,

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

(0; 0; 80; 0; 0; 120; 0) = Х^* = (0; 0; 20; 60; 0; 0; 0).

Аналогічно розраховується інтервал стійкості двоїстої оцінки у₃ = 2 для дефіцитного ресурсу 3:

,

.

Отже, якщо запас ресурсу 3 збільшиться на 45 ум.од. або змен-шиться на 17,5 ум.од., то двоїста оцінка у₃=2 цього ресурсу залишиться такою ж. Згідно із цим можлива виручка підприємства та оптимальний план виробництва продукції будуть знаходитися у межах:

;

(0; 0; 0; 62,5; 0; 30; 0) = Х* = (0; 0; 125; 0; 0; 30; 0).

Для розрахунку інтервалу зміни недефіцитного ресурсу досить розв'язати одну нерівність

.

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

.

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

.

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

, .

Простішою для дослідження є ситуація, коли зміни ресурсів відомі і необхідно визначити лише новий оптимальний план. Нехай додатковою умовою прикладу 6.1 є зміна обсягів усіх трьох ресурсів, що змінюються відповідно так: b₁= + 10, b₂ = - 10, b₃ = + 20. Для визначення компонент нового оптимального плану скористаємось одним із головних співвідношень обчислювальної процедури симплекс-методу. З першої теореми двоїстості відомо, що:

.

З останньої симплекс-таблиці отримуємо обернену матрицю:

.

Змінені запаси ресурсів утворюють вектор

.

Тоді новий оптимальний план виробництва продукції за відповідної одночасної зміни запасів усіх трьох ресурсів

,

тобто Х^* = (0; 0; 70; 30; 0; 10; 0).

Усі х_j 0, і тому оптимальним планом двоїстої задачі залишається Y* = (1/2; 0;2). Загальна максимальна виручка підприємства зміниться на

F_max = b₁y₁ + b₂y₂ + b₃y₃ = 10·1/2 - 10·0 + 20·2 = +45 ум. од.

і становитиме: max F = 285 + 45 = 330 ум. од.

Використовуючи , проведемо дослідження можливого взаємозамінювання ресурсів.

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

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

Оскільки

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

Отже, якщо перший ресурс збільшити на 4ум.од. і використовувати в обсязі 284ум.од., а третій зменшити на 1ум.од. і залишити у виробництві 79ум.од., то обсяг виручки від реалізації продукції залишиться незмінним у порівнянні з початковими умовами прикладу 6.1 - 285 ум.од.

Размещено на Allbest.ru