Короткі теоретичні відомості

Відведений час: 4 год.

Теорія двоїстості та двоїсті оцінки

Мета: формувати у студентів уміння будувати двоїсті задачі.

Завдання для практичного заняття:

1. Пригадайте основні теоретичні питання теми.

2. Орієнтовні запитання та завдання:

- сформулюйте правила побудови двоїстих задач;

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

3. Виконайте індивідуальне завдання.

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

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

Знайти максимум функції при обмеженнях

Знайти мінімум функції при обмеженнях

Ці задачі мають наступні властивості:

1^о. В одній задачі знаходиться максимум функції, а в іншій – мінімум.

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

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

4^о. Коефіцієнти біля змінних в системах обмежень описуються матрицями

і ,

які є транспонованими одна по відношенню до іншої.

5^о. Кількість нерівностей в системі обмежень однієї задачі співпадає з кількістю змінних іншої задачі.

6^о. Умова невід’ємності змінних присутня в обох задачах.

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

Наступна таблиця 2.42 значно полегшує процес складання математичної моделі двоїстої задачі.

Таблиця 2.42 – Вихідні дані

	х1	x2	x3	…	xn
y1	а11	a12	a13	…	a1n	b1
y2	а21	a22	a23	…	a2n	b2
y3	а31	a23	a33	…	a3n	b3
…	…	…	…	…	…	…
ym	am1	am2	am3	…	amn	bm
	c1	c2	c3	…	cn

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

Щоб отримати, наприклад, перше обмеження двоїстої задачі, потрібно знайти суму добутку чисел, які стоять в стовпчику під х₁, на відповідні змінні першого стовпчика:

a₁₁ y₁ + a₂₁ y₂ + … + a_m1 y_m.

Вважаємо, що ця сума не менше с₁:

a₁₁ y₁ + a₂₁ y₂ + … + a_m1 y_m с₁.

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

а) змінній х₁ вихідної задачі відповідає перше обмеження двоїстої задачі,

змінній х₂ – друге обмеження двоїстої задачі і т. д., змінній х_n – останнє обмеження двоїстої задачі і навпаки;

б) змінній у₁ двоїстої задачі відповідає перше обмеження вихідної задачі і т. д., змінній у_m двоїстої задачі відповідає останнє обмеження вихідної задачі і навпаки.

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

Якщо система обмежень вихідної задачі на максимум, крім нерівностей типу , містить нерівності типу , то нерівності типу необхідно помножити на -1. А задачі на мінімум нерівності типу множимо на -1.

Наприклад, двоїстою до задачі

L = x₂– 3x₃ + 2x₅ – min;

x_j 0, j=1, 2,…6

є така:

L^* = 7y₁ + 12y₂ + 10y₃ – max

Процес побудови двоїстої задачі зручно зобразити схематично (рисунок 2.9):

Рисунок 2.9 – Схема побудови двоїстої задачі до прямої

Пари задач лінійного програмування бувають симетричні та несиметричні.

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

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

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

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

Дата добавления: 2017-02-01