Главная стр 1
скачать


Министерство образования Российской Федерации
Прикамский социальный институт

ЛОГИСТИКА

Методическое пособие по проведению практических занятий

для студентов экономического факультета
Специальность 080507 – «Менеджмент организации»
Выпуск 1. Транспортная логистика


Пермь


2009


  1. Решение транспортной задачи

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

Постановка задачи: имеется “m” пунктов отправления А1, А2, …, А m , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а 1 , а 2 , … , а m единиц. Имеется “n” пунктов назначения В1, В2, … , Вn , подавших заявки соответственно на b1 , b2 , … , bn единиц груза. Сумма всех заявок равна сумме всех запасов: . Известны стоимости сij перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj (i = 1, 2, .. , m; j = 1, 2, … , n).

Все числа сij , образующие прямоугольную таблицу (матрицу), заданы:.



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

Требуется: составить такой план перевозок (откуда, куда и сколько единиц везти), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Обозначим xij – количество единиц груза, отправляемого из i-го пункта отправления Ai в j-й пункт назначения BJ. Неотрицательные переменные xij можно тоже записать в виде матрицы .

Совокупность чисел xij будем называть “планом перевозки”, а сами величины xij – “перевозками”.

Переменные xij должны удовлетворять следующим условиям.

1. Суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это можно записать в виде:




2. Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Запишем это в виде:

3. Суммарная стоимость всех перевозок, то есть сумма величин xij умноженных на соответствующие стоимости сij должна быть минимальной:



Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (1) и (2) – все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будем называть опорным, если в нем отличны от нуля не более m+n+1 базисных перевозок, а остальные перевозки равны нулю.

План будем называть оптимальным, если он, среди допустимых планов, приводит к минимальной суммарной стоимости перевозок (F = min)

Для нахождения оптимального плана строится транспортная таблица, состоящая из “m” строк и “n” столбцов. В правом верхнем углу каждой клетки записывается стоимость сij перевозки единицы груза из Аi в Вj , а в центре клетки записывается сама переменная xij . Для удобства вычислений, к транспортной таблице добавляется вспомогательный столбец, содержащий величины запасов грузов в пунктах отправления, и вспомогательная строка, содержащая величины заявок, поданных пунктами назначения.

Для решения задачи могут применяться различные методы, такие как: метод линейного программирования; метод потенциалов; сетевой метод; венгерский метод; метод ветвей и границ; метод северо-западного угла.



    1. Решение транспортной задачи методом северо-западного угла

Рассмотрим на примере все этапы решения практической задачи данным методом.

Задача.

На двух складах А и В имеются соответственно 50 и 40 т груза. Требуется спланировать перевозки к трем потребителям С, Д и Е так, чтобы потребитель С получил 30 т, Д – 20 т, Е – 40 т, а затраты на перевозку были минимальными. Стоимость перевозок от складов к потребителям заданы в табл.1.

Таблица 1

Стоимость перевозок



потребители

склады


С

Д

Е




А

3

x11



2

x12



1

x13




50

В

3

x21



5

x22




6

x23



40




30

20

40







  1. Составим математическую модель задачи

На множестве решений системы:

При этом количество пунктов отправления m = 2, а количество пунктов назначения n =3.

Найти минимальное значение целевой функции F = 3 x11 + 2 x12 + x13 +

3 x21 + 5 x22 + 6 x23 .

2. Составим первое распределение поставок методом “северо-западного угла”, начиная заполнение транспортной таблицы с левого верхнего (“северо-западного”) угла.

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

Найдем новый северо-западный угол – это клетка АД. Из условий задачи известно, что потребитель Д заказал 20 т груза. На складе А осталось: 50 – 30 = 20 т груза. Направим этот груз потребителю Д. В этом случае, весь груз со склада А перевезен, и первую строчку можно исключить из дальнейшего рассмотрения. Заказ потребителя Д также полностью выполнен и столбик Д транспортной таблицы можно исключить из дальнейшего рассмотрения.

