![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Доказательство.
Докажем теорему для случая КЗЛП (для остальных постановок доказательство аналогично). Итак, Рассмотрим выпуклую линейную комбинацию точек Для доказательства выпуклости P достаточно показать, что Действительно:
Теорема 2.5. Пересечение любого числа выпуклых множеств является выпуклым множеством. Доказательство. Пусть Замечание. Очевидно, что объединение двух выпуклых множеств, вообще говоря, не выпукло. Нетрудно доказать, что если Пользуясь теоремой 2.4., можно, например, доказать, что множество планов Р основной ЗЛП является выпуклым множеством. Действительно,
Определение 2.9. Точка Теорема 2.6. Множество выпукло тогда и только тогда, когда оно содержит все выпуклые комбинации любого конечного числа своих точек. Доказательство. Необходимость. Пусть P – выпуклое множество. Тогда по определению 1
Тогда точка Достаточность. Если множество Определение 2.10. Точка Теорема 2.7. Если Доказательство. Пусть Действительно, поскольку
Из определения
и, так как Определение 2.11. Точка Замечание. Таким образом, множество Теорема 2.8. Если Доказательство. Пусть Большую роль в построении теории линейного программирования играет понятие крайней точки. Определение 2.12. Точка
Геометрически это означает, что крайняя точка не может лежать внутри отрезка, соединяющего две различные точки выпуклого множества. Она лишь может быть одной из концевых точек этого отрезка.
Например, крайними точками треугольника являются его вершины, а круга - все точки окружности. Определение 2.13. Замкнутое ограниченное выпуклое множество с конечным числом крайних точек будем называть выпуклым многогранником. Например, треугольник является выпуклым многогранником, а круг - нет, так как у него бесконечное число крайних точек. Теорема 2.9 (о представлении).Любая точка выпуклого замкнутого ограниченного множества может быть представлена в виде выпуклой линейной комбинации конечного числа крайних точек этого множества. Пример 2.2. Любая внутренняя точка круга может быть представлена в виде выпуклой линейной комбинации концов хорды, проходящей через эту точку. Пример 2.3. Любая внутренняя точка Легко видеть, что `Х = (1- l)`Х1 + l`Х4, 0 £ l £ 1
и `Х4 = (1- l1)`Х2 + l1`Х3, 0 £ l1 £ 1,
откуда `Х = (1- l)`Х1 + l (1-l1)`Х2 + l× l1`Х3 , 0 £ l £ 1, 0 £ l1 £ 1,
причём 1 - l ³ 0, l(1- l1) ³ 0, l× l1 ³ 0 и (1- l) + l(1- l1) + l× l1 = 1.
|