Повна версія

Головна arrow Економіка arrow Дослідження операцій в економіці

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ПЕРША ТЕОРЕМА ПОДВІЙНОСТІ

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

Основне нерівність теорії подвійності

Нехай є пара двоїстих задач I і II. Покажемо, що для будь-яких допустимих рішень X = х у х Т ..., х п і Y = y v у 2, ..., у т вихідної і двоїстої задач справедливо нерівність

(6.7)

□ Помноживши нерівності системи обмежень (6.2) вихідної задачі відповідно на змінні і склавши праві і ліві частини отриманих нерівностей, маємо

(6.8)

Аналогічно перетворивши систему обмежень (6.5) двоїстої задачі шляхом

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

(6.9)

Так як ліві частини нерівностей (6.8) і (6.9) представляють один і той же вираз , то в силу властивості

транзитивності нерівностей отримаємо доказувана нерівність (6.7). ■

Тепер можна перейти до ознаками оптимальності рішень.

Достатній ознака оптимальності

Сформулюємо теорему.

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

(6.10)

то - оптимальне рішення вихідної задачі I, а оптимальне рішення двоїстої задачі II.

□ Нехай Х {- будь-яке припустиме рішення вихідної задачі I. Тоді застосовуючи основне нерівність (6.7), отримаємо i. Однак X, - довільне рішення задачі I, звідси в силу рівності (6.10) випливає, що тобто X * - оптимальне рішення задачі I. Аналогічно доводиться, що рішення оптимально для задачі II. ■

Крім достатнього ознаки оптимальності взаємно двоїстих задач існують і інші важливі співвідношення між їхніми рішеннями. Перш за все виникають питання: чи завжди для кожної пари двоїстих задач є одночасно оптимальні рішення; чи можлива ситуація, коли одна з двоїстих задач має рішення, а інша ні? Відповідь на ці питання дає наступна теорема.

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

(6.11)

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

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

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

в силу основного нерівності теорії двоїстості (6.7) I, що суперечить умові необмеженість Г (Х). Отже, при у вихідній задачі допустимих рішень в двоїстої завданню бути не може. ■

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

6.2. Дано дві взаємно двоїсті задачі:

I. II.

при обмеженнях:

При обмеженнях:

Завдання I про використання ресурсів (див. Параграф 1.2) і двоїста їй задача II були вирішені раніше (див. Параграфи 5.2, 5.3) і отримані оптимум лінійних функцій 24 для завдання I і для завдання І, тобто висновок першої частини основної теореми подвійності (6.11) вірно. ► Економічний сенс першої (основної) теореми подвійності. План виробництва і набір цін (оцінок) ресурсів виявляються оптимальними тоді і тільки тоді, коли прибуток (виручка) від реалізації продукції, знайдена при "зовнішніх" (відомих заздалегідь) цінах , дорівнює витратам на ресурси по "внутрішнім" (визначеним тільки з рішення задачі) цінами . Для всіх же інших планів X і Y обох завдань відповідно до основного нерівністю (6.7) теорії подвійності прибуток (виручка) від реалізації продукції завжди менше (або дорівнює) витрат на ресурси.

Так, в задачі 6.2 оптимум прибутку від продукції F і витрат на ресурси Z ■ рівні 24 руб. [1] , для всіх інших планів F (X) ≤ 24, 7 (У)> 24.

Економічний сенс першої теореми подвійності можна інтерпретувати і так: підприємству байдуже, виробляти чи продукцію по оптимальному плану X " = (Хр х ' 2, ..., .р *) і отримати максимальний прибуток (виручку) F або продавати ресурси за оптимальними цінами у * = {у, у, ..., у * т ) і відшкодувати від продажу рівні їй мінімальні витрати на ресурси Zmjn.

6.3. Дано дві взаємно двоїсті задачі:

I. II.

при обмеженнях: при обмеженнях:

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

6.4. Дано дві взаємно двоїсті задачі:

I. II.

при обмеженнях: при обмеженнях:

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

  • [1] Нагадуємо, що в розглянутій задачі всі цифри умовні.
 
<<   ЗМІСТ   >>