Тема 1.3. Двоїстість у задачах лінійного програмування

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

Розглянемо стандартну задачу лінійного програмування:

(max) ,

(1.3.1)

.

Увівши m-вимірний вектор-рядок , побудуємо стандартну задачу вигляду

(min) ;

(1.3.2)

.

Задача (1.3.2) називається двоїстою до задачі (1.3.1). Відповідно, задача (1.3.1) називається прямою стосовно до задачі (1.3.2).

Зі співставлення задач (1.3.1) і (1.3.2) визначаються правила, згідно яких одна стандартна задача (пряма) перетворюється в іншу (двоїсту). Змінних у_і в задачі (1.3.2) стільки, скільки обмежень у задачі (1.3.1). Матриця умов задачі (1.3.2) – транспонована матриця умов задачі (1.3.1). Задача максимізації переходить в задачі мінімізації, обмеження-нерівності типу “  “ замінюють обмеженнями типу “  ”. Вектор коефіцієнтів цільової функції прямої задачі стає вектором обмежень двоїстої задачі, а вектор обмежень задачі (1.3.1) стає вектором цільової функції двоїстої задачі (1.3.2). Звернемо увагу на те, що при стандартності однієї з двоїстих задач інша теж стандартна. Система обмежень в обох випадках задана нерівностями, спрямованими у протилежні боки.

Розглянемо тепер канонічну задачу

(1.3.3)

Правила побудови двоїстої задачі можна застосувати до задачі (1.3.3), якщо попередньо записати її у вигляді стандартної задачі. В результаті задачі, двоїста до канонічної, матиме вигляд

(min) , (1.3.4)

причому на вектор не накладають умову не-від’ємності.

Можна перевірити, що задача, двоїста до задачі (1.3.4), співпадає з задачею (1.3.3), а двоїста до (1.3.2) співпадає з (1.3.1). Тому пряму та двоїсту задачі називають також взаємодвоїстими, а задачі (1.3.1) і (1.3.2) називаються симетричними. Взаємодвоїсті задачі (1.3.3) і (1.3.4) називаються несиметричними, оскільки в прямій задачі система обмежень задана рівняннями, у двоїстій – нерівностями; у прямій задачі всі змінні не-від’ємні, у двоїстій – можуть бути й від’ємними.

Побудуємо приклад взаємодвоїстих задач. Як пряму розглядаємо задачу виробничого планування. Нагадаємо її зміст. Підприємство має m видів ресурсів і випускає n видів продукції. На виробництво одиниці j-тої продукції витрачається а_ij одиниць і-того ресурсу. Запас і-того ресурсу складає b_і одиниць, і = 1…m, дохід від реалізації одиниці j-тої продукції дорівнює С_j одиниць, j = 1…n. Необхідно знайти план випуску продукції, при якому сумарна вартість її максимальна. У цих позначеннях отримуємо математичну постановку вихідної задачі у вигляді моделі (1.3.1).

Економічну інтерпретацію двоїстої задачі (1.3.2) можна подати так. Нехай задані величини b_i, a_ij, i = 1…m, j = 1…n з тим самим змістом, що й у вихідній задачі. І нехай, крім того, уведена ще одна умова: сировину можна спрямувати або на виготовлення продукції, або на продаж іншому підприємству. Питається, яку мінімальну ціну треба встановити за одиницю кожного виду сировини і = 1…m при умові, що дохід від реалізації всіх її запасів повинен бути не меншим від реалізації всієї продукції, яка може бути вироблена з цієї сировини.

Позначимо через у_і  0 шукану ціну сировини і-того виду. Дохід, який можна було б отримати від реалізації сировини, необхідної для виробництва одиниці продукції виду j, дорівнює , а дохід від реалізації всіх запасів сировини складе величину .

Для того, щоби продаж сировини був не менш вигідним, ніж реалізація виготовленої з неї продукції, має виконуватися нерівність

. (1.3.5)

Будь-яка система цін у_і  0, встановлених із врахуванням умови (1.3.5), задовольняє інтереси підприємства-продавця. Звичайно, що врахування інтересів підприємства-покупця вимагає вибору такої системи цін, яка мінімізує сумарну вартість сировини . В результаті постановка двоїстої задачі набуває вигляду (1.3.2).

Приклад. Для даної задачі

(min) ;

побудувати симетричну задачу.

Помноживши друге обмеження на (–1), отримаємо задачу з однотипними обмеженнями-нерівностями:

(min) ;

.

Таким чином, симетрична задача до отриманої матиме вигляд:

(max) ;

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

Для побудови двоїстої задачі слід перевірити, чи виконуються для вихідної задачі такі умови:

а) в усіх обмеженнях вільні члени містяться у правій частині виразу, а доданки з невідомими – у лівій;

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

в) загальний член нерівності системи обмежень пов’язується з оптимізацією форми таким чином:

«  »  (min);

«  »  (max).

Будуючи систему обмежень двоїстої задачі, потрібно виконувати такі правила:

1. Кожному обмеженню вихідної задачі відповідає невідома двоїстої задачі, причому двоїста невідома, що відповідає обмеженню-нерівності, має бути не-від’ємною, а обмеженню-рівності – може мати будь-який знак.