В оставшейся части таблицы найдем новый северо-западный угол – это клетка ВЕ. Заказ потребителя Е – 40 т груза полностью удовлетворим со склада В. Тогда исходным распределением поставок будет: x11 = 30; x12 = 20; x23 = 40 и транспортная таблица примет следующий вид (табл.2).

Таблица 2

потребители

склады


С

Д

Е




А

3

30


2

20


1


50

В

3


5


6

40


40




30

20

40




По таблице определим значение целевой функции F1 = 30·3 +20·2 + 40·5 = 370 руб.

Данный план является допустимым, т.к. сумма перевозок по строке равна запасу соответствующего пункта отправления (склада), а сумма перевозок по столбцу – заявке соответствующего пункта назначения (потребителя).

Проверим, является ли план перевозок опорным. Определим величину

m + n – 1 = 2 + 3 – 1 = 4, и сравним ее со значение с количеством базисных перевозок, отличных от нуля (p = 3). Условие m + n – 1 ≥ p выполняется, т.е. план перевозок является опорным.

3. Проверим, является ли полученный план оптимальным. Сформулируем математическую модель задачи, двойственной исходной. Для этого введем пять переменных: u1, u2 (по числу складов) и v1, v2, v3 (по числу потребителей). Результаты внесем в таблицу 3.

Таблица 3

1 план

30

20










40







x11

x12

x13

x21

x22

x23




u1

1

1

1

0

0

0

50

u2

0

0

0

1

1

1

40

v1

1

0

0

1

0

0

30

v2

0

1

0

0

1

0

20

v3

0

0

1

0

0

1

40




3

2

1

3

5

6




Теперь двойственную задачу можно сформулировать так: требуется найти максимальное значение целевой функции F = 50u1 + 40u2 + 30v1 + 20v2 + 40v3, на множестве решений системы:

u1 + v1 ≤ 3

u1 + v2 ≤ 2

u1 + v3 ≤ 1

u2 + v1 ≤ 3

u2 + v2 ≤ 5

u2 + v3 ≤ 6.


Заметим, что если все ограничения исходной задачи имели вид равенств, то переменные двойственной задачи (u1, u2, v1, v2, v3) могут принимать и отрицательные значения.

Проверка оптимальности полученного плана перевозок состоит в следующем:

если некоторые переменные исходной задачи строго больше нуля (xij>0), то соответствующие им условия двойственной задачи выполняются как строгие равенства. При этом получаем систему из (m + n -1) уравнений с (m + n) переменными: u1, u2,…, um; v1, v2,…, vn;

если найти одно из решений полученной системы и подставить его в оставшиеся неравенства системы ограничений двойственной задачи, не вошедшие в систему (m + n – 1) уравнений, и эти неравенства выполняются, то проверяемый план является оптимальным;

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

Тогда для нашей задачи, в соответствии с табл.3, занятым клеткам транспортной таблицы соответствует следующая система уравнений:

u1 + v1 = 3

u1 + v2 = 2

u2 + v3 = 6.
Положим u1 равным нулю и решим данную систему. Из первого уравнения находим v1 = 3, из второго - v2 = 2. Третье уравнение не имеет однозначного решения, так как в рассматриваемой системе три уравнения, но четыре переменных. Поэтому введем так называемую “условную подстановку”, для чего будем считать клетку x13 (или x22) занятой, поместив в нее число “0”.

Получим следующую систему уравнений:

u1 + v1 = 3 Решением данной системы будет следующее:

u1 + v2 = 2 u1 = 0; u2 = 5; v1 = 3; v2 = 2; v3 = 1.

u1 + v3 = 1

u2 + v3 = 6.


Подставим полученные значения в оставшиеся неравенства системы ограничений двойственной задачи:

u2 + v1 ≤ 3 5 + 3 ≤ 3 8 ≤ 3

u2 + v2 ≤ 5 5 + 2 ≤ 5 7 ≤ 5

Условия не выполняются, т.е. первоначальный план можно улучшить.

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

