М-Чм-зао-09

Пример 5.4. Задача о назначениях (проблема выбора)

Имеются 3-и бригады В1, В2, В3, каждая из которых может быть использована на каждой из 3-х строительной площадке с производительностью (в условных единицах), заданной в таблице 5.4.

				Таблица 5.4
№		Производительность бригад (у.е.)
строительной	В1		В2	В3,
площадки
1	1		2	3
2	2		4	1
3	3		1	5

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

Решение.

Обозначим xij=1, если на i-ую стройплощадку назначена j-ая бригада и xij=0, если она на эту стройплощадку не назначена.

В качестве функции цели возьмите суммарную производительность всех бригад:

zmax =x11 +2x12 +3х13+
+2x21	+4x22 +x23+	(5.7)
+3x31	+x32.+5x33

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

выполняет работу на одной определенной стройплощадке и что каждая площадка обеспечена одной бригадой рабочих.

a) x i1 + x b) x1j + x c) x ij ³ 0

i2

2 j

+x

+x

i3

3 j

− 1 = 0,	i = 1,2,3
- 1 = 0,	j =1,2,3.	(5.8)

31

Приложение 1

Исходные данные к первому заданию. Матрица А

1).			− 2				2).							3).					− 3		4).						−1
		10			1	1.5				3	2	1	1.5				2	1		4				1	0	2
		− 2	8		−1	2.5				2	8	−1	2.5				1	1	−1	0				6 − 4		3	0
		1 −1			6 1					− 3 −1		6 1					0	2 − 7		1				4 0 − 4			2
		3 − 2		2 5						− 4 − 2 2 5							2	1 1 1						1	5	1 6

5).							6).					7).							8).
		31	14	30	27				2	3 −1 1					1	17 − 25		54				2	1	4	3
		26	32	18	24				1	2	3 −1				47	1	67	− 32				5	0 −1		0
		46	22	20	31				4	5	9 6				−11 43		1	− 74				2 −1		6	3
		40	34	36	17				1	1− 4 − 2					55	35	36	1				1	5 −1		2

9).					10).							11).							12).
	−1	3	3	L1.5				2	−1	1 −1					2	3	−1	1				1	0 − 3		1
	− 3	5	2	2.5				2	−1	0	− 3				1	2	3	−1				0	7	5 2
	− 3 1 − 5 5							3	0 −1		1				4	5	− 8	6				− 3 5 10			1
	− 5	7	1,5	16				2	2 − 2		5				1	1	− 4	− 2				1	7	2	4

13).						14).							15).							16).
		1	10 − 5		0				10	− 2	1	1				1	3	5	−1.5				1	− 5	− 8	− 8
		4	1	6	4				− 2	8	−1	2				3	5.1	7	−1				3	1	− 3	− 5
		1	4	2 − 6					1 −1		6	5				5	7	9 0					11 − 7		2	0
		8	0	1	5				− 3	3	2	2.5				3	−1	3	2				1	20	− 9	2.5

17).						18).							19).							20).				− 4		− 2
		1	− 2	−1	− 2				1	2	3	4.5				1	2	3	2				2		3
		1	1	− 4	−1				1	0	2	2				1	1	2 −1					1	− 2	−1	−1.5
		4	− 3	2	0				4	1 −1		0				3 −1 −1 0							0	1	1	0
		2	1	−1	1.5				2	1	1	0				1	2	− 5	1.5				4	− 7	4.5 −1

21).						22).							23).						24).
		1	0 3 − 4						1	4 1		3				3 1 1− 2						2	1 − 5 1
		0 1 5			6				0	− 1 3 −1						− 2 3	1 4					1	− 3 0 − 6
		− 5	4	0	2				3	−1	0	2				1 4	2	3.5				0	2 −1	2
		− 3	− 6	2	0				1	− 2	5	1.5				− 5 − 2	− 3	2				1	4 − 7.5	6

32

