Е.В. Буйная Симплексный метод решения оптимизационных задач

21
27. Минимизировать	28. Минимизировать
F(x)=x1+2x2 – x3	F(x)=-3x1+ x2 + x3
при условиях	при условиях
-x1 + 4x2 - 2x3 ≥ 6	4x2 - 5x3 ≥ 3
x1 + x2 + 2x3 ≥ 6	3 ≤ x1 - x2 + 2x3 ≤ 12
2x1 - x2+ 2x3 =4	x1 + x2+ x3 ≤ 9
x1 ≤ 0	5x1 - 20 ≥	2
x2, x3 ≥ 0	2,5 ≤ x2 ≤	18,	x1, x3 ≥ 0
29. Максимизировать	30. Минимизировать
F(x)=8x1 - 3x2 + x3 +6x4 – 5x5	F(x)=x1+3x2 – 5x4
при условиях	при условиях
2x1 + 4x2 + x3 + x4 – 2x5 =28	2x1 + 4x2 + x3 + 2x4 ≥ 28
x1 - 2x2 + x4 + x5 =31	-3x1 + 5x2 - 3x4		≤ 30
-x1 + 3x2+ 5x3 + 4x4 – 8x5 =118	4x1 - 2x2+ 8x4		≤ 32
x2, x3, x4 ≥ 0	x2, x3, x4 ≥ 0
31. Минимизировать	32. Максимизировать
F(x)=18x1+16x2+5x3+21x4–15x5	F(x)=2x1 -13x2 - 6x3
при условиях	при условиях
x1 + 2x2 +3x3 ≥ 2	x1 - x2 + 3x3 ≥ 12
3x1 + x2 + x3 ≥ 3	x1 - 2x2 + x3 ≤ -10
x5 ≤ 11	x1 ≤ 5
x1, x2, x3, x4 ≥ 0	x2, x3 ≥ 0

33. Максимизировать	34. Минимизировать
F(x)=14x1+10x2+14x3 +14x4	F(x)=-6x1+10x2+9x3 +8x4
при условиях	при условиях
4x1 + 2x2 +2x3 + x4 ≤ 35	-2x1 + x2 +x3 ≥ 2
x1 + x2 + 2x3 + 3x4 ≤ 30	x1 - x2 – x4 ≤ -1
3x1 + x2 + 2x3 + x4 ≤ 40	5x1 – 3(x3 + x4 ) ≥ 12
x1, x2, x3 ≥ 0	x1, x2, x3, x4 ≥ 0
x4 ≤ 0

	22
35. Максимизировать		36. Минимизировать
F(x)=6x1+3x2- 4x3 +5x4 + 6x5 -2x6		F(x)=x1+3x2+2x3
при условиях		при условиях
x1 + 2x2 –3x3 + x4 – x5+2x6≤ 36		3x1 - 2x2 + x3 ≥	5
-x1 + 3x2 +4x3 +2x4 + 3x6 =24		x1 + x2 + 2x3 ≥	10
2x1 - 4x2 + 5x3 + 5x5 –x6 ≤ 20		-2x1 + 3x2 – x3 ≥ 2
x1 + 2x2 + x3 + x4 + 4x5 ≤ 12		x1, x2, x3 ≥ 0
x1, x2, x3, x4 , x5, x6 ≥ 0
37. Минимизировать		38. Максимизировать
F(x)=x1+ x2+ x3 + x4		F(x)=4x1+3x2+6x3 +7x4
при условиях		при условиях
x1 - x2 - 2x3 + x4 ≥	6	2x1 + x2 +x3 + x4 ≤ 280
-x1 + x3 ≤ 2		x1 + x3 + x4 ≤ 80
2x2 – 3x3 + 2x4 ≤	8	x1 + 2x2 + x3 ≤ 250
x1 ≥ 10 , x2 ≥ 2 , x3, x4 ≥ 0		x1, x2, x3, x4 ≥ 0
39. Максимизировать		40. Минимизировать
F(x)=x1+3x2+2x3		F(x)=3x1 + 2x5 – 6x6
при условиях		при условиях
3x1 - 2x2 + x3 ≥ 12		2x1 + x2 -3x5 + 5x6 = 34
x1 + x2 + 2x3 =9		4x1 + x3 +2x5 - 4x6 =28
-2x1 + 3x2 – x3 ≤ 8		-3x1 + x4 -3x5 +6x6 =24
x1 ≥ 0		x1, x2, x3, x4 , x5, x6 ≥ 0

