Лекція 06. Двоїстість, тіньові ціни та чутливість у лінійному програмуванні

Коротко про лекцію

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

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

Постановка та базові поняття

1. Чому після оптимального плану виникає нове запитання

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

Сам оптимальний вектор \(x^*\) відповідає на запитання «скільки виробляти». Він ще не показує граничну цінність кожного обмеження. Для цього лінійне програмування вводить двоїсті змінні.

Двоїста змінна пов’язується з одним обмеженням прямої задачі. Її значення показує локальну оцінку відповідного ресурсу. Через цей зв’язок одна LP-модель породжує другу LP-модель з тією самою матрицею коефіцієнтів.

1.1. Чому задача називається двоїстою

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

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

Тіньова ціна — прикладне тлумачення двоїстої змінної для ресурсу. Вона показує локальну зміну оптимального значення цілі при малому збільшенні запасу ресурсу. Назва «тіньова» підкреслює, що це внутрішня розрахункова оцінка моделі, а не обов’язково реальна ринкова ціна.

2. Наскрізна пряма задача

Розглянемо задачу:

\[ \max Z=3x_1+2x_2 \]

за умов:

\[ x_1+x_2\le4 \]

\[ 2x_1+x_2\le5 \]

\[ x_1\ge0,\qquad x_2\ge0 \]

Перше обмеження задає запас першого ресурсу. Друге обмеження задає запас другого ресурсу.

Оптимальний план уже відомий:

\[ x^*= \begin{pmatrix} 1\\ 3 \end{pmatrix} \]

Його цільове значення:

\[ Z^*=3\cdot1+2\cdot3=9 \]

Обидва ресурсні обмеження активні:

\[ 1+3=4 \]

\[ 2\cdot1+3=5 \]

Тому жоден із двох ресурсів у цій точці не має запасу.

3. Що означає двоїста змінна

Позначимо через \(y_1\) оцінку однієї одиниці першого ресурсу. Через \(y_2\) позначимо оцінку однієї одиниці другого ресурсу.

Маємо вектор:

\[ y= \begin{pmatrix} y_1\\ y_2 \end{pmatrix} \]

Одиниці \(y_i\) залежать від предметного змісту. Якщо ціль вимірюється у грошових одиницях, а ресурс — у годинах, то \(y_i\) має одиницю «грошові одиниці на годину».

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

4. Загальна пряма форма

Для подальшого виведення зручно записати пряму задачу компактно:

\[ \max_x c^Tx \]

за умов:

\[ Ax\le b \]

\[ x\ge0 \]

Тут \(A\in\mathbb{R}^{m\times n}\) містить коефіцієнти обмежень. Вектор \(b\in\mathbb{R}^m\) містить запаси. Вектор \(c\in\mathbb{R}^n\) містить коефіцієнти цілі.

Для нашої задачі:

\[ A= \begin{pmatrix} 1 & 1\\ 2 & 1 \end{pmatrix} \]

\[ b= \begin{pmatrix} 4\\ 5 \end{pmatrix} \]

\[ c= \begin{pmatrix} 3\\ 2 \end{pmatrix} \]

Математична логіка

5. Вартість усіх доступних ресурсів

Якщо одна одиниця першого ресурсу оцінена в \(y_1\), то запас 4 має оцінку \(4y_1\).

Аналогічно запас 5 другого ресурсу має оцінку \(5y_2\).

Сумарна оцінка доступних ресурсів:

\[ 4y_1+5y_2 \]

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

\[ \min W=4y_1+5y_2 \]

Напрям мінімізації має важливий зміст. Ми шукаємо найменшу оцінку запасів, яка все ще достатня для пояснення прибутковості кожного продукту.

6. Звідки береться перше двоїсте обмеження

Одна одиниця першого продукту використовує 1 одиницю першого ресурсу та 2 одиниці другого.

За двоїстими цінами ресурсна оцінка цієї одиниці дорівнює:

