Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Теория игр Задача о назначениях Поток сети Транспортная задача Графический метод Решение дифф уравнений Симплексный метод Двойственная задача Параметры сетевой модели

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

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