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

Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных переменных n-m>3, а затруднительна уже при n-m=3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод. Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.

Допустимое множество базисных решений системы линей­ных уравнений образует в объеме многогранное тело, например тетраэдр, вершины которого угловые точки.

Каждой угловой точке многогранника решений соответствует опорный план (допустимое базисное решение).

Количество перебираемых допустимых базисных решений можно сократить и проводить не беспорядочный перебор, а по­следовательный по специальному алгоритму, улучшая значение целевой функции.

В тех случаях, когда модель содержит m уравнений, для пост­роения опорных решений используются т переменных, прини­мающих некоторые положительные значения при нулевых зна­чениях остальных свободных переменных. Вычислительная процедура может быть представлена в виде следующей последо­вательности.

Итеративный переход от одного допустимого базисного ре­шения проводится направленно от одной вершины области допу­стимых решении к другой, заключающегося в обмене базисных и свободных переменных: базисная переменная приравнивается к нулю и переходит в свободную, а соответственно свободная пере­менная переводится на место базисной. Если в столбце свобод­ных членов все элементы положительны, то решение является допустимым. Если в строке целевой функции все элементы неот­рицательные, то решение является оптимальным при решении задачи на максимум.

В соответствии с симплексным методом на первом шаге нахо­дят начальное опорное решение — допустимый вариант, удовле­творяющий всем ограничениям. Затем последовательно за опре­деленное число итераций направленно осуществляется переход от одного опорного решения к другому вплоть до оптимального. Следует заметить, что на первом шаге в качестве базисных пере­менных следует выбрать такие т переменные, каждая из которых входит только один раз в одно из т уравнений системы, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. При этом если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены в пра­вых частях, то полученное базисное решение будет допустимым. В процессе решения системы линейных уравнений необходимо ориентироваться на сохранение неотрицательности всех пере­менных, поскольку это определяет допустимость решения.

Д ля использования рассмотренного алгоритма симплексного метода к минимизации линейной формы связи F(X) следует ис­кать максимум функции F₁(X)=- F(X), а затем полученное реше­ние взять с обратным знаком.

Предложенный алгоритм приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система линейных уравнений задачи сов­местна.

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

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется n переменных и m неза­висимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) до­стигается в одной из опорных точек, где по край­ней мере k=n-m из переменных равны нулю. Выберем ка­кие-то k переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k=n-m переменных x₁, x₂, …, x_k, а остальные т выражены через них:

(1)

Предположим, что все свободные переменные х₁, х₂, ..., х_к равны нулю.

При этом мы получим:

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены , неот­рицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптималь­ным? Чтобы проверить это, выразим целевую функцию Z через свободные переменные х₁, х₂, ..., х_к:

(2)

