Симплекс- метод решения задач линейного программирования

Лекция СИМПЛЕКС- МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В В Е Д Е Н И Е В 1949 году американским ученым Дж.Б. Данцигом был разработан один из наиболее общих методов решения задач линейного программирования – симплекс-метод. Симплекс метод иногда называют «методом последовательного улучшения плана», так как суть его заключается в последовательном переборе вершин области ограничений таким образом, что значение целевой функции убывает от вершины к вершине до минимума. Примером пространства области ограничений является многогранником; простейший многогранник- симплекс, имеющий в качестве граней треугольники, отсюда название метода. Симплекс- метод является универсальным методом решения задач линейного программирования. В силу универсальности метод является довольно громоздким, хотя его идея проста. В основе метода лежит формализованный вариант метода постановки – метод обыкновенных жордановых исключений (шаг ОЖИ). 1. Основные понятия линейного программирования Прежде чем перейти к детальному рассмотрению поставленных на предыдущей лекции задач, дадим ряд определений (понятий), которые необходимы для изложения сущности симплекс- метода. Для изложения воспользуемся канонической формой записи ЗЛП: (1) при ограничениях (2) Задачи ЛП имеют смысл лишь для совместных систем ограничений (2). Система ограничений (2) называется совместной, если существует хотя бы одно решение, обращающее все уравнения системы ограничений (2) в тождества, и несовместной, если ни одного такого решения не существует. Проверка наличия решений в системе (2) может быть осуществлена по рангу основной и расширенной матриц системы. Основная матрица системы (2)- матрица коэффициентов. Расширенная матрица системы (2)- основная матрица, дополненная столбцом сводных членов . Ранг матрицы (r)- число линейно- независимых уравнений в системе ограничений (2), определяемое как наивысший порядок отличного от нуля определителя системы. В общем случае ранг матрицы не превышает числа неизвестных, то есть r n. При r=n система ограничений (2) имеет единственное решение. В линейном программировании рассматривается случай rn , при котором система ограничений (2) имеет множество решений и, следовательно, есть возможность отыскать среди них одно, обращающее в минимум целевую функцию (1). r n означает, что число линейно- независимых уравнений системы меньше числа неизвестных. Принцип решения таких систем уравнений заключается в следующем: часть неизвестных, число которых равно числу линейно- независимых уравнений системы r и называемых базисными, выражается через остальные неизвестные, называемые свободными. Затем, полагая свободные неизвестные равными нулю, находят какое- нибудь решение системы ограничений. Неизвестные, через которые выражаются все решения системы ограничений, называются свободными (они записываются сверху симплекс- таблицы). Неизвестные, которые выражаются через свободные неизвестные, называются базисными (левый столбец симплекс- таблицы). Набор свободных неизвестных можно менять, при этом в каждом случае базисные неизвестные и целевую функцию (линейную форму) надо выражать через свободные неизвестные. Решение системы ограничений, соответствующее нулевым свободным неизвестным, называется базисным. Каждому набору свободных неизвестных отвечает свое базисное решение. Всякое неотрицательное решение системы ограничений (2) называется допустимым. Допустимое базисное решение называется опорным планом. Допустимое базисное решение называется опорным планом (решением). Опорное решение, минимизирующее целевую функцию (линейную форму) (1), называется оптимальным. 1. Алгоритм симплекс- метода и его применение Алгоритм симплекс- метода состоит из следующих этапов (рис. 1.) Подготовительный этап. Задача преобразуется в ОЗЛП: минимизировать при ограничениях и представляется в виде исходной симплекс- таблицы: x1 … xj … xn 1 y1 a11 … a 1j … a 1n b1 … … … … … … … yi a i1 … a ij … a in bi … … … … … … … ym a m1 … a mj … a mn bm z c1 … cj … cn c0 Оптимальное решение X0= ; Zmin = Z (X0) = I этап: поиск базисного решения. (рис. 3.1) Задача преобразуется в ОЗЛП и представляется в виде исходной симплекс-таблицы. Блоки 1, 6: проверка системы ограничения на совместимость. Для yi= 0 не могут быть все aij = 0, а bi  0, так как в ОЗЛП yi = Блоки 2, 7: из системы ограничения убираются тривиальные тождества. Блоки 3, 4: преобразование симплекс-таблицы с помощью метода обыкновенных жордановых исключений (ОЖИ). Рис 3.1. I этап. Поиск базисного решения Формализованные правила шага ОЖИ: 1. Выбрать в исходной симплекс-таблице разрешающий элемент ars0; s-й столбец и r–я строка называются разрешающими. 2. В новой симплекс-таблице на месте разрешающего элемента записать единицу. 3. Остальные элементы разрешающего столбца a1s (ir) оставить без изменений. 4. У остальных элементов разрешающей строки arj (js) изменить знаки на противоположные. 5. Остальные элементы новой симплекс-таблицы вычислить с помощью определителя второго порядка. 6. Все элементы новой симплекс-таблицы разделить на разрешающий элемент ars. В результате 1 этапа получаем базисное решение, которое записывается следующим образом: все свободные переменные xj приравниваются нулям, базисные переменные xi равны свободным членам. II этап: поиск опорного решения (рис. 3.2). Неотрицательное базисное решение будет опорным, если в симплекс-таблице все bi  0. Блоки 11, 18: проверка системы на ограниченность. Условие сj < 0 позволяет неограниченно уменьшать значение целевой функции, увеличивая xj; при этом, так как aij > 0, базисные переменные xi будут также неограниченно возрастать. Поскольку в реальных задачах переменные xj выражают запасы каких-то материальных средств, данный случай соответствует задаче, не имеющей решений. Блоки 12, 19: проверка системы ограничений на совместимость. При допустимых xj не могут быть aij  0 и bi <0 для выполнения условия yi=0. Блок 13: предварительный выбор разрешающей строки. Выбрать строку xi, в которой bi < 0. Этот выбор определяется тем, что при выполнении шага ОЖИ знаки в разрешающей строке меняются на противоположные, а нужно получить bi  0. Блок 14: выбор разрешающего столбца. Выбрать столбец xj, в котором aij>0. Условие aij>0 приводит к тому, что при увеличении xj переменная xi=bi<0 в базисном решении будет возрастать от значения bi до нуля, если i–я строка будет разрешающей. Рис.3.2 II этап. Поиск опорного решения Блок 21: обеспечение допустимости решения. Выбирается min; это определяется требованием неотрицательности базисных переменных во всех строках. В результате П этапа получаем опорное решение, которое записывается по аналогии с 1 этапом: свободные переменные xj = 0, базисные xi равны свободным членам. III этап: поиск оптимального решения (рис. 3.3). Рис.3.3 III этап. Поиск оптимального решения Блок 24: проверка опорного решения на оптимальность. Неотрицательность всех коэффициентов при переменных в выражении целевой функции означает, что дальнейшее улучшение плана невозможно, данное опорное решение является оптимальным. Блок 25: выбор разрешающего столбца. Наличие сj < 0 означает, что, увеличивая значение xj, можно еще уменьшить значение целевой функции. Блоки 26, 27: выбор разрешающей строки. Содержание этих блоков аналогично содержанию блоков 20, 21 предыдущего этапа. В итоге III этапа получаем оптимальное решение задачи линейного программирования: все свободные переменные xj, располагающиеся в верхней части симплекс-таблицы, берутся равными нулю, а базисные переменные xi, записанные в симплекс-таблице слева, приравниваются свободным членам. Практическая часть Работу каждого этапа алгоритма рассмотрим на примере. Пример. Найти неотрицательное решение системы ограничений обращающее в максимум целевую функцию z1 = x2 – x1 Решение Подготовительный этап. Введением дополнительной неотрицательной неизвестной 1 преобразуем неравенство в равенство, т.е. приведём задачу к ОЗЛП От максимизации целевой функции z1 перейдём к минимизации функции z противоположного знака z=-z1=x1-x2min xj Исходная симплекс – таблица имеет вид: x1 x2 x3 1 1 y1 2 -1 -6 y2 3 4 1 -13 z 1 -1 I этап. Поиск какого- нибудь базисного решения. Задачей этого этапа является перевод вспомогательных неизвестных yi в свободные неизвестные, а некоторых свободных переменных в базисные. После исключения столбцов со вспомогательными неизвестными yi=0 получается симплекс- таблица, с каким- нибудь базисным решением. Блок 4. Выбираем разрешающий элемент для шага ОЖИ. В качестве такого элемента удобно выбрать a24=10.Обведём его в рамку и переходим к преобразованию симплекс – таблицы с помощью шага обыкновенных жордановых исключений (ОЖИ) (Блок 7). После выполнения шага ОЖИ получим новую симплекс – таблицу. (Пояснить подробнее шаг ОЖИ для одного преобразования симплекс – таблицы), в которой столбец y2 вычёркиваем x1 x2 x3 y2 1 y1 2 -6 1 -3 -4 1 13 z 1 -1 Так как осталось ещё одна строка y1 (Блок 8), то возвращаемся к блоку 1 и процесс повторяется, в результате получим новую симплекс – таблицу, в которой столбец y1 вычёркиваем. x1 x2 y1 1 x3 2 -1 -6 1 -3 -4 13 z 1 -1 Поскольку строк yi больше нет (Блок 8), получено какое – нибудь базисное решение (Блок 9). Оно записывается следующем образом: все свободные переменные xj приравниваются нулям (в данном случае x1 и x2),базисные переменные xi (сейчас это x3 и w1) будут равны свободным членам, записанным в последнем столбце симплекс- таблицы x1=x2=0; x3=-6; 1=13; z=0. Так как последняя симплекс – таблица представляет собой систему уравнений, запишем её z=x1-x2 Эту же систему можно было получить непосредственно из исходной, выбрав x1 и x2 в качестве свободных, а x3 и – базисных неизвестных. Следовательно, в частном случае первого этапа симплекс – метода может не быть, если какое- либо базисное решение очевидно. (При недостатке времени первый этап таким образом можно исключить). Проанализируем полученное решение. Так как одна из базисных неизвестных отрицательна (x3=-60), то базисное решение не является допустимым, то есть опорное решение ещё не получено. II этап. Поиск опорного решения (все bi>0). На данном этапе отрицательные базисные переменные переводятся в свободные, а соответствующие свободные становятся базисными. Одновременно целевая функция также преобразуется и выражается через свободные неизвестные. Процедура продолжается до тех пор, пока все базисные неизвестные не станут положительными. Блок 12. Проверка системы на ограниченность. Условие ci<0 позволяет неограниченно уменьшать значение целевой функции, увеличивая xj, при этом, так как aij>0, базисные переменные xi будут также неограниченно возрастать. Поскольку в реальных задачах переменные выражают запасы каких – то материальных средств, данный случай соответствует задаче, не имеющей решений (Блок 13). У нас таких столбцов нет. Блок 14. Проверка системы ограничений на совместимость. При допустимых xj не могут быть aij<0 и bi<0 для выполнения условия yi=0. Если система несовместна – к Блоку 15. Так как в рассматриваемой симплекс – таблице таких строк нет, переходим к Блоку 16. Блок 16. Предварительный выбор разрешающей строки. Выбрать строку, в которой bi<0. Этот выбор определяется тем, что при выполнении шага ОЖИ знаки в разрешающей строке меняются на противоположные, а нужно получить bi>0. У нас это базисная переменная x3. Для того, чтобы сделать допустимое решение опорным, необходимо увеличить x3 до нуля (перевести переменную в свободные) за счёт увеличения x1 и x2. Блок 17. Выбор разрешающего столбца. Выбрать столбец xj в котором aij>0. Условие aij>0 приведёт к тому, что при увеличении xj переменная x3=-6<0 в базисном решении будет возрастать от значения –6 до нуля, если i-я строка будет разрешающей. Так как в строке x3 только коэффициент при x1 положителен, именно эту переменную будем вводить в состав базисных. Итак, разрешающий столбец – первый. Отметим разрешающий столбец знаком. Блоки 18 – 21. Окончательный выбор разрешающей строки. Нам необходимо перевести x3 в свободные переменные и ни в какой другой строке базисные переменные не должны стать отрицательными. В нашем случае переменную x1 можно увеличивать до тех пор, пока одна из базисных переменных x3, 1 не обратится в нуль. Та из них, которая первой обратится в нуль, укажет окончательную разрешающую строку. Для этого в блоках 19 или 20 рассчитываются неположительные отношения свободных членов bi к коэффициентам ai разрешающего столбца, из них выбирается min Соответствующая строка и будет разрешающей. В нашем примере с1=1>0 ( Блок18), в соответствии с Блоком 19 h1=-6/2=-3, h2=13/-3=-4.33. В Блоке 21 min{}=3= таким образом, разрешающая строка – первая. Это означает, что с увеличением x1 первой обратится в нуль x3. Это произойдёт при x1=3. Другая базисная переменная остаётся положительной (1=4). Итак, разрешающим элементом будет а11=2. Проверка Блока 18 предусмотрена для сокращения вычислений, так как на следующем этапе потребуется менять знак отрицательных коэффициентов сj и данную процедуру можно совместить со сменой знака bi. Блок 22. Выполняем шаг ОЖИ с разрешающим элементом a11=2 x3 x2 1 x1 1/2 3 1 -3/2 -4 4 z 1/2 -1 3 Поскольку все bi>0 (Блок 10), найдено опорное решение x1=3; x2=0; 1=4; x3=0; z=3. Данное решение оптимальным не является, так как с2<0 в выражении для целевой функции и с увеличением x2 значение z будет уменьшаться. Поэтому полученное нами решение не обеспечивает минимума целевой функции. III этап: поиск оптимального решения. Как мы установили, признаком оптимального решения является неотрицательность коэффициентов сj при переменных xj в выражении для целевой функции. Блок 23. Проверка опорного решения на оптимальность. Так как с2<0 то к Блоку 25. Блок 25. Проверка системы на ограниченность, аналогичен Блоку 12. Блок 27. Выбор разрешающего столбца. Так как с2<0, второй столбец и будет разрешающим. Блоки 28-29. Выбор разрешающей строки. Содержание этих блоков аналогично содержанию блоков 19-21 предыдущего этапа. В нашем случае переменную x2 можно увеличивать до тех пор, пока не нарушится условие неотрицательности переменных x1, 1. В соответствии с Блоком 29 отношение h2=4/-4=-1 и является единственным. Таким образом, разрешающая строка – вторая. Блок 30. Выполняем шаг ОЖИ с разрешающим элементом а22=-4 x3 1 1 x1 1/2 3 x2 -3/8 -1/4 1 z 7/8 1/4 2 Поскольку все сj>0 (Блок 23), получено оптимальное решение x1=3; x3=0; x2=1; 1=0. При этом z min=2, и соответственно z1 max=-zmin=-2.