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

Опуклі множини

Введемо деякі поняття з теорії множин.

Розглянемо точки , . Точка лежить на відрізку , якщо вектори і колінеарні, тобто їх координати пропорційні:

;

або

де , , .

Можна записати: , (1)

, , .

Означення 1. Точка , для якої виконується рівність називається опуклою лінійною комбінацією точок і . Точки і називаються кутовими точками відрізка .

Очевидно, що кутові точки не є лінійними комбінаціями жодних двох точок відрізка.

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

Означення 2. Точка є опуклою лінійною комбінацією точок , -вимірного простору, якщо існують числа , , такі що і .

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

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

Опуклі множини: відрізок, пряма, півплощина, круг, квадрат, куля, піраміда.

Прикладами неопуклих множин є парабола, коло, еліпс, а також:

Твердження 1. Перетин будь-якої кількості опуклих множин є опуклою множиною.

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

Означення 5

1) Множина називається відкритою, якщо вона містить тільки свої внутрішні точки. Якщо множина, крім внутрішніх, містить всі граничні точки, то вона називається замкнутою.

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

Означення 6

1) Опуклим многокутником називається опукла замкнена обмежена множина на площині, яка має скінчене число кутових точок.

2) Кутові точки многокутника називаються його вершинами, а відрізки, що з’єднують дві вершини і утворюють його границю, - сторонами многокутника.

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

На рис.4.1 АВСДЕ – опуклий многокутник; АЕ, СF – опуклі прямі.

 

 

 

Рисунок 4.1

Означення 7

1) Опуклим многогранником називається замкнена обмежена опукла множина - вимірного простору, яка має скінчене число кутових точок.

2) Кутові точки многогранника називаються вершинами; многокутники, що обмежують многогранники – гранями; відрізки, по яких перетинаються грані – ребрами.

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

Твердження 2 Опуклий многокутник (многогранник) є опуклою лінійною комбінацією своїх кутових точок

, , , .

, , .