13.2 Розв’язування задач.

Пример. Методом динамического программирования найти оптимальное решение для задачи трех станков для следующих исходных данных: количество деталей n=5; матрица трудоемкостей (табл.4.21).

Таблица 4.21. Матрица трудоемкостей

Станки	Номера деталей
	1	2	3	4	5
	8	9	5	4	6
	7	4	9	3	2
	9	5	3	6	5

Шаг 1. Конструируются фрагменты перестановок данной, равной 1. Результаты представлены в табл. 4,22.

Таблица 4.22. Характеристики фрагментов

	А	В	С
<1>	8	15	24
<2>	9	13	18
<3>	5	14	17
<4>	4	7	13
<5>	б	8	13

Шаги 2-5. Последовательно конструируются фрагменты перестановок (табл. 4.23), (табл. 4.24), (табл.4.25), (табл. 4.26).

Таблица 4.23. Характеристики фрагментов

	A	B	C	Признак оптимальности
<1,2>	17	21	29	*
<2,1>	17	24	33
<1,3>	13	24	27	*
<3,1>	13	21	30
<1,4>	12	18	30
<4,1>	12	19	28
<1,5>	14	17	29	*
<5,1>	14	21	30
<2,3>	13	22	25
<3,2>	14	18	23
<2,4>	13	16	24	*
<4,2>	13	17	22	*
<2,5>	15	17	23
<5,2>	15	19	24
<3,4>	9	17	23	*
<4,3>	9	18	21
<3,5>	11	16	22	*
<5,3>	11	20	23
<4,5>	10	12	18	*
<5,4>	10	13	19

Таблица 4.24. Характеристики фрагментов

	А	В	С	Признак оптимальности
<1,2,3>	22	31	34
<1,3,2>	22	28	33	*
<3,1,2>	22	26	35	*
<3,2,1>	22	29	38
<1,2,4>	21	24	35	*
<1,4,2>	21	25	35
<2,4,1>	21	28	37
<4,1,2>	21	25	33
<4,2,1>	21	28	37
<1,2,5>	23	25	34	*
<1,5,2>	23	27	34
<2,5,1>	23	30	39
<1,3,4>	17	27	33
<1,4,3>	17	27	33
<3,1,4>	17	24	36
<3,4,1>	17	24	33
<4,1,3>	17	28	31
<4,3,1>	17	25	34
<1,3,5>	19	26	32
<1,5,3>	19	28	32
<3,1,5>	19	23	35
<3,5,1>	19	26	35
<1,4,5>	18	20	35	*
<1,5,4>	18	23	35
<4,1,5>	18	21	33	*
<4,5,1>	18	25	34
<2,4,3>	18	27	30
<3,2,4>	18	21	29	*
<3,4,2>	18	22	28
<4,2,3>	18	27	30
<4,3,2>	18	22	27	*
<2,4,5>	19	21	29
<2,5,4>	19	22	29
<4,2,5>	19	21	27	*
<4,5,2>	19	23	28
<2,5,3>	20	29	32
<3,2,5>	20	22	28	*
<3,5,2>	20	24	29
<3,4,5>	15	19	28
<3,5,4>	15	19	28
<4,3,5>	15	20	26
<4,5,3>	15	24	27

Таблица 4.24. Характеристики фрагментов

	А	В	С	Признак оптималь­ности
<1,2,4,3>	26	35	38
<1,3,2,4>	26	31	39
<3,1,2,4>	26	29	41
<3,2,4,1>	26	33	42
<3,4,1,2>	26	30	38	*
<4,1,2,3>	26	35	38
<4,1,3,2>	26	32	37	*
<4,3,2,1>	26	33	42
<1,2,4,5>	27	29	40
<1,2,5,4>	27	30	40
<1,4,5,2>	27	31	40
<4,1,2,5>	27	29	38	*
<4,1,5,2>	27	31	38
<4,2,5,1>	27	33	42
<1,2,5,3>	28	37	40
<1,3,2,5>	28	30	38	*
<1,3,5,2>	28	32	37	*
<3,1,2,5>	28	30	40
<3,1.5,2>	28	32	40
<3,2,5,1>	28	35	44
<1,3,5,4>	23	29	38
<1,4,5,3>	23	32	38
<3,1,5,4>	23	26	41
<3,4,1,5>	23	26	38	*
<4,1,3,5>	23	30	36	*
<4,1,5,3>	23	32	36	*
<4,3,5,1>	23	30	39
<3,2,4,5>	24	26	34
<3,2,5,4>	24	27	34
<4,2,5,3>	24	33	36
<4,3,2,5>	24	26	32
<4,3,5,2>	24	28	33

Таблица 4.26

Характеристики фрагментов .

	А	В	С	Признак оптимальности
<1,3,2,5,4>	32	35	44
<1,3,5,2,4>	32	35	43
<3,4,1,2,5>	32	34	43
<3,4,1,5,2>	32	36	43
<4,1,2,5,3>	32	41	44
<4,1,3,2,5>	32	34	42
<4,1,3,5,2>	32	36	41	*
<4,3,2,5,1>	32	39	4$
<4,1,5,3,2>	32	36	41	*

Оптимальные последовательности запуска деталей на обработку и Длительность производственного цикла равна 41.