Симплекс-метод решения задач линейного программирования

Министерство образования и  науки Российской Федерации

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

Факультет экономики  и управления

 

Кафедра математических методов и моделей в экономике

 

 

 

ОТЧЕТ

по лабораторной работе № 3

по курсу «Методы  принятия управленческих решений»

 

Симплекс-метод решения  задач линейного программирования

Вариант № 1

ОГУ 080200.62.8.0.13.209. О

 

 

 

 

 

 

 

 

                                                      

              

Руководитель

_________ Зеленина Т. А.

«___»_________________2013 г.

 

Исполнитель

студентка группы 12Мен(б)МРД

_________ Батакова А.А.

«___»_________________2013 г.

 

 

 

Оренбург 2013

1. Экономико-математическая модель задачи

 

Найти решение задачи линейного программирования симплекс-методом:

 

2. Решение задачи симплекс-методом

 

Получим из системы неравенств систему уравнений путем приведения к канонической форме:

 

    

 

Решим систему уравнений  относительно базисных переменных: x3, x4.

 

Полагая, что свободные переменные равны 0, получим первый опорный план:

_X1 = (0,0,8,3).

 

 Построим симплекс-таблицу:

 

			1	1	0	0
Базис	С базисное	B	A1	A2	A3	A4	Q
A3	0	8	1	2	1	0	8
A4	0	3	6	-1	0	1	0,5
		f(x)	-1	-1	0	0

 

Найдем оценки Δ _j для всех A _i по формуле:

 

                                        Δ _{j = .}

 

а) ∆₁= ;

б) ∆₂= ;

в) ∆₃=0

г) ∆₄=0

Поскольку среди ∆ есть отрицательные, то решение не является оптимальным.

 

Определение нового базиса

 

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения Q по строкам как частное от деления: B_i/A1 и из них выберем наименьшее: A4= 0,5. Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен 6 и находится на пересечении ведущего столбца и ведущей строки.

 

Строим новую симплекс-таблицу

 

			1	1	0	0
Базис	С базисное	B	A1	A2	A3	A4	Q
A3	0	15/2	0	13/6	1	-1/6	45/13
A1	1	1/2	1	-1/6	0	1/6	-3
		f(x)	0	-1/6	0	1/6

 

Найдем оценки Δ _j для всех A _i по формуле:

 

                                        Δ _{j = .}

 

а) ∆₁=0;

б) ∆₂= ;

в) ∆₃=0

г) ∆₄=

 

Поскольку среди ∆ есть отрицательные, то решение не является оптимальным.

 

Определение нового базиса

 

В качестве ведущего выберем  столбец, соответствующий переменной x₂. Т.к. в ведущем столбце есть отрицательно значение, то автоматически ведущей строкой будет А3, которая выйдет из базиса. Разрешающий элемент равен 13/6 и находится на пересечении ведущего столбца и ведущей строки.

 

Строим новую симплекс-таблицу:

 

			1	1	0	0
Базис	С базисное	B	A1	A2	A3	A4
A2	1	45/13	0	1	6/13	-1/13
A1	1	14/13	1	0	1/13	6/39
		f(x)	0	0	7/13	3/39

 

Найдем оценки Δ _j для всех A _i по формуле:

 

                                        Δ _{j = .}

 

а) ∆₁=0;

б) ∆₂=0;

в) ∆₃=

г) ∆₄=

Т.к. Среди оценок ∆_i нет отрицательных, следовательно, решение является оптимальным.