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

4.7.1. Идея симплекс-метода. Как отмечалось в п.4.1?, допустимая область задачи линейного программирования (заданной в любой форме: стандартной, канонической, общей) представляет собой многогранное множество, а решение задачи (если оно существует) находится в одной или нескольких его вершинах (и если в нескольких, – то и на всей грани, содержащей эти вершины). Исходя из этого, можно было бы предложить метод решения задачи линейного программирования, заключающийся в переборе всех вершин многогранного множества и сравнении значения целевой функции в них. Решением задачи была бы та вершина (те вершины и содержащая их грань), где значение целевой функции максимально (минимально). Однако такой способ решения для реальных экономических задач, содержащих большое число переменных и ограничений, практически неприемлем. Напомним, что вершиной многогранного множества в -мерном пространстве является точка, которая лежит на пересечении как минимум гиперплоскостей. Пусть, например, в канонической записи задачи (или в стандартной – это не важно) имеется переменных, линейно независимых уравнений-ограничений (линейно зависимые можно исключить) и, естественно, ограничений неотрицательности

(1)

Тогда для нахождения вершин допустимого множества нужно решить всевозможные системы линейных уравнений, содержащие уравнений вида из задачи (1) и . Число таких различных систем будет, очевидно, равно , что, например, уже при составляет около двухсот тысяч. Кроме того, каждую найденную точку необходимо проверить на допустимость, т.е. подставить ее в остальные уравнения и неравенства (не вошедшие в решаемую систему) и проверить их справедливость.

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

Но идея целенаправленного перебора нашла свое воплощение в так называемом симплекс-методе (или симплексном методе). Эта идея была реализована в 1947 году американским математиком Джорджем Данцигом.

Решение задачи линейного программирования симплекс-методом осуществляется в два этапа:

· на первом этапе находится одна из вершин многогранного множества – точка, удовлетворяющая всем ограничениям задачи, т.е. некоторое допустимое решение;

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

При этом возможны два вырожденных случая:

1) если многогранное множество не ограничено, то задача может (но не обязательно) не иметь решения: можно двигаться вдоль ребра многогранного множества, улучшая значение целевой функции до бесконечности, не встречая вершины (см. рис.2).;

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

Алгоритм симплекс-метода учитывает оба этих случая: в первом случае он выдает информацию об отсутствии решения задачи; во втором – предпринимаются специальные меры, исключающие зацикливание.

4.7.2. Понятие симплекса. Название «симплекс-метод» происходит от слова «симплекс».

Определение

Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств содержащих (): .

Например, выпуклой оболочкой невыпуклого четырехугольника (см. рис.4) будет треугольник (доказать!).

	Рис.4. Пример выпуклой оболочки

Очевидно, выпуклой оболочкой выпуклого множества будет само это множество (доказать!)

Определение

Пусть - точки из -мерного арифметического пространства , , причем векторы линейно независимы. Тогда выпуклая оболочка точек называется -мерным симплексом.

Проиллюстрируем данное определение на примерах.

Пусть . Тогда имеем только две точки: и , причем , так как иначе вектор , что означало бы его линейную зависимость. Пространство может быть любой размерности (). Выпуклой оболочкой множества, состоящего из двух различных точек (одномерным симплексом), очевидно, будет отрезок, соединяющий эти две точки (доказать!).

Пусть . В этом случае имеем три различные точки в пространстве размерности 2 или более. Причем векторы не должны быть коллинеарными. Выпуклой оболочкой точек (двумерным симплексом), очевидно, будет треугольник в соответствующем пространстве (доказать!) - см. рис.5.

Пусть . В этом случае имеем четыре различные точки в пространстве размерности 3 или более. Причем векторы не должны быть компланарными. Выпуклой оболочкой точек (трехмерным симплексом), очевидно, будет тетраэдр в соответствующем пространстве (доказать!) – см. рис.6.

Заметим, что симплекс – выпуклое, замкнутое, ограниченное множество.

Посмотрим, какое отношение имеет симплекс к методу решения задач линейного программирования.

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

.

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

