Симплекс метод

этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи ЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу ЛП к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
Стандартная форма задачи ЛП необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.

разделе мы сначала рассмотрим стандартную форму записи задачи линейного программирования, а затем покажем, как определить базисное решение.
Стандартная форма задачи ЛП
Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.
1. Все ограничения (включая ограничения не отрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
2. Все переменные неотрицательные.
3. Целевую функцию следует или максимизировать, или минимизировать.
1. ПРЕОБРАЗОВАНИЕ НЕРАВЕНСТВ В РАВЕНСТВА. Неравенства любого типа (со знаками неравенств ≤ или ≥) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных — остаточных или избыточных (см. определения этих переменных в разделе 2.3.3).
Пример неравенства типа "≤". Неравенство x1 + 2х2 ≤ 3 эквивалентно равенству x1 + 2х2 + s1 = 3, где s1 — остаточная переменная и s1 ≥ 0.
Пример неравенства типа "≥". Неравенство 3x1 + х2 ≥ 5 эквивалентно равенству 3x1 + х2 + S1 = 5, где S1 — избыточная переменная и S1 ≥ 0.
Правую часть равенства всегда можно сделать неотрицательной путем умножения всего равенства на -1. Кроме того, заметим, что неравенство типа "≤" также преобразуется в неравенство типа "≥" посредством умножения обеих частей неравенства на -1. Например, неравенство 2 < 4 после умножения на -1 становится неравенством -2 > -4.

которая может принимать как отрицательные, так и положительные значения) можно представить как разность двух неотрицательных переменных следующим образом.xj = xj+ - xj-, где xj+, xj- ≥ 0
Например, для xj = - 5 положим xj+ = 0 и xj- = 5. Если же xj = +5, тогда xj+ = 5 и xj- = 0. В обоих случаях переменные xj+ и xj- неотрицательны.
Такое преобразование свободных переменных следует выполнить во всех неравенствах и в целевой функции. После решения задачи с переменными xj+ и xj- значения исходных переменных восстанавливаются с помощью обратной подстановки.
3. ПРЕОБРАЗОВАНИЕ ЗАДАЧИ МАКСИМИЗАЦИИ В ЗАДАЧУ МИНИМИЗАЦИИ. Задача максимизации функции f(х1, х2, ..., хn) эквивалентна задаче минимизации функции - f(х1, х2, ..., хn), поскольку при решении обеих задач предоставляется один и тот же набор значений переменных х1, х2, ..., хn.
Пример 3.2-1
Преобразуем следующую задачу ЛП в стандартную форму.
Максимизировать
z = 2x1 + 3х2 + 5х3
при выполнении условий
x1 +х2 - х3 ≥ - 5,
- 6x1 + 7х2 - 9х3 ≤ 4,
x1 +x2 + 4х3 = 10,
х1, х2 ≥ 0,
х3 — свободная переменная.

из левой части первого неравенства дополнительную (избыточную) переменную S1 и затем умножим все неравенство на -1, для того чтобы правая часть неравенства стала положительной. (Другой путь преобразования неравенства: сначала умножим его на -1 — неравенство примет вид "≤" вместо "≥", далее к левой части неравенства прибавим дополнительную (остаточную) переменную s1)
2. Добавим дополнительную (остаточную) переменную s2 к левой части второго неравенства.
3. Так как третье ограничение изначально записано в виде равенства, поэтому оставляем его без изменения.
4. Выполняем замену x3 = x3+ - x3-, где x3+, x3- ≥ 0, во всех ограничениях и целевой функции.
Получаем следующую стандартную задачу линейного программирования.
Максимизировать
z = 2х1 + 3х2 + 5x3+ -5x3-
при выполнении следующих условий
-x1 - x2 + x3+ - x3- + x4 = 5,
- 6х1 + 7x2 – 9x3+ + 9x3- + x5 = 4,
x1 + x2 + 4x3+ -4x3- = 10,
x1, x2, x3+, x3-, x4, x5 ≥ 0.

