К О Н Т Р О Л Ь Н А Я Р А Б О Т А

По предмету: Экономико-математический практикум

Выполнил:

Студент 2 курса

Семестр

Рахимова Лидия Рустамовна

Ташкент,2009

Задача № 1

 

Условно стандартная задача линейного программирования

Необходимо выполнить в указанном порядке следующие задания.

1. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

2. Построить двойственную задачу.

3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.

4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).

6. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений

4

Решение задачи 1

1. Найдем оптимальный план решения графическим методом:

 

;

 

Построим на координатной плоскости Ох ₁ х ₂ граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):

 

 

Область допустимых решений определяется многоугольником ОАВС D (см. график 1).

Для линий уровня х ₁ - 3 х ₂ = h (h — const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора  до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L ₃ и L ₄, т. е. через точку . Для определения координат точки P решаем систему уравнений

.

 

Получаем х ₁ = 5,3, х ₂ = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Z _min=3,5

 

 

 

 

10

 

6

 

4

 

 

P

 

2

 

 

 

 

				(4)
	(3)
			(2)

 

 

График № 1

1б) Перейдем к расширенной задаче:

 

 

Данная расширенная задача имеет начальное опорное решение  с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

 

 

Расчеты проведем в таблице (Табл. 1)

 

Таблица 1

				1	-3	0	0	0	0	M
	Б	Сб	В	А 1	А 2	А 3	А 4	А 5	А 6	А 7
	А 3	0	9	-2	3	1	0	0	0	0
	А 4	0	53	5	2	0	1	0	0	0
	А 5	0	17	4	-7	0	0	1	0	0
←	А 7	М	37	6	8	0	0	0	1	1
			0	–1	3	0	0	0	0	0
			37	6	8	0	0	0	0	0

Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора А _k, вводимого в базис опорного решения, и вектора А _l, выводимого из базиса. Наибольшая положительная оценка соответствует А₂, за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.

Вектор А₂ выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение  с базисом  (табл. 1.3). Целевая функция  =-3 М -21. Это решение не является оптимальным, так как есть положительная оценка.

 

Таблица 1

Б	Сб	B	А 1	А 2	А 3	А 4	А 5	А 6	
А2	-3	3,0	-0,7	1,0	0,3	0,0	0,0	0,0	0,0
А 4	0	47,0	6,3	0,0	-0,7	1,0	0,0	0,0	0,0
А 5	0	38,0	-0,7	0,0	2,3	0,0	1,0	0,0	0,0
a7	М	13,0	11,3	0,0	-2,7	0,0	0,0	1,0	1,0
M+1		-9,0	1,0	0,0	-1,0	0,0	0,0	0,0	0,0
M+2		13,0	11,3	0,0	-2,7	0,0	0,0	0,0	0,0
A2	-3	-2,4	-0,6	1,0	0,0	0,0	-0,1	0,0	0,0
a4	0	57,9	6,1	0,0	0,0	1,0	0,3	0,0	0,0
А 3	0	16,3	-0,3	0,0	1,0	0,0	0,4	0,0	0,0
A7	М	56,4	10,6	0,0	0,0	0,0	1,1	1,0	1,0
M+1		7,3	0,7	0,0	0,0	0,0	0,4	0,0	0,0
M+2		56,4	10,6	0,0	0,0	0,0	1,1	0,0	0,0
A2	-3	0,6	0,0	1,0	0,0	0,0	-0,1	0,1	0,1
a4	0	25,1	0,0	0,0	0,0	1,0	-0,4	-0,6	-0,6
А 5	0	17,8	0,0	0,0	1,0	0,0	0,5	0,0	0,0
A1	1	5,3	1,0	0,0	0,0	0,0	0,1	0,1	0,1
		3,5	0,0	0,0	0,0	0,0	0,4	-0,1	-0,1
		0,0	0,0	0,0	0,0	0,0	0,0	-1,0	-1,0

Целевая функция после второй итерации равна  = 3,5. Все оценки отрицательные, план оптимален.

 

 

 

Оптимальный план исходной задачи Х^*=(х₁^*=5,3; х₂^*=0,6). Минимальное значение целевой функции исходной задачи =3,5.

 

Ответ: min Z (X ^*) =3,5.

Двойственная задача

 

Двойственная задача имеет вид.

 

 

при условиях