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

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (1)-(3) та (4)-(6) з економічною інтерпретацією.

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

або . (7)

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

(8)

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

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

.

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

Перша теорема двоїстості дає змогу в процесі розв’язування однієї задачі водночас знаходити план другої.

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

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

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

(9)

.

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

(10)

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

Аналогічно:

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

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

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

(11)

. (12)

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

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

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

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

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

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

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

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

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

(13)

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

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

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

(14)

(15)

(16)

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

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

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

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

max Z = – 5 x₁ + 2 x₂;

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

max Z = – 5 x₁ + 2 x₂;

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

min F = – y₁ + 5 y₂;

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

1. max Z = – 5 x₁ + 2 x₂ + 0 x₃ + 0 x₄;

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

,

де , , , , .

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

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

max Z = – 5 x₁ + 2 x₂ + 0 x₃ + 0 x₄ – М x₅;

У цій задачі х ₄ та х ₅ – базисні змінні, а х₁, х₂, х₃ – вільні. Нехай х₁ = х₂ = х₃ =0, тоді х₄ =5; х₅ =1.

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

X₀ =(0; 0; 0; 5; 1), Z₀ = – M.

4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:

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

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

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

min F = max Z = 10/3.

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

,

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

.

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

Отже,

,

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

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

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

min Z = x₁ + 2 x₂ + 2 x₃;

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

mах F = y₁ + 4 y₂;

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

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

Рисунок 2

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

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

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

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

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

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

Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х₁ =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) є оптимальними планами відповідно прямої та двоїстої задач.

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

min Z = 12 x₁ – 4 x₂ + 2 x₃;

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

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

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

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

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

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

max F = y₁ + 2 y₂;

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

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

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

Z = 12 × 8/7 – 4 × 3/7 + 2 × 0 = 12.

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

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

;

.

Для визначених значень у₁ = 4; у₂ = 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.

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

Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у₁ та у₂: 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) за яких умов оптимальний план є стійким;

2) чи є вигідним додаткове залучення ресурсів;

3) як зміниться ефективність виробництва в разі загострення конкуренції на ринку збуту (оцінити виправданість у цій ситуації зниження цін на продукцію);

4) доцільність виробництва нової продукції;

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

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