Рефераты

Курсовая работа: Формирование логистической цепи

 

 Склад

№3

1

3

4

5

Склад№3

0 17 55 65

2

0

6 57 85

3

0 10

3 43

4

28 54 0

0

5

45 78 37 0

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

ξ(G11)=216+35=251        

1.5.Произведем ветвление G0=G11U G12, где G11={1, 2}, G12={1, 2}

Шаг 2

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

ССклад№31=0, С2Склад№3=0, С3Склад№3=0, С43=0, С45=0, С54=0;

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

Ө(Склад№3,1)=17+10=27;

 Ө(2,Склад№3)=6+0=6; 

Ө(3,Склад№3)=3+0=3;

 Ө(4,3)=6+0=6;

Ө(4,5)=43+0=43;

 Ө(5,4)=37+3=40;

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

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

ξ(G22)=251+43=294;

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

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

 Склад

№3

1

3

4

h i

Склад№3

0 17 55

0

2

0

6 57

0

3

0 10

3

0

5

45 78 37

37

 Склад

№3

1

3

4

Склад№3

0 17 55

2

0

6 57

3

0 10

3

5

8 41 0

h j

0 0 0

3


 Склад

№3

1

3

4

Склад№3

0 17 52

2

0

6 54

3

0 10

0

5

8 41 0

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

ξ(G21)=251+40=291;

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

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

G11=G21U G22, где G21={4,5}, G22={4,5}

Шаг 3

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

Сij=0;

ССклад№3 1=0, С2Склад№3=0, С3Склад№3=0, С34=0, С53=0;

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

Ө(Склад№3,1)=17+10=27;

Ө(2,Склад№3)=6+0=6;

Ө(3,Склад№3)=0+0=0;

Ө(3,4)=0+54=54;

Ө(5,3)=8+6=14;

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


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

ξ(G32)=291+54=345;

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

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

1 2 4

min i

1

0 11

0

3 0

0

0

6 0 33

8

min j

0

0

6


 Склад

№3

1

3

Склад№3

0 17

2

0

6

5

8 41 0

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

min i

3

0

0

6 0

0

min j

0

0

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)

1

2

3

4

5

6

hi

1

0 11 17 55 65

0

2

0

14 61 85

11

3

35 0

41 92 120

0

4

0 10 0

3 43

0

5

28 54 48 0

0

0

6

45 78 76 37 0

0

Hj

0

0

37

0

0

0

 ξ(G12)=216+48=264;

Шаг 5.1

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

С12=0, С21=0, С32=0, С41=0, С43=0, С54=0, С56=0, С65=0;

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

Ө(1,2)=11+0=11; Ө(2,1)=14+0=14; Ө(3,2)=35+0=35; Ө(4,1)=0+0=0; Ө(4,3)=11+0=11;  Ө(5,4)=14+0=14; Ө(5,6)=43+0=43; Ө(6,5)=3+37=40;

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

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

ξ(G22)=264+43=307;

1.3. Построим матрицу С21, для этого вычеркнем в матрице C11 пятую строку и шестой столбец. Чтобы избежать образования замкнутых циклов, запретим переезд из 6 в 5, полагая, что С65→ и выполним процесс приведения. В результате получим матрицу С21:

 

Таблица 15(С21)

1 2 3 4 5

hi

1

0 11 17 52

0

2 0

14 58

0

3 35 0

41 89

0

4 0 10 0

0

0

6 8 41 39 0

37

Hj

0

0

0

0

3

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

ξ(G21)=264+40=304;

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

G12=G21U G22, где G11={5, 6}, а G12={5, 6}

Шаг 5.2.

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

С12=0, С21=0, С32=0, С41=0, С43=0, С45=0, С64=0;

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

Ө(1,2)=11+0=11; Ө(2,1)=14+0=14; Ө(3,2)=35+0=35; Ө(4,1)=0+0=0; Ө(4,3)=11+0=11;  Ө(4,5)=52+0=52; Ө(6,4)=8+14=22;

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

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

ξ(G32)=304+52=356;

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

таблица 15(С31 )

1 2 3 4

hi

1

0 11 17

0

2 0

14

0

3 35 0

41

0

6 0 33 31

8