содержит m линейных равенств с п неизвестными переменными (m < n). Разделим n переменных на два множества: (1) n - m переменные, которые положим равными нулю, и (2) оставшиеся m переменные, значения которых определяются как решение системы из m линейных уравнений. Если это решение единственное, тогда соответствующие m переменные называются базисными, а остальные n - m нулевые переменные — небазисными. В этом случае результирующие значения переменных составляют базисное решение. Если все переменные принимают неотрицательные значения, то такое базисное решение является допустимым. В противном случае — недопустимым.
Основываясь на этих определениях, нетрудно подсчитать, что количество всех положительных базисных решений для m уравнений с n неизвестными не превосходит
,
где через обозначаются биномиальные коэффициенты .
Пример 3.2-2
Рассмотрим следующую систему двух уравнений с пятью неизвестными (m = 2, n = 5)
х1 + x2 + 4x3 +2x4 +3x5 = 8,
4х1 + 2x2 + 2x3 + x4 + 6x5 = 4
Определим различные решения этой системы. Количество положительных базисных решений равно . Ниже мы покажем, что некоторые из этих решений на самом деле не будут базисными.
По определению базисное решение включает только две (= m) переменные, предполагая, что небазисных нулевых переменных три (= n - m).

+ 4x3 = 8,
4x1 + 2x3 = 4.
Решение: единственное решение х1 = 0, х3 = 2.
Заключение: базисное решение допустимо, так как х1, х3 ≥ 0.
Случай 2. Недопустимое базисное решение.
Нулевые (небазисные) переменные: x3, х4 и x5.
Уравнения: х1 + x2 = 8,
4x1 + 2х2 = 4.
Решение: единственное решение x1 = - 6, x3 = 14.
Заключение: базисное решение недопустимо, так как х1 < 0.
Случай 3. Решение не единственное.
Нулевые (небазисные) переменные: х1, х2 и x5.
Уравнения: 4х3 + х4 = 8,
2х3 + х4 = 4.
Решение: единственного решения не существует, так как уравнения зависимы (если первое уравнение разделить на 2, то получим второе уравнение).
Заключение: бесконечное количество решений.
Случай 4. Решения не существует.
Нулевые (небазисные) переменные: x1, х3 и x4.
Уравнения: х2 + 3х5 = 8,
2x2 + 6x5 = 4.
Решение: решения не существует, так как уравнения несовместны.
Заключение: решения не существует.

разделе 2.3.2. Затем в разделе 3.2.1 показали, что в стандартной форме записи задачи ЛП свободная переменная xj, должна быть представлена как разность двух неотрицательных переменных:
xj = xj+ - xj-, xj+, xj- ≥ 0
Основываясь на определении базисного решения из раздела 3.2.2, нетрудно показать, что невозможна ситуация, когда xj+ и xj- одновременно будут базисными переменными, что вытекает из их зависимости. В свою очередь, их зависимость следует из того, что в ограничении коэффициент при xj+ имеет знак, противоположный знаку коэффициента при xj-. Это означает, что в любом базисном решении, по крайней мере, одна из переменных xj+ и xj- должна быть небазисной, т.е. нулевой.

найти оптимальное решение задачи линейного программирования, записанной в стандартной форме, путем простого перебора всех базисных (допустимых) решений. Но, конечно, такая процедура не эффективна. Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений.
Алгоритм симплекс-метода всегда начинается с некоторого допустимого базисного решения и затем пытается найти другое допустимое базисное решение, улучшающее" значение целевой функции. Это возможно только в том случае, если возрастание какой-либо нулевой (небазисной) переменной ведет к улучшению значения целевой функции. Но для того, чтобы небазисная переменная стала положительной, надо одну из текущих базисных переменных сделать нулевой, т.е. перевести в небазисные. Это необходимо, чтобы новое решение содержало в точности m базисных переменных. (Напомним, что нас интересуют только базисные решения, содержащие в точности m базисных переменных.) В соответствии с терминологией симплекс-метода выбранная нулевая переменная называется вводимой (в базис), а удаляемая базисная переменная — исключаемой (из базиса).
Вычисление нового базисного решения основывается на методе исключения переменных (методе Гаусса-Жордана). В следующей таблице, которая пока совпадает с начальной таблицей задачи ЛП, определим ведущий столбец, ассоциируемый с вводимой переменной, и ведущую строку, ассоциируемую с исключаемой переменной. Элемент, находящийся на пересечении ведущего столбца и ведущей строки, назовем ведущим.
Оптимальное решение задачи ЛП можно "считать" из симплекс-таблицы следующим образом. Неотрицательные (базисные) переменные представлены в столбце "Базис", а их значения — в столбце "Решение".
В случае минимизации целевой функции, исключаемые переменные определяются точно так же, как и при максимизации целевой функции. Задача минимизации сводится к задаче максимизации простым соотношением max z = - min (-z). Поэтому в случае минимизации целевой функции вводимая переменная выбирается как небазисная с наибольшим положительным коэффициентом в z - строке симплекс-таблицы, а минимум целевой функции будет достигнут тогда, когда все коэффициенты в z - строке будут неположительные

