Тема 3.

Задача линейного программирования (ЗЛП) и ее свойства

1. Свойства множества допустимых решений ЗЛП

2. Формы и терминология ЗЛП.

3. Эквивалентность форм ЗЛП.

4. Основные свойства ЗЛП и теоремы ЛП.

1. Свойства множества допустимых решений ЗЛП

Многогранные множества, многогранники, вершины

def.Множество точек пространства, координаты которых удовлетворяют уравнению

, где, называетсягиперплоскостьюH_ab.

Или H_ab=

def.Множества

,, (2)

порождаемые этой гиперплоскостью, называются (закрытыми) полупространствами.

def.Векторaназываетсянормальюк гиперплоскостиH_ab, к ней ортогонален и направлен в сторону пространстваH⁺_ab

Если в соотношениях (2) знаки “”,”” заменить на “”,””, получим открытые полупространства.

Алгоритм доказательства выпуклости некоторого множества .

1. записать множество Хв виде

Х={x  Rⁿxудовлетворяют условиямS;

2. предположить, что точки (для них выполняются условияS);

3. показать,что выпуклая линейная комбинация этих двух точек

принадлежитХ,

то есть, используя тот факт, что точкиудовлетворяют условиямSпоказать,что и их линейная выпуклая комбинация удовлетворяет тем же условиям.

Утверждение

Гиперплоскости является выпуклым множеством.

Доказательство

1. 

2. Пусть ,

значит и(точкиx¹иx²свойствомS )

3. И пусть ,

Покажем, что ВЛК (т.е. докажем, что).

,

значит xудовлетворяет условиюS, то есть.

Таким образом - выпуклое множество. Ч.т.д.

Самостоятельно №1. Показать, что шар является выпуклым множеством.

Теорема:Пересечение произвольного числа выпуклых множеств является выпуклым множеством.

Самостоятельно № 2. Доказать теорему.

def.Множество, образованное пересечением конечного числа полупространств и гиперплоскостей (если это пересечение не пусто) называетсямногогранным множеством.

Многогранное множество выпукло.

Самостоятельно № 3 Доказывать.

def.Многогранникомназывается ограниченное многогранное множество.

Многогранное множество Хможет быть представлено как множество решений системы из конечного числа линейных неравенств:

(3)

Для любой точки обозначим черезI(x)множество номеров тех неравенств из (3), которые в данной точке выполняются как равенства:

defОграничения с номерами изI(x)называютсяактивнымив точкех.

def.Точканазываетсявнутренней, если для нее все неравенства в (3) выполняются как строгие неравенства.

Для внутренней точки.

defВсе точки множестваХ, не являющиеся внутренним, являютсяграничными.

Для граничной точки

def.Точканазываетсявершиной(крайней точкой,экстремальной точкой), если она не может быть выражена в виде линейной комбинации других различных точек множестваХ,

т.е.

Точка называется вершиной, если не существует точектаких, что

при0<<1

Определим мощность множества I(x)вершиныx*.

Утверждение. Точкаx*будет вершиной многогранного множестваХвида (3), еслии среди векторов(!!!!) имеетсяn линейно-независимых.

УтверждениеТочкаx*будет вершиной многогранного множестваХвида (3), если она является единственным решением системы уравнений

Таким образом, для вершины имеем

Самостоятельно № 4.

Разработать алгоритм нахождения всех вершин многогранного множества вида (11).

def.Вершинуназываютневырожденной, если, и вырожденной в противном случае.

Теорема: Любое многогранное множество имеетне более конечного числавершин.

Самостоятельно № 4.Доказать теорему

Теорема. Непустое многогранное множество вида (3) имеет по крайней мере одну вершину в том и только том случае, еслиrang A = n.

Без доказательства.

def.Ограничение многогранного множестваХназываетсяжестким, если любая точкаХудовлетворяет емукак точному равенству.

def. Размерностьrмногогранного множестваопределяется формулой: rn-g, гдеg- ранг матрицы, составленной из жестких ограничений этого множества.

def 1. ПодмножествоYмногогранного множестваXназываетсяq-мерной гранью Х,если

а) размерность Y = q

б) из условий иследует, что

.

При q=0приведенное определение превращается в определение вершины.

Определение грани может быть дано в терминах ограничений, определяющих Х.

def 2.q-мерной гранью множества Хявляетсяq-мерное многогранное множество, система условий которого образуется из ограничений (описывающих многогранник) путем замены некоторых знаков неравенства знаками равенства, при этом число линейно-независимых ограничений, выполняемых на грани как равенство, равноn-q.

def.Одномерная грань множестваХназываетсяребром.

Из следующей теоремы следует, что вершины многогранника полностью определяют этот многогранник

Теорема (о представлении многогранника): Множество точек многогранникасовпадает с множеством любых выпуклых линейных комбинаций его вершин.

Доказательство:

Теорема содержит два утверждения, если – вершины многогранника, то

а) каждая его точка хможет быть представлена в виде:

()

б) каждая точка х, удовлетворяющая условиям (), принадлежит многограннику с данными вершинами.

Утверждение б) мы уже доказали: каждая выпуклая линейная комбинация () определяет только точкиk-угольника, порожденного даннымиkвершинами.

Ограничимся доказательством утверждения а) для случая n=2.

Доказательство:

 При одной вершине (k=1) теорема содержит тривиальное утверждение:х=х¹;

 При k=2 многогранник представляет собой отрезок, соединяющий точких¹ их². Но, как известно, любая точкахэтого отрезка может быть представлена в виде

И наоборот, если будет принимать все значения от 0 до 1 включительно, то тогда точкахбудет пробегать весь отрезок отх¹ дох²включительно. Таким образом, оба утверждения теоремы справедливы.

 Пусть k=3, то есть многогранник имеет три вершины:х¹, х², х³.

Продолжить доказательство самостоятельно.