Симплексный метод решения задач линейного программирования. Преобразование Жордана-Гаусса и симплекс-метод в Excel

Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств

(2)

Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)

Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:

F(x)=∑c i x i +F 0 =0 (4)

Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.

Алгоритм решения задачи следующий:

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

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

Таблица 1.

x n

базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x 1	x 2	...	x l	...
x n+1	b 1	a 11	a 12	...	a 1l	...	a 1n
x n+2	b 2	a 21	a 22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	a r1	a r2	...	a rl	...	a rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	a m1	a m2	...	a ml	...	a mn
F(x) max	F 0	-c 1	-c 2	...	-c 1	...	-c n

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

Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия

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

Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.

3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:

Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.

Остальные формулы легко записать с помощью .

Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).

4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.

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

Рис. 1. Правило прямоугольника

Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:

Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.

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

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

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

Пример 1. Решить задачу

max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}

Симплексным методом и дать геометрическую интерпретацию процесса решения.

Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда

Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Рис. 2. Графическое решение задачи

Метод Гаусса-Жордана предназначен для решения систем линейных алгебраических уравнений (СЛАУ). Он является модификацией метода Гаусса . Если метод Гаусса осуществляется в два этапа (прямой ход и обратный) то метод Гаусса-Жордана позволяет решить систему в один этап. Подробности и непосредственная схема применения метода Гаусса-Жордана описаны в примерах.

Во всех примерах $A$ обозначает матрицу системы, $\widetilde{A}$ - расширенную матрицу системы. О матричной форме записи СЛАУ можно прочесть .

Пример №1

Решить СЛАУ $ \left\{ \begin{aligned} & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end{aligned} \right.$ методом Гаусса-Жордана.

Давайте перейдём от последней полученной нами матрице к системе:

$$ \left\{ \begin{aligned} & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2;\\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1. \end{aligned} \right. $$

Упрощая полученную систему, имеем:

$$ \left\{ \begin{aligned} & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end{aligned} \right. $$

Полное решение без пояснений выглядит так:

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

Выбор разрешающих элементов на главной диагонали матрицы системы.

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

Первый шаг

В первом столбце выбираем элемент первой строки, т.е. в качестве разрешающего имеем элемент 4. Понимаю, что выбор числа 2 кажется более предпочтительным, так как это число всё-таки меньше, нежели 4. Для того, чтобы число 2 в первом столбце переместилось на первое место, поменяем местами первую и вторую строки:

$$ \left(\begin{array} {ccc|c} 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end{array} \right)\rightarrow \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) $$

Итак, разрешающий элемент представлен числом 2. Точно так же, как и ранее, разделим первую строку на 2, а затем обнулим элементы первого столбца:

$$ \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} I:2 \\\phantom{0} \\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} \phantom{0} \\ II-4\cdot I\\ III+3\cdot I \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right). $$

Второй шаг

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

$$ \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-5\cdot II \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right). $$

Второй шаг окончен. Переходим к третьему шагу.

Третий шаг

На третьем шаге требуется обнулить элементы третьего столбца. В качестве разрешающего элемента выбираем элемент третьей строки, т.е. 37/2. Разделим элементы третьей строки на 37/2 (чтобы разрешающий элемент стал равен 1), а затем обнулим соответствующие элементы третьего столбца:

$$ \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right) \begin{array} {l} \phantom{0}\\ \phantom{0}\\ III:\frac{37}{2} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end{array} \right) \begin{array} {l} I+2\cdot III\\II+3/2\cdot III\\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end{array} \right). $$

Ответ получен: $x_1=-2$, $x_2=1$, $x_3=-1$. Полное решение без пояснений выглядит так:

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

Ответ : $x_1=-2$, $x_2=1$, $x_3=-1$.

Пример №2

Решить СЛАУ $ \left\{ \begin{aligned} & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27;\\ & -3x_1-2x_2-2x_3-10x_4=1. \end{aligned} \right.$ методом Гаусса-Жордана.

Запишем расширенную матрицу данной системы : $\widetilde{A}=\left(\begin{array} {cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end{array} \right)$.

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

Первый шаг

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

$$ \left(\begin{array}{cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} I:3\\ \phantom{0}\\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} \phantom{0}\\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right). $$

Второй шаг

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

$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right)\rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) $$