Приложение 2

Исходные данные ко второму заданию

1).			2).
3,5x1	- 1,7x2 + 2,8x3 = 1,7		2,1x1	+ 4,4x2	+ 1,8x3			= 1,1
5,7x1	+ 3,3x2 + 1,3x3 = 2,1		0,7x1	- 2,8x2 +		3,9x3	= 0,7
2,1x1	+ 5,8x2 + 2,8x3 = 0,8		4,2x1	- 1,7x2	+ 1,3x3			= 2,8
3).			4).
3,1x1	+ 2,8x2 + 1,9x3 = 0,		4,1x1	+ 5,7x2	+ 1,2x3			= 5,8
1,9x1	+ 3,1x2 + 2,1x3 = 2,1		0,8x1	+ 1,1x2	-	2,8x3	= 6,7
7,5x1	+ 3,8x2 + 4,8x3 = 5,6		9,1x1	- 3,6x2 +		2,8x3	= 9,8
5).			6).
2,7x1	- 0,8x2 + 4,1x3 = 3,2		1,9x1	+ 1,1x2	+ 3,8x3			= 7,8
1,1x1	+ 3,7x2 + 1,8x3 = 5,7		7,6x1	+ 5,8x2	-	4,7x3	= 10,1
3,3x1	+ 2,1x2 - 2,8x3 = 0,8		1,8x1	- 4,1x2 +		2,1x3	= 9,7
7)			8).
3,2x1	- 8,5x2 + 3,7x3 = 6,5		4,2x1	+ 6,7x2	-	2,3x3		= 2,7;
0,5x1	+ 0,34x2 +3,7x3 = -0,24		5,4x1	- 2,3x2	+ 1,4x3			= - 3,5;
4,6x1	+ 2,3x2 - 1,5x3 = 4,3		3,4x1	+ 2,4x2	+ 7,4x3			= 1,9.
.
9).			10).
1,5x1	+ 4,5x2 + 1,3x3 = -1,7		3,4x1	- 3,6x2	-	7,7x3 = -2,4
2,7x1	- 3,6x2 + 6,9x3 = 0,4		5,6x1	+ 2,7x2	-	1,7x3	= 1,9
6,6x1	+ 1,8x2 - 4,7x3 = 3,8		-3,8x1 + 1,3x2 +3,7x3 = 1,2
11).			12).
-2,7x1 + 0,9x2 - 1,5x3 = 3,5			0,8x1	+ 7,4x2	-	0,5x3	= 6,4.
3,5x1	- 1,8x2 + 6,7x3 = 2,6		3,1x1	- 0,6x2 - 5,3x3 = -1,5;
5,1x1	+ 2,7x2 + 1,4x3 = -0,1		4,5x1	- 2,5x2 +		1,4x3	= 2,5;
13).			14).
5,4x1	- 6,2x2 - 0,5x3 = 0,52		3,8x1	+ 6,7x2	+ 2,2x3			= 5,2
3,4x1	+ 2,3x2 + 0,8x3 = -0,8		6,4x1	+ 1,3x2	-	2,7x3	= 3,8
2,4x1	- 1,1x2 + 3,8x3 = 1,8		-2,4x1 - 4,5x2 + 3,5x3 = -0,6
15).			16).
-3,3x1 + 1,1x2 + 5,8x3 = 2,3			3,8x1	+ 7,1x2	-	2,3x3	= 4,8
7,8x1	+ 5,3x2 + 1,8x3 = 1,8		-2,1x1 + 3,9x2 - 6,8x3 = 3,3
4,5x1	+ 3,3x2 - 3,8x3 = 3,4		8,8x1	+ 1,1x2	-	2,1x3	= 5,8
		33

