Тема 1. Линейное программирование

МЕТОДЫ ОПТИМИЗАЦИИ

Индивидуальные задания

Тема 1. Линейное программирование

Симплекс-метод

1.3. Для производства двух видов изделий A ₁ и A ₂ используется токарное (Т), фрезерное (Ф) и шлифовальное (Ш) оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида и общий фонд рабочего времени каждого из типов оборудования приведены в табл. 1.6 а, прибыль от реализации одного изделия каждого вида дана в табл. 1.6 б. Найти план выпуска изделий A ₁, A ₂, обеспечивающий максимальную прибыль от их реализации.

 

Таблица 1.6а		Таблица 1.6б
Варианты	Тип оборудования	Затраты времени на обработку 1 изделия (ст.-ч)	Общий фонд раб. времени оборудов. (ст.-ч)		Варианты	Прибыль от реализации 1 изделия (д. е.)
А 1	А 2		А 1	А 2
	Ф Т Ш
	Ф Т Ш
	Ф Т Ш
	Ф Т Ш
	Ф Т Ш

 

1.10. Для производства некоторого сплава используют 4 различных шихтовых материала A ₁, A ₂, A ₃, A ₄. Химический состав сплава определяется содержанием в нем химических элементов B ₁ и B ₂. Готовый сплав должен иметь строго определенный состав, который задается долями (в %) химических элементов в готовом продукте. При этом известно содержание (в %) каждого химического элемента во всех видах шихтового материала (см. табл. 1.13 а). Задана также стоимость каждого шихтового материала (табл. 1.13 б). Определить необходимое количество шихтовых материалов, обеспечивающее получение заданного количества сплава при минимальной общей стоимости используемых шихтовых материалов.

 

		Таблица 1.13а
Варианты	Химические элементы	Содержание (в %) химических элементов в шихтовом материале	Химический состав сплава (в %)	Заданное количество сплава (т)
A 1	A 2	A 3	A 4
	B 1 B 2					57,5 42,5
	B 1 B 2
	B 1 B 2					62,5 37,5
	B 1 B 2
	B 1 B 2

 

Таблица 1.13б

Варианты

Стоимость 1 т шихты (д. е .)

А 1

А 2

А 3

А 4

 

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

а) Целевые функции:

 

 

б) Ограничения:

1.		2.		3.
4.		5.		6.
7.		8.		9.
10.		11.		12.

1.20. Сформировать задачи ЛП (как на максимум, так и на минимум) из целевых функций а и ограничений б, отбросив, где необходимо, лишние переменные в целевых функциях, и свести их к канонической форме.

 

a) Целевые функции:

 

1. j x 1 - 3 x 2 - 3 x 3 2. j 2 x 1 - 2 x 2 + x 3 3. j 3 x 1 + x 2 - x 3 4. j 2 x 1 - 4 x 2 - 4 x 3 5. j 3 x 1 - 5 x 2 + 4 x 3 6. j x 1+ 2 x 2 - x 3 7. j 2 x 1 - 3 x 2 - x 3

8. j 2 x 1 + x 2 - x 3 9. j x 1 + x 2 - 5 x 3 10. j x 1 - 5 x 2 + x 3 11. j 5 x 1 + 2 x 2 - x 3 12. j 3 x 1 + 5 x 2 + 3 x 3 13. j 2 x 1 - x 2 + x 3

14. j x 1 - 2 x 2 + 3 x 3 - x 4 15. j x 1 + x 2 + 2 x 3 + x 4 16. j 2 x 1 - 2 x 2 - x 3 - x 4 17. j 2 x 1 + 2 x 2 + x 3 + 3 x 4 18. j 2 x 1 - x 2 + x 3 + 2 x 4 19. j 5 x 1 + 10 x 2 +15 x 3 + x 4 20. j 30 x 1 + 15 x 2 +10 x 3 - 5 x 4

 

б) Ограничения:

 

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.

1.27. Решить задачу 1.3, добавив к вариантам табл. 1.6 а дополнительные ограничения на выпуск продукции, заданные в табл. 1.39.

Таблица 1.39

Варианты	d *1	d *2

 

1.30. Из целевых функций 1.20 a и приведенных ниже ограничений a и б сформировать задачи ЛП на максимум, отбросив в целевых функциях, где необходимо, лишнюю переменную, и решить задачи симплекс-методом.

a) Ограничения:

1.		2.
3.		4.
5.		6.

б) К приведенным ниже основным ограничениям добавить следующие прямые ограничения:

0 £ x ₁ £ 5, 0 £ x ₂ £3, 1 £ x ₃ £5, 2 £ x ₄ £ 10.

 

