Основные утверждения линейного программирования. Теорема об оптимальном решении З. Л. П. В выпуклом многограннике

 

Опр 1. Множество точек называется выпуклым, если вместе с его любыми двумя точками ему принадлежит и весь отрезок, соединяющий их. Примерами выпуклых множеств являются: сектор, круг, многогранная область, прямая, отрезок, полуплоскость

Опр 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

Опр 3. Точка множества называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Опр4. Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества.

Опр5. Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.

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

Опр6. Множество точек называется замкнутым, если оно включает все свои граничные точки.

Опр7. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество. В противном случае множество называется неограниченным.

Опр8. Выпуклое, замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек называется выпуклым многогранником если оно ограниченное, и выпуклой многогранной областью, если нет.

Множество всех допустимых решений совместной системы m линейных уравнений с n переменными (m<n) является выпуклым многогранником (выпуклой многогранной областью) в n-мерном пространстве.

Утв 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).

Теорема. Если задача линейного программирования имеет оптимальное решение, то целевая функция принимает max (min) значение в одной из угловых точек многогранника решений. Если целевая функция принимает max (min) значение более чем в одной угловой точке, то она достигает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Вырождение, зацикливание,неразрешимость задач линейного программирования

Вырождение - если некоторые из свободных членов=0, то в соответствующем опорном решение некоторые из базисных переменных окажутся 0.

Если нулевой свободный член окажется в разрешающей строке, то Z не изменится после выполнения итерации. Тоже самое может быть и на 2,3 шаге. Теоретически не исключается возможность после нескольких шагов прийти к первоначальному опорному решению. Такая ситуация называется Зацикливание

Если после очередной итерации окажется Bs<0 а все остальные элементы этой строки >0 то задача неразрешима и з-за несовместимости системы ограничений.

Теорема о выборе разрешающего элемента при решении симплексным методом основной злп в случае неотрицательности свободных членов.

Для того, что бы свободные члены системы ограничетельных уравнений остались неотрицательными, а значение целевой функции не уменьшилось при выполнении шага МЖИ достаточно

1 выбрать разрешающий столбец содержащий любую отрицательную оценку и хотя бы 1 положительный элемент(на практике выбирают максимум по модулю отриц. Оценку)

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

Условие оптимальности и неразрешимости в случае неограниченности целевой функции для основной задачи линейного программирования в случае неотрицательности свободных членов.