Вектор можна уявити у вигляді опуклої лінійної комбінації

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

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

Нехай x⁰ = (x⁰₁, x⁰₂, …, x⁰_n) – довільний допустимий розв’язок. Позначимо через N+ множину індексів додатніх координат вектору x⁰. Якщо стовпці матриці A з номерами, що належать N+, лінійно незалежні, то x⁰ – опорний план, і твердження теореми виконується. Тому розглянемо випадок, коли вказані стовпці лінійно залежні, і виконується рівняння

l_j a^j = 0,

j N+

у якому не усі коефіцієнти дорівнюють нулю.

Як і при доведенні попередньої теореми, побудуємо вектор l^’ = (l^’₁, l^’₂, …, l^’_n) таким чином

l^’_j = l_j, якщо j N+; l^’_j = 0, якщо j N+.

l^’_j a^j = 0, або Al^’ = 0.

Серед ненульових координат вектору l^’ є як додатні, так і від’ємні, бо інакше, наприклад, при відсутності від’ємних, вектор x⁰ + tl^’ при будь-якому значенні t ³. 0 належить допустимій області. А це суперечить обмеженості допустимої області, оскільки | x⁰ + tl^’ | може приймати як завгодно великі значення при досить великому t.

Визначимо два числа p ₁ і p ₂ таким чином

p₁ = min { x⁰ _j / (-l^’_j ) | l^’_j < 0 }; p₂ = min { x⁰ _j / l^’_j | l^’_j > 0 }.

j j

Тоді вектори x⁺ = x⁰ + p₁l^’ і x^- = x⁰ - p₂l^’ належать допустимій області, що можна показати, як при доведенні теореми 5.2 для векторів x¹ і x².

x⁰ = p₂ / (p₁ + p₂) x⁺ + p₁ / (p₁ + p₂) x^-,

де кожний з векторів x⁺ і x^- має меншу кількість ненульових координат, ніж x⁰. Зменшення кількості ненульових координат зумовлено тим, що для значень індексів, при яких відношення { x⁰ _j / (-l^’_j ) і x⁰ _j / l^’_j мають мінімальні значення, координати векторів x⁺ і x⁰ відповідно дорівнюють нулю.

Дата добавления: 2014-01-13