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

Розглянемо приклад виробничої задачі.

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

 

Таблиця

Ресурси	Продукція, хj			Обсяг ресурсів	Варт. од. ресурсу, уі
	х1	х2	х3
Робоча сила, людино-год.	15 а11	20 а12	25 а13	1200 b1	у1 (х4)
Сировина, m	2 а21	3 а22	2,5 а23	150 b2	у2 (х5)
Енерговитрати, кВт – год.	35 а31	60 а32	60 а33	3000 b3	у3 (х6)
Вартість одиниці продукції	300 с1	250 с2	450 с3	-	-

(у₄) (у₅) (у₆)

 

Потрібно знайти кількість кожного з різновидів продукції, які забезпечують найбільшу вартість загальної продукції. З економічної точки зору вартість ресурсів, використаних на виготовлення одиниці продукції, не може бути меншою, ніж вартість самої одиниці продукції, інакше це позначає, що вартість частини одиниці продукції виникає з повітря. Для якої завгодно виробничої програми вартість виробленої продукції не перевищує загальної вартістю наявних ресурсів. Проаналізуємо отримані результати. Розв’язок прямої задачі вказує на то, що необхідно виробити першої продукції х₁ = 60 одиниць, третьої продукції х₃ = 12 одиниць, другу продукцію виробляти непотрібно (х₂ = 0). Використані повністю ресурси робочої сили (х₄ = 0) та сировини (х₅ = 0), залишок енерговитрат складає х₆ = 180 кВт – год. Розв’язок двоїстої задачі вказує на те, що ресурси перший (у₁ > 0) та другий (у₂ > 0) використані повністю, третій ресурс надмірний (у₃ = 0). Додаток першого обмеженого ресурсу на одиницю збільшує цільову функцію прямої задачі на 12 одиниць (зростає вартість, бо у₁ = 12), другого обмеженого ресурсу на одиницю збільшує Z(x), цільову функцію, на 60 одиниць (у₂ = 60). Збільшення третього ресурсу (необмеженого) – енерговитрату околиці оптимального плану не викликає змін цільової функції. Як у_n = 0, у₆ = 0, так це позначає, що виробництво продукції першої та третьої не є збитковим; у₅ = 170 – це позначає, що виготовлення одиниці другої продукції викликає збиток у 170 грошових одиниць. перевіримо це таким чином: вартість ресурсів на другу продукцію складає

а₁₂у₁ +а₂₂у₂ + а₃₂у₃ = 20 × 12 + 3 × 60 + 60 × 0 = 420,

 

водночас вартість другого виробу складає 250; тобто збиток = 420 – 250 = 170.

Арифметична перевірка задач.

Основна задача:

15 × 60 + 20 × 0 + 2,5 × 12 = 1200;

2 × 60 + 3 × 0 + 2,5 × 12 = 150;

35 × 60 + 60 × 0 + 60 × 12 = 2820 < 3000№

х₄ = 0;

х₅ = 0;

х₆ = 180 > 0;

у₁ = 12 > 0;

у₂ = 60 > 0;

у₃ = 0;

Двоїста задача:

15 × 12 + 2 × 60 + 35 × 0 = 300;

20 × 12 + 3 × 60 + 60 × 0 = 420 250;

25 × 12 + 2,5 × 60 + 60× 0 = 450;

у₄ = 0;

у₅ = 170 > 0;

у₆ – 0;

х₁ = 60 > 0;

х₂ = 0;

х₃ = 12 > 0.

Стійкість оптимальних планів прямої та двоїстої задач обумовлені зміною обмежень “D С₂ < 170;” “DС_j, які не викликають порушень умов оптимізму. У нашому прикладі D b₃ = D b₁ = 0. Це позначає, що збільшення без обмежень, та зменшення менш ніж на 180 енерговитрат не змінює оптимального плану задачі.

У оптимальному плані двоїстої задачі значення змінної (у_і*) чисельно дорівнює частковій похідній функції

j_max (b₁,b₂,..,b_m) за аргументом “у_і”ю. тобто

 

¶ j _max = y_i*.

   ¶ b_i

 

Це вочевидь співвідношення вказує на те, що зміна “bі” викликає зміну j _max, яка визначається зміною “у_і”. Але на прикладі ми бачили, що як обмеження не є критичним, так зміна “bі” ресурсу у околиці оптимального плану не викликає зміни цільової функції. Тому важливо визначити інтервали зміни кожного з вільних членів системи обмежень основної задачі. або коефіцієнтів цільової функції двоїстої задачі, у яких оптимальний план двоїстої задачі не змінюється. Це має місце для усіх значень (b_i + Db_i), при котрих стовпець вектора Р₀останньої симплекс-таблиці розв’язання основної задачі не містить від’ємних чисел, тобто коли серед компонентів вектора

 

b₁ + Db₁

b₂ + Db₂

_. b_n + Db_n

 

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

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

 

Література

 

Основна:

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. – М.: Высш. шк., 1986. – 319 с.

2. Бугір М.К. Математика для економістів. Лінійна алгебра, лінійні моделі. Посібник для студентів вищих навчальних закладів. – К.: Видавничий центр “Академія”, 1998 – 272 с.

3. Вітлінський В.В., Наконечний С.І. Ризик у менеджменті. – К.: ТОВ “Борисфен – М”, 1996. – 336 с.

4. Справочник по математике для экономистов / В.Е.Барбогумов, В.И.Ермакова, Н.Н.Кривенцова и др.; Под ред. В.И. Ермакова. – 2 изд., перераб. и доп. – М.: Высш. шк., 1997. – 384 с.

Додаткова:

5. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988. – 128 с.

6. Численные методы в экстремальных задачах. Пшеничный Б.Н., Данилин Ю.М., Главная редакция физико-математической литературы издательства «Наука», 1975. – 319 с.

7. Численные методы. Н.Н. Калиткин. Главная редакция физико-математической литературы издательства «Наука», М., 1978. – 512 с.

8. Юдин Д.Б. Задачи и методы стохастического программирования. М., 1979. – 345 с.

9. Мажид К.И. Оптимальное проектирование конструкций. Лондон, 1974, пер. с англ. – М.: Высш. шк., 1979. – 237 с.

10. Грешилов А.А. Как принять наилучшее решение в реальных условиях. – М.: Радио и связь, 1991. – 320 с.