\[ y_1+2y_2 \]

Прибуток від першого продукту дорівнює 3. Узгоджена оцінка ресурсів повинна покривати цю величину:

\[ y_1+2y_2\ge3 \]

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

7. Друге двоїсте обмеження

Одна одиниця другого продукту використовує по одній одиниці кожного ресурсу.

Її ресурсна оцінка:

\[ y_1+y_2 \]

Прибуток дорівнює 2, тому отримуємо:

\[ y_1+y_2\ge2 \]

Двоїсті змінні також невід’ємні:

\[ y_1\ge0,\qquad y_2\ge0 \]

Від’ємна оцінка ресурсу суперечила б поточній ресурсній інтерпретації стандартної задачі максимізації з обмеженнями типу \(\le\).

8. Повна двоїста задача

Отже, двоїста задача має вигляд:

\[ \min W=4y_1+5y_2 \]

за умов:

\[ y_1+2y_2\ge3 \]

\[ y_1+y_2\ge2 \]

\[ y_1,y_2\ge0 \]

У прямій задачі два обмеження породили дві двоїсті змінні. Дві прямі змінні породили два двоїсті обмеження.

Ця перестановка ролей є ключовою структурою двоїстості.

9. Матричний зв’язок прямої та двоїстої задач

Для стандартної пари:

\[ \max_x c^Tx \]

\[ Ax\le b,\qquad x\ge0 \]

двоїста задача записується:

\[ \min_y b^Ty \]

за умов:

\[ A^Ty\ge c \]

\[ y\ge0 \]

Транспонування \(A^T\) міняє місцями рядки та стовпці. Через це обмеження прямої задачі перетворюються на змінні двоїстої задачі, а прямі змінні — на двоїсті обмеження.

10. Слабка двоїстість

Слабка двоїстість стверджує, що для будь-якого допустимого прямого плану \(x\) і будь-якого допустимого двоїстого плану \(y\) виконується:

\[ c^Tx\le b^Ty \]

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

Це можна побачити послідовно. Із \(A^Ty\ge c\) та \(x\ge0\) маємо:

\[ x^TA^Ty\ge x^Tc \]

Ліва частина дорівнює:

\[ (Ax)^Ty \]

Оскільки \(Ax\le b\) та \(y\ge0\), отримуємо:

\[ (Ax)^Ty\le b^Ty \]

Поєднання двох нерівностей дає:

\[ c^Tx\le b^Ty \]

Тому двоїстий допустимий план автоматично дає межу для прямої цілі.

11. Сильна двоїстість

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

\[ c^Tx^*=b^Ty^* \]

Різницю називають розривом двоїстості (розрив двоїстості):

\[ g=\left|c^Tx-b^Ty\right| \]

Для оптимальної пари очікуємо дуже мале значення:

\[ g\le\varepsilon \]

У точній ручній арифметиці нашого прикладу розрив дорівнює нулю.

Алгоритм і покроковий розбір

12. Розв’язуємо двоїсту задачу вручну

У двоїстій задачі оптимум виникає в точці перетину двох активних меж:

\[ \begin{cases} y_1+2y_2=3\\ y_1+y_2=2 \end{cases} \]

Віднімемо друге рівняння від першого:

\[ y_2=1 \]

Підставляємо у друге:

\[ y_1+1=2 \]

Тому:

\[ y_1=1 \]

Отримуємо:

\[ y^*= \begin{pmatrix} 1\\ 1 \end{pmatrix} \]

Двоїста ціль:

\[ W^*=4\cdot1+5\cdot1=9 \]

Пряма ціль також дорівнює 9. Тому розрив двоїстості:

\[ g=|9-9|=0 \]

13. Тіньова ціна першого ресурсу

Маємо \(y_1^*=1\). Локально це означає: збільшення правої частини першого обмеження на одну малу одиницю збільшує оптимальне значення прямої цілі приблизно на 1.