Множество функциональных ограничений представляет собой систему линейных уравнений относительно неизвестных. Как известно из линейной алгебры, если , то либо среди ограничений есть «лишние» – линейно зависимые от других (и их можно отбросить – на решение задачи они не повлияют), либо система несовместна, т. е. задача не имеет решений. Если , то система имеет либо единственное решение, либо несовместна. В первом случае допустимая область вырождается в точку, которая и будет представлять единственное допустимое и, одновременно, оптимальное решение. Во втором случае допустимое множество пусто. Указанные случаи интереса не представляют, поскольку задача вырождается, что с практической точки зрения скорее всего свидетельствует о ее неправильной постановке. Таким образом, будем считать, что . В этом случае, правда, допустимое множество тоже может оказаться пустым, если система окажется несовместной, что также будет свидетельствовать о неправильной, противоречивой постановке задачи. При нормальной же постановке допустимое множество представляет собой линейное многообразие размерности , ограниченное первым ортантом. Таким образом, границы допустимого множества всегда лежат на границах первого ортанта . Рассмотрим подробнее, как выглядят допустимые множества для малых размерностей, допускающих наглядную иллюстрацию.

Пусть имеем одно ограничение: и два неизвестных: . В этом случае ограничение представляет собой прямую на плоскости. Если при этом учесть ограничения неотрицательности переменных, то будем иметь либо пустое множество (что не интересно), либо отрезок (см. рис.7а), либо луч (см. рис.7б).

В первом случае мы имеем дело с одномерным симплексом, во втором – допустимое множество не ограничено (симплексом не является).

Пусть имеем одно ограничение: и три неизвестных: . В этом случае ограничение представляет собой плоскость в трехмерном пространстве. Если при этом учесть ограничения неотрицательности переменных, то будем иметь либо пустое множество (что не интересно), либо треугольник (см. рис.8а), либо неограниченную фигуру – угол (рис.8б) или «корыто» (рис.8в).

В случае треугольника имеем двумерный симплекс. В остальных – неограниченное множество.

Пусть имеем два ограничения: и три неизвестных: . В этом случае ограничения представляют собой две плоскости в трехмерном пространстве. Будем считать, что они пересекаются (в пересечении образуют прямую линию), иначе допустимое множество будет пустым. Если при этом учесть ограничения неотрицательности переменных, то будем иметь либо пустое множество (что не интересно), либо отрезок (рис.9а), либо луч (рис.9б).

Таким образом, мы видим, что допустимая область в задаче линейного программирования, заданной в канонической форме, либо не ограничена, либо представляет собой симплекс. В связи с этим следует отметить, что возможный вид допустимых областей в задачах линейного программирования, заданных в канонической форме, весьма специфичен и значительно менее разнообразен, чем в задачах, заданных в стандартной форме. Так, например, если в двумерной задаче (на плоскости) каноническая форма допускает лишь отрезки и лучи, то стандартная форма – любые выпуклые многоугольники и неограниченные выпуклые многоугольные множества. Обратим внимание также, что на рис. 1 – 3 приведены иллюстрации для задач, ограничения в которых записаны в виде неравенств, поскольку любое ограничение в виде равенства снижает размерность допустимой области (как минимум) на единицу, а значит, в этом случае на плоскости могут быть только линии, в трехмерном пространстве – плоские фигуры (да и то не всякие) или линии.

Отметим также, что для одной и той же (по сути) задачи линейного программирования размерность (число переменны) ее канонической формы всегда не ниже размерности стандартной формы. Чаще всего при моделировании экономической задачи ограничения задаются в виде неравенств. Проиллюстрируем на простейшем примере различие в виде допустимых множеств для задачи линейного программирования, заданной в стандартной и канонической формах.

Пример

Пусть имеем задачу линейного программирования в стандартной форме (рис.10а):

Стандартный перевод ее в каноническую форму даст (рис.10б):

.

Как видно из рис.10, размерность допустимой области для задачи, заданной в стандартной форме, совпадает с размерностью пространства («плоский» треугольник на плоскости), а размерность допустимой области для задачи, заданной в канонической форме, на единицу меньше размерности пространства («плоский» треугольник в трехмерном пространстве).

