Использование задачи коммивояжера для планирования на предприятии

В некоторых случаях решение задачи коммивояжёра можно применить для моделирования загрузки производственного оборудования (поточных линий, станков и т.п.), когда важна очередность операций, но нет строгой привязки к начальной операции. Например, имеется n цехов по производству некоторой продукции. Каждый цех способен выполнить все технологические операции {1,2,..m}, но по тем или иным причинам (изношенности оборудования, нехватки квалифицированных рабочих и т.п.) эффективно (с наименьшими затратами) может выполнять операцию i. Обозначим zi – затраты i-ой операции. Тогда матрицу затрат технологических операций каждого цеха можно представить в виде:

 

1

2

m

1

M

z12

z1i

z1m

2

z21

M

z2i

z2m

zj1

zj2

M

zjm

m

zm1

zm2

zmi

M


где zji – затраты i-ой операции в j-ом цеху.
Поскольку очередность операций четко регламентирована, то задачу можно решить одним из методов целочисленного программирования -  методом ветвей и границ.
Как видно из условия, данная задача представляет собой частный случай задачи о назначении. И если очередность технологических операций не важна, поставленную задачу можно решить венгерским методом.
Рассмотрим пример решения данной задачи. Технологические операции заданы матрицей затрат (руб.):

i  j

1

2

3

4

1

M

22

26

56

2

34

M

12

51

3

45

33

M

44

4

39

7

16

M


В качестве произвольной технологической цепочки рассмотрим:
X0 = (1,2);(2,3);(3,4);(4,1)
т.е. первую операцию начинаем с цеха №1.
В этом случае общие затраты на производство продукции будут равны: F(X0) = 22 + 12 + 44 + 39 = 117 руб.
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij

i  j

1

2

3

4

di

1

M

22

26

56

22

2

34

M

12

51

12

3

45

33

M

44

33

4

39

7

16

M

7


Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i  j

1

2

3

4

1

M

0

4

34

2

22

M

0

39

3

12

0

M

11

4

32

0

9

M


Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij

i  j

1

2

3

4

1

M

0

4

34

2

22

M

0

39

3

12

0

M

11

4

32

0

9

M

dj

12

0

0

11


После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

i  j

1

2

3

4

1

M

0

4

23

2

10

M

0

28

3

0

0

M

0

4

20

0

9

M


Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 22+12+33+7+12+0+0+11 = 97
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n цехов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждая допустимая технологическая цепочка представляет собой цикл, по которому изготавливается продукция.
Текущие затраты на изготовление определяются выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в цепочку только один раз с элементом dij .

Шаг №1.
Определяем ребро ветвления и разобьем все множество цепочек относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

4

di

1

M

0(4)

4

23

4

2

10

M

0(14)

28

10

3

0(10)

0(0)

M

0(23)

0

4

20

0(9)

9

M

9

dj

10

0

4

23

0


d(1,2) = 4 + 0 = 4; d(2,3) = 10 + 4 = 14; d(3,1) = 0 + 10 = 10; d(3,2) = 0 + 0 = 0; d(3,4) = 0 + 23 = 23; d(4,2) = 9 + 0 = 9;
Наибольшая сумма констант приведения равна (0 + 23) = 23 для ребра (3,4), следовательно, множество разбивается на два подмножества (3,4) и (3*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,4*) = 97 + 23 = 120
Исключение ребра (3,4) проводим путем замены элемента d34 = 0 на M, после чего осуществляем очередное приведение матрицы затрат для образовавшегося подмножества (3*,4*), в результате получим редуцированную матрицу.

i  j

1

2

3

4

di

1

M

0

4

23

0

2

10

M

0

28

0

3

0

0

M

M

0

4

20

0

9

M

0

dj

0

0

0

23

23


Включение ребра (3,4) проводится путем исключения всех элементов 3-ой строки и 4-го столбца, в которой элемент d43 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 10
После операции приведения сокращенная матрица будет иметь вид:

i  j

1

2

3

di

1

M

0

4

0

2

10

M

0

0

4

20

0

M

0

dj

10

0

0

10


Нижняя граница подмножества (3,4) равна:
H(3,4) = 97 + 10 = 107  <  120
Поскольку нижняя граница этого подмножества (3,4) меньше, чем подмножества (3*,4*), то ребро (3,4) включаем в цепочку.

Шаг №2.
Определяем ребро ветвления и разобьем все множество цепочек относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

di

1

M

0(4)

4

4

2

0(10)

M

0(4)

0

4

10

0(10)

M

10

dj

10

0

4

0


d(1,2) = 4 + 0 = 4; d(2,1) = 0 + 10 = 10; d(2,3) = 0 + 4 = 4; d(4,2) = 10 + 0 = 10;
Наибольшая сумма констант приведения равна (0 + 10) = 10 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) = 107 + 10 = 117
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы затрат для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i  j

1

2

3

di

1

M

0

4

0

2

M

M

0

0

4

10

0

M

0

dj

10

0

0

10


Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 8
После операции приведения сокращенная матрица будет иметь вид:

i  j

2

3

di

1

M

4

4

4

0

M

0

dj

0

4

8


Нижняя граница подмножества (2,1) равна:
H(2,1) = 107 + 8 = 115  <  117
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в цепочку.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,3) и (4,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра: (3,4), (4,2), (2,1), (1,3),
Общие затраты равны F(Mk) = 111 руб.
Итак, для выпуска продукции с минимальными затратами необходимо начать изготовление продукции в цехе №3, затем в цехе №4, №2 и №1. В этом случае экономия от такой последовательности составит 6 руб. с единицы изделия.
загрузка...