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

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

 

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

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

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

Элементы дополнительной строки 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. Составляем симплексную таблицу, соответствующую  исходной задаче:

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
Ri	ai,1	ai,2	...	ai,n-1	ai,n	bi
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm
M	-∑ai,1	-∑ai,2	...	-∑ai,n-1	-∑ai,n	-∑bi

 

  

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

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

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

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

Шаг 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 – строка (для которой это отношение минимально): ведущая. Элемент 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 – строка (для которой это отношение минимально): ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k), исключается из базиса; переменная, соответствующая ведущему столбцу (x_l), включается в базис.

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

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

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

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

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

1. вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k;  
2. ведущий элемент заменяется на обратную величину a_k,l'=1/a_k,l;
3. все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l;
4. все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l;
5. оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'=a_i,j- a_i,l×a_k,j/ a_k,l.