Необхідні і достатні умови для оптимального розв’язку двоїстої задачі

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

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

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. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:

Базис	Сбаз	План	–5				– М	q
x 1	x 2	x 3	x 4	x 5
x5 x4	–М 0	1 5	1 2	1 3	– 1 0	0 1	1 0	1 5/3
Zj – cj ³ 0	0 – М	5 – М	–2 – М	0 М	0 0	0 0
x2 x4	2 0	1 2	1 –1	1 0	–1 3	0 1	1 –3	– 2/3
Zj – cj ³ 0				– 2		2 М
x 2 x 3	2 0	5/3 2/3	2/3 –1/3	1 0	0 1	1/3 1/3	0 –1
Zj – cj ³ 0	10/3	19/3			2/3	0 М

 

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

Х* = (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.

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

19. Теореми двоїстості, які дозволяють знайти розв’язок прямої задачі ЛП

Теорема (перша теорема двоїстості).

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

Якщо X⁰ – оптимальній розв’язок прямої задачі, а

Y⁰ – оптимальний розв’язок двоїстої задачі, то справедлива слідуюча рівність: .

Економічний зміст першої теореми двоїстості.

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

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

,

де – це значення стовпчика в останній симплекс таблиці.

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

 

Теорема (друга теорема двоїстості для симетричних задач).

 

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

Наслідок.

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

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

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

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

? Теорема (третя теорема двоїстості).

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

Економічний зміст третьої теореми двоїстості.

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

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