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

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


Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

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

Пряма задача:
max F = c1x1 + c2x2 + … + cnxn (3.1)

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

за умов: <img width=«197» height=«90» src=«ref-1_1739029138-1103.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_002.gif» v:shapes="_x0000_i1035">(3.2)
<img width=«95» height=«27» src=«ref-1_1739030241-342.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_004.gif» v:shapes="_x0000_i1036">. (3.3)
Необхідно визначити, яку кількість продукції кожного j-го виду <img width=«16» height=«24» src=«ref-1_1739030583-223.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_006.gif» v:shapes="_x0000_i1037"><img width=«50» height=«24» src=«ref-1_1739030806-285.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_008.gif» v:shapes="_x0000_i1038">необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів – <img width=«67» height=«24» src=«ref-1_1739031091-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_010.gif» v:shapes="_x0000_i1039">; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції –<img width=«113» height=«27» src=«ref-1_1739031404-387.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_012.gif» v:shapes="_x0000_i1040">, а також <img width=«67» height=«27» src=«ref-1_1739031791-314.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_014.gif» v:shapes="_x0000_i1041"> – ціни реалізації одиниці j-ої продукції.

Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу <img width=«64» height=«24» src=«ref-1_1739032105-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_016.gif» v:shapes="_x0000_i1042">поставимо у відповідність його оцінку <img width=«68» height=«24» src=«ref-1_1739032418-316.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_018.gif» v:shapes="_x0000_i1043">. Умовно вважатимемо, що <img width=«16» height=«21» src=«ref-1_1739032734-223.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_020.gif» v:shapes="_x0000_i1044"> – ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю (3.1) – (3.3) m видів ресурсів у кількості відповідно <img width=«101» height=«24» src=«ref-1_1739032957-361.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_022.gif» v:shapes=«Рисунок_x0020_11»>. Оскільки ціна одиниці і-го виду ресурсу дорівнює <img width=«67» height=«24» src=«ref-1_1739033318-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_024.gif» v:shapes=«Рисунок_x0020_12»>, то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб:
<img width=«185» height=«24» src=«ref-1_1739033631-493.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_026.gif» v:shapes=«Рисунок_x0020_13»>.
Продавати ресурси доцільно лише за умови, що виручка, отримана від продажу ресурсів, перевищує суму, яку можна було б отримати від реалізації продукції, виготовленої з тих самих обсягів ресурсів, тобто:
<img width=«300» height=«24» src=«ref-1_1739034124-613.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_028.gif» v:shapes=«Рисунок_x0020_14»>.
Зрозуміло, що покупці ресурсів прагнуть здійснити операцію якнайдешевше, отже, необхідно визначити мінімальні ціни одиниць кожного виду ресурсів, за яких їх продаж є доцільнішим, ніж виготовлення продукції. Загальну вартість ресурсів можна виразити формулою:
<img width=«152» height=«21» src=«ref-1_1739034737-420.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_030.gif» v:shapes=«Рисунок_x0020_15»>.
Отже, в результаті маємо двоїсту задачу:
<img width=«172» height=«21» src=«ref-1_1739035157-459.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_032.gif» v:shapes=«Рисунок_x0020_16»>(3.4)
за умов:<img width=«243» height=«77» src=«ref-1_1739035616-1231.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_034.gif» v:shapes=«Рисунок_x0020_17»> (3.5)


<img width=«108» height=«21» src=«ref-1_1739036847-361.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_036.gif» v:shapes=«Рисунок_x0020_18»>(3.6)
Тобто необхідно визначити, які мінімальні ціни можна встановити для одиниці кожного і-го виду ресурсу <img width=«61» height=«24» src=«ref-1_1739037208-295.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_038.gif» v:shapes=«Рисунок_x0020_19»>, щоб продаж ресурсів був доцільнішим, ніж виробництво продукції.

Зауважимо, що справжній зміст величин <img width=«61» height=«24» src=«ref-1_1739037208-295.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_038_0000.gif» v:shapes=«Рисунок_x0020_20»> – умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadowprices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л.В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

