Несиметричні двоїсті задачі. Теорема двоїстості.

Двойственность в линейном программировании

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

Зв'язок вихідної і двоїстої задач полягає в тому, що коефіцієнти Cj функції мети вихідної завдання є вільними членами системи обмежень двоїстої задачі, вільні члени Bi системи обмежень вихідної завдання служать коефіцієнтами функції мети двоїстої завдання, а матриця коефіцієнтів системи обмежень двоїстої задачі є транспонованої матрицею коефіцієнтів системи обмежень вихідної задачі. Рішення двоїстої задачі може бути отримано з рішення вихідної і навпаки.

Як приклад розглянемо завдання використання ресурсів. Підприємство має т видів ресурсів у кількості bi (i = 1, 2, ..., m) одиниць, з яких виробляється n видів продукцій. Для виробництва 1 од. i-й продукції витрачається aij од. t-гo ресурсу, а її вартість становить Cj од. Скласти план випуску продукції, що забезпечує її максимальний випуск у вартісному вираженні. Позначимо через xj (j = 1,2, ..., n) кількість од. j-й продукций, Тоді вихідне завдання сформулюємо так.

Знайти вектор Х =(x₁, x₂, …, x_n), котрий задовольняє обмеженням

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n £ b_1,

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n £ b_2,                  x_j ³ 0 (j =1,2, ..., n)

…………………………………

a_m1x₁ + a_m2x₂ + … + a_mnx_n £ b_m,

і доставляє максимальне значення лінійної функції

Z = C₁x₁ + C₂x₂ + … + C_nx_n,

Оцінимо ресурси, необхідні для виготовлення продукції. За одиницю вартості ресурсів приймемо одиницю вартості своєї продукції. Позначимо через уi (j = 1,2, ..., m) вартість одиниці i-го ресурсу. Тоді вартість всіх витрачених ресурсів, що йдуть на виготовлення одиниці j-й продукції, дорівнює . Вартість витрачених ресурсів не може бути менше вартості остаточного продукту, тому має виконуватися нерівність ³ C_j, j =1,2, ..., n. Вартість усіх наявних ресурсів виразиться величиною . Отже, двоїсту задачу можна сформулювати наступним чином.

Знайти вектор Y =(y₁, y₂, …, y_n), котрий задовольняє обмеженням

a₁₁y₁ + a₁₂y₂ + … + a_m1y_m £ C_1,

a₁₂y₁ + a₂₂y₂ + … + a_m2y_m £ C_2,                  y_j ³ 0 (i =1,2, ..., m)

…………………………………

a_1ny₁ + a_2ny₂ + … + a_mny_m £ C_m,

і доставляє мінімальне значення лінійної функції

f = b₁y₁ + b₂y₂ + … + b_my_m.

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

Вихідне завдання. Скільки і якої продукції xj (j = 1,2, ..., n) необхідно зробити, щоб при заданих вартостях Cj (j = 1,2, ..., n) одиниці продукції і розмірах наявних ресурсів bi (i = 1 , 2, ..., n) максимізувати випуск продукції у вартісному вираженні.

Двоїста задача. Яка повинна бути ціна одиниці кожного з ресурсів, щоб при заданих кількостях ресурсів bi і величинах вартості одиниці продукції Ci мінімізувати загальну вартість затрат?

Змінні уi називаються оцінками або обліковими, неявними цінами.

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

Несиметричні двоїсті задачі. Теорема двоїстості.

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

Вихідне завдання. Знайти матрицю-стовпець X= (x₁, x₂, …, x_n), яка задовольняє обмеженням

(1.1)                   AX = A₀, Х ³ 0

і мінімізує лінійну функціюZ=СХ.

Двоїста задача. Знайти матрицю-рядок Y= (y₁, y₂, …, y_m), яка задовольняє обмеженням

(1.2)                    YA £ С

і максимізує лінійну функцію f = YA₀

В обох задачах C= (c₁, c₂, …, c_n) - матриця-рядок, A₀ = (b₁, b₂, …, b_m) — матриця-стовпець, А= (a_ij) — матриця коефіцієнтів системи обмежень. Зв'язок між оптимальними планами пари двоїстих задач встановлює наступна теорема.

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

min Z = max f.

Якщо лінійна функція одної з задач не обмежена, то інша не має рішення.

Доведення. Припустимо, що вихідна задача має оптимальний план, який отримано симплекс методом. Не порушуючи спільності, можна вважати, що остаточний базис складається з т перших векторів A₁, A₂, ..., A_m. Тоді остання симплекс­ таблиця має вигляд табл. 1.1.

Т а б л и ц я 1.1

