1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 8
Текст из файла (страница 8)
Если | S ¢ |= n - m - 1 , то получим грань размерности 1 , то есть ограниченное или неограниченное ребро.38Из определения б.д.р. следует, что x единственное решение системыEx B + B -1Nx N = B -1b ³ 0 , x N = 0 .Пусть s Î S ¢ – произвольная небазисная переменная. Тогда следующаясистема уравнений и неравенств:Ex B + B -1Nx N = B -1b ,x j = 0 , j ÎS¢ \ s ,x B ³ 0, xs ³ 0 ,определяет ребро множества Q . Перепишем эту систему в эквивалентномвиде:Ex B + B -1 As x s = B -1b = x B , x B ³ 0, xs ³ 0 .Если переменную xs рассматривать как параметр, то данная система эквивалентна следующей:Ex B = x B - ( B -1 As )t , x B ³ 0 , t ³ 0 .Таким образом, из этого представления системы уравнений следует, что коэффициенты замещения симплекс-таблицы, отвечающие небазисной переменной с номером s , образуют направляющий вектор ребра множества Q ,выходящего из вершины x .Чтобы выяснить является ли это ребро конечным или бесконечным, рассмотрим следующее параметризованное семейство векторов x (t ) , t ³ 0 :xs (i ) ( t ) = xs (i ) - zis t ,üïx s (t ) = t ,ýx j ( t ) = 0, j Î S ¢ \ s.
ïþ(9)Будем говорить, что вектор x (t ) получен элементарным преобразованиемб.д.р. x , если выполнено (9) и t ³ 0 .В зависимости от знака коэффициентов замещения zis возможны следующие варианты.1. zis £ 0 , i = 1, K, m . Тогда из соотношений (9) следует, что для любогоt ³ 0 вектор x (t ) ³ 0 и, следовательно, ребро, выходящее из вершины x снаправляющим вектором B -1 As = ( z1s ,K, zms )T , является неограниченным.2. Существуют положительные элементы среди коэффициентов замещения s -го столбца симплекс-таблицы.
Очевидно, что в данном случае векторыx (t ) , полученные элементарным преобразованием x , имеют неотрицательные компоненты лишь тогда, когда выполняются условия: 0 £ t £ t , гдеxs ( i )t = min. Это означает, что в рассматриваемом случае соответствующееzis >0 zisребро конечно и имеет длину t .39Таким образом, параметризованное семейство векторов (9) при измененииt от 0 до бесконечности (в случае 1) и от 0 до t (в случае 2), описывает движение из вершины x по ребру.Вернемся к анализу условий У2 и У3. Условие У2 рассматривается в лемме 5, У3 – в лемме 6.Лемма 5 (о неразрешимости). Если оценка замещения z0s < 0 , s Î S ¢ , икоэффициенты замещения zis £ 0 , i = 1, K, m , то в задаче (1)-(3) не существует оптимального решения.Доказательство.
Из условия леммы следует, что ребро, выходящее извершины x и образованное векторами x (t ) , t ³ 0 , бесконечно. Тогда из (7)имеем w( x (t )) = - z00 + z0 st ® -¥ при t ® ¥ , то есть целевая функция неограниченна снизу. Из критерия разрешимости следует, что в задаче нет оптимальных решений. ▄Лемма 6 (о существовании лучшей вершины). Если оценка замещенияz 0 s < 0 и существуют базисные переменные с коэффициентами замещенияz is > 0 , то в задаче (1)-(3) существует б.д.р.
с меньшим значением целевойфункции.Доказательство. В данном случае ребро, выходящее из вершины x и образованное векторами x(t ) , 0 £ t £ t , является конечным. Предположим, чтоего длина t > 0 . Пусть r – индекс базисной переменной такой, чтоxs ( r ) z r0üìzОчевидно,чтодля== min í i 0 | zis > 0, i Î {1, K, m}ý .t=z rsz rsþî zisi Î {1,K, m} иt£tвыполняются неравенстваxs ( i ) ( t ) = xs (i ) - zis t ³ 0 ,xs ( r ) (t ) = 0 , и xs ( r ) (t ) < 0 для t > t .Покажем, что вектор x (t ) – б.д.р. Действительно, по определению коэф-фициентов замещения ( z1s , K, zms )T = B -1 As .
То есть As = B ( z1s , K, zms )T =m= å zis As (i ) .i =1Так как в этом представлении вектора As через базисные векторы величина zrs отлична от нуля, то замена столбца As (r ) в базисной матрице B настолбецAsприводиткB ¢ [ As (1) , K, As ( r -1) , As , As ( r +1) , K, As ( m ) ] .=40невырожденнойматрицеЧтобы проверить это утверждение, допустим противное, то есть пустьматрица B¢ вырождена.
Тогда существует такая нетривиальная линейнаякомбинация столбцов матрицы B¢r -1mi =1i = r +1å b i As (i) + å b i As (i ) + b s As = 0 ,в которой коэффициент b s ¹ 0 . Так как иначе из-за нетривиальности линейной комбинации следовала бы линейная зависимость столбцов матрицы B ,что противоречило бы ее невырожденности.mæ b öТакимобразом,Следовательно,A=å çç - b i ÷÷ As (=i ) å zis As (i ) .ssøi ¹ rè=i 1æb ö÷÷ As ( i ) + z rs A=s 0 .
Так как zrs ¹ 0 , то получаем нетривиальнуюsøi ¹r èлинейную комбинацию столбцов матрицы B . Получили противоречие. Следовательно, предположение неверно, и матрица B¢ невырождена.Ранее было показано, что компоненты вектора x (t ) неотрицательны. Сучетом невырожденности матрицы B¢ получаем, что x (t ) – б.д.р.
и B¢ егобазисная матрица. Так как w( x (t )) = - z00 + z0 s t < - z00 , то x (t ) – искомоеб.д.р. с меньшим значением целевой функции.Рассмотрим случай t = 0 . Это означает, что ребро имеет нулевую длину,при движении по которому не происходит смены вершины. Но, как и в предыдущем случае, происходит смена базиса. В силу того, что zrs > 0 , тривиальное элементарное преобразование б.д.р. x в x (t ) = x (0) = x приводит кзамене базиса B на B¢ .▄å çç zis + b iПусть B¢ – базис, который получается из базиса B заменой столбца As (r )на столбец As , s Î S ¢ .
В этом случае говорят, что базис B¢ результат элементарного преобразования базиса B относительно вектора As .Итак, теперь идею алгоритма решения задачи (1)-(3) содержательно можно описать следующим образом. Найдем начальное б.д.р. и проверим какоеиз трех условий выполняется.
Если реализовался первый случай, то в соответствии с леммой 4 это решение оптимально. Во втором случае, как установлено в лемме 5, задача неразрешима. В обоих случаях алгоритм завершаетсвою работу. И, наконец, при выполнении последнего условия, когда известно, что текущая вершина не оптимальна, при помощи элементарного преобразования получаем новое б.д.р., на котором значение целевой функции нехуже.
Если элементарное преобразование нетривиально, то получим соседнюю вершину, на которой значение целевой функции строго меньше, чем наисходной вершине. В противном случае вершина не меняется. Изменяетсятолько способ ее представления, то есть базис. В любом случае решение за-41дачи сводится к анализу новой симплекс-таблицы T ¢ , которую можно былобы построить по тем же правилам, что и исходную таблицу T .Однако существует более простой способ получения таблицы T ¢ .
Вспомним, что исходная таблица состоит из коэффициентов формы (7)-(8), диагональной относительно базисных переменных и переменной ( - w ), и в новомнаборе базисных переменных присутствует переменная xs , заменяющая переменную xs (r ) . То есть для получения новой таблицы достаточно выполнить один шаг процедуры Гаусса-Жордана, чтобы исключить xs из всех,кроме одного, уравнений системы (7)-(8), определяемой старым базисом. Дляэтого используем уравнение системы с номером r , как единственное уравнение, содержащее исключаемую из базиса переменную xs (r ) .
Разделим этустроку на величину z rs > 0 , чтобы в позиции ( r, s) симплекс-таблицы была 1.Затем к каждой строке с номером i ¹ r прибавим модифицированную r -уюстроку, умноженную на величину ( - zis ) . Выполнив указанные действия, получим симплекс-таблицу T ¢ , в которой переменной x s соответствует единичный столбец. Будем говорить, что симплекс-таблица T ¢ получена элементарным преобразованием симплекс-таблицы T относительно вектораAs .
Таким образом вектор-строки a i = ( zi 0 , zi1,K, zin ) , i = 0, K, m , таблицы¢ ) , i = 0, K, m , таблицыT преобразуются в вектор-строки a i¢ = ( zi¢0 , zi¢1,K, zinT ¢ по следующему правилу:zisìïai¢ = ai - z a r , i ¹ r,ïrs(10)í1ïa r¢ =ar .ïîzrsПри этом r -ая строка, s -ый столбец и элемент zrs называются ведущими.Элементы симплекс-таблицы пересчитываются по формулам:zis zrjì, i ¹ r,ï zij¢ = zij z rsïíï z¢ = z rj .ïî rj z rsВ качестве иллюстрации лемм 5 и 6 рассмотрим следующий пример.Пример 2. Исследовать на оптимальность решение x = ( 0,1,0,2,1)T задачиw( x ) = - x1 - x2 ® min- x1 + x2 + x3 = 1 ,x1 - 2 x 2 + x 4 = 0 ,- x1 + 2 x2 + x5 = 3 ,x j ³ 0, j = 1, 2,3, 4,5 .42Решение.Вэтомпримерестолбцы( A2 , A4 , A5 ) == ((1,-2,2)T , (0,1,0)T , (0,0,1)T ) – линейно независимы.
Следовательно, x – базисное допустимое решение с базисными переменными x2 = 1 , x4 = 2 , x5 = 1 .Построим соответствующую решению x симплекс-таблицу. Небазисные переменные здесь x1 и x3 . Следовательно, из первого ограничения-равенствасразу получаемx2 = 1 + x1 - x3 .Подставив x2 , выраженное через небазисные переменные, во второе итретье ограничения-равенства, придем к соотношениям- x1 + x2 + x3 = 1 ,- x1 + 2 x3 + x4 = 2 ,x1 - 2 x2 + x5 = 1 .Осталось исключить базисные переменные из целевой функции:w( x ) = - x1 - x2 = - x1 - (1 + x1 - x3 ) = -1 - 2 x1 + x3 .Таким образом, приходим к равенству- w - 2 x1 + x3 = 1 .Симплекс-таблица принимает вид-wx2x4x51121x1-2-1-11x20100x3112-2x40010x50001Базис не является вырожденным, так как вектор ( z10 , z20 , z30 )T = (1,2,1)Tне содержит нулевых элементов.
Таблица прямо допустима, но не являетсядвойственно допустимой: z10 = -2 < 0 . И так как z31 = 1 > 0 , то согласно утверждению леммы 6 существует базисное допустимое решение, которое даетменьшее значение целевой функции, чем w( x ) = - z00 = -1 . Действительно,так как z31 ¹ 0 , то можно преобразовать базис, выведя из него столбец A5 изаменив его на столбец A1 , то есть получить базис ( A1, A2 , A4 ) .Согласно формулам элементарного преобразования базиса, получимтаблицу-wx2x4x13231x10001x2010043x3-3-10-2x40010x52111¢ = -3 , гдезначением целевой функцииw( x ¢)= - z00¢ - 3 < 0 и в третьем столбце ( j = 3) нет положиx=¢ (1,2,0,3,0) T .
Так как z03тельных элементов, то из леммы 5 следует неограниченность снизу целевойфункции w(x) на рассматриваемом множестве X .сменьшим1.3 Алгоритм симплекс-методаСформулируем симплекс-метод в виде следующей последовательностишагов.Шаг 0. Построить симплекс-таблицу, соответствующую заданному базисному допустимому решению, таблица будет прямо допустимой.Шаг 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
