Диссертация (1149837), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Решением является матрица00V1 = 00000000,00так что Q1 = Q(G1 +V1 ) = Q(G1 ) = F (G1 ). По теореме 5.1 это гарантируетлокальную оптимальность матрицы G1 .676.4. Рассмотрим другой способ выбора начального приближения. Разобъеммножество B на четыре подгруппы по три точки. Далее будем линейноотделять каждую подгруппу от множества A.Построим начальное приближение. Возьмём точки {b1 , b3 , b4 } и линейноотделим их от множества A (см.

§ 1). Получим векторg1 = (w1 , γ1 ) = (−1, 0, 3),определяющий гиперплоскость, линейно отделяющую эти точки от множества A (см. рис. 6.8).Рис. 6.8. Наилучшее линейное отделение первой группы точекДалее возьмём точки {b2 , b5 , b8 }, получим векторg2 = (w2 , γ2 ) = (−0.59, −0.81, 3.23),(см. рис. 6.9).68Рис. 6.9. Наилучшее линейное отделение второй группы точекАналогично отделяем точки {b9 , b10 , b12 }, получаем векторg3 = (w3 , γ3 ) = (0.99, 0.08, 3.72),и точки {b6 , b7 , b11 }, получаем векторg4 = (w4 , γ4 ) = (0.45, 0.89, 4.47)(см. рис. 6.10 и рис.

6.11).69Рис. 6.10. Наилучшее линейное отделение третей группы точекРис. 6.11. Наилучшее линейное отделение четвертой группы точекТеперь в качестве начального приближения возьмем матрицу G0 со строками g1 , g2 , g3 , g4 , так что (см. рис. 6.12)70−103−0.59 −0.81 3.23G0 = . 0.99 0.08 3.720.45 0.89 4.47Рис.

6.12. Начальное приближение G0Будем решать задачу строгого 4-отделения при c = 0.5 методом градиентного типа (см. п. 4.3).Заполним таблицу 11 и таблицу 12.Таблица 11: Вычисление функций ϕi (G0 )i12345678910f (g01 , âi )0.50−0.50−0.50−2.50−2.50−3.50−4.50−5.50−5.50−6.50f (g02 , âi )−0.97−1.560.87−4.35−3.54−4.13−3.91−7.73−5.31−3.47f (g03 , âi )−6.21−5.21−5.44−3.07−3.14−2.15−1.220.08−0.150.61f (g04 , âi )−5.31−4.87−7.55−2.18−3.08−2.63−3.080.95−1.74−3.97ϕ̂i (G0 )0.50−0.500.87−2.18−2.50−2.15−1.220.95−0.150.61R̂i (G0 ){1}{1}{2}{4}{1}{3}{3}{4}{3}{3}ϕi (G0 )0.5000.8700000.9500.6171Таблица 12: Вычисление функций ψj (G0 )j123456789101112f (g01 , b̌j )−2.5000.500.501.502.504.505.506.507.508.509.50f (g02 , b̌j )0.210.873.59−0.86−1.487.198.360.8711.972.048.295.65f (g03 , b̌j )10.207.787.067.486.604.832.842.610.610.61−0.92−1.61f (g04 , b̌j )7.657.434.529.4410.330.950.058.55−3.527.650.954.08ψ̌j (G0 )−2.5000.50−0.86−1.480.950.050.87−3.520.61−0.92−1.61Řj (G0 ){1}{1}{1}{2}{2}{4}{4}{2}{4}{3}{3}{3}ψj (G0 )000.50000.950.050.8700.6100Значение целевой функции F (G0 ) равно 0.54.

Производная по направлению V функции F (G) при G = G0 принимает вид:1 1′243F (G0 , V ) =hv , â1 i + hv , â3 i + hv , â8 i + hv , â10 i +101 114423+hv , b̌2 i + + hv , b̌3 i + hv , b̌6 i + hv , b̌7 i + hv , b̌8 i + hv , b̌10 i .12Решаем задачу линейного программированияF ′ (G0 , V ) → min,V ∈Ωгде в качестве Ω возьмём множество (4 × 3)-матриц V , все элементы которых по модулю не превосходят 10 (K = 10). Решением этой задачи являетсяматрица−5.71 10 10 10 −10 10V0 = ; 10 −10 10−1010 −10при этом F ′ (G0 , V0 ) = −20.22.Получили направление наискорейшего убывания V0 функции F (G) приG = G0 .