2. Кожній невідомій вихідної задачі відповідає обмеження двоїстої задачі: коефіцієнти при невідомих вихідної задачі перемножують на відповідні змінні двоїстої задачі, записуючи суму добутків у лівій частині обмеження, а у правій частині – відповідні коефіцієнт цільової функції прямої задачі.

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

Теореми двоїстості. Вивчимо зв’язки між прямою та двоїстою задачами. Для визначеності будемо формулювати основні твердження стосовно симетричної пари двоїстих задач (1.3.1)-(1.3.2), записаних у векторній формі.

Визначимо множини

(1.3.6)

Лема 1. Для будь-яких допустимих планів , прямої та двоїстої задач справедлива нерівність

. (1.3.7)

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

Лема 2. Якщо для деяких допустимих планів , пари двоїстих задач виконується рівність

, (1.3.8)

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

Ця лема формулює критерій оптимальності для задач лінійного програмування. Згідно леми, якщо серед допустимих розв’язків знайдуться вектори і , що задовольняють умову (1.3.8), то вони будуть оптимальними розв’язками відповідних задач.

І теорема двоїстості (теорема існування).

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

ІІ теорема двоїстості (теорема про рівновагу, теорема про доповнюючу нежорсткість).

Допустимі розв’язки двоїстих задач , оптимальні тоді й тільки тоді, коли виконуються умови:

1. ;

2. .

Сформульовані умови називаються умовами доповнюючої нежорсткості.

Дамо їм економічну інтерпретацію. Згідно першої умови, якщо деякий продукт j входить в оптимальний план виробництва (x_j > 0), то при оптимальній системі цін двоїстої задачі витрати ресурсів на його виготовлення співпадають з вартістю цього продукту.

За другої умови, якщо в оптимальній системі цін який-небудь ресурс j отримує відмінну від нуля ціну y_j > 0, то, згідно оптимального плану виробництва вихідної задачі, цей ресурс буде витрачений повністю.

Звертаючись до системи обмежень прямої (1.3.1) і двоїстої (1.3.2) задач, можна доповнити інтерпретацію обох умов доповнюючої нежорсткості так. З обмежень (1.3.2) і першої умови отримуємо: якщо витрати ресурсів на випуск якого-небудь продукту j перевищують його вартість, то цей продукт не виробляється (x_j = 0). З іншого боку, обмеження (1.3.1) і друга умова вказують: якщо який-небудь ресурс і витрачається не повністю, то його ціна y_j = 0.

Отже, кожному ресурсові можна присвоїти оцінку, що є характеристикою його дефіцитності. Ресурси, що використовують у виробництві, не є рівнозначними. Ті з них, які при оптимальному плані виробництва використовуються не повністю, отримують нульову оцінку. Збільшення чи зменшення запасів таких ресурсів не відбивається на величині цільової функції, і, отже, не впливає на показник якості виробничого плану. Якщо ж оцінка і-того ресурсу y_j > 0, то збільшення його використання на одиницю означає покращення показника якості роботи (значення цільової функції) на y_j одиниць.

Наведемо деякі наслідки з теорем існування та рівноваги.

Наслідок 1. Якщо одна з взаємодвоїстих задач має оптимальний розв’язок, то його має й інша задача.

Наслідок 2. Якщо одна з двоїстих задач допустима, в інша недопустима, то цільова функція першої задачі необмежена.

Тісний зв’язок, який існує між взаємодвоїстими задачами, проявляється і в тому, що при розв’язуванні однієї з них одночасно розв’язується й інша. Неважко помітити, що симплекс-таблиця з умовами вихідної задачі містить також умови двоїстої задачі. Рядки цієї таблиці містять ліві частини обмежень вихідної задачі, стовпчики – ліві частини обмежень двоїстої задачі. Елементи стовпчика є коефіцієнтами вектора обмежень прямої задачі й одночасно оцінками плану двоїстої задачі. Елементи нульового рядка задають оцінки плану вихідної задачі й одночасно коефіцієнти вектора обмежень двоїстої задачі. Тому при розв’язуванні двоїстої задачі можна не будувати спеціальну симплекс-таблицю, а розв’язувати її за таблицею, де записані умови вихідної задачі. Оптимальні розв’язки обох задач відшукуються одночасно. Компоненти оптимального плану двоїстої задачі знаходяться в клітинках оціночного (нульового) рядка, що відповідає початковому одиничному базису прямої задачі.

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

Вводячи в систему нерівностей прямої задачі додаткові змінні х₄, х₅  0, отримаємо задачу з одиничним базисом:

(max) ;

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

Базисні змінні	Вільні члени	х1	х2	х3	х4	х5
х4 х5	1 2	2 1	-2 7	2 3	1 0	0 1
Z1	0	-3	1	-6	0	0
х3 х5	½ ½	1 -2	-1 10	1 0	½ -3/2	0 1
Z1	3	3	-5	0	3	0
х3 х2	11/20 1/20	4/5 -1/5	0 1	1 0	7/20 -3/20	1/10 1/10
Z1	13/4	2	0	0	9/4	½

