Решение транспортных задач

Понятие и содержание транспортной задачи, ее цели и методика решения. Определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные расходы на перевозку всей продукции.

Рубрика Менеджмент и трудовые отношения
Вид контрольная работа
Язык русский
Дата добавления 30.11.2012
Размер файла 58,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

транспортный склад задача перевозка

Цель работы - определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные расходы на перевозку всей продукции.

Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громоздко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.

Задача 7.1. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.

Решение: Общий объём запасов:

Общая потребность:

Т.к. , то это транспортная задача закрытого типа.

Построение оптимального плана методом северо-западного угла

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

- 17

95

+ 12

10

17

2

21

1

U1 = 0

2

70

6

-10

11

70

20

6

28

9

U2 = -1

3

240

+ 10

-14

- 19

80

22

135

27

25

U3 = 7

4

85

18

14

14

15

23

21

7

85

U4 = -13

Vj

V1 = 17

V2 = 12

V3 = 15

V4 = 20

1

Здесь в верхнем правом углу клеток записана стоимость перевозки.

Заполнять таблицу первоначального опорного плана начинаем с клетки а1b1 - это северо-западный угол.

Закрываем потребности b1 поставкой из а1 и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а1 отправляем потребителю b2 и строку а1 исключаем из дальнейшего рассмотрения. Затем весь груз из а2 отправляем в b2, исключая строку а2 и частью груза из а3 закрываем потребность b2, исключая столбец b2. Далее закрываем потребность b3 поставкой из а3, а остаток груза из а3 отправляем потребителю b4. Груз из а4 отправляем потребителю b4. Опорный план составлен.

Стоимость перевозок по этому плану:

Z1 = 95·17 + 10•12 + 70•11 + 80•19 + 135•22 + 25?27 + 85?7 = 8265 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 4 - 1 = 7, что так и есть, т.е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij - Vj; Vj = Cij - Ui;

V1 = C11 - U1 = 17 - 0 = 17; V2 = C12 - U1 = 12 - 0 = 12; U2 = C22 - V2 = 11 - 12 = -1;

U3 = C32 - V2 = 19 - 12 = 7; V3 = C33 - U3 = 22 - 7 = 15; V4 = C34 - U3 = 27 - 7 = 20.

U4 = C44 - V4 = 7 - 20 = -13;

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij - (Vj + Ui) (вписаны в левый нижний угол)

Е13 = С13 - (V3 + U1) = 17 - (15 + 0) = 2; Е14 = С14 - (V4 + U1) = 21 - (20 + 0) = 1;

Е21 = С21 - (V1 + U2) = 6 - (17 - 1) = -10; Е23 = С23 - (V3 + U2) = 20 - (15 - 1) = 6;

Е24 = С24 - (V4 + U2) = 28 - (20 - 1) = 9; Е31 = С31 - (V1 + U3) = 10 - (17 + 7) = -14;

Е41 = С41 - (V1 + U4) = 18 - (17 - 13) = 14; Е42 = С42 - (V2 + U4) = 14 - (12 - 13) = 15;

Е43 = С43 - (V3 + U4) = 23 - (15 - 13) = 21;

Среди характеристик свободных клеток есть две отрицательные (Е21 = -10 и Е31 = -14), значит полученный план не оптимален.

Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (80), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2).

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

- 17

15

12

90

17

-12

+ 21

-13

U1 = 0

2

70

6

-10

11

70

20

-8

28

-5

U2 = -1

3

240

+ 10

80

19

14

22

135

- 27

25

U3 = -7

4

85

18

8

14

29

23

21

7

85

U4 = -27

Vj

V1 = 17

V2 = 12

V3 = 29

V4 = 34

2

Цена этого плана:

Z2 = 15·17 + 90•12 + 70•11 + 80•10 + 135•22 + 25?27 + 85?7 = 7145 д.е.

что меньше первого плана на 1120 ден. ед.

Проверка методом потенциалов показывает, что этот план не оптимален, т.к. среди характеристик свободных клеток есть отрицательные.

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

17

13

12

90

17

1

21

15

U1 = 0

2

70

6

3

11

70

20

5

28

8

U2 = -1

3

240

10

95

19

1

22

135

27

10

U3 = 6

4

85

18

8

14

16

23

21

7

85

U4 = -14

Vj

V1 = 4

V2 = 12

V3 = 16

V4 = 21

3

Далее без комментариев повторяем итерацию с перемещением перевозки по циклу в клетку a1b4 с отрицательной характеристикой (-13). Получаем третий план (табл. №3).

Его цена:

Z3 = 90•12 + 15?21 + 70•11 + 95•10 + 135•22 + 10?27 + 85?7 = 6950 д.е.

что меньше второго плана на 195 ден. ед.