4.7.3. Пример решения задачи симплекс-методом. Для иллюстрации идейной стороны симплекс-метода продемонстрируем работу его алгоритма (в упрощенном варианте) на решении простой задачи с графической иллюстрацией его шагов.

Пример 1

Пусть имеем задачу линейного программирования в стандартной форме:

(2)

Изобразим допустимое множество (рис.11). Очевидно, оно будет неограниченным.

Приведем задачу к каноническому виду. Для этого из левых частей функциональных ограничений-неравенств вычтем неотрицательные невязки и :

(3)

Обратим внимание, что если в точке ограничение (2.1) является активным, т.е. точка находится на соответствующей грани допустимого множества, то невязка . Аналогично, если активным является ограничение (2.2), то . Если точка находится на ребре допустимого множества, лежащего на пересечении этих граней, то обе невязки равны нулю. Если же точка является вершиной многогранного множества (например, ), то три переменные в задаче (3) обращаются в нуль (в данном случае , и ). Таким образом, переход от одной вершины допустимого множества к другой формально осуществляется путем вывода одной из переменных задачи (3) из разряда нулевых (такие переменные называют свободными) и ввода какой-либо из «ненулевых» переменных (такие переменные называют базовыми) в разряд нулевых, т.е. базовая и свободная переменные обмениваются местами («статусом»). При этом в каждой вершине хотя бы три переменные обращаются в нуль1.

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

Чтобы проиллюстрировать существо метода и его формальную сторону будем каждый шаг алгоритма сопровождать тремя действиями: 1) показом на графике, 2) фактическими расчетами на системе ограничений и 3) манипуляцией на таблице. Для этого перепишем задачу (3) в виде (то, что мы функцию минимизируем и все переменные неотрицательны, будем помнить, а записывать не будем):

(4)

или, что то же самое (нужно для заполнения таблицы):

(5)

Кроме того, составим соответствующую таблицу коэффициентов (см.табл.1).

Таблица 1

		– 8	– 10	– 10
	– 4000	– 50	– 100	– 100
	– 5000	– 100	– 50	– 100

Итак, сначала нужно попасть в допустимое множество (шаг 1).

Шаг 1. Начнем движение из начала координат – точка . Из рис.11 непосредственно видно, что точка не принадлежит допустимому множеству. Однако вычислительный алгоритм рисунком не располагает – этот факт нужно установить формально. Вспомним, что все переменные должны быть неотрицательными, и подставим координаты точки в систему (4). Мы увидим, что переменные и отрицательны. В таблице об этом свидетельствует столбец – стоящие в нем коэффициенты отрицательны (если хотя бы один коэффициент отрицателен, точка не принадлежит допустимому множеству). Таким образом, заключаем, что точка не принадлежит допустимому множеству.

Как попасть в допустимое множество? Будем двигаться вдоль какой-либо из осей в положительном направлении в надежде попасть в некоторую вершину допустимого множества. Заметим, что это не всегда удается, а именно – если допустимое множество не имеет общих точек с осями. Очевидно, указанное движение целесообразно только в том случае, если коэффициент при соответствующей переменной в уравнении из (4) положителен (в таблице, наоборот, – отрицателен). В противном случае мы только уменьшим базисную переменную, стоящую в левой части равенства. Если же в строке с отрицательным значением коэффициенты при всех свободных переменных в уравнении из (4) неположительны, то это означает, что мы не можем сделать соответствующую базисную переменную неотрицательной, а значит, задача не имеет решения. В нашем же случае, как это видно из рис.11, движение вдоль любой оси приводит в вершину допустимого множества – в точку , или .

Что означает такое движение формально? Это означает, что одну из координат мы начинаем увеличивать, причем увеличиваем ее до тех пор, пока все переменные не станут неотрицательными. Попробуем увеличивать переменную (оставляя нулевыми и ). Очевидно, для того, чтобы переменные и стали неотрицательными, нужно, чтобы , т.е. . При этом, чтобы попасть в вершину многогранного множества, нужно, чтобы хотя бы одно из этих неравенств выполнялось как равенство (как минимум, три переменные должны быть нулевыми). Таким образом, нужно взять 1.

