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

2010

Вступ

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

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

Предметом дослідження є аналіз ринку ресурсів у передплановому періоді.

Мета роботи дослідити плани, здобуті за економіко-математичними моделями, на стійкість, а також оцінювання ситуацій, які мають виконуватися в передплановому періоді.

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

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

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

Задачі математичного програмування поділяються на два великі класи лінійні та нелінійні. Якщо цільова функція та обмеження є лінійними функціями, тобто вони містять змінні Хj у першому або нульовому степені. В усіх інших випадках задача буде нелінійною. Важливою перевагою лінійних задач є те, що для їх розв’язування розроблено універсальний метод, який називається симплексним методом. Теоретично кожну задачу лінійного програмування можна розв’язати. Для деяких класів лінійних задач, що мають особливу структуру, розробляють спеціальні методи розв’язування, які є ефективнішими. Наприклад, транспортну задачу можна розв’язати симплексним методом, але ефективнішими є спеціальні методи, наприклад метод потенціалів.

Економічні та технологічні процеси, як правило, є нелінійними, стохастичними, розвиваються в умовах невизначеності. Лінійні економіко-математичні моделі часто є неадекватними, а тому доводиться будувати нелінійні та стохастичні моделі. Розв’язувати нелінійні задачі набагато складніше, ніж лінійні, оскільки немає універсального методу розв’язування таких задач. Для окремих типів нелінійних задач розроблено численні спеціальні ефективні методи розв’язування. Проте слід зазначити, що на практиці застосовують, здебільшого, лінійні економіко-математичні моделі. Часто нелінійні залежності апроксимують (наближають) лінійними. Такий підхід на практиці є доволі ефективним.

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

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

Множина S в n-мірному евклідовому просторі називається опуклою множиною, якщо для будь-яких точок (елементів) цієї множини  точки  належать множині S за всіх значень  які належать відрізку

Геометрично це означає, якщо  та  належать до множини S, то відрізок прямої, що з’єднує ці дві точки, також цілком належить до множини S.

Функція  визначена на опуклій множині лінійного простору (на опуклій множині S), називається опуклою, якщо виконується нерівність для всіх  які належать відрізку Квадратичне програмування – цільова функція квадратична, а обмеження лінійні.

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

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

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

Економічні процеси розвиваються в часі, а тому відповідні моделі мають відображати динаміку. Це означає, що для знаходження оптимального плану потрібно застосовувати класи задач математичного програмування статичні (однокрокові) і динамічні (багатокрокові). Поняття динамічності зрозуміле, воно пов’язане з часом. Наприклад, якщо йдеться про план розвитку України до 2005 року, мають бути обґрунтовані значення відповідних макроекономічних показників не лише на 2005 рік, а й на всі проміжні роки, тобто враховано динаміку розвитку народногосподарських процесів. Такий план називають стратегічним.

У ньому має бути обґрунтована оптимальна (раціональна) траєкторія розвитку народного господарства. Проте під впливом некерованих чинників реальні показники щороку можуть відхилятися від планових. Тому постає потреба коригувати кожний річний план. Такі плани називають тактичними. Вони визначаються в результаті реалізації статичної економіко-математичної моделі.

Важливо чітко усвідомити відмінність між одно – та багатокроковими задачами. Багатокроковість як метод розв’язування задач математичного програмування зумовлюється, насамперед, їх багатовимірністю. Сутність цього методу полягає в тому, що оптимальні значення розглядуваної множини змінних знаходять крок за кроком, послідовно застосовуючи індукцію, причому рішення, яке приймається на кожному кроці, має задовольняти умови оптимальності щодо рішення, прийнятого на попередньому кроці. Така процедура може бути і не бути пов’язаною з часом. Однокрокові задачі, навпаки, характеризуються тим, що всі компоненти оптимального плану задачі визначаються одночасно на останній ітерації (кроці) алгоритму. Потрібно розрізняти ітераційність алгоритму і його багатокроковість. Наприклад, симплекс-метод розв’язування задач лінійного програмування є ітераційним, тобто якимось чином задаємо допустимий план і в результаті деякої кількості ітерацій дістаємо оптимальний план. Тут виконуються ітерації (кроки) алгоритму симплексного методу, але це не інтерпретується як багатокроковість економічного процесу (явища).

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

