5. Зв’язок між розв’язками прямої і двоїстої задач лінійного програмування

Перша та друга теореми двоїстості дають змогу за розв’язком однієї з двоїстих задач знайти розв’язок іншої.

Запишемо співвідношення канонічної задачі лінійного програмування та двоїстої до неї у матричному вигляді:

пряма задача

(2.26)

(2.27)

(2.28)

двоїста задача

(2.29)

(2.30)

де – матриця-рядок змінних прямої задачі;

– матриця-рядок коефіцієнтів цільової функції прямої задачі;

– матриця коефіцієнтів системи обмежень прямої задачі:

; – матриця-рядок вільних членів системи обмежень прямої задачі; – матриця-рядок змінних двоїстої задачі.

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

, (2.31)

де – обернена до матриці ;

– матриця, складена із базисних стовпців матриці що відповідають оптимальному розв’язку прямої задачі;

– коефіцієнти цільової функції при базисних невідомих.

Приклад 5. Дана задача лінійного програмування

(2.32)

(2.33)

. (2.34)

Потрібно: 1) знайти симплекс-методом розв’язок даної задачі; 2) скласти двоїсту задачу до заданої; 3) знайти симплекс-методом розв’язок двоїстої задачі; 4) знайти розв’язок двоїстої задачі за співвідношенням (2.31) та порівняти з розв’язком, знайденим симплекс-методом.

Розв’язання. 1. Ввівши додаткові невідомі запишемо всі обмеження прямої задачі у вигляді строгих рівностей

(2.35)

Розв’язок даної задачі шукатимемо за допомогою Maple. За вільні виберемо змінні x₃, x₆:

> z:=10*x[1]–x[2]–42*x[3]–52*x[4]:

Sys:={- 3*x[1] + x[2]+4*x[3]+x[4]+x[5] = 1,

3*x[1]–2*x[2]+2*x[3]–2*x[4]+x[6] = -9,

- 2*x[1]+x[2]+x[3]+3*x[4] = 2,

- 3*x[1]+2*x[2]–3*x[3] = 7}:

sols1:=solve (Sys, {x[1], x[2], x[4], x[5]});

Знайдемо значення базисних змінних

> subs(x[3]=0, x[6]=0, %);

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

> ‘z’=subs(%%, z);

.

Збільшення будь-якої з вільних невідомих – або приводить до зменшення цільової функції, отже знайдений опорний план – оптимальний:

, (2.36)

причому

. (2.37)

2. Складемо задачу, двоїсту до заданої задачі (2.32) – (2.34):

(2.38)

(2.39)

. (2.40)

3. Знайдемо симплекс-методом розв’язок двоїстої задачі (2.38) – (2.40). Перш за все зведемо двоїсту задачу до канонічного вигляду.

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

. (2.41)

_{Крім цього перетворимо нерівності системи обмежень (2.39) на строгі рівності, дістанемо}

(2.42)

(2.43)

Оскільки ліві частини нерівностей (2.39) не менші правих частин, то від лівих частин відняли невід’ємні додаткові невідомі

В Maple вказані дії зручно реалізувати в такій послідовності. Запишемо цільову функцію (2.38) та систему обмежень (2.39)

> F:=y[1]–9*y[2]+2*y[3]+7*y[4]:

Sys0:=[–3*y[1]+3*y[2]–2*y[3]–3*y[4]>=10,

y[1]-2*y[2]+y[3]+2*y[4]>= -1,

4*y[1]+2*y[2]+y[3]–3*y[4]>=-42,

y[1]-2*y[2]+3*y[3]>= -52];

Введенням додаткових змінних перетворимо нерівності на строгі рівності

> Sys1:=[-3*y[1]+3*y[2]–2*y[3]–3*y[4]=10,

y[1]–2*y[2]+y[3]+2*y[4]=-1,

4*y[1]+2*y[2]+y[3]–3*y[4]=-42,

y[1]–2*y[2]+3*y[3]=-52];

