18. Свойство решений задачи линейного программ-я.

Симплекс–метод основан на ряде следующих теорем.

Теорема 1. О множестве планов задачи линейного программирования. Множество всех планов ЗЛП является выпуклым множеством.

Теорема 2. О целевой функции задачи линейного программирования. Целевая функция задачи линейного программирования принимает своё оптимальное значение в одной из угловых точек ОДЗ переменных.

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

Теорема 3. Достаточные условия угловой точки

Пусть система векторов А1,А2,…,Аk (k≤n) в разложении А1х1+А2х2+…+Аnхn=А0 является линейно независимой и такой, что А1х1+А2х2+…+ Аkхk= 0А , где все хj≥0, j=1,k, (k≤n), то точка х=(х1,х2,…,хk,0,0,…,0) является угловой точкой ОДЗ.

Теорема4. Необходимые условия угловой точки. Пусть точка х=(х1,х2,…,хn) является угловой точкой ОДЗ, тогда векторы в разложении, соответствующие положительным значениям переменных будут линейно независимыми.

Следствия из теорем

Следствие 1. Опорный план имеет не более m положительных координат. Если он имеет ровно m положительных координат, то такой опорный план наз-ся невырожденным, в противном случае – вырожденным.

Следствие 2. Каждая угловая точка ОДЗ является опорным планом.

19. Теорема об опорном плане.

Определение. План х, положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП.

Следствие 1. Опорный план имеет не более m положительных координат. Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае – вырожденным.

След-е 2. Каждая угловая точка ОДЗ яв-ся опорным планом.

20. Геометрическая интерпретация задачи линейного программирования.

Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, наз-ся допустимыми значениями переменных или планами.

Множество всех планов ЗЛП называется областью допустимых значений переменных (ОДЗ).

План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным.

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

Прямая наз-ся опорной к множеству M, если она имеет с множеством M хотя бы одну общую точку и все точки множ-ва M расположены по одну сторону от этой прямой.

21. Графический метод решения задачи линейного программирования с двумя неизвестными

Случай двух переменных. Область допустимых решений (ОДР) такой задачи строится как решение системы линейных неравенств, фигурирующих в системе ограничений. При этом неравенство определяет полуплоскость, лежащую ниже прямой , а неравенство – полуплоскость, лежащую выше этой прямой.

Если ОДР пуста, то задача решений не имеет. В противном случае необходимо использовать линии уровня и опорные прямые.

Прямая (коэффициенты при x, y – это коэффициенты целевой функции) называется линией уровня; постоянная C пробегает все множество действительных чисел. Линии уровня образуют семейство параллельных прямых с общим вектором нормали . Опорной прямой называется линия уровня, которая имеет с областью допустимых решений хотя бы одну общую точку и по отношению к которой область допустимых решений оказывается полностью в одной из полуплоскостей. Область допустимых решений имеет не более двух опорных прямых!

Вектор нормали в данном случае совпадает с градиентом целевой функции ( ), т.е. это вектор, указывающий направление наибольшего возрастания функции. Таким образом, если линии уровня перемещаются в направлении нормали, то значения целевой функции возрастают; если перемещение происходит в противоположном направлении, то значения целевой функции убывают. Следовательно, после построения непустой ОДР необходимо выполнить следующие действия.

1) Построить вектор нормали и одну линию уровня, например, проходящую через начало координат (прямую ).

2) Линию уровня перемещать до превращения ее в опорную прямую (учитывать, решается ли задача на минимум или максимум, смешение шло по направлению нормали или в противоположном направлении).

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