Диссертация (1149837), страница 3
Текст из файла (страница 3)
Значение целевой функции на нём равно 2c.Вместе с тем, на планеw = O,γ = 0,yi ≡ c,zj ≡ c(1.16)задачи (1.10) значение целевой функции также равно 2c. Отсюда следует,что план (1.16) задачи (1.10) с w = O является оптимальным.Теорема доказана.Пример 1.2. Рассмотрим на плоскости R2 два двухточечных множестваA = (0, 0), (1, 1) ,B = (1, 0), (0, 1)20(см.
рис. 1.4). В данном случае выполняется условие (1.11). По теореме 2задача (1.9) имеет решение g∗ = (w∗ , γ∗ ) с w∗ = O. При этом µ = 2c.Рис. 1.4. Множества A и B из примера 1.2Покажем, что у задачи (1.9) существует другое решение g0 = (w0 , γ0 )с w0 6= O.Согласно (1.3)f (g) =12 [−γ + c]+ + [w1 + w2 − γ + c]+ + 21 [−w1 + γ + c]+ + [−w2 + γ + c]+ .Здесь w = (w1 , w2 ). Положимw0 = (c, c),γ0 = c,g0 = (w0 , γ0 ).Тогда f (g0 ) = 2c. Значит, на векторе g0 достигается минимум функции f (g).Гиперплоскость H0 = {x | x1 + x2 = 1} является наилучшей гиперплоскостью, приближённо отделяющей множество A от множества B.Таким же свойством обладают вектор g1 = (w1 , γ1 ) с w1 = (0, c), γ1 =c2и гиперплоскость H1 = {x | x2 = 21 } (см.
рис. 1.4).1.7. Особенность,отмеченная в примере 1.2, имеет общий характер.Теорема 1.3. При µ > 0 у задачи (1.9) существует решение g0 = (w0 , γ0 )с w0 6= O.Д о к а з а т е л ь с т в о. Допустим, что у решения g∗ = (w∗ , γ∗ ) задачи (1.9)21компонента w∗ оказалась нулевой. Построим другое решение g0 = (w0 , γ0 )с w0 6= O.По теореме 1.2 выполняется соотношение (1.11) и µ = 2c. Возьмём произвольный ненулевой вектор p ∈ Rn и рассмотрим задачу линейного программированияhp, wi → min,m(1.17)k1 X1X−yi −zj = −2c;m i=1k j=1−hw, ai i + γ + yi ≥ c,i ∈ 1 : m;hw, bj i − γ + zj ≥ c, j ∈ 1 : k;yi ≥ 0, i ∈ 1 : m;zj ≥ 0, j ∈ 1 : k.Вектор (1.16) удовлетворяет ограничениям задачи (1.17), то есть являетсяеё планом.
Покажем, что этот план не может быть оптимальным.В случае оптимальности плана (1.16) у задачи, двойственной к (1.17),должен существовать план с таким же (нулевым) значением целевой функции. Таким образом, должна быть совместной системаXmkXcui +vj − 2ζ = 0,i=1−mXj=1ui ai +i=1mXi=10 ≤ ui ≤1m ζ,(1.18)kXvj bj = p,(1.19)j=1ui −kXvj = 0,(1.20)j=10 ≤ vj ≤ k1 ζ, j ∈ 1 : k.i ∈ 1 : m;Покажем, однако, что эта система несовместна.22(1.21)Из (1.18) и (1.20) следует, чтоmXkXui = ζ,i=1vj = ζ.j=1В силу (1.21) получаем ui ≡ m1 ζ, vj ≡ k1 ζ.
Равенство (1.19) принимает видmk1 X1Xζ −ai +bj = p.m i=1k j=1Но это противоречит условию (1.11) (напомним, что p 6= O).Установлено, что план (1.16) задачи (1.17) с нулевым значением целевойфункции не является оптимальным. Значит, существует планw0 , γ0 , {u0i }, {vj0 }(1.22)с отрицательным значением целевой функции. У такого плана должно бытьw0 6= O.Теперь отметим, что план (1.22) задачи (1.17) удовлетворяет ограничениям задачи (1.10) и на нём целевая функция задачи (1.10) принимаетнаименьшее возможное значение, равное 2c (напомним, что µ = 2c).
В силу эквивалентности задач (1.9) и (1.10) вектор g0 = (w0 , γ0 ) с w0 6= O будетрешением задачи (1.9).Теорема доказана.З а м е ч а н и е. В качестве ненулевого вектора p можно взять, например,любую ненулевую разность bj0 − ai0 . В этом случае множество планов задачи, двойственной к (1.17), которое определяется условиями (1.19)– (1.21),будет непустым. Вместе с непустотой множества планов само́й задачи (1.17)это гарантирует наличие у задачи (1.17) оптимального плана.1.8. При µ > 0 решение g0 = (w0 , γ0 ) задачи (1.9) с w0 6= O можно привестик каноническому виду. Как и в п.
1.5 положим23w1 = w0 /kw0 k,γ1 =1min hw1 , bj i2 j∈1:kc1 =1min hw1 , bj i2 j∈1:k+ maxhw1 , ai i ,i∈1:m− maxhw1 , ai i ,i∈1:mg1 = (w1 , γ1 ).В данном случае c1 ≤ 0. При c1 = 0 гиперплоскость H1 = x | hw1 , xi = γ1не строго отделяет множество A от множества B. При c1 < 0 та же гиперплоскость H1 является наилучшей, приближённо отделяющей множество Aот множества B.Согласно определению w1 , γ1 , c1 имеемhw1 , ai i − γ1 + c1 ≤ 0, i ∈ 1 : m−hw1 , bj i + γ1 + c1 ≤ 0, j ∈ 1 : k.При c1 < 0 эти неравенства определяют «смешанную полосу»c1 ≤ hw1 , xi − γ1 ≤ −c1 ,которая содержит как точки множества A, так и точки множества B.
Ширина смешанной полосы равна 2|c1 |.1.9. На рис. 1.5 приведён пример наилучшего приближённого отделениядвух множеств.1.10. Чтобы подчеркнуть зависимость от параметра c, будем писать f (g, c),µ(c) вместо f (g) и µ. Очевидно, что при всех c > 0 справедлива формулаf (cg, c) = cf (g, 1).Поэтомуµ(c) = min f (g, c) = min f (cg, c) = c min f (g, 1) = cµ(1).ggg24Рис.
1.5. Наилучшее приближённое отделение двух множествБолее того, если g1 — решение задачи (1.9) при c = 1, то векторgc = cg1 будет решением задачи (1.9) при произвольном c > 0. Такимобразом, аддитивный параметр c > 0 играет роль нормирующего множителя.§ 2.Постановка задачи строгого h-отделения2.1. Пусть в Rn заданы два конечных множестваkA = {ai }mi=1 и B = {bj }j=1 .Следуя [27], назовём выпуклую оболочку множества A и множество Bстрого h-отделимыми, если существует h гиперплоскостей видаHs = x ∈ Rn | hws , xi = γs ,ws 6= O,s ∈ 1 : h,таких, что выполняются неравенстваhws , ai i < γs при всех i ∈ 1 : m и всех s ∈ 1 : h,shw , bj i > γs при каждом j ∈ 1 : k и некотором s ∈ 1 : h.25(2.1)На рис.
2.1 приведён пример строгого 2-отделения.Рис. 2.1. Пример строгого 2-отделенияВведём функциюmk1 X1XF (G) =max hws , ai i − γs + c + +min −hws , bj i + γs + c + .m i=1 s∈1:hk j=1 s∈1:hЗдесь G — матрица размера h × (n + 1) со строкамиg s = (ws , γs ),s ∈ 1 : h;c > 0 — параметр. Матрицу G указанного вида будем называть подходящей, если у неё все элементы ws ненулевые (ws 6= O, s ∈ 1 : h). Ясно, чтоF (G) ≥ 0 при всех G.Теорема 2.1.
Выпуклая оболочка множества A и множество B строгоh-отделимы тогда и только тогда, когда существует подходящая матрица G∗ , такая, что F (G∗ ) = 0.Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. Пусть выполнены соотношения (2.1) и ws 6= O при всех s ∈ 1 : h. Обозначимδ :=mini∈1:m, s∈1:h−hws , ai i + γs > 0.Каждому j ∈ 1 : k соответствует индекс sj ∈ 1 : h, такой, чтоδj :=hwsj , bj i − γsj > 0.26При δ∗ = min{δ, δ1 , .
. . , δk }, δ∗ > 0, выполняются неравенстваПоложим w∗s =δ∗ ≤ −hws , ai i + γs ,i ∈ 1 : m, s ∈ 1 : h,δ∗ ≤ hwsj , bj i − γsj ,j ∈ 1 : k.c sδ∗ w ,γs∗ =cδ∗ γ s .Получимhw∗s , ai i − γs∗ + c ≤ 0,i ∈ 1 : m, s ∈ 1 : h;s−hw∗j , bsj i + γs∗j + c ≤ 0,j ∈ 1 : k.Отсюда по определению плюсиковой функции следует, что на подходящей матрице G∗ со строками (w∗s , γs∗ ), s ∈ 1 : h, выполняется равенствоF (G∗ ) = 0.Д о с т а т о ч н о с т ь. Если F (G∗ ) = 0 на некоторой подходящей матрице G∗ , тоmax hw∗s , ai i − γs∗ + c + = 0 при всех i ∈ 1 : m;s∈1:hmin −hw∗s , bj i + γs∗ + c + = 0 при всех j ∈ 1 : k.s∈1:hЭто значит, чтоhw∗s , ai i − γs∗ + c[−hw∗s , bj i + γs∗ + c+= 0 при всех i ∈ 1 : m и всех s ∈ 1 : h;+= 0 при каждом j ∈ 1 : k и некотором s ∈ 1 : h.По определению плюсиковой функции данные соотношения гарантируютвыполнение условий (2.1) с ws = w∗s , γs = γs∗ .Теорема доказана.З а м е ч а н и е.
В случае co(A) ∩ B = ∅ всегда существует строгое|B|-отделение. Для этого при каждом j ∈ 1 : k нужно построить гиперплоскость Hj = x ∈ Rn | hwj , xi = γj , строго отделяющую точку bj от27замкнутого выпуклого множества co(A). На самом деле, некоторые гиперплоскости Hj могут отделять от co(A) сразу несколько точек множества B,поэтому h ≤ |B|.На рис. 2.2 приведён пример строгого |B|-отделения.Рис.
2.2. Строго |B|-отделимые множества2.2. Равенство F (G∗ ) = 0 может выполняться на матрице G∗ , котораяне является подходящей. В этой связи представляет интерес следующееутверждение [3].Теорема 2.2. Пусть F (G∗ ) = 0. Тогда1) у матрицы G∗ не все компоненты w∗s равны нулю;2) если w∗s = O на множестве J ⊂ 1 : h, то co(A) и B строгоh − |J| -отделимы.Д о к а з а т е л ь с т в о. Если F (G∗ ) = 0 и все компоненты w∗s матрицы G∗ненулевые, тоmax[c − γs∗ ]+ + min [c + γs∗ ]+ = 0.s∈1:hs∈1:hНо это противоречит свойству 11) плюсиковой функции (см. Дополнение B).Обозначим через J множество индексов s ∈ 1 : h, на которых w∗s = O.Условие F (G∗ ) = 0 перепишем в видеon s1 X∗∗max max hw∗ , ai i − γs + c + , max[c − γs ]+ +s∈Jm i=1s∈1:h\Jmon1Xs∗∗min min −hw∗ , bj i + γs + c + , min[c + γs ]+ = 0.+s∈Jk j=1s∈1:h\Jk28(2.2)Из равенства нулю первой суммы и свойства 5) плюсиковой функции следует, чтоmax hw∗s , ai i − γs∗ + c ≤ 0,s∈1:h\Jc − γs∗ ≤ 0,i ∈ 1 : m;s ∈ J.(2.3)(2.4)В силу (2.4), c + γs∗ ≥ 2c при всех s ∈ J, так чтоmin[c + γs∗ ]+ ≥ 2c.s∈JПо свойству 6) плюсиковой функции равенство нулю второй суммы из (2.2)возможно только тогда, когдаmin −hw∗s , bj i + γs∗ + c ≤ 0,s∈1:h\Jj ∈ 1 : k.(2.5)На основании (2.3) и (2.5) получаемhw∗s , ai i < γs∗ при всех i ∈ 1 : m и всех s ∈ 1 : h \ J;hw∗s , bj i > γs∗ при каждом j ∈ 1 : k и некотором s ∈ 1 : h \ J.Это и означает, что множества co(A) и B строго h − |J| -отделимы.Теорема доказана.2.3.
В дальнейшем мы будем исследовать экстремальную задачуF (G) → min,(2.6)где минимум берётся по всем матрицам G размера h × (n + 1). Будет показано, что задача (2.6) всегда имеет решение.Пусть G∗ — какое-нибудь решение задачи (2.6) и µ = F (G∗ ). Если µ = 0,то по теореме 2.2 множества co(A) и B строго h − |J| -отделимы, гдеJ — множество индексов s ∈ 1 : h, на которых w∗s = O.
В частности, ес-ли G∗ — подходящая матрица, то множества co(A) и B строго h-отделимы.29При µ > 0 по теореме 2.1 строгое h-отделение невозможно. Если соответствующая матрица G∗ подходящая, то будем говорить, что она обеспечивает наилучшее приближённое h-отделение множеств co(A) и B.§ 3.Строгая h-отделимость и линейное программирование3.1. Как показано в предыдущем параграфе, задачу строгого h-отделенияkвыпуклой оболочки множества A = {ai }mi=1 от множества B = {bj }j=1можно формализовать так:mk1 X1XF (G) :=ϕi (G) +ψj (G) → min,m i=1k j=1где(3.1)ϕi (G) = max hws , ai i − γs + c + ,s∈1:hψj (G) = min −hws , bj i + γs + c + .s∈1:hНеизвестной является h × (n + 1) -матрица G со строками (ws , γs ),s ∈ 1 : h; c > 0 — параметр. Принципиальным является тот факт, чтозадача (3.1) сводится к конечному числу задач линейного программирования [3].3.2.
Обозначим Π = S = (s1 , . . . , sk ) | sj ∈ 1 : h при всех j ∈ 1 : k .Лемма 3.1. Справедливо равенствоinf F (G) = min infGS∈Π Gmn1 Xmi=1 o1 Xsj−hw , bj i + γsj + c + .ϕi (G) +k j=1k(3.2)Д о к а з а т е л ь с т в о. По лемме о сумме минимумов (см. Дополнение D)kXj=1ψj (G) = minS∈ΠkXj=1−hwsj , bj i + γsj + c + .30Отсюда и из определения функции F (G) следует, чтоF (G) = minS∈Πmn1 Xmi=1Значит,inf F (G) = inf minGG S∈Π o1 Xsj−hw , bj i + γsj + c + .ϕi (G) +k j=1kmn1 Xmi=1 o1 Xsjϕi (G) +−hw , bj i + γsj + c + .k j=1k(3.3)Остаётся в правой части (3.3) поменять местами инфимум по G и минимумпо S ∈ Π.3.3. Лемма показывает, что задача (3.1) эквивалентна конечному числуэкстремальных задач видаmk1 X1 Xmax hws , ai i − γs + c + +−hwsj , bj i + γsj + c + → inf , (3.4)Gm i=1 s∈1:hk j=1соответствующих различным S ∈ Π. В свою очередь, задача (3.4) эквивалентна задаче линейного программированияmk1 X1Xpi +qj → inf,m i=1k j=1−hai , ws i + γs + pi ≥ c,(3.5)i ∈ 1 : m, s ∈ 1 : h;hbj , wsj i − γsj + qj ≥ c, j ∈ 1 : k;pi ≥ 0,i ∈ 1 : m;qj ≥ 0,j ∈ 1 : k.Задача (3.5) имеет решение при всех S ∈ Π.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
