Задачи линейного программирования (ЛП).

KОНТРОЛЬНАЯ РАБОТА ПО МАТЕМАТИЧЕСКОМУ

ПРОГРАММИРОВАНИЮ И МАТЕМАТИЧЕСКИМ МЕТОДАМ ИССЛЕДОВАНИЯ В ЭКОНОМИКЕ

Задачи нелинейного программирования.

Для задач 1–40:

1) составить математическую модель задачи применительно к числовым данным выполняемого варианта;

2) решить полученную задачу с помощью MathCAD как задачу нелинейного программирования;

3) графическим методом решить полученную задачу и сформулировать ответ в экономических терминах в соответствии с условиями задачи.

Формулировка задачи. Предприятие выпускает изделия А и В, при изготовлении которых используется сырьё S₁ и S₂. Известны запасы b_i (i=1,2) сырья, нормы a_ij (j=1,2) его расхода на единицу изделия, плановая себестоимость и оптовые цены р_j. Как только объём выпускаемой продукции перестаёт соответствовать оптимальным размерам предприятия, дальнейшее увеличение выпуска х_j ведёт к повышению себестоимости продукции, и в первом приближении фактическая себестоимость с_j описывается функцией с_j= +с¢х_j, где с¢ – некоторая постоянная величина. При поиске плана выпуска изделий, обеспечивающего предприятию наивысшую прибыль в условиях нарушения баланса между объёмом выпуска и оптимальными размерами предприятия, целевая функция принимает вид

z=(р₁-( +с¢х₁))х₁+(р₂-( +с¢х₂))х₂,

а ограничения по сырью

a₁₁х₁+a₁₂х₂≤b₁,

a₂₁х₁+a₂₂х₂≤b₂,

х₁≥0, х₂≥0

(нормы расхода сырья a_ij от х_j не зависят).

Все необходимые числовые данные указаны в таблице.

Номер задачи	b1	b2	a11	a12	a21	a22	р1	р2			с¢
											0,2
											0,1
											0,1
											0,2
											0,2
											0,1
											0,2
											0,2
											0,3
											0,3
							8,6	5,4		4,6	0,2
	22,5			1,5					2,25	3,25	0,125
											0,2
				8,5						4,5	0,25
									7,4	7,2	0,4
	7,5			0,5		8,5	12,75				0,125
									4,8	5,4	0,2
		82,5	1,6	0,8	5,5	7,5		22,5			0,25
									6,4	11,2	0,4
	37,5			2,5		9,5	15,5	21,75	12,75	18,5	0,125
									3,6	2,8	0,2
	22,5			1,5	6,5			18,5			0,25
									2,6	2,4	0,4
			1,5				6,25	6,25			0,125
								18,6		16,2	0,2
			2,5								0,25
									2,4		0,4
			3,5					2,25		0,5	0,125
							15,6	23,8		22,2	0,2
			4,5								0,25
Номер задачи	b1	b2	a11	a12	a21	a22	р1	р2			с¢
							6,46	9,6	5,6		0,2
		22,5				1,5			4,25	3,25	0,125
			0,5		5,5						0,1
					0,5						0,2
			0,5								0,2
											0,1
									3,8	4,4	0,2
	82,5		5,5	7,5	1,6	0,8				4,5	0,25
									2,4	7,2	0,4
		37,5		9,5		2,5		10,25	7,25		0,125

В задачах 41–50:

дана линейная целевая функция и нелинейная система ограничений. Найти глобальные экстремумы функции.

При этом в №№41–45принять математическую модель задачи вида

L=c₁х₁+c₂х₂,

≤b₁,

х₁≥0, х₂≥0;

в №№46–50– вида

L=c₁х₁+c₂х₂,

х₁х₂≤b₁,

х₁≤b₂,

х₂≤b₃,

х₁≥0, х₂≥0.

Значения коэффициентов целевых функций и систем ограничений приведены в таблице.

