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

Теорема 2.2. Множина всіх планів задачі лінійного програмування опукла.

Доведення. Необхідно довести, що коли X1 та X2 -- плани задачі лінійного програмування (2.1)--(2.3), то їх опукла комбінація X = Л1X1 + Л2X2, Л1 ? 0, Л2 ? 0, Л1 + Л2 = 1 також є планом задачі.

Так як X1 і X2 -- плани задачі, то виконуються такі співвідношення:

AX1 = A0, X1 ? 0; AX2 = A0, X2 ? 0.

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

AX = A(Л1X1 + Л2X2) = Л1AX1 + Л2AX2 = Л1A0 + Л2A0 = (Л1 + Л2)A0 = A0.

Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки Х1 ? 0, Х2 ? 0, Л1 ? 0, Л2 ? 0, то й Х ? 0, тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х -- план задачі лінійного програмування.

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

багатокутник розв'язків задачі у двовимірному просторі

Рис. 2.3 Багатокутник розв'язків задачі у двовимірному просторі

Доведення. 1) Припустимо, що багатогранник розв'язків задачі Обмежений і має скінченну кількість кутових точок. Позначимо кутові точки через Х1, Х2,..., ХР, А оптимальний план -- Х0

Для значення Х0 Виконується нерівність F(X0) ? F(X). Припустимо, що Х0 не є кутовою точкою.

Отже, її можна подати як опуклу лінійну комбінацію кутових точок множини Q, тобто

X0 = Л1X1 + Л2X2 + ... + ЛPXP,

.

F(X) -- лінійна функція:

(2.16)

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

.

За припущенням Х0 -- оптимальний план, отже, з одного боку, F(X0) ? F(XK) = M, а з другого, доведено, що F(X0) ? M, значить, F(X0) = M = F(XK), де XK -- кутова точка. Отже, лінійна функція досягає максимального значення в кутовій точці (XK).

2) Припустимо, що F(X) набирає максимальних значень більше, ніж в одній кутовій точці,

Наприклад у точках

Х1, Х2,..., ХQ, (1 ? Q ? P),

Тоді F(X1) = F(X2) = ... = F(XQ) = M.

Якщо Х Опукла лінійна комбінація цих кутових точок, то:

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

багатокутник розв'язку задачі у двовимірному просторі з необмеженою областю

Рис. 2.4 Багатокутник розв'язку задачі у двовимірному просторі з необмеженою областю

Зауваження. Якщо багатокутник розв'язків -- Необмежена область (рис. 2.4), то не кожну точку можна подати у вигляді опуклої лінійної комбінації її кутових точок. У такому разі введемо в систему додаткове обмеження

Х1 + Х2 ? L,

Де L -- достатньо велике число. Введення цього обмеження означає відтинання прямою Х1 + Х2 = L від багатокутної необмеженої області обмеженого багатокутника, для якого виконується наведена теорема.

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

Теорема 2.4. Якщо відомо, що система векторів (K ? n) у розкладі, лінійно незалежна і така, що

,

Де всі XJ ? 0, то точка X = (X1, X2, ..., XK, 0, ..., 0) є кутовою точкою багатогранника розв'язків.

Доведення. Припустимо, що точка Х Не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок Х1 та Х2 багатокутника розв'язків, тобто:

Компоненти векторів Х1 та Х2, значення Л1 і Л2 невід'ємні і останні N - k компонентів вектора Х дорівнюють нулю, тому відповідні N - k Компонент векторів Х1 та Х2 також мають дорівнювати нулю, тобто

,

.

Оскільки Х1 та Х2 -- плани, то

,

.

Віднімаючи від першого рівняння друге, отримаємо:

.

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

.

Звідси:

Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв'язків. Значить, Х -- кутова точка.

Теорема 2.5. Якщо -- кутова точка багатогранника розв'язків, то вектори в розкладі, , що відповідають додатним, є лінійно незалежними.

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

.

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

.

За умовою

.

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

,

.

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

.

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

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

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

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

З наведених властивостей можна висновувати:

Якщо функціонал задачі лінійного програмування обмежений на багатограннику розв'язків, то:

Існує така кутова точка багатогранника розв'язків, в якій лінійний функціонал досягає свого оптимального значення;

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

Тому для розв'язання задачі лінійного програмування необхідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.

Похожие статьи




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

Предыдущая | Следующая