Диссертация (1149837), страница 4
Текст из файла (страница 4)
Выделим цепочку S∗ , на которой минимальное значение целевой функции в задаче (3.5) принимаетнаименьшее значение. Обозначим {w∗s }, {γs∗ }, {p∗i }, {qj∗ } соответствующее решение задачи (3.5). В силу леммы 3.1 матрица G∗ , составленная изстрок (w∗s , γs∗ ), s ∈ 1 : h, является решением задачи (3.1).Приходим к следующему заключению.31Теорема 3.1. Задача (3.1) эквивалентна конечному числу задач линейного программирования вида (3.5) в том смысле, что решение задачи (3.5)при S∗ ∈ Π, которому соответствует наименьшее значение целевойфункции, порождает решение задачи (3.1).3.4.
Рассмотрим пример. Пусть на плоскости заданы множества A и B,состоящие соответственно из точекa1 = (−2, 0), a2 = (2, 0), a3 = (0, 2), a4 = (0, 1);b1 = (0, 3), b2 = (3, 0), b3 = (−3, 0).Очевидно, что co(A) ∩ B = ∅ (см. рис. 3.1).Рис. 3.1. Множества A и BРешим задачу строгой 2-отделимости. В данном случаеn = 2, m = 4, k = 3, h = 2.Выясним, как выглядит задача (3.5) при S = (1, 1, 2). Выпишем векторнеизвестныхz = (w11 , w21 , γ1 , w12 , w22 , γ2 , p1 , p2 , p3 , p4 , q1 , q2 , q3 )и матрицу ограничений322 0 11−2 0 11 0 −2 11 0 −1 112 0 1 1.D=−20110 −2 110 −1 11 0 3 −11 3 0 −11 −3 0 −11Задача (3.5) примет вид431X1Xpi +qj → inf,4 i=13 j=1(3.6)Dz ≥ c e,pi ≥ 0,i ∈ 1 : 4;qj ≥ 0,j ∈ 1 : 3,где e — вектор, все компоненты которого равны единице.
При c = 1 решением данной задачи является векторz∗ = (111.2210, 112.0012, 272.9097, −78.1474, 27.3511, 192.1601,0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000).Минимальное значение целевой функции равно нулю. Строгое 2-отделениемножества co(A) от B при S = (1, 1, 2) выглядит так, как показано нарис. 3.2.33Рис. 3.2. Строгое 2-отделение при S = (1, 1, 2)Из общих соображений (см. пункт 1.10) следует, что при c = 0.1 решением задачи (3.6) является вектор 0.1z∗ . Вместе с тем, непосредственноерешение задачи линейного программирования (3.6) при c = 0.1 по программе из MATLAB даёт такой результат:z = (108.1756, 108.8484, 256.1022, −76.0149, 25.6934, 186.8208,0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000).Так проявляется неединственность решения задачи строгого h-отделения.Задание вектора индексов S = (1, 1, 2) соответсвует разбиению множества B на два подмножества {b1 , b2 } ∪ {b3 }.
Эти два подмножества согласовано отделяются от co(A) с помощью двух прямыхhw1 , xi = γ1 и hw2 , xi = γ2 .Существуют ещё два разбиения множества B на два подмножества:{b1 , b3 } ∪ {b2 } и {b2 , b3 } ∪ {b1 }.Им соответствуют векторы S = (1, 2, 1) и S = (2, 1, 1).Результат строгого 2-отделения при S = (1, 2, 1) показан на рис.
3.3.34Рис. 3.3. Строгое 2-отделение при S = (1, 2, 1)Этот случай симметричен случаю S = (1, 1, 2).При S = (2, 1, 1) строгой 2-отделимости нет (см. рис. 3.4).Рис. 3.4. Случай S = (2, 1, 1)Решением задачи, аналогичной (3.6), при c = 1 является векторz = (0.0000, −112.0230, −1.0000, 0.0000, 111.8673, 273.7824,2.0000, 2.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000).Минимальное значение целевой функции равно единице.3.5. В общем случае задание вектора S ∈ Π соответствует разбиению множества B, состоящего из k векторов, на h подмножеств. Число таких разбиений и определяет количество задач линейного программирования вида (3.5), к решению которых сводится решение задачи (3.1).Если заранее известно, что множества co(A) и B строго h-отделимы,то решение задачи (3.1) можно упростить.
После разбиения множества B35на h подмножеств следует независимо решать задачи линейного отделения каждого из этих подмножеств от множества A. В случае успешногоотделения совокупность разделяющих гиперплоскостей образует решениезадачи (3.1).В рассмотренном выше примере при S = (1, 1, 2) будем независимо решать задачи линейного отделения множеств {b1 , b2 } и {b3 } от A. Запишемсоответствующие задачи линейного программирования (см. (1.10))421X1Xpi +qj → inf,4 i=12 j=1−hai , w1 i + γ1 + pi ≥ c,i ∈ 1 : 4;(3.7)hbj , w1 i − γ1 + qj ≥ c, j ∈ 1 : 2;pi ≥ 0,иi ∈ 1 : 4;qj ≥ 0,j ∈ 1 : 2,41Xpi + q3 → inf,4 i=1−hai , w2 i + γ2 + pi ≥ c, i ∈ 1 : 4;(3.8)hb3 , w2 i − γ2 + q3 ≥ c;pi ≥ 0,i ∈ 1 : 4;q3 ≥ 0.Их решения {w1 , γ1 } и {w2 , γ2 } определяют две прямые, строго отделяющие co(A) от B (см. рис.
3.5).Рис. 3.5. Решения задач (3.7) и (3.8)36§ 4.Метод «градиентного типа» строгого h-отделения4.1. Итак, задача (3.1) строгого h-отделения сводится к конечному числузадач линейного программирования. Это приниципиальный факт. Однакос практической точки зрения здесь возникают трудности, поскольку количество соответствующих задач линейного программирования может бытьдостаточно большим. В такой ситуации приобретают интерес приближённые методы.Ниже будет показано, что функция от матрицы F (G) дифференцируемапо направлениям (в качестве которых также выступают матрицы). Этопозволит построить метод градиентного типа для решения задачи (3.1).4.2.
Введём обозначенияf (v, u) = hv, ui + c, v, u ∈ Rn+1 ,!!ai−bjâi =, i ∈ 1 : m, b̌j =, j ∈ 1 : k.−11С их помощью функции ϕi (G) и ψj (G) можно представить в видеϕi (G) = max f (g s , âi ) + ,ψj (G) = min f (g s , b̌j ) + .s∈1:hs∈1:hПо-прежнему рассматривается задачаmk1X1 Xϕi (G) +ψj (G) → min .F (G) :=Gm i=1k j=1Введём дополнительные обозначенияϕ̂i (G) = max f (g s , âi ),ψ̌j (G) = min f (g s , b̌j ),s∈1:hs∈1:hтак что (см. Дополнение B, свойство 5) и 6) плюсиковой функции)ψj (G) = ψ̌j (G) + .ϕi (G) = ϕ̂i (G) + ,37(4.1)ПоложимR̂i (G) = s ∈ 1 : h | f (g s , âi ) = ϕ̂i (G) ,Řj (G) = s ∈ 1 : h | f (g s , b̌j ) = ψ̌j (G) .Производные функций ϕi (G) и ψj (G) в точке G по направлению V определяются следующим образом:ϕi (G + tV ) − ϕi (G),t→+0tψj (G + tV ) − ψj (G)ψj′ (G, V ) = lim.t→+0tϕ′i (G, V ) = limСправедливаТеорема 4.1.
Производные ϕ′i (G, V ), ψj′ (G, V )h × (n + 1) -матриц G и V . При этомmax hv s , âi i,еслиs∈R̂(G) i sϕ′i (G, V ) =max, еслиhv,âii+s∈R̂(G)i0,еслиmin hv s , b̌j i,еслиs∈Ř(G) j sψj′ (G, V ) =hv,b̌iminj + , еслиs∈Ř(G)j0,еслисуществуют для всехϕ̂i (G) > 0,ϕ̂i (G) = 0,ϕ̂i (G) < 0;ψ̌j (G) > 0,ψ̌j (G) = 0,ψ̌j (G) < 0.Д о к а з а т е л ь с т в о этой теоремы приведено в Дополнении C.Отметим, что согласно (4.1)mk1 X ′1X ′F (G, V ) =ϕi (G, V ) +ψ (G, V ).m i=1k j=1 j′(4.2)4.3. Переходим к описанию «градиентного» метода. Возьмём начальноеприближение G0 . Пусть уже имеется ν-е приближение Gν .38Решаем вспомогательную задачуF ′ (Gν , V ) → min,V ∈Ω(4.3)где Ω — множество матриц V = v s (α) , элементы которых удовлетворяютнеравенствам s v (α) ≤ K,s ∈ 1 : h, α ∈ 1 : n + 1.Задача (4.3) сводится к небольшому числу задач линейного программирования.
Она имеет решение (в силу ограниченности множества Ω). Обозначим его Vν . ЕслиF ′ (Gν , Vν ) ≥ 0,то Gν — стационарная точка функции F (G). Вычисления прекращаются.В противном случае матрица Vν является направлением убывания функции F (G) из точки Gν . Находим точку минимума функции F (Gν + tVν )при t > 0. Обозначим её tν . Полагаем Gν+1 = Gν + tν Vν , после чего вычисления повторяются. Описание принципиальной схемы градиентного методадля решения задачи (4.1) завершено.4.4. Приведём пример строгого 3-отделения двух конечных множеств наплоскости с помощью градиентного метода.
Основное внимание будем уделять организации вычислений.Пусть на плоскости заданы множества A и B, состоящие соответственноиз точекa1 = (−3, 0), a2 = (1, 3), a3 = (2, −1), a4 = (0, 1);b1 = (−2, 2), b2 = (2, 3), b3 = (4, 1), b4 = (−1, −2).Очевидно, что co(A) ∩ B = ∅ (см. рис. 4.1).39Рис. 4.1. Задача строгого 3-отделенияСначала будем решать задачу строгого 3-отделения при c = 0. Возьмёмначальное приближение (см. рис. 4.2)1 0 3G0 = 0 1 4.0 −1 4Рис. 4.2.
Начальное приближение G0Заполним таблицу 1 и таблицу 2.Последние строки таблицы 1 и таблицы 2 позволяют вычислить значениецелевой функции: F (G0 ) = 45 .40Таблица 1: Вычисление функций ϕi (G0 )i1234f (g01 , âi )−6−2−1−3f (g02 , âi )−4−1−5−3f (g03 , âi )−4−7−3−5ϕ̂i (G0 )−4−1−1−3R̂i (G0 ){2, 3}{2}{1}{1, 2}ϕi (G0 )0000Таблица 2: Вычисление функций ψj (G0 )j1234f (g01 , b̌j )51−14f (g02 , b̌j )2136f (g03 , b̌j )6752ψ̌j (G0 )21−12Řj (G0 ){2}{1, 2}{1}{3}ψj (G0 )2102Переходим к вычислению производных по направлению.
Имеемϕ′i (G0 , V ) ≡ 0 при всех i ∈ 1 : 4;ψ1′ (G0 , V ) = hv 2 , b̌1 i = 2v 2 (1) − 2v 2 (2) + v 2 (3);ψ2′ (G0 , V ) = min hv s , b̌2 i =s∈{1, 2}= min{−2v 1 (1) − 3v 1 (2) + v 1 (3), −2v 2 (1) − 3v 2 (2) + v 2 (3)};ψ3′ (G0 , V ) ≡ 0;ψ4′ (G0 , V ) = hv 3 , b̌4 i = v 3 (1) + 2v 3 (2) + v 3 (3).Производная по направлению V функции F (G) при G = G0 в случаеψ2′ (G0 , V ) = −2v 1 (1) − 3v 1 (2) + v 1 (3) принимает видF ′ (G0 , V ) = − 12 v 1 (1) − 34 v 1 (2) + 14 v 1 (3) + 21 v 2 (1) − 12 v 2 (2) + 14 v 2 (3)++ 14 v 3 (1) + 21 v 3 (2) + 14 v 3 (3).41Решаем задачу линейного программированияF ′ (G0 , V ) → min,(4.4)V ∈Ωгде в качестве Ω возьмём множество (3 × 3)-матриц V , все элементы которых по модулю не превосходят 10 (K = 10). Очевидно, что решениемзадачи (4.4) является матрица10 10 −10V0 = −10 10 −10;−10 −10 −10при этом F ′ (G0 , V0 ) = −37.5.Таким образом, получили, что в случае ψ2′ (G0 , V ) = −2v 1 (1) − 3v 1 (2) ++v 1 (3) решение V0 — направление наискорейшего убывания функции F (G)при G = G0 .
Минимум функции F (G0 + tV0 ) на луче t > 0 достигаетсяпри t0 = 0.05, поэтому(см. рис. 4.3).1.5 0.5 2.5G1 := G0 + t0 V0 = −0.5 1.5 3.5−0.5 −1.5 3.5Рис. 4.3. Матрица G142Повторяем процесс.Таблица 3: Вычисление функций ϕi (G1 )i1234f (g11 , âi )−70.50−2f (g12 , âi )−20.5−6−2f (g13 , âi )−2−8.5−3−5ϕ̂i (G1 )−20.50−2R̂i (G1 ){2, 3}{1, 2}{1}{1, 2}ϕi (G1 )00.500Таблица 4: Вычисление функций ψj (G1 )j1234f (g11 , b̌j )4.5−2−45f (g12 , b̌j )−0.5046f (g13 , b̌j )5.5970ψ̌j (G1 )−0.5−2−40Řj (G1 ){2}{1}{1}{3}ψj (G1 )0000Очевидно, что F (G1 ) = 0.125.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