Этот план оптимальный, т.к. все характеристики свободных клеток положительны.

Zопт = Zmin = Z3 = 6950 ден. ед.

Построение оптимального плана методом минимального элемента

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

17

14

12

105

17

2

21

1

U1 = 0

2

70

- 6

70

+ 11

-4

20

2

28

5

U2 = 3

3

240

+ 10

25

- 19

55

22

135

27

25

U3 = 7

4

85

18

29

14

16

23

22

7

85

U4 = -14

Vj

V1 = 3

V2 = 12

V3 = 15

V4 = 20

1

Минимальная стоимость перевозок (6) в клетке а2b1 - отправляем весь груз из а2 потребителю b1 и строку а2 исключаем из дальнейшего рассмотрения.

Следующий минимум (7) в клетке а4b4 - отправляем весь груз из а4 потребителю b4 и строку а4 исключаем из дальнейшего рассмотрения.

Следующий минимум (10) в клетке а3b1 - закрываем потребность b1 поставкой из а3 и столбец b1 исключаем из дальнейшего рассмотрения.

Следующий минимум (12) в клетке а1b2 - весь груз из а1 отправляем в b2 и строку а1 исключаем из дальнейшего рассмотрения.

Следующий минимум (19) в клетке а3b2 - закрываем потребность b2 поставкой из а3 и столбец b2 исключаем из дальнейшего рассмотрения.

Поставкой остатка груза из а3 закрываем потребности b3 и b4.

Опорный план составлен.

Стоимость перевозок по этому плану:

Z1 = 105·12 + 70•6 + 25•10 + 55•19 + 135•22 + 25?27 + 85?7 = 7215 д.е.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij - Vj; Vj = Cij - Ui;

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij - (Vj + Ui) (вписаны в левый нижний угол).

Среди характеристик свободных клеток есть одна отрицательная (Е22 = -4), значит полученный план не оптимален.

Строим для клетки а2b, цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2).

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

17

10

- 12

105

17

-2

+ 21

-3

U1 = 0

2

70

- 6

15

+ 11

55

20

2

28

5

U2 = -1

3

240

+ 10

80

19

4

22

135

- 27

25

U3 = 3

4

85

18

28

14

19

23

21

7

85

U4 = -17

Vj

V1 = 7

V2 = 12

V3 = 19

V4 = 24

2

Очевидно, что полученный план не является оптимальным, т.к. среди характеристик свободных клеток есть отрицательные.

Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a1b4 с отрицательной характеристикой (-3). Получаем третий план (табл. №3).

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

95

160

135

110

1

105

17

13

12

90

17

1

21

15

U1 = 0

2

70

6

3

11

70

20

5

28

8

U2 = -1

3

240

10

95

19

1

22

135

27

10

U3 = 6

4

85

18

8

14

16

23

21

7

85

U4 = -14

Vj

V1 = 4

V2 = 12

V3 = 16

V4 = 21

3

Этот план оптимальный, т.к. все характеристики свободных клеток положительны. План повторяет план, ране полученный методом северо-западного угла.

Zопт = Zmin = 6950 ден. ед.

Построение оптимального плана методом Фогеля

Номер поставщика

Мощность поставщика

Потребители и их спрос

1

2

3

4

95

160

135

110

1

105

17

12

90

17

21

15

5

5

5

5

5

2

70

6

11

70

20

28

5

5

9

3

240

10

95

19

22

135

27

10

9

9

3

3

3

4

85

18

14

23

7

85

7

4

1

3

14

4

1

3

6

1

3

6

2

5

6

2

5

При определении опорного плана методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находим разность между двумя записанными в них минимальными затратами. Эти разности записаны в специально отведенных для этого строках и столбцах для каждого шага. Среди указанных разностей выбрана максимальная. В строке (или в столбце), которой данная разность соответствует, определён минимальный тариф и клетка, в которой он записан, заполнена на данной итерации (выделено жирным шрифтом).

Например, на первом шаге в первой строке минимальные затраты 17 и 12, разность - 5, во 2-ой строке 11 и 6, разность 5, в 3-ей 19 и 10, разность 9, в 4-ой 14 и 7, разность 7.

В 1-ом столбце минимальные затраты 10 и 6, разность 4, во 2-ом 12 и 11, разность 1, в 3-ем 20 и 17, разность 3, в 4-ом 21 и 7, разность 14.

Наибольшая из этих разностей - 14 соответствует 4-му столбцу. В этом столбце минимум затрат - 7 в строке 4. Заполняем клетку а4b4 объёмом поставок 85 единиц, который может быть поставлен от четвёртого поставщика и строку 4 из дальнейшего рассмотрения исключаем. По аналогии заполнены остальные клетки таблицы и получен опорный план.

