Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
С войства решений задач линейного программирования
Пусть на плоскости Ох2 (рис. 1) заданы две точки: А1 (х , х ) и А2 (х , х ), определяющие вектор . Найдем координаты произвольной точки А(х1, х2) данного вектора: рассмотрим вектора , Так как , коллинеарны и одинаково направлены, то где 0 £ t £ 1
Пусть 1 - t = l1, t = l2 Þ и l1 ³ 0, l2 ³ 0, l1 + l2 =1. Рис. 1 Итак: если A = (х1; х2), A1 = (; ), A2 = (; ), то A = l1A1 + l2 A2, l1 ³ 0, l2 ³ 0, l1 + l2 = 1. (4) Точка А, для которой выполняются условия (4), называется выпуклой линейной комбинацией точек А1 и А2. При х1 = 1, х2 = 0 точка А совпадает с точкой А1; при х1 = 0, х2 = 1 – с концом A2. Таким образом для любой внутренней точки А отрезка [А1А2] выполняются условия (4). Точки А1 и А2 называются угловыми или крайними точками отрезка [А1А2]. Очевидно, что угловая точка не может быть представлена как выпуклая линейная комбинация двух других точек отрезка. Соотношения верны и для n-мерного пространства: Ā = λ1Ā1, + λ2Ā2 +... + λnĀn, при λ1 ³ 0, . Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя любыми точками полностью принадлежит и весь отрезок, их соединяющий. Примерами выпуклых множеств является: отрезок, прямая, полуплоскость, круг, шар, куб, пирамида, полупространство и т. д. Пример не выпуклого множества показан на рис. 2., т. к. [А1 А2] полностью этому множеству не принадлежит. Рис. 2 Точка множества называется граничной, если любой шар с центром в этой точке содержит как точки принадлежащие множеству, так и не принадлежащие множеству. Граничные точки множества образуют его границу. Замкнутым называется множество, содержащее все свои граничные точки. Замкнутое множество может быть ограниченным и неограниченным. Угловой точкой выпуклого множества называется точка, которая принадлежит этому множеству, но не является внутренней ни для какого отрезка, целиком лежащего в заданном множестве. Например, у многоугольника угловыми точками являются его вершины, у круга – точки окружности, которая его ограничивает. Таким образом, выпуклое множество может иметь конечное и бесконечное число угловых точек.
Опорной прямой выпуклого многоугольника (многогранника) называется прямая, имеющая с многоугольником (многогранником), расположенным по одну сторону от нее, хотя бы одну общую точку. Теорема 1 Замкнутый, ограниченный, выпуклый многоугольник является выпуклой линейной комбинацией своих угловых точек. Пример 3. Даны точки А1(3; – 2; 5) и A2(– 1; 6; 1). Найти точку А (х1; х2; x3), являющуюся линейной комбинацией точек А1 и A2. Так как точка А является линейной комбинацией точек А1 и A2, то Ā = = l1Ā1 + l2Ā2, l1 ³ 0, l1 + l2 = 1. Пусть, например, l1 = , тогда l2 = Þ (х1; х2; x3) = (3; –2; 5) + + (-1; 6; 1) = (; ; ), отсюда х1 = ; х2 = ; х3 = . Теорема 2 Если система векторов , , …, содержит m линейно независимых векторов , , , то допустимый план = (х1, х2, …, xm, 0, 0…0), n – является угловой точкой мно- () гоугольника планов. Теорема 3 Если задача линейного программирования имеет решение, то целевая функция достигает экстремального значения, хотя бы в одной из угловых (крайних) точек многогранника решений. Если же целевая функция достигает экстремального значения больше, чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.
|
|||||||
Последнее изменение этой страницы: 2020-11-11; просмотров: 77; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.95.7 (0.008 с.) |