Задачи ЛП и методы их решения

99

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

7.4. Характеристика угловых точек

Каждое допустимое решение ЗЛП является некоторой точкой множества D (см. (+)). Оказывается вершинам данного выпуклого множества соответствуют базисные решения ЗЛП (см. Рис.)

Утверждение

X 0 [N]- базисное решение ЗЛП

Не уменьшая общности можно считать, что N ' = {1,2, ,m} (в противном случае можно перенумеровать неизвестные).

(от противного) Пусть X 0 [N] - невырожденное базисное решение и предположим,

100

Пусть теперь X 0 [N] - вершина множества D и предположим, что столбцы матрицы A[M , N ' ] - линейно зависимы, т.е. λ[N ' ] ≠ 0[N ' ]:

A[M, N ' ] λ[N ' ] = 0[M ] (**) Рассмотрим вектор λ[N] = (λ[N ' ], 0[N \ N ' ]) . Очевидно, что

A[M, N] λ[N] = A[M, N ' ] λ[N ' ] + A[M, N \ N ' ] 0[N \ N ' ] = 0[M ] Возьмем число ε > 0 настолько малым, что неотрицательность векторов

Последнее представление противоречит условию теоремы о том, что X 0 [N] - вершина множества D. Следовательно, неверным является исходное предположение о линейной зависимости столбцов матрицы A[M , N ' ] и, на самом деле, X 0 [N] является базисным решением ЗЛП. ■

7.5. Достижимость оптимального решения ЗЛП в угловой точке множества допустимых решений

Допустимое решение ЗЛП X *[N] является оптимальным решением ЗЛП (I), если допустимого решения ЗЛП X[N]

f (X * ) ≥ f (X )

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

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

101

hЛинейная комбинация векторов {X1[N], , X s [N]}

s

∑λ[i] X i [N]

i=1

s

называется выпуклой, если 1) λ[i] ≥ 0 , (i 1: s) 2) ∑λ[i] =1h

i=1

Проиллюстрируем доказательство леммы для плоского многоугольника. Пусть D - выпуклый многоугольник на плоскости с вершинами {X1 , X 2 , , X p } и пусть X D - произвольная

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

X1

X1

Триангуляция

X

X3

X

X4

Тогда точка Х попадет в один из элементов триангуляции (пусть это будет треугольник

= λ1 X1 + λ2 X 3 + λ3 X 4

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

1) λ1 = α ≥ 0, λ2 = (1−α)β ≥ 0, λ3 = (1− α)(1− β ) ≥ 0 2) λ1 + λ2 + λ3 = α + (1− α)β + (1− α)(1− β ) = α + (1− α)(β + 1− β ) = α + 1− α =1

Лемма доказана. Теперь переходим к доказательству утверждения (для случая выпуклого

многогранника).

102

Пусть X *[N]- оптимальное решение ЗЛП и {X1[N], , X p [N]} - вершины множества D.

Согласно лемме

X *[N] = λ[1] X1[N] + + λ[p] X p [N] Подставим X *[N] в целевую функцию ЗЛП

f (X * ) = λ[1] f (X1 ) + + λ[p] f (X p )

Выберем среди вершин ту, на которой достигается наибольшее (среди всех вершин) значение целевой функции. Пусть это будет вершина X k [N] : f (X k ) ≥ f (Xi ), i 1: p .

решением ЗЛП. ■

7.6. Условия разрешимости ЗЛП. Конечность способа перебора вершин

Задача линейного программирования может быть неразрешима по одной из 2-х причин (см. раздел 1):

1)несовместность системы ограничений (множество D допустимых решений ЗЛП - пусто)

2)неограниченность целевой функции на множестве допустимых решений.

Если ни одна из этих причин не имеет места, то ЗЛП разрешима. Таким образом справедливо

утверждение

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

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

2) Число базисных решений ЗЛП (I) конечно и ограничено сверху числом сочетаний из n = N элементов по m = M (см. П. 3.1.).

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

число шагов.

7.7. Критерий оптимальности

Рассмотрим базисное решение ЗЛП с базисом N ' N

X0 [N] = (X 0 [N ' ], 0[N \ N ' ] )