Значения	№ задачи
c1			-1		-3			-2		-1
c2			-2		-1			-1		-2
b1
b2	–	–	–	–	–
b3	–	–	–	–	–

В задачах 51–60:

дана нелинейная целевая функция и линейная система ограничений. Найти глобальные экстремумы функции.

Математическая модель задачи:

L=(х₁+а)²+(х₂+b)²,

а₁₁х₁+а₁₂х₂≤b₁,

а₂₁х₁+а₂₂х₂≤b₂,

х₁≥0, х₂≥0.

Значения коэффициентов целевой функции и системы ограничений приведены в таблице.

Значения	№ задачи
а	-5	-6	-1	-2	-3	-1	-3	-2	-2
b	-4	-2	-1	-1	-4	-1	-1	-6	-2	-1
а11
а12	-4		-4
b1	-20		-20
а21
а22									-2	-2
b2									-6	-6

В задачах 61–70:

дана нелинейная целевая функция и нелинейная система ограничений. Найти глобальные экстремумы функции.

При этом в №№61–65принять математическую модель задачи вида

L=(х₁+а)²+(х₂+b)²

х₁х₂≤b₁,

х₁≤b₂,

х₂≤b₃,

х₁≥0, х₂≥0;

в №№66–70– вида

L=(х₁+а)²+(х₂+b)²

≤b₁,

х₁≤b₂,

х₂≤b₃,

х₁≥0, х₂≥0.

Значения коэффициентов целевой функции и системы ограничений приведены в таблице.

Значения	№ задачи
а		-2		-1		-1	-1			-2
b	-1		-2	-1		-2		-1	-2
b1
b2						3,5	4,5	5,5	6,5	2,8
b3						3,5	4,5	5,5	6,5	2,8

Задачи теории игр.

Решить графически игру, заданную платёжной матрицей (2´n).

№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

Решить графически игру, заданную платёжной матрицей (m´2).

№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

Решить матричную игру т´п с помощью линейного

программирования………

№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

KОНТРОЛЬНАЯ РАБОТА ПО МАТЕМАТИЧЕСКОМУ

ПРОГРАММИРОВАНИЮ И МАТЕМАТИЧЕСКИМ МЕТОДАМ ИССЛЕДОВАНИЯ В ЭКОНОМИКЕ

Задачи линейного программирования (ЛП).

Задачи 1-50 решить ЛП графически (найти максимум и минимум

целевой функции z); все переменные неотрицательны.

1) z=x₁+2x₂ 2) z=3x₁+4x₂ 3) z=x₁+7x₂ 4) z=x₁-3x₂ 5) z=2x₁-6x₂

x₁+x₂≥1 3x₁+2x₂≥6 -x₁+x₂≤4 x₁+2x₂≥3 x₁+x₂≥4

-2x₁+x₂≤2 -3x₁+2x₂≤7 x₁+x₂≥2 x₁-2x₂≤2 2x₁-6x₂≤12

x₁+x₂≤4, x₁≤3 2x₁-4x₂≤8, x₁≥1 x₁+2x₂≤10, x₁≥1 x₁+2x₂≤6, x₁≥1 x₁≥2

6) z=2x₁+x₂ 7) z=2x₁+4x₂ 8) z=2x₁+x₂ 9) z=3x₁+2x₂ 10) z=x₁-2x₂

x₁+2x₂≥8 -x₁+3x₂≥0 x₁+3x₂≥9 3x₁+4x₂≤12 x₁+x₂≥2

x₁+x₂≤8 3x₁+6x₂≤12 2x₁+4x₂≤16 2x₁+x₂≥2 x₁-x₂≤1

-2x₁+x₂≤2 -4x₁+2x₂≤8 x₁-x₂≤2 x₁-2x₂≤0

11) z=x₁+3x₂ 12) z=2x₁+3x₂ 13) z=x₁+x₂ 14) z=3x₁-2x₂ 15) z=5x₁-3x₂

