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


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


8

Учитывая, что параметрическое уравнение прямой, проходящей через точки , Х2, имеет вид х(а) = Х2 +(xi -Х2)а , то перегруппировав слагаемые в последнем соотношении, получим x(a) = axi+(1-а)х2 и, следовательно, выпуклое множество X вместе с любыми двумя точками xi,X2eX, содержит весь отрезок, соединяющий эти точки.

На рисунке многоугольник ABFCDD является выпуклым, а многоугольник ABFCDL - выпуклым не является. Выпук-

Среди точек выпуклого множества можно выделить точки внутренние. граничные и угловые. Точка множества называется внутренней, если существует окрестность, в которой содержатся только точки данного множества. Точка называется граничной, если в ее окрестности содержатся как точки, принадлежащие данному множеству, так точки и не принадлежащие ему. Точка множества называется угловой (или крайней), если она не является внутренней ни для одного отрезка, целиком принадлежащего данному множеству.

Если задача линейного программирования имеет оптимальное решение, то целевая функция принимает оптимальное значение в одной из угловых точек.

лыми могут быть не только многоугольники, но и круг, сектор, полуплоскость, полупространство.

Рис. 2.2

Рассмотрим свойства выпуклых множеств.

Теорема 2.2. Пересечение выпуклых множеств выпукло.

Доказательство. Пусть X = Xj п , где , Х2 выпуклые множества. Рассмотрим две произвольные точки х, х множества X. Так как X с Xj , то х,х с X,. В силу выпуклости множества X, из этого вытекает, что весь отрезок [x,x]cXj. Точно так же доказывается, что с Х2. Из этого следует, что [х,х] с п Xj = X.

Определение 2.2. Суммой двух множеств XqR" , Х2 с R" назовем множество X = хх = + Х2,х, G ХрЛ:2 G 21, состоящее из всех попарных сумм элементов множеств ХиХ2-



Теорема 2.3. Сумма выпуклых множеств выпукла.

Доказательство. Пусть x,xgX, где Х = Х, 4-Х2 . Тогда в Х, и Х2 найдутся такие элементы, что х = х, + Х2 и х = х, + Х2 , где х, х, с Х,, а Х2 Х2<Х 2 , Пусть а произвольное число О < а < 1. Тогда

oxi+(l-a)xi , 0x2+(l-a)x2 е Х2 . По определению сумма этих элементов принадлежит множеству Х :

ах +(l-a)xi +ах2 +(1-а)х2 = = a(xi +X2) + (l-a)(xi +X2)=ax + (l-a)x g X

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

Основным свойством, характеризующим выпуклые множества является так называемое свойство отделимости. Для пояснения этого свойства рассмотрим на плоскости замкнутое выпуклое множество X и точку d, не принадлежащую этому множеству (рис. 2.3).

Тогда найдется такая прямая ах\ + bxj = с, что множество X и точка J = (б/р2) лежат по разные стороны от этой прямой, т.е. для любой точки (хрХз) g X выполняется неравенство ох, + fcx2 < с, в то время как ad + bd2 > с . Сформулируем и докажем этот факт для выпуклого множества в «-мерном пространстве. Для этого введем понятие - аналогичное понятию прямой на плоскости.

Adud2)=d

Рис. 23

Определение 2.3. Гиперплоскостью в пространстве назьшается множество точек X = (xp...,x„), координаты которых удовлетворяют уравнению вида РХ, + Р2Х2 4-... + рх = с, или в векторном виде (р,х) = с . 32



Вектор p = {Pi,-,p„) называется нормалью к этой гиперплоскости (предполагается, что /? О).

Теорема 2.4, Пусть X - замкнутое выпуклое множество аеХ, а = (ар...,тогда существует гиперплоскость с нормалью рчО такая,

что (р,а)>с и для любого хеХ вьшолняется неравенство < с [14].

Доказательство. Рассмотрим функцию аргумента x = (xp...,x)

на множестве X.

(р(х) = {х,-аУ +(х2-аУ +... + (х„ .

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

Пересечение X = U пХ является замкнутым и ограниченным множеством. Следовательно, функция (р(х) достигает на нем минимума в некоторой точке ЬеХ.

Учитывая, что b является минимумом функции (р(х) на всем множестве X, зафиксируем произвольную точку хеХ и рассмотрим отрезок x(a) = ax-\-{l-a)b, 0<а<1 Так как X выпукло, то х(а) g Xдля всех

0<а<1 и поэтому (р[х{а))>(р{Ь). Функция (р[х{а)) дифференцируема по « как суперпозиция двух дифференцируемых функций (х) и

ср{х{а))-(р{Ь)

Х[а), поэтому существует предел lim

- = (х(0))>0.

Рис. 2.4

2 Исследование операций

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