41. Минимизировать	42. Минимизировать
F(x)=2x1 -3x2+ 4x3+5x4 - x5 + 8x6	F(x)=4x1 +15x2+ 12x3+2x4
при условиях	при условиях
x1 + 5x2 -3x3 - 4x4 + 2x5 +x6 = 120	2x2 +3x3 + x4 ≥ 5
2x1 + 9x2 -5x3 - 7x4+4x5+2x6 =320	x1 + 3x2 + x3 - x4 ≥ 0
x2 ≤ 0 , x1, x3, x4 , x5, x6 ≥ 0	x3 ≥ 1, x4 ≤ 0 , x1, x2 ≥ 0

	23
43. Минимизировать	44. Максимизировать
F(x)=x1+ x2+ x3 - x4	F(x)=x1+3x2+2x3
при условиях	при условиях
x1 - x2 - 2x3 + x4 ≥ 9	3x1 - 2x2 + x3 ≥ 5
-x1 + x3 ≤ 2	x1 + x2 + 2x3 =10
2x2 – 3x3 + 2x4 ≤ 8	-2x1 + 3x2 – x3 ≤ 20
1,5 ≤ x1≤ 10	x1, x2, x3 ≥ 0
x2, x3 ≥ 0
45. Максимизировать
F(x)=5x1 - x2+8x3+10x4 - 5x5 + x6
при условиях
2x1 - x2 +3x3 + x5 - x6 ≥	36

-x1 +2x2 +x3 +2x4 + 2x6 =20 3x1 - x2+2x3 – x4 + 3x5 + x6 =30

x1, x2, x3, x4 , x5, x6 ≥ 0

6.Контрольные вопросы

1.Что означает «найти оптимальное решение задачи»?

2.В чем преимущества симплекс-метода поиска оптимального плана перед перебором всех вариантов решения задачи?

3.Объясните, почему при поиске оптимального решения задачи рассматривают только опорные планы?

4.Подумайте, каким образом можно сократить размерность зада-

чи?

5.Почему искусственные переменные в целевой функции отражаются с коэффициентом +М для задачи минимизации и -М для задачи максимизации?

6.В каких случаях невозможен дальнейший перебор опорных пла-

нов?

7.Если найденный оптимальный план не единственный, как найти остальные варианты оптимального поведения?

8.В каком случае нельзя привести задачу к каноническому виду?

9.Почему нельзя использовать стандартный симплекс-метод для решения нелинейных задач?

10.В каком случае, решая задачу симплекс-методом, вы сделаете вывод, что она не разрешима?

24

11.Cуществует ли гарантия решения задачи за конечное число симплексных преобразований?

12.Имеется задача поиска максимума линейной функции при трех ограничениях на 5 неотрицательных переменных. Может ли ее план с компонентами (1, 2, 3, 4, 5) быть оптимальным?

СПИСОК ЛИТЕРАТУРЫ

1.Тынкевич М.А., Ветрова Г.С., Бияков О.А. Экономикоматематические методы (исследование операций). -Кемерово: КузГТУ, 1997.-176с.

2.Акулич И.Л. Математическое программирование в примерах и задачах.- М.: Высш.шк.,1986.-319с.

3.Карасев А.И. и др. Математические методы и модели в планировании.- М.: Экономика,1987.-240с.

4.Исследование операций в экономике/ Под ред.проф. Н.Ш. Кре- мера.-М: Банки и биржи,1997.-407с.

25

Составители Елена Васильевна Буйная

Моисей Аронович Тынкевич

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Методические указания и задания к практическим занятиям по курсу «Экономико-математические методы» для студентов экономических специальностей

Редактор З.М. Савина

ЛР № 020313 от 23.12.96

Подписано в печать 29.12.99. Формат 60х84/16.

Бумага офсетная. Уч.-изд.л. 1,4 . Отпечатано на ризографе. Тираж 200 экз. Заказ .

Кузбасский государственный технический университет. 650026, Кемерово,ул. Весенняя, 28.

Типография Кузбасского государственного технического университета.

650099, Кемерово, ул. Д.Бедного, 4А.