17).		18).
1,7x1	- 2,2x2 - 4,0x3 = 1,8	2,8x1	+ 3,8x2 – 8,2x3 = 4,5
2,1x1	+ 1,9x2 - 2,3x3 = 2,8	2,5x1	- 7,8x2 + 3,3x3 = 7,1
4,2x1	+ 1,9x2 - 0,1x3 = 5,1	6,5x1	- 1,1x2 + 4,8x3 = 6,3
19).		20).
2,3x1	+ 0,7x2 + 4,2x3 = 5,8	3,1x1	+ 6,8x2 + 2,1x3 = 7,0
-2,7x1 + 2,3x2 - 2,9x3 = 6,1		-5,0x1 - 4,8x2 + 5,3x3 = 6,1
9,1x1	+ 4,8x2 - 5,0x3 = 7,0	8,2x1	+ 1,8x2 + 5,1x3 = 5,8
21).		22).
3,7x1	+ 3,1x2 + 7,0x3 = 5,0	2,1x1	+ 0,2x2 - 5,8x3 = 7,0
4,1x1	+ 9,5x2 - 4,8x3 = 4,9	3,8x1	- 8,1x2 + 4,0x3 = 5,3
-7,1x1 + 3,7x2 + 1,8x3 = 2,7		7,8x1	+ 5,3x2 - 0,3x3 = 5,8
23).		24).
3,7x1	- 2,3x2 + 4,5x3 = 2,4	6,3x1	+ 5,2x2 - 0,4x3 = 1,5;
2,5x1	+ 4,3x2 - 7,8x3 = 3,5	3,4x1	- 2,3x2 - 3,4x3 = 2,7;
1,6x1	+ 5,3x2 + 1,3x3 = -2,4	2,8x1	+ 1,4x2 - 3,5x3 = -2,3.
25).		26).
1,1x1	+ 2,3x2 - 3,7x3 = 4,5	0,9x1	+ 2,7x2 - 3,8x3 = 2,4
6,8x1	+ 3,4x2 + 1,8x3 = -3,2	,5x1 + 5,8x2 - 0,5x3 = 3,5
1,2x1	+ 7,3x2 - 2,3x3 = 5,6	8,5x1	- 2,1x2 + 3,2x3 = -1,2
27).		28).
1,5x1	- 2,3x2 + 8,6x3 = -5,5	5,4x1	- 2,4x2 + 10,8x3 = 5,5
7,4x1	+ 2,5x2 - 2,9x3 = 4,5	2,5x1	+ 6,8x2 - 1,1x3 = 4,3
0,8x1	+ 3,5x2 - 1,4x3 = 3,2	2,7x1	- 0,6x2 + 1,5x3 = -3,5
29).		30).
2,4x1	+ 3,7x2 - 8,3x3 = 2,3	23,2x1 - 11,5x2 + 3,8x3 = 2,8
1,8x1	+ 4,3x2 + 1,2x3 = -1,2	0,8x1	+ 1,3x2 - 6,4x3 = -6,5
10,4x1 - 1,3x2 + 5,2x3 = 3,5		2,4x1	+ 7,2x2 - 1,2x3 = 4,5

34

Приложение 3

Исходные данные к третьему заданию

1).			2).				3).
y'' + 2y' = 1− x			y'' − 2xy' − 2y = −4x				x2 y'' − 2y' = 2x
y' (0) = 0,	y(1) = 1		y(0) − y' (0) = 0,			y(1) = 3,718	y(1) = 0,
h = 0,2			h = 0,2				y(2) + 2y' (2) = 0,
							h = 0,2
