ЭММ : 2.Транспортная задача

Транспортная задача — задача об оптимальном плане перевозок продукта (-ов) из пунктов наличия в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки.

Будем считать, что имеем m различных поставщиков, располагающих некоторыми изделиями, которые они могут отправить n потребителям. Предполагается, что i-предприятие может осуществить поставку не более чем bi-изделий, а j-потребителю требуется не менее чем аj-изделий. Затраты на перевозку груза из пункта направления i в пункт назначения j составляют Cij. Целевой функцией является выбор плана перевозок, min-щего общие транспортные затраты предприятия.

Математическая постановка классической транспортной задачи имеет вид:

Z = CYMM (CYMM (cij*xij))->min
при ограничениях:
CYMM (xij)<=bi, (на ресурсы)
CYMM (xij)>=aj, (на спрос)

Обычно транспортная задача имеет табличное представление.

Если сумма bi равна сумме аj, то транспортная задача называется закрытой, в противном случае транспортная задача — открытая.

Если сумма bi больше суммы аj, то вводится фиктивный потребитель an+1=CYMM (bi)-CYMM (aj) и транспортные затраты Сi,n+1 полагаются равными нулю.

Если сумма bi меньше суммы аj, то вводится фиктивный (m+1) поставщик bm+1=CYMM (aj)-CYMM (bi) и транспортные затраты относительно данного пункта Cm+1,j полагаются равными нулю.

Пример: требуется перевезти из 4 пунктов отправления (7, 9, 46, 17) в 3 пункта назначения (10, 16, 2). Известна матрица затрат на перевозку.

4 5 6
С = 5 3 5
5 5 6
8 3 8

Сумм (A) = 79, сумм (B) = 60, значит задача открытая, вводим дополнительного поставщика. B4 = 19

Z = 4×11 + 5×12 + 6×13 + 5×21 + 3×22 + 5×23 + …. + 8×43 -> min.
x11 + x12 + x13 <= 7
x21 + x22 + x23 <= 9
x31 + x32 + x33 <= 40
x41 + x42 + x43 <= 17
x11 + x21 + x31 + x41 =>16
x12 + x22 + x32 + x42 =>16
x13 + x23 + x33 + x43 =>28
xij => 0, i = 1,4, j = 1,3

Составляем макет задачи.

Нахождение допустимого плана по методу северо-западного угла.

В макет записывается матрица, элементы которой находятся так: отыскивается самая левая верхняя клетка макета, в которой еще не записан элемент матрицы. В качестве элемента записывается минимальный из грузов A и B.Затем значения грузов уменьшаются на эту величину. Если при этом значении A или B станут равными 0, то все клетки макета данной строки или столбца, в которые еще не записаны элементы матрицы, заполняются нулями.

Затем вычисляется система потенциалов Ui иVj, только для тех клеток, в которых Xij>0.

V1 — u1 = 4
V1 — u2 = 5
V2 — u2 = 3
V2 — u3 = 5
V3 — u3 = 6
V4 — u3 = 0
V4 — u4 = 0

U1 = 0
V1 = 4
u2 = -1
v2 = 2
u3 = -3
v3 = 3
u4 = -3
v4 = -3

Затем испытываем план на потенциальность, т. е. проверяем условие, что Vj — Ui <=Cij для пустых клеток.

L12 = 2-0-5=-3
L13 = 3-0-6=-3
L14 = -3
L23 = -1
L24 = -2
L31 = 2
L41 = -1
L42 = 2
L43 = -2

Рассмотрим клетку, для которой план не выполняется. Из этой клетки строим цикл — он начинается и заканчивается выбранной переменной. Цикл состоит из последовательных горизонтальных и вертикальных отрезков, концами которых должны быть не пустые ячейки. Затем помети клетки знаками «+" и «-». В начальную клетку ставим «+" и далее попеременно.

Из отрицательной полуцепи выбираем минимум (гамма). Далее перевозки клеток отрицательной полуцепи уменьшаем на гумму, а положительной — увеличиваем. Эта операция называется сдвигом по циклу.

Записываем новый план.

Для вновь полученного плана вычисляем систему потенциалов и т. д.

Ответ записываем в виде матрицы и считаем Z min.

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