Вот теперь всё в норме: разрешающий элемент равен (-1). Бывает, кстати, что смена мест строк невозможна, но это обговорим в следующем примере №3. А пока что делим вторую строку на (-1), а затем обнуляем элементы второго столбца. Обратите внимание, что во втором столбце элемент, расположенный в четвёртой строке, уже равен нулю, поэтому четвёртую строку трогать не будем.

$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} \phantom{0}\\II:(-1) \\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} I-1/3\cdot II\\ \phantom{0} \\III-2\cdot II\\\phantom{0}\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right). $$

Третий шаг

Приступаем к обработке третьего столбца. В качестве разрешающего элемента мы условились брать диагональные элементы матрицы системы. Для третьего шага это означает выбор элемента, расположенного в третьей строке. Однако если мы просто возьмём элемент 7 в качестве разрешающего, то всю третью строку придётся делить на 7. Мне кажется, что разделить на (-2) попроще. Поэтому поменяем местами третью и четвёртую строки, и тогда разрешающим элементом станет (-2):

$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) $$

Разрешающий элемент - (-2). Делим третью строку на (-2) и обнуляем соответствующие элементы третьего столбца:

$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\III:(-2)\\\phantom{0}\end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} I-2/3\cdot III\\ \phantom{0} \\ \phantom{0}\\IV-7\cdot III\end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right). $$

Четвёртый шаг

Переходим к обнулению четвёртого столбца. Разрешающий элемент расположен в четвёртой строке и равен числу $-\frac{39}{2}$.

$$ \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\ \phantom{0}\\IV:\left(-\frac{39}{2}\right) \end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end{array}\right) \begin{array} {l} I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom{0} \end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end{array}\right). $$

Решение окончено. Ответ таков: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Полное решение без пояснений:

Ответ : $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.

Пример №3

Решить СЛАУ $\left\{\begin{aligned} & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4+14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5=-9. \end{aligned}\right.$ методом Гаусса-Жордана. Если система является неопределённой, указать базисное решение.

Подобные примеры разбираются в теме "Общее и базисное решения СЛАУ" . Во второй части упомянутой темы данный пример решён с помощью метод Гаусса . Мы же решим его с помощью метода Гаусса-Жордана. Пошагово разбивать решение не станем, так как это уже было сделано в предыдущих примерах.

$$ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end{array}\right) \begin{array} {l} \phantom{0} \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I\\ V+2\cdot I\\VI+4\cdot I \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} \phantom{0} \\ II:5 \\ \phantom{0}\\ \phantom{0}\\ \phantom{0} \\ \phantom{0}\end{array} \rightarrow \\ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right). $$

Полагаю, что одно из сделанных преобразований всё-таки требует пояснения: $IV:3$. Все элементы четвёртой строки нацело делились на три, поэтому сугубо из соображений упрощения мы разделили все элементы этой строки на три. Третья строка в преобразованной матрице стала нулевой. Вычеркнем нулевую строку:

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) $$

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

В этой ситуации проблема решается крайне незамысловато. Мы не можем обработать третий столбец? Хорошо, перейдём к четвёртому. Может, в четвёртом столбце элемент третьей строки будет не равен нулю. Однако четвёртый столбец "болеет" той же проблемой, что и третий. Элемент третьей строки в четвёртом столбце равен нулю. И смена мест строк опять-таки ничего не даст. Четвёртый столбец тоже не можем обработать? Ладно, перейдём к пятому. А вот в пятом столбце элемент третьей строки очень даже не равен нулю. Он равен единице, что довольно-таки хорошо. Итак, разрешающий элемент в пятом столбце равен 1. Разрешающий элемент выбран, поэтому осуществим дальшейшие преобразования метода Гаусса-Жордана:

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) \begin{array} {l} I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom{0}\\ IV+III\\ V+2\cdot III \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \rightarrow \\ \rightarrow\left|\text{Удаляем нулевые строки}\right|\rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)$$

Мы привели матрицу системы и расширенную матрицу системы к ступенчатому виду. Ранги обеих матриц равны $r=3$, т.е. надо выбрать 3 базисных переменных. Количество неизвестных $n=5$, поэтому нужно выбрать $n-r=2$ свободных переменных. Так как $r < n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":

На "ступеньках" стоят элементы из столбцов №1, №2, №5. Следовательно, базисными будут переменные $x_1$, $x_2$, $x_5$. Свободными переменными, соответственно, будут $x_3$, $x_4$. Столбцы №3 и №4, соответствующие свободным переменным, перенесём за черту, при этом, конечно, не забыв сменить им знаки.

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)\rightarrow \left(\begin{array}{ccc|ccc} 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end{array}\right). $$

Из последней матрицы получим общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$. Базисное решение найдём, приняв свободные переменные равными нулю, т.е. $x_3=0$, $x_4=0$:

$$ \left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right. $$

Задача решена, осталось лишь записать ответ.

Ответ : Общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$, базисное решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right.$.

Для разрешения выполнения апплета на вашем компьютере надо сделать следующее - нажать кнопку Пуск>Панельуправления>Программы>Java. В окне Java Control Panel выбираем вкладку Security (Безопастность) нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной строки браузера. Далее нажимаем кнопки ОК, после этого перезагружаем компьютер.

Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java.

После нажатия на кнопку « Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.

После нажатия на кнопку « ok » выводится окно для ввода остальных данных задачи на симплекс-метод: режима отображения (десятичные дроби или обыкновенные), тип критерия задачи min или max , ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ≤ », « ≥ » или « = », ограничения вида х i ≥ 0 вводить не надо, их учитывает в своем алгоритме.

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

Замеченные ошибки и комментарии по работе апплета присылайте на [email protected] или звоните 8 962 700 77 06, за что мы будем Вам очень благодарны.

Программа М-метод

Программа для решения транспортной задачи

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

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

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

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0), т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

итерация 0

БП						Решение	Отношение

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

Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x 2 заменит в базисе s 3 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0 , цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z -строки имеем:

Старая z-строка (-4 -6 0 0 0 0)
-(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120)
=Новая z-строка (-4 0 0 0 6 120) .

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

итерация 1

						Решение	Отношение

Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

Итерация 2

						Решение	Отношение

Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.

Итерация 3

						Решение	Отношение

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.

Симплекс-метод, решение задачи с искусственным базисом

2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х 3 ≥ 0 и х 4 ≥ 0 получим:

Система ограничений предлагает только одну допустимую базисную переменную x 4 , только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R 1 ≥ 0 и R 2 ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R 1 , R 2 и x 4 . Получили, так называемую, М-задачу:

Данная система является системой с базисом, в которой R 1 , R 2 и x 4 базисные переменные, а x 1 , x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

итерация 0

							Решение	Отношение
		-16

В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2 , он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из базисной – в свободную. Запишем следующую симплекс-таблицу:

Разрешающий столбец х 1 , разрешающая строка R 1 , R 1 выходит из базиса, x 1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

							Решение	Отношение

Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1 , который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Особые случаи применения симплекс-метода

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

2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать разрешающую строку, в этом случае решение неограничено.

3) Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (R i). Если они там есть, то задача не имеет решений.

Как известно, метод Жордана-Гаусса, он же метод последовательного исключения неизвестных, является модификацией метода Гаусса решения систем линейных алгебраических уравнений (СЛАУ).

Метод базируется на элементарных преобразованиях (переводящих систему в эквивалентную), к которым относятся:

• прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
• перестановка местами уравнений в системе;
• удаление из системы уравнений вида 0 = 0.

В отличие от метода Гаусса, на каждом шаге одна переменная исключается из всех уравнений, кроме одного.

Шаг метода состоит в следующем:

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

Алгоритмизировать это можно так:

Для СЛАУ в матричном виде A*x=b (матрица A размерности m*n , совсем необязательно квадратная) составляется следующая таблица:

В таблице выбран разрешающий элемент a r,s ≠0 , тогда r - разрешающая строка, s - разрешающий столбец.