ипроизвольное допустимое решение X[N], в котором выделим части относящиеся к

множествам индексов N ' и N \ N '

X[N] = (X[N ' ], X[ N \ N ' ] )

103

Так как X[N] - допустимое решение ЗЛП, то

A[M, N] X[N] = A[M, N ' ] X[N ' ] + A[M, N \ N ' ] X[N \ N ' ] = b[M ] Умножим последнее равенство слева на матрицу обратную к базисной

B[N ' , M ] A[M , N ' ] X[N ' ] + B[N ' , M ] A[M , N \ N ' ] X[N \ N ' ] = B[N ' , M ] b[M ] или

X[N ' ] = B[N ' , M ] b[M ] − Z[N ' , N \ N ' ] X[N \ N ' ]

Используя полученное выражение, вычислим значение целевой функции на решении X[N] f (X ) = C[N] X[N] = C[N ' ] X[N ' ] + C[N \ N ' ] X[N \ N ' ] =

= C[N ' ] B[N ' , M ] b[M ] − (C[N ' ] Z[N ' , N \ N ' ] − C[N \ N ' ]) X[N \ N ' ]

hЛегко видеть, что (см. Определение Z[N ' , N] в п. 5.1.)

ε[N] = (ε[N ' ],ε[N \ N ' ]) = (C[N ' ] Z[N ' , N ' ] − C[N ' ],C[N ' ] Z[N ' , N \ N ' ] − C[N \ N ' ]) = = (0[N ' ],ε[N \ N ' ])

Т.о. оценки базисных переменных всегда равны нулю!h

С учетом введенных обозначений имеем

f (X ) = C[N ' ] B[N ' , M ] b[M ]−ε[N \ N ' ] X[N \ N ' ]

Подставляя в последнее равенство X 0 [N] вместо X[N] находим

(это равенство можно получить также, определив X 0 [N ' ] из системы ограничений

X0 [N ' ] = B[N ' , M ] b[M ]

ивычислив значение целевой функции).

Окончательно получим соотношение

f (X ) = f (X 0 ) − ε[N \ N ' ] X[N \ N ' ] Из данной формулы следует, что неравенство

f (X 0 ) ≥ f (X )

будет выполнено для любого допустимого X[N], если ε[N \ N ' ] X [N \ N ' ]≥ 0[N \ N ' ] . А т.к. X[N \ N ' ] ≥ 0[N \ N ' ], то достаточно выполнения неравенства

ε[N \ N ' ] ≥ 0[N \ N ' ]

Таким образом нами получено следующее условие оптимальности текущего базисного решения:

Если все компоненты вектора оценок ε[N] неотрицательны, т. е. ε[ j] ≥ 0 j N ,

то текущее базисное решение является оптимальным решением ЗЛП.

Пример. Рассмотрим ЗЛП

f = 2x1 + x2 + 5x3 − x4 → max

107

hЗначение целевой функции на новом базисном решении f (Xθ ) = f (X 0 ) −θ ε[ j0 ]

увеличивается на f = −θ ε[ j0 ]. Указанное произведение называется величиной скачка целевой функции ( f ) при переходе к новому решению. Так в вышеприведенном примере

f (Xθ ) = f (X 0 ) −θ ε[4] = 50 − 5 (−7) = 85 f = −θ ε[4] = 35

Величина f может быть использована как определяющая для вектора наилучшего направления при переходе к новому решению (см. замечание к алгоритму симплекс-метода в п.3.3)h

Таким образом, окончательно можно резюмировать, что если ε[ j0 ] < 0 и критерий неограниченности не выполняется ( N+ ≠ 0/ , т.е. среди компонент вектора Z[N ' ] есть хотя бы одна положительная), то выбрав значение θ > 0 по правилу (+), получим новое

7.9. Базисная матрица нового решения ЗЛП. Левый мультипликатор. Формулы исключения Гаусса-Жордана

Так как матрица, заменившая в новом решении базисную матрицу A[M , N ' ] отличается от нее только одним столбцом, то для базисности новой матрицы A[M , N1' ] достаточно доказать следующую лемму: