Навігація
Главная
Авторизация/Регистрация
 
Головна arrow Природознавство arrow ПРИКЛАДНА МАТЕМАТИКА: ТЕХНОЛОГІЇ ЗАСТОСУВАННЯ
Переглянути оригінал

ДВОЇСТІСТЬ В ЛІНІЙНОМУ ПРОГРАМУВАННІ

Для кожного завдання лінійного програмування можна побудувати так звану подвійну до неї завдання. Наведемо схему побудови двоїстої задачі по відношенню до вихідної задачі лінійного програмування. Нехай задана задача лінійного програмування у вигляді (14.1), (14.2), (14.5). Подвійна по відношенню до неї завдання лінійного програмування будується за наступною схемою:

  • 1) кожному i-му обмеження ставиться у відповідність двоїста змінна у ,, причому нерівності у вихідній задачі відповідає неотрицательная змінна (у,> 0), рівності у вихідній задачі відповідає змінна, від якої не потрібно невід'ємності. Тому для ОЗЛП на все двоїсті змінні не накладається умова невід'ємності;
  • 2) матриця обмежень замінюється на транспоновану матрицю: А -> А г ;
  • 3) обмеженнями в двоїстої завданню виступають коефіцієнти цільової функції вихідної задачі;
  • 4) коефіцієнтами цільової функції двоїстої задачі виступають обмеження вихідної задачі;
  • 5) нерівності в обмеженнях замінюються на протилежні;
  • 6) зміст екстремуму замінюється на протилежний (якщо вихідна задача - завдання на максимум, то двоїста по відношенню до неї - завдання на мінімум).

У підсумку можна розглядати наступну пару двоїстих задач лінійного програмування:

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

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

або

Таким чином, перш ніж записати двоїсту задачу, вихідну задачу потрібно привести до однієї з наведених форм.

приклад 14.5

Нехай задана задача лінійного програмування

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

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

Теорема 14.2 (основна теорема подвійності). Якщо одна з пари двоїстих задач має рішення, то і інша двоїста по відношенню до неї також має рішення, причому

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

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

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

Теорема 14.3. Існує приватна похідна функції L = = L (b 1; ред 2 , ..., b m ) за допомогою одного з аргументів, причому

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

приклад 14.6

Нехай задана пара двоїстих задач за умов

і

за умов

при невід'ємності всіх змінних в обох задачах.

Рішення цих завдань мають вигляд X "= (0, 9/4, 0, 7/4, 0), L * = 59/2 і Y * = (19/12, -1/6), Г = 59/2 .

Визначити, як зміниться V , якщо вільний член першого рівняння в обмеженнях збільшиться з 8 до 10.

Рішення. Відповідно до формули (14.13) маємо L (X) = 59/2 + + 2 • 19/12 = 98/3, тобто значення V збільшилася на 19/6.

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

У лінійних задач існує ряд особливостей, що полегшують пошук їх вирішення. По-перше, в задачах лінійного програмування існує тільки абсолютний екстремум цільової функції, що усуває необхідність додаткових перевірок результату рішення. По-друге, безліч точок, в яких цільова функція I = СХ приймає постійне значення, є гіперплоскость, що визначається рівнянням СХ = const. При цьому гиперплоскости, що відповідають різним значенням константи, паралельні між собою, що виключає ускладнення, пов'язані з перетином поверхонь рівня. І нарешті, область визначення лінійної задачі є опуклою і має кінцеве число вершин (крайніх точок). Принаймні в одній з них досягається екстремальне значення L, і таку оптимальну крайню точку можна досягти за кінцеве число кроків. Саме це властивість лежить в основі симплекс-методу. Перераховані особливості забезпечують можливість розв'язання практично будь-яких завдань лінійного програмування і дозволяють побудувати досить гнучкі і універсальні алгоритми пошуку екстремуму цільової функції в загальному вигляді.

 
Переглянути оригінал
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук