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

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

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

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

Показатель

Сетевой график

Показатель

Сетевой график

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

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

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

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

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

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

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

Таблица 7

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

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

Упражнения

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

Таблица 9

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