назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [ 12 ] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


12

Допустимая область для 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 - угловая точка, что и доказывает теорему.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [ 12 ] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]