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

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

В некоторых случаях решение задачи коммивояжёра можно применить для моделирования загрузки производственного оборудования (поточных линий, станков и т.п.), когда важна очередность операций, но нет строгой привязки к начальной операции. Например, имеется 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 руб. с единицы изделия.
Формулы в MS Word
Конвертируем формулы из изображения в MS Word.
Из картинки в Word
Метод Гомори
Метод Гомори
Метод Гомори. Решение задачи целочисленного программирования
Решить онлайн
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн