В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 75

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

J -Xl + x2 - x2/ - 2x3 + 2x3/ + x4 = 4,

\ 2Xl + x2 - x2/ + 4x3 - 4x3 = В;

Xl > 0, x2 > 0, x2/ > 0, x3 > 0, x3/ > 0, x4 > 0;

2) f = -f = 4xl - 3(x2 - x2/) - БX3 max; Г 3xl + 2(x2 - x2/) + 3X3 = -Т, <   2xi - (x2 - x2/) - 2X3 - X4 = Б, [ 2xi + 3(x2 - x2/) + X3 + X5 = В; xl > 0, x2 > 0, x2/ > 0, X3 > 0, x4 > 0,x5 > 0;

2. І) f = 3xl + 2x3 max; 2) f = -2xl - 2x5 - 4 max; Г Xl - X3 < 4, Г Xl + Бx5 < ІІ,

[ xl + X3 < Xl > 0, X3 > 0;

Xl > 0, X5 > 0.

231

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

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

Тому спочатку розглянемо деякі додаткові поняття й озна­чення лінійної алгебри.

2.1. Опуклі множини. Множина П С Кга називається опуклою, якщо вона разом з двома своїми довільними точ­ками Х\ Є П, Х2 Є П містить всі точки вигляду

X = ХХг + (1 - \)Х2,   0 < А < 1.

(1)

Тут і надалі під аХ, а Є К, розумітимемо добуток вектора на число.

Очевидно, що коли А пробігає значення від 0 до 1, то точка X описує відрізок Х2Х1. Точка X, для якої виконується умова (1), називається опуклою лінійною комбшацією точок Х2 і Хі. Точки Хі і Х2 називаються кутовими або крайніми точками відрізка Х1Х2.

По-іншому можна сказати, що множи­на П називається опуклою, якщо вона разом зі своїми двома довільними точ­ками Хі і Х2 містить відрізок, який їх

з'єднує.

Прикладами опуклих множин є прямолінійний відрізок, пряма, півплощина, круг, куля, куб, півпростір і т.д.

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

Неопуклі множини

Доводиться, що переріз довільної кількості опуклих мно­жин є опуклою множиною.

232

Точка X називається опуклою лінійною комбінацією

точок Хі, Х2, ..., Хп, якщо виконується умова

X = аіХі + «2X2 + ... + апХп,

де

п

аі > 0,   і є {1,... ,п},^2/аг = 1.

і=1

У відповідності з означенням опуклої множини вона мі­стить опуклу лінійну комбінацію будь-яких своїх точок.

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

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

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

Опорною прямою опуклого многокутника називається пря­ма, яка має з многокутником, розміщеним по один бік від неї, принаймні одну спільну точку. Прямі МХ і РС; є опорними до многокутника АВСБЕ.

2.2. Властивості розв'язків задачі лінійного програ­мування. Розглянемо канонічну задачу, записану в матрично-векторній формі

/ = СХ -»■ тах; (2) Ж1А1 + Ж2А2 + ... + ХпАп = Ао; (3)

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


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

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія