Методическое пособие по проведению практических занятий для студентов экономического факультета icon

Методическое пособие по проведению практических занятий для студентов экономического факультета




НазваниеМетодическое пособие по проведению практических занятий для студентов экономического факультета
Дата24.02.2014
Размер176.74 Kb.
ТипМетодическое пособие


Министерство образования Российской Федерации


Прикамский социальный институт


ЛОГИСТИКА



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

для студентов экономического факультета


Специальность 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





Похожие:

Методическое пособие по проведению практических занятий для студентов экономического факультета iconМетодическое пособие для преподавателей и студентов экономического факультета сгпу. Составители
Общие положения об организации учебных и преддипломной(производственной) практике
Методическое пособие по проведению практических занятий для студентов экономического факультета iconМетодическое пособие для студентов непсихологических факультетов Уфа 2010 Цели и задачи практики по психологии
Данное методическое пособие состоит из трех разделов
Методическое пособие по проведению практических занятий для студентов экономического факультета iconУчебно-методическое пособие для 4 курса ро озо филологического факультета Махачкала ипц дгу 2 0 0 3
Практическую подготовку студенты получают на практических и лабораторных занятиях и во время педагогической практики
Методическое пособие по проведению практических занятий для студентов экономического факультета iconУчебно-методическое пособие Рекомендовано методической комиссией механико-математического факультета для студентов высших
Г 71 Горяченко В. Д., Пригоровский А. Л., Сандалов В. М. Задачи по теории колебаний, устойчивости движения и качественной теории...
Методическое пособие по проведению практических занятий для студентов экономического факультета iconТемы практических занятий по дисциплине «Экономика и социология труда» для студентов дневного отделения экономического факультета специальности «Управление персоналом»
Социология труда как элемент общей системы знания о труде, ее место в системе наук, анализирующих труд социологического и несоциологического...
Методическое пособие по проведению практических занятий для студентов экономического факультета iconУчебно-методическое пособие для студентов, обучающихся по специальности «Информатика»
Учебно-методическое пособие предназначено для студентов, обучающихся по специальности «информатика», а также может использоваться...
Методическое пособие по проведению практических занятий для студентов экономического факультета iconМетодические указания по проведению практических занятий, самостоятельных работ студентов

Методическое пособие по проведению практических занятий для студентов экономического факультета iconМетодическое пособие для изучения раздела «структура экологического менеджмента на предприятии» дисциплины «менеджмент и маркетинг в экологии»
Методическое пособие предназначено для студентов-бакалавров, обучающихся по направлению 511100 «Экология и природопользование», а...
Методическое пособие по проведению практических занятий для студентов экономического факультета iconМетодическое пособие к специальному курсу лекций
В методическом пособии кратко излагается содержание специального курса лекций для студентов исторического факультета Томского государственного...
Методическое пособие по проведению практических занятий для студентов экономического факультета iconСборник задач по курсу основы программирования часть 1 Учебно-методическое пособие для студентов
Бабенко Т. А., Бельченко В. Е., Козырева Г. Ф. Сборник задач по курсу "Основы программирования": Учебно-методическое пособие для...
Разместите ссылку на наш сайт:
Занятия


База данных защищена авторским правом ©zanny.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
контакты