Симплекс—метод

Рассмотрим следующую задачу линейного программирования:

Задача 1.

,

,

(1)

.

Здесь линейный оператор действует из в , , . Считаем что , и ранг матрицы равен .▄

Предположим теперь, что допустимый элемент задачи доставляет ей решение, т.е., для любого , такого что , справедливо: . Постараемся выяснить, что следует из такого предположения. Так как , то некоторые компоненты вектора нулевые, а некоторые – строго положительны. Пусть - строго положительные компоненты вектора . Им соответствуют столбцы матрицы , такие что в силу (1),

.

(2)

Предположим, что эти столбцы линейно зависимы. Тогда один из них, например, можно выразить через остальные, т.е. найдутся числа , такие что . Числа можно трактовать как компоненты некоторого вектора , число ненулевых компонент которого на одну, (), меньше чем число ненулевых компонент вектора . Про знаки ненулевых компонент вектора ничего определенного сказать нельзя. Тогда последнее равенство можно записать как . Подставим это равенство в (2). Тогда, если обозначить через вектор, отличающийся от лишь тем, что -я его компонента нулевая, получаем: и . Положим , и еще определим -ю компоненту как . Вектор удовлетворяет уравнению , про знаки же его компонент нам ничего не известно. Однако, т.к., номера ненулевых компонент вектора те же что и номера строго положительных компонент вектора , можно заключить, что при достаточно малых , будет справедливо

, , и .

(3)

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

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

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

.

(4)

Тогда вектор обладает следующими свойствами:

1. Число ненулевых компонент вектора как минимум на одну меньше, чем число ненулевых компонент исходного вектора , это следует из (4).
2. Это допустимый вектор, действительно, из (4) следует , из (3) - .
3. Вектор также доставляет решение нашей задаче, т.к. векторы и ортогональны.

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

Сформулируем теперь полученные результаты в виде следующих утверждений:

Лемма 1. Если задача 1 имеет решение, то найдется такое ее решение , что столбцы матрицы , соответствующие его ненулевым компонентам, будут линейно независимы. ▄

Лемма 2. Если - допустимый элемент задачи 1, а столбцы матрицы , соответствующие его ненулевым компонентам, линейно зависимы, то найдутся такие допустимые элементы задачи 1, и , , что точка лежит внутри отрезка с концами и .▄

Дадим теперь необходимые для дальнейших рассуждений определения.

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

Определение 2. Точки выпуклого множества, не являющиеся простыми, называются вершинами этого выпуклого множества. ▄

Например, все точки треугольника, кроме трех вершин – простые; все точки круга, кроме лежащих на окружности – простые.

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

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

.

(5)

Из того что (5) выполняется покомпонентно, из и , заключаем, что у векторов и те компоненты, которые нулевые у ,- тоже нулевые. Далее, , , откуда , причем , но это означает линейную зависимость столбцов матрицы , соответствующих ненулевым компонентам вектора , что противоречит исходным предположениям. Полученное противоречие и доказывает теорему. ▄

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

Доказательство. Утверждение теоремы есть прямое следствие леммы 1 и теоремы 1. ▄

Замечание 1. Если в рассуждении, которое привело нас к доказательству леммы 1 и леммы 2, считать точку просто допустимой точкой задачи (т.е. не требовать ее оптимальности), можно заключить во-первых, что если множество допустимых значений задачи непусто, то и множество вершин области допустимых значений задачи также непусто. И, во-вторых, получить конструктивный способ достижения одной из вершин из любой допустимой точки задачи. ▄

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

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

Доказательство. Утверждение теоремы есть прямое следствие леммы 2. ▄

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

Вектор удовлетворяет уравнению (1). Как известно, любое решение уравнения (1) представимо в виде: , где , - ядро оператора , т.е., удовлетворяет уравнению . Ядро оператора в нашем случае – это -мерное подпространство пространства . Найдем его базис. Пусть столбец не входит в набор столбцов матрицы , соответствующих ненулевым компонентам . Тогда его можно представить в виде линейной комбинации этих столбцов, т.е., найдется вектор , у которого нулевые все те компоненты, которые нулевые у , такой что . Теперь каждому столбцу матрицы соответствующему одной из нулевых компонент , поставим в соответствие вектор с компонентами: ; ; остальные компонент векторов - нулевые. Семейство векторов обладает следующими свойствами:

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

Отсюда можно заключить, что система векторов есть базис подпространства (ядра оператора ).

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

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

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

Теорема 4. Пусть вершина не доставляет максимума задаче 1, Тогда найдется вектор из базиса подпространства нулей матрицы такой что , и при достаточно малых векторы допустимы. ▄

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

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

Мы видим, что направление изменения функционала зависит от знака величины . Если - функционал убывает, если - возрастает, если ,- не меняется.

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

Описание алгоритма симплекс-метода

1. Находясь в очередной вершине (как попасть в самую первую вершину из просто допустимой точки, ясно из замечания 1), перебираем не задействованные в базисе соответствующем строго положительным компонентам , столбцы матрицы , вычисляем их разложения по базису , () и ищем такое, что . Если такого не найдется, т.е., все , то по теореме 4, наша вершина - и есть решение задачи.
2. Если же нашелся столбец , такой что , рассмотрим ненулевые компоненты вектора . Если все , то при любом справедливо , следовательно, функционал неограниченно возрастает на неограниченном множестве допустимых элементов задачи, и задача не имеет решения.
3. Если же есть строго положительные компоненты , выберем из них ту, для которой отношение минимально, и положим . Тогда в силу этого выбора, одна из компонент вектора с компонентами , , обратится в ноль. (Большее число компонент обратиться в ноль не может, в силу нашего предположения, что любые столбцов расширенной матрицы линейно независимы, и равенства ). Тогда вектор имеет ровно ненулевых компонент, для него выполнено , и, стало быть он является вершиной области допустимых значений задачи. Таким образом, мы перешли в смежную вершину, увеличив при этом значение функционала задачи.

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