Обобщение результатов линейного программирования

Предположим, что начальная каноническая форма задана уравнениями, в которых ограничения преобразованы таким образом, что X₁,...,X_n последовательно выражаются через b и остальные X_i. Это можно записать в виде

X₁+...…..a'_1(m+1)X_(m+1)+...+a'_1nX_n=b'₁ (43)

X_m+a'_m(m+1)X_(m+1)+...+a'_mnXn=b'_n

Если умножить ограничения системы (43) на с₁, с₂,...,с_m и вычесть из Z, то X₁,...,X_m исключаются из Z и мы получим

c'_m+1X_m+1+c'_m+2X_m+2+...+c'_nX_n=Z–Z_o, (44)

где

m

Z_o= å c_i*b_i. (45)

i=1

Если X_m+1,X_m+2,...,X_n =0, то соотношения X₁=b'₁, X₂=b'₂, X_m+1=0, X_n= 0 задают базисное решение. Если же при этом все b'_i≥ 0 – это решение допустимо. Среди таких решений надо найти оптимальное. Симплекс-метод обеспечивает процедуру замены одной канонической формы на другую, при которой значение целевой функции уменьшается. В виде симплекс таблиц уравнения (43)-(45) приведены ниже.

Таблица 13

Итерация	Базис	Значение	X1	X2	Xr	Xm	Xm+1	Xn
	X1 X2 Xr Xm	B’1 B’2 B’r B’m	* * *	* * *	* * *	* * *	A’1(m+1) A’2(m+1) A’r(m+1) A’m(m+1)	A’1n A’2n A’rn A’mn
–Z	–Z’c	*	*	*	*	C’m+1	C’n

Итерационный процесс состоит из трех шагов.

1. Найти переменную для включения в базис.

Таковой будет небазисная переменная, для которой с'_j ≤0 (лучше максимальная по модулю с'_j. Пусть это будет с'_m+1.

2. Найти переменную для исключения из базиса.

Для этого необходимо найти ответ на следующий вопрос: насколько можно увеличивать X_m+1, не нарушая условия неотрицательности базисных переменных? Если в i -том ограничении a'_(m+1) >0, то наибольшее значение, которое может принимать X_m+1 равно b'_i/a'_i(m+1), иначе переменная X_i станет отрицательной. Таким образом значение X_m+1 может быть увеличено до величины {max}X_m+1={min}(b'_i/a'1_(m+1)) при i =1... m, a'_i(m+1)> 0. Если этот минимум достигается в строке r, то X_r обращается в ноль, когда X_m+1 = b'_r/a'_r(m+1). Элемент a'_r(m+1) называется ведущим элементом, строка r – ведущая строка, столбец m+1 – ведущий столбец.

3. Построение новой канонической формы.

Теперь получили новый базис X₁, X₂, X_m, X_m+1. Чтобы построить новую каноническую форму, коэффициент при X_m+1 в ведущей строке сделаем равным единице, поделив строку на a_r(m+1), чтобы образовать новую ведущую строку. Затем удалим X_m+1 из других ограничений целевой функции. Для этого из i строки (i≠r) с коэффициентом a'_r(m+1) при X_m+1 вычтем a'_r(m+1) (новая ведущая строка).

На очередной итерации каноническая форма будет выглядеть следующим образом табл.14)

Таблица 14

Итерация	Базис	Значение	X1	X2	Xr	Xm	Xm+1	Xn
K+1	X1 X2 Xm Xm+1	B^+1 B^+2 B^+m B^+m+1	* * *	* * *	A^+1r A^+2r A^+mr A^+(m+1)r	* * *	* * *	A^+1n A^+2n A^+mn A^+(m+1)n
–Z	–Z’c	*	*	C^+r	*	*	C ^+n

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

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

Минимизировать функцию

– 6X₁–2X₂=Z (46)

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

X₁, X₂, X₃, X₄> =0, (47)

2 X₁ +4 X₂ + X₃ =9, (48)

3 X₁ + X₂ + X₄ =6. (49)

Последовательность итераций с комментариями решения приводится в табл. 15.

Таблица 15

Итерация	Базис	Значение	X1	X2	X3	X4
	X3 X4		3^0		*	*
–Z		–6	–2	*	*
	X3 X1		*	10/3^0 1/3	*	–2/3 1/3
–Z		*		*
	X1 X2	3/2 3/2	*	*	–1/10 3/10	4/10 –2/10
–Z		*	*

Начальный базис очевиден: X₁ = X ₂=0; X₃ =9; X₄ =6. Желательной переменной для включения в базис является X₁, так как для этой переменной значение коэффициента c₁ в выражении целевой функции имеет максимальную отрицательную величину. При этом ведущим будет столбец с номером 1, ведущей строка с номером 2; значение коэффициента a₂₁ =3. Для включения в базис X₁ разделим ведущую строку на 3, получим Х₁ +1/3 Х₂ +1/3 Х₄ =2. Исключим X₁ из ограничения (48) и целевой функции (46), умножив Х₁ +1/3 Х₂ +1/3 Х₄ =2 на 2 и (–6) и вычтем соответственно полученные уравнения из ранее упомянутых. Получим, соответственно, новые выражения ограничения и целевой функции (табл. 15, итерация 1). В целевой функции коэффициент С₄ имеет положительное значение, коэффициент С₂ равен нулю, то есть включение X₂ в базис не имеет смысла, так как это не уменьшит значение целевой функции. Покажем это на примере следующей итерации. Предлагаем читателю самостоятельно получить выражения ограничений и целевой функции для второй итерации. Значение целевой функции не изменилось. Если сравнить полученные результаты с рис. 9 для графического решения данного упражнения, то легко убедиться, что первая итерация соответствует точке С, вторая – точке В.

Дата добавления: 2014-01-07