Допустимая область для X этой системы изображена на рисунке 2.8.
-Xi+X2=2
3X1+5X2=15
10X1+7X2=35
Рис. 2.8
Тогда носителем точки А является пара прямых 3x+5x2=15; 10х, +7x2 =35.
Пусть с7 = (/р...,/)л, 1</<7w, 7 = 1,...,Л: номера тех векторов ,
которые определяют носитель точки xq , сг - множество остальных номеров / е {1,..., , не попавших в множество сг .
Обозначим через А матрицу, строками которой являются векторы а/, / 6 от, через - вектор, составленный из координат вектора b с номерами из множества сг. Аналогично введем обозначения А-,Ы,
Тогда ограничения для точки xq, являющейся граничной, примут вид: AXq = й, AXq <Ь. Докажем следующую теорему.
Теорема 2.10. Точка xq еХ является крайней тогда и только тогда, когда ранг матрицы А равен п.
Доказательство. Вспомним, что рангом матрицы называется максимальное число ее линейно независимых строк (или столбцов) Далее, из курса линейной алгебры известно, что уравнение Ах = О имеет нулевое
решение тогда и только тогда, когда ранг матрицы А равен числу переменных п.
Покажем вначале, что если х - крайняя точка, то ранг матрицы А равен п.
Допустим, это не так, тогда ранг меньше п и уравнение Ах = О имеет решение хО. Так как А-х <Ь,то можно подобрать такое малое
аО,что A-(xQ+ax)<b, A-(Xq - ах) <b, при этом: А (Хо -{-ах) = Ах-\- аА х = Ах = . Аналогично A(Xq - ах) = .
Отсюда следует, что точки Хо+ах, Xq-otx принадлежит X. Это противоречит тому, что xq является крайней точкой, поскольку Xq = \/2(Xq +ax) + l/2(xQ -ах).
Обратно, пусть ранг матрицы А равен п. Допустим, Xq не является крайней точкой множества X. Тогда должны существовать две точки х, х"еХ, хх\ что Хо =1/2x41/2х\ В этом случае b=AXQ=l/2Ах + \12Ах\ Поскольку Ах <, Ах"<Ь,то из последнего равенства вытекает Ах = Ь= Ах". Отсюда получим А{х - х") = О , что противоречит предположению о ранге матрицы А, учитывая, что х - х" О. Теорема доказана.
Из этой теоремы получаем два важных следствия.
Теорема 2.11. Если в множествеимеются край-
ние точки, то их число конечно.
Доказательство, Из теоремы 2.10 следует, что всякой крайней точке соответствует квадратная невырожденная матрица А, полностью определяющая эту точку Xq = Ab. Следовательно, число крайних точек
в множестве X конечно, поскольку у матрицы А существует лишь конечное число подматриц.
Теорема 2.12. Если множество X = xg/?" Ах<Ь ограниченно, то
оно является выпуклым многоугольником.
Для доказательства достаточно применить определение 2.8. вьшуклого многогранника и теорему 2.8 о том, что всякое ограниченное и замкнутое (компактное) множество является вьшуклой оболочкой своих крайних точек.
Определение 2.11. Множество X = \хеК\Ах<Ъ будем называть
многогранной областью, если оно неограниченное. В общем случае множество X (если оно ограниченное или неограниченное) будем называть многогранником решений задачи линейного программирования.
Ответ на вопрос, в какой точке многогранника решений возможно решение задачи линейного программирования, дается в следующей фундаментальной теореме.
Рассмотрим задачу линейного программирования:
F - {с, х) max(min) при ограничениях Ах < b , х > О.
Теорема 2.13. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает оптимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает оптимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек [25].
Доказательство. Предположим, что многогранник решений является ограниченным. Обозначим угловые точки через Xi,...,x, а оптимальное решение через х * (далее доказательство приводится для линейной задачи максимизации). Тогда целевая функция FX*>F(x)
для всех точек многогранника решений. Если X* - угловая точка, то
первая часть теоремы доказана. Предположим, что X* не является угловой точкой.
Тогда на основании теоремы 2.8 и 2.9 X* можно представить как выпуклую комбинацию угловых точек многогранника решений, т.е.
Так как F(x) -линейная функция, получаем:
F{r) = F(a,x, + а,х, +... + ах) = ± cCjFix).(2.4)
В последнем выражении среди значений F (х. ) / = 1,...,р выберем максимальное. Пусть оно соответствует угловой точке х,{\<к<р). Обозначим его через М, т.е. F{x,) = M. Заменим в выражении (2.4) каждое значение этим максимальным значением М.
Найдем F(x*<aM -\-a2M + ... + арМ = Mjaj = М . Так как предположению X* - оптимальное решение, поэтому FX*>M, с другой стороны F Х* < М . Следовательно, F (х*) = М = F(x), где X - угловая точка, что и доказывает теорему.