В теории линейного программирования доказывается, что при опорном плане для каждой свободной клетки транспортной таблицы существует цикл, и притом единственный, одна вершина которого (первая) лежит в данной свободной клетке, а остальные – в базисных клетках.

При этом нечетные вершины цикла (1, 3, 5 и т.д.) отмечаются знаком “+” – это значит, что перевозки в этих клетках увеличиваются. А четные вершины (2, 4, 6 и т.д.) отмечаются знаком “-“, так как перевозки в них уменьшаются.

Так как свободных клеток в таблице несколько, то и возможных циклов также будет несколько. Приступая к оптимизации и выбирая цикл (контур) перераспределения поставок, необходимо определить “цену цикла”, подсчитав сумму стоимостей перевозок, стоящих в вершинах цикла, учитывая знак (+ или -), которым данная вершина отмечена.

Для нашего примера существует две свободные клетки (ВС и ВД) в транспортной таблице и, соответственно два возможных цикла (табл.4).

Таблица 4



потребители

склады


С

Д

Е



А


3

--
30

2


--


20

1

+

+

0


50

В


3


+


5

+

6

--

--



40

40





30

20

40






Первый цикл: ВД АД АЕ ВЕ ВД, его цена: 5 – 2 + 1 – 6 = -2.

Второй цикл: ВС АС АЕ ВЕ ВС, его цена: 3 – 3 + 1 – 6 = -5.

Поэтому выбираем второй цикл и проводим перераспределение поставок. Результат показан в таблице 5.

Таблица 5



потребители

склады


С

v1



Д

v2



Е

v3






А

u1



3


2

20


1

30


50

В

u2



3

30


5


6

10


40




30

20

40



Из таблицы видно, что решением является: x12 = 20; x13 = 30; x21 = 30;

x23 = 10. F2 = 20·2 +30·1 + 10·6 +30·3 = 220 рублей.

Можно рассчитать и иначе: F2 = F1 – (цена цикла х величина перемещаемых перевозок) = 370 - 5·30 = 220 рублей.

5. Проверим оптимальность полученного плана. Для этого решим систему уравнений:

u1 + v2 = 2 Решением данной системы будет следующее:

u1 + v3 = 1 u1 = 0; u2 = 5; v1 = -2; v2 = 2; v3 = 1.

u2 + v1 = 3

u2 + v3 = 6.
Проверим выполнение неравенств:

u1 + v1 ≤ 3 0 + (-2) ≤ 3 -2 ≤ 3

u2 + v2 ≤ 5 5 + 2 ≤ 5 7 ≤ 5
Условия не выполняются, т.е. план можно улучшить.

6. Проведем вторую циклическую перестановку в транспортной таблице.

Возможны два цикла (табл.6).

Первый цикл: ВД АД АЕ ВЕ ВД, его цена: 5 – 2 + 1 – 6 = -2.

Второй цикл: АС АЕ ВЕ ВС АС, его цена: 3 – 1 + 6 – 3 = 5, т.е. он увеличит общую цену перевозки.


Таблица 6

потребители

склады


С

Д

Е



А


3

+



2


--


20

1

--

+

30


50

В


3


--

30



5

+

6

--

+



10

40





30

20

40



Поэтому выбираем первый цикл и проводим перераспределение поставок. Результат перераспределения приведен в таблице 7.

Таблица 7

потребители

склады


С

v1



Д

v2



Е

v3






А

u1



3


2

10

1

40

50


В

u2



3

30

5

10

6

40





30

20

40



Из таблицы видно, что решением является: x12 = 10; x13 = 40; x21 = 30;

x22 = 10. F3 = 10·2 +40·1 + 30·3 +10·5 = 200 рублей.

7. Проверим оптимальность плана. Для этого решим систему уравнений:

u1 + v2 = 2 Решением данной системы будет следующее:

u1 + v3 = 1 u1 = 0; u2 = 3; v1 = 0; v2 = 2; v3 = 1.

u2 + v1 = 3

u2 + v2 = 5.

Проверим выполнение неравенств:

