Использование задачи коммивояжера для планирования на предприятии
В некоторых случаях решение задачи коммивояжёра можно применить для моделирования загрузки производственного оборудования (поточных линий, станков и т.п.), когда важна очередность операций, но нет строгой привязки к начальной операции. Например, имеется 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 руб. с единицы изделия.