Раздел 6, тема 6.2. Тема 2 Симплексметод решения злп
 Скачать 0.63 Mb.
|
|
Тема 6.2 Симплекс-метод решения ЗЛП Симплекс-метод является универсальным, так как позволяет решить практически лю- бую ЗЛП, записанную в каноническом виде. Данный метод еще называют методом последо- вательного улучшения плана, его идея заключается в том, что, начиная с некоторого опорно- го решения, осуществляется последовательно направленное перемещение по опорным реше- ниям задачи к оптимальному. Значение целевой функции при этом перемещении для задач на минимум не увеличи- вается. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется неотрицательное базисное решение. Для того чтобы решить ЗЛП симплекс-методом, необходимо систему ограничений и линейную форму представить в виде: m =b n x mn +a + m+ x m,m+ +a m x . . . . . . . . . . . . =b n x n +a + m+ x ,m+ +a x =b n x n +a + m+ x ,m+ +a x 1 1 2 2 1 1 2 2 1 1 1 1 1 1 (5) n , j= ≥ j x =c n x n +c + m+ x m+ z+c 1 0 0 1 1 (6) m. , i= ≥ j b 1 0 (7) Этот вид характеризуется следующими особенностями: 1. Ограничения (5) имеют только форму уравнений, в уравнениях выделены базисные неизвестные. В системе (5) в качестве базисных – первые т неизвестных (т<п). Остальные (п-т) неизвестных – свободные. 2. Линейная форма z, которую требуется минимизировать, должна бытьвыражена только через свободные неизвестные и вместе с ними записана в левой части уравнения (6). 3. Все неизвестные n x x x , , , 2 1 должны быть неотрицательны. 4. Все свободные члены m b b b , , , 2 1 должны быть неотрицательны. Допустим, нам удалось привести систему ограничений к виду (5). Условие m i b i , 1 0 может быть обеспечено только в том случае, когда система ограничений в ЗЛП имеет хотя бы одно неотрицательное решение. Базисным неизвестным n x x x , , , 2 1 системы (5) соответствует неотрицательное базис- ное решение (или опорный план): ) n , , , , m ,b , ,b (b 0 0 0 2 1 , (8) 2 который получается из системы (5), если в ней свободные неизвестные n m m x x x , , , 2 1 при- равнять к нулю. При этом форма примет значение 0 с . Решение ЗЛП симплекс-методом удобно оформлять с помощью, так называемых, сим- плексных таблиц. Практически это та же матричная форма записи системы уравнений и це- левой функции, что и в методе Гаусса решения систем линейных алгебраических уравнений. Талицы подобного вида полностью отражают систему (5-6). Алгоритм симплекс-метода 1. Математическую модель задачи приводят к каноническому виду и записывают в виде (5-7). 2. Составляют симплексную таблицу. Все строки таблицы 1-го шага заполняют по данным системы ограничений и целевой функции. Базис. перем. Своб. члены 1 x … i x … m x 1 m x … n x ij i a b / 1 x 1 b 1 … 0 … 0 1 , 1 m a … n a , 1 … … … … … … … … … … i x i b 0 … 1 … 0 1 , m i a … n i a , … … … … … … … … … … m x m b 0 … 0 … 1 1 , m m a … n m a , z 0 с 0 … 0 … 0 1 m с … n с 3. Просматривают элементы последней строки таблицы кроме элемента с 0 . Если сре- ди них нет положительных, то базисное решение, соответствующее таблице, является опти- мальным и 0 min c z 4. Если в последней строке найдется хотя бы один положительный элемент, напри- мер, j c >0, то, отметив j-й столбец стрелкой, переходят к п.5. 5. Просматриваются элементы выделенного столбца, над элементом j c . Если среди них нет положительного, то z min 6. Если найдется хотя бы один положительный элемент, то для положительных эле- ментов отмеченного столбца вычисляют отношения ) 0 ( / ji ij i a a b и заносят в последний столбец таблицы. 7. Выбирают наименьшее из этих отношений. Пусть оно достигается при i=k. Отме- чают k-ю строку стрелкой. Элемент kj a , находящийся на пересечении выделенных строки и столбца, называют разрешающим (ключевым) элементом. 8. Составляют таблицу 2-го шага. В базис на место базисного неизвестного k x ставят неизвестную j x . Делят элементы отмеченной строки таблицы 1-го шага на разрешающий элемент kj a и вносят полученные элементы в ту же строку таблицы 2-го шага. Умножая от- меченную строку таблицы 1-го шага на соответствующие числа, прибавляют ее к остальным 3 строкам таблицы 1-го шага для того чтобы получить выше и ниже разрешающего элемента kj a нули. Все вновь вычисленные элементы строк заносят в таблицу 2-го шага. 9. С таблицей 2-го шага работают аналогично (см. п.3). Пример 1. Решим задачу из примера 2.2 симплекс-методом. Решение. Математическая модель задачи имеет вид: 18 3 15 3 13 2 19 3 2 1 2 2 1 2 1 x x x x x x 2 , 1 0 j x j , max 5 7 2 1 x x z Для того чтобы задача приобрела необходимый для симплекс-метода вид, приведем це- левую функцию и ограничения задачи к виду (5-7): 18 3 15 3 13 2 19 3 2 6 1 5 2 4 2 1 3 2 1 x x x x x x x x x x (9) 6 , 1 0 j x j , (10) 6 5 4 3 , , , x x x x - дополнительные переменные. Сведем теперь задачу об отыскании максимального значения z к задаче об отыскании минимального значения формы 2 1 5 7 ) ( x x z , записав это уравнение в соответствии с требованием (6) в виде: 0 5 7 ) ( 2 1 x x z (11) Ранг системы (12) определим из матрицы коэффициентов системы: 1 0 0 0 0 3 0 1 0 0 3 0 0 0 1 0 1 2 0 0 0 1 3 2 A . Так как , 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 то r(А)=4. Число базисных переменных равно 4, число свободных равно 2 (это неизвестные 2 1 , x x ). Составим таблицу 1-го шага из коэффициентов системы (9-11). 4 Таблица 1 Базис. пе- рем. Своб. чле- ны 1 x 2 x 3 x 4 x 5 x 6 x ij i a b / 3 x 19 2 3 1 0 0 0 19/2 4 x 13 2 1 0 1 0 0 13/2 5 x 15 0 3 0 0 1 0 - 6 x 18 3 0 0 0 0 1 6 z 0 7 5 0 0 0 0 Среди элементов последней строки табл.1 есть положительные, значит данное решение не является оптимальным и его можно улучшить. Выберем, например, элемент 7 1 c и от- мечаем этот столбец стрелкой вверху таблицы. Этот столбец назовем разрешающим. Для положительных элементов разрешающего столбца вычисляем отношения 1 / i i a b (последняя строка не рассматривается), т.е. 19/2, 13/2, 18/3 и заносим в последний столбец табли- цы. Среди этих отношений выбираем наименьшее, оно равно 6. Отмечаем строку, где стоит наименьшее значение, стрелкой. Эта строка соответствует базисному неизвестному 6 x . На пере- сечении отмеченных стрелками строки и столбца, находится разрешающий элемент 3 61 a (обве- ден рамкой). Переходим к составлению табл.2. Базисную неизвестную 6 x заменяем на новую базис- ную переменную 1 x . Все элементы отмеченной строки делимна разрешающий элемент 3 61 a и заносим в ту же строку табл.2. В табл.1 умножаем отмеченную строку последовательно на (- 2/3), (-2/3), (-7/3) и прибавляем соответственно к 1-й, 2-й и последней строке. Результаты заносим в табл.2. Таблица 2 Базис. пе- рем. Своб. члены 1 x 2 x 3 x 4 x 5 x 6 x ij i a b / 3 x 7 0 3 1 0 0 -2/3 7/3 4 x 1 0 1 0 1 0 -2/3 1 5 x 15 0 3 0 0 1 0 5 1 x 6 1 0 0 0 0 1/3 - z -42 0 5 0 0 0 -7/3 Просматриваем элементы последней строки табл.2, находим положительный 5 1 c . От- мечаем соответствующий столбец стрелкой. Просматриваем элементы отмеченного столбца, вы- числяем отношения 2 / i i a b , находим наименьшее из этих отношений -1, значит разрешающая строка соответствует базисной переменной 4 x . Разрешающий элемент 1 42 a Составляем табл.3, в ней переменная 4 x в базисе заменится на 2 x . Отмеченная строка без изменений переносится в табл.3. Вторую строку табл.2 умножаем последовательно на (-3), (-3) 5 и (-5) и прибавляем соответственно к 1-й, 3-й и последней строке табл.2. Результаты заносим в табл.3. Таблица 3 Базис. пе- рем. Своб. члены 1 x 2 x 3 x 4 x 5 x 6 x ij i a b / 3 x 4 0 0 1 -3 0 4/3 3 2 x 1 0 1 0 1 0 -2/3 - 5 x 12 0 0 0 -3 1 2 6 1 x 6 1 0 0 0 0 1/3 18 z -47 0 0 0 -5 0 1 Просматриваем последнюю строку табл.3. Находим положительный элемент 1 6 c . Отмечаем разрешающий столбец. Находим разрешающую строку (это первая строка), отме- чаем ее. Разрешающий элемент 3 / 4 36 a Составляем табл.4. Вместо 3 x в базис войдет переменная 6 x . Действуя по указанным пра- вилам, получим Таблица 4 Базис. перем. Своб. члены 1 x 2 x 3 x 4 x 5 x 6 x ij i a b / 6 x 3 0 0 3/4 -9/4 0 1 2 x 3 0 1 1/2 - 1/2 0 0 5 x 6 0 0 -3/2 3/2 1 0 1 x 5 1 0 - 1/4 3/4 0 0 z -50 0 0 -3/4 -11/4 0 0 В последней строке табл.4 нет положительных элементов, значит она содержит опти- мальное решение задачи х з X переменны ьных дополнител начения * ); 3 , 6 , 0 , 0 , 3 , 5 ( 50 ) ( * max * z X z Замечание. Для решения ЗЛП симплекс-методом необходимо привести ее к специаль- ному виду (5-7). Можно привести систему ограничений к виду (5) методом Гаусса, но усло- вие неотрицательности свободных членов в системе (5) не всегда может быть обеспечено. Перебор всех базисных решений в поисках неотрицательного решения может оказаться за- труднительным. В связи с этим существует специальный метод отыскания исходного допу- стимого базисного решения – метод искусственного базиса. 6 Метод искусственного базиса Этот метод позволяет каноническую форму ЗЛП, в которой требуется найти минимум функции (1) при ограничениях (2-3), привести к виду (5-7), если система уравнений (2) имеет хотя бы одно неотрицательное решение. Пусть ранг системы уравнений (2) равен m. Необходимо, чтобы свободные члены в уравнениях этой системы были неотрицательны. Если в каком-либо уравнении свободный член отрицателен, то умножим обе его части на (-1). Введем вспомогательные неизвестные m y y y , , , 2 1 и построим для системы (2) вспомо- гательную систему линейных уравнений: , m =b m +y n x mn +a + x m +a x m a . . . . . . . . . . . . . . =b +y n x n +a + x +a x a =b +y n x n +a + x +a x a 2 2 1 1 2 2 2 2 22 1 21 1 1 1 2 12 1 11 (12) m , i= ≥ i b 1 0 Система (2) тогда и только тогда имеет неотрицательные решения, когда система (12) имеет неотрицательные решения, в которых вспомогательные неизвестные m y y y , , , 2 1 рав- ны нулю. Предположим, систему (12) удалось привести к виду: m b = m y mm a + + y m a + n x mn a + + m+ x m,m+ a + m x . . . . . . . . . . . . . . . . . . . . b = m y m a + + y a + n x n a + + m+ x ,m+ a + x b = m y m a + + y a + n x n a + + m+ x ,m+ a + x 1 1 1 1 2 2 1 21 2 1 1 2 2 1 1 1 11 1 1 1 1 1 (13) m , i= ≥ i b 1 0 Тогда, приравняв к нулю вспомогательные неизвестные m y y y , , , 2 1 в системе (13), приходим к системе нужного вида (5): m b = n x mn a + + m+ x m,m+ a + m x . . .. . . . . . . . . . b = n x n a + + m+ x ,m+ a + x b = n x n a + + m+ x ,m+ a + x 1 1 2 2 1 1 2 2 1 1 1 1 1 1 (14) m , i= ≥ i b 1 0 Переход от системы (12) к системе (14) можно осуществить, решив вспомогательную ЗЛП: среди неотрицательных решений системы уравнений (12) найти решение, дающее ми- нимум линейной форме 2 1 m y y y F Система уравнений (12) удовлетворяет всем требованиям первого шага симплекс- метода. Вспомогательные неизвестные m y y y , , , 2 1 образуют исходный базис: отсюда и 7 название метода. Форму F легко выразить через свободные неизвестные n x x x , , , 2 1 , сложив все уравнения системы (12). Так какформа F неотрицательна, то она имеет конечный мини- мум. Возможны два случая: 1. Min F > 0, тогда система (12) не имеет неотрицательных решений, в которых все вспомогательные неизвестные m y y y , , , 2 1 равны нулю, следовательно, система (2) не имеет неотрицательных решений, т.е. множество ее допустимых решений пусто. 2. Min F = 0, тогда система (12) имеет неотрицательные решения, в которых все вспомогательные неизвестные m y y y , , , 2 1 равны нулю, следовательно, система (2) имеет неотрицательные решения. Пример 2. Найти допустимое неотрицательное базисное решение системы линейных уравнений: 3 5 3 4 3 4 6 5 2 4 3 2 1 4 3 2 1 x x x x x x x x Решение. Умножим 2-е уравнение на -1, поскольку свободный член в нем отрицатель- ный: 3 5 3 4 3 4 6 5 2 4 3 2 1 4 3 2 1 x x x x x x x x Введем искусственный базис 2 1 y , y , формально преобразовав систему: 3 5 3 4 3 4 6 5 2 2 4 3 2 1 1 4 3 2 1 y x x x x y x x x x Выражение вспомогательной формы 2 1 y y F через свободные неизвестные 4 1 , , x x можно получить, сложив уравнения системы 7 6 3 4 3 2 1 F x x x x Для отыскания неотрицательного решения системы, дающего минимум форме F , со- ставим симплекс-таблицу: Таблица 1 Базис. пе- рем. Своб. чле- ны 1 x 2 x 3 x 4 x 1 y 2 y ij i a b / 1 y 4 2 -5 6 1 1 0 4 2 y 3 -3 4 -3 5 0 1 3/5 F 7 -1 -1 3 6 0 0 С помощью симплекс-метода находим разрешающий элемент. Выводим из базиса 2 y , заменяя на 4 x . Поскольку в последующем 2 y следует приравнять нулю, то сделаем это на этом шаге исключаю его из последующих рассуждений. 8 Таблица 2 Базис. пе- рем. Своб. Члены 1 x 2 x 3 x 4 x 1 y ij i a b / 1 y 17/5 13/5 -29/5 33/5 0 1 17/13 4 x 3/5 -3/5 4/5 -3/5 1 0 - F 17/15 13/5 -29/5 33/5 0 0 Выбрав разрешающий элемент, заменяем в базисе 1 y на 1 x и приравниваем 1 y к нулю. Базисное решение, соответствующее новому базису, дает форме F минимум равный нулю. В итоговой таблице отсутствует столбец с 1 y и строка, соответствующая F . Таблица 3 Базис. пе- рем. Своб. члены 1 x 2 x 3 x 4 x ij i a b / 1 x 17/13 1 -29/13 33/15 0 4 x 18/13 0 -7/13 12/13 1 Система уравнений, соответствующая последней таблице имеет вид: 13 / 18 13 / 12 13 / 7 13 / 17 13 / 33 13 / 29 4 3 2 3 2 1 x x x x x x Она эквивалентна исходной системе и имеет тот же вид, что и система (5). Приравняв в ней нулю свободные переменные 3 2 , x x , получим допустимое базисное решение системы, равное ) 13 / 18 , 0 , 0 , 13 / 17 ( |