1.		2.
3.		4.
5.		6.

 

Двойственные задачи. Анализ

2.9. Для задач 1.26-1.30 записать двойственные задачи.

 

2.10. Для задач 1.26-1.30 по оптимальному прямому плану найти оптимальный двойственный план, если он существует. Провести анализ чувствительности по векторам ресурсов, нижних и верхних прямых ограничений. Установить границы изменения координат указанных векторов, в которых оптимальный двойственный план устойчив. Для измененных значений параметров, входящих в пределы устойчивости оптимального двойственного плана, найти оптимальный прямой план, не решая задачу заново.

 

2.11. Решить задачи 1.26-1.30 двойственным симплекс-методом. Взяв параметры задач из-за пределов устойчивости оптимального двойственного плана, найти оптимальный прямой план, не решая задачи заново.

 

 

Таблица 3.3б

Варианты

с 12 с 15 с 23 с 27 с 34 с 46 с 56 с 58 с 68 с 71 с 73 с 75 с 83 с 84 с 87

 

3.6. Решить задачу 4.5, уменьшив предложение первого источника на 4 ед.

 

Таблица 4.13а

Варианты	Ресурсы районов (тыс. ц)	Мощности элеваторов (тыс. ц)
A 1	A 2	A 3	A 4	B 1	B 2	B 3	B 4	B 5

 

Таблица 4.13б

 

Матрицы тарифов
1.	10 8 5 9 16 4 3 4 11 12 5 10 29 7 6 9 2 4 1 3	2.	10 7 2 4 5 8 4 3 7 3 2 4 10 11 8 8 12 9 7 6	3.	3 9 11 8 11 6 2 3 6 5 10 4 13 8 10 3 8 7 5 7
4.	10 10 5 1 5 4 10 2 10 2 10 8 10 5 2 4 2 10 10 8	5.	6 2 10 4 10 2 1 1 9 10 5 2 10 10 7 10 5 10 4 8	6.	8 10 8 10 4 3 10 1 6 1 10 9 10 8 3 1 12 10 1 10

7.	3 4 10 10 3 9 10 7 7 10 9 8 10 8 10 2 10 8 10 9	8.	0 1 3 10 2 10 8 3 10 2 10 2 16 10 8 7 10 10 5 3	9.	10 6 10 7 3 2 10 1 9 10 2 3 15 10 10 10 5 10 6 5
10.	3 9 10 10 2 7 10 1 3 3 9 10 10 1 3 10 6 1 10 6	11.	3 4 10 2 10 3 6 4 10 10 10 7 8 10 4 10 4 1 2 10	12.	10 5 10 9 6 1 10 2 2 10 10 5 12 10 1 10 9 3 3 10
13.	10 10 1 2 9 10 6 1 5 3 10 8 14 5 10 9 10 2 6 10	14.	10 4 8 6 10 10 2 3 10 3 7 10 10 2 3 10 3 2 10 1	15.	4 6 8 10 2 3 4 3 9 5 4 6 13 2 1 2 3 4 10 9
16.	8 5 8 2 7 9 2 3 10 9 16 12 12 8 14 10 6 3 6 12	17.	9 10 16 4 12 13 1 2 1 9 2 20 12 8 4 30 10 10 14 18	18.	3 10 6 10 10 10 2 1 8 12 16 10 15 10 10 9 14 10 10 10
19.	10 8 3 8 5 10 5 2 1 14 10 12 20 13 20 6 2 16 3 18	20.	10 6 14 16 7 8 3 3 8 5 12 20 14 20 10 10 5 18 16 4	21.	1 3 4 7 5 10 8 1 2 3 8 10 14 6 8 7 5 9 12 11
22.	3 5 11 8 10 8 7 1 4 3 10 11 12 9 7 6 4 7 8 10	23.	4 5 8 7 5 5 10 1 11 8 3 4 8 7 1 2 10 11 10 4	24.	3 5 7 5 4 10 12 1 4 8 10 11 10 8 7 10 8 9 7 8
25.	10 3 8 11 2 8 7 6 10 5 11 10 12 9 10 12 14 10 14 8	26.	10 1 7 2 4 8 3 2 2 10 5 2 6 2 2 10 3 2 4 2	27.	11 12 13 14 15 6 7 6 9 10 1 2 5 4 5 17 15 19 12 11
28.	1 2 3 6 5 6 7 3 9 10 1 2 5 4 5 6 7 8 9 2	29.	1 5 9 3 6 2 6 5 4 7 3 7 16 5 8 4 8 12 6 2	30.	6 8 4 10 10 10 12 1 8 9 12 13 13 5 4 2 4 8 6 9

 