x₁-x₂≥0 x₁+x₂≥1 x₁+2x₂≥2 3x₁+4x₂≥20 3x₁+2x₂≥6

x₁-x₂≤1 3x₁+2x₂≤6 x₁+2x₂≤10 2x₁+x₂≤11 -2x₁+3x₂≤6

2x₁+x₂≤2 -x₁+x₂≤2 2x₁+x₂≤10 -3x₁+2x₂≤10 x₁-x₂≤4

16) z=x₁+2x₂ 17) z=7x₁-2x₂ 18) z=2x₁+x₂ 19) z=2x₁+2x₂ 20) z=2x₁-4x₂

3x₁+4x₂≥27 x₁+x₂≥1 5x₁+2x₂≥10 x₁+x₂≥3 2x₁+7x₂≥9

2x₁+x₂≤14 5x₁-2x₂≤3 4x₁-3x₂≤12 -3x₁+2x₂≤6 8x₁-5x₂≤16

-3x₁+2x₂≤9 2x₁+x₂≤4 7x₁+4x₂≤28 x₁≤3 x₁+3x₂≤2

21) z=x₁+2x₂ 22) z=3x₁+3x₂ 23) z=2x₁-x₂ 24 )z=7x₁+x₂ 25) z=x₁+x₂

x₁+x₂≥4 x₁+2x₂≥2 x₁+x₂≥4 5x₁+3x₂≥21 3x₁+x₂≥8

5x₁-2x₂≤4 3x₁+2x₂≤6 -x₁+x₂≤3 x₁+x₂≤14 x₁+2x₂≤6

-x₁+2x₂≤4 -x₁+x₂≤1 6x₁+7x₂≤42 3x₁-5x₂≤15 x₁-x₂≤3

26) z=-3x₁+6x₂ 27) z=-2x₁+x₂ 28) z=-2x₁+x₂ 29) z=2x₁-x₂ 30) z=2x₁-4x₂

x₁+x₂≥4 x₁+3x₂≥6 -3x₁+2x₂≥3 x₁+2x₂≥2 x₁+3x₂≥2

5x₁-2x₂≤4 2x₁+x₂≤8 2x₁+x₂≤8 -x₁+x₂≤3 8x₁-5x₂≤16

-x₁+2x₂≤4 -2x₁+x₂≤4 x₁+x₂≤6 6x₁+7x₂≤42 2x₁+7x₂≤9

31) z=2x₁-3x₂ 32) z=-2x₁+x₂ 33) z=6x₁+4x₂ 34) z=-x₁-2x₂ 35) z=6x₁+4x₂

5x₁+2x₂≥10 -3x₁+2x₂≥3 2x₁+x₂≥3 x₁+x₂≥4 2x₁+x₂≥3

x₁+3x₂≤12 x₁+x₂≤6 x₁+x₂≤8 5x₁-2x₂≤4 x₁-x₂≤1

2x₁-x₂≤10 -x₁+x₂≤4 -x₁+x₂≤4 -x₁+2x₂≤4 x₁+x₂≤8

36) z=4x₁+3x₂ 37) z=x₁+3x₂ 38) z=x₁-2x₂ 39) z=2x₁-x₂ 40) z=3x₁+2x₂

5x₁+2x₂≥20 x₁+x₂≥3 x₁+x₂≥1 3x₁+2x₂≥16 2x₁+x₂≥3

x₁+3x₂≤15 6x₁+x₂≤42 5x₁-2x₂≤3 x₁+2x₂≤12 x₁-2x₂≤2

x₁+x₂≤10 -x₁+x₂≤6 -3x₁+x₂≤3 2x₁+x₂≤18 x₁+2x₂≤8

41) z=-x₁-2x₂ 42) z=x₁+2x₂ 43) z=x₁+x₂ 44) z=x₁+2x₂ 45) z=2x₁-3x₂