Щойно було розглянуто лише найбільші класи задач математичного програмування, які визначені згідно з математичними критеріями. Можна також за різними ознаками виокремити й підкласи. Це особливо стосується задач лінійного, нелінійного і стохастичного програмування. Наприклад, як окремий клас розглядають дробово-лінійне програмування, коли обмеження є лінійними, а цільова функція – дробово-лінійна. Особливий клас становлять задачі теорії ігор, які широко застосовуються в ринковій економіці. Адже тут діють дві чи більше конфліктних сторін, які мають цілі, що не збігаються, або протилежні цілі. У сукупності задач теорії ігор, у свою чергу, також виокремлюють певні підкласи. Наприклад, ігри двох осіб із нульовою сумою. Наведену класифікацію використано для структурування курсу «Математичне програмування».

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

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

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

Пряма задача:

max F = c1x1 + c2x2 + … + cnxn (3.1)

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

за умов: (3.2)

. (3.3)

Необхідно визначити, яку кількість продукції кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів – ; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції –, а також – ціни реалізації одиниці j-ої продукції.

Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу поставимо у відповідність його оцінку . Умовно вважатимемо, що – ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю (3.1) – (3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб:

.

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

.

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

.

Отже, в результаті маємо двоїсту задачу:

(3.4)

за умов: (3.5)

(3.6)

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

Зауважимо, що справжній зміст величин – умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadowprices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л.В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

Задача (3.4) – (3.6) є двоїстою або спряженою до задачі (3.1) – (3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4) – (3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу – двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: , ; . Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

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

2.1 Правила побудови двоїстих задач

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

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

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

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

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

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

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

6. Матриця

,

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків – рядками.

Процес побудови двоїстої задачі зручно зобразити схематично:

Рис. 3.1. Схема побудови двоїстої задачі до прямої

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

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

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

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

Пряма задача

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

Cиметричні задачі

max F = CX

AX  B

X  0

min Z = BY

ATY  C

Y  0

min F = CX

AX  B

X  0

max Z = BY

ATY  C

Y  0

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

max F = CX

AX = B

X  0

min Z = BY

ATY  C

Y 

min F = CX

AX = B

X  0

max Z = BY

ATY  C

Y 

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

max F = –5x1 + 2x2;

Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max F = –5x1 + 2x2;

Тепер за відповідними правилами складемо двоїсту задачу:

;

Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:

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

Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду «». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

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

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

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

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

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

або . (3.7)

Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:

Підсумувавши праві і ліві частини нерівностей, отримаємо:

. (3.8)

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

Підсумувавши після множення тут також ліві та праві частини, отримаємо нерівність:

(3.9)

Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:

.

Нерівність (3.7) доведено.

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

(3.10)

то X*, Y* – оптимальні розв’язки відповідних задач.

Доведення. Нехай – допустимий план прямої задачі (3.1) – (3.3). Тоді на підставі нерівності (3.7) маємо: . За умовою задачі , отже

(3.11)

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

В аналогічний спосіб доводиться, що – оптимальний план двоїстої задачі.

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

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

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

Доведення. Допустимо, що початкова задача (3.1) – (3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з першихm векторів . Остання симплексна таблиця має вигляд:

Таблиця 3.1

і

Базис

Сб

План

с1

с2

…

сm

cm + 1

…

cn

x1

x2

…

xm

xm + 1

…

xn

1

x1

1

0

…

0

…

2

x2

0

1

…

0

…

m

xm

0

0

…

1

…

m + 1

F0

0

0

…

0

…

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

Для оптимального плану отримаємо:

(3.12)

де , В-вектор, що складається з вільних членів системи обмежень.

Звідси:

(3.13)

Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1) – (3.3) Аj відповідає в симплексній таблиці вектор , такий що

(3.14)

Позначимо через матрицю, що складається з коефіцієнтів розкладу векторів . Тоді буде справджуватися рівність:

, звідки

. (3.15)

Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді:

де , причому

,

тобто всі компоненти вектора є оцінками оптимального плану задачі (3.1) – (3.3), а тому

. (3.16)

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

. (3.17)

Доведемо, що дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд: .

Підставимо в цю нерівність значення . Тоді, враховуючи (3.15), (3.16) та (3.17), отримаємо: .

Звідки: . Отже, задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4) – (3.6).

Для даного плану значення функціонала дорівнюватиме:

, (3.18)

де . Підставимо в (3.18) значення з (3.17) та, враховуючи (3.13), матимемо:

. (3.19)

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

Отже, за лемою 3.2 (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (3.4) – (3.6).

Аналогічно доводиться, що коли двоїста задача має розв’язок, то початкова також має розв’язок і виконується рівність: .

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

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

3.2 Друга теорема двоїстості

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

Пряма задача:

(3.20)

.

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

(3.21)

Для розв’язування задач симплексним методом необхідно звести їх доканонічної форми, для чого в системи обмежень задач (3.20) і (3.21) необхідно ввести відповідно m та n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні її двоїстої задачі.

Отримали таку відповідність між змінними спряжених задач:

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

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани X* та Y* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

(3.22)

. (3.23)

Доведення. Необхідність. Нехай X* та Y* – оптимальні плани відповідно прямої та двоїстої задач (3.20) i (3.21). З першої теореми двоїстості відомо, що

,

а також компоненти векторів X* та Y* задовольняють системи обмежень задач (3.20) та (3.21), тобто:

, (3.24)

. (3.25)

Помножимо (3.24) на , а (3.25) – на і підсумуємо праві та ліві частини. Отримаємо:

;

Праві частини останніх двох нерівностей не збігаються, але оскільки їх ліві частини однакові, то це означає, що разом вони виконуються лише за умови рівностей, тобто:

;

Виконаємо перетворення для кожного рівняння:

; (3.26)

. (3.27)

Оскільки , то в рівнянні (3.26) кожна з компонент , а , тому виконання рівняння (3.26) можливе лише у тому разі, коли кожний доданок виду . Аналогічне міркування проведемо для (3.27), після чого можна висновувати, що .

Достатність. За умовою виконуються рівняння

,

, .

Необхідно довести, що X* та Y* – оптимальні плани відповідно прямої (3.20) та двоїстої (3.21) задач. У кожному рівнянні розкриємо дужки та підсумуємо перше рівняння по , а друге – по . Отримаємо:

;

.

Ліві частини цих рівнянь однакові, отже, . Тоді за першою теоремою двоїстості, оскільки значення цільових функцій цих задач збігаються, можна висновувати, що X* та Y* – оптимальні плани спряжених симетричних задач. Теорему доведено.

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

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

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

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг , то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

Якщо ж витрати ресурсу дорівнюють його наявному обсягові , тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка буде строго більшою від нуля.

Економічне тлумачення другої теореми двоїстості щодо оптимального плану Y* двоїстої задачі: у разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю.

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

3.3 Третя теорема двоїстості

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

Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі дорівнюють значенням частинних похідних від цільової функції за відповідними аргументами , або

(3.28)

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:

(3.29)

(3.30)

(3.31)

Двоїсту задачу до задачі (3.29) – (3.31) сформулюємо так: знайти оптимальний план , за якого мінімізується значення

(3.32)

за умов:

(3.33)

причому умова невід’ємності змінних відсутня.

Позначимо – оптимальний план двоїстої задачі, – оптимальний план задачі (3.29) – (3.31). За першою теоремою двоїстості відомо, що:

,

або

. (3.34)

Оскільки досліджується питання впливу зміни значень на F, то лінійну функцію (3.34) можна розглядати як функцію від аргументів . Тоді частинні похідні за змінними будуть дорівнювати компонентам оптимального плану двоїстої задачі :

. (3.35)

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

Отже, рівності (3.35) справджуються лише за незначних змін , інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3.30) та цільової функції (3.32)) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої .

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

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

