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


[Старт] [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]


13

Докажем вторую часть теоремы, предположив, что F[x) принимает максимальное значение более, чем в одной угловой точке, например, в точках Xi,X2,...,X , где \<q<p, В этом случае, следовательно, выполняется F[x) = F[x2) =... = ) = М.

Пусть X -выпуклая линейная комбинация угловых точек, т.е.:

В этом случае, учитывая линейность функции F{x), получим F(x) = (aiXi+a22+-.. + «g)=«i(i) + «2(2) + --- + «(

т.е. линейная функция F принимает максимальное значение в произвольной точке X, являющейся выпуклой линейной комбинацией угловых точек.

Теорема доказана.

Замечание 1. Теорема доказана для задачи линейного программирования на максимум. Утверждение теоремы сохраняет силу и при рассмотрении задачи линейного программирования на минимум. Доказательство теоремы в этом случае аналогично уже приведенному.

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

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

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



решений и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение [2].

Пусть X = (xi,...,x,0,...,0) - допустимое базисное решение задачи

линейного программирования вида тах(с,х), Ах<Ь, х>0.

В этом решении первые т компонент основные переменные, а остальные п-т компонент- неосновные переменные, равные нулю в базисном решении (если это не так, то можно перенумеровать переменные); покажем, что X - угловая точка многогранника. Предположим обратное, т.е. X не является угловой точкой, и тогда точку X можно представить внутренней точкой отрезка, соединяющего две различные, не совпадающие с X точки.

2 >2 »••»mm+l••.„)• ToгдaXмoжeт быть представлена как вьшуклая линейная комбинация точек XiH Xi, т.е.

Х = «1X + 2,(2.5)

где а, > О, «2 О и «1 + «2 = 1 •

Запишем векторное равенство (2.5) в координатной форме.

Поскольку х] > о, х > О (у =!,...,«), а>0, «2 - » но из последних

п-т равенств следует, что х,1 =0, xi =0, х =0, х =0, т.е. в

решениях Xi, Х2 и X системы уравнений Ах = В значения п-т компонент можно считать значениями не основных переменных. Значения не основных переменных определяют значения основных и, следовательно xJ =xf =Xi,...,x =х =Х2. Таким образом, все п компонент в



решениях , , X совпадают, и значит точкиХ сливаются,

что противоречит допущению. Следовательно, X - угловая точка многогранника решений.

Докажем обратное утверждение. Пусть X = (xi,jC2,..,x,x,,...,x„) - угловая точка многогранника решений и первое ее т координат положительны. Покажем, что X - допустимое базисное решение. Рассмотрим задачу линейного программирования в виде F = (с,х) -> max .

Р,Х,+РХ,+... + Р„Х„В,

где X > О

f«u1

Г«,2

Г«1„

«21

«22

«2„

ч«т2;

Если векторы Р,,„,Р линейно независимы, то ранг г матрицы А, составленной из компонент этих векторов, равен т , т.е. определитель IO, следовательно, переменные Xi,X2,..,x - базисные, а решение

X = (xi,X2,...,x,0,...,0) - базисное допустимое, и теорема доказана. Предположим противное, т.е. векторы Р,,„,Р линейно зависимы, следовательно, в равенстве

а,Р, + «22 + ... + ССтРт + .•• += О

хотя бы один из коэффициентов а,,..,а,,„,а отличен от нуля. Умножим почленно равенство (2.6) на множитель > О,

(2.6)

(2.7)

а,Р, + fiaP +... + ИССтРш +... + ИССпРп = О-

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

Рл + Р22+... + А=.(2.8)

Равенство (2.7) и (2.8) почленно сложим и затем вычтем его из равенства (2.8). Получим

Р,{х, + «,) +... + Рх + а J +... + Р„{х„ + = В(2.9)

[Старт] [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]