4).			5).				6).
y'' = x + y			x y '' − y '		= x 2		x2 y'' + 2xy = x −1
y(0) = 0,	y(2) − y'	(2) = 0	y(1) = 0,		y ' (2) = 0,		y(1) = 0,	y'(3) = 0,
h = 0,4			h = 0,2				h = 0,4
7)/			8).	+ y ' / x − y / x 2		= −1	9).
y'' + y' = 1			y ''				2y'' − xy = 2
y(0) − y' (0) = 0,		y(1) = 0	y(1) = 0,		y(2) − y ' (2) = 0		y' (0) = 0,	y(1) = 0
h = 0,2			h = 0,2				h = 0,2
10).			11).				12).
y '' + xy ' + y = 2 x			y '' + 2 y ' = x 2				y '' + 2xy '	− 2 y = −4x
y(0) = 1,	y ' (2) = 0		y(0) = 0,		y ' (2) = 1		y(0) − y' (0) = 0,
h = 0,4			h = 0,4				y(1) = 3
							h = 0,2
13).			14).				15).
x2 y'' − 2 y = 2x			y ''	= y + 2 x			x y'' − y' = x2 − 1
y(1) = 0,	y(3) + y' (3) = 0		y '	(0) = 0, y(2) = 0			y(1) = 0,	y' (2) = 0
h = 0,4			h = 0,4				h = 0,2
16).			17).				18).
x2 y'' + xy = x − 1			y ''	+ y ' = 1 − x			y '' + y ' − y / x 2 = 1
y'(1) = 0,	y(3) = 0		y (0) = 0,		y(1) − y ' (1) = 0		y ' (1) = 0,		y (3) = 0
h = 0,4			h = 0,2				h = 0,4
19).			20).				21).
2 y '' − xy '	+ y = 2		y '' + y ' + xy = 2 x				y'' − 2 y = 2x + 1
y (0) = 0,	y ' (1) = 0		y ' (0) = 1,		y(2) = 0		y(1) = 0, y(2) + 2 y' (2) = 0
h = 0,2			h = 0,4				h = 0,2
22).			23).				24).
y'' + y' = 2x + y			xy '' − y ' / x = 1 − x 2				x2 y' ' + 2xy = x − 1
y(0) = 0,	y(2) = 0,		y '	(1) = 0,	y (2) = 0 .		y(1) = 0,	y'	(3) = 0
h = 0,4			h = 0,2				h = 0,4
					35

25).		26).		27).
y'' + y' − 2 y = 1,		y ' ' + y ' / x − y = − 1		y'' + y' − y = 2x
y(0) − y' = 0,	y(1) = 0,	y (1) = 0,	y ' (3) = 0,	y(0) = 0, y(2) − y' (2) = 0,
h = 0,2		h = 0,4		h = 0,4
28).		29).		30).
y'' − 2xy' − 2y = 4x		y '' + 2 y ' = x 2 − 1		x2 y'' + xy = x + 1
y(0) − y'(0) = 0,	y(1) = 3,1	y(0) = 0,	y ' (1) = 1	y'(1) = 0, y(2) = 0
h = 0,2		h = 0,2		h = 0,2

36

Приложение 4

Исходные данные к четвертому заданию 4

1)		2)		3).			4)
zmin = x1 − 2x2 ,		zmin = −x1 − 3x2 ,		zmax = 3x1 − 6x2 ,			zmax = 2x1 + x2 ,
- x1 + x2 £ 0,		x1 + x2	£ 2,	x1	+ 2x2	+1 ³ 0,	2x1 + x2 ³ 1,
2x1 + 2x2 £ 3,		x1 - x2	³ 0,	2x1 + x2		³ 4,	3x1 - x2 ³ -1,
x1	- x2 £ 1,	x1 - x2	£ 1,	x1	- x2 ³ 1,		x1 - 4x2 £ 2,
x1	³ 0, x2 ³ 0	x1 ³ 0, x2 ³ 0		x1	- 4x2	+13 ³ 0,	x1 ³ 0, x2 ³ 0
				- 4x1 + x2 + 23 ³ 0.

