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

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	0	…	0		…
2	x2			0	1	…	0		…
m	xm			0	0	…	1		…
m + 1			F0	0	0	…	0		…

 

Позначимо через 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), після чого можна висновувати, що .