симплекс-метода.
Эта задача в стандартной форме записывается так:
Максимизировать
z = 5х1 + 4х2 + 0s1 + 0s2 + 0s3 + 0s4
при ограничениях
6x1 + 4x2 + s1 = 24,
1x1 + 2x2 +s2 = 6,
- x1 + x2 +s3 = 1,
х2 + s4 = 2,
х1, х2, s1, s2, s3, s4 ≥ 0.
Здесь s1, s2, s3, s4 — дополнительные (остаточные) переменные, добавленные в неравенства для преобразования их в равенства.
Задачу ЛП в стандартной форме можно представить в виде следующей компактной таблицы:

частей этих равенств даны в столбце "Решение". Строка z получена из равенства z - 5х1 - 4х2 = 0.
Дополнительные переменные s1, s2, s3 и s4 составляют очевидное начальное допустимое базисное решение, при этом, поскольку небазисные переменные x1 и х2 равны нулю, их значения автоматически отображаются в столбце "Решение": s1 = 24, s2 = 6, s3 = 1 и s4 = 2. Значение целевой функции при этом решении равно нулю.
Два правила выбора вводимых и исключающих переменных в симплекс-методе назовем условием оптимальности и условием допустимости. Сформулируем эти правила, а также рассмотрим последовательность действий, выполняемых при реализации симплекс-метода.
Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая наибольший отрицательный (положительный) коэффициент в z - строке. Если в z - строке есть несколько таких коэффициентов, то выбор вводимой переменной делается произвольно. Оптимальное решение достигнуто тогда, когда в z - строке все коэффициенты при небазисных переменных будут неотрицательными (неположительными).
Условие допустимости. Как в задаче максимизации, так и в задаче минимизации, в качестве исключаемой выбирается базисная переменная, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если базисных переменных с таким свойством несколько, то выбор исключаемой переменной выполняется произвольно.

начальное допустимое базисное решение.
Шаг 1. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.
Шаг 2. На основе условия допустимости выбирается исключаемая переменная.
Шаг 3. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 1.
Вычисления в симплекс-методе выполняются итерационно в том смысле, что условия оптимальности и допустимости, а также вычисления применяются к текущей симплекс-таблице, в результате чего получается следующая таблица. Мы будем называть последовательные симплекс-таблицы итерациями.
Отслеживание последовательных базисных решений из примера 3.3-1 по графическому представлению пространства решений (рис. 3.1) показывает, что итерационный процесс симплекс-метода начался в крайней (угловой) точке А, затем переместился в крайнюю точку В и закончился в крайней точке С — точке оптимума. Эти итерации соответствуют смежным крайним точкам границы пространства решений. Алгоритм симплекс-метода никогда не сможет переместиться сразу из точки А в точку С. (См. раздел 7.8, где описан алгоритм, использующий внутренние точки пространства решений.)

