1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 7
Текст из файла (страница 7)
Тогда в A имеется mлинейно независимых столбцов. Система линейных уравнений (2) совместна32и неизбыточна. Обозначим через A j = ( a1 j ,K, amj )T , j Î J , столбцы матрицы ограничений.Определение 1. Любой набор As (1) , K, As ( m ) из m линейно независимыхстолбцов называется базисом, как и матрица B = [ As (1) , K, As ( n) ] , составленная из этих столбцов.Перестановкой столбцов матрицу A можно привести к виду A = [ B, N ] ,где N – подматрица, составленная из остальных столбцов матрицы A . Поступив аналогичным образом с вектором x , получим представлениеæx öx = çç B ÷÷ , где x B = ( xs (1) ,K, xs ( m ) )T .è xN øОпределение 2. Переменные x j , являющиеся компонентами вектора x B(соответственно, x N ), называются базисными (соответственно, небазисными).Обозначим через S множество номеров базисных переменных, а через S ¢– множество номеров небазисных переменных.Определение 3.
Решение системы (2)æ x B ö æ B -1b ö÷x = çç ÷÷ = çç÷è xN ø è 0 øназывается базисным решением, соответствующим базису B .Лемма 1. Вектор x – базисное решение системы (2) тогда и только тогда,когда множество столбцов A j | x j ¹ 0, j Î J матрицы A линейно незави-{}симо.Определение 4. Базисное решение называется невырожденным, если унего ровно m ненулевых компонент. В противном случае базисное решениеназывается вырожденным.Определение 5.
Задача (1)-(3) называется невырожденной, если все ее базисные решения невырожденые. В ином случае задача будет вырожденной.Число базисных решений конечно и не превосходит числа Cnm . Каждомубазису соответствует одно базисное решение, но базисному решению можетсоответствовать несколько базисов.33Определение 6. Базисным допустимым решением (б.д.р.) называется любой элемент множества Q = {x | Ax = b, x ³ 0}, являющийся базисным решением системы Ax = b .Ясно, что решение, соответствующее базису B , является б.д.р. тогда итолько тогда, когда B -1b ³ 0 .Приведем ряд утверждений, касающихся разрешимости задач ЛП, существования допустимых и оптимальных базисных решений.Теорема 1.
Вектор x является базисным допустимым решением тогда итолько тогда, когда x есть крайняя точка множества Q .Теорема 2 (критерий разрешимости). Задача (1)-(3) разрешима тогда итолько тогда, когда Q ¹ Æ и целевая функция w(x ) ограничена снизу на множестве X .Лемма 2. Если Q ¹ Æ , то существует базисное допустимое решение.Лемма 3. Если задача ЛП разрешима, то существует оптимальное базисное допустимое решение.В следующем примере показано, что в задаче ЛП все б.д.р. могут быть вырождеными.Пример 1.
Найти все базисы системы равенств и соответствующие им базисные решения:x1 + x2 + x3 + x4 = 1 ,x1 - x2 + x3 - x4 = 1 ,x j ³ 0 , j = 1,2,3,4 .Решение. Рассмотрим множество столбцов {A1, A2 }, они линейно незави-æ 1 1ö÷÷ – базис. Набор столбцовсимы; отметим, что здесь m = 2 . Значит, B = ççè 1 - 1ø{A1, A3} базисом не является, так как очевидно, что эти столбцы линейно зависимы. Аналогично устанавливаем, что {A1, A4 }, {A2 , A3}, {A3 , A4 } – базисы,а {A2 , A4 } – не базис.
Так как в данном примере C42 = 6 , то рассмотрены всеслучаи.Таким образом, {A1, A2 }, {A1, A4 }, {A2 , A3}, {A3 , A4 } – все базисы даннойсистемы равенств.Найдем теперь все базисные решения. Согласно введенным выше обозна-34чениям система (2) при выбранном базисе B может быть записана в такомвиде:Bx B + Nx N = b .Откуда, в силу существования обратной матрицы B -1 , получаем, чтоx B = B -1b - B -1Nx N .x B=B -1b ,Положивx N= 0 ,получимбазисноерешениеxN= 0 .æx öОчевидно, что базисное решение çç B ÷÷ можно найти, положив в (2)è xN øx N = 0 , а затем разрешив получившуюся систему уравнений относительноæ1 öx B любым удобным способом.
Если B = ( A1, A2 ) , то x B = çç ÷÷ . Значит,è 0øx = (1,0,0,0)T – базисное решение.Последовательно находим, что вектор x = (1,0,0,0)T соответствует базису{A1, A4 }, a векторx = (0,0,1,0)T – базисам {A2 , A3 } и { A3 , A4 } .Таким образом, система имеет четыре базиса, но только два базисных решения, каждому из которых можно поставить в соответствие по два базиса.Отметим, что для всех базисных решений выполнено условие x ³ 0 , то естьэто базисные допустимые решения.1.2.
Элементарные преобразования. Симплекс-таблицыПусть x – базисно-допустимое решение, B = [ As (1) ,K, As ( m ) ] – соответствующая базисная матрица. Умножим ограничение (2) на матрицу B -1 иполучим(4)Ex B + B -1Nx N = B -1b ,Ex B = B -1b - B -1Nx N ,(5)используя это равенство, исключим базисные переменные из целевой функции. Для этого подставим в (1) представление базисных переменных черезнебазисные переменные (5), приведем подобные и, введя новую переменнуюw , запишем целевую функцию в виде уравнениягдеx = ( xB , xN ) ,w = c B B -1b + ( c N - cB B -1N ) x N ,x B = ( xs (1) ,K, xs ( m) ) – базисные(6)переменные, аx N = ( x j ) jÎS ¢ – небазисные переменные.Из приведенных рассуждений следует, что если x – допустимое решениеканонической задачи, то (c, x ) = w тогда и только тогда, когда вектор (w, x )35является решением системы уравнений и неравенств (3), (4), (6). Запишемсистему уравнений (5), (6) в матричном видеwæ - 1 0 c N - B -1N öæç ö÷ æ - c B B -1b öç÷ x =ç÷.ç B÷ ç-1-1 ÷ç 0 E÷B N øç x ÷ è B b øèè NøВведем новые обозначения:z 00 = - c B B -1b = - w( x ) – значение целевой функции на текущем б.д.р., взятое с обратным знаком;z0 j = c j - cB B -1 A j , j = 1, K, n , – оценки замещения;zi 0 , i = 1, K, m , – значения базисных компонент текущего б.д.р., то есть( z10 , K, zm 0 )T = B -1b ;zij , i = 1, K, m , j = 1, K, n , – коэффициенты замещения, которые удовлетво-ряют условиям ( z1 j ,K, zmj )T = B -1 A j , j = 1, K, n .Перепишем систему уравнений (5), (6) в эквивалентном виде:- w + å z0 j x j = z00 ,(7)jÎS ¢xs ( i ) +å zij x j = zi 0 , i = 1,K, m,(8)jÎS ¢где S ¢ = J \ {s (1), K, s ( m )}.
Коэффициенты этой системы определяют симплекс-таблицу.x1KxjKxn-wz00z 01Kz0 jKz 0nxs (1)z10Kzi 0Kz m0z11Kzi1Kzm1KKKKKz1 jKKKKKz1nKzinKzmn.xs (i ).xs (m )KzijKzmjСимволы переменных слева от таблицы и над ней используются для повышения ее информативности.Из вида системы уравнений (8) следует, что столбец, отвечающий переменной с номером s (i ) , i Î {1,K, m} , является единичным вектором, имеющим 1 в i -ой строке и 0 в остальных строках.
Аналогично из (7) следует, чтооценки замещения базисных переменных равны нулю. Таким образом, еслиs (i ) = i , i = 1, K, m , то симплекс-таблица имеет вид36-wx1.xi.xmБазисноеx101K0z00z10Kzi 0Kzm 00решение,KKKKKKKKxi00K1K0KKKKKKxm00K0K1соответствующееxm +1z0m +1z1m +1Kzim +1Kzmm +1базисуKKKKKKKB,xnz 0nz1nKzinKzmnимеетвидTx B= ( z10 , z20 , K, z m 0 ) , x N= 0 , а целевая функция w на данном решениипринимает значение w( x ) = - z00 . Величины zi 0 неотрицательные.Определение 7.
Симплекс-таблица называется прямо допустимой, еслиzi 0 ³ 0, i = 1, K, m . Базис B , которому соответствует эта таблица, также называется прямо допустимым.Определение 8. Симплекс-таблица называется двойственно допустимой,если z0 j ³ 0, j = 1, K, n . Базис B , которому соответствует эта таблица, такженазывается двойственно допустимым.Назовем симплекс-таблицу оптимальной, если она одновременно прямо идвойственно допустима.В зависимости от знаков величин zij , z j 0 , j Î S ¢ = J \ {s (1),K, s ( m )} ,i = 1, K, m , выполняется одно из условий:У1. z0 j ³ 0 , j Î S ¢ ,У2. существует s Î S ¢ такой, что z 0s < 0 и zis £ 0 , i = 1, K, m ,У3.
существует s Î S ¢ такой, что z 0s < 0 и существует r такой, чтоz rs > 0 , 1 £ r £ m .Знаки оценок замещения z0 j , j = 1, K, n , определяют, является ли текущее б.д.р. оптимальным решением.Лемма 4 (признак оптимальности). Если симплекс-таблица прямо идвойственно допустима, то текущее базисное допустимое решение x является оптимальным решением задачи (1)-(3).Доказательство. Пусть x – произвольное допустимое решение. Так какz0 j ³ 0иx j ³ 0,j Î S¢ ,тоиз(7)следуетw( x ) = - z00 +å z 0 j x j ³ - z00 = w( x ) .
▄jÎS ¢37Пример 2. Исследовать на оптимальность решение x = (0,0,1,1)T задачиw( x ) = x1 + x2 - 2 x3 - 3x4 ® min2 x1 - x2 + x3 = 1 ,- x1 + 2 x 2 + x 4 = 1 ,x j ³ 0, j = 1,2,3,4 .ìæ 1 öæ 0 ö üРешение. Множество столбцов { A j | x j > 0} = { A3 , A4 } = íçç ÷÷çç ÷÷ ý матрицыîè 0 øè 1 ø þA линейно независимо. Так как матрица B единичная, то для построениясимплекс-таблицы, соответствующей этому базису, достаточно исключитьбазисные переменные x3 и x 4 из целевой функции. Получимw( x ) = x1 + x 2 - 2(1 - 2 x1 + x 2 ) - 3(1 + x1 - 2 x2 ) = -5 + 2 x1 + 5x 2 .Следовательно, равенства принимают вид- w + 2 x1 + 5 x2 = 5 ,x3 + 2 x1 - x 2 = 1 ,x 4 - x1 + 2 x 2 = 1 .И симплекс-таблица может быть представлена так-wx3x4511x122-1x 2 x35 0-1 12 0x4001Так как таблица является прямо ( z10 = 1 , z20 = 1 ) и двойственно ( z01 = 2 ,z 02 = 5 , z 03 = 0 , z 04 = 0 ) допустимой, то базисное допустимое решение x –оптимальное решение.
Заметим, что здесь s (1) = 3 , s ( 2) = 4 .Для анализа условий У1 и У2 введем параметризованное семейство векторов x (t ) , t ³ 0 , такое, что xs ( i ) ( t ) = xs ( i ) - zis t, i = 1, K, m , x s (t ) = t ,x j ( t ) = 0 , j Î S ¢ \ s . Здесь s Î S ¢ .Определение 9. Множество решений системы уравнений и неравенствAx = b , x j = 0 , j Î G ¢ , x j ³ 0, j Î G , G ¢ È G = {1, K, n} , G ¢ Ç G = Æ ,называется гранью множества допустимых решений (2)-(3) размерности( n - m - | G ¢ | ), здесь ( m + | G ¢ | ) – ранг системы.Так как x – базисно допустимое решение, то, полагая G ¢ = S ¢ , получим,что x – грань размерности 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