Очевидно, что при х₁ = х₂ = ... = х_к = 0, Z= ₀. Проверим, мо­жет ли быть улучшено решение, т. е. получено уменьшение функции Z c увеличением каких-нибудь из переменных х₁, х₂, ..., х_к (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты , , …, в (2) положительны, то увеличение каких-либо из переменных х₁, х₂, ..., х_к не может уменьшить Z; следовательно, найденное опорное решение является оптималь­ным. Если же среди коэффициентов , , …, есть отрицатель­ные, то, увеличивая некоторые из переменных х₁, х₂, ..., х_к (т.е, коэффициенты при которых отрицательны), мы можем улуч­шить решение.

Пусть, например, коэффициент в (2) отрицателен. Зна­чит, есть смысл увеличить х₁ т. е. перейти от данного опорного решения к другому, где переменная х₁ не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличивать х₁ следует с осторожностью, так чтобы не стали отрицательными другие пе­ременные x_k+l, x_k+2, ..., х_n, выраженные через свободные перемен­ные, в частности через x₁ формулами (1).

Например, если коэффициент при х₁ в соответствующем х_j уравнении (1) отрицателен, то увеличение x₁, может сделать х_j отрицательным. Наоборот, если среди уравнений (1) нет уравнения с отрицательным коэффициентом при x₁, то величину x₁ можно увеличивать беспредельно, а, значит, линейная функ­ция Z не ограничена снизу и оптимального решения 03 не су­ществует.

Допустим, что это не так и что среди уравнений (1) есть такие, в которых коэффициент при x₁ отрицателен. Для пере­менных, стоящих в левых частях этих уравнений, увеличение x₁ опасно — оно может сделать их отрицательными.

Возьмем одну из таких переменных x₁ и посмотрим, до какой степени можно увеличить x₁, пока переменная x₁ не станет отри­цательной. Выпишем l-е уравнение из системы (1):

Здесь свободный член 0, а коэффициент отрицателен. Легко понять, что если мы оставим х₂ = х₃ = ... = х_к = 0, то х₁ можно увеличивать только до значения, равного , а при дальнейшем увеличении х₁ переменная х₁ станет отрицательной.

Выберем ту из переменных x_k+l, x_k+2, ..., х_n, которая раньше всех обратится в нуль при увеличении х₁, т. е. ту, для которой ве­личина наименьшая. Пусть это будет х₁ . Тогда имеет смысл разрешить систему уравнений (1) относительно других базис­ных переменных, исключая из числа свободных переменных х₁ и переводя вместо нее в группу свободных переменных х_r. Дейст­вительно, мы хотим перейти от опорного решения, задаваемого равенствами х₁ = х₂ = ... = х_к = 0, к опорному решению, в котором уже , а х₂ = ... = х_к = х_r. = 0. Первое опорное решение мы по­лучили, положив равными нулю все прежние свободные пере­менные х₁, х₂, ..., х_к, второе мы получим, если обратим в нуль все новые свободные переменные х₂, х₃, ..., х_к, х_r.

Базисными переменными при этом будут x₁, x_k+1, x_k+2, …, x_r-1, x_r+1, …, x_n.

Предположим, что уравнения типа (1) для нового набора базисных и свободных переменных составлены. Тогда можно выразить через новые свободные переменные и линейную функ­цию Z. Если все коэффициенты при переменных в этой формуле положительны, то мы нашли оптимальное решение: оно полу­чится, если все свободные переменные положить равными нулю. Если среди коэффициентов при переменных есть отрицатель­ные, то процедура улучшения решения продолжается: система вновь разрешается относительно других базисных переменных, и так далее, пока не будет найдено оптимальное решение, обра­щающее функцию Z в минимум.

Рассмотрим алгоритм симплексного метода на примере решения задачи пла­нирования товарооборота предприятия торговли.

К оммерческое предприятие реализует n товарных групп, рас­полагая m ограниченными материально-денежными ресурсами b_i> 0 (i=1,m). Известны расходы ресурсов каждого i-вида на ре­ализацию единицы товара по каждой группе, представленной в виде матрицы А = (a_ij), и прибыль с_ij получаемая предприятием от реализации единицы товара j-группы. Необходимо определить объем и структуру товарооборота х_j (j=1,n), при ко­торых прибыль коммерческого предприятия была бы максималь­ной.

Математическую модель задачи запишем следующим обра­зом. Определить вектор Х = (х_их₂, …,х_п), который удовлетворяет ограничениям вида:

и обеспечивает максимальное значение целевой функции:

Алгоритм симплексного метода включает следующие этапы:

1. Составление первого опорного плана. Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «<», правые части которых b_i> 0. Перейдем от системы неравенств к системе уравнений путем введения неотри­цательных дополнительных балансовых переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:

где - дополнительные переменные,

х_j- базисные переменные,

Решим эту систему относительно дополнительных перемен­ных:

,

а функцию цели перепишем в виде уравнения

Следует заметить, что опорным решением называется базис­ное неотрицательное решение.

Полагая, что основные переменные x₁ =х₂ =х₃ = ... х_п = 0, по­лучим допустимое базисное решение - опорный план Х₁ = (0, 0, ..,, 0, b_ь b₂, ..., b_m); F(X₁) = 0, который заносим в симплексную таблицу. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком.

2. Проверка плана на оптимальность. Если значение базисных переменных неотрицательны, то решение является допустимым. Если все коэффициенты индексной строки симплексной табли­цы при решении задачи на максимум неотрицательны ( 0), то план является оптимальным. Если найдется хотя бы один коэф­фициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.

3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбираем наибольший по аб­солютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные.

Затем элементы столбца свободных членов симплексной таб­лицы делим на элементы того же знака (⁺/+; -/-) ведущего столб­ца. Результаты заносим в отдельный столбец Q_i, которые должны быть всегда положительны. Строка симплексной таблицы, соот­ветствующая минимальному значению Q_i, является ведущей. Она и определяет переменную x_i, которая на следующей итерации выйдет из базиса и станет свободной (обмен).

Элемент симплексной таблицы, находящийся на пересече­нии ведущих столбца и строки, называют разрешающим и выде­ляют, например, кружком.

4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы ме­тодом Жордана — Гаусса. Сначала заменим переменные в базисе, т.е. вместо x_i в базис войдет переменная х_j, соответствующая веду­щему столбцу (замена).

Разделим все элементы ведущей строки предыдущей симп­лексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответству­ющей введенной в базис переменной x_j. В результате этого на ме­сте разрешающего элемента в следующей симплексной таблице запишем 1, а в остальных клетках у столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

,

где СТЭ - элемент старого плана;

РЭ – разрешающий элемент;

А и В – элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Далее возвращаемся ко второму этапу алгоритма - проверке плана на оптимальность.

При решении задачи линейного программирования на мини­мум целевой функции признаком оптимальности плана являют­ся отрицательные значения всех коэффициентов индексной стро­ки симплексной таблицы.

Если_в ведущем столбце все коэффициенты a_ij < 0, то функция цели F( ) не ограничена на множестве допустимых планов, т.е. и задача не имеет решения.

Если в столбце Q_i - симплексной таблицы содержатся два или несколько одинаковых наименьших значений, то новый опор­ный план будет вырожденным (одна или несколько базисных пе­ременных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. В таких случаях для выбора ведущей строки используют ме­тод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения Q_i, делятся на пред­полагаемые разрешающие элементы, а результаты заносятся в до­полнительные строки. За ведущую строку выбирается та, в кото­рой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.

Если в оптимальный план вошла дополнительная переменная х_п+1, то при реализации такого плана имеются недоиспользован­ные ресурсы i-го вида в количестве, полученном в столбце сво­бодных членов симплексной таблицы.

Если в индексной строке симплексной таблицы оптимально­го плана находится нуль, принадлежащий свободной перемен­ной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соот­ветствующую указанному столбцу, можно внести в базис, выпол­нив соответствующие этапы алгоритма. В результате будет полу­чен второй оптимальный план с другим набором базисных пере­менных.