x₁+x₂≥4 x₁+x₂≥16 x₁+2x₂≥4 x₁+2x₂≥14 5x₁+2x₂≥10

5x₁-2x₂≤4 5x₁-2x₂≤20 2x₁+x₂≤8 2x₁+x₂≤18 x₁+3x₂≤12

-x₁+2x₂≤4 -x₁+2x₂≤4 x₁+4x₂≤10 x₁+x₂≤9 x₁+x₂≤10

46) z=2x₁-x₂ 47) z=3x₁+2x₂ 48) z=x₁+2x₂ 49) z=x₁-2x₂ 50) z=x₁+2x₂

-x₁+2x₂≥2 3x₁+4x₂≥20 3x₁+4x₂≥27 2x₁+7x₂≥9 x₁+x₂≥4

5x₁+9x₂≤45 2x₁+x₂≤11 2x₁+x₂≤14 8x₁-5x₂≤16 5x₁-2x₂≤4

2x₁+x₂≤6 -3x₁+2x₂≤10 -3x₁+2x₂≤9 x₁+3x₂≤2 -x₁+2x₂≤4

Для задач 51–90:

1) составить математическую модель;

2) решить графически;

3) решить симплекс-методом;

4) показать соответствие опорных решений и вершин допустимой области.

Формулировка задачи. Предприятие выпускает продукцию двух разновидностей. Каждый вид продукции проходит обработку на трёх станках. При обработке 1 т продукции I вида первый станок используетcя а₁₁ ч., второй станок – а₂₁ ч., третий станок – а₃₁ ч.. При обработке 1 т продукции II вида первый станок используется a₁₂ ч., второй станок – a₂₂ ч., третий станок – a₃₂ ч. Время работы станков ограничено и не может превышать для первого станка b₁ ч., для второго b₂ ч., для третьего b₃ ч. При реализации 1 т продукции I вида предприятие получает прибыль с₁ руб., а при реализации 1 т продукции II вида – с₂ руб. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.

№ задачи	К-т аi1	К-т аi2	К-т bi.	К-т сj		№ задачи	К-т аi1	К-т аi2	К-т bi.	К-т сj
	1,1,3	4,1,1	28,10,24	3,6			1,3,7	2,4,4	22,46,70	6,8
	1,3,2	3,4,1	24,37,18	3,5			2,1,5	3,1,3	30,11,45	5,6
	0,1,5	1,4,4	6,27,55	2,9			1,3,5	2,5,4	18,46,55	6,10
	0,1,1	1,4,1	7,29,11	2,5			1,3,2	3,4,1	24,37,18	2,4
	1,1,7	2,1,6	22,12,77	6,7			1,3,7	2,5,4	22,56,77	4,7
	1,4,5	1,3,3	10,31,35	8,6			2,3,2	4,4,1	36,40,20	5,8
	1,1,2	5,1,1	30,10,18	3,9			1,4,4	1,3,1	13,40,24	8,6
	1,2,3	2,3,2	14,23,27	4,7			1,2,4	4,3,1	28,26,32	2,4
	1,2,3	2,3,2	16,26,29	7,12			1,3,5	3,5,2	27,49,50	5,12
	1,1,3	4,1,1	24, 9,23	6,12			1,3,5	3,5,1	27,49,45	2,4
	0,2,3	1,5,2	8,44,27	2,10			1,3,10	2,5,3	28,71,100	6,10
	1,2,5	2,3,2	20,31,50	4,6			1,1,5	3,2,2	24,17,45	2,5
	1,3,3	2,5,2	14,36,27	12,23			1,3,5	2,5,2	18,46,45	6,11
	2,5,2	3,4,1	33,51,18	3,4			1,4,3	3,5,1	33,62,30	3,6
	0,1,6	1,4,5	7,28, 54	3,4			1,3,3	2,4,1	26,54,27	6,8