Цена этого плана:

Z1 = 90•12 + 15?21 + 70•11 + 95•10 + 135•22 + 10?27 + 85?7 = 6950 д.е.

Этот полученный план является оптимальным, т.к. такой же план получен при использовании методов северо-западного угла и минимального элемента.

Задача 7.2. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.

Решение: Общий объём запасов:

Общая потребность:

Т.к. , то это транспортная задача открытого типа.

Для приведения её к закрытому типу вводим фиктивного потребителя с нулевой стоимостью перевозок, имеющего потребность:

Построение оптимального плана методом северо-западного угла

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

- 17

95

+ 12

10

17

2

21

1

0

-13

U1 = 0

2

70

6

-10

11

70

20

6

28

9

0

-12

U2 = -1

3

240

+ 10

-14

- 19

55

22

135

27

50

0

-20

U3 = 7

4

85

18

14

14

15

23

21

7

60

0

25

U4 = -13

Vj

V1 = 17

V2 = 12

V3 = 15

V4 = 20

V5 = 13

1

Порядок составления опорного плана этим методом описан в задаче 7.1.

Стоимость перевозок по этому плану:

Z1 = 95·17 + 10•12 + 70•11 + 55•19 + 135•22 + 50?27 + 60?7 = 8290 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 5 - 1 = 8, что имеет место в действительности, т.е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij - Vj; Vj = Cij - Ui;

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij - (Vj + Ui) (вписаны в правый нижний угол).

Среди характеристик свободных клеток есть отрицательные, значит полученный план не оптимален.

Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2) с ценой z2 = 7520.

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

- 17

40

12

65

17

-12

+ 21

-13

0

-27

U1 = 0

2

70

6

-10

11

70

20

-8

28

-5

0

-26

U2 = -1

3

240

+ 10

55

19

14

22

135

- 27

50

0

-20

U3 = -7

4

85

18

28

14

29

23

21

7

60

0

25

U4 = -27

Vj

V1 = 17

V2 = 12

V3 = 29

V4 = 34

V5 = 27

2

Среди характеристик свободных клеток есть отрицательные значит полученный план не оптимален.

Строим для клетки а1b4 с отрицательной характеристикой (-13), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (40), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №3) с ценой z3 = 7000.

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

17

13

12

65

17

1

21

40

0

-14

U1 = 0

2

70

6

3

11

70

20

5

28

8

0

-13

U2 = -1

3

240

10

95

19

1

22

135

- 27

10

+ 0

-20

U3 = 6

4

85

18

28

14

16

23

21

- 7

60

+ 0

25

U4 = -14

Vj

V1 = 4

V2 = 12

V3 = 16

V4 = 21

V5 = 14

3

Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а3b5 с характеристикой (-20). Получаем четвёртый план (табл. №4) c ценой z4 = 6800.

Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а2b1 с характеристикой (-17). Перемещаем по этому циклу наименьшую перевозку (15), отмеченную знаком «минус».

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

17

-7

+ 12

65

17

-19

- 21

40

0

-14

U1 = 0

2

70

+ 6

-17

- 11

70

20

-15

28

-8

0

-13

U2 = -1

3

240

- 10

95

19

21

22

135

27

20

+ 0

10

U3 = -14

4

85

18

28

14

16

23

3

+ 7

70

- 0

15

U4 = -14

Vj

V1 = 24

V2 = 12

V3 = 36

V4 = 21

V5 = 14

4

Получаем пятый план (табл. №5) с ценой z5 = 6545.

17

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

10

- 12

80

+ 17

-2

21

25

0

3

U1 = 0

2

70

- 6

15

+ 11

55

20

2

28

8

0

4

U2 = -1

3

240

+ 10

80

19

4

- 22

135

27

3

0

25

U3 = 3

4

85

18

25

14

16

23

18

7

85

0

U4 = -14

Vj

V1 = 7

V2 = 12

V3 = 19

V4 = 21

V5 = -3

5

Ещё одна итерация по клетке а1b3 с перемещением 15 единиц груза и получаем оптимальный план с положительными характеристиками всех свободных клеток (табл. №6):

17

Номер поставщика

Мощность поставщика

Потребители и их спрос

Ui

1

2

3

4

5

95

135

135

110

25

1

105

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

12

12

65

17

15

21

25

0

5

U1 = 0

2

70

6

2

11

70

20

4

28

8

0

6

U2 = -1

3

240

10

95

19

2

22

120

27

1

0

25

U3 = 5

4


