1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 9
Текст из файла (страница 9)
Если симплекс-таблица двойственно допустима, то КОНЕЦ (получено оптимальное решение).Шаг 2. Иначе выбрать ведущий столбец s по правилу: z0 s < 0 ,s Î{1,K, n} .Шаг 3. Если {i | zis > 0, i Î {1, K, m}} ¹ Æ , то выбрать ведущую строку r поправилу:z r0z= min{ i 0 | zis > 0, i Î {1,K, m}} ,z rszisиначе КОНЕЦ (задача неразрешима из-за неограниченности целевойфункции).Шаг 4. Преобразовать симплекс-таблицу, положить s ( r ) := s и перейти нашаг 1.Шаги с 1-го по 4-ый образуют одну итерацию симплекс-метода. Обоснование шага 1 содержится в лемме 4, а шага 3 – в леммах 5 и 6.
Из доказательства леммы 6 также следует, что при элементарном преобразовании сохраняется прямо допустимость симплекс-таблицы.В данном алгоритме не описан 0-ой шаг, а именно, способ построения начальной симплекс-таблицы. Предполагается, что известно начальное б.д.р.Реализация 0-го шага содержится в параграфе 4 при описании двухфазногосимплекс-метода.При выполнении шагов 2 и/или 3 выбор ведущего столбца s и/или ведущей строки r может оказаться неоднозначным.
Существуют разные правилавыбора ведущего элемента. Ограничимся теми правилами, которые приводятк детерминированному алгоритму решения задач ЛП.При выборе ведущего столбца используются следующие способы:а) правило Данцига, которое заключается в выборе s с минимальнымz 0s < 0 ;44б) правило Блэнда, которое состоит в выборе наименьшего s такого, чтоz 0s < 0 .При выборе ведущей строки используются следующие способы:а) правило Блэнда: выбрать строку r с минимальным номером базиснойпеременной s (r ) , удовлетворяющей условиям шага 3;б) лексикографическое правило, описанное в параграфе 3: выбрать строку1r , для которой векторa r лексикографически минимален среди векторовzrsüì 1í a i | zis > 0, i Î {1,K, m}ý .þî zisНе всегда выбор ведущего элемента можно свести к последовательномувыбору сначала ведущего столбца, а затем ведущей строки.
Примером является правило наибольшего улучшения, в котором требуется выбрать такой ведущий элемент, для которого достигается максимальное уменьшение целевойфункции.Следующий пример демонстрирует работу описанного алгоритма.Пример 3. Решить задачуw( x ) = - x1 - 2 x2 - 3 x3 + x4 ® minx1 - 3x2 - x3 - 2 x4 = -4 ,x1 - x2 + x3 = 0 ,x j ³ 0, j = 1,2,3,4 ,взяв в качестве исходного решения точку x = (0,1,1,0)T .Решение. Таблица, соответствующая нулевому шагу, может быть поìæ - 3 öæ - 1ö üстроена следующим образом.
Так как столбцы { A2 , A3} = íçç ÷÷çç ÷÷ ý линейîè - 1 øè 1 ø þно независимы, то имеем базис B 0 = ( A2 , A3 ) . Выразим базисные переменныеx2 и x3 из ограничений равенств через небазисные переменные x1 и x4 . Получим:x2 - 1 / 2 x1 + 1 / 2 x4 = 1 ,x3 + 1 / 2 x1 + 1 / 2 x4 = 1 .Исключим базисные переменные из целевой функции, выразив ее только через небазисные переменные:w( x) = - x1 - 2(1 / 2 x1 - 1 / 2 x4 + 1) - 3(-1 / 2 x1 - 1 / 2 x4 + 1) + x4 == -5 - 1 / 2 x1 + 7 / 2 x4 .Представим это равенство в удобном виде:- w - 1 / 2 x1 + 7 / 2 x2 = 5 .Симплекс-таблица имеет такой исходный вид:45-wx2x3511x1-1/2-1/21/2x2010x3001x47/21/21/2Базис не является двойственно допустимым, так как элемент z01 = -1 / 2отрицателен. Рассматриваемый базис невырожденый ( z10 = 1 , z20 = 1 ), и,следовательно, значение целевой функции можно улучшить.
Взяв в качествеведущего первый столбец ( s = 1 ), находим ведущую строку: r = 2 , так кактолько z21 = 1 / 2 > 0 . Преобразовав исходную таблицу с ведущим элементомz21 , получим новый базис B1 = ( A1, A2 ) и таблицу-wx2x3622x1001x2010x3112x4411Так как таблица является двойственно допустимой, то базис B1 оптималени в соответствии с таблицей получаем, что x * = ( 2,2,0,0)T и w( x * ) = -6 , таккак x * = ( z20 , z10 ,0,0) T , w( x* ) = - z00 .Обоснование конечности симплекс-метода зависит от того, является лизадача вырожденной или невырожденной, а также от используемого в алгоритме способа выбора ведущего элемента.
В прямо допустимой симплекстаблице всегда выполняются строгие неравенства zi 0 > 0 , i = 1, K , m , а в силувыбора ведущего элемента справедливо z 0s < 0 , z rs > 0 . Поэтому при элементарном преобразовании таблицы элемент z 00 обязательно увеличивается,то есть значение целевой функции при переходе к новому б.д.р. строгоуменьшается. Это гарантирует неповторяемость встречающихся в ходе алгоритма базисов. И, как следствие, конечность числа итераций. Очевидно, чтоданный вывод не зависит от используемого способа выбора ведущего элемента.В вырожденной задаче величина z r 0 может оказаться равной 0.
В лемме 6отмечалось, что в этом случае элементарное преобразование не приводит кновой вершине, а лишь изменяет форму представления исходной вершины,то есть ее базис. При этом нельзя исключить, что цепочка из нескольких последовательных тривиальных преобразований может привести к уже встречавшемуся базису, то есть алгоритм будет неограниченное число раз повторять данный цикл преобразований. Такое явление называется зацикливанием.Этого можно избежать, используя правило Блэнда, а также лексикографиче-46ское правило выбора ведущей строки. Этот вариант симплекс-метода описывается в третьем параграфе.
Там же приводится пример, демонстрирующийзацикливание. Правила Данцига и наибольшего улучшения зацикливание неустраняют.§ 2. Модифицированный симплекс-методВ описанной в предыдущем параграфе реализации симплекс-метода накаждой итерации пересчитывается вся симплекс-таблица размера(m + 1) ´ (n + 1) . Однако так как она определяется выбором базиса, то при выполнении алгоритма нет необходимости в информации обо всей таблице.
Если число столбцов в матрице ограничений значительно больше числа еестрок, то можно понизить трудоемкость симплекс-метода, храня и преобразуя матрицу размера (m + 1) ´ ( m + 1) . В литературе [7] этот алгоритм известенпод названием модифицированного симплекс-метода или алгоритма с обратной матрицей.Пусть B – произвольный базис канонической задачи (1)-(3),æ 0 cB c N öA= çç÷÷ – расширенная матрица условий задачи, тогда симплексèb B N øтаблица T , соответствующая базису B , имеет видæ - c B -1b 0 c - c B -1N öBNB÷.T =çç÷-1-1B Nè B b EøЛегко проверить, чтоT = MA ,(11)æ1 - c B B -1 ö÷ – матрица, обратная к расширенной базисной матрицегде M = çç 0 B -1÷èøæ1 c öB = çç B ÷÷ .è0 B øПусть симплекс-таблица T ¢ получена в результате элементарного преобразования симплекс-таблицы T по следующим формулам:zis z rjzij¢ = zij , i¹r,z rszij¢ =zrjzrs47, i=r.Введем обозначения mir = - zis / zrs , m rr = 1 / zrs .
Тогда T ¢ = M rsT , гдеæ1 0 K m 0 r K 0 öç÷ç 0 1 K m1r K 0 ÷M rs = ç.MMMM ÷ç÷ç 0 0 K m K1 ÷mrèøИтак, T ¢ = M rsT = M rs MA = M ¢A , где M ¢ = M rs M . Следовательно, достаточно пересчитывать на каждой итерации матрицу Mразмера(m + 1) ´ (m + 1) и хранить матрицу A . Требуемые элементы симплекстаблицы вычисляются по формуле (11) по мере необходимости на шагах 1-3симплекс-метода.§ 3. Лексикографический прямой симплекс-методВ первом параграфе было отмечено, что в вырожденных задачах при детерминированном правиле выбора ведущего элемента может наблюдатьсязацикливание алгоритма симплекс-метода, то есть появляется возможностьвозвращения к базису, который уже встречался.
Приведем пример, иллюстрирующий эту ситуацию.Пример 4. Решить задачуw( x ) = - x 3 + x 4 - x5 + x 6 ® minx1 + x 3 - 2 x 4 - 3 x 5 +4 x6 = 0,x 2 + 4 x3 - 3x 4 - 2 x5 + x 6 = 0,x3 + x 4 + x5 + x 6 + x7 = 1,x j ³ 0, j = 1,2, K,7.Решение. Нетрудно заметить, что в качестве исходного можно выбрать базис B 0 = ( A1 , A2 , A7 ) , при этом имеем базисное допустимое решение x = (0,0,0,0,0,0,1)T . Данное решение, очевидно, вырожденное.
Так какбазисные переменные x1 , x 2 и x7 не содержатся в целевой функции и равенства имеют требуемый для построения симплекс-таблицы вид, то сразу получаем симплекс-таблицу:-wx1x2x70001x10100x20010x3-114148x41-2-31x5-1-3-21x61411x70001Выбираем s = 3 , r = 1 и переходим к базису B1 = ( A2 , A3 , A7 ) , при этомбазисное решение не изменится, так как z 01 = 0 :-wx3x2x70001x111-4-1x20010x30100x4-1-253x5-4-3104x654-15-3x70001Выбираем =r 2 и переходим к базису B 2 = ( A3 , A4 , A7 ) .
Базисноеs 4, =решение вновь не изменится:-wx3x4x70001Здесь можно взятьтаблица:-wx5x4x70001x11/5-3/5-4/57/5x21/52/51/5-3/5x30100x40010x5-212-2x62-2-36x70001s = 5 , r = 1 . Базису B 3 = ( A4 , A5 , A7 ) соответствуетx1x2-1-3/52/51/512/5-3/51/5x321-22x40010x50100x6-2-212x70001с тем же базисным решением.Теперь возьмем s = 6 , r = 2 . Получим базис B 4 = ( A5 , A6 , A7 ) и таблицу-wx5x6x70001x1-1/51/52/5-3/5x2-1/5-4/5-3/57/5x3-2-3-26Базисное решение и здесь не изменилось.49x4221-2x50100x60010x70001Пусть теперь s = 1 , r = 1 . Новый базис B 5 = ( A1 , A6 , A7 ) с соответствующей таблицей и тем же решением:-wx1x6x70001x10100x 2 x3-1 -5-4 -1514-1 -3x4410-34x515-23x60010x70001Выбрав s = 2 , r = 2 , придем к базису B 6 = ( A1 , A2 , A7 ) = B 0 , то есть произошел возврат к исходному базису.
Решение получить не удалось.Для того чтобы гарантировать конечность симплекс-метода в вырожденных задачах, необходимо исключить возможность подобного зацикливания.Таким свойством обладает упоминавшееся выше правило Блэнда. Также зацикливание можно предотвратить при использовании лексикографическойпроцедуры выбора ведущей строки.Определение 10. Ненулевой вектор a = ( z0 , z1, K, zn ) лексикографическибольше нуля ( a f 0 ), если первая отличная от нуля компонента положительна, то есть z p > 0 , где p = min{i | i Î {1,K, n}, zi ¹ 0} .Пусть a ¢ , a ¢¢ Î R n +1 . Говорят, что вектор a ¢ лексикографически большевектора a ¢¢ ( a ¢ f a ¢¢ ), если a ¢ - a ¢¢ f 0 . Тем самым на R n +1 определено отношение линейного порядка, так что в любой конечной совокупности векторов {a i } имеется лексикографически минимальный вектор, обозначаемыйlex min{a i } .Определение 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