Перевіримо зміну на \(0.5\):

\[ x_1+x_2\le4.5 \]

Друге обмеження залишається:

\[ 2x_1+x_2\le5 \]

Перетин активних меж дає:

\[ x_1=0.5,\qquad x_2=4 \]

Нове значення цілі:

\[ Z=3\cdot0.5+2\cdot4=9.5 \]

Приріст дорівнює:

\[ 9.5-9=0.5 \]

Це збігається з оцінкою \(y_1^*\cdot0.5=0.5\).

14. Тіньова ціна другого ресурсу

Для другого ресурсу маємо \(y_2^*=1\).

Збільшимо другу межу до 5.5:

\[ 2x_1+x_2\le5.5 \]

Перше обмеження залишимо рівним 4. Перетин дає:

\[ x_1=1.5,\qquad x_2=2.5 \]

Нова ціль:

\[ Z=3\cdot1.5+2\cdot2.5=9.5 \]

Приріст знову дорівнює 0.5. Локальна оцінка двоїстої змінної працює.

15. Чому слово «локальна» важливе

Тіньова ціна не зобов’язана залишатися сталою для великих змін запасу. Після певної зміни може змінитися активний базис.

Тоді оптимальна вершина переходить на інше поєднання меж. Двоїсті оцінки також можуть змінитися.

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

16. Комплементарна нежорсткість

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

Для ресурсного обмеження:

\[ b_i-a_i^Tx\ge0 \]

виконується умова:

\[ y_i\left(b_i-a_i^Tx\right)=0 \]

Якщо ресурс має додатний залишок, відповідна двоїста ціна в оптимумі дорівнює нулю.

Якщо двоїста ціна додатна, ресурсне обмеження повинно бути активним.

У нашому прикладі обидва ресурси використані повністю. Тому додатні значення \(y_1=y_2=1\) узгоджуються з комплементарністю.

17. Комплементарність для прямих змінних

Існує симетрична умова для двоїстих обмежень:

\[ x_j\left((A^Ty)_j-c_j\right)=0 \]

Оскільки \(x_1^*=1>0\), перше двоїсте обмеження активне:

\[ y_1+2y_2=3 \]

Оскільки \(x_2^*=3>0\), друге двоїсте обмеження також активне:

\[ y_1+y_2=2 \]

Це дає ще один незалежний спосіб перевірити оптимальну пару.

Програмна реалізація та перевірка

18. Від математики до Python

Для прямої задачі SciPy linprog мінімізує передану функцію. Тому максимізацію \(3x_1+2x_2\) передаємо через коефіцієнти \((-3,-2)\).

Математика	Python	Зміст
\(c\)	profit	коефіцієнти прямої цілі
\(A\)	resource_usage	витрати ресурсів
\(b\)	available_resources	запаси
\(x\)	production_plan	прямий план
\(y\)	shadow_prices	двоїсті змінні

19. Розв’язання прямої та двоїстої задач

# Імпортуємо NumPy, SciPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np
from scipy.optimize import linprog


# Задаємо матрицю коефіцієнтів; порядок рядків і стовпців має збігатися з математичною моделлю.
resource_usage = np.array([
    [1.0, 1.0],
    [2.0, 1.0],
])

# Задаємо праві частини, запаси або спостереження у порядку, узгодженому з рядками матриці.
available_resources = np.array([
    4.0,
    5.0,
])

# Задаємо коефіцієнти цільової функції в тому самому порядку, що й компоненти вектора змінних.
profit = np.array([
    3.0,
    2.0,
])

# Запускаємо linprog: ціль, матрицю нерівностей, праві частини та межі передаємо у фіксованому порядку.
primal = linprog(
    c=-profit,
    A_ub=resource_usage,
    b_ub=available_resources,
    bounds=(0.0, None),
    method="highs",
)

