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

Постановка задачи: Некий гражданин решил стать индивидуальным предпринимателем и предполагает работать в течение n лет. Для того чтобы начать деятельность, он должен закупить оборудование. Считается, что оно закупается в комплекте. Оборудование может работать все n лет, а может быть заменено в некотором промежуточном периоде, с_ij– затраты на закупку и эксплуатацию оборудования, если оно закуплено вначале i-го периода и выведено в начале j-го периода. Надо определить моменты замены оборудования так, чтобы суммарные затраты на закупку и эксплуатацию оборудования в течение n периодов были минимальны.

Если рассмотреть конец третьего периода, то этот момент будет началом четвертого периода. Введем n + 1 период и будем считать, что начало n +1 –ого периода совпадает с окончанием n – ого периода, когда все оборудование списывается.

Введем матрицу затрат С. Очевидно, что эта матрица верхняя, треугольная и i: c_ij<c_ij+1. Построим математическую модель задач, x_ij ϵ {0, 1}- булева переменная. При этом x_ij= 1, если оборудование закупается в начале i-го периода и списывается в начале j-го периода. Иначе x_ij= 0.

Ограничения задачи:

- в начале первого периода оборудование должно быть закуплено:

(3.1)

- в начале n+1периода все оборудование должно быть списано:

(3.2)

- для всех промежуточных периодов, если в начале периода оборудование списывается, то новое должно быть сразу закуплено:

Целевая функция будет иметь вид:

Окончательный вид модели:

Заметим, что полученная модель полностью совпадает с моделью (2.1) – (2.5) задачи о кратчайшем пути.

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

Решив задачу с помощью алгоритма, изложенного выше на странице 24. Мы получим кратчайший путь и его длину.

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

1. Длина кратчайшего пути u1 – есть суммарные затраты на закупку и эксплуатацию оборудования.

2. Рассмотрим теперь кратчайший путь 1 – k₁ – k₂ – … – k_n – n + 1. Если дуга (i , j) , где i > 1, а j < n+1 входит в кратчайший путь, то = 1, но тогда это означает, что оборудование было закуплено в начале i – ого периода и списано в начале j – ого периода. То есть i и j – есть моменты замены оборудования.

Таким образом, моменты замены оборудования – это все промежуточные вершины в кратчайшем пути.

Если кратчайший путь состоит всего из двух вершин 1 – n + 1, то следует выписать ответ: оборудование в промежуточных периодах не меняется.

Пример:

Пусть предприниматель предполагает работать в течение 6 периодов. Затраты на закупку и эксплуатацию оборудования записаны в таблице.

	2	3	4	5	6	7
1	2	5	7	9	10	18
2		3	10	12	17	20
3			5	10	18	25
4				7	10	15
5					3	8
6						4

Рис. 3.1

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

В самом деле, добавим к таблице два вертикальных столбца u_i, j_i и одну горизонтальную строку u_j . Эти соответствующие графы будем заполнять, используя формулы:

u_n+1 = 0 (3.10) (3.11)

j_i : (3.12)

	2	3	4	5	6	7	ui	ji
1	2	5	7	9	10	18	14	6
2		3	10	12	17	20	19	5
3			5	10	18	25	17	5
4				7	10	15	14	5, 6
5					3	8	7	6
6						4	4	7
uj	19	17	14	7	4	0

Рис. 3.2

Получим путь: 1 – 6 – 7, L_кр = 14.

Ответ в терминах предметной области: оборудование следует менять в начале 6-го периода, при этом минимальные затраты равны 14

???Задание для самостоятельной работы:

Решить задачу о замене оборудования с матрицей, имеющей вид:

	2	3	4	5	6	7
1
2
3
4
5
6

Для которой заданы пять значений элементов, остальные значения произвольные с выполнением условия для всех i, c_i,j < c_i,j+1

1. c_1,4 = 7, c_1,7 = 25, c_3,7 = 36, c_6,7 = 2.

2. c_2,4 = 4, c_3,4 = 8, c_3,6 = 20, c_6,7 = 2.

3.c_1,2 = 10, c_2,4 = 6, c_2,6 = 25, c_5,6 = 12.

4.c_3,4 = 9, c_3,7 = 30, c_4,5 = 24, c_4,7 = 30.

5.c_1,3 = 25, c_1,6 = 29, c_4,6 = 17, c_5,7 = 13.

6.c_1,7 = 14, c_2,4 = 37, c_2,6 = 40, c_4,5 = 5.

7.c_3,5 = 18, c_4,5 = 25, c_4,7 = 30, c_5,6 = 9.

8.c_1,3 = 15, c_1,6 = 25, c_4,6 = 31, c_5,7 = 11.

9.c_1,4 = 10, c_1,6 = 17, c_4,7 = 22, c_5,7 = 12.

10.c_2,4 = 4, c_2,7 = 25, c_3,4 = 14, c_4,5 = 21.

11.c_3,5 = 10, c_3,7 = 34, c_4,6 = 27, c_5,7 = 7.

12.c_1,5 = 17, c_1,7 = 35, c_3,5 = 20, c_3,7 = 27.

13.c_2,3 = 25, c_2,7 = 35, c_3,5 = 34, c_4,7 = 19.

14.c_2,5 = 27, c_3,7 = 15, c_4,6 = 29, c_6,7 = 32.

15.c_3,4 = 7, c_2,7 = 31, c_4,7 = 33, c_5,6 = 26.

16.c_2,5 = 37, c_2,7 = 40, c_3,6 = 28, c_4,5 = 15.

17.c_1,4 = 10, c_1,6 = 15, c_2,7 = 23, c_4,5 = 1.

18.c_3,4 = 8, c_4,5 = 6, c_4,7 = 23, c_5,6 = 7.

19.c_4,6 = 12, c_5,6 = 18, c_5,7 = 36, c_6,7 = 22.

20.c_2,6 = 17, c_3,5 = 9, c_4,6 = 19, c_5,7 = 17.

21.c_1,3 = 7, c_2,3 = 15, c_4,7 = 20, c_5,6 = 11.

22.c_2,4 = 27, c_3,7 = 10, c_4,5 = 30, c_5,7 = 20.

23.c_1,3 = 3, c_3,4 = 7, c_4,7 = 18, c_5,6 = 9.

24.c_1,4 = 19, c_1,7 = 29, c_4,5 = 3, c_6,7 = 18.

25.c_3,5 = 32, c_4,7 = 33, c_5,7 = 24, c_6,7 =17.