№ задачи	К-т аi1	К-т аi2	К-т bi.	К-т сj		№ задачи	К-т аi1	К-т аi2	К-т bi.	К-т сj
	1,1,3	4,1,1	28,10,24	4,4			1,1,2	5,1,1	30,10,18	3,3
	1,3,2	3,4,1	24,37,18	6,8			1,2,3	2,3,2	14,23,27	4,6
	0,1,5	1,4,4	6,27,55	2,8			1,2,3	2,3,2	16,26,29	6,9
	1,1,7	2,1,6	22,12,77	7,7			1,1,3	4,1,1	24,9,23	6,6
	1,3,1	1,1,4	10,24,28	6,6			3,1,6	3,4,2	27,24,26	8,8

Задачи 91–120 решить симплекс-методом.

Решить стандартную задачу линейного программирования

z=c₁x₁+c₂x₂+c₃x₃àmax

при условиях, что переменные х₁, х₂, х₃ неотрицательны и удовлетворяют системе неравенств

а₁₁х₁+а₁₂х₂+а₁₃х₃ b₁;

a₂₁x₁+a₂₂x₂+a₂₃x₃ b₂;

а₃₁х₁+а₃₂х₂+а₃₃х₃ b₃

№ задачи	К-т аi1	К-т аi2	К-т аi3	К-т bi	К-т сj		№ задачи	К-т аi1	К-т аi2	К-т аi3	К-т bi	К-т сj
	1,2,1	2,-1,2	3,1,-2	5,8,1	1,1,-1			2,1,1	-1,2,-1	2,1,0	9,7,1	2,2,-1
	2,1,0	0,3,-1	3,0,2	2,1,3	5,6,8			1,1,2	2,0,-1	-1,1,1	8,6,5	1,1,-2
	2,-1, 0	0,3,-1	3,0,1	3,2,1	3,2,5			1,2,1	-1,3,1	1,2,0	6,9,4	2,-1,1
	2,0,1	-1,1,0	1,2,1	4,6,6	3,2,-1			1,1,1	1,0,2	1,2,1	1,2,2	3,3,2
	1,0,1	-1,1,0	2,3,2	3,5,3	1,1,1			2,1,1	1,-1,1	-3,2,1	4,7,8	1,2,-1
	5,1,0	3,2,1	0,4,1	8,4,1	1,3,1			1,2,1	1,-1,0	-1,1,4	3,5,9	1,-1,1
	1,0,1	2,1,0	0,1,1	3,1,1	1,2,1			0,1,2	2,-1,3	1,3,1	6,4,10	1,2,-5
	2,1,1	1,2,1	1,1,1	2,3,5	3,2, 1			1,2,-1	1,-1,1	-1,0,1	4,2,8	2,3, 6
	1,0,1	0,2,-1	1,0,3	1,2,3	3,2,5			2,-1,1	1,0,2	3,2,-1	5,7,4	1,1,-1
	3,1,0	0,-2,3	1,0,1	3,6,1	9,5,3			0,2,3	1,-1,1	1,2,0	7,5,3	3,-1,2
	3,1,1	4,3,1	1,2,-1	5,4,1	2,1,3			2,1,0	3,2,1	-1,1,2	6,7,9	4,-1,2
	1,-1,2	1,0,2	2,1,1	2,6,3	2,-1,2			1,0,2	-2,1,3	2,1,1	2,4,3	2,-1,1
	1,2,-1	2,1,0	1,0,2	3,2,4	2,1,1			2,1,1	1,1,1	1,-2,1	8,3,5	1,1,-1
	3,-1,-4	-1,2,3	1,0,4	7,6,10	-1,3,-1			2,0,1	1,1,0	1,2,1	4,6,6	3,2,8
	1,2,0	2,-1,1	1,1,2	5,1,3	2,-1,7			1,0,2	1,1,0	1,2,-1	2,2,4	1,1,2

