3.3. Решение задачи оптимизации по одному показателю

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

Задан сетевой график (рис. 6), (табл. 3) и задано допустимое время выполнения комплекса работ Т₀=25. Время выполнения сетевого графика не должно превышать Т₀ (3.5), а стоимость выполнения работ должна быть минимальна (3.6) . Из рис. 8 видно, что функция С_СГ=f (Т_СГ) всюду убывает, поэтому для минимизации стоимости выполнения комплекса работ сетевого графика неравенство следует заменить равенством Т_СГ=Т₀. Графическое решение задачи показано пунктирными стрелками на рис. 8, откуда следует С_min=110. Так как нас интересует не только общее время Т_СГ и общая стоимость С_СГ, но также времена и стоимость всех работ t_i, c_i, i=1, n, решим задачу аналитически.

Точка т0 лежит между второй и третьей точками зависимости

С_СГ=f (Т_СГ) ,

т.е. на втором шаге процедуры оптимизации. На этом шаге сокращается работа а₁ (табл. 5). Для получения требуемого решения Т_СГ=Т₀ уменьшить время выполнения работы а₁ нужно на величину

В общем виде, если

.

Далее задача решается по описанному алгоритму:

Т_СГ=26-1=25; t₁=12-1=11; с₁=49-2 11=27; С_СГ=110.

Остальные данные см. в табл. 5.

Результаты расчета приведены в табл. 7.

Таблица 7

Показатель	Работы					Сетевой график
	1	2	3	4	5
Время	11	13	5	14	9	25
Стоимость	27	16	8	39	20	110

2. Для того же сетевого графика задано, что суммарные затраты С_СГ не должны превышать С₀=135, а время выполнения комплекса работ необходимо минимизировать . Приняв С_СГ=С₀=135, как показано пунктирными стрелками на рис.8, найдем оптимальное значение времени выполнения сетевого графика Т_Сгmin=18.

Решим задачу аналитически. Точка С₀ лежит между пятой и шестой точками т.е. на пятом шаге процедуры оптимизации. На этом шаге сокращается работа а₁ и а₂ (табл. 5). В силу линейности зависимости С_СГ=f(Т_СГ) на каждом шаге оптимизации можно записать следующую пропорцию:

,

откуда

.

В общем виде, если

.

Далее задача решается по описанному алгоритму

Т_СГ=19-1=18; t₁=6-1=5; t₂=13-1=12; с₁=49-2 5=39; с₂=94-6 12=22; С_СГ=135. Остальные данные см. в табл. 5.

Результаты расчета приведены в табл. 8.

Таблица 8

Показатель	Работы					Сетевой график
	1	2	3	4	5
Время	5	12	5	13	6	18
Стоимость	39	22	8	40	26	135

Аналогичным образом могут быть решены и другие задачи оптимизации сетевых графиков.

Упражнения

Оптимизировать сетевой график по времени и стоимости.

Таблица 9

№ п.п.	Номер варианта	Параметры	Р А Б О Т Ы
			1	2	3	4	5	6	7
1	2	3	4	5	6	7	8	9	10
		Di	7	28	9	5	14	11	-
1	1.1	di	6	15	7	2	11	6	-
		CDi	20	12	6	13	14	8	-
		Cdi	25	38	8	40	26	18	-
№ п.п.	Номер варианта	Параметры	Р А Б О Т Ы
			1	2	3	4	5	6	7
1	2	3	4	5	6	7	8	9	10
		Di	8	20	12	10	14	13	-
2	1.2	di	8	15	9	3	6	6	-
		CDi	17	12	15	6	18	8	-
		Cdi	17	22	30	13	66	22	-
		Di	9	16	22	7	17	13	-
3	1.3	di	5	16	14	4	12	5	-
		CDi	1	23	15	10	25	12	-
		Cdi	26	23	31	25	65	36	-
		Di	20	23	18	2	11	16	-
4	1.4	di	10	17	3	1	8	8	-
		CDi	22	14	15	5	18	13	-
		Cdi	42	36	60	7	33	21	-
		Di	11	19	28	12	5	27	16
5	2.1	di	6	11	18	5	1	25	14
		CDi	22	26	15	55	40	18	30
		Cdi	52	90	65	125	48	24	44
		Di	5	21	38	13	27	28	8
6	2.2	di	4	16	30	8	12	25	4
		CDi	25	44	150	60	84	108	32
		Cdi	43	54	214	105	174	150	60
		Di	34	40	30	12	18	32	23
7	2.3	di	19	32	20	8	13	16	18
		CDi	52	80	110	32	28	140	95
		Cdi	142	192	280	44	38	460	140
		Di	15	28	18	20	2	27	14
