1)Различные формы постановок задач линейного программирования ( ЗЛП). Переход от общей формы к стандартной и канонической. Эквивалентность перехода от стандартной формы к канонической и наоборот.

Общая форма:

Задачу линейного программирования можно сформулировать так:

Максимизировать (минимизировать) при условиях:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n  (≥, =) b₁ ;

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n  (≥, =) b₂ ;

. . . . . . . . . . . . .

a_i1x₁ + a_i2x₂ + … + a_inx_n  (≥, =) b_i ;                

x₁  0, x₂  0, …, x_n  0.    

                  

Стандартная форма:

В стандартной форме все ограничения, кроме условий неотрицательности x, принимают вид неравенств.

(Записывая уже в матричной форме):

Ax  b или Ax ≥ b

x ≥ 0 x ≥ 0

  -> max -> min

Каноническая форма:

В канонической форме все ограничения, кроме условий неотрицательности x, принимают вид равенств:

Ax = b

x ≥ 0

-> extr(max или min)

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

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

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной.

В то же время каждое уравнение системы ограничений

можно записать в виде неравенств:

Отметим, наконец, что если переменная , не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и , приняв .

По первой теореме эквивалентности для всякой задачи линейного программирования существует эквивалентная ей каноническая задача линейного программирования, а по второй теореме эквивалентности для всякой задачи ЛП существует эквивалентная ей стандартная задача ЛП. Пользуясь этими двумя теоремами, мы можем спокойно говорить о том, что стандартная и каноническая задача тесно связаны между собой и простым преобразованием от одной формы легко перейти к другой.

2) Свойства множества допустимых решений ЗЛП. Внутренние и граничные точки. Выпуклость множества оптимальных решений ЗЛП.

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

1) Множество допустимых решений ЗЛП является выпуклым (если оно не пусто);

2) Множество оптимальных решений ЗЛП также является выпуклым;

3) Локальный и глобальный оптимумы совпадают;

4) Любая точка допустимого множества решений является выпуклой комбинацией вершин;

5) Если ЗЛП имеет допустимое решение, то она имеет допустимое базисное решение (оно соответствует вершине многогранного множества)

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

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

Теорема: если у ЗЛП есть оптимальные решения, то их множество выпукло.

4) Определение вершины. Крайняя точка. Базисное решение. Теоремы о вершине ( теорема 1 о соответствии вершины допустимого множества решений базисному; теорема 2 о ранге матрицы носителя; теорема 3 о продвижении по ребру от вершины к вершине при поиске оптимального решения)

Непустое множество планов основной задачи линейного программирования называется многогранником решений, а всякая угловая (крайняя) точка многогранника решений – вершиной.

Точка выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Крайнюю точку следует искать среди граничных. Крайняя точка обращает некоторые неравенства в условии в равенства.

Решение задачи называется базисным решением задачи, если его компоненты, соответствующие базисным столбцам и называемые базисными компонен­тами, больше или равны нулю а все остальные компоненты (небазисные) — равны нулю.

1 Теорема:

Пусть х - произвольная крайняя точка. Необходимо доказать, что х является допустимым базисным решением.

Предположим противное, т.е. х - недопустимое базисное решение. Тогда для ненулевых компонент вектора х система вектор-столбцов    

линейно зависима. Пусть    

Линейная зависимость означает, что существуют

                                              

для которых выполняется равенство

                                              

                С другой стороны, из допустимости вектора х имеем равенство

                                              

                Это означает, что точка

                              

является пересечением тех же гиперплоскостей, что  и у точки х (совпадение ненулевых компонент означает совпадение гиперплоскостей, проходящих через точку). Но точка х - крайняя точка, это означает, что соответствующие ей гиперплоскости имеют только одну точку пересечения. Поэтому должно выполняться х'=х, а значит все       

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

2 Теорема:

3 Теорема: Перебирая все вершины (а их обязательно конечное число) многомерного множества М мы обязательно получим вершину (опт. баз. реш) в кот. цел. ф-ция З достигает своего минимума. Пусть ЗЛП разрешима, т.е. она имеет опт. реш. Тогда эта ЗЛП имеет оптимальное баз. решение

5)Симплексный метод решения ЗЛП: общая характеристика и геометрический смысл.

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X1, ..., Xm) >= 0 при Xj = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений Ai,0 >= 0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные Ai,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A0,j >= 0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования. Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все Ai,0 >= 0 и A0,j >= 0, то решение оптимально.

Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной Xj с отрицательным коэфициентом A0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменную Xj с A0,j < 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A0,p < 0 из всех отрицательных A0,j <0.

Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A0,p < 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную Xq, которая раньше других обращается в нуль при увеличении переменной Xp ведущего столбца. Ее индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (Ai,0 / Ai,p).

Элемент Aq,p называется ведущим элементом, cтрока q симплекс-таблицы, cодержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки Xq заменяется в базисе переменной ведущего столбца Xp и становится свободной переменной с значением 0, в то время как новая базисная переменная Xp достигнет максимально возможного значения, равного: max Xp = ( Aq,0 / Aq,p)

После указанного взаимообразного обмена переменными Xp и Xq между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице:

Ai,p = 0, если i не равно q

и

Ai,p = 1, если i = q.

Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение.

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