Отже, за умови незначних змін замість задачі (3.29) – (3.31) маємо нову задачу, де замінено на . Позначимо через оптимальний план нової задачі. Для визначення не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою , де  – оптимальний план задачі (3.29) – (3.31).

4. Приклади застосування теорії двоїстості для знаходження оптимальних планів прямої та двоїстої задач

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

До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язати одну з них симплекс-методом та визначити оптимальний план другої задачі, використовуючи співвідношення першої теореми двоїстості.

max Z = – 5x1 + 2x2;

Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і всистемі обмежень є нерівності, то їх слід звести до виду «». Тому перше обмеження задачі помножимо на (–1). Отримаємо:

max Z = – 5x1 + 2x2;

Тепер за відповідними правилами складемо двоїсту задачу:

min F = – y1 + 5y2;

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

1. max Z = – 5x1 + 2x2 + 0x3 + 0x4;

2. Векторна форма запису системи обмежень має вигляд:

,

де , , , , .

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

3. Розширена задача лінійного програмування буде такою:

maxZ = – 5x1 + 2x2 + 0x3 + 0x4 – Мx5;

У цій задачі х4 та х5 – базисні змінні, а х1, х2, х3 – вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1.

Перший опорний план задачі:

X0 = (0; 0; 0; 5; 1), Z0 = – M.

З останньої симплекс-таблиці запишемо оптимальний план прямої задачі:

Х* = (0; 5/3; 2/3; 0), Zmax = 10/3.

