Курсовая работа на тему: Задание . Задание . Задание . Задание

Введение

Так как полученная матрица- приведенная, то ξ(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)

Нj

Шаг 5.1

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

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

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

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

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

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

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

Нj

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

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;

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

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

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

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

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

Нj

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

Вывод:

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

Шаг 6

С56→ ∞;

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

Нj

Шаг 6.1

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

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

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

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

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

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

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

Нj

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

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;

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

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

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

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

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

Нj

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

Оглавление

- Введение 3

- Задание 1

- Задание 2

- Задание 3

- Задание 4

- Заключение... 48

- Список литературы... 49

Заключение

Так как ξ(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

Склад№4

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

Таблица 17а

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

Склад№4

Нi

Склад№4

Нj

Таблица 17б

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

Склад№4

Нi

Склад№4

Нj

Таблица 17в

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

Склад№4

Нi

Склад№4

Нj

2. Определим оценку G0, вычислив сумму приводящих констант:

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

Нj

Шаг 1

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

С12=0, С21=0, С34=0, С43=0, С46=0, С53=0, С64=0, С65=0;

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

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

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

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

Таблица 17(C11)

Нj

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

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

G0=G11U G12, где G11={2, 1}, а G12={2, 1}

Шаг 2

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

С13=0, С32=0, С34=0, С43=0, С46=0, С53=0, С64=0, С65=0;

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

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

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

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

Таблица 17(C21)

Нj

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

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

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

G11=G21U G22, где G21={3,2}, а G22={3,2}

Шаг 3

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

С15=0, С43=0, С46=0, С53=0, С64=0, С65=0

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

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

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

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

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

Нj

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

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;

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

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

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

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

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

Нj

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

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

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

Вывод:

Так как полученная матрица- приведенная, то ξ(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

Нj

Таблица 18а

Нj

Таблица 18(С0)

Нj

Шаг 5.1

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

С12=0, С23=0, С31=0, С34=0, С43=0, С46=0, С53=0, С64=0, С65=0;

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

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

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

1.3. Построим матрицу С11, для этого вычеркнем в матрице С0 первую строку и второй столбец. Выполним процесс приведения. В результате получим матрицу С11:

Таблица 18(С11)

Нj

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

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

G12=G21U G22, где G21={1,2}, а G22={1,2}

Шаг 5.2

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

С23=0, С31=0, С34=0, С43=0, С46=0, С53=0, С64=0, С65=0;

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

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

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

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

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

Нj

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

G21=G31U G32, где G31={2,3}, а G32={2, 3}

Шаг 5.3

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

С34=0, С46=0, С51=0, С56=0, С64=0, С65=0;

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

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

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

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

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

Нj

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

G31= G41 U G42 где = G41 {4,6},а = G42{4,6}

Шаг 5.4

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

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

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

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

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

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

Нi

Нj

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

Вывод:

Так как ξ(G51)=237< ξ(G61)=245 дальнейшее ветвление на подмножества не имеет смысла.

Вывод:

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

Издержки на транспортировку продукции по данному маршруту будут равны:(11+30+28+50+60+58)*0,5=118,5

Шаг 6

С32→ ∞;

Таблица 19(С0)

Нj

Шаг 6.1

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

С13=0, С34=0, С43=0, С46=0, С53=0, С64=0, С65=0;

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

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

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

1.3. Построим матрицу С11, для этого вычеркнем в матрице С0 первую строку и третий столбец. Выполним процесс приведения. В результате получим матрицу С11:

Таблица 19(С11)

Нj

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

G22=G31U G32, где G31={1,3}, а G32={1, 3}

Шаг 6.2

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

С34=0, С46=0, С52=0, С64=0, С65=0;

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

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

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

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

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

Нj

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

G31= G41 U G42 где = G41 {4,6},а = G42{4,6}

Шаг 6.3

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

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

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

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

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

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

Нi

Нj

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

Вывод:

Так как ξ(G51)=243< ξ(G61)=245 дальнейшее ветвление на подмножества не имеет смысла.

Дополнительное задание:

1. Для склада №3 по маршруту: скл№3→1→2→3→4→5→скл№3

Таблица 12

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

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

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

Склад№3

Склад№3

Найдем общий километраж: 22+24+82+48+42+87=305 км.

Издержки на транспортировку продукции по данному маршруту равен: 305*0,5=152,5 у.д.е.

Для склада №4 по маршруту: скл№4→1→2→3→4→5→скл№4

Таблица 17

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

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

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

Склад№4

Склад№4

Найдем общий километраж: 11+30+28+60+60+100=289 км.

Издержки на транспортировку продукции по данному маршруту равен: 289*0,5=144,5 у.д.е.

2. Для склада №3 по маршруту: скл№3→1→3→2→5→N→4→скл№3

Таблица 12

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

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

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

Склад№3

Склад№3

Найдем общий километраж: 22+55+82+155+43+38+70=465 км.

Издержки на транспортировку продукции по данному маршруту равен: 465*0,5=232.5 у.д.е. Из них водитель должен возместить: дистанция от магазина 5 до магазина 4 составляет 42 км. т. е. 21 у.д.е., а дистанция от магазина 5 до пункта N и до магазина 4 составляет 81 км. т. е. 40,5 у.д.е., разницу между 40,5 у.д.е. и 21 у.д.е. которая составила 19,5 у.д.е.

Для склада №4 по маршруту: скл№4→1→3→2→5→N→4→скл№4

Таблица 17

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

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

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

Склад№4

Склад№4

Найдем общий километраж: 11+53+28+60+43+38+58=291км.

Издержки на транспортировку продукции по данному маршруту равен: 291*0,5=145,5 у.д.е. Из них водитель должен возместить: дистанция от магазина 5 до магазина 4 составляет 60 км. т. е. 30 у.д.е., а дистанция от магазина 5 до пункта N и до магазина 4 составляет 81 км. т. е. 40,5 у.д.е., разницу между 40,5 у.д.е. и 30 у.д.е. которая составила 10,5 у.д.е.

Заключение:

Целью данной работы являлась оптимизация логистических издержек формирование, преобразования и поглощения материальных потоков на этапе распределения, а также получения практических навыков выполнения подобной работы.

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

Уникальность и новизна многих подходов к разрешению проблем логистики,

Создают предпосылки для обеспечения широкого внедрения в автотранспортное производство.

Список литературы

1. Гаджинский А.М. Практикум по логистике. - М.: Информационно - внедренческий центр "Маркетинг", 1999.-128 с.

2. Залманова М.Е. Логистика: Учеб. Пособие.- Саратов: Сарат. гос. техн. ун-т, 1995. 168 с.

3. Лаврова О.В. Распределительные системы в логистики: конспект лекций для студентов: .- Саратов: Сарат. гос. техн. ун-т, 1997. 35 с.

4. Лаврова О.В. Стратегии закупочной и распределительной логистике: конспект лекций для студентов: .- Саратов: Сарат. гос. техн. ун-т, 1997. 34 с.

5. Неруш Ю.М. Коммерческая логистика: Учебник для вузов- М.: Банки и биржи, ЮНИТИ, 1997.-271 с.

6. Сергеев В.И. Менеджмент в бизнес- логистике.- М.: Информационно издательский дом "Филинъ", 1997.-772с.

7. Семененко А.И. Предпринимательская логистика.- СПб.: Политехника 1997.-352с.

8. Родников А.Н. Логистика: Терминологический словарь -М.: Экономика,1995.- 252с.

9. Уваров С.А. Логистика. - СПб.: ЗАО "Инвестиции в науку и производства",1996-232с.

10. Эдодоус М., Методы принятия решений: Пер. с англ./ Под ред. Член-корр. РАН И.И. Елесеевой. - М.: аудит, ЮНИТИ, 1997.-590с.