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

 

Наиболее простым и распространенным методом решения канонической задачи линейного программирования до сих пор является симплекс-метод, предложенный в 40-е годы прошлого века Дж. Данцигом. Геометрически идею симплекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче линейного программирования является некоторое многогранное множество и-мерного векторного пространства (в частном случае n = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начинается с некоторой начальной вершины (начального опорного плана) многогранного множества. Специальным образом выясняется, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина находится, то она и принимается за следующее приближение. После этого вновь исследуются соседние вершины для полученного приближения и т. д. до тех пор, пока не будет получена вершина, среди соседних вершин которой не существует вершины с лучшим значением целевой функции. Такая вершина является оптимальной. Она соответствует оптимальной точке (оптимальному решению) задачи линейного программирования.

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

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

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

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

Решение задачи при помощи симплекс-метода распадается на ряд шагов. В каждой вершине многогранника будет m ненулевых координат, которые образуют базис. Остальные (n-m) координат входят в набор небазисных (свободных) переменных. На каждом k-м шаге от данного базиса Бk переходят к другому, новому базису Бk+1 с таким расчетом, чтобы значение функции f(x) увеличивалось, т. е. fБk+1≥fБk. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б k*, для которого fБ(k*) есть искомый максимум для линейной функции f, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

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

Целевая функция вида:

и ограничения

,

Переобозначим свободные коэффициенты ограничений aj0=bj. Приведем матрицу ограничений к каноническому виду:

(2.4)

Используя метод Гаусса - Жордана, приведем записанную систему к виду, где выделены базисные переменные. Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений и др. задач.

Задачи линейного программирования, решаемые с помощью симплекс-метода, основываются на представлении решения в табличной форме. Рассмотрим последовательность действия при решении задачи линейного программирования.

По последней системе ограничений и целевой функции в каноническом виде построим симплекс-таблицу.

Таблица 4.1. Симплекс-таблица

	С	С1	С2	С3	…	Сj	…	Cn		…
Bx	A0	A1	A2	A3	…	Aj	…	An	An+1	…	An+m
xn+1	a10	a11	a12	a13	…	a1j	…	a1n		…
xn+2	a20	a21	a22	a23	…	a2j	…	a2n		…
	…	…	…	…	…	…	…	…	…	…	…
xn+i	ai0	ai1	ai2	ai3	…	aij	…	ain		…
	…	…	…	…	…	…	…	…	…	…	…
xn+m	am0	am1	am2	am3	…	amj	…	amn		…
L	a00	a01	a02	a03	…	a0j	…	a0n	a0m+1	…	a0m+n

Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Нижняя строка элементов а_ок, к = 0,…,m+п называется индексной. Элементы индексной строки вычисляются следующим образом:

означает номер соответствующей строки.

Поскольку на первом шаге заполнения таблицы все элементы с_n+i равны нулю, то элементам индексной строки присваиваются значения соответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. а_ok= -С_к. Последняя строка таблицы служит для определения направляющего столбца.

Элемент а₀₀ равен значению целевой функции, которое вычисляется по формуле - номер базисной переменной (индексация идет по строкам таблицы).

В столбце Вх записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные {х_п+к }, к =1,…,n. В дальнейшем фиктивные переменные необходимо вывести из базиса.

В столбец С записываются коэффициенты при х_п+к,; на первом шаге значения этих коэффициентов равны нулю.

Далее выполняются преобразования в соответствии с алгоритмом симплекс -метода.

Алгоритм симплекс-метода:

 

Этап 1. Находится начальное допустимое базисное решение

Этап 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.

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

Этап 3. На основе условия допустимости выбирается исключаемая переменная.

3.1. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке. То есть разрешающая строка соответствует той из базисных переменных, которая будет увеличиваться меньше других. Если таких переменных нет (все a_i,вед. ≤0), то задача неразрешима.

3.2. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

Этап 4. Методом Гаусса - Жордана вычисляется новое базисное решение. Переход к этапу 1.

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

4.2. Вычисление элементов новой таблицы выполняется так.

Новая ведущая строка =текущая разрешающая строка / разрешающий элемент.

Для элементов остальных строк:

Новая строка = текущая строка – ее коэффициент в разрешающем столбце ×новая разрешающая строка.

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