# Двоїста задача має обмеження A.T @ y >= c.
# Для linprog множимо їх на -1 і отримуємо <=.
dual = linprog(
    c=available_resources,
    A_ub=-resource_usage.T,
    b_ub=-profit,
    bounds=(0.0, None),
    method="highs",
)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not primal.success:
    raise RuntimeError(primal.message)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not dual.success:
    raise RuntimeError(dual.message)

# Обчислюємо величину прямої або двоїстої задачі для перевірки узгодженості.
production_plan = primal.x
shadow_prices = dual.x

# Обчислюємо величину прямої або двоїстої задачі для перевірки узгодженості.
primal_value = -primal.fun
dual_value = dual.fun

# Порівнюємо значення прямої та двоїстої цілей через розрив двоїстості.
duality_gap = abs(
    primal_value - dual_value
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Прямий план:", production_plan)
print("Двоїсті ціни:", shadow_prices)
print("Пряма ціль:", primal_value)
print("Двоїста ціль:", dual_value)
print("Duality gap:", duality_gap)

Очікуваний зміст результату:

Прямий план: [1. 3.]
Двоїсті ціни: [1. 1.]
Пряма ціль: 9.0
Двоїста ціль: 9.0
Duality gap: 0.0

Малі числові відхилення можливі через з рухомою комою арифметику.

20. Перевірка допустимості прямої задачі

Спочатку повторно обчислюємо:

\[ Ax^*= \begin{pmatrix} 4\\ 5 \end{pmatrix} \]

Порівняння з \(b\) дає нульові залишки:

\[ b-Ax^*= \begin{pmatrix} 0\\ 0 \end{pmatrix} \]

Тому прямий план допустимий.

21. Перевірка допустимості двоїстої задачі

Для \(y^*=(1,1)^T\):

\[ A^Ty^*= \begin{pmatrix} 3\\ 2 \end{pmatrix} \]

Це точно збігається з \(c\):

\[ A^Ty^*=c \]

Обидва двоїсті обмеження активні.

22. Візуальне читання двоїстих цін

Обидві тіньові ціни дорівнюють 1. Тому мале збільшення будь-якого активного ресурсу має однакову локальну цінність для цільової функції.

Стовпчики прямої та двоїстої цілі збігаються. Це візуально підтримує перевірку сильної двоїстості.

Інтерпретація, межі та підсумок

23. Як читати тіньова ціна у практичній задачі

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

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

Предметна одиниця ціни завжди походить із співвідношення «одиниці цілі / одиниці ресурсу».

24. Знак граничні оцінки у API чисельного розв’язувача

Під час використання linprog варто уважно читати документацію. SciPy повертає нев’язки і граничні оцінки для власної форми мінімізації.

У задачі максимізації ми змінили знак цільової функції. Через це знак чисельний розв’язувач гранична оцінка може відрізнятися від економічної тіньової ціни, яку ми використовуємо в ручному виведенні.

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

25. Коли двоїстість потребує обережності

Правила знаків залежать від форми прямої задачі. Обмеження типу \(\ge\), рівності, вільні змінні та задачі мінімізації змінюють відповідні знакові умови.

Тому таблицю правил варто застосовувати після приведення задачі до чітко визначеної форми.

Для поточного курсу базовим шаблоном є максимізація з \(Ax\le b\) та \(x\ge0\).

26. Типова помилка

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

26.1. Двоїста задача як сертифікат верхньої межі

Двоїсту задачу корисно читати як конструкцію верхньої межі для прямої максимізації. Візьмемо будь-які невід’ємні коефіцієнти \(y_1\) та \(y_2\). Помножимо перше пряме обмеження на \(y_1\), а друге — на \(y_2\).

Отримаємо:

\[ y_1(x_1+x_2)\le4y_1 \]

\[ y_2(2x_1+x_2)\le5y_2 \]

Додаємо нерівності:

\[ (y_1+2y_2)x_1+(y_1+y_2)x_2\le4y_1+5y_2 \]

Якщо одночасно виконується:

\[ y_1+2y_2\ge3 \]

і:

\[ y_1+y_2\ge2 \]

ліва частина не менша за пряму ціль \(3x_1+2x_2\). Тому маємо:

\[ 3x_1+2x_2\le4y_1+5y_2 \]

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

26.2. Геометричне читання двоїстої області

Двоїста задача також має дві змінні, тому її можна уявити на площині \((y_1,y_2)\).

Перше обмеження:

\[ y_1+2y_2\ge3 \]

задає півплощину над відповідною прямою. Друге:

\[ y_1+y_2\ge2 \]

задає ще одну півплощину. Умови невід’ємності залишають перший квадрант.

Двоїста ціль:

\[ W=4y_1+5y_2 \]

рухається в напрямку зменшення. Оптимальна точка \((1,1)\) лежить на перетині двох активних меж. Геометрично це повністю симетрично пошуку вершини у прямій задачі.

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

26.3. Чутливість як похідна за правою частиною

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

Позначимо оптимальне значення прямої задачі через функцію:

\[ \varphi(b) \]

Тут \(b\) — вектор ресурсів. Для малого приросту \(\Delta b_i\) маємо наближення:

\[ \varphi(b+\Delta b_i e_i)\approx\varphi(b)+y_i^*\Delta b_i \]

\(e_i\) — одиничний вектор, який змінює тільки компоненту \(b_i\).

У нашому прикладі \(y_1^*=1\) і \(y_2^*=1\). Тому локальна зміна будь-якого запасу на \(0.1\) дає очікуваний приріст цілі приблизно \(0.1\).

Це наближення має сенс, поки активний набір обмежень не змінився. Коли оптимум переходить на іншу вершину, функція \(\varphi(b)\) змінює локальний нахил.

26.4. Що відбувається з неактивним ресурсом

Розглянемо уявну модифікацію, де одне ресурсне обмеження має великий запас і не є активним в оптимумі.

Тоді:

\[ b_i-a_i^Tx^*>0 \]

Комплементарна нежорсткість вимагає:

\[ y_i^*=0 \]

Це має просте предметне пояснення. Додаткова одиниця ресурсу, якого вже достатньо, локально не покращує оптимальний план.

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

26.5. Знижена вартість як симетрична ідея

Двоїсті обмеження також мають залишки. Для прямої змінної \(x_j\) визначимо:

\[ s_j^{dual}=(A^Ty)_j-c_j \]

У задачі максимізації стандартної форми має виконуватися:

\[ s_j^{dual}\ge0 \]

Якщо \(x_j^*>0\), комплементарність дає:

\[ s_j^{dual}=0 \]

Тому додатна пряма змінна відповідає активному двоїстому обмеженню.

У нашому прикладі обидві прямі змінні додатні. Тому обидві двоїсті нерівності виконуються як рівності.

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

26.6. Практичний аудит двоїстої пари

Для навчального звіту корисно фіксувати окремі числа.

Перша перевірка — пряма допустимість:

\[ \max_i\max((Ax-b)_i,0) \le\varepsilon \]

Друга — двоїста допустимість:

\[ \max_j\max((c-A^Ty)_j,0) \le\varepsilon \]

Третя — розрив двоїстості:

\[ |c^Tx-b^Ty|\le\varepsilon \]

Четверта — комплементарність:

\[ \max_i \left| y_i(b_i-a_i^Tx) \right| \le\varepsilon \]

і:

\[ \max_j \left| x_j((A^Ty)_j-c_j) \right| \le\varepsilon \]

Коли всі ці перевірки проходять, маємо значно сильніший доказ коректності, ніж одне поле success.

26.7. Таблиця причинних зв’язків

Спостереження в оптимумі	Математичний сигнал	Практичне читання
ресурс використано повністю	\(b_i-a_i^Tx^*=0\)	ресурс активний
ресурс має запас	\(b_i-a_i^Tx^*>0\)	додаткова одиниця локально не потрібна
тіньова ціна додатна	\(y_i^*>0\)	ресурс локально цінний
пряма змінна додатна	\(x_j^*>0\)	відповідне двоїсте обмеження активне
розрив близький до нуля	$	c^Tx-b^Ty

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

26.8. Межі економічної інтерпретації

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

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

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

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

26.9. Як читати діагностика чисельного розв’язувача у контексті двоїстості

Сучасний розв’язувач лінійного програмування часто повертає більше інформації, ніж тільки вектор \(x\). Для нерівностей корисні нев’язка або запас та гранична оцінка.

Нев’язка показує запас обмеження. Для форми:

\[ A_{ub}x\le b_{ub} \]

типовий запас має зміст:

\[ s=b_{ub}-A_{ub}x \]

Нульовий запас означає активну межу. Додатний запас означає невикористаний запас.

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

У нашій прямій задачі максимізація реалізована через мінімізацію \(-Z\). Тому економічна тіньова ціна для початкової максимізації може мати протилежний знак до гранична оцінка у результат чисельного розв’язувача.

Такий нюанс показує важливу практичну звичку: API-поле спочатку потрібно пов’язати з математичною формою, яку фактично отримала бібліотека.

26.10. Перевірка малої зміни правої частини програмно

Чутливість можна перевірити повторним розв’язанням моделі після малої зміни ресурсу.

Для першого ресурсу беремо:

\[ \Delta b_1=0.1 \]

Очікувана локальна зміна прямої цілі:

\[ \Delta Z\approx y_1^*\Delta b_1=0.1 \]

Після повторного розв’язання порівнюємо:

\[ \frac{Z(b_1+0.1)-Z(b_1)}{0.1} \]

з \(y_1^*\).

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

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

26.11. Двоїстість і рішення про закупівлю ресурсу

Припустимо, додаткова одиниця першого ресурсу коштує \(p_1\) грошових одиниць. Тіньова ціна дорівнює \(y_1^*=1\).

Локальний чистий ефект можна оцінити як:

\[ \Delta \Pi\approx (y_1^*-p_1)\Delta b_1 \]

Якщо \(p_1=0.6\), то для малого приросту ресурсу очікуваний чистий ефект додатний.

Якщо \(p_1=1.4\), локальна закупівля знижує чистий результат за поточних припущень.

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

26.12. Двоїстість як міст до наступних тем

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

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

У задачах з обмеженнями з’являться множники Лагранжа. Для опуклих задач KKT-умови поєднають стаціонарність, допустимість і комплементарну нежорсткість.

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

26.13. Самоперевірка перед завершенням теми

Студент повинен уміти відтворити повний причинний маршрут.

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

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

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

26.14. Короткий алгоритм побудови двоїстої задачі

Для стандартної прямої максимізації зручно користуватися стабільною послідовністю. Спочатку випишіть матрицю \(A\), вектори \(b\) і \(c\). Далі створіть одну двоїсту змінну для кожного прямого обмеження. Після цього транспонуйте \(A\), перенесіть \(b\) у двоїсту ціль, а \(c\) — у праві частини двоїстих обмежень.

На завершення перевірте знаки змінних і напрям нерівностей. Потім розв’яжіть обидві задачі та порівняйте цільові значення.

Цей порядок зменшує кількість знакових помилок і робить побудову двоїстої моделі відтворюваною.

26.15. Міні-аудит перед здачею

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

26.16. Перевірка одиниць у двоїстій цілі

Коефіцієнт \(b_i\) має одиницю ресурсу, а \(y_i\) — одиницю цілі на одиницю ресурсу. Тому добуток \(b_i y_i\) має ту саму одиницю, що й пряма ціль. Ця перевірка допомагає підтвердити правильність економічного тлумачення двоїстої моделі.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

27. Підсумок

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

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

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