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

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

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

ξ(G32)=241+7=248;

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

Таблица 17(С31)

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

ξ(G31)=241+4=245;

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

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

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

Шаг 4

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

С43=0, С46=0, С56=0, С64=0;

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

Ө(4,3)=2+0=0; Ө(4,6)=0+0=0; Ө(5,6)=0+22=22; Ө(6,4)=2+22=24;

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

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

ξ(G42)=245+24=269;

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

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

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

ξ(G41)=245+0=245;

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

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

G0=194

G11(2,1) G12(2,1)

194+30=224 194+36=230

G21(3,2) G22(3,2)

224+17=241 224+19=243.

G31(1,5) G32(1,5)

241+4=245 241+7=248

G41(6,4) G42(6,4)

245+0=245 245+24=269

G51(4,3)

245+0=245

G61(5,6)

245+0=245

Вывод:

Так как полученная матрица- приведенная, то ξ(G41)= ξ(G31)=245.

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

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

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

Шаг 5

С21→ ∞;

Таблица 18

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