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

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

1) построить упорядоченный сетевой график комплекса работ в терминах событий;

2) вычислить ранние и поздние сроки свершения событий, найти критический путь и критическое время;

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

4) вычислить моменты раннего и позднего начала и окончания работ, полный и свободный резервы времени работ;

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

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

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

Формулировка задачи. Построить сетевую модель и произвести расчёт её временных параметров. Исходные данные для расчёта содержатся в структурной таблице комплекса работ, включающей перечень (номера) всех работ, последовательность их выполнения, продолжительность каждой работы. Первый столбец таблицы (№i) – номера работ.

№i	Номера работ, на которые опирается i-я работа (левый столбец каждой задачи), продолжительность i-й работы (правый столбец).
	-		-		-		-		-		-		-		-		-		-
					-				-		-				-		-
	-				-										-
	2,3						3,4				2,5
					3,4,5		3,4				2,5		3,5		3,5				3,4
	2,3		4,5		3,4,5				4,6		2,5		3,5		3,5				3,4
	7,8		4,5						4,6		4,6		4,7		4,6				5,7
	7,8						6,8		5,8				4,7		7,9		5,6,8		5,7
	5,6						6,8		5,8				6,8		7,9		5,6,8		6,8,9
	9,11		7,8,10		8,10		7,10		7,9,10		8,9,10		6,8		8,10		7,10
			7,8,10		8,10		7,10		7,9,10		8,9,10		9,11		8,10		7,10
			9,12		9,12		9,11		11,12		11,12						9,12		11,12
	12,14		9,12		9,12		9,11		11,12								9,12

№i
	-		-		-		-		-		-		-		-		-		-
	-				-				-						-				-
					-
					2,4
	3,5								3,5						3,5
	3,5		4,6						3,5		4,6				3,5				2,5
	4,7		4,6		5,7		5,7		4,6		4,6				3,5				2,5
	6,8		5,8		6,8		5,7		4,6		5,7		3,5,7		6,7		4,5,7		4,6,8
	6,8		5,8				6,8,9		7,9		5,7		6,8,10		6,7		6,8		7,10
	9,10		7,9,10				6,8,9		7,9				6,8,10		6,7		6,8
	9,10		7,9,10				6,8,9		8,10,		9,10		9,11		8,10		9,11
	11,12		11,12		10,11		10,11				9,10		12,13		9,11		10,12		11,12
	11,12						12,14		13,14		11,12,13		12,13		12,14				13,14

№i
	-		-		-		-		-		-		-		-		-		-
	-		-				-		-		-		-		-		-
			-		-		-								-
											2,3				3,4
					2,3		3,4				2,3						4,5
	3,5				5,6		2,5		3,5		2,3				2,5
	3,5		3,4,5		2,3		2,5		3,5		4,5				3,4		4,5
	4,6		3,4,5		7,8		6,7		4,7		4,5		4,6,7		2,5				4,6
	4,6				5,6		6,7		4,7		7,8		4,6,7		6,7		4,5		4,6
			7,8		7,8				6,8,9				5,9				7,10		4,6
	8,9,11												5,9		8,9		8,11		8,11
	8,9,11				10,11		8,11		6,8,9		9,10						8,11		5,7,9
	10,12		10,11,12				10,12		10,12		9,10		8,10,				7,10		10,12
					13,14		13,14				12,14				12,13,14		9,12		13,14

№i
	-		-		-		-		-		-		-		-		-		-
	-				-				-		-		-				-
					-						-
									1,3
											2,4
			3,4
			5,6				3,4								4,6
	3,5,7		5,6				3,4												5,7
	3,5,7		5,6		5,7		6,8		5,8		2,4		5,7				4,5
	4,6				5,7		5,7,9		5,8		3,5		5,7		4,6
	4,6						6,8		9,10				6,9		5,7				8,10
	9,11						10,11		6,10,				6,9				8,9,10		4,9,11
	8,10,		7,10,		8,9,11		10,11		7,9		8,9,10		8,11		9,10		8,9,10		8,10
			7,10,		8,9,11								8,11				11,12		12,13
			12,14		10,12,13		13,14				12,13		10,12,13		12,13,14		13,14		8,10