Нехай D — матриця, складена з компонент векторів остаточного базису A₁, A₂, ..., A_m; тоді табл. 1.1 складається з коефіцієнтів розкладання векторів A₁, A₂, ..., A_n вихідної системи по векторах базису, тобто кожному вектору A_j в цій таблиці відповідає та­кий вектор X_j що

(1.3)              A_j= DX_j(j= 1,2, ,.., n)

.

Для оптимального плана отримуєм

(1.4)              A₀ = DX*,

де X* = (x*₁, x*₂, …, x*_m).

Позначимо через  матрицю, складену з коефіцієнтів розкладання векторів А_j (j = 1, 2, ..., n), записанних в табл. 1.1. Тоді, враховуючи співвідношення (1.3) и (1.4), отримуємо:

(1.5)                 A = D , D^-1A = ,

(1.6)                     A₀=DX*; D^-1A₀ = X*,

(1.7)                 min Z= C*X*,

(1.8)                 = C* —C £ 0,

де С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a  = (C*X₁ – C₁; С*Х₂ - С₂, ..., C*X_n – C_n) = (Z₁ – С₁; Z₂ - C₂; ..., Z_n — C_n) — вектор, компоненти якого не позитивні, так як вони збігаються з Z_j — C_j  £ 0, соответствующими оптимальному плану.

Оптимальний план вихідної задачі має виглядX* = D^-1 А₀, тому оптимальний план двоїстої задачі шукаємо у вигляді:

(1.9)                      Y* = C*D^-1.

Покажемо, що Y* дійсно план двоїстої задачі. Для цього обмеження (1.2) запишемо у вигляді нерівності YA — С £ 0, в ліву частину якого підставимо Y*. Тоді на підставі (1.9), (1.5)  та (1.8) отримуємо

Y* А – С = С* D^-1А – С = С*  - С £ 0,

Звідки знаходимоY*A £ С.

Так як Y* задовольняє обмеженням (1.2), то це і є план двоїстої задачі. При цьому в плані значення лінійної функції двоїстої завдання f (Y *) = Y * A0. Враховуючи співвідношення (1.9), (​​1.6) і (1.7), маємо (1.10)

f(Y*) = Y*A₀ = C*D^-1 A₀ = C*X* = min Z(X).

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

Доведемо тепер, що Y* є оптимальним планом. Помножимо (1.1) на будь-який план Y двоїстої завдання, а (1.2) - на будь-який план X вихідної завдання: YAX=YA₀=f (Y), YAX £ СХ = Z (X), звідси випливає, що для будь-яких планів Х іY виконується нерівність

(1.11)               f (Y) £ Z (X).

Цим же співвідношенням пов'язані і екстремальні значення max f (Y) min Z£ (Х). З останнього нерівності укладаємо, що максимальне значення лінійної функції досягається тільки у випадку, якщо max f (Y) = min Z (X), але це значення [см. (1.10)] f (Y) досягає при плані Y *, отже, план Y * - оптимальний план двоїстої задачі. Аналогічно можна довести, що якщо двоїста задача має рішення, то вихідна також має рішенням і має місце співвідношення max f (Y) = min Z (X).

Для доказу другої частини теореми припустимо, що лінійна функція вихідної завдання не обмежена знизу. Тоді з (1.11) випливає, що f(Y) £ -¥ . Цей вираз позбавлене сенсу, отже, двоїста задача не має рішень.

Аналогічно припустимо, що лінійна функція двоїстої завдання не обмежена зверху. Тоді з (1.11) отримуємо, що Z (X) ³ +¥. Цей вираз також позбавлено сенсу, по-цьому вихідна задача не має рішень.

Доведена теорема дозволяє при вирішенні однієї з двоїстих завдань знаходити оптимальний план іншої.

Вихідна задача. Знайти мінімальне значення лінійної функції Z = x₂ – x₄ – 3x₅ при обмеженнях

x₁ + 2x₂     - x₄ + x₅    = 1,

- 4x₂ + x₃ + 2x₄ – x₅    = 2,          x_ij ³ 0 (j = 1, 2, …, 6)

3x₂             + x₅ + x₆ = 5,

Тут мятриця-рядок С = (0;. 1; 0; —1; — 3, 0), матриця-стовпець

        1                                1 2 0 -1 1 0

A₀ = 2                A =  0 -4 1 2 -1 0

        3                             0 3 0 0 1 1

         1 0 0

         2 -4     3

A’’ =  0 1 0

        -1 2 0

         1 -1 0

         0 0 1

Двоїста задача. Знайти максимальне значення лінійної функції f = y1 + 2y2 +5 y3 при обмеженнях

 y₁                £ 0,