8	2.4	di	8	22	10	11	1	14	9
		CDi	10	35	27	38	44	23	18
		Cdi	31	65	75	47	48	36	58
		Di	16	18	15	41	44	33	12
9	3.1	di	11	10	3	25	41	19	4
		CDi	51	77	24	86	62	175	120
		Cdi	91	125	72	134	68	455	256
		Di	31	16	7	10	51	11	19
10	3.2	di	21	11	7	6	34	7	16
		CDi	36	115	44	15	40	27	62
		Cdi	46	165	44	23	91	75	83
		Di	46	21	14	48	52	17	16
11	3.3	di	40	15	10	33	42	15	9
		CDi	135	120	86	260	140	54	41
		Cdi	153	192	110	320	290	58	97
№ п.п.	Номер варианта	Параметры	Р А Б О Т Ы
			1	2	3	4	5	6	7
1	2	3	4	5	6	7	8	9	10
		Di	35	18	26	33	63	20	32
12	3.4	di	27	13	15	29	50	14	19
		CDi	52	37	84	63	71	46	25
		Cdi	108	62	95	91	97	82	64
		Di	17	49	25	28	12	40	22
13	4.1	di	12	40	10	23	11	33	18
		CDi	47	150	63	55	18	86	34
		Cdi	122	267	153	60	22	121	42
		Di	26	44	15	32	23	38	30
14	4.2	di	22	41	8	14	7	21	26
		CDi	71	142	43	22	38	95	104
		Cdi	99	178	71	58	86	248	164
		Di	20	49	24	35	14	41	23
15.	4.3	di	15	41	14	27	8	30	19
		CDi	105	180	96	52	77	134	166
		Cdi	150	284	156	68	167	255	214
		Di	14	56	20	34	8	40	32
16	4.4	di	11	35	6	20	3	32	19
		CDi	74	68	41	84	26	59	36
		Cdi	92	89	83	112	61	70	140
		Di	21	24	20	8	7	26	21
17	5.1	di	6	15	13	3	4	14	13
		CDi	16	22	10	26	8	13	30
		Cdi	46	67	52	41	17	61	38
		Di	13	26	37	11	20	33	14
18	5.2	di	11	16	22	8	15	16	91
		CDi	22	17	28	34	9	12	18
		Cdi	34	56	58	43	14	29	48
		Di	19	22	27	18	15	19	28
19.	5.3	di	10	20	17	14	8	11	15
		CDi	25	13	12	35	15	23	31
		Cdi	34	21	72	67	29	63	70
		Di	7	15	27	7	12	18	19
20	5.4	di	2	9	12	4	8	12	3
		CDi	13	21	38	18	9	16	26
		Cdi	48	45	53	27	33	34	58
		Di	20	16	16	25	7	22	15
21	6.1	di	9	6	8	17	4	16	7
		CDi	14	18	9	12	32	21	13
		Cdi	47	38	17	68	35	39	61
№ п.п.	Номер варианта	Параметры	Р А Б О Т Ы
			1	2	3	4	5	6	7
1	2	3	4	5	6	7	8	9	10
		Di	34	31	13	29	7	12	24
22	6.2	di	14	13	7	20	5	8	16
		CDi	18	11	34	8	27	37	15
		Cdi	38	65	52	71	35	61	31
		Di	17	18	10	23	15	25	26
23	6.3	di	9	9	7	18	8	13	21
		CDi	11	25	15	46	34	22	8
		Cdi	67	52	39	56	48	58	38
		Di	15	20	11	16	14	38	18
24	6.4	di	12	9	7	11	4	22	11
		CDi	16	11	23	34	31	42	10
		Cdi	37	66	55	49	51	58	38

Схема № 1.

Г

2

раф:

Пути:

1

4

1) 2)

3

3) 4)

Сечения:

1) 2)

3) 4)

Схема № 2.

Граф:

Пути:

1)

2) 3)

4) 5)

Сечения:

1) 2) 3)

4) 5) 6)

Схема № 3.

Г раф:

Пути:

1)

2) 3) 4)

Сечения:

1) 2) 3)

4) 5) 6)

Схема № 4.

Граф:

Пути:

1)

2) 3) 4)

Сечения:

1) 2) 3)

4 ) 5) 6)

Схема № 5.

Г раф:

Пути:

1)

2) 3) 4)

Сечения:

1) 2) 3)

4) 5) 6)

Схема № 6.

Г раф:

Пути:

1)

2) 3) 4)

Сечения:

1) 2) 3)

4) 5) 6)