Згідно зі співвідношенням двоїстості за першою теоремою можна висновувати, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3.

Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою:

,

де та міститься в стовпчику «сбаз» останньої симплекс-таблиці;

.

Матриця D– 1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис.

Отже,

,

min F = – 1 х 0 + 5 х 2/3 = 10/3.

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

До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язавши двоїсту задачу графічно, визначити оптимальний план прямої задачі.

min Z = x1 + 2x2 + 2x3;

Розв’язання. За відповідними правилами побудуємо двоїсту задачу:

mах F = y1 + 4y2;

Зауважимо, що задачі несиметричні, і тому змінна у1, що відповідає першому рівнянню в системі обмежень прямої задачі, може мати будь-який знак, а змінна у2 – лише невід’ємна.

Двоїста задача має дві змінні, а отже, її можна розв’язати графічно (рис. 3.2).

Рис. 3.2

Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розв’язанням системи рівнянь:

Отже, Y* = (– 2/3; 4/3); mах F = 1 х (– 2/3) + 4 х 4/3 = 14/3.

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

Підставимо Y* у систему обмежень двоїстої задачі і з’ясуємо, як виконуються обмеження цієї задачі:

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

Тепер проаналізуємо оптимальний план двоїстої задачі. Оскільки друга компонента плану у2 = 4/3 додатна, то друге обмеження прямої задачі для Х*виконуватиметься як строге рівняння (друга частина другої теореми двоїстості).

Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х1 = 0, та визначити решту змінних:

тобто Х* = (0; 5/3; 2/3), min Z = 1 х 0 + 2 х 5/3 + 2 х 2/3 = 14/3.

Умова min Z = max F = 14/3 виконується, і тому Х* = (0; 5/3; 2/3); Y* = (– 2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач.

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

min Z = 12x1 – 4x2 + 2x3;

а) Х = (8/7; 3/7; 0); б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/3).

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

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

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

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

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

max F = y1 + 2y2;

Перевіримо запропоновані плани на оптимальність.

1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:

Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 х 8/7 – 4 х 3/7 + 2 х 0 = 12.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2:

Підставимо ці значення в третє обмеження системи двоїстої задачі:

;

.

Для визначених значень у1 = 4; у2 = 4 це обмеження не виконується, і тому відповідний план у = (4; 4) є недопустимим планом двоїстої задачі. Внаслідок цього наше допущення, що Х = (8/7; 3/7; 0) є оптимальним планом прямої задачі, виявилося помилковим.

2. Х = (0; 1/5; 8/5). Підставимо цей план у систему обмежень прямої задачі:

План допустимий, і для нього Z = 12 х 0 – 4 х 1/5 + 2 х 8/5 = 12/5.

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

Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у1 та у2: 2 х 8/5 + 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього

F = 8/5 + 2 х 2/5 = 12/5 = Z.

З огляду на викладене можна висновувати, що Y* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X* = (0; 1/5; 8/5) – оптимальним планом прямої задачі.

Наше припущення відносно запропонованого плану виявилося правильним.

3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так:

Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі.

Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні; б) так, Х* = (0; 1/5; 8/5), min Z = 12/5; в) ні.

Список використаних джерел

1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., Изд-во Ленинград. ун-та, 1976. – 184 с.

2. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высш. шк., 1985.

3. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.

4. Белман Р. Динамическое программирование. – М.: Изд-во иностранной литературы, 1960.

5. Белман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965.

6. Вагнер Г. Основы исследования операций. – Т. 1–3. – М.: Мир, 1972.

7. Вентцель Е.С. Исследование операций. М.: «Сов. радио», 1972. – 552 с.

8. Вентцель Е.С. Элементы динамического программирования. – М.: Наука, 1964.

9. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. – М.: Советское радио, 1966.

10. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. – М.: Наука, 1969.

11. Данциг Дж. Линейное программирование, его обобщение и приложения. – М.: Прогресс, 1966.

12. Зайченко Ю.П. Дослідження операцій: Підручник. – 4-те вид., перероб. і допов. – К., 2000. – 688 с.

13. Зангвилл У. Нелинейное программирование. Единый подход. М.: «Сов.радио», 1973. – 312 с.

14. Ермольев Ю.М., Ястремский А.И. Стохастические модели и методы в экономическом планировании. М.: Наука, 1979. – 249 с.

15. Ермольев Ю.М. Методы стохастического программирования. – М.: Наука, 1976.

16. Калихман И.Л. Сборник задач по математическому программированию. – М.: Высшая шк., 1975.