Основні властивості розв’язків задачі лінійного програмування

Вла 535i85f 89;тивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем (доведення теорем та їх наслідки наведено нижче).

Вла 535i85f 89;тивість 1

Вла 535i85f 89;тивість 2 розв’яз­ків. Якщо ж цільова функція набуває екстремального значення

Вла 535i85f 89;тивість 3 A A A_k (k ≤ n) у розкла 535i85f 76;і A x A x A_nx_n A X

A x A x A_kx_k A

x_j X x x x_k

Вла 535i85f 89;тивість 4. (Теорема 2.5) Якщо X = (x₁, x₂, …, x_n) — кутова точка багатогранника розв’язків, то вектори в розкла 535i85f 76;і A₁x₁ + + A₂x₂ + … + A_nx_n = A₀, X ≥ 0, що відповідають додатним x_j, є лінійно незалежними.

. Необхідно довести, що коли X₁ та X₂ — плани задачі лінійного програмування (2.1)—(2.3), то їх опукла комбінація X = λ₁X₁ + λ₂X₂, λ₁ ≥ 0, λ₂ ≥ 0, λ₁ + λ₂ = 1 також є планом задачі.

Так як X₁ і X₂ — плани задачі, то виконуються такі співвідношення:

AX A X AX A X

Якщо підставити в систему обмежень значення X, то отримаємо:

AX = A( X + λ₂X₂) = λ₁AX₁ + λ₂AX₂ = λ₁A₀ + λ₂A₀ = (λ₁ + λ₂)A₀ = A₀.

Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки Х₁ ≥ 0, Х₂ ≥ 0, λ₁ ≥ 0, λ₂ ≥ 0, то й Х ≥ 0, тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х — план задачі лінійного програмування.

. Припустимо, що багатогранник розв’язків задачі обмежений і має скінченну кількість кутових точок. Позначимо його через Q. У двовимірному просторі Q має вид багатокутника, що зображено на рис. 2.3. Позначимо кутові точки через Х₁, Х₂, , Х_р, а оптимальний план — Х₀.

Задача (2.1) — (2.3) розв’язується на максимум, отже, при будь-якому Х із Q для значення Х₀ виконується нерівність F X F X . Якщо Х₀ — кутова точка, то перша частина теореми доведена. Припустимо, що Х₀ не є кутовою точкою, тоді Х₀ є точкою, яка належить опуклій множині (доведено в попередній теоремі). Отже, її можна подати як опуклу лінійну комбінацію кутових точок множини Q, тобто

X = λ₁X₁ + λ₂X₂ + … + λ_pX_p,

.

У зв’язку з тим, що F(X) — лінійна функція, отримаємо:

(2.16)

У такому розкла 535i85f 76;і серед значень F X_i вибираємо найбільше (припустимо, що воно відповідає кутовій точці і позначимо його через m, тобто . Замінимо в (2.16) кожне значення F X_i цим найбільшим значенням. Оскільки , то

.

F X F X_k m, а з другого, доведено, що F(X₀) ≤ m, значить, F(X₀) = m = F(X_k), де X_k — кутова точка. Отже, лінійна функція досягає максимального значення в кутовій точці (X_k).

F X набирає максимальних значень більше, ніж в одній кутовій точці, наприкла 535i85f 76; у точках Х₁, Х₂, , Х_q, (1 ≤ q p , тоді F(X₁) = F(X₂) = … = F(X_q) = m. Якщо Х опукла лінійна комбінація цих кутових точок, то:

тобто лінійна функція F набирає максимальних значень у довільній точці Х, яка є опуклою лінійною комбінацією кутових точок Х₁, Х₂, , Х_q.

L, де L — достатньо велике число. Введення цього обмеження означає L

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

Компоненти векторів Х₁ та Х₂, значення λ₁ і λ₂ невід’ємні і останні n – k компонентів вектора Х дорівнюють нулю, тому відповідні n – k компонент векторів Х₁ та Х₂ також мають дорівнювати нулю, тобто

,

.

,

.

.

За припущенням вектори лінійно незалежні, тому останнє співвідношення виконується, якщо

.

Звідси:

. Не порушуючи загальності, можна вважати нерівними нулю перші k елементів вектора Х, отже,

.

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

.

.

Задамо деяке число , помножимо на нього першу рівність, далі результат спочатку додамо до другого, а потім віднімемо від другого рівняння:

,

.

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

.

> 0, тому число можна вибрати настільки малим, що всі перші компоненти та набуватимуть додатних значень, тоді та — плани. При цьому , тобто Х — опукла лінійна комбінація точок Х₁ та Х₂, що суперечить умові теореми, оскільки Х — кутова точка.

Припущення стосовно лінійної залежності векторів привело до суперечності. Отже, воно є неправильним, а система векторів — лінійно незалежна.

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

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