Сущность и особенности симплексного метода

ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА имени адмирала С.О. МАКАРОВА ИНСТИТУТ ВОДНОГО ТРАНСПОРТА КАФЕДРА МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И ПРИКЛАДНОЙ ИНФОРМАТИКИ УТВЕРЖДАЮ Заведующий кафедрой д.т.н., доцент 31. августа 2020г С.В. Колесниченко ЛЕКЦИЯ №5 ТЕМА: ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НАПРАВЛЕНИЕ ПОДГОТОВКИ: 09.03.03. ПРИКЛАДНАЯ ИНФОРМАТИКА УЧЕБНАЯ ДИСЦИПЛИНА: Б1.О.21 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ ОПТИМИЗАЦИИ Обсуждена на заседании кафедры Протокол № 01 от 31 августа 2020 Разработал: профессор кафедры, к.в.н., доцент БУРЫКИН А.А. Санкт-Петербург  2020 УДК 519.876.3 ББК 22.18 Рецензент: Земсков А.В. доктор технических наук, профессор ГУМРФ имени адмирала С.О. Макарова Бурыкин А.А., Численные методы решения задачи линейного программирования: Фондовая лекция по дисциплине «Исследование операций и методы оптимизации». СПб: ГУМРФ имени адмирала С.О. Макарова, 2020. 8с. УДК ББК 519.876.3 22.18  Бурыкин А.А., 2020.  ГУМРФ имени адмирала С.О. Макарова, 2020. 2 ВВЕДЕНИЕ Вводная часть Лекция №4 является частью раздела I «Методы оптимизации». На изучение данной темы лекции отведено  2 часа лекционных занятий и 1 час самостоятельной работы. Актуальность темы Симплексный метод (метод последовательного улучшения плана) является самым эффективным и универсальным среди точных численных методов решения задачи линейного программирования. Идеи метода в 1939 году были разработаны советский академик Леонидом Витальевичем Канторовичем российским. Но как метод он впервые были предложен американским ученым Джорджем Бернардом Данцигом в 1947 году. Предтечей же «симплекс-метода» можно считать метод разрешающих множителей, описанный в 1797-1801 году Жозефом Луи Лагранжем и работы венгерских математиков Эйгена Эгервари и Денеша Кёнига в 1931 году. Конкретная цель К настоящему времени разработано два вида симплексного метода:  симплекс-метод с естественным базисом;  симплекс-метод с искусственным базисом (М-метод). Пояснение плана лекции В лекции рассматриваются следующие основные вопросы: 1. Сущность и особенности симплексного метода решения задач линейного программирования. 2. Симплекс-метод решения задач линейного программирования с естественным базисом. 3. Симплекс-метод решения задач линейного программирования с искусственным базисом (М-метод). 1. СУЩНОСТЬ И ОСОБЕННОСТИ СИМПЛЕКСНОГО МЕТОДА РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Симплексный метод основан на свойствах задачи линейного программирования (ЗЛП), поэтому данный метод – это итерационный процесс при любом положительном n – m> 0, который начинается с нахождения начального допустимого решения с последующим переходом по угловым точкам ОДР к другому допустимому решению до нахождения оптимального решения. Направление перехода от одного допустимого решения к другому выбирается на основе критерия оптимальности. Таким образом, решая ЗЛП симплекс-методом необходимо (этапы): 1. Найти первоначальное решение. 2. Проверить решение на оптимальность. 3. Перейти к улучшенному решению (если проверяемое решение было не оптимально). 3 Нахождение первоначального решения. Для нахождения начального решения, удовлетворяющего всем условиям задачи, могут быть использованы различные методы. Однако все они построены на использовании свойств ЗЛП. Основными из них являются:  Метод «Приведение ЗЛП к каноническому виду»;  Метод «Полного исключения (Жордана-Гаусса);  Метод «Искусственного базиса». Проверка решение на оптимальность. Признак оптимальности заключается в следующих трех теоремах1: Теорема № 1 Если для некоторого вектора2, не входящего в базис выполняется условие  j  z j c j  0 , (1) (2) z j   ci aij j где i  1, m ; j  1, n . то можно получить новое допустимое решение, для которого значение ЦФ будет больше исходного, в случае если имеется хотя бы одна положительная переменная, подлежащая вводу в базис. Т.е. вводя в базис величину, для  j  0 которой, можно только ухудшить решение, поскольку задача состоит в том, чтобы придать ЦФ минимальное значение. Теорема № 2 Если для некоторого вектора, не входящего в базис, выполняется условие  j  z j c j  0 , (3) то нельзя получить улучшенного решения, т.к. ЦФ сохраняет свое прежнее значение. Теорема № 3 Отсюда следует, что если для всех j нет ни одного положительного, то решение, соответствующее данному базису, не может быть улучшено и, следовательно, является оптимальным:  j  z j c j  0 , (4) Таким образом, изложенные правила позволяют определить, является ли начальный план оптимальным, а если он не оптимален, то указать, как совершить переход к другому улучшенному плану. Переход к улучшенному решению. На основании признака оптимальности в базис вводиться вектор Ак, давший наибольшую положительную величину симплекс-разности:  k  z k  c k  max( z j  c j ) (5) Чтобы выполнялось условие неотрицательности значений допустимого решения, выводиться из базиса вектор Аr, которой дает положительное минимальное отношение: 1 2 Доказательство теорем смотри учебное пособие [3]. Упорядоченная система из n действительных чисел называется n-мерным вектором. 4 Q  min bi b  min r aik a rk (6) ark  0 разрешающий элемент; Хr – направляющая строка; Хk – направляющий столбец. Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам: где a rj/  (7) a rj a rk Т.е. все элементы направляющей строки надо разделить на разрешающий элемент и результаты деления занести в строку следующей симплекс-таблице, соответствующей введенной в базис переменной. В результате этого на месте разрешающего элемента в следующей симплекс-таблице будем иметь 1, а в остальных ячейках нули. Элементы любой другой i-строки пересчитываются по формулам: a ij/  a ij  a rk  a rj  a ik a rk (8) Значения ограничений базисных переменных нового допустимого решения рассчитываются по формулам: b br/  r a rk для i  r (9) bi/  bi  a rk  br  aik a rk для i  r (10) 2. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ЕСТЕСТВЕННЫМ БАЗИСОМ Для применения данного метода ЗЛП должна быть сформулирована в канонической форме. Начальное решение находиться методом «приведения ЗЛП к каноническому виду» или методом «полного исключения». Метод «Приведение ЗЛП к каноническому виду». Если по условиям ЗЛП линейные ограj aij  x j  bi ничения выражаются в виде неравенств и все, bi  0 то нахождение начального решения осуществляется приведением ЗЛП к каноническому виду с помощью дополнительных переменных. В ЦФ дополнительные переменные входят с коэффициентами, равными нулю (см. лекцию 9.). Так как оптимальный план соответствует одной из вершин области допустимых решений, то целесообразнее его искать среди этих вершин. Для нахождения начального решения воспользуемся тем, что каждой из вершин области допустимых решений m искомых величин положительны, а n – m величин равны нулю. В системе уравнений приравняв неизвестные переменные хj к нулю, система линейных ограничений примет следующий вид: хnk  bi (11) Так как все bi  0, то полученное решение, которое удовлетворяет всем условиям задачи может быть взято в качестве начального решения: 5 X  ( х j  0; х n 1  b1 ,..., хn  m  bm ) (12) Метод «Полного исключения (Жордана-Гаусса)». В том случае, когда система линейных ограничений задана в виде равенства для нахождения начального решения может быть применен метод полного исключения. Первый шаг способа состоит в выборе из числа неизвестных переменных m линейнонезависимых величин и в преобразовании системы линейных уравнений (СЛУ) так, чтобы эти величины имели номера с первого по m-й. Совокупность таких m линейно-независимых величин называют – базисом, а переменные – базисными. Остальные n – m переменные называют – свободными. Базисным решением СЛУ называется – частное решение, в котором свободные переменные имеют нулевые значения. Если все элементы базисного решения неотрицательны, то такое решение называется - начальным. Каждому разбиению на базисные и свободные переменные соответствует одно базисное решение, а количество способов разбиения не превышает величины: n! (13) Сnm  m!(n  m)! Далее последовательно над строками расширенной матрицы системы линейных уравнений-ограничений выполняются элементарные преобразования3, переводящие ее в эквивалентную систему, так чтобы некоторая неизвестная переменная исключалась из всех уравнений, кроме одного, т.е. в составе расширенной матрицы, формируется единичная матрица4 размера m  m так, чтобы все bi после преобразования были положительными. Элементарными преобразованиями СЛУ называются следующие преобразования: • перестановка любых двух уравнений; • прибавление к обеим частям одного уравнения, соответствующих частей другого уравнения, умноженных на любое число отличное от нуля; • вычеркивание нулевой строки, т.е. уравнения с нулевыми коэффициентами и свободными членами. В таком виде полученное решение удовлетворяет всем условиям задачи и может быть взято в качестве начального решения: X  ( х1  b1 ,..., хn  bm ; хn l  0) (14) где l  1, n  m Метод полного исключения очень громоздкий и его применение подчас бывает нецелесообразным. Далее осуществляется проверка решения на оптимальность, а в случае его не оптимальности переход к улучшенному решению. Если наименьшее значение Q достигается для нескольких базисных векторов, то чтобы исключить возможность зацикливания применяется следующий способ: вычитаются частные, полученные от деления всех элементов строк, давших одинаковое минимальное значение Q, на свои направляющие элементы. Полученные частные сопоставля- Эти преобразования целесообразно производить при записи системы линейных уравнений-ограничений в матричном виде. 4 Это значит, путем элементарных преобразований добиться такого положения, когда в каждое уравнение будет входить только одна из базисных величин с коэффициентом равным единице. 3 6 ются по столбцам слева на право, при этом учитываются и нулевые, и отрицательные значения. В процессе сравнения исключаются строки, в которых имеются большие отношения, и из базиса выводиться вектор, соответствующий строке, в которой раньше обнаружиться меньшее частное. 3. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСКУССТВЕННЫМ БАЗИСОМ Для применения этого метода ЗЛП должна быть сформулирована в канонической форме с добавлением таких соответствующих неотрицательных искусственных переменных, чтобы вновь полученная матрица содержала подсистему линейно-независимых векторов. Т.е. начальное решение должно быть найдено методом искусственного базиса. Метод «Искусственного базиса». Существо метода искусственного базиса для получения начального решения состоит в том, что вводятся вспомогательные переменные по числу линейных ограничений. Эти вспомогательные переменные с коэффициентом, равным единице, прибавляются к левым частям линейных ограничений. Ни в коем случае не надо путать эти вспомогательные переменные с дополнительными переменными приводящие линейные неравенства в равенства. В зависимости от того, максимизируется или минимизируется ЦФ, коэффициенты при вспомогательных переменных берутся со знаком «минус» или «плюс» соответственно. Для нахождения начального решения приравнивают неизвестные переменные хj к нулю, система линейных ограничений примет следующий вид: хn s  bi где (15) s  1, m Так как все bi  0, то полученное решение, которое удовлетворяет всем условиям задачи и может быть взято в качестве начального решения: X  ( х j  0; х n 1  b1 ,..., хn  m  bm ) (16) Этот метод получил наибольшее распространение, т.к. может быть применен для получения начального решения и в случае, когда все или часть линейных ограничений записаны в виде неравенств или уравнений. Далее в линейную форму исходной задачи добавляется слагаемое, представляющее собой произведение достаточно большого положительного числа М на сумму искусственных переменных. y   c j  x j  M  xn  s  min j s y   c j  x j  M  xn s  max j s , при xj  X (17) , при xj  X (18) Процедура нахождения оптимального решения принципиально не меняется от описанного выше метода. Различие заключается в том, что оценки j теперь будут зависеть от числа М и из базиса в первую очередь должны быть выведены все искусственные переменные путем 7 замены их на действительные переменные. Если все искусственные переменные вышли из базиса, то получаем исходную задачу. Если оптимальное решение содержит искусственные векторы, то исходная задача неразрешима. Путем преобразований число искусственных переменных иногда может быть уменьшено до одной. Т.к. при введении искусственного базиса берутся достаточно большие коэффициенты при вспомогательных величинах в ЦФ. То критерий оптимальности имеет вид:  j  g j  M  hj где (19) gj - равно действительной части суммы hj – коэффициент при постоянной части суммы. a i ij  ci  c j ; величине в этой действительной Поэтому алгоритм предусматривает ввод в базис той величины, которой соответствует положительное наибольшее значение hj. После вывода из базиса всех вспомогательных величин, дальнейшая процедура осуществляется выше описанным образом. Вспомогательная величина, выведенная на какой-то итерации из базиса, в дальнейших расчетах не участвует. ЗАКЛЮЧЕНИЕ Таким образом, в процессе изучения лекции Вы практически ознакомились с применением симплексного метода решения задачи линейного программирования. ЛИТЕРАТУРА а) Основная: 1. Экономико-математические методы и модели в управлении водным транспортом: Линейное программирование: Учебное пособие / под редакцией профессора В.А. Бабурина. СПБ.: СПГУВК, 2012. 206с. 2. Кремер Н.Ш., Исследование операций в экономике: Учебное пособие. М.: Юрайт, 2010. 432с. 3. Есипов Б.А., Методы исследования операций: Учебник для Вузов. М.: Лань, 2010. 256с. б) Дополнительная: 4. Кремер Н.Ш, Путко Б.А., Фридман М.Н., Исследование операций в экономике: Учебное пособие. М.: ЮНИТИ, 2006. 5. Хэмди А. Таха, Введение в исследование операций. М.: ВИЛЬЯМС, 2001. 6. Бережная Е.В, Бережной В.И., Математические методы моделирования экономических систем: Учебное пособие. М.: Финансы и кредит, 2001. 7. Вентцель Е.С., Исследование операций: Учебное пособие. М.: Советское радио, 1972. Профессор кафедры математического моделирования и прикладной информатики, к.в.н., доцент 31 августа 2020г. 8 А.А. БУРЫКИН