Hj

0

0

11

14

 

 

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

ξ(G31)=304+33=337;

Вывод:

Так как ξ(G31)=337> ξ(G61)=305 дальнейшее ветвление на подмножества не имеет смысла, так как длина данного цикла будет увеличиваться.

Шаг 6

С56→ ;           

Таблица 16(С21)

1 2 4 5 6

hi

1

0 17 55 22

0

3 0

6 57 42

0

4 0 10

3 0

0

5 28 54 0

0

6 45 78 37 0

0

Hj

0

0

0

0

43

ξ(G22)=251+43=294;


Шаг 6.1

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

С12=0, С31=0, С41=0, С46=0, С54=0, С65=0;

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

Ө(1,2)=17+10=27; Ө(3,1)=0+6=6; Ө(4,1)=0+0=0; Ө(4,6)=22+0=22;  Ө(5,4)=6+28=34; Ө(6,5)=3+37=40;

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

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

ξ(G32)=294+40=334;

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

 

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

1 2 4 6

hi

1

0 17 22

0

3 0

6 42

0

4 0 10

0

0

5 28 54 0

0

Hj

0

0

0

0

 

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

ξ(G31)=294+0=294;

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

G22=G31U G32, где G31={6, 5}, а G32={6, 5}

Шаг 6.2

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

С12=0, С31=0, С41=0, С46=0, С54=0;

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

Ө(1,2)=17+10=27; Ө(3,1)=0+6=6; Ө(4,1)=0+0=0; Ө(4,6)=0+22=22;  Ө(5,4)=6+28=34;

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

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

ξ(G42)=294+34=328;

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

таблица 16(С41 )

1 2 6

hi

1

0 0

0

3 0

20

0

4 0 10

0

Hj

0

0

22

 

 

 

 

 

 

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

ξ(G41)=294+22=316;

Вывод:

Так как ξ(G41)=316> ξ(G61)=305 дальнейшее ветвление на подмножества не имеет смысла, так как длина данного цикла будет увеличиваться.

Вывод:

В результате проверки данных подмножеств выяснилась, что полученная длина новых циклов больше, чем длина предыдущего. Следовательно, маршрут 1→2→3→4→5→6→1, является оптимальным.

Издержки на транспортировку продукции по данному маршруту будут равны: (22+24+82+48+42+87)*0,5=152,5 у.д.е.


2. Решаем задачу для автомобилей для складов № 4.

Таблица 17

Расстояние между оптовым складом и сетью розничных магазинов

Склады и магазины

Расстояние между складами и магазинами, км

Склад№4

1

2

3

4

5

Склад№4

11 39 63 58 100

1

11

30 53 55 90

2

45 30

28 40 60

3

63 61 28

60 50

4

58 55 34 60

60

5

100 90 60 58 60

Пользуясь методом ветвей и границ, определим порядок посещения автомобилем склада и пяти магазинов. Сформируем начальную «матрицу» и осуществим ее приведение по строкам и столбцам.

Таблица 17а

     J

          I

Расстояние между складами и магазинами, км

Склад№4

1

2

3

4

5

 Hi

Склад№4

11 39 63 58 100

11

1

11

30 53 55 90

11

2

45 30

28 40 60

28

3

63 61 28

60 50

28

4

58 55 34 60

60

34

5

100 90 60 58 60

58

Hj

Таблица 17б

     J

   I

Расстояние между складами и магазинами, км

Склад№4

1

2

3

4

5

   Hi

Склад№4

0 28 52 47 89

11

1

0

19 42 44 79

11

2

17 2

0 12 32

28

3

35 33 0

32 22

28

4

24 21 0 26

26

34

5

42 32 2 0 2

58

Hj

0

0

0

0

2

22

Таблица 17в

     J

  

I

Расстояние между складами и магазинами, км

Склад№4

1

2

3

4

5

Hi

Склад№4

0 28 52 45 67

11

1

0

19 42 42 57

11

2

17 2

0 10 10

28

3

35 33 0

30 0

28

4

24 21 0 26

4

34

5

42 32 2 0 0

58

Hj

0

0

0

0

2

22

Страницы: 1, 2, 3, 4, 5


© 2010 Собрание рефератов