Лабораторная работа №5 Вариант 10

2

Липецкий государственный технический университет

Кафедра автоматизированных систем управления

ЛАБОРАТОРНАЯ РАБОТА №5

по Теории принятия решений

Модифицированный симплекс-метод

Студент

Ключанских А.С

^подпись, дата

^фамилия, инициалы

Группа

АС-10

Принял

доцент

Корнеев А.М.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2013

1. Задание

1. Решить задачу линейного программирования, используя итерации модифицированного симплекс-метода.

2. Вычислить коэффициенты z-строки и определить включаемую в базис переменную .

3. Определить исключаемую переменную

4. Определить новый базис и перейти к шагу 2.

2. Решение

Целевая функция имеет вид: .

А область ограничений задачи в стандартной форме имеет вид:

Найденное оптимальное решение в предыдущих практических работах:

.

Начальное решение:

Итерация 1

Шаг 1 – Вычисление для небазисных векторов и .

Следовательно, включению в базис подлежит вектор .

Шаг 2 – Определение исключаемого вектора при введении в базис вектора .

Базис							Решение
	-5	-10	0	0	0	0
		1					4
		2					10
		2					14
		2					56

Отсюда следует, что

Значит, исключению из базиса подлежит вектор .

Шаг 3 – Определение обратной матрицы, соответствующей новому базису.

Так как вместо вектора в базис вводится вектор и , то:

Новому базису соответствуют векторы:

Итерация 2

Шаг 1 – Вычисление для небазисных векторов и .

Следовательно, включению в базис подлежит вектор .

Шаг 2 – Определение исключаемого вектора при введении в базис вектора .

Базис							Решение
	-15	0	10	0	0	0
	-1						4
	1						2
	2						6
	9						48

Отсюда следует, что

Значит, исключению из базиса подлежит вектор .

Шаг 3 – Определение обратной матрицы, соответствующей новому базису.

Так как вместо вектора в базис вводится вектор и , то:

Новому базису соответствуют векторы:

Итерация 3

Шаг 1 – Вычисление для небазисных векторов и .

Следовательно, включению в базис подлежит вектор .

Шаг 2 – Определение исключаемого вектора при введении в базис вектора .

Базис							Решение
	0	0	-20	15	0	0
			-1				6
			-2				2
			2				2
			16				30

Отсюда следует, что

Значит, исключению из базиса подлежит вектор .

Шаг 3 – Определение обратной матрицы, соответствующей новому базису.

Так как вместо вектора в базис вводится вектор и , то:

Новому базису соответствуют векторы:

Итерация 4

Шаг 1 – Вычисление для небазисных векторов и .

Следовательно, включению в базис подлежит вектор .

Шаг 2 – Определение исключаемого вектора при введении в базис вектора .

Базис							Решение
	0	0	0	-5	10	0
				0			7
				-1			4
				-1			1
				7			14

Отсюда следует, что

Значит, исключению из базиса подлежит вектор .

Шаг 3 – Определение обратной матрицы, соответствующей новому базису.

Так как вместо вектора в базис вводится вектор и , то:

Новому базису соответствуют векторы:

Итерация 5

Шаг 1 – Вычисление для небазисных векторов и .

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

Полученное оптимальное решение