Для задач 121–130:

1) составить математическую модель задачи;

2) решить задачу графически;

3) решить задачу симплекс-методом;

4) показать соответствие опорных решений и вершин допустимой области;

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

121. Для изготовления различных изделий А и В предприятие использует три вида сырья. На производство единицы изделия А требуется затратить сырья первого вида 6 кг, второго – 5 кг, третьего – 3 кг. На производство единицы изделия В соответственно: 3 кг, 10 кг и 12 кг. Производство обеспечено сырьем первого вида в количестве 714 кг, сырьем второго вида в количестве 910 кг и третьего вида 948 кг. Прибыль от реализации единицы готового изделия А составляет 3 руб., изделия В – 9 руб. Составить план производства изделий А и В, максимизирующий прибыль от их реализации. При этом должно быть выпущено не менее 80 штук изделия А.

122. Для производства двух видов изделий А и В используется три типа технологического оборудования. На изготовление одного изделия А оборудование первого типа используется в течение 5 ч., второго – в течение 3 ч. и третьего – 2 ч. На производство одного изделия В соответственно: 2 ч., 3ч. и 3 ч. В плановом периоде оборудование первого типа может быть использовано в течение 505 ч., второго – 394 ч. и третьего – 348 ч. Прибыль от реализации одного изделия А равна 7 руб., В – 4 руб. Составить план производства, максимизирующий прибыль предприятия. При этом должно быть произведено не менее 70 штук изделия В.

123. Для изготовления изделий А и В предприятие использует три вида сырья. На производство одного изделия А требуется сырья первого вида 15 кг, второго – 11 кг, третьего – 9 кг, а на производство одного изделия В соответственно 4 кг, 5 кг и 10 кг. Сырья первого вида имеется 1095 кг, второго – 865 кг, третьего – 1080 кг. Составить план производства, максимизирующий прибыль, если прибыль от реализации единицы изделия А составляет 3 руб., В – 2 руб. При этом должно быть выпущено не менее 80 штук изделий В.

124. Для производства изделий А и В используется три вида оборудования. При изготовлении одного изделия А оборудование первого вида занято 7 ч., второго – 6 ч. и третьего – 1 ч. При изготовлении одного изделия В соответственно 3 ч., 3 ч. и 2 ч. В месяц оборудование первого вида может быть занято 1365 ч., второго – 1245 и третьего – 650 ч. Составить план производства, максимизирующий прибыль, если прибыль от реализации одного изделия А равна 6 руб., изделия В – 5 руб. При этом должно быть произведено не менее 140 изделий А.

125. Для изготовления изделий А и В используется три вида сырья. На изготовление одного изделия А требуется 9 кг сырья первого вида, 6 кг сырья второго вида и 3 кг сырья третьего вида. На изготовление одного изделия В требуется соответственно 4 кг, 7 кг и 8 кг сырья. Производство обеспечено сырьем первого вида в количестве 801 кг, второго – 807 кг, третьего – 703 кг. Прибыль от продажи одного изделия А равна 3 руб., изделия В – 2 руб. Составить план производства, максимизирующий прибыль. При этом должно быть произведено не менее 70 штук изделия А.

126. Завод выпускает два вида редукторов. На изготовление одного редуктора первого вида расходуется 3 т чугуна и 1 т стали, а на изготовление одного редуктора второго вида 1 т чугуна и 2 т стали. Завод располагает на месяц 160 т чугуна и 120 т стали и имеет обязательное задание – изготовить не менее 60 редукторов обоих видов вместе. Составить месячный план производства редукторов, максимизирующий прибыль завода, если прибыль от продажи одного редуктора первого вида равна 400 руб., а второго – 100 руб. При этом оборудование завода позволяет выпустить за месяц не более 40 штук редукторов первого вида.

127. Для производства изделий А и В используется три вида станков. На производство одного изделия А<