Задача (3.4) – (3.6) є двоїстою або спряженою до задачі (3.1) – (3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4) – (3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу – двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: <img width=«67» height=«24» src=«ref-1_1739037798-316.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_041.gif» v:shapes=«Рисунок_x0020_21»>, <img width=«113» height=«27» src=«ref-1_1739038114-388.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_043.gif» v:shapes=«Рисунок_x0020_22»>; <img width=«68» height=«27» src=«ref-1_1739038502-317.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_045.gif» v:shapes=«Рисунок_x0020_23»>. Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

Початкова постановка задачі та математична модель може мати вигляд як (3.1) – (3.3), так і (3.4) – (3.6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування.

    продолжение
--PAGE_BREAK--2.1 Правила побудови двоїстих задач


Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду «<img width=«13» height=«15» src=«ref-1_1739038819-211.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_047.gif» v:shapes=«Рисунок_x0020_93»>», а для задачі на відшукання мінімального значення – до виду «<img width=«13» height=«15» src=«ref-1_1739039030-210.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_049.gif» v:shapes=«Рисунок_x0020_94»>».

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

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

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

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

6. Матриця
<img width=«147» height=«83» src=«ref-1_1739039240-786.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_051.gif» v:shapes=«Рисунок_x0020_95»>,
що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі


<img width=«148» height=«96» src=«ref-1_1739040026-832.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_053.gif» v:shapes=«Рисунок_x0020_96»>
утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків – рядками.

Процес побудови двоїстої задачі зручно зобразити схематично:
<img width=«360» height=«210» src=«ref-1_1739040858-3321.coolpic» alt=«Схема побудови двоїстої задачі до прямої» v:shapes=«Рисунок_x0020_97»>

Рис. 3.1. Схема побудови двоїстої задачі до прямої
Пари задач лінійного програмування бувають симетричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

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

Всі можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач у матричній формі наведено нижче.



Пряма задача Двоїста задача Cиметричні задачі
max F = CX

AX <img width=«15» height=«17» src=«ref-1_1739044179-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_057.gif» v:shapes=«Рисунок_x0020_98»> B

X <img width=«15» height=«15» src=«ref-1_1739044393-212.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_059.gif» v:shapes=«Рисунок_x0020_99»> 0

min Z = BY

ATY <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060.gif» v:shapes=«Рисунок_x0020_100»> C

Y <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0000.gif» v:shapes=«Рисунок_x0020_101»> 0

min F = CX

AX <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0001.gif» v:shapes=«Рисунок_x0020_102»> B

X <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0002.gif» v:shapes=«Рисунок_x0020_103»> 0

max Z = BY

ATY <img width=«15» height=«17» src=«ref-1_1739044179-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_057_0000.gif» v:shapes=«Рисунок_x0020_104»> C

Y <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0003.gif» v:shapes=«Рисунок_x0020_105»> 0


Несиметричні задачі

max F = CX

AX = B

X <img width=«15» height=«15» src=«ref-1_1739044393-212.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_059_0000.gif» v:shapes=«Рисунок_x0020_106»> 0

min Z = BY

ATY <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0004.gif» v:shapes=«Рисунок_x0020_107»> C

Y <img width=«57» height=«21» src=«ref-1_1739046315-295.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_062.gif» v:shapes=«Рисунок_x0020_108»>

min F = CX

AX = B

X <img width=«15» height=«17» src=«ref-1_1739044605-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0005.gif» v:shapes=«Рисунок_x0020_109»> 0

max Z = BY

ATY <img width=«15» height=«17» src=«ref-1_1739044179-214.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_057_0001.gif» v:shapes=«Рисунок_x0020_110»> C

Y <img width=«57» height=«21» src=«ref-1_1739046315-295.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_062_0000.gif» v:shapes=«Рисунок_x0020_111»>



До даної задачі лінійного програмування записати двоїсту.

max F = –5x1 + 2x2;
<img width=«88» height=«59» src=«ref-1_1739047333-547.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_067.gif» v:shapes=«Рисунок_x0020_112»>
Розв’язання.Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «<img width=«13» height=«15» src=«ref-1_1739038819-211.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_047_0000.gif» v:shapes=«Рисунок_x0020_113»>». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max F = –5x1 + 2x2;

<img width=«88» height=«59» src=«ref-1_1739048091-542.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_069.gif» v:shapes=«Рисунок_x0020_114»>

Тепер за відповідними правилами складемо двоїсту задачу:
<img width=«103» height=«21» src=«ref-1_1739048633-348.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_071.gif» v:shapes=«Рисунок_x0020_115»>;

<img width=«99» height=«59» src=«ref-1_1739048981-586.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_075.gif» v:shapes=«Рисунок_x0020_116»>
Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:
<img width=«559» height=«135» src=«ref-1_1739049567-3741.coolpic» alt=«Двоїста задача» v:shapes=«Рисунок_x0020_117»>
До заданої задачі лінійного програмування записати двоїсту.

<img width=«184» height=«21» src=«ref-1_1739053308-450.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_079.gif» v:shapes=«Рисунок_x0020_118»>

<img width=«184» height=«59» src=«ref-1_1739053758-893.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_081.gif» v:shapes=«Рисунок_x0020_119»>

<img width=«107» height=«24» src=«ref-1_1739054651-346.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_083.gif» v:shapes=«Рисунок_x0020_120»>

Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду «<img width=«13» height=«15» src=«ref-1_1739039030-210.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_049_0000.gif» v:shapes=«Рисунок_x0020_121»>». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

<img width=«184» height=«59» src=«ref-1_1739055207-904.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_085.gif» v:shapes=«Рисунок_x0020_122»>

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

<img width=«152» height=«21» src=«ref-1_1739056111-422.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_087.gif» v:shapes=«Рисунок_x0020_123»>

<img width=«128» height=«96» src=«ref-1_1739056533-1022.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_089.gif» v:shapes=«Рисунок_x0020_124»><img width=«152» height=«21» src=«ref-1_1739057555-437.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_091.gif» v:shapes=«Рисунок_x0020_125»>
Оскільки перше обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі <img width=«16» height=«21» src=«ref-1_1739057992-224.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_093.gif» v:shapes=«Рисунок_x0020_126»>може набувати як додатного, так і від’ємного значення.

    продолжение
--PAGE_BREAK--3. Основні теореми двоїстості та їх економічний зміст


Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.

Якщо <img width=«101» height=«21» src=«ref-1_1739058216-343.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_095.gif» v:shapes=«Рисунок_x0020_161»>та <img width=«102» height=«21» src=«ref-1_1739058559-352.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_097.gif» v:shapes=«Рисунок_x0020_162»> – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

<img width=«80» height=«20» src=«ref-1_1739058911-335.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_099.gif» v:shapes=«Рисунок_x0020_163»>або <img width=«90» height=«37» src=«ref-1_1739059246-419.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_101.gif» v:shapes=«Рисунок_x0020_164»>. (3.7)

Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:
<img width=«215» height=«77» src=«ref-1_1739059665-1154.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_103.gif» v:shapes=«Рисунок_x0020_165»>
<img width=«236» height=«77» src=«ref-1_1739060819-1245.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_105.gif» v:shapes=«Рисунок_x0020_166»>
Підсумувавши праві і ліві частини нерівностей, отримаємо:
<img width=«132» height=«43» src=«ref-1_1739062064-575.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_107.gif» v:shapes=«Рисунок_x0020_167»>. (3.8)
Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:
<img width=«193» height=«77» src=«ref-1_1739062639-1122.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_109.gif» v:shapes=«Рисунок_x0020_168»>


Підсумувавши після множення тут також ліві та праві частини, отримаємо нерівність:
<img width=«135» height=«41» src=«ref-1_1739063761-566.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_111.gif» v:shapes=«Рисунок_x0020_169»>(3.9)
Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:
<img width=«147» height=«39» src=«ref-1_1739064327-573.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_113.gif» v:shapes=«Рисунок_x0020_170»><img width=«132» height=«43» src=«ref-1_1739062064-575.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_107_0000.gif» v:shapes=«Рисунок_x0020_171»>.
Нерівність (3.7) доведено.

Якщо <img width=«97» height=«21» src=«ref-1_1739065475-352.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_116.gif» v:shapes=«Рисунок_x0020_172»>та <img width=«112» height=«23» src=«ref-1_1739065827-376.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_118.gif» v:shapes=«Рисунок_x0020_173»> – допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність
<img width=«93» height=«23» src=«ref-1_1739066203-353.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_120.gif» v:shapes=«Рисунок_x0020_174»>(3.10)
то X*, Y* – оптимальні розв’язки відповідних задач.

Доведення. Нехай <img width=«20» height=«21» src=«ref-1_1739066556-230.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_122.gif» v:shapes=«Рисунок_x0020_175»> – допустимий план прямої задачі (3.1) – (3.3). Тоді на підставі нерівності (3.7) маємо: <img width=«89» height=«23» src=«ref-1_1739066786-356.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_124.gif» v:shapes=«Рисунок_x0020_176»>. За умовою задачі <img width=«90» height=«23» src=«ref-1_1739067142-350.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_126.gif» v:shapes=«Рисунок_x0020_177»>, отже
<img width=«141» height=«23» src=«ref-1_1739067492-432.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_128.gif» v:shapes=«Рисунок_x0020_178»>(3.11)
Оскільки за допущенням <img width=«20» height=«21» src=«ref-1_1739067924-230.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_130.gif» v:shapes=«Рисунок_x0020_179»> – довільний допустимий план прямої задачі, то нерівність (3.11) виконується для будь-якого з можливих розв’язків. Отже, маємо, що при <img width=«21» height=«19» src=«ref-1_1739068154-227.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_132.gif» v:shapes=«Рисунок_x0020_180»>цільова функція (3.1) набирає найбільшого значення, тобто є оптимальним розв’язком початкової задачі.

В аналогічний спосіб доводиться, що <img width=«19» height=«19» src=«ref-1_1739068381-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_134.gif» v:shapes=«Рисунок_x0020_181»> – оптимальний план двоїстої задачі.


3.1 Перша теорема двоїстості


Теорема (перша теорема двоїстості). Якщо одна з пари спряжених задач має оптимальний план, то й друга задача також має розв’язок, причому для оптимальних розв’язків значення цільових функцій обох задач збігаються, тобто <img width=«83» height=«20» src=«ref-1_1739068603-325.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_002_0000.gif» v:shapes=«Рисунок_x0020_203»>.

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

Доведення. Допустимо, що початкова задача (3.1) – (3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з першихm векторів <img width=«71» height=«21» src=«ref-1_1739068928-306.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_004_0000.gif» v:shapes=«Рисунок_x0020_204»>. Остання симплексна таблиця має вигляд:
Таблиця 3.1
і

Базис

Сб

План

с1

с2

…

сm

cm + 1

…

cn

x1

x2

…

xm

xm + 1

…

xn

1

x1

<img width=«15» height=«23» src=«ref-1_1739069234-223.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_006_0000.gif» v:shapes=«Рисунок_x0020_205»>

<img width=«16» height=«23» src=«ref-1_1739069457-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_008_0000.gif» v:shapes=«Рисунок_x0020_206»>

1



…



<img width=«41» height=«24» src=«ref-1_1739069679-262.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_010_0000.gif» v:shapes=«Рисунок_x0020_207»>

…

<img width=«26» height=«24» src=«ref-1_1739069941-241.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_012_0000.gif» v:shapes=«Рисунок_x0020_208»>

2

x2

<img width=«16» height=«23» src=«ref-1_1739070182-225.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_014_0000.gif» v:shapes=«Рисунок_x0020_209»>

<img width=«16» height=«23» src=«ref-1_1739070407-225.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_016_0000.gif» v:shapes=«Рисунок_x0020_210»>



1

…



<img width=«44» height=«24» src=«ref-1_1739070632-267.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_018_0000.gif» v:shapes=«Рисунок_x0020_211»>

…

<img width=«23» height=«21» src=«ref-1_1739070899-235.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_020_0000.gif» v:shapes=«Рисунок_x0020_212»>























m

xm

<img width=«17» height=«23» src=«ref-1_1739071134-226.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_022_0000.gif» v:shapes=«Рисунок_x0020_213»>

<img width=«19» height=«23» src=«ref-1_1739071360-228.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_024_0000.gif» v:shapes=«Рисунок_x0020_214»>





…

1

<img width=«46» height=«24» src=«ref-1_1739071588-268.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_026_0000.gif» v:shapes=«Рисунок_x0020_215»>

…

<img width=«26» height=«21» src=«ref-1_1739071856-240.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_028_0000.gif» v:shapes=«Рисунок_x0020_216»>

m + 1

<img width=«59» height=«27» src=«ref-1_1739072096-296.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_030_0000.gif» v:shapes=«Рисунок_x0020_217»>

F0





…



<img width=«33» height=«23» src=«ref-1_1739072392-255.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_032_0000.gif» v:shapes=«Рисунок_x0020_218»>

…

<img width=«21» height=«21» src=«ref-1_1739072647-231.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_034_0000.gif» v:shapes=«Рисунок_x0020_219»>



Позначимо через D матрицю, що утворена з компонент векторів А1, А2,…, Аm останнього базису в першій симплексній таблиці.

Для оптимального плану отримаємо:
<img width=«52» height=«19» src=«ref-1_1739072878-274.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_036_0000.gif» v:shapes=«Рисунок_x0020_220»>(3.12)


де <img width=«110» height=«23» src=«ref-1_1739073152-369.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_038_0001.gif» v:shapes=«Рисунок_x0020_221»>, В-вектор, що складається з вільних членів системи обмежень.

Звідси:
<img width=«139» height=«20» src=«ref-1_1739073521-381.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_040.gif» v:shapes=«Рисунок_x0020_222»>(3.13)
Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів <img width=«69» height=«21» src=«ref-1_1739073902-303.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_042.gif» v:shapes=«Рисунок_x0020_223»>початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1) – (3.3) Аj відповідає в симплексній таблиці вектор <img width=«19» height=«24» src=«ref-1_1739074205-233.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_044.gif» v:shapes=«Рисунок_x0020_224»>, такий що
<img width=«112» height=«27» src=«ref-1_1739074438-392.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_046.gif» v:shapes=«Рисунок_x0020_225»>(3.14)
Позначимо через <img width=«17» height=«16» src=«ref-1_1739074830-220.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_048.gif» v:shapes=«Рисунок_x0020_226»>матрицю, що складається з коефіцієнтів розкладу векторів <img width=«19» height=«24» src=«ref-1_1739075050-230.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_050.gif» v:shapes=«Рисунок_x0020_227»><img width=«49» height=«24» src=«ref-1_1739075280-294.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_052.gif» v:shapes=«Рисунок_x0020_228»>. Тоді буде справджуватися рівність:

<img width=«55» height=«24» src=«ref-1_1739075574-281.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_054.gif» v:shapes=«Рисунок_x0020_229»>, звідки
<img width=«61» height=«25» src=«ref-1_1739075855-294.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_056.gif» v:shapes=«Рисунок_x0020_230»>. (3.15)
Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді:
<img width=«89» height=«23» src=«ref-1_1739076149-336.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_058.gif» v:shapes=«Рисунок_x0020_231»>
де <img width=«107» height=«23» src=«ref-1_1739076485-362.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_060_0006.gif» v:shapes=«Рисунок_x0020_232»>, причому

<img width=«281» height=«23» src=«ref-1_1739076847-594.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_062_0001.gif» v:shapes=«Рисунок_x0020_233»>

<img width=«160» height=«21» src=«ref-1_1739077441-415.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_064.gif» v:shapes=«Рисунок_x0020_234»>,

тобто всі компоненти вектора <img width=«16» height=«19» src=«ref-1_1739077856-218.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_066.gif» v:shapes=«Рисунок_x0020_235»>є оцінками оптимального плану задачі (3.1) – (3.3), а тому
<img width=«67» height=«20» src=«ref-1_1739078074-285.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_068.gif» v:shapes=«Рисунок_x0020_236»><img width=«124» height=«27» src=«ref-1_1739078359-431.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_070.gif» v:shapes=«Рисунок_x0020_237»>. (3.16)
Оскільки оптимальний план початкової задачі подано у вигляді <img width=«68» height=«19» src=«ref-1_1739078790-286.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_072.gif» v:shapes=«Рисунок_x0020_238»>, то за правилами побудови двоїстої задачі можна допустити, що її оптимальний план матиме вигляд:
<img width=«68» height=«20» src=«ref-1_1739079076-289.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_074.gif» v:shapes=«Рисунок_x0020_239»>. (3.17)
Доведемо, що <img width=«69» height=«20» src=«ref-1_1739079365-289.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_076.gif» v:shapes=«Рисунок_x0020_240»>дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд: <img width=«115» height=«17» src=«ref-1_1739079654-359.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_078.gif» v:shapes=«Рисунок_x0020_241»>.

Підставимо в цю нерівність значення <img width=«19» height=«19» src=«ref-1_1739068381-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_080.gif» v:shapes=«Рисунок_x0020_242»>. Тоді, враховуючи (3.15), (3.16) та (3.17), отримаємо: <img width=«211» height=«20» src=«ref-1_1739080235-479.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_082.gif» v:shapes=«Рисунок_x0020_243»>.

Звідки: <img width=«50» height=«20» src=«ref-1_1739080714-279.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_084.gif» v:shapes=«Рисунок_x0020_244»>. Отже, <img width=«19» height=«19» src=«ref-1_1739068381-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_080_0000.gif» v:shapes=«Рисунок_x0020_245»>задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4) – (3.6).

Для даного плану значення функціонала дорівнюватиме:
<img width=«75» height=«23» src=«ref-1_1739081215-322.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_087_0000.gif» v:shapes=«Рисунок_x0020_246»>, (3.18)
де <img width=«100» height=«21» src=«ref-1_1739081537-355.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_089_0000.gif» v:shapes=«Рисунок_x0020_247»>. Підставимо в (3.18) значення <img width=«19» height=«19» src=«ref-1_1739068381-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_080_0001.gif» v:shapes=«Рисунок_x0020_248»>з (3.17) та, враховуючи (3.13), матимемо:
<img width=«223» height=«23» src=«ref-1_1739082114-527.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_092.gif» v:shapes=«Рисунок_x0020_249»>. (3.19)
Доведено, що <img width=«40» height=«23» src=«ref-1_1739082641-268.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_094.gif» v:shapes=«Рисунок_x0020_250»>збігається зі значенням оптимального плану початкової задачі.

Отже, за лемою 3.2 (достатня умова оптимальності плану задачі лінійного програмування) план <img width=«19» height=«19» src=«ref-1_1739068381-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_080_0002.gif» v:shapes=«Рисунок_x0020_251»>є оптимальним планом двоїстої задачі (3.4) – (3.6).

Аналогічно доводиться, що коли двоїста задача має розв’язок, то початкова також має розв’язок і виконується рівність: <img width=«83» height=«20» src=«ref-1_1739083131-327.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_097_0000.gif» v:shapes=«Рисунок_x0020_252»>.

Для доведення другої частини теореми допустимо, що лінійна функція початкової задачі необмежена зверху. Тоді з нерівності <img width=«80» height=«20» src=«ref-1_1739058911-335.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_099_0000.gif» v:shapes=«Рисунок_x0020_253»>маємо, що <img width=«64» height=«20» src=«ref-1_1739083793-303.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_101_0000.gif» v:shapes=«Рисунок_x0020_254»>, що не має змісту. Отже, двоїста задача в даному разі не має розв’язків. Доведена теорема дає змогу в процесі розв’язування однієї задачі водночас знаходити план другої.

Економічний зміст першої теореми двоїстості. Максимальний прибуток (Fmax) підприємство отримує за умови виробництва продукції згідно з оптимальним планом <img width=«109» height=«23» src=«ref-1_1739084096-363.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_103_0000.gif» v:shapes=«Рисунок_x0020_255»>, однак таку саму суму грошей (<img width=«64» height=«21» src=«ref-1_1739084459-294.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_105_0000.gif» v:shapes=«Рисунок_x0020_256»>) воно може мати, реалізувавши ресурси за оптимальними цінами <img width=«108» height=«23» src=«ref-1_1739084753-376.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_107_0001.gif» v:shapes=«Рисунок_x0020_257»>. За умов використання інших планів <img width=«58» height=«24» src=«ref-1_1739085129-292.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_109_0000.gif» v:shapes=«Рисунок_x0020_258»><img width=«45» height=«24» src=«ref-1_1739085421-277.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_111_0000.gif» v:shapes=«Рисунок_x0020_259»>на підставі основної нерівності теорії двоїстості можна стверджувати, що прибутки від реалізації продукції завжди менші, ніж витрати на її виробництво.


    продолжение
--PAGE_BREAK--3.2 Друга теорема двоїстості


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

Пряма задача:
<img width=«171» height=«21» src=«ref-1_1739085698-432.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_113_0000.gif» v:shapes=«Рисунок_x0020_317»>

<img width=«179» height=«77» src=«ref-1_1739086130-1005.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_115.gif» v:shapes=«Рисунок_x0020_318»>(3.20)


<img width=«89» height=«27» src=«ref-1_1739087135-335.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_117.gif» v:shapes=«Рисунок_x0020_319»>.

Двоїста задача:
<img width=«173» height=«21» src=«ref-1_1739087470-453.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_119.gif» v:shapes=«Рисунок_x0020_320»>

<img width=«177» height=«77» src=«ref-1_1739087923-1024.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_121.gif» v:shapes=«Рисунок_x0020_321»>(3.21)

<img width=«90» height=«24» src=«ref-1_1739088947-336.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_123.gif» v:shapes=«Рисунок_x0020_322»>
Для розв’язування задач симплексним методом необхідно звести їх доканонічної форми, для чого в системи обмежень задач (3.20) і (3.21) необхідно ввести відповідно m та n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні її двоїстої задачі.
<img width=«256» height=«77» src=«ref-1_1739089283-1269.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_125.gif» v:shapes=«Рисунок_x0020_323»>

<img width=«255» height=«77» src=«ref-1_1739090552-1266.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_127.gif» v:shapes=«Рисунок_x0020_324»>
Отримали таку відповідність між змінними спряжених задач:

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

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани X* та Y* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:
<img width=«158» height=«40» src=«ref-1_1739091818-556.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_129.gif» v:shapes=«Рисунок_x0020_326»>(3.22)


<img width=«172» height=«44» src=«ref-1_1739092374-579.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_131.gif» v:shapes=«Рисунок_x0020_327»>. (3.23)



Доведення. Необхідність. Нехай X* та Y* – оптимальні плани відповідно прямої та двоїстої задач (3.20) i (3.21). З першої теореми двоїстості відомо, що
<img width=«193» height=«37» src=«ref-1_1739092953-594.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_133.gif» v:shapes=«Рисунок_x0020_328»>,
а також компоненти векторів X* та Y* задовольняють системи обмежень задач (3.20) та (3.21), тобто:
<img width=«115» height=«40» src=«ref-1_1739093547-442.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_135.gif» v:shapes=«Рисунок_x0020_329»>, (3.24)
<img width=«115» height=«37» src=«ref-1_1739093989-433.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_137.gif» v:shapes=«Рисунок_x0020_330»>. (3.25)
Помножимо (3.24) на <img width=«17» height=«23» src=«ref-1_1739094422-229.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_139.gif» v:shapes=«Рисунок_x0020_331»>, а (3.25) – на <img width=«17» height=«25» src=«ref-1_1739094651-227.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_141.gif» v:shapes=«Рисунок_x0020_332»>і підсумуємо праві та ліві частини. Отримаємо:
<img width=«121» height=«37» src=«ref-1_1739094878-513.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_143.gif» v:shapes=«Рисунок_x0020_333»>;

<img width=«124» height=«40» src=«ref-1_1739095391-522.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_145.gif» v:shapes=«Рисунок_x0020_334»>
Праві частини останніх двох нерівностей не збігаються, але оскільки їх ліві частини однакові, то це означає, що разом вони виконуються лише за умови рівностей, тобто:


<img width=«120» height=«37» src=«ref-1_1739095913-506.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_147.gif» v:shapes=«Рисунок_x0020_335»>;

<img width=«125» height=«40» src=«ref-1_1739096419-515.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_149.gif» v:shapes=«Рисунок_x0020_336»>
Виконаємо перетворення для кожного рівняння:
<img width=«128» height=«43» src=«ref-1_1739096934-545.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_151.gif» v:shapes=«Рисунок_x0020_337»>; (3.26)
<img width=«132» height=«39» src=«ref-1_1739097479-528.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_153.gif» v:shapes=«Рисунок_x0020_338»>. (3.27)
Оскільки <img width=«69» height=«37» src=«ref-1_1739098007-365.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_155.gif» v:shapes=«Рисунок_x0020_339»>, то в рівнянні (3.26) кожна з компонент <img width=«102» height=«43» src=«ref-1_1739098372-469.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_157.gif» v:shapes=«Рисунок_x0020_340»>, а <img width=«81» height=«24» src=«ref-1_1739098841-332.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_159.gif» v:shapes=«Рисунок_x0020_341»>, тому виконання рівняння (3.26) можливе лише у тому разі, коли кожний доданок виду <img width=«116» height=«43» src=«ref-1_1739099173-493.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_161.gif» v:shapes=«Рисунок_x0020_342»>. Аналогічне міркування проведемо для (3.27), після чого можна висновувати, що <img width=«119» height=«39» src=«ref-1_1739099666-483.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_163.gif» v:shapes=«Рисунок_x0020_343»>.

Достатність.За умовою виконуються рівняння
<img width=«116» height=«43» src=«ref-1_1739099173-493.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_161_0000.gif» v:shapes=«Рисунок_x0020_344»>, <img width=«45» height=«24» src=«ref-1_1739100642-270.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_166.gif» v:shapes=«Рисунок_x0020_345»>

<img width=«119» height=«39» src=«ref-1_1739099666-483.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_163_0000.gif» v:shapes=«Рисунок_x0020_346»>, <img width=«43» height=«24» src=«ref-1_1739101395-263.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_169.gif» v:shapes=«Рисунок_x0020_347»>.
Необхідно довести, що X* та Y* – оптимальні плани відповідно прямої (3.20) та двоїстої (3.21) задач. У кожному рівнянні розкриємо дужки та підсумуємо перше рівняння по <img width=«58» height=«24» src=«ref-1_1739101658-311.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_171.gif» v:shapes=«Рисунок_x0020_348»>, а друге – по <img width=«61» height=«24» src=«ref-1_1739101969-311.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_173.gif» v:shapes=«Рисунок_x0020_349»>. Отримаємо:




<img width=«120» height=«37» src=«ref-1_1739095913-506.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_147_0000.gif» v:shapes=«Рисунок_x0020_350»>;

<img width=«121» height=«37» src=«ref-1_1739102786-505.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_176.gif» v:shapes=«Рисунок_x0020_351»>.
Ліві частини цих рівнянь однакові, отже, <img width=«41» height=«36» src=«ref-1_1739103291-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_178.gif» v:shapes=«Рисунок_x0020_352»><img width=«52» height=«37» src=«ref-1_1739103604-321.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_180.gif» v:shapes=«Рисунок_x0020_353»>. Тоді за першою теоремою двоїстості, оскільки значення цільових функцій цих задач збігаються, можна висновувати, що X* та Y* – оптимальні плани спряжених симетричних задач. Теорему доведено.

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

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

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

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг <img width=«15» height=«21» src=«ref-1_1739103925-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_182.gif» v:shapes=«Рисунок_x0020_354»>, то відповідна оцінка такого ресурсу <img width=«17» height=«23» src=«ref-1_1739104147-229.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_184.gif» v:shapes=«Рисунок_x0020_355»>(компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

Якщо ж витрати ресурсу дорівнюють його наявному обсягові <img width=«15» height=«21» src=«ref-1_1739103925-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_182_0000.gif» v:shapes=«Рисунок_x0020_356»>, тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка <img width=«17» height=«23» src=«ref-1_1739104147-229.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_184_0000.gif» v:shapes=«Рисунок_x0020_357»>буде строго більшою від нуля.

Економічне тлумачення другої теореми двоїстості щодо оптимального плану Y* двоїстої задачі: у разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції <img width=«16» height=«25» src=«ref-1_1739104827-226.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_188.gif» v:shapes=«Рисунок_x0020_358»>дорівнює нулю.

Якщо витрати на виробництво j-го виду продукції дорівнюють ціні одиниці продукції <img width=«16» height=«24» src=«ref-1_1739105053-221.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_190.gif» v:shapes=«Рисунок_x0020_359»>, то її необхідно виготовляти в обсязі, який визначає оптимальний план прямої задачі <img width=«39» height=«25» src=«ref-1_1739105274-265.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_192.gif» v:shapes=«Рисунок_x0020_360»>.


    продолжение
--PAGE_BREAK--3.3 Третя теорема двоїстості


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

Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі <img width=«70» height=«24» src=«ref-1_1739105539-319.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_002_0001.gif» v:shapes=«Рисунок_x0020_405»>дорівнюють значенням частинних похідних від цільової функції <img width=«87» height=«21» src=«ref-1_1739105858-342.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_004_0001.gif» v:shapes=«Рисунок_x0020_406»>за відповідними аргументами <img width=«67» height=«24» src=«ref-1_1739106200-318.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_006_0001.gif» v:shapes=«Рисунок_x0020_407»>, або

<img width=«144» height=«40» src=«ref-1_1739106518-446.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_008_0001.gif» v:shapes=«Рисунок_x0020_408»>(3.28)

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:
<img width=«172» height=«21» src=«ref-1_1739106964-431.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_010_0001.gif» v:shapes=«Рисунок_x0020_409»>(3.29)




<img width=«176» height=«77» src=«ref-1_1739107395-994.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_012_0001.gif» v:shapes=«Рисунок_x0020_410»>(3.30)
<img width=«83» height=«27» src=«ref-1_1739108389-333.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_014_0001.gif» v:shapes=«Рисунок_x0020_411»>(3.31)
Двоїсту задачу до задачі (3.29) – (3.31) сформулюємо так: знайти оптимальний план <img width=«112» height=«23» src=«ref-1_1739108722-376.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_016_0001.gif» v:shapes=«Рисунок_x0020_412»>, за якого мінімізується значення
<img width=«147» height=«21» src=«ref-1_1739109098-416.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_018_0001.gif» v:shapes=«Рисунок_x0020_413»>(3.32)
за умов:

<img width=«176» height=«77» src=«ref-1_1739109514-1018.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_020_0001.gif» v:shapes=«Рисунок_x0020_414»>(3.33)
причому умова невід’ємності змінних <img width=«68» height=«24» src=«ref-1_1739110532-314.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_022_0001.gif» v:shapes=«Рисунок_x0020_415»>відсутня.

Позначимо <img width=«112» height=«23» src=«ref-1_1739108722-376.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_016_0002.gif» v:shapes=«Рисунок_x0020_416»> – оптимальний план двоїстої задачі, <img width=«110» height=«23» src=«ref-1_1739111222-364.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_025.gif» v:shapes=«Рисунок_x0020_417»> – оптимальний план задачі (3.29) – (3.31). За першою теоремою двоїстості відомо, що:

<img width=«357» height=«23» src=«ref-1_1739111586-708.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_027.gif» v:shapes=«Рисунок_x0020_418»>,

або
<img width=«148» height=«23» src=«ref-1_1739112294-437.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_029.gif» v:shapes=«Рисунок_x0020_419»>. (3.34)
Оскільки досліджується питання впливу зміни значень <img width=«64» height=«24» src=«ref-1_1739112731-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_031.gif» v:shapes=«Рисунок_x0020_420»>на F, то лінійну функцію (3.34) можна розглядати як функцію від аргументів <img width=«64» height=«24» src=«ref-1_1739112731-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_031_0000.gif» v:shapes=«Рисунок_x0020_421»>. Тоді частинні похідні за змінними <img width=«67» height=«24» src=«ref-1_1739113357-313.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_034_0001.gif» v:shapes=«Рисунок_x0020_422»>будуть дорівнювати компонентам оптимального плану двоїстої задачі <img width=«17» height=«23» src=«ref-1_1739113670-227.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_036_0001.gif» v:shapes=«Рисунок_x0020_423»>:
<img width=«127» height=«41» src=«ref-1_1739113897-453.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_038_0002.gif» v:shapes=«Рисунок_x0020_424»>. (3.35)
Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану <img width=«112» height=«23» src=«ref-1_1739108722-376.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_016_0003.gif» v:shapes=«Рисунок_x0020_425»>залишаються постійними, а оскільки за першою теоремою двоїстості <img width=«69» height=«20» src=«ref-1_1739079365-289.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_041_0000.gif» v:shapes=«Рисунок_x0020_426»>, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі.

Отже, рівності (3.35) справджуються лише за незначних змін <img width=«15» height=«21» src=«ref-1_1739103925-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_043_0000.gif» v:shapes=«Рисунок_x0020_427»>, інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3.30) та цільової функції (3.32)) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої <img width=«41» height=«19» src=«ref-1_1739115237-259.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_045_0000.gif» v:shapes=«Рисунок_x0020_428»>.

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

Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу <img width=«56» height=«40» src=«ref-1_1739115496-334.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_047_0001.gif» v:shapes=«Рисунок_x0020_429»>.

