Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

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

полученное оптимальное значение	0	0	. По оценкам
	0

j	0 (если они есть) определяется вектор для введения в

базис на данной итерации. Процесс продолжается до тех пор,

пока не исчезнут такие	j, что	j	0 ,	j	0 ,
		j		j
соответствующий столбец Aj	имеет элементы aij			0 .

Итак, сформулируем алгоритм метода искусственного

базиса (модифицированного симплекс метода):

1.Ввести в исходную задачу искусственные переменные так, чтобы среди столбцов полученной матрицы появился единичный базис в пространстве Rm , где m - число ограничений задачи. Ввести искусственные переменные в целевую функцию с коэффициентами, равными – M.

2.Составить исходную таблицу для оформления решения задачи. Фрагмент таблицы завершается двумя строками для оценок

	j	j	M j	(первая - для чисел j , вторая - для				j ).
3.	Вычислить оценки всех векторов-ограничений задачи по
	формулам		j	ci aij c j . При наличии искусственных
				i I
	векторов в базисе получим выражения вида					j	M j .
	Поместить		j	в первую оценочную строку,		j - во вторую
	(нижнюю).
4.	При наличии двух оценочных строк проверить, если все								j	0 ,
									j
	то перейти к п. 11, иначе к п.6 с числами j					. Если осталась одна
	оценочная строка, то проверить условие				j	0 . Если это условие
					j
	выполняется, то перейти к п.9.
5.	Просмотреть векторы-столбцы Aj , для которых						j	0 . Если

103

среди них существует такой, что все его координаты		ij	0 , то
		ij
перейти к п. 10, иначе - к п.9 с числами j	j .

6.Определить направляющий элемент для выполнения преобразований Жордана-Гаусса. Номер столбца k может быть

выбран любым среди тех j, для которых

0 . Номер строки l

определяется следующим образом:

min

, где xi - базисные координаты проверяемой

alk

aik 0

aik

базисной точки, alk - направляющий элемент.

7.Перейти к новой базисной точке. Осуществить преобразования Жордана-Гаусса с направляющим элементом alk . Выбросить из

рассмотрения искусственный вектор, если он на данной итерации стал небазисным. Перейти к п.3.

8 .Проанализировать значение целевой функции в данной базисной

точке z(xB )

0 M 0 . Если 0 0 , то проверить наличие

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

j	0 для тех номеров j, для которых	j	0 . Если неравенства

выполняются, то получено решение задачи. Перейти к п.12. Если среди j таких, что j 0 , существуют такие, что j 0 , то перейти к п.5, где проверке будут подвергаться только те векторы

Aj , для которых j 0 , j

имеет место неравенство	0

0 . Если в выражении 0 M 0

0 , то перейти к п. 11.

9. Проверка единственности решения.
Если среди небазисных векторов есть такие, что	j	0 , то в
	j

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

x	x'	x'' . B этом случае, если одна из переменных	x'	или x''
s	s	s	s	s

является базисной, то оценка второй обязательно равна нулю. Этот факт означает бесчисленное множество пар, с помощью

104

которых может быть получено значение переменной xs . Если

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

небазисных векторов	j	0 , то задача имеет единственное
	j

решение. Перейти к п.15.

10.СТОП. Задача не имеет решения из-за неограниченности целевой функции на допустимом множестве. Перейти к п. 12.

11.СТОП. Задача не имеет решения из-за пустоты исходного допустимого множества.

12.Выписать ответ.

Пример 1. Решить ЗЛП:

x1	2x2	3x3		x4	min
x1	2x2	3x3			15,
2x1	x2	5x3			20,
x1	2x2		x3	x4	10,
x j	0, j	1, 4.

Решение.

Так как в задаче нет начального базиса, введѐм дополнительные переменные z5 и z6:

x1	2x2	3x3	x4	Mz5 Mz6	min
x1	2x2	3x3		z5	15,
2x1	x2	5x3		z6	20,
x1	2x2	x3	x4		10,

x j	0,	j 1, 4.

Запишем данные в таблицу:

105

					-1	-2	-3	1	M	M
	B	CB		x	-1	-2	-3	1	M	M
	B	CB			A1	A2	A3	A4	z1	z2
					A1	A2	A3	A4	z1	z2
	z1	M	15		1	2	3	0	1	0	5
	z2	M	20		2	1	5	0	0	1	4
	x4	1	10		1	2	1	1	0	0	10
			10		2	4	4	0	0	0
			35		3	3	8	0	0	0

На первой итерации вектор						z2 выводится из базиса,				следовательно
его столбец вычѐркиваем. В базис вводится вектор A3 .

	B	CB		x	-1	-2	-3	1	M
	B	CB			A1	A2	A3	A4	z1
					A1	A2	A3	A4	z1
	z1	M	3		-1/5	7/5	0	0	1		15/7
	x3	-3	4		2/5	1/5	1	0	0		20

	x4	1	6		3/5	9/5	0	1	0		30/9
			10		2	4	0	0	0
			3		-1/5	7/5	0	0	0

На второй итерации из базиса выводится вектор z2 , и

дополнительные переменные исчезают. Продолжаем решать исходную задачу по стандартной схеме.

				-1	-2	-3	1
B	CB		x	-1	-2	-3	1
B	CB			A1	A2	A3	A4
				A1	A2	A3	A4

x2	-2	15/7		-1/7	1	0	0	-15
x3	-3	25/7		3/7	0	1	0	25/3

x4	1	15/7		6/7	0	0	1	15/6
		-90/7		6/7	0	0	0

x2	-2	5/2		0	1	0	1/6
x3	-3	5/2		0	0	1	-3/6

x1	-1	5/2		1	0	0	7/6
		-15		0	0	0	-1

106

Итак,	задача решена. Найдена оптимальная точка x* (	5	,	5	,	5	,0) ,
Итак,	задача решена. Найдена оптимальная точка x* (	2	,	2	,	2	,0) ,
		2		2		2
L(x* )	15 .

Пример 2. Решить ЗЛП:

x1		3x3		x4	max
2x1	4x2			x4	9,
3x1	2x2			3x4	3,
x1	5x2		x3	2x4	4,
x j	0, j
x j	0, j	1, 4.

Так как в задаче присутствует только один базисный вектор A3 , добавим искусственные переменные в 1-е и 2-е ограничение.

				x1			3x3		x4	Mz1		Mz2		max
				2x1	4x2				x4		z1			9,
				3x1	2x2				3x4				z2	3,
				x1		5x2	x3		2x4					4,
				x j	0, j
				x j	0, j		1, 4.

B	CB			1		0		3			-1		-M		-M
			x
			x	A1		A2		A3			A4		z1		z2
				A1		A2		A3			A4		z1		z2
z1	-M	9		2		4		0			-1		1		0	9/4
z2	-M	3		-3		2		0			3		0		1	3/2
x3	-M	4		1		5		1			2		0		0	4/5

		12		2		15		0			7		0		0
		-12		1		-6		0			-2		0		0
z1	-M	4		1		0		2			1		1		0
z2	-M	7/5		-17/5		0		-2/5			11/5		0		1
x2	0	4/5		1/5		1		1/5			2/5		0		0
		0		-1		0		-3			1		0		0
		-36/5		11/5		0		6/5			2/5		0		0

107

Источник: https://studfile.net/preview/16565974/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)