являются неравенствами типа "≤" (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа "≥"?
Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод и двухэтапный метод.
М-метод
Пусть задача ЛП записана в стандартной форме. Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Ri„ которая далее войдет в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.
Переменная Ri, с помощью достаточно большого положительного числа M, штрафуется путем ввода в целевую функцию выражения -MRi в случае максимизации целевой функции и выражения + MRi — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Ri. Следующий пример проясняет детали этого метода.

условий
3x1 + х2 = 3,
4x1 + 3х2 ≥ 6,
x1 + 2х2 ≤ 4,
x1, x2 ≥ 0.
Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной х3 во второе неравенство и дополнительной (остаточной) переменной х4 в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.
Минимизировать z = 4х1 + х2
при выполнении условий
3x1 + х2 = 3,
4x1 + 3х2 - x3 = 6,
x1 + 2х2 + x4 = 4,
x1, x2 x3, x4 ≥ 0.
В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MR1 + МR2. В результате получим следующую задачу ЛП.
Минимизировать z = 4х1 + х2 + MR1 + МR2
при выполнении условий
3x1 + х2 + R1 = 3,
4x1 + 3х2 - x3 + R2 = 6,
x1 + 2х2 + x4 = 4,
x1, x2 x3, x4, R1, R2 ≥ 0.

использовать в качестве начального допустимого базисного решения. В результате получим следующую симплекс-таблицу.
Прежде чем применять симплекс-метод, надо согласовать значения в z - строке с остальной частью таблицы. В частности, значение функции z, соответствующее начальному базисному решению R1 = 3, R2 = 6 и х4 = 4, должно равняться 3M + 6M + 0 = 9M, а не 0, как показано в таблице. Это несоответствие связано с тем, что переменным R1 и R2 соответствуют ненулевые коэффициенты (-M, -М) в строке z (сравните с начальным решением в примере 3.3-1, где дополнительным переменным соответствуют нулевые коэффициенты в z - строке). Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк R1 и R2 на величину M, и затем сложить эти строки с z - строкой. (Обратите внимание на "подсвеченные" единицы в этих строках — если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты.) Кратко это действие можно записать следующим образом.
Новая z - строка = Старая z - строка + M × R1 - строка + M × R2 – строка
Выполним эту операцию в данном примере.
Старая z – строка: (-4 - 1 0 -M -M 0| 0)
M × R1 – строка: (3M M 0 M 0 0|3M)
M × R2 – строка: (4M 3M –M 0 M 0|6M)
Новая z – строка: (-4 +7M -1+4 M -M 0 0 0|9M)

что соответствует базисному решению R1 = 3, R2 = 6 и x4 = 4.
Последняя таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости. Поскольку мы минимизируем целевую функцию, находим наибольший положительный коэффициент в z - строке. Наибольший коэффициент -4 + 7M соответствует переменной x1, которая и будет вводимой. Условие допустимости указывает на переменную R1 в качестве исключаемой.
Поскольку вводимая и исключаемая переменные определены, новую симплекс-таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вычисления в z - строке, где присутствует M, следует проводить алгебраически. Так, для получения новой z - строки надо новую ведущую строку умножить на -(-4 + 1М) и сложить с текущей z - строкой. В результате получим следующую таблицу.

переменную R1, что является результатом включения штрафа в целевую функцию.
Последняя таблица показывает, что следующими, вводимой и исключаемой, переменными будут x2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет х1 = 2/5, х2 = 9/5, x3 = 1 и z = 17/5 (см. упр. 3.4,а(1)).
При использовании M-метода следует обратить внимание на следующие два обстоятельства.
1. Использование штрафа M может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения.
2. Теоретически применение M-метода требует, чтобы M →∝. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин "достаточно большая" — это открытый вопрос. Величина M должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа. Эту проблему иллюстрирует следующий пример.

M-методе вследствие ошибок округления. Двухэтапный метод полностью лишен тех недостатков, которые присущи M-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведется поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.
Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в M-методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.
Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.
Пример 3.4-3
К задаче из примера 3.4-1 применим Двухэтапный метод.
Этап 1.
Минимизировать
r = R1 + R2
При ограничениях
3x1 +x2 + R1 = 3,
4x1 +3x2 – x3 + R2 = 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4, R1, R2 ≥ 0

новая r - строка.
Новая r – строка r + 7x1 + 4x2 – x3 +0R1 +0R2 + 0x4 = 9 используется для решения задачи первого этапа, что приведет к следующему оптимальному решению (проверьте!)
Поскольку достигнут минимум r = 0, значит, на первом этапе получено допустимое базисное решение x1 = 3/5, x2 = 6/5 и x4 = 1. Искусственные переменные полностью выполнили свою "миссию", поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.

следующим образом.
Минимизировать z = 4х1 + х2
с ограничениями
Обратите внимание, что после первого этапа исходная задача претерпела некоторые изменения, которые учитывают полученное базисное решение. Этой трансформированной задаче соответствует следующая таблица.
Поскольку базисные переменные х1 и х2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать.
Начальная таблица второго этапа примет следующий вид.