u1 + v1 ≤ 3 0 + 0 ≤ 3 0 ≤ 3

u2 + v3 ≤ 6 3 + 1 ≤ 6 4 ≤ 6.
Условия выполняются, т.е. план является оптимальным.

Если число складов и потребителей значительно больше, для решения задачи используют специальные программы, реализованные на ЭВМ.



Задачи для самостоятельного решения.

Задача 2. На вокзалы А и В прибыло по 30 комплектов мебели. Эту мебель необходимо доставить в магазины С, Д и Е, по 20 комплектов в каждый. Спланировать перевозки этой мебели так, чтобы затраты на перевозку были минимальными. Стоимость перевозок от вокзалов до магазинов заданы в табл.8.

Таблица 8

Стоимость перевозок

магазины

вокзалы


С

Д

Е




А

2

x11



3

x12



2

x13



30

В

1

x21



2

x22



3

x23



30




20

20

20





Задача 3. В пунктах А и В находятся заводы по производству кирпича, в пунктах С и Д – карьеры, снабжающие их песком. Заводу А необходимо 40 т песка, заводу В – 50 т. Карьер С готов доставить на заводы 70 т песка, а карьер Д – 30 т. Распланируйте перевозки таким образом, чтобы затраты на перевозку были минимальными. Для упрощения задачи в таблицу 9 введен условный потребитель Е. Стоимость перевозок песка от карьеров до заводов заданы в табл.9.

Таблица 9

Стоимость перевозок

заводы

карьеры


А

В

Е




С

2

x11



6

x12



0

x13



70

Д

5

x21



3

x22



0

x23



30




40

50

10




Задача 4. На трех складах А, В и С находятся соответственно 5, 8 и 7 тыс. т. сырья, которое должно быть доставлено на оптовые базы четырех городов D, E, F и G для реализации по торговой сети. При этом потребности городов в этом сырье определены соответственно следующим образом: 4, 5, 4 и 7 тыс. т. Стоимость перевозки 1 тыс. т. груза со складов на оптовые базы соответствующих городов представлены в таблице 10. Определите оптимальный план перевозок сырья, при котором общая стоимость перевозок будет минимальной.

Таблица 10

Стоимость перевозок

базы

склады


D

E

F

G




А

3

x11



4

x12



5

x13



5

x14



5

В

1

x21



3

x22



2

x23



3

x24



8

С

2

x31



2

x32



5

x33



1

x34



7




4

5

4

7

20




скачать


Смотрите также:
Методическое пособие по проведению практических занятий для студентов экономического факультета Специальность 080507 «Менеджмент организации»
170.47kb.
Методическое пособие по проведению практических занятий для студентов экономического факультета Специальность 080507 «Менеджмент организации»
176.88kb.
Методическое пособие по проведению практических занятий для студентов экономического факультета Специальность 080507 «Менеджмент организации»
278.08kb.
Методическое пособие для практических занятий красноярск 2002
886.62kb.
Учебное пособие для студентов очного и заочного обучения специальности 080507 «Менеджмент организации»
1629.56kb.
Занятие №18 Факторы экономического роста
97.5kb.
Занятие №1 Методические указания к проведению практических работ по дисциплине «Корпоративный менеджмент» для студентов специальности
665.58kb.
Занятие №1 Методические указания к проведению практических работ по дисциплине «Корпоративный менеджмент» для студентов специальности
665.7kb.
Учебно-методическое пособие по организации и проведению практических занятий оздоровительной направленности Тема: профилактика нарушения осанки, плоскостопия заборов Вадим Геннадьевич
107.32kb.
Методические указания к проведению практических работ по дисциплине «Экономическая теория» для студентов специальности «Менеджмент организации» (Менеджмент в спорте),
238.76kb.
Наглядное пособие для студентов экономического факультета Нижний Новгород 2005 ббк 65. 052 З 26
356.28kb.
Занятие №10 Фирма Методические указания к проведению практических работ по дисциплине «Экономическая теория» для студентов специальности «Менеджмент организации» и«Управление персоналом»
332.68kb.