Таблично это оформляется так: коэффициенты из столбца делятся на отрицательные коэффициенты из выбранного (так называемого разрешающего)столбца (), и результаты заносятся в соответствующие клетки разрешающего столбца () – см. таблицу 2.

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

Таблица 2

		– 8	– 10	– 10
	– 4000	– 50	– 100	– 100
	– 5000	– 100	– 50	– 100

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

Таким образом, мы можем увеличивать значение до 80. При этом все переменные станут неотрицательными, причем переменная станет положительной, а переменная станет равной нулю. Это означает, что мы попадем в точку . Поскольку алгоритм на каждом шаге должен работать с однотипными по форме и содержанию элементами, то в системе (4) в правой части равенств должны стоять переменные, принимающие нулевые значения (свободные переменные). Аналогично, столбцы таблицы должны соответствовать переменным с нулевыми значениями. Это значит, что переменные и должны поменяться местами, т.е. нужно выразить через . Вычисления дают:

(6)

Соответствующие преобразования в таблице осуществляются по следующим правилам:

1. Разрешающий элемент заменяется на 1.

2. Остальные элементы разрешающей строки остаются без изменения.

3. Остальные элементы разрешающего столбца умножаются на (-1);

4. Все оставшиеся элементы преобразуются по формуле .

5. Все элементы полученной таблицы делятся на .

В нашем случае после преобразований 1 – 4 получаем (см. табл.3):

Таблица 3

	-32 000		– 300	– 300
	– 4000		– 100	– 100
	– 150 000		– 7500	– 5 000

После преобразования 5 будем иметь (см. табл.4):

Таблица 4

	3 000	-2

Шаг 2. Поскольку мы уже попали в вершину допустимой области, т.е. получили опорное решение, перейдем теперь к процессу уменьшения значения целевой функции. По рис.11 видно, что мы можем двигаться либо в точку , либо в точку . Из анализа системы (6) видно, что уменьшить значение целевой функции можно за счет увеличения значения переменных или , поскольку обе они входят в выражение для функции с отрицательными коэффициентами. Можно выбрать любую из этих переменных.

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

, или ,

причем одно из них должно выполняться как равенство. Значит, , и мы получаем точку . Переменная переходит в разряд базисных, а переменная – в разряд свободных. Выражаем новые базовые переменные через новые свободные:

(7)

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

Таблица 5

			2
	3 000	-2	150

После выбора разрешающего элемента проводим преобразования 1 – 4 (см. табл.6):

Таблица 6

	78 000	-12	-6
			-2
	3 000	-2

После преобразования 5 будем иметь (см. табл.7):

Таблица 7

Шаг 3. Каквидно из таблиц 4 и 7, значение целевой функции после выполнения шага 2 уменьшилось с 640 до 520. Посмотрим, можем ли мы еще уменьшить ее значение. Из (7) видно, что уменьшить ее значение можно за счет увеличения значения переменной (напомним, что пока ). Аналогично шагу 2 получим:

,

т.е. значение переменной мы можем увеличивать до 30.

Таким образом, , и мы получаем точку . Переменная переходит в разряд базисных, а переменная - в разряд свободных. Выражаем новые базисные переменные и целевую функцию через новые свободные переменные:

(8)

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

После выбора разрешающего элемента проводим преобразования 1 – 4 (см. табл.9):

Таблица 9

				-2

После преобразования 5 будем иметь (см. табл. 10):

Таблица 10

				-3
				-1

Из выражения для целевой функции в (8) видно, что увеличение (от нуля) значения свободных переменных приведет только к увеличению значения целевой функции. А значит, мы достигли ее глобального минимума. То же самое видно из последней таблицы: все коэффициенты при свободных переменных отрицательны в записи вида (5), где все знаки перед коэффициентами противоположные по сравнению с (8). Значение же целевой функции записано в клетке . Таким образом, решение задачи достигается в точке , а значение целевой функции при этом равно .

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

Поиск по сайту: