Нахождение начального опорного решения и алгоритм перехода к новому решению

Пусть дана задача ЛП в канонической форме.

В случае, если правая часть какого-либо уравнения отрицательна, то это уравнение следует умножить на (-1). Для нахождения опорного решения воспользуемся тем, что любое допустимое базисное решение является опорным. Базисное решение будем искать методом Жордана-Гаусса, разрешающие элементы при этом для преобразования уравнения будем выбирать таким образом, чтобы правая часть этих уравнений оставалась неотрицательной. В этом случае базисное решение будет допустимым, т.е. опорным. Выведем правило линейного преобразования уравнений таким образом, чтобы его правая часть оставалась неотрицательной. Предположим, что разрешающим элементом для преобразования является элемент а _{l k} при неизвестной х_k в уравнении с номером l. В результате преобразования правые части уравнений будут пересчитаны следующим образом:

Для того, чтобы правая часть необходимо, чтобы a_lk>0, т.к. b_l>0 по первому шагу. Для выполнения b_j ³0 рассмотрим 2 случая:

Пусть a_jk £0, тогда в силу того, что все b_j ³ 0, b_l ³ 0, a_lk > 0, и без дополнительных условий b_j ³ 0.

Во втором случае a_jk > 0, то неравенство разделим на a_jk.

Это неравенство должно выполняться для любого неравенства с номером j, при a a_jk > 0.

Для удобства вычислений вводят вспомогательный параметр q _0k.

q _0k – есть min

при a_ik>0 ищем номер l

В этой формуле k-номер условия A_k, вводимого в базис (выбираемого столбца матрицы системы ограничений, а l – номер столбца матрицы ограничений, выбираемого из базиса). С помощью данного условия можно выбрать разрешающий элемент в любом столбце k системы ограничений, в a имеется хотя бы один положительный элемент. Этим руководствуются, выбирая начальное опорное решение и переходя от одного опорного решения к другому. Предположим, что при помощи разрешающих элементов приведена таким образом, что правые части системы сохранились неотрицательными, и такая система имеет вид:

В этой записи k – номер вектора, вводимого в базис; l – номер вектора, выводимого из базиса; x_i0 – координата опорного решения; x_ik – коэффициент разложения вектора А_k по базису опорного решения.

Пример: Имеем задачу ЛП

Найти начальное опорное решение и определить оптимальное решение задачи.

Будем решать табличным способом

r =2

X1	X2	X3	X4	b	q1
						q2
			-2				q3
		-1	-1					q4
	0.5 0.5		3/2 -0.5					14/3	q5
2/3 2/3	2/6 2/3			14/3 16/3

Правило треугольников преобразования

X1	X2	X3	X4	b	Q1	Q2	Q3
-1			-3
			-2
			-1
	1/2 1/2		3/2 -1/2
2/3 1/3	1/3 2/3			14/3 16/3			14/3
½ 1/2		-1/2 3/2

Преобразование целевой функции при переходе от одного опорного решения к другому

Имеем опорное решение:

При преобразовании находим другое:

Используя формулу Жордана, имеем:

-оценка разложения вектора условий А_k по базису опорного решения. Вычисляется по формуле:

Пример:

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

Б	Сб	А0	А1	А2	А3	А4	А5	А6
А4
А5				-1	-4
А6				-2
			-13

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