Отже, за умови незначних змін <img width=«15» height=«21» src=«ref-1_1739103925-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_043_0001.gif» v:shapes=«Рисунок_x0020_430»>замість задачі (3.29) – (3.31) маємо нову задачу, де <img width=«15» height=«21» src=«ref-1_1739103925-222.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_043_0002.gif» v:shapes=«Рисунок_x0020_431»>замінено на <img width=«71» height=«21» src=«ref-1_1739116274-312.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_050_0000.gif» v:shapes=«Рисунок_x0020_432»>. Позначимо через <img width=«20» height=«16» src=«ref-1_1739116586-224.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_052_0000.gif» v:shapes=«Рисунок_x0020_433»>оптимальний план нової задачі. Для визначення <img width=«40» height=«20» src=«ref-1_1739116810-270.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_054_0000.gif» v:shapes=«Рисунок_x0020_434»>не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою <img width=«137» height=«23» src=«ref-1_1739117080-424.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_056_0000.gif» v:shapes=«Рисунок_x0020_435»>, де <img width=«21» height=«19» src=«ref-1_1739068154-227.coolpic» alt=«fingal.com.ua/imag/Other/nak_mp/2_058_0000.gif» v:shapes=«Рисунок_x0020_436»> – оптимальний план задачі (3.29) – (3.31).

    продолжение
--PAGE_BREAK--