Целочисленное программирование.

1. Решить задачу графически МЕТОДом ВЕТВЕЙ И ГРАНИЦ (все переменные неотрицательны).

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

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

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

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₂→min 7) z=2x₁+4x→max₂ 8) z=2x₁+x₂→min 9) z=3x₁+2x₂→max 10) z=x₁-2x₂→max

x₁+3x₂≥8 -x₁+3x₂≥0 x₁+4x₂≥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₂→max 12) z=2x₁+3x→max₂ 13) z=x₁+x₂→max 14) z=3x₁-2x₂→max 15) z=5x₁-3x₂→min

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₂→min 17) z=7x₁-2x₂→max 18) z=2x₁+x→max₂ 19) z=2x₁+2x₂→max 20)z=2x₁+4x₂→min

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

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

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₂→min 27) z=-2x₁+x₂→min 28) z=-2x₁+x₂→min 29) z=x₁-2x₂→min 30) z=2x₁-4x₂→min

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

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

z=c₁x₁+c₂x₂®max (min),

а₁₁x₁+а₁₂x₂≤b₁,

а₂₁x₁+а₂₂x₂≤b₂,

а₃₁x₁+а₄₂x₂≥b₃,

x_j³0, j=1÷2

Графически найти максимальное и минимальное целочисленные решения задач (методом ветвей и границ). Решить задачу методом отсечений Гомори (для максимального или минимального значения целевой функции − по своему смотрению). Коэффициенты ограничений и целевой функции приведены в таблице.

№ вар.	а11	а12	b1	а21	а22	b2	а31	а32	b3	c1	c2
										-1	-1
										-3	-5
				-5			-2
				-5
					-5					-3	-2
										-3
				-2		-7				-5
		-10								-2

3. Для задач 1–30:

а) определить всевозможные варианты распила досок на заготовки нужной длины (т.е. составить карту раскроя);

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

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

г) найти все оптимальные решения задачи.

Формулировка задачи. Доски длиной L, имеющиеся в достаточном количестве, следует распилить на заготовки двух видов: длиной l₁ и длиной l₂, причём заготовок первого вида должно быть получено не менее n₁ штук и заготовок второго вида – не менее n₂ штук. Каждая доска может быть распилена на указанные заготовки несколькими способами. Требуется найти число досок, распиливаемых каждым способом, с тем, чтобы необходимое количество заготовок было получено из наименьшего количества досок. Все необходимые числовые данные указаны в таблице.

Номер задачи	L, м	l1, м	l2, м	n1	n2		Номер задачи	L, м	l1, м	l2, м	n1	n2
	2,5	0,9	0,8				3,6	1,6	1,0
	3,4	1,4	1,0				2,6	0,7	1,1
	2,0	0,6	0,8				4,1	1,4	1,3
	2,3	1,1	0,6				1,8	0,5	0,8
	3,7	0,8	1,3				2,1	0,9	0,6
	2,8	1,0	0,9				3,5	1,0	1,5
	4,3	1,4	1,5				4,0	1,8	1,1
	1,7	0,7	0,5				2,7	0,8	1,1
	3,9	1,2	1,5				3,0	1,2	0,9
	2,2	1,0	0,6				3,3	1,0	1,3
	2,9	0,8	1,2				3,8	1,4	1,2
	1,6	0,6	0,5				3,7	1,1	1,5
	4,4	1,3	1,8				4,2	1,6	1,3
	1,9	0,9	0,5				3,2	0,9	1,4
	2,4	0,7	0,9				4,5	1,7	1,4

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

Решить графически игру, заданную платёжной матрицей (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