Минимум функции F (G0 + tV0 ) на луче t > 0 достигается приt0 = 0.01, поэтому72−1.060.1 3.1−0.49 −0.91 3.33G1 := G0 + t0 V0 = , 1.09 −0.02 3.820.35 0.99 4.37F (G1 ) = 0.43 (см. рис. 6.13).Рис. 6.13. Первое приближение G1Повторяем процесс. На следующем шаге получаем матрицу−1.260.3 2.9−0.29 −1.11 3.53G2 = , 0.90 0.18 4.020.15 1.19 4.57F (G2 ) = 0.35 (см. рис.

6.14).73Рис. 6.14. Второе приближение G2Повторяем процесс. На следующем шаге получаем матрицу−1.160.33−0.19 −1.01 3.63G3 = , 0.90 0.18 4.020.05 1.09 4.67F (G3 ) = 0.16 (см. рис. 6.15).74Рис. 6.15. Третье приближение G36.5. Далее рассмотрим решение данного примера при тех же начальныхусловиях, что и в п. 6.4, с помощью метода из §5.Положим c = 0.5, εA = 0.1, εB = 0.1 и σ = 0.0001. Строим начальноеприближение как в п.

6.4. Получим−103−0.5882 −0.8087 3.2349G0 =  0.9971 0.0767 3.71980.4472 0.8944 4.4721и F (G0 ) = 0.5416.Формируем индексные множестваI0 = i ∈ 1 : m | max f (gνs , âi ) > −εA ,s∈1:hJ0 = j ∈ 1 : k | min f (gνs , b̌j ) > −εB ,s∈1:hL0j = s ∈ 1 : h | f (gνs , b̌j ) = min f (gνp , b̌j ) ,p∈1:h75j ∈ Jν .Имеем (см. таблицу 11 и таблицу 12)I0 = {1, 3, 8, 10},J0 = {2, 3, 6, 7, 8, 10},L02 = {1}, L03 = {1}, L06 = {4}, L07 = {4}, L08 = {2}, L010 = {3}.Решаем задачу линейного программирования вида (5.19).

Запишем вектор неизвестныхz = ξ1 , ξ3 , ξ8 , ξ10 , η2 , η3 , η6 , η7 , η8 , η10 , v 1 (1), v 1 (2), v 1 (3),v 2 (1), v 2 (2), v 2 (3), v 3 (1), v 3 (2), v 3 (3), v 4 (1), v 4 (2), v 4 (3) ,матрицу1111D=ограничений30130131111233302312-31121111031-4 1-3 -4 1-3 -4 1-3 -41111-421-4 21-4 21-4 21-3.5 -1 -1-3 2 -111-1 51 5112 -5 -114 -5 -1761111-1-1и вектор правой части ограниченийb = 0.5000, −0.9703, −6.2111, −5.3137, −0.5000, 0.8676, −5.4441,−7.5497, −5.5000, −7.7343, 0.0783, 0.9471, −6.5000, −3.4703, 0.6152,−3.9721, 0, 0.5000, 0.9473, 0.0529, 0.8678, 0.6149 .Тогда задача линейного программирования (5.19) примет вид110 (ξ1+ ξ3 + ξ8 + ξ10 ) +112 (η2+ η3 + η6 + η7 + η8 + η10 ) → min,Dz ≥ b,ξi ≥ 0,i ∈ I0 ;ηj ≥ 0,−10 ≤ v s (α) ≤ 10,j ∈ J0 ;α ∈ 1 : 3, s ∈ 1 : 4.Решением этой задачи является матрица−0.0061 0.0044−0.0001 −0.0031V0 = −0.0016 −0.0046−0.0062 0.00680.00070.0066,0.00700.0022при этом выполняется неравенство (см.

п. 5.5)Q̂(G0 + V0 ) < F (G0 ) − σ,где Q̂(G0 + V0 ) = 0.5382 и σ = 0.0001.В качестве очередного приближения берём матрицу (см. рис. 6.16)−1.1826 0.1310 3.0208−0.5904 −0.9010 3.4325G1 := G0 + t0 V0 = , 0.9494 −0.0625 3.92840.2624 1.0993 4.5388где t0 = 30 — точка минимума функции F (G0 + tV0 ) при t0 > 0. Значениецелевой функции F (G1 ) равно 0.4391.77Рис. 6.16. Первое приближение G1Повторяем процесс. Формируем индексные множестваI1 = {1, 3, 8, 10},J1 = {8, 10},L18 = {2}, L110 = {3}.Решаем задачу линейного программирования вида (5.19). Решением является матрица0.0004 0.0009V1 = −0.0001−0.0002−0.0036−0.0028−0.0035−0.00270.00340.00010.00040.0015и Q̂(G1 + V1 ) = 0.4392.