Подамо змінні , у вигляді різниці двох додаткових невід’ємних змінних: і подивимося як змінилися рівності, що є елементами списку Sys1

> y[3]:=y1[3]-y2[3]:y[4]:y1[4]-y2[4]:

Sys1;

Всього рівнянь 4, змінних – 10, отже, для знаходження базисного розв’язку 10 – 4 = 6 змінних потрібно вибрати за вільні. Вибираємо за вільні та знаходимо загальний розв’язок

> sols1:=solve (convert (Sys1, set),{y[2], y2[3], y1[4], y[7]});

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

> subs(y[1]=0, [3]=0, y2[4]=0, y[5]=0, y[6]=0, y[8]=0, sols1);

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

> ‘F’=subs(sols1, F);

.

Збільшення будь-якої вільної невідомої не може зменшити значення цільової функції, отже, , що дорівнює z_max (див. (2.37)).

Отже, оптимальним є такий розв’язок

, (2.44)

або з урахуванням співвідношень (2.41)

. (2.45)

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

4. Знайдемо розв’язок двоїстої задачі за співвідношенням (2.31). Оптимальному розв’язку (2.36) прямої задачі відповідають такі базисні змінні: (адже за вільні були прийняті змінні та ). Отже, коефіцієнти цільової функції (2.32) при базисних невідомих дорівнюють 10, -1, -52, 0:

> C[b]:=matrix([[10, -1, -52, 0]]):

Створимо матрицю з коефіцієнтів системи (2.35) при базисних змінних

> A[b]:=matrix([[-3, 1, 1, 1], [3, -2, -2, 0], [-2, 1, 3,0], [-3, 2, 0, 0]]);

Знайдемо матрицю, обернену до створеної матриці

> A_1[b]:=linalg[inverse](A[b]):

Оскільки елементи цієї матриці нас не цікавлять, результат операції присвоюється Maple-змінній A_1[b], але на екран монітора не виводиться.

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

> Y[0]=evalm(C[b]&*A_1[b]);

.

Отриманий розв’язок є тотожним розв’язку (2.45), якщо із останнього вилучити додаткові (допоміжні) змінні

Отже, якщо симплекс-методом знайдено розв’язок одної із пари двоїстих задач, то розв’язок іншої може бути легко знайдений за співвідношенням (2.31), що незрівнянно простіше в порівняні з розв’язанням двоїстої задачі як окремої задачі лінійного програмування.

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

Приклад 6. За допомогою другої та першої теорем двоїстості знайти розв’язок двоїстої задачі (2.38) – (2.40) із прикладу 5, якщо відомий розв’язок (2.36) прямої задачі (2.32) – (2.34).

Розв’язання. За першою теоремою двоїстості F_min = z_max = 21.

В оптимальному розв’язку (2.36) прямої задачі відмінними від нуля є змінні ( змінна – нас не цікавить, оскільки це додатково введена змінна). Отже, відповідні їм нерівності двоїстої задачі повинні перетворюватися на строгі рівності при оптимальних значеннях змінних двоїстої задачі. Згідно з (2.39), матимемо

(2.46)

До цих трьох рівнянь додаємо четверте – завдяки відомому оптимальному значенні цільової функції (2.38)

. (2.47)

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

> System:=[-3*y[1]+3*y[2]-2*y[3]-3*y[4]=10,

y[1]-2*y[2]+y[3]+2*y[4]=-1,

y[1]-2*y[2]+3*y[3]=-52,

y[1]-9*y[2]+2*y[3]+7*y[4]=21]:

Y[0]=solve(convert(System, set));

.

Очевидно, що отримано той самий розв’язок, що і в прикладі 5, за допомогою співвідношення (2.31). Першою та другою теоремами двоїстості можна користуватися для знаходження розв’язку двоїстої задачі і у випадку, коли пряма задача розв’язана геометричним методом, а отже, співвідношенням (2.31) скористатися неможливо.