4.8. Решить задачу 4.1 при наличии прямых ограничений на перевозки, определенных матрицей ограничений

 

.

 

4.9. а) Используя первую фазу, построить начальный базисный план перевозок для задания 4.8.

б) Уменьшив в матрице задания 4.8 на 5 единиц, построить начальный базисный план перевозок, используя первую фазу.

 

Таблица 5.3

 

Варианты
a			-1					-1
b	-1		-1
с	-1			-1	-1				-1
Варианты
a			-3	-2					-2
b				-2	-2
с			-1					-1
Варианты
a							-6
b	-1		-2
с	-1		-1				-1

 

5.21. Записать уравнение гиперплоскости, опорной к множеству X = в точке = , координаты которой заданы в табл. 5.4. Если точка Ï X, то выписать уравнение отделяющей гиперплоскости.

 

Таблица 5.4

 

Вари-анты
	-6/5	-8/5		6/5		8/5		6/5	8/5
	12/5		9/5		12/5	9/5	-9/5	-12/5		-9/5
									-3	-4
Вари-анты
		6/5	8/5		8/5	6/5		-6/5	-8/5
	9/5		-9/5	12/5		12/5	-12/5		-9/5	-12/5
	-4	-4		-3						-3
Вари-анты
		-			-8/5	-6/5		-6/5	3/2	-3/2
							-12/5	-12/5
		-			-3	-4	-3

5.22. Выписать уравнение гиперплоскости, опорной к множеству X и отделяющей его от точки , координаты которой заданы в табл. 5.5.

Таблица 5.5
Варианты
	5/4	4/3	5/3	5/4	5/3	3/2	3/2	5/4	10/9	13/9
	5/16	2/3	5/9	15/16	10/9	3/2	3/8	5/8	10/27	26/27
	15/16	13/12	7/9	23/16	10/9	7/4	13/16	9/8	19/18	11/9
Вари-анты
	1/2	1/3				5/4				4/5
	1/2	2/3								1/5
	1/2	3/9								12/25
Варианты
	9/8	5/4	9/8	4/3	5/3	11/9	7/5	3/2	4/3	11/9
	27/32	5/4	9/32	4/9	5/6	22/27	14/25	3/4	8/9	11/27
	3/2	15/8		17/18	11/12	4/3	24/25		23/18

 

5.23. Записать уравнение гиперплоскости, разделяющей множества , (числа a, b, c заданы в табл. 5.6).

Таблица 5.6

 

Варианты
a	1/9		1/4		1/9			1/4	1/9
b	2/3				16/3			9/2	8/3
с	8/3		9/4		1/3			1/2	2/3
Варианты
a	1/4		9/4			1/4	1/9		9/4
b	1/2					9/4	1/3		5/4
c	9/2		5/4				16/3
Варианты
a				3/4			21/20		3/2	7/4
b				1/4			3/2
c							2/3	1/4	1/2	1/4

 

5.26. Проверить, является ли функция f выпуклой (вогнутой) на заданном множестве X, или указать такие точки из X, в окрестности которых f не является ни выпуклой, ни вогнутой:

 

1. ;

2. ;

3. ;

4. ;

5. X = R ³;

6. ;

7. X = R ³;

8. X = R ³;

9. X = R ³;

10. ;

11. X = R ³;

12. X = R ³;

13. ;

14. ;

15. ;

16. X = R ³;

17. ;

18. X = R ³;

19. ;

20. X = R ³;

21. X = R ³;

22. ;

23. X = R ³;

24. ;

25. ;

26. ;

27. ;

28. X = R ³;

29. X = R ³;

30. ;

31. X = R ²;

32. X = R ²;

33. X = R ²;

34. ;

35. ;

36. ;

37. ;

38. ;

39. ;

40. ;

41. ;

42. ;

43. ;

44. ;

45. ;

46. ;

47. ;

48. ;

49. ;

50. ;

51. ;

52. ;

53. ;

54. .

 

Задачи условной оптимизации

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

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.
31.		32.
33.		34.
35.		36.
37.		38.
39.		40.
41.		42.
43.		44.
45.
46.
47.

 

48.
49.
50.

 

Тема 4. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ НЕЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

Метод ветвей и границ

10.3. Решить задачу о рюкзаке с данными, приведенными ниже.

 

1. с 45

2. с 45

i

i

ci

ci

pi

pi

 

3. с 35

4. с 50

i

i

ci

ci

pi

pi

 

5. с 26

6. с 40

i

i

ci

ci

pi

pi

 

 

7. с 45

8. с 55

i

i

ci

ci

pi

pi

 

9. с 44

10. с 38

i

i

ci

ci

pi

pi

 

11. с 32

12. с 48

i

i

ci