Подобные документы

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

    презентация [559,7 K], добавлен 23.01.2015

  • Принятие управленческих решений с использованием метода "платежной матрицы". Линейное программирование (задача планирования производства). Пример решения транспортной задачи, определение начального плана перевозок с помощью метода северо-западного угла.

    контрольная работа [1,1 M], добавлен 17.12.2013

  • Распределение оптимальным образом денежных средств между предприятиями. Формула для расчета суммарного дохода. Определение оптимального маршрута доставки груза, который обеспечивал бы минимальные транспортные расходы. Оптимальный план инвестиций.

    контрольная работа [35,2 K], добавлен 01.10.2014

  • Цели, задачи, содержание планирования себестоимости промышленной продукции. Составные элементы плана по издержкам предприятия. Критерии классификации и виды затрат на производство, нормы и нормативы на некоторые из них. Расчет себестоимости продукции.

    курсовая работа [55,6 K], добавлен 14.03.2010

  • Понятие, показатели и механизмы управления качеством продукции на предприятии. Цели и задачи мониторинга и оценивания эффективности производственных процессов фирмы. Разработка плана обеспечения качества новых видов продукции на примере ОАО "ЧМЗАП".

    курсовая работа [226,1 K], добавлен 14.02.2012

  • Формирование набора критериев. Постановка задачи о назначениях. Выбор метода принятия решения, его обоснование. Распределение работ, при котором в минимальные сроки будет возможно оценить затраты на проект, его длительность, рентабельность и прибыль.

    курсовая работа [2,8 M], добавлен 13.01.2015

  • Понятие и принципы управления качеством на современном предприятии, определение его необходимости и значения. Менеджмент как сфера деятельности, уровни решения его управленческих задач. Основные принципы обеспечения качества продукции, стандарты.

    контрольная работа [34,0 K], добавлен 11.01.2011

  • Экономическая сущность, задачи и функции транспортной логистики, перспективы развития. Показатели использования транспортных средств, методика их расчета. Анализ логистической системы ЗАО "Регата" и разработка мероприятий по ее совершенствованию.

    курсовая работа [41,5 K], добавлен 05.02.2012

  • Понятие и содержание управленческого решения, определение и реализация конкретной цели, стоящей перед управляемым объектом. Типология и функции, условия и факторы качества, методы и модели разработки, виды и целевая ориентация управленческих решений.

    реферат [26,3 K], добавлен 26.01.2010

  • Построение математической модели проблемы в виде задачи линейного программирования. Факторы увеличения прибыльности предприятия. Расчет плана производства продукции мебельной фабрикой, согласно которому прибыль от её реализации является максимальной.

    контрольная работа [1,1 M], добавлен 01.03.2016

  • Способы принятия управленческого решения. Определение длительности производственного цикла при синхронном движении предметов труда. Риски и неопределенности в расчетах эффективности инновационных проектов. Понятие миссии, целей и задач организации.

    контрольная работа [84,8 K], добавлен 11.07.2011

  • Определение себестоимости для продукции, алгоритм расчета цены и прибыли предприятия. Оценка затрат предприятия на оплату труда, амортизацию здания и оборудования, материальных затрат. Срок окупаемости продукции, анализ объема реализации продукции.

    бизнес-план [299,0 K], добавлен 04.05.2013

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

    курсовая работа [631,0 K], добавлен 04.12.2013

  • Понятие и основные признаки вовлеченности работника. Вовлечение персонала в решение корпоративных задач. Вовлеченность в рабочий процесс. Инструменты измерения инициативности и нацеленности персонала. Методика расчета индекса вовлеченности работника.

    реферат [1,4 M], добавлен 11.09.2010

  • Понятие и содержание, факторы, критерии и показатели конкурентоспособности продукции. Анализ существующих подходов к оценке конкурентоспособности продукции. Определение путей и мероприятий по повышению данного показателя для товара на современном рынке.

    дипломная работа [156,9 K], добавлен 05.07.2012

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

    дипломная работа [1,9 M], добавлен 26.09.2010

  • Понятие управленческого решения и требования к нему. Процесс выработки решения и основные задачи при его принятии. Сущность и принципы метода мозгового штурма, его виды, этапы, достоинства и недостатки. Роль творческого мышления для принятия решения.

    презентация [1,2 M], добавлен 12.03.2012

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

    дипломная работа [115,4 K], добавлен 27.10.2015

  • Методы и модели решения задач. Модель задачи оптимального использования ресурсов. Стандартные способы решения системы линейных уравнений. Основная теорема линейного программирования. Построение симплекс-таблицы. Построение начального опорного плана.

    лабораторная работа [275,9 K], добавлен 17.10.2013

  • Определение целей и задач сервисной логистики, которая изучает оптимизацию потоков услуг, предоставляемых предприятиями потребителям продукции. Виды услуг. Формирование системы логистического сервиса фирмы. Анализ уровня сервиса и затрат на его развитие.

    реферат [35,1 K], добавлен 30.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.