Таким образом, G1 — почти локально оптимальнаяматрица при σ = 0.0001.78ДОПОЛНЕНИЕ AДвойственность в линейном программированииA.1. Рассмотрим задачу линейного программированияf (x) := c[N ] × x[N ] → minA[M1 , N ] × x[N ] ≥ b[M1 ],(A.1)A[M2 , N ] × x[N ] = b[M2 ],x[N1 ] ≥ O[N1 ],где N1 ⊂ N . Вектор x = x[N ], удовлетворяющий ограничениям задачи (A.1), называется планом. Множество планов обозначим Ω.

Требуетсянайти оптимальный план — вектор x∗ ∈ Ω, на котором целевая функция f (x) принимает наименьшее на Ω значение (см. например [3, с. 16]).Теорема A.1. Оптимальный план существует тогда и только тогда,когда множество планов Ω непусто и целевая функция f (x) ограниченаснизу на Ω.A.2. Обозначим M = M1 ∪ M2 , N2 = N \ N1 и запишем двойственнуюзадачу линейного программированияg(u) := b[M ] × u[M ] → maxu[M ] × A[M, N1 ] ≤ c[N1 ],u[M ] × A[M, N2 ] = c[N2 ],u[M1 ] ≥ O[M1 ].Множество планов задачи (A.2) обозначим Λ.79(A.2)Первая теорема двойственности. Из существования оптимальногоплана у одной из двойственных задач (A.1), (A.2) следует существованиеоптимального плана и у другой задачи. При этом справедливо соотношение двойственностиmin f (x) = max g(u).x∈Ωu∈ΛСледствие.

Для того чтобы планы x0 ∈ Ω, u0 ∈ Λ двойственных задач были оптимальными, необходимо и достаточно, чтобы выполнялосьравенство f (x0 ) = g(u0 ).A.3. Обычно исследуется пара двойственных задач линейного программирования и результаты формируются одновременно для прямой и двойственной задачи.Теорема A.2. Для того чтобы обе задачи (A.1) и (A.2) имели оптимальные планы, необходимо и достаточно, чтобы множества их планов Ω и Λбыли непустыми.Вторая теорема двойственности. Планы x0 , u0 двойственных задач (A.1)и (A.2) являются оптимальными тогда и только тогда, когда выполняются условия дополнительностиA[i, N ] × x0 [N ] − b[i] × u0 [i] = 0, i ∈ M1 ;x0 [j] × c[j] − u[M ] × A[M, j] = 0, j ∈ N1A.4. Если x0 — оптимальный план задачи (A.1), то всё множество оптимальных планов описывается системой линейных соотношений80c[N ] × x[N ] = c[N ] × x0 [N ],A[M1 , N ] × x[N ] ≥ b[M1 ],(A.3)A[M2 , N ] × x[N ] = b[M2 ],x[N1 ] ≥ O[N1 ].Иногда требуется найти другой оптимальный план, отличный от x0 .

Этоможно сделать, введя подходящую целевую функциюh(x) = d[N ] × x[N ]и минимизируя её при ограничениях (A.3).A.5. Доказательство приведенных в этом Дополнении фактов имеется, например, в [3, глава 1].A.6. Для решения задач линейного программирования разработаны эффективные численные методы. В пакете MATLAB задействованы два метода: метод внутренней точки (Large-Scale Algorithm) и вариант симплексметода (Medium-Scale Algorithm). По умолчанию используется метод внутренней точки. Программа реализована в виде функции Linprog.

Характеристики

Список файлов диссертации