Лекция № 6

1.6. Основные теоремы линейного программирования и идея симплекс-метода

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

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

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

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

Из теоремы 1 следует, что ЗЛП является выпуклой задачей математического программирования, так как линейную целевую функцию можно считать как выпуклой, так и вогнутой (в зависимости от направления оптимизации на max или min), а множество допустимых решений по утверждению теоремы является выпуклым. Следовательно, ЗЛП можно отнести к классу одноэкстремальных оптимизационных задач.

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

Конечное число крайних точек (теорема 1) при их переборе гарантирует сходимость поиска к оптимальному решению за конечное число шагов.

На основе этих теорем может быть следующим образом определена идея алгоритма нахождения оптимального решения ЗЛП, названного алгоритмом симплекс-метода.

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

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

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

1.7. Обоснование алгоритма симплекс-метода для поиска оптимального решения злп

Обоснование алгоритма состоит из двух частей:

- обоснование процедуры перебора допустимых базисных решений,

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

1.7.1. Перебор допустимых базисных решений

Предположим, что для ЗЛП (1.37) выбран допустимый базис и в соответствии с ним определены следующие структуры данных : Этому базису в n-мерном пространстве оптимизационных переменных соответствует некоторая крайняя точка выпуклого многогранного множества допустимых решений, которой, в свою очередь, инцидентны ряд ребер этого множества, соединяющих указанную крайнюю точку с другими его крайними точками.

Можно показать, что для осуществления перемещения в пространстве оптимизационных переменных по одному из указанных ребер необходимо выбрать соответствующую небазисную компоненту x[l] (lN(B)) и начать увеличивать ее значение (уменьшать нельзя, так как в рассматриваемом выше базисном решении x[l]=0, и это сразу приведет к выходу из множества допустимых решений).

Общее решение (1.45) системы уравнений, обеспечивающее выполнение основных ограничений ЗЛП, будет изменяться в соответствии с соотношением:

.

Это соотношение в векторной форме записи имеет следующий вид:

. (1.53)

Установим связь нового решения системы уравнений (1.53) с прежним допустимым базисным решением. Для этого необходимо выполнить следующие формальные процедуры:

- умножим обе части равенства (1.40) на (-x[l]);

- суммируем левые и правые части двух равенств: получившегося в результате выполнения предыдущего пункта и равенства (1.48);

- приведем подобные члены образовавшегося равенства при одних и тех же векторах a^j.

В результате получим следующее соотношение:

. (1.54)

Из сравнения (1.54) и (1.53) можно сделать вывод о том, что эти соотношения имеют идентичную структуру. На основе этого можно записать следующие выражения, определяющие связь нового решения системы уравнений (1.53) с прежним допустимым базисным решением:

, , (1.55)

, (1.56)

, (для ). (1.57)

Эти соотношения соответствуют линейному перемещению от точки прежнего базисного решения x* в направлении вектора S на шаг λ≥0 (рис.1.14):

(1.58)

где , а компоненты вектора S определяются следующим образом:

, , (1.58)

, (1.59)

, (для ). (1.60)

Новое решение будет оставаться допустимым решением ЗЛП до тех пор, пока выполняются условия . Нарушение этого условия при перемещении в направлении S может произойти только по тем прежним базисным компонентам, значения которых уменьшаются, то есть тем, которым в векторе a^l(B) соответствуют положительные коэффициенты:

. (1.61)

В общем случае, уменьшаться могут одновременно несколько таких компонент.

Максимальный шаг λ(В), который можно сделать в выбранном направлении S, определяется той r-ой базисной компонентой, которая, уменьшаясь, первой примет нулевое значение:

. (1.62)

При неоднозначности решения задачи (1.62) значение r определяется следующим образом:

. (1.64)

Cущность соотношения (1.64) состоит в определении r как наименьшего порядкового номера базисной компоненты и соответствующего номера строки матрицы А(В), удовлетворяющих указанному в (1.64) условию.

Соотношения (1.55-1.60, 1.62-1.64) определяют переход в n-мерном пространстве оптимизационных переменных из крайней точки, соответствующей прежнему базисному решению, в новую крайнюю точку, соответствующую новому базисному решению, по соединяющему их ребру. Их можно переписать еще и в следующем виде:

, (1.65)

, (для ).

Сам базис изменяется при этом следующим образом:

, (1.66)

то есть место столбца в новом базисе занимает столбец .

Соответственно изменяется и базисное множество:

. (1.67)

Рассмотрим специальный случай, когда после выбора l и соответствующего ему направления перемещения S выполняется следующее условие:

для всех i=1,2,...,m. (1.68)

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

(1.69)