2y₁ – 4y₂ + 3y₃ £ 1,

      y₂      £ 0,

-y₁ + 2y₂      £ -1,

y₁ – y₂ + y₃ £ -3,

               y₃ £ 0.

Решение исходной задачи находим симплексным методом (табл. 1.2).

Оптимальний план вихідної задачіX* = (0; 1/3; 0; 11/3; 4; 0), при якому Z_min = - 46/3, отриманий у четвертій ітерації табл. 1.2. Використовуючи цю ітерацію, знайдемо оптимальний план двоїстої задачі. Згідно теоремі подвійності оптимальний план двоїстої задачі знаходиться зі співвідношення Y* =C*D^-1, де матрицяD^-1 - матриця, зворотна матриці, складеної з компонент векторів, що входять в останній базис, при якому отримано оптимальний план вихідної задачі. Минулий базис входять вектори A₅, A₄, A₂; значить,

                              1 -1 2

D = (A₅, A₄, A₂)= -1 2 -4

                              1 0 3

Зворотній матрицяD^-1 утворена з коефіцієнтів, що стоять в стовпцяхA₁, A₃,A6 четвертої ітерації:

           2  1      0

D^-1 =    -1/3 1/3 2/3

        -2/3 -1/3 1/3

 З цієї ж ітерації слідуєС* = (— 3; —1; 1). Таким чином

                                                             2  1  0

                Y = С*D^-1= (-3; -1; 1) · -1/3 1/3 2/3

                                                          -2/3 -1/3 1/3

Y*=(-19/3; -11/3; -1/3),

тобто. y_i = С*Х_i, де Х_i — коефіцієнти розкладання останньої ітерації, що стоять в стовпцях векторів первісного одиничного базису.

Отже, i-ту двоїсту зміну можна отримати з значення оцінки (m + 1)-й рядки, стоїть проти відповідного вектора, що входив в початковий одиничний базиc, якщо до неї додати відповідне значення коефіцієнта лінійної функції: у₁ = — 19/3 + 0 = — 19/3; y₂ = -11/3 + 0 = -11/3; у₃ = -1/3+0 = -1/3. При цьому план max f = -46/3.

Симетричні двоїсті задачі

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

Вихідна задача. Знайти матрицю-стовпець Х = (x₁, x₂, …, x_n), яка задовольняє системі обмежень (1.12).                АХ>А₀, Х>0

і мінімізує лінійну функцію Z = СХ.

Двоїста задача. Знайти матрицю-рядок Y = (y₁, y₂, …, y_n), яка задовольняє системі обмежень YA £ C, Y ³ 0 і максимізує лінійну функцію f = YA₀.

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

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

Вихідна задача. Знайти мінімальне значення лінійної функції Z = x₁ + 2x₂ + 3x₃ при обмеженнях

 2x₁ + 2x₂ - x₃ ³ 2,

x₁ - x₂ - 4x₃ £ -3,       x_i ³ 0 (i=1,2,3)

x₁ + x₂ - 2x₃ ³ 6,

 2x₁ + x₂ - 2x₃ ³ 3,

Очевидно, для того щоб записати двоїсту задачу, спочатку необхідно систему обмежень вихідної завдання привести до вигляду (1.12). Для цього другу нерівність слід помножити на -1.

Двоїста задача. Знайти максимум лінійної функції f = 2y₁+ 3y₂ + 6y₃ + 3y₄ при обмеженнях

2y₁ - y₂ + y₃ + 2y₄ £ 1,

2y₁ + y₂ + y₃ + y₄ ³ 2,

 -y₁+ 4y₂ - 2y₃ - 2y₄ ³ 3,

Для рішення вихідної завдання необхідно ввести чотири додаткові перемінні і після перетворення системи - одну штучну. Таким чином, вихідна симплексная таблиця буде складатися з шести рядків і дев'яти стовпців елементи яких підлягають перетворенню.

Двоїсту задачу вирішуємо симплексним методом (табл. 1.3).

Оптимальний план двоїстої задачі Y* = (0; 1/2; 3/2; 0), f_max = 21/2.

Оптимальний план вихідної задачі знаходимо, використовуючи оцінки (m + 1)-го рядка останньої ітерації, які знаходяться в стовпцях A₅, A₆, A₇ : x₁ = 3/2 + 0 = 3/2; x₂ = 9/2 + 0 = 9/2; x₃= 0+ 0 = 0. При оптимальному плані вихідної задачіX* = (3/2; 9/2; 0) лінійна функція досягає найменшого значення: Z_min =21/2.

Т а б л и ц а 1.3