Двоїста задача лінійного програмування: економічна інтерпретаціязнаходження оптимальних планів
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 …
/> …
/> 2
x2
/>
/> 1 …
/> …
/>
m
xm
/>
/> … 1
/> …
/>
m + 1
/>
F0 …
/> …
/>
Позначимо через 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 у = (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.