Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Еквівалентний запис
- Визначення 1.3 Точкова множина S називається опуклою множиною
- Визначення 1.5 (опуклої оболонки множини)
| Визначення 1.2
Відрізок лежить на векторі , де Q і P суть дві точки, представлені векторами q, p Rn, є множина точок g, визначених співвідношенням Еквівалентний запис має наочну геометричну інтерпретацію: до кінця вектора q додається частка різницевого вектору (p-q), який спрямований з точки Q в точку P. Оскільки нас зараз цікавить тільки множина точок відрізка, а не його напрямок, завжди можна замінити на , і можна цей відрізок позначати рискою : Визначення 1.3 Точкова множина S називається опуклою множиною (ОМ), якщо для будь-яких виконується Для відрізка це може звучати так: множина точок відрізка S утворює опуклу множину, якщо будь-який відрізок, обмежений точками з S, лежить в S. Очевидно що в точкову множину відрізка, входять всі точки відрізка, тобто дана умова для відрізка виконується. Тому відрізок - це опукла множина Приклад, коли умова не виконується: Визначення 1.4 Внутрішня і екстремальна точки Т очка множини називається внутрішньою, якщо існує її околиця (- + -) (з усіх боків) яка містить точки тільки даної множини. Будь-яку точку В опуклої множини S називають екстремальною (або крайньою точкою або вершиною або кутовою точкою) цієї множини, якщо не існує ніякої підмножини S для якої В є внутрішньою точкою. Наприклад для відрізка: якщо не існує в цій множині таких двох точок Q і P, що утворюють відрізок усередині якого лежить розглянута точка В. Визначення 1.5 (опуклої оболонки множини) Опукла оболонка точок P1, P2, ... Pk, представлених відповідними векторами p1, p2, ... pk, є множина точок (векторів) виду (Е) Опуклу оболонку можна конструктивно вивести (побудувати) на цих векторах, послідовно застосовуючи визначення відрізка. Одночасно це буде поясненням умов на вагові коефіцієнти . Отже Нехай P1, P2 - довільні точки. Тоді із визначення 1.2 слідує що є будь-яка точка відрізка P1-P2. З'єднаємо її відрізком з довільною точкою P3. Тоді є довільна точка трикутника P1P2P3. З'єднаємо її відрізком з довільною точкою P4. Тоді є довільна точка чотирьохгранника P1P2P3P4. Такий процес побудови ОМ можна продовжувати до вичерпання всіх наявних точок (векторів). Наприклад, якщо остання з наявних точок є P5, то поєднуючи її відрізком з точкою y4, отримаємо, що є довільна точка п’ятигранника P1P2P3P4P5. По побудові, маємо де , , , Нехай тепер накладена умова на вагові коефіцієнти : , Тоді, вибрав довільні , що задовольняють цій умові, послідовно знайдемо Це тіж k2,k3,k4 та k5, що вище беруть участь в побудові будь-яких точок: двухгранніка (k2), тригранника (k3), четирехгранніка (k4) і пятігранніка (k5). Тим самим доведено, що опукла оболонка точок p1, p2, ..., pk визначена повністю умовою на невід'ємні коефіцієнти в лінійної комбінації (*) Зауваження: Може бути питання, а що, якщо чотири вектора P1, P2, P3, P4 задані в одній площині б тобто в просторі Rn де к = 4 і n = k-2 Тоді маємо 2 варіанти 1.випукла оболонка на трьох векторах покриває четвертий P4 і тоді в (е) відповідний приймає граничне значення або Опукла оболонка існує на всіх чотирьох векторах і це буде перетин трьох підмножин побудованих на поєднаннях трьох векторів з даних чотирьох P1, P2, P3, P4 і по суті (Е) виконується. Правда як видно з рис. це уявлення неоднозначне - дійсно для представлення кожної точки даного 4-кутника досить якогось одного набору трьох векторів з P1, P2, P3, P4. Однак по суті (Е) все одно виконується Тобто в загальному випадку гарантовано можливо побудувати опуклу оболонку на заданих векторах P1,P2,...Pk якщо будь-яка їх підмножина є векторами загального положення в Rd-1 для всіх . Це означає що жодна з підмножин при всіх d а) на деякому підмножині векторів або б) як перетин опуклих множин збудованих на подмножествах заданих векторов. Останній випадок при очевидно зводиться до (*) Тобто останні зауваження ніяк не відбиваються на висновках загального випадку опуклої оболонки на множині векторів - P1,P2,...Pk жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|