Формирование логистической цепи

1.4. Вычислим оценку для ветвления G31:

ξ(G31)=291+14=305;

1.5. Произведем ветвление;

Так как ξ(G21)< ξ(G22), то на следующем шаге разбиваем подмножество ξ(G21).

G21=G31U G32, где G31= {4, 5}, а G32={4, 5}

Шаг 4

1.1. Выберем пары магазин-склад - претендентов на ветвление, т. е., (i,j), для которых Сij=0;

С12=0, С31=0, С61=0;

Для выявления претендентов подсчитаем оценки:

Ө(1,2)=11+33=44; Ө(3,1)=0+0=0; Ө(3,4)=11+0=11; Ө(6,1)=0+33=33;

Для ветвления выберем пару претендентов с максимальной оценкой, т. е. пару (1,2), так как max Ө(1,2)=44;

1.2. Вычислим оценку для ветвления G42:

ξ(G42)=305+44=349;

1.3. Построим матрицу С41, для этого вычеркнем в матрице C31 первую строку и второй столбец.Чтобы избежать образования замкнутых циклов, запретим переезд из 3 в 1: полагая, что С31→ ∞ и выполним процесс приведения. В результате получим матрицу С41:

Таблица 14(С41)

1.4. Вычислим оценку для ветвления G41:

ξ(G41)=305+0=305;

1.5. Произведем ветвление;

Так как ξ(G31)< ξ(G32), то на следующем шаге разбиваем подмножество ξ(G31).

G0=216

G11(2,3) G12(2,3)

216+35=251 216+48=264

G21(5,6) G22(5,6)

251+40=291 251+43=294

G31(4,5) G32(4,5)

291+14=305 291+52=343

G41(1,2) G42(1,2)

305+0=305 305+44=349

G51(3,4)

305+0=305

G61(6,1)

305+0=305

Вывод:

Так как полученная матрица- приведенная, то ξ(G41)= ξ(G31)=305. Матрица (С41) имеет размерность 2x2 и допускает в маршрут только двух пар (6,1) и (3,4), что соответствует шагам 5-6. В результате получаем цикл t={(2,3), (5,6), (4,5), (1,2), (6,1), (3,4)}, отвечающий подмножеству G61. Длина цикла t равна оценке для подмножества G61: 1(t)= ξ(G61)=305.

Сравним длину этого цикла с полученными ранее оценками для неветвленных подмножества. Подмножество G12 , G22 , имеют меньшую оценку, чем построенный цикл: ξ(G12)=264<ξ(G61)=305; ξ(G22)=294<ξ(G61)=305;

Эти подмножества могут привести к образованию цикла с меньшей оценкой, поэтому оно должно быть подвергнуто анализу.

Шаг 5

С23→ ∞;

Таблица 15(C11)

 Скачать реферат