Застосування теорем двоїстості до моделі Леонтьєва. У 20-30-х роках ХХ століття американський економіст Василь Леонтьєв поклав початок систематизованому дослідженню структури економіки в її розукрупненому вигляді. Основними припущеннями моделі, яку в подальшому почали називати моделлю Леонтьєва (і за яку, до речі, автор у 1973 році отримав Нобелівську премію!), були такі:

1. У економічній системі виробляється, купується, споживається та інвестується n видів продукції.

2. Кожна галузь виробляє лише один вид продукції. Спільне виробництво різних товарів виключається.

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

У моделі Леонтьєва такий характер перетворень можна описати так: якщо для виробництва одиниці продукції в j-тій галузі треба витратити a_ij одиниць і-тої продукції, то випуск  одиниць j-тої продукції потребує витрат a_ij одиниць і-тої продукції. Ці n величин a_ij називають витратними (або технологічними) коефіцієнтами. Припускається, що вони сталі. За економічною термінологією, у моделі зберігається сталість питомого випуску при сталих пропорціях витрат (незалежно від масштабів виробництва).

Якщо через Х_і позначити загальний обсяг продукції, випущеної за одиницю часу і-тою галуззю, а через Y_i – кінцеву продукцію, то

, (1.3.9)

де – продукція, спожита як виробничі витрати в усій економічній системі.

Система рівнянь

(1.3.10)

називається моделлю Леонтьєва «витрати-випуск».

З економічної точки зору наявність розв’язку системи рівнянь (1.3.10) означає, що модель Леонтьєва є продуктивною.

У багатьох літературних джерелах модель Леонтьєва пов’язують з матричною моделлю міжгалузевого балансу. Наведемо її постановку й основні математичні співвідношення.

Через Х_і, як і раніше, позначимо загальний обсяг продукції, випущеної галуззю під номером і, через Y_i – його частину, що була спожита у невиробничій сфері (створення запасів, інвестицій, експорту та ін.). Числа x_ij показують розподіл продукції і-тої галузі на виробничі потреби j-тої галузі.

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

Балансовий характер моделі полягає у тому, що виконуються співвідношення:

, (1.3.11)

що виражають характер розподілу виробленої продукції, та

, (1.3.12)

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

Розглянемо числа a_ij, які визначаються формулою

(1.3.13)

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

. (1.3.14)

Виходячи з формули (1.3.13), співвідношення (1.3.11) можна записати через модель Леонтьєва. При векторах валового випуску та товарної продукції цей вираз матиме вигляд

(1.3.15)

або

, (1.3.16)

де Е – одинична матриця.

Якщо через (Е – а)­^-1 позначити обернену матрицю до матриці (Е – а), то формально розв’язок системи рівнянь (1.3.16) можна записати у вигляді

, (1.3.17)

де А = (Е – а)­^-1, або в розгорнутій формі

. (1.3.18)

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

Число , яке задовольняє рівняння

, (1.3.19)

називають власним числом матриці А.

Теорема. Модель Леонтьєва продуктивна тоді й лише тоді, коли виконується співвідношення .

На практиці замість цієї теореми використовують просту достатню умову продуктивності моделі Леонтьєва, а саме: модель Леонтьєва продуктивна, якщо сума елементів матриці А по всіх рядках та стовпцях не перевищує 1.

Модель Леонтьєва стає змістовнішою, якщо в неї включити питання про використання трудових ресурсів. Позначимо через ℓ_j витрати праці в j-тій галузі на випуск одиниці продукції. Якщо через L_j позначити витрати праці в галузі j, то

. (1.3.20)

При дослідженні статичного варіанта моделі Леонтьєва, яка не враховує попередні стани виробництва і, зокрема, обмеженість матеріальних ресурсів, природно припустити, що одним із факторів обмеження є загальний обсяг трудових ресурсів системи L, тобто

. (1.3.21)

У цьому випадку модель Леонтьєва розширюється і набирає вигляду

(1.3.22)

Задачу (1.3.22) можна інтерпретувати як задачу лінійного програмування. Для цього вважають, що права частина першої системи рівнянь задає не саму кінцеву продукцію, а її структуру (наприклад, у вигляді пропорції). Тому, позначивши її праву частину через С і вважаючи, що , розглянемо таку задачу:

(max) ; (1.3.23)

(1.3.24)

де  можна інтерпретувати як кількість комплектів С. Економічним змістом задачі (1.3.23)-(1.3.24) є раціональний розподіл трудових ресурсів.

Якщо до записаної задачі побудувати двоїсту, то вона матиме вигляд:

(min) L; (1.3.25)

(1.3.26)

де р і  – двоїсті невідомі (р – n-вимірний вектор,  – число, яке можна інтерпретувати як об’єктивно зумовлені оцінки вектора С і загальної кількості трудових ресурсів L), р^* – вектор, транспонований до вектора р.

Вектор р можна трактувати як вектор ціни відповідної продукції, а  – заробітну плату, що припадає на одиницю трудових ресурсів. Тоді, згідно зі співвідношеннями між оптимальними розв’язками,

max  = min L. (1.3.27)

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