5).	6).		7).	8).
zmin = −x1 − 2x2 ,	zmin = 3 − x1 − x2 ,		zmax = x1 + 4x2 ,	zmax = x1 + x2 ,
x1 £ 3,	x1 - x2 +1 ³ 0,		x1 £ 2,	x1	£ 4,
x2 £ 2,	x1 + 2x2	³ 2,	x1 + 2x2 ³ 2,	x1 + x2 ³ 1,
x1 + x2 £ 1,	2x1 + x2	£ 4,	x2 £ 2,	x1 - x2		³ -1,
x1 ³ 0, x2 ³ 0	x1 ³ 0, x2 ³ 0		x1 ³ 0, x2 ³ 0	x2 £ 2,
				x1	³ 0,	x2 ³ 0

9).		10).			11).		12).
z min = 2 x1 − x 2 ,		zmax = x1 + 3x2 ,			zmax = −4x1 + x2 ,		zmax = −2x1 − x2 ,
x1	+ 2 x 2 ³ 2,	x1 £ 2,			x1 + 4x2	³ 8,	2x1 + x2 ³ 5,
- 2 x1 - x 2 = 0,		2x1 + x2		³ 0,	2x1 - x2	³ -2,	3х1 - x2 ³ -1,
x1	- 2 x 2 £ 0,	x1 + x2	£ 3,		- x1 - x2 ³ -10,		x1	- 2x2 £ 2,
x1	- x 2 ³ -1,	x2 £ 3,			- x1 + 2x2 ³ -2		x1	³ 0, x2 ³ 0
x1	³ 0, x 2 ³ 0	2x1 + x2		³ 2,
		x1 ³ 0,		x2 ³ 0

13).		14).		15).		16).
zmin = − x1 ,		zmax = −3x1 + 6x2 ,		zmax = x1 − 4x2 ,		zmin = 2 x1 − 4 x2 ,
x1 + x2	³ 3,	x1 - x2 ³ -1,		x1 £ 6,		x1 + 2 x2 ³ 2,
x1 - x2	³= -1,	x1 + 2x2	³ -1,	x1 + 2x2 ³ 2,		- 2 x1 - x2 £ 0,
- x1 + x2 ³ -1,		2x1 + x2	³ 4,	x2 £ 2,		x1 - 2 x2 £ 0,
2 x1 + x2 ³ 0,		x1 - 4x2	³ -13,	x1	- x2 £ 3,	x1	- x2 ³ -1,
x1 ³ 0, x2 ³ 0		- 4x1 + x2 ³ -23		x1	³ 0, x2 ³ 0	x1	³ 0, x2 ³ 0
				37

17).	18).			19).	20).
zmin = x1 + x2 ,	zmax = 2x1 + 3x2 ,			zmax = 4x1 − x2 + 2,	zmax = 5x1 + 5,5x2 ,
- 2 x1 - x2 + 8 ³ 0,	x1	- x2	³ 4,	x1 + x2 ³ 1,	3x1 + 6x2	£ 18,
x1 + x2 ³ 1,	x1	+ x2	£ 8,	3x1 - x2 ³ -1,	6x1 + 4x2	£ 24,
3x1 - 2 x2 + 3 ³ 0,	x1	³ 0, x2 ³ 0		x2 £ 2,	2x1 + x2 ³ 2,
- x1 + x2 + 4 ³ 0,				x1 ³ 0, x2 ³ 0	x1 ³ 0, x2 ³ 0

21).	22).	23).	24).
zmax = −4x1 + x2 ,	zmax = −2x1 − x2 ,	zmax = 2x1 − x2,	zmin = 5x1 + 3x2,
x1 + 4x2 ³ 8,	2x1 + x2 ³ 5,	- x1 + x2 £ 1,	x1 + x2 £ 4,
2x1 - x2 £ -2,	3x1 - x2 ³ -1,	x1 - 2x2 £ 1,	6x1 + 2x2 ³ 8,
- x1 - x2 ³ -10,	x1 - 2x2 £ 2,	x1 ³ 0, x2 ³ 0	x1 + 5x2 ³ 4,
- x1 + 2x2 ³ -2	x1 ³ 0, x2 ³ 0		x1 ³ 0, x2 ³ 0

