Фінансовий менеджмент – Крамаренко Г. О. – 6.4.2.1. Класифікація невласних задач лінійного та випуклого програмування
Для розробки виробничих програм поточного і перспективного фінансового планування діяльності підприємств необхідною умовою їхнього функціонування є врахування різних факторів (умов), таких як режим роботи підприємства, вид залежності витрат від обсягів випуску продукції, узгодженість в роботі окремих структурних підрозділів і т. д. З метою наочності та загальності викладення процедур коригування суперечливої системи обмежень даний підхід до подолання несумісності в задачах перспективного і поточного фінансового планування подається на прикладі найпростіших моделей задач фінансового планування виробничо-господарської діяльності.
6.4.2.1. Класифікація невласних задач лінійного та випуклого програмування
Запишемо задачу лінійного програмування:
Тут ї – множина цілих чисел. Нехай 7-ї’ оптимальне значення.
Форма запису (6.1) задачі і зручна через її стандартну виробничо-економічну інтерпретацію, відповідно до якої Ь — вектор ресурсів, с – вектор цін. Стовпці матриці А моделюють технологічні способи шляхом завдання витрат ресурсів, які припадають на одиничну інтенсивність використання відповідних способів, так що вектор інтенсивності х= [х,, х2,…, ху задає рівень виробництва (фінансовий план виробництва).
Двоїстою до (6.1) виступає задача лінійного програмування
Ці множини називаються допустимими для /_ і і* відповідно.
Основний факт, що пов’язує задачі і і £.*, формулюється як теорема двоїстості: якщо задача /. розв’язувана, то /_* також розв’язувана, при цьому їхні оптимальні значення збігаються: / = / .
Якщо задача і розв’язувана, то вона називається власною задачею, якщо ж ні – невласною.
Припущення М* 0, М” * 0 рівносильне розв’язуваності задачі і, а відповідно, і задачі і*.
Якщо задача і невласна, то можливі такі три випадки:
Залежно від того, чи виконується одна з умов (6.3) – (6.5), будемо говорити про невласну задачу і відповідно 1-го, 2-го та 3-го роду.
З даної класифікації невласних задач лінійного програмування видно, що коли і – невласна задача 1-го роду, то і* – 2-го роду (і навпаки); якщо і – невласна задача 3-го роду, то /.* – також невласна задача 3-го роду (і навпаки).
Розглянемо кожну з цих умов. Перша з них означає, що, як тільки за деякого прирощення ДЬ є Ет система нерівностей
Сумісна, то задача
Розв’язувана.
Дійсно, із сумісності системи (6.6) та умови М*ф0 виходить розв’язуваність (6.7), а відповідно, в силу теореми двоїстості і
А також, якщо при деякому АЬ задача (6.7) розв’язувана, то, розв’язувана і задача (6.8), то М* ф 0.
Умова (6.4) означає, що в задачі і оптимальне значення 7 дорівнює + оо. а умова (6.5) еквівалентна тому, що при будь-якому прирощенні АЬ, яке забезпечує розв’язуваність системи (6.6), оптимальне значення задачі (6.7) дорівнює + оо, що є наслідком теореми двоїстості для задач лінійного програмування.
Запишемо задачу випуклого програмування у формі
Де 2- множина цілих чисел.
Введемо позначення: 7 – оптимальне значення задачі (6.9),
Двоїстою до С будемо вважати задачу
Або еквівалентну до неї задачу
Остання має вигляд задачі лінійного програмування з нескінченним числом обмежень. Задача (6.9) називається власною, якщо
Де І – оптимальне значення задачі (6.10); в іншому випадку – невласною.
Виділимо (як у лінійному випадку) три класи невласних задач випуклого програмування залежно від пустоти або непусто” ти допустимих множин М і ЛГ задач С і С* відповідно:
Залежно від виконуваності властивостей (6.1)-(6.3) будемо говорити про невласну задачу С 1-го, 2-го або 3-го роду відповідно.
Для невласних задач випуклого програмування не може бути дано характеристику у тій формі, яка має місце для невласних задач лінійного програмування. Проте справедливі формули
(2 votes, average: 2,50 out of 5)