Лекция 5 звернення матриць. Подвійність у лінійному програмуванні. Одночасне рішення пари двоїстих задач лінійного програмування.

Зворотна матриця

Нехай А и В - дві матриці наступного виду:

і ;

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

,

називану добутком А на В (пишуть ІЗ=АВ), за правилом

,

де i=1,...,m і j=1,...,r. Серед матриць прийнято виділяти й позначати буквою E

наступну матрицю, називану одиничної, -

;

пояснимо: одинична матриця завжди квадратна, по її діагоналі коштує 1, а всі інші елементи - нулі, тобто якщо Е=(е_ij), i,j=1,...,n, те

.

Говорять, що квадратна матриця А и квадратна матриця В того ж розміру є зворотними по відношенню друг до друга, якщо виконано хоч одне з матричних рівностей - або АВ=Е або ВА=Е. Можна перевірити, що якщо одне із цих матричних рівностей виконується, то виконується й інше. Про всякий випадок пояснимо, що слова «матрична рівність» означають рівність заелементне, тобто якщо має місце рівність матриць U=V, те це означає, що в них рівні кількості рядків і рівні кількості стовпців і при цьому u_ij=v_ij для всіх i і j. Зокрема, система лінійних алгебраїчних рівнянь із п.3 Лекції 1 може бути записана у вигляді AX=B, де

,

а А и В мають той же змив, що й у п.3 Лекції 1.

Неважко помітити, що якщо для квадратної матриці А потрібно знайти зворотну матрицю В, те треба вирішити n систем лінійних алгебраїчних рівнянь із однієї й тої ж матрицею: запишемо матричну рівність АВ=Е поелементно (тут усього вийде n² рівностей), причому будемо послідовно дорівнювати стовпці - перший стовпець лівої частини до першого стовпця правої частини, другий стовпець лівої частини до другого стовпця правої частини й т.д. –

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

Визначення пари двоїстих задач лінійного програмування.

Нагадаємо, що основна задача лінійного програмування - це задача пошуку максимуму лінійної функції

при обмеженнях

.

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

.

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

Задачею, двоїстої до ОЗЛП, називається задача пошуку мінімуму лінійної функції

при обмеженнях:

,

,

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

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

1) існує тоді й тільки тоді, коли існує й при цьому має

місце рівність: ;

2) якщо одна із задач суперечлива, те інша або теж суперечлива, або необмежена;

3) якщо одна із задач необмежена, те інша суперечлива.

Одночасне рішення пари двоїстих задач лінійного програмування.

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

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

Можна помітити, що проведення симплекс-методу із цією таблицею у відношенні змінних x_j, y_i дає рішення й для двоїстої задачі, якщо на кожному кроці міняти місцями й відповідні u_i, v_j. Ми продемонструємо це нижче на конкретному прикладі.

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

Отже, потрібно вирішити одночасно дві екстремальні задачі. Задача перша:

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

Тепер по таблиці нам легше буде записати умова двоїстої задачі. А саме:

Таким чином, змінні u₃, u₄ - вільні. Алгоритм симплекс-методу нам уже відомий з попереднього викладу; тому будемо лише вказувати розв'язні елементи для чергових модифікованих жордановых виключень (як звичайно, що дозволяє елемент виділяється в таблиці сірим тлом):

От результат відповідного модифікованого жорданова виключення:

Наступний розв'язний елемент:

Проводимо відповідне модифіковане жорданово виключення:

Черговий розв'язний елемент:

Стовпець, що починається з нуля, ураховувати далі, мабуть, не має змісту. Черговий результат:

І знову стовпець під нулем не будемо далі враховувати; розв'язний елемент:

Результат відповідного модифікованого жорданова виключення:

Отже, висновки:

крапка екстремуму для z:

крапка екстремуму для w: