Симплексный метод с использованием М- базиса

 

1.3 Метод искусственного базиса (М-Метод)

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

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

Симплекс-таблица, которая составляется в процессе решения, используя метод  искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (x_n+m) и искусственные (R_i)- базисными.

 

Исходная таблица для "Метода искусственного базиса" (таблица 3) имеет следующий вид:

	x1	x2	...	xn-1	xn	b
F	- a0,1	-  a 0,2	...	- a0,n-1	-a0,n	-b 0
xn+1	A 1,1	A1,2	...	A 1,n-1	A 1,n	B 1
xn+2	A 2,1	A 2,2	...	A 2,n-1	A2,n	B 2
Ri	A i,1	A  i,2	...	A i,n-1	A i,n	Bi
...	...	...	...	...	...	...
xn+m	A  m,1	A  m,2	...	A m,n-1	A m,n	B m
M	-∑ ai,1	-∑a i,2	...	-∑a i,n-1	-∑ai,n	-∑b i

Таблица 3.

Элементы дополнительной строки M расчитываются как сумма соответствующих  коэффициентов условий-равенств (условий  в которые после приведения к  каноническому виду введены переменные R_i) взятая с противоположным знаком.

 

 

 

Алгоритм  метода искусственного базиса. 

Приводим  задачу ЛП  к    каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.........................................

a_i,1x₁+a_i,2x₂+...a_i,nx_n+R_i=b_i

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов  целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x_n+m , к каждому i-му условию-равенству добавляем искусственную переменную R_i.

 

 

 

 Шаг 0. Составляем симплексную таблицу (таблица 4), соответствующую исходной задаче

	x1	x2	...	xn-1	xn	b
F	- a 0,1	-   a0,2	...	-  a 0,n-1	-   a0,n	-  b  0
xn+1	A 1,1	A1,2	...	A       1,n-1	A       1,n	B       1
xn+2	A 2,1	A       2,2	...	A       2,n-1	A       2,n	B      2
Ri	A  i,1	A  i,2	...	A i,n-1	A i,n	B     i
...	...	...	...	...	...	...
xn+m	A m,1	A m,2	...	A m,n-1	A  m,n	B m
M	-∑  a       i,1	-∑a     i,2	...	-∑a       i   ,n-1	-∑a      i,n	-∑ b      i

Таблица 4.

 

 

 Шаг 1. Проверка на допустимость.   

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

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

Если после перерасчета  в столбце свободных членов остались отрицаетельные элементы, то переходим  к первому шагу, если таких нет, то ко второму.  

Шаг 2. Проверка на оптимальность. 

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

2.1 Положительность строки M

Если в строке M есть отрицательные элементы то решение  требует улучшения. Выбираем среди  отрицательных элементов строки M максимальный по модулю (исключая -∑b_i)

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для  которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу  по формулам Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2

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

Если в строке M и в столбце свободных членов все элементы положительные, то переходим  к шагу 2.2.

 

2.2 Положительность строки F

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

-a_0,l=min{-a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для  которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу  по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено  оптимальное решение.  

 

Правила преобразований симплексной таблицы

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

• Вместо базисной переменной                   x        _k       записываем       x       _l         ; вместо небазисной переменной x_l записываем                x       _k.  
• ведущий элемент заменяется на обратную величину a                    _{k ,l}  '=      1    /    a  _k,l
• все элементы ведущего столбца (           кроме a      _{k ,l}) умножаются на  -  1  / a  _{k     ,l}
• все элементы ведущей строки (     кроме a           _k,l) умножаются на 1  /  a  _k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,l*a_k,j/ a_k,l

 

 

2 Решение задач

2. 1 Табличный симплекс-метод

 

Постановка задачи (в канонической форме):

,

 (1)

 

 

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

Пусть , где .

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

2. Переменные – объявляются базисными, а переменные –внебазисными.

 

 

 

 

 

3. Система (1) преобразуется к эквивалентной форме вида:

 (2)

4. Производится проверка: все ли числа в (2) неотрицательны. В случае если хотя бы одно из них строго отрицательно, необходимо выбрать другой набор линейно независимых столбцов и для него повторить пункты 1-3, соответствующим образом изменив нумерацию переменных.

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

6. Строится симплекс-таблица (таблица 6)

		1		0		0
		0		1		0
		0		0		1
		0		0		0

 

Таблица 6.

 

 

 

 

 

 

 

 

7. Производится анализ знаков :

а). все  , тогда решение задачи ЛП имеет вид: , где

 

Значение целевой функции на оптимальном решении  (левый нижний угол таблицы 6);

б). , такой, что , тогда выполняется пункт 8.

8. Исследуется столбец, у которого (как правило, выбирается наименьший отрицательный коэффициент ):

а). все        и счет необходимо прекратить;