Главная | Обратная связь | Поможем написать вашу работу!

Економічна інтерпретація двоїстих задач.

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

1.90. Для виробництва трьох видів виробів А, В і С використовується три різних види сировини. Кожний з видів сировини може бути використаний у кількості, відповідно не більше 180, 210 і 244 кг. Норми витрат кожного з видів сировини на одиницю продукції даного виду і ціна одиниці продукції кожного виду наведені в табл. 1.43.

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

Таблиця 1.43

Вид сировини	Норми витрат сировини (кг) на одиницю продукції
А	В	С
I II III
Ціна одиниці продукції (грн.)

Розв’язок. Припустимо, що виробляється х₁ виробів А, х₂ виробів В і х₃ виробів С. Для визначення оптимального плану виробництва потрібно вирішити задачу, що полягає в максимізації цільової функції

F= 2 x₁ + x₂ +3 x₃ (66)

при наступних умовах:

х₁, х₂, х₃ ≥ 0 (68)

Припишемо кожному з видів сировини, що використовується для виробництва продукції, двоїсту оцінку, відповідно рівну y₁, y₂ і y₃. Тоді загальна оцінка сировини, що використовується на виробництво продукції, складе

F*= 180 y₁ +210 y₂ +244 y₃ → min (69)

Відповідно до умови, двоїсті оцінки повинні бути такими, щоб загальна оцінка сировини, що використовується на виробництво одиниці продукції кожного виду, була не менше ціни одиниці продукції даного виду, тобто y₁, y₂ і y₃ повинні задовольняти наступній системі нерівностей:

(70)

y₁, y₂, y₃ ≥ 0 (71)

Як видно, задачі (66)-(68) і (69)-(71) утворять симетричну пару двоїстих задач. Розв’язок прямої задачі дає оптимальний план виробництва виробів А, В і С,арозв’язок двоїстої – оптимальну систему оцінок сировини, що використовується для виробництва цих виробів. Щоб знайти розв’язок цих задач, варто спочатку відшукати розв’язок якої-небудь однієї з них. Так як система обмежень задачі (66)-(68) містить лише нерівності виду «≤», то краще спочатку знайти розв’язок цієї задачі. Її розв’язок наведений в табл. 1.44.

Із цієї таблиці видно, що оптимальним планом виробництва виробів є такий, при якому виготовляється 82 вироби В і 16 виробів С. При даному плані виробництва залишається невикористаним 80 кг сировини II виду, а загальна вартість виробів дорівнює 1340 грн. З табл. 1.44 також видно, що оптимальним розв’язком двоїстої задачі y₁ ^*=23/4; y₂ ^*=0; y₃ ^*=5/4.

Таблиця 1.44

i	Базис	C_б	Р₀
P₁	P₂	P₃	P₄	P₅	P₆
	P₂ Р₅ P₃			19/8 23/8 –3/4 57/4		5/8 1/8 –1/4 23/4	–1/8 –5/8 1/4 5/4

Змінні y₁ ^*і y₃ ^*позначають умовні двоїсті оцінки одиниці сировини, відповідно I і III видів. Ці оцінки відмінні від нуля, а сировина I і III видів повністю використовується при оптимальному плані виробництва продукції. Двоїста оцінка одиниці сировини II виду дорівнює нулю. Цей вид сировини не повністю використовується при оптимальному плані виробництва продукції.

