Материал: Економетрія - Навчальний посібник ( Лугінін О.Є.)


2.2. основні поняття геометрії випуклих множин

 

2.2.1. Випуклі множини та їх геометрична інтерпретація на площині та в просторі

 

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

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

Множини бувають випуклими та невипуклими. Випуклою є множина, де разом з її будь-якими двома точками їй належить і увесь відрізок, що з'єднує ці точки (рис. 2.1., а). У невипуклих множин існує хоча б одна пара точок, що відрізок, який з'єднує ці точки, не належить цілком даній множині (рис.2.1., б).

 

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

 

мають важливу властивість: пересікання скінченого числа випуклих множин теж є випуклою множиною. Це і зумовило широке використання випуклих      множин у

практичних задачах.

 

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

Для випуклого многокутника на площині кутовими точками є його вершини і число їх скінченне. У п-мірному просторі випукла множина з скінченним числом кутових точок називається випуклим многогранником, або сімплексом, (у подальшому розгляді він є об'єктом геометричної інтерпретації сімплекс-метода задач ЛП). У відповідності з цими визначеннями до випуклого многокутника відносяться точка, луч, кут (мають по одній кутовій точці), відрізок (має дві кутові точки), трикутник, ромб, трапеція тощо. У трьохмірному просторі випуклими многогранниками є піраміда, призма, паралелепіпед тощо. Поняття кутовій точки вводиться тільки до випуклих множин.

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

 

2.2.2. Системи лінійних нерівностей та знаходження області допустимих рішень

Спочатку розглянемо систему з т лінійних нерівностей, які мають дві змінні (п=2) х1 та х2:

 

аі1х1 + аі2х2 < Ьі, і — 1...т,

(3.1)

 

де аі1, аі2 відомі коефіцієнті при змінних, які задаються у вигляді дійсних чисел; Ьі праві частини.

При двох змінних область допустимих рішень системи нерівностей (2.18) може бути зображена на площині в осях координат х1 та х2 у вигляді замкненого або незамкненого випуклого многокутника. При відсутності рішень такий многокутник пустий. Кожна з сторін многокутника графічно відображає пряму аі1х1 + аі2х2 Ьі — 0, яка розділяє площину

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

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

рішень на площині системи т лінійних нерівностей з числом змінних п=2.

Приклад 2.5. Побудувати множину      рішень системи лінійних нерівностей та знайти координати     кутових точок випуклого многокутника: х1 + х2 3 < 0; х1 + х2 -1 > 0; < х1 + х2     > 0; х1        < 2,5;

0 < х2 < 1.

Введемо на площині

прямокутну систему координат х10х2 (рис. 2.3). Відомо, що геометричне місце точок на площині, координати яких задовольняють системі лінійних нерівностей, утворює випуклий многокутник. Цей многокутник є многокутником рішень однієї системи нерівностей. Сторони цього многокутника розташовуються на прямих, рівняння яких одержуються, якщо в нерівностях системи їх знаки поміняти на знаки рівнянь. А сам многокутник є перетин полуплощин, на які розділяється площина кожною з вказаних прямих.

 

 

х2

к

•*

 

2

Ж А

 

1

Є

Д

І

Б

N .

 

1 2

 

Рисунок 2.3 Многокутник рішень системи нерівностей

1. Будуємо пряму АБ х1+х2-3=0: при х1=0х2=3; при х2=0 х1=3. Вона проходить через точки (0;3) та (3;0) в осях координат х1 та х2. Для знаходження області рішень, яке дає перша нерівность, використуємо контрольну точку, наприклад, начало координат (0;0). Підстановка координат начала в строгу нерівність х1+х2-3<0 дає-3<0, тобто вона виконується. Таким чином, з двох полуплощин, на які розділяє

 

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

Будуємо пряму ЄД х1+х2-1=0: при х1=0 х2=3; при х2=0 х1=3. Вона проходить через точки (0;1) та (1;0) в осях координат. Підстановка координат начала в строгу нерівність х1+х2-1>0 показує її невиконання: -1< 0. Тобто, з двох полуплощин, на які розділяються площина прямою ЄД, множиною рішень другої нерівності буде верхня полуплощина, що показується напрямком стрілок на прямої.

Будуємо пряму ЄЖ х1-х2=0. Так як вона проходить через начало координат, другу точку знайдемо, приймая, наприклад, х1=2, тоді х2=2. Пряма ЄЖ пройде через точки з координатами (0;0) та (2;2). Для знаходження полуплощин рішень строгої нерівності х1+х2>0 візьмемо контрольну точку з однієї сторони від прямої, так як координати начала в рівнянні з попередніми випадками не дозволяє досягнути поставленої цілі. За контрольну, наприклад, візьмемо точку з координатами (0;2). Підстановка її координат у строгу нерівність дає -2>0, тобто вона не виконується. Це означає, що полуплощина множини рішень для третьої нерівності даної системи лежить нижче прямої ЄЖ, де знаходиться контрольна точка.

Будуємо пряму СБ х1=2,5. Вона проходить через точку з координатами х1=2,5 паралельно осі х2. Значення х1 лежать зліва від знайденої прямої, що і визначає полуплощину рішень нерівності х1 < 2,5.

Двійчаста нерівність 0 < х2 < 1 відповідає системі двох нерівностей: х2<1; х2>0. Нерівності х2<1 відповідає полуплощина нижче прямої АЖ х2=1, а нерівності х2>0 полуплощина вище осі х1.

Таким чином, множині рішень системи з п'яти заданих нерівностей відповідає випуклий многокутник АБСДЄЖ область штрихування в якому відповідає області рішень системи нерівностей.

Знайдемо координати кутових точок многокутника як точки пересікання відповідних прямих.

Із рисунка очевидні координати точок Д(1;0) і С(2,5;0). Координати інших кутових точок знаходяться з рішень системи рівнянь прямих, на пересіканні яких знаходяться ці точки.

Точка Є лежить на пересіканні прямих ЄД та ЄЖ. Вирішуя спільно рівняння цих прямих х1 +х2=1 та х1-^2=0, знаходимо х1 =х2=0,5, тобто координати т. Є(0,5;0,5).

Точка Ж лежить на пересіканні прямих ЄЖ та АЖ. Вирішуя спільно рівняння цих прямих хгл2=0, та х1 =1 знаходимо х1 =х2=1, тобто координати т. Ж(1;1).

Точка А лежить на пересіканні прямих АЖ та АБ. Вирішуя спільно рівняння цих прямих х2=1 та х1+х2=3, знаходимо х1 =2, х2=1, тобто координати т. А(2;1).

Точка Б лежить на пересіканні прямих АБ та БС. Вирішуя спільно рівняння цих прямих х1 +х2=3 та х1=2,5, знаходимо  х1  =2,5,  х2=0,5.   Таким  чином,  координати т.

Б(2,5;0,5).

У загальному випадку для системи т лінійних рівнянь з п змінними

аиХ1 + ааХ2 +... + ОіпХп < Ьі, і = 1...т,

область допустимих рішень даної системи може відповідати випуклому многограннику (сімплексу), який побудований у п-мірному просторі. Кожна грань розглядаємого сімплексу геометрично відображує площину, яка відповідає і-му рівнянню з системи (2.19). Кожна з таких площин відокремлює у п-мірному просторі полупростір, який складається з точок Х(хі, х2, ... хп), розміщених за однією з сторін від площини аі1х1 + аі2х2 +... + аіпхп Ьі = 0 та на самій площині. Тоді

сімплекс, побудований у п-мірному просторі як пересікання випуклих множин у вигляді окремих площин, відповідає у загальному випадку області допустимих рішень системи лінійних нерівностей (2.19).

 

Запитання для самоконтролю

Що вивчає геометрія випуклих множин?

Яка множина є точковою?

Навести приклади точкових множин на площині та в просторі.

Які множини є випуклими? невипуклими? Навести приклади.

Яка властивість випуклих множин зумовила їх широке використання в практичних задачах?

Які точки випуклих множин називаються кутовими?

Яка випукла множина називається сімплексом?

Навести приклади випуклих множин на полощині.

Що графічно відображає пряма многокутника допустимих рішень на полощині?

 

Як знаходиться область допустимих рішень для однієї з нерівностей при двох змінних?

Як знаходиться область допустимих рішень для системи нерівностей з двох змінних?

Як знайти координати кутових точок у випуклого многокутника на площині?

Що відображає кожна грань випуклого многокутника допустимих рішень?

2.2.14. Що відображає побудований многокутник у п-мірному просторі?

 

Вправи

Побудувати    множину рішень нерівностей та знайти координати кутових допустимих рішень:

2.2.1.

2.2.2.

х1 + 2х2 8 > 0; х1 - 2х2       < 0; 3х1 + 2х2 32 > 0;

2.2.4.

х2    < 0.

2.2.5.

2.2.6.

0 < х2 < 3. 4х1 + 3х2 < 24; 4х1 х2 < 0;

х1 6х2 < -6;

х1        < 3.

4х1 х2 + 8 > 0;

2.2.7.

2.2.8.

х1 + х2 4 > 0;

х1 + 3х2 6 > 0;

х1        < 0;

х2       > 0.

 

системи лінійних точок многокутника

х1 + х2 < 6; 2х1 х2 < 4;

х1      < 3;

х2 < 4;

х1 + 2х2 > 4. 2х1 х2 + 4 > 0;

х1 + х2 3 > 0;

х1 + х2 7 < 0;

х1        < 6;

х2      > 0. 5х1 3х2 + 15 > 0; 0 < х2 < 2;

х1 + х2 -17 < 0;

0 < х1 < 11.

5х1 2х2 10 < 0; 3х1 + 2х2 -10 > 0;

х1 + 2х2 6 > 0;

х1        < 0.

 

 

 

 

 

2.2.9.

 

2.2.11.

2х1 +   х2 2 > 0; 3х1 4х2 +12 > 0; х1        > 0;

х2      > 0. 3х1 + 2 х2 > 16; х1 + 2 х2 > 8;

х2 > 1;

х1        > 2.

 

 

2.2.10.

 

2.2.12.

х1 + х2 < 1; х1 + х2 > 1; х1 х2 < 2;

х2 < 0. х1 + 2х2 > 12; 2х1 + х2 < 6; х1        > 2;

х2 > 2.