Переход к следующей таблице выполняется по правилам:

1. вычисляются элементы разрешающей строки: a" r,j =a r,j /a r,s - то есть, r-строка таблицы делится на разрешающий элемент;

2. все элементы разрешающего столбца, кроме a r,s , равного единице, становятся равны нулю;

3. элементы вне разрешающих строки и столбца вычисляются по формуле, изображённой ниже:

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

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

Возможны следующие случаи:

1. В процессе исключений левая часть уравнения системы обращается в 0, а правая b≠0 , тогда система не имеет решения.

2. Получается тождество 0 = 0 - уравнение является линейной комбинацией остальных и строка нулей может быть вычеркнута из системы.

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

Запрограммируем метод в Excel одной формулой, изменять которую должно быть не слишком трудоёмко. Например, для решения СЛАУ

заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a 1,1 =1 , а первый шаг метода сделаем в ячейке A6 , куда загоним "универсальную" формулу для преобразования Жордана-Гаусса:

ЕСЛИ(СТРОКА($A$1)=СТРОКА(A1);A1/$A$1;
ЕСЛИ(СТОЛБЕЦ($A$1)=СТОЛБЕЦ(A1);0;(A1*$A$1-
ДВССЫЛ(АДРЕС(СТРОКА(A1);СТОЛБЕЦ($A$1)))*
ДВССЫЛ(АДРЕС(СТРОКА($A$1);СТОЛБЕЦ(A1))))/$A$1))

На следующем шаге разрешающим элементом может быть, например, a 2,2 =1 (ячейка B7). Нам останется скопировать формулу из A6 в A11 (по пустой строке оставляем, чтоб визуально разделить шаги метода), войти в режим редактирования формулы (двойной щелчок по ячейке или выбрать её и нажать клавишу F2) и поправить (аккуратно перетащить мышкой за границу) все закреплённые ссылки с ячейки A1 на B7 .

Конечно, можно заменить везде в формуле закреплённую ссылку $A$1 на конструкцию вида ДВССЫЛ(ЯЧЕЙКА) , образующую динамический адрес ссылки. Скажем, ДВССЫЛ(F8) , а в ячейке F8 будет автоматически формироваться адрес ячейки разрешающего элемента по заданным пользователем номеру строки и столбца. Тогда для этих номеров строки и столбца придётся предусмотреть отдельные ячейки, например, так:

Увы, всё это ничего не даст - вместо $A$1 мы просто вынуждены будем закрепить в формуле ДВССЫЛ($F$8) и всё равно потом перетаскивать столько же ссылок при копировании формулы. Кроме того, "вручную" введённые номера строки и столбца придётся ещё и проверять на допустимость (хотя бы как на рисунке), так что, не будем умножать сущностей.

Посмотреть метод в работе можно на двух первых листах приложенного файла Excel (2 разных примера).

На преобразовании Жордана-Гаусса основан и такой универсальный метод решения линейных задач оптимизации, как симплекс-метод . Описания его обычно страшны, длинны и перегружены теоремами. Попробуем сделать простое описание и разработать пригодный для расчёта в Excel алгоритм. На самом деле, симплекс-метод уже встроен в стандартную надстройку Пакет анализа, и программировать его "вручную" не нужно, так что наш код имеет, скорее, учебную ценность.

Сначала минимум теории.

Если вектор-столбцы СЛАУ линейно независимы, соответствующие им переменные являются базисными , а остальные – свободными . Например, в СЛАУ

переменные x 2 и x 4 - базисные, а x 1 и x 3 - свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить { x 2 =2, x 4 =1 } – базисное решение системы.

Выбирая различные разрешающие элементы, можно получить решения СЛАУ с различными базисами. Любое неотрицательное базисное решение СЛАУ называется опорным .

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

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

1. Задача ЛП преобразуется к каноническому виду:

Это всегда можно сделать следующим образом: к задаче, записанной в стандартной постановке

добавляются дополнительные балансовые переменные , число которых соответствует числу ограничений-неравенств m (ограничения на неотрицательность значений неизвестных не учитываются). После этого неравенства со знаком " ≤ " превращаются в равенства, например, система ограничений вида

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1 ,x 2 ≥0

