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

 

Введемо деякі означення, пов’язані з поняттям опуклості.

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

Відрізком в -мірному евклідовому просторі , що з’єднує точки і назвемо множину всіх точок таких, що , де , — кінці відрізка. Будемо його позначати .

Множина точок , яка задовольняє умові

,

називається півпростором в ,

Множина точок , яка задовольняє умові

,

називається гіперплощиною в .

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

Лема 1.3.1. Перетин опуклих множин — опукла множина (якщо тільки вона непорожня).

Доведення.

Нехай і — опуклі множини і . Тоді і . З означення опуклої множини і . Отже , а це і означає, що — опукла множина.

Теорема 1.3.1. Допустима множина ЗЛП опукла (якщо вона непорожня).

Доведення.

Оскільки допустима множина ЗЛП є перетин множин точок, які задовольняють окремим обмеженням, то згідно з лемою 1.3.1, достатньо довести, що множина точок, які задовольняють окремому обмеженню, опукла.

Окремим обмеженням ЗЛП може бути або гіперплощина, або півпростір.

Нехай — довільні точки такі що і .

Тоді для будь-якої точки ,

,

тобто належить гіперплощині.

Аналогічно для півпростору. Нехай і ,

. Тоді і

,

тобто і . Теорему доведено.

Теорема 1.3.2. Множина оптимальних точок допустимої множини ЗЛП опукла (якщо вона непорожня).

Доведення.

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

Нехай оптимальних точок більше ніж одна. Візьмемо дві з них, і .

Нехай і — оптимальне значення цільової функції.

Розглянемо будь-яку точку : . Очевидно, що .

Тоді

.

Отже, — також оптимальна точка. Цим і доводиться опуклість множини оптимальних точок ЗЛП.

З теореми 1.3.2 випливає, що множина оптимальних точок не може бути скінченною, якщо оптимальна точка не єдина.

Теорема 1.3.3. Якщо цільова функція ЗЛП на максимум (мінімум) обмежена зверху (знизу) на допустимій множині, то ця задача має оптимальний розв’язок.

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

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

Тобто — вершина многогранника , якщо не існує точок таких що , і , де .

Лема 1.3.2. Будь-яка точка опуклого обмеженого многогранника є опуклою лінійною комбінацією його вершин.

Тобто, якщо — вершини многогранника , то будь-яку точку можна подати у вигляді:

.

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

Доведення.

Нехай — вершини допустимого многогранника і нехай задача максимізації за умови розв’язувана.

Припустимо, що . Тоді

.

(1.3.1)

 

Нехай не є вершиною , то в силу леми 1.3.2

.

Далі

,

де .

З (1.3.1) випливає, що , а це і означає, що існує вершина , у якій цільова функція набуває найбільшого значення.

Теорему доведено.

Розглянута властивість дає важливу ідею розв’язування ЗЛП — перебір вершин її допустимої множини. Але такий шлях розв’язування ЗЛП, навіть з відносно невеликим числом обмежень і невідомих, практично нездійсненний, оскільки процес відшукування вершин досить трудомісткий, а число вершин многогранника може бути досить великим.

Тому на початку 50-х років було винайдено американським математиком Дж.Данцигом досить раціональний спосіб перебору вершин: симплекс-метод або метод послідовного поліпшення плану для розв’язування задач лінійного програмування [14].

Нехай розглядається задача з непорожньою допустимою множиною. Загальна ідея симплекс-методу:

1) тим чи іншим способом знаходиться одна з вершин допустимої області і по певному правилу перевіряється, чи є вона оптимальною точкою; якщо вона оптимальна — задача розв’язана; якщо ні, то

2) по певному правилу перевіряється, чи не можна стверджувати, що задача не має оптимальних розв’язків (цільова функція необмежена зверху або, відповідно, знизу на допустимій множині); якщо стверджувати це можна, то задача нерозв’язувана; якщо не можна, то

3) по певному правилу шукаємо нову, ліпшу з точки зору значення цільової функції вершину і повертаємося на 1-й крок.

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

Симплекс-метод