Таким чином, позитивну двоїсту оцінку мають лише ті види сировини, які повністю використовуються при оптимальному плані виробництва виробів. Тому двоїсті оцінки визначають дефіцитність сировини, що використовується підприємством. Більше того, величина даної двоїстої оцінки показує, на скільки зростає максимальне значення цільової функції прямої задачі при збільшенні кількості сировини відповідного виду на 1 кг. Так, збільшення кількості сировини I виду на 1 кг призведе до того, що з’явиться можливість знайти новий оптимальний план виробництва виробів, при якому загальна вартість виготовленої продукції зросте на 5,75 грн. і стане рівною 1340+ 5,75-= 1345,75 грн. При цьому числа, що стоять у стовпці вектора Р₄ табл. 1.44, показують, що зазначене збільшення загальної вартості виготовленої продукції може бути досягнуте за рахунок збільшення випуску виробів В на 5/8 од. і скорочення випуску виробів С на 1/4 од. Внаслідок цього використання сировини II виду зменшиться на 1/8 кг. Точно так само збільшення на 1 кг сировини III виду дозволить знайти новий оптимальний план виробництва виробів, при якому загальна вартість виготовленої продукції зросте на 1,25 грн. і складе 1340+1,25 = 1341,25 грн. Це буде досягнуто в результаті збільшення випуску виробів С на 1/4 од. і зменшення виготовлення виробів В на 1/8 од., причому об’єм використовуваної сировини II виду зросте на 5/8 кг.

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

F * _min =180·(23/4)+210·0+244·(5/4)=1340,

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

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

Перше обмеження двоїстої задачі виконується як строга нерівність. Це означає, що двоїста оцінка сировини, що використовується на виробництво одного виробу виду А,вище ціни цього виробу і, отже, випускати вироби виду А невигідно. Його виробництво і не передбачене оптимальним планом прямої задачі. Друге і третє обмеження двоїстої задачі виконуються як строгі рівності. Це означає, що двоїсті оцінки сировини, що використовується для виробництва одиниці відповідно виробів В і С, рівні в точності їхнім цінам. Тому випускати ці два види продукції за двоїстими оцінками економічно доцільно. Їхнє виробництво і передбачене оптимальним планом прямої задачі.

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

5. Аналіз стійкості двоїстих оцінок.

Продовжимо розгляд основної задачі лінійного програмування (61)-(63) і двоїстої до неї (64), (65).

Припустимо, що задача (61)-(63) має не вироджені опорні плани і хоча б один з них є оптимальним.

Максимальне значення цільової функції (61) задачі (61)-(63) будемо розглядати як функцію вільних членів системи лінійних рівнянь (62): F_тах (b₁, b₂,..., b_т).

Теорема 1.12. В оптимальному плані двоїстої задачі (64), (65) значення змінної y_i ^* чисельно дорівнює частинній похідній функції F_тах (b₁, b₂,..., b_т) по даному аргументу, тобто

(72)

Остання рівність означає, що зміна значень величин b_i приведе до збільшення або зменшення F_тах (b₁, b₂,..., b_т). Ця зміна F_тах (b₁, b₂,..., b_т)визначається величиною | y_i ^*|і може бути охарактеризована лише тоді, коли при зміні величин b_i значення змінних y_i ^*в оптимальному плані відповідної двоїстої задачі (64), (65) залишаються незмінними. Тому представляє інтерес визначити такі інтервали зміни кожного з вільних членів системи лінійних рівнянь (62), у яких оптимальний план двоїстої задачі (64), (65) не змінюється. Це має місце для всіх тих значень b_i +Δ b_i, при яких стовпець вектора Р₀ останньої симплекс-таблиці розв’язку задачі (61)-(63) не містить від’ємних чисел, тобто тоді, коли серед компонентів вектора

немає від’ємних. Тут В ^-1 – матриця, зворотна матриці В, складеної з компонентів векторів базису, що визначає оптимальний план задачі (61)-(63).

Таким чином, якщо знайдено розв’язок задачі (61)-(63), то неважко провести аналіз стійкості двоїстих оцінок щодо змін b_i. Це, у свою чергу, дозволяє проаналізувати стійкість оптимального плану задачі (64), (65) щодо змін вільних членів системи лінійних рівнянь (62), оцінити ступінь впливу зміни b_i на максимальне значення цільової функції задачі (61)-(63) і дає можливість визначити найбільш доцільний варіант можливих змін b_i.

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