примет вид

2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0

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

Если в исходной задаче искался не минимум, а максимум, целевая функция Z заменятся на Z 1 = -Z . Решения задач совпадают, при этом min Z = - max Z 1 . Например, цель

Z(x 1 ,x 2)=2*x 1 +5*x 2 (max)

переписывается в виде

Z 1 (x 1 ,x 2)=-2*x 1 -5*x 2 (min)

Если в исходной задаче были уравнения-неравенства со знаками " ≥ " вместо " ≤ ", обе части каждого такого неравенства умножаются на -1 , а знак неравенства меняется на противоположный, например,

3*x 1 +x 2 +x 4 ≥15

превращается в

3*x 1 -x 2 -x 4 ≤15

Канонический вид модели получен, для него выписывается симплекс-таблица :

В левом столбце записываются базисные переменные (БП), если они ещё не выделены – пусто.

2. С помощью шагов Жордана–Гаусса ищется первоначальный опорный план, т.е. СЛАУ приводится к базисному виду с неотрицательными свободными членами b i >0 . При этом целевая функция Z должна быть выражена только через свободные неизвестные (нулевые коэффициенты в Z-строке стоят только под переменными x i , которые есть в базисе). При выборе разрешающего элемента a r,s в строку r столбца БП выписываем переменную x s , если там уже была переменная – вычеркиваем её (выводим из базиса).

3. Выписываем под столбцами x i опорный план X * : под свободными переменными - нули, под базисными – соответствующие базисной переменной коэффициенты из столбца b .

Ниже выписываем вектор R по правилу: под базисными переменными – нули, под свободными R i =Z i .

Если все R i ≥0 , найдено оптимальное решение X * и значение цели Z min = -q , иначе нужен новый план, а у вас он есть, товарищ Жюков? (п. 4).

4. Для выбора разрешающего столбца s выбираем максимальную по модулю отрицательную компоненту вектора R , разрешающий столбец s выбран. Затем анализируем коэффициенты s-го столбца матрицы системы ограничений. Если все a i,s ≤0 , решения нет и Z min стремится к минус бесконечности, иначе переходим к п.5.

5. Для выбора разрешающей строки r составляем неотрицательные отношения b i /A i,s ≥0 , i=1,2,...,m , и выбираем среди них наименьшее. Если минимум достигается для нескольких строк, за разрешающую можно принять любую из них, при этом, в новом опорном плане значения некоторых базисных переменных станут равными 0, т.е., получаем вырожденный опорный план.

6. Выполняем преобразование Жордана-Гаусса с разрешающим элементом a r,s и переходим к п.3

Геометрически симплекс-методу соответствует кратчайший обход вершин n-мерного выпуклого многогранника, образующего область допустимых решений задачи:

Здесь мы перешли от опорного плана C , представляющего собой одну из вершин многомерного многоугольника, к оптимальному плану E=X * .

Запрограммировать это всё в Excel нелегко, но можно. В прилагаемом документе приведены 3 примера, реализующие решение задач симплекс-методом. Правда, при выполнени шага менять уже придётся 3 формулы, на листе первого примера на симплекс-метод они выделены жёлтым цветом: расчёт отношений для выбора разрешающей строки в ячейке I2 , заполнение столбца БП в ячейке A12 , шаг преобразования Жордана-Гаусса в ячейке B12 . Как и в примере на преобразование Жордана-Гаусса, изменение формул связано только с необходимостью сослаться на новую строку, содержащую адрес ячейки с разрешающим элементом (для первого шага - ячейка C9).

При условии отсутствия “0-строк” (ограничений-равенств) и “сво­бодных” перемен­ных (т.е. переменных, на которые не наложено требование неотри­цатель­ности).

2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.

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

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

Вырожденность в задачах линейного программирования

Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно
положительных компонент, где
– число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда
(число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида
. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку.

Аналогично при
в вы­рож­денной задаче в одной вершине пересекается более 3-х плоскостей
.

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

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

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

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

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

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

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