25).		26).	27).	28).
zmax = 626x1 + 656x2,		zmax = 5x1 + 3x2,	zmin = 2x1 + 5x2,	zmin = 2x1 − x2,
5x1 + 8x2 £ 81,		3x1 + 5x2 £ 15,	3x1 + 4x2 £ 34,	- x1 + x2 £ 1,
6x1 + 4x2 £ 70,		5x1 + 2x2 £ 10,	- 2x1 + x2 £ 3,	x1 - 2x2 £ 1,
x1 + x2	£ 12,	x1 ³ 0, x2 ³ 0	4x1 + x2 £ 28,	x1 ³ 0, x2 ³ 0
3x1 + x2 £ 26,			x1 ³ 0, x2 ³ 0
x1 ³ 0,	x2 ³ 0

29).	30).
z min = x1 + x 2 ,	zmin = −4x1 + x2,
- 2 x1 - x 2 + 8 ³ 0,	x1 + 4x2 ³ 8,
x1 + x 2 ³ 1,	2x1 - x2 ³ -2,
3x1 - 2 x 2 + 3 ³ 0,	- x1 - x2 ³ -10,
- x1 + x 2 + 4 ³ 0,	- x1 + 2x2 ³ -2

38

Приложение 5

Исходные данные к пятому заданию

1. Задача об оптимальном выпуске продукции.

Предприятие располагает тремя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1час работы первым способом выпускается 20 единиц продукции, а вторым способом - 30 единиц продукции.

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

Требуется найти план производства, при котором будет выпущено наибольшее количество продукции.

				Таблица 1.
Вид сырья	Расход сырья (кг\ч)			Запасы сырья
	при способе
	производства
	№1		№2
1	10		20	100
2	20		10	100
3	15		15	90

2*. Транспортная задача

На 3-х цементных заводах производится цемент одной и той же марки в количествах соответственно 30, 40, 53 тонн. Цемент следует доставить на четыре завода ЖБК, потребляющих его соответственно в количествах 22, 35, 25, 41 тонн. Стоимости (у.е.) перевозок одной тонны продукта с i-го (i=1,2,3) завода на j-ый (j=1,2,3,4) ЖБК приведены в таблице 2.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

					Таблица 2
	Стоимость перевозки				Объем
Цементный	(у.е.)		Количество .		производств
завод		перевозимого продукта (т)			а (т)
	ЖБК-1	ЖБК-2	ЖБК-3	ЖБК-4
№1	23	27	16	18	30
№2	12	17	20	51	40
№3	22	28	12	32	22
Объем пот-	22	35	25	41
ребления
			39

3. Задача об оптимальном выпуске продукции

Для изготовления продукции используют три вида сырья. При этом можно применять любой из четырех способов производства. Запасы сырья, расход сырья и количество производимой продукции за 1час работы по каждому способу приведены в табл.3.

Требуется найти план производства, при котором будет выпущено наибольшее количество продукции.

					Таблица 3
Вид сырья		Способ производства			Запас сырья
	1	2	3	4
1	1	2	1	0	18
2	1	1	2	1	30
3	1	3	3	2	40
Выпуск про-	12	7	18	10
дукции (шт)

4. Задача оптимизации производственной программы

Технологический процесс состоит из двух этапов. На первом этапе

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

Выход промежуточных продуктов из одной тонны сырья и расход этих продуктов на производство одной тонны конечной продукции каждого вида указаны в табл.4. При этом оптовая цена тонны конечной продукции первого

вида - 50 руб, а второго - 60 руб.
Определить	производственную программу выпуска,				при которой
максимизируется цена выпускаемой продукции.
					Таблица 4
Промежуточны		Выход из 1 т сырья,	Расход на 1 т конечного
й		кг	продукта, кг
продукт			1 вид		2 вид
1		460	250		800
2		200	250		200
3		340	500

40