1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 10
Текст из файла (страница 10)
Симплекс-таблица называется нормальной, если ее строки a i = ( zi 0 , zi1 , K, zin ) , i = 1, K , m , лексикографически положительны.Следующая лемма очевидна.Лемма 7. Любую прямо допустимую симплекс-таблицу можно преобразовать в нормальную путем перенумерации переменных и соответствующейперестановкой столбцов.Из определения 11 следует, что нормальная симплекс-таблица являетсяпрямо допустимой.50Отличия лексикографического прямого симплекс-метода от симплексметода, описанного в параграфе 1, касаются только 0 -го и 3 -го шагов, остальные шаги остаются без изменений:Шаг 0'. Начать с нормальной симплекс-таблицы.Шаг 3'. Если {i | zis > 0, i Î {1, K, m}} ¹ Æ , то выбрать ведущую строку rпо правилу:üì 11a r = lex min í a i | zis > 0, i Î {1, K, m}ý ,z rsþî zisиначе КОНЕЦ (задача неразрешима).Элементарное преобразование базиса при этом сохраняет нормальностьсимплекс-таблицы.
Действительно, строка a r¢ остается лексикографическиположительной, так как она получается умножением лексикографически положительного вектора a r на положительное число 1 / z sr . Для доказательства лексикографической положительности остальных строк a i¢ , i ¹ r ,i = 1, K , m , рассмотрим два случая:zа) если zis £ 0 , то a i¢ = a i - is a r ≽ a i f 0 ;z rsб) если zis > 0 , то в соответствии с правилом выбора ведущей строки (шагé 1ù111ai fa r , следовательно, a i¢ = zis ê a i ar ú f 0 .3') имеемzisz rsz rs ûë zisЛемма 8. В результате одной итерации лексикографического симплексметода происходит лексикографическое возрастание нулевой строкиa 0 = ( z00 , z01,K, z0n ) .Из нормальности симплекс-таблиц следует, что на каждой итерации ведущая строка r лексикографически положительна.
С учетом неравенствz0 s < 0 и zrs > 0 имеемæz öa 0 - çç 0 s ÷÷a r f a 0 .è zrs øЛемма 9. В ходе работы лексикографического симплекс-метода базисы неповторяются, что гарантирует его конечность.Из леммы 8 следует, что последовательность нулевых строк симплекстаблиц является лексикографически возрастающей. Поэтому в ходе работыалгоритма симплекс-таблицы, а значит и базисы, не повторяются, что гарантирует конечность лексикографического симплекс-метода.51Пример 5. Рассмотрим пример 4, на котором была продемонстрированавозможность зацикливания обычного симплекс-метода. Выбрав базисB 0 = ( A1, A2 , A7 ) , получим исходную таблицу, которая является нормальной:-wx1x2x7Пусть0001x10100по-прежнемуx20010x3-1141x41-2-31=s 3.x5-1-3-21Здесьx61411x70001=a 1 (0,1,0,1,-2, -3, 4,0) ,=a 2 (0,0,1, 4,-3,-2,1,0) и a 3 = (1,0,0,1,1,1,1,1) .Так как a 3 - a 1 = (1, -1, K) f 0 и a 3 - a 2 / z23 = (1,0,K) f 0 , то a 3 f a 1 иa 3 f a 2 / z23 .
Таким образом, нужно сравнить a 1 и a 2 / z23 . Имеем1a 1 - a 2 = (0,1,K) f 0 .4iЗначит, lex min{a / zi 3 | zi 3 > 0} = a 2 / z23 и r = 2 .Преобразовав симплекс-таблицу (перейдя к базису B1 = ( A1, A3 , A7 ) ), получим-wx1x3x70001x10100x21/4-1/41/4-1/4x30010x41/4-5/4-3/47/4x5-6/4-10/4-2/46/4x65/415/41/43/4x70001Здесь ведущий элемент определяется однозначно: s = 5 , r = 3 .
Переходя кбазису B 2 = ( A1, A3 , A5 ) , преобразуем симплекс-таблицу. В результате перейдем к таблице (ненужные элементы опущены):-wx1x3x515/31/32/3x1 x 20 0100x3 x 4 x5 x6 x70 2 0 2 1001001Таблица является прямо и двойственно допустимой. Оптимальное решениеполучено за две итерации. При этом x * = (5 / 3,0,1 / 3,0,2 / 3,0,0)T , w( x * ) = -1 .52§ 4. Метод искусственного базисаВ примерах, рассмотренных ранее, предполагалось, что либо задан исходный допустимый базис, либо было известно базисное допустимое решение.В этом параграфе рассматривается общий метод решения задачи ЛП в канонической форме, позволяющий на первом шаге найти базисное допустимоерешение или установить, что Q = Æ , а на втором шаге найти оптимальныйбазис и соответствующее ему решение, либо установить неразрешимость задачи из-за неограниченности целевой функции. При этом не предполагается,что ранг матрицы A равен m .Без ограничения общности можно считать, что система ограниченийравенств Ax = b записана таким образом, что b ³ 0 .
Этого можно добиться,умножая нужные строки на - 1 .Тогда метод искусственного базиса можно представить в виде следующих шагов.Шаг 0. Построить симплекс-таблицу для задачиmx = å xn + i ® min(12)ai x + xn +i = bi , i = 1,K, m,x j ³ 0, j = 1, K, n + m,(13)(14)i =1выбрав в качестве базиса B = ( An +i , K, An + m ) . Здесь ai – это i -ая строка,i = 1, K , m , матрицы A . Так как матрица B единичная, то для построениятаблицы достаточно в целевой функции x выразить базисные переменные(искусственный базис) xn +i , i = 1, K , m , через небазисные переменные x j ,j = 1, K, n , используя ограничения (13).
В результате получимmx = å (bi - ai x) .i =1Следовательно,mmi =1i =1z00 = - å bi , а z0 j = - å aij , j = 1, K, n , z0 j = 0 , j = n + 1, K , n + m .При этом симплекс-таблица прямо допустима, а базисное допустимое решение имеет вид x j = 0 , j = 1, K, n , и xn + i = bi , i = 1, K , m .Шаг 1. Проделать шаги 1)-4) алгоритма симплекс-метода, описанного впункте 1.3.Так как целевая функция задачи (12)-(14) ограничена снизу нулем и допустимое множество, задаваемое условиями (13)-(14), не пусто, то задача(12)-(14) всегда разрешима и минимум неотрицателен. Поэтому на первомэтапе вычисления могут завершиться только получением прямо и двойствен-53но допустимого базиса.
Как только такой базис получен, перейти к следующему пункту.Шаг 2. Если оптимальное решение x * > 0 , то КОНЕЦ (исходная задача неимеет допустимых решений: Q = Æ ), иначе удалить из симплекс-таблицы всестолбцы,соответствующиеискусственнымпеременнымx=j 0,j n + 1, K , n + m , и нулевую строку.=Шаг 3.
Если базисными переменными являются только переменные исходной задачи x j , j £ n , то перейти на шаг 7.Шаг 4. Выбрать строку, соответствующую искусственной переменнойxr , r < n .Шаг 5. Если существует zrs ¹ 0 , 1 £ s £ n , то выполнить элементарноепреобразование базиса с ведущим элементом zrs и перейти на шаг 3.Шаг 6. Если zrs = 0 для всех j = 1, K, n , то удалить r -ую строку из симплекс-таблицы и перейти на шаг 3.Шаг 7. Добавить нулевую строку в симплекс-таблицу, записав в нее коэффициенты целевой функции основной задачи w(x) , выраженной через небазисные переменные. Получена прямо допустимая симплекс-таблица исходной задачи.Шаг 8. Проделать шаги 1)-4) алгоритма симплекс-метода, описанного впункте 1.3.Шаги 0)-7) описанного выше способа получения базисного допустимогорешения обычно называют первым этапом симплекс-метода, а метод в целом– двухэтапным симплекс-методом.Выполнение шага 6 свидетельствует о линейной зависимости уравненийAx = b , что позволяет удалить часть уравнений.
Подобная ситуация возникает, когда ранг матрицы A меньше числа уравнений m .После выполнения шага 7 имеем прямо допустимую симплекс-таблицуисходной задачи, то есть завершен 0-ой шаг алгоритма пункта 1.3, и можнопереходить к его шагам 1)-4). В результате либо установим, что целеваяфункция w(x) не ограничена снизу, либо получим оптимальное решение.Следующие примеры иллюстрируют случаи, когда множество ограничений исходной задачи либо несовместно, либо избыточно.Пример 6. Решить задачуx1 - x2 + x3 - x4 + 3x5 ® minx1 + x4 + 2 x5 = 1 ,- x2 - x3 + x4 + 2 x5 = 2 ,2 x1 - 3x2 + x3 + x4 = 0 ,x j ³ 0, j = 1, K,5 .54Решение. Найдем начальное базисное допустимое решение с помощьюметода искусственного базиса.
Для этого добавим искусственные переменные x6 , x7 , x8 и получим задачуx6 + x7 + x8 ® minx1 + x4 + 2 x5 + x6 = 1 ,- x2 - x3 + x4 + 2 x5 + x7 = 2 ,2 x1 - 3 x2 + x3 + x4 + x8 = 0 ,x j ³ 0, j = 1, K,8 ,с базисным допустимым решением x = (0,0,0,0,0,1,2,0)T . Исключим базисныепеременные из целевой функции этой задачи и получим исходную симплекстаблицу:-xx6x7x8x1-3102-3120x240-1-3x300-11x4-3111x5-4220x60100x70010x80001Таблица не является двойственно допустимой.
Выбираем в качестве ведущего элемента z34 = 1 . Преобразовав, получим симплекс-таблицу:-xx6x7x4x13-1-22-3120x2-532-3x33-1-21x40001x5-4220x60100x70010x83-1-11Теперь в качестве ведущего элемента выбираем z15 = 2 . После преобразования получим симплекс-таблицу:-xx5x7x4-11/210x11-1/2-12x213/2-1-3x31-1/2-11x40001x50100x621/2-10x70010x81-1/201Таблица прямо и двойственно допустима. Получено оптимальное решениевспомогательной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
