ТЕОРЕТИЧНІ ОСНОВИ МЕТОДІВ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Для розгляду теоретичних основ методів лінійного програмування доцільно знову повернутися до поняття опуклого безлічі точок, давши йому більш суворе визначення в аналітичній формі.

Опуклі безлічі в n-вимірному просторі

У параграфі 2.2 опукле безліч точок визначалося як безліч, яке разом з будь-якими своїми двома точками містить весь відрізок, їх з'єднує. Однак в разі п змінних не ясно, що слід розуміти під "відрізком" в n -мірному просторі. Очевидно, треба дати аналітичне визначення цього поняття.

Почнемо з п = 2 (двовимірного простору, площини). Нехай і | - точки площини , а "будь-яка точка відрізка (рис. 3.1).

Мал. 3.1

Очевидно, що відношення а довжин відрізків ХХ 2 і Х х Х 2 задовольняє умові 0 <а <1. Запишемо це відношення а через координати точок. отримаємо

звідки

(3.1) де

(3.2)

Вважаючи оц = а і α2 = 1-α, умови (3.1), (3.2) приймуть вид

(3.3)

(3.4)

Рівність (3.3) можна записати у вигляді

(3.5)

розуміючи, що в ньому всі операції виконуються покоординатно (тобто окремо по змінної ДГ, і окремо по змінної х 2 ).

Таким чином, відрізок Х х Х 2 можна визначити як безліч точок (векторів), які відповідають умовам (3.5) і (3.4).

У разі "мірного простору визначення відрізка буде таким же - безліч точок, які відповідають умовам (3.5) і (3.4), якщо під ХX., мати на увазі точки (вектори) n-мірного простору: і

Узагальненням поняття відрізка для декількох точок є їх опукла лінійна комбінація.

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

Так, наприклад, вираз (1/6) ¾ + (1/2) Х 2 + (l / 3) X : i є опукла лінійна комбінація точок Х х , Х 2 , Х у а вираження (1/3) ¾ + (1/2) ¾ + (1/3) ¾ або (1/3) ¾ - (1/2) ¾ + (7/6) ¾ є лінійними, але нс опуклими комбінаціями тих же точок (в нервом , а у другому ).

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

Розглянемо теорему про подання опуклого багатогранника.

Теорема 3.1. опуклий п-мірний багатогранник є опуклою лінійною комбінацією своїх кутових точок.

Візьмемо для простоти п = 2, а в якості багатогранника - трикутник ^, ¾¾ (рис. 3.2). Через довільну точку X трикутника проведемо відрізок X l X i. Оскільки точка X лежить на цьому відрізку, то

де

Точка Х Л лежить на відрізку Х 2 Х 3, отже, Х А = а 2 Х 2 + а3Х3, де А2> О, а3> О, а 2 + а3 = 1.

Підставивши значення Х 4 в вираз для X, отримаємо

Мал. 3.2

Позначивши , одержимо остаточно

де

Таким чином, точка X є опукла лінійна комбінація кутових точок (вершин) трикутника Х х Х. 2 Х n. ■

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

 
< Попер   ЗМІСТ   Наст >