1. Двоїсті задачі лінійного програмування

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

Двоїсті системи рівнянь. Нехай маємо дві системи функцій:

Друга с-ма р-нь складена так, що матриці коефіцієнтів при змінних –xj(j=1,n) , ui(i=1,m) ,будуть транспоновані одна до одної. Складемо для цих с-м симплекс- таблиці. Для 1-ї системи.

-x1…-xs… -xn

y1 a11…-a1s…a1n

yk ak1…aks…akn

ym am1..ams…amn

Зробимо крок МЖВ виключаючи з базису змінну yk і вводячи до базису змінну xs

-x1…-yk…-xn

y1 a11…a1s..akn /aks

xs ak1…1….akn

ym am1..-ams..amn

Для 2-ї с-ми ф-цій складемо симплекс-табл. таким чином , щоб залежні змінні vj(j=1,n) ,були вгорі, а незалежні змінні – ліворуч, і зробивши крок МЖВ маємо виключаючи з базису

змінну νs і вводячи до базису змінну uk

ν1….uk… νn

u1 a11..-a1s..a1n

νs ak1…1…akn /aks

um am1..-ams..amn

З наведених таблиць випливає, що коли над табли­цею, яка відповідає першій системі, зробити крок МЖВ з

розв'язувальним елементом aks, а над таблицею, яка відпо­відає другій системі, зробити крок ЗЖВ з розвзувальним елементом aks, то дістанемо однакові таблиці. Отже суміщення цих таблиць доцільне, оскільки крок МЖВ одночасно перетворює обидві таблиці. Суміщена табли­ця піля кроку МЖВ матиме вигляд

ν1….uk…. νn

-x1...-yk…-xn

u1 y1 a11...-a1s…a1n

νs xs ak1…1…. akn /aks

um ym am1..-ams..amn