АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Транспортная модель

Читайте также:
  1. II. Учебно-информационная модель
  2. III. Изучение демократического транзита в России (модель Б.А. Исаева)
  3. Sog Pentagon, новая модель
  4. Американская модель общества угрожает Европе
  5. Американская модель управления.
  6. Базовая модель Солоу
  7. Визначення рівноважного ВВП за методом “вилучення–ін’єкції”. Модель “заощадження-інвестиції”.
  8. Влияние периодичности решетки на электронные состояния. Зонная модель
  9. Вопрос 17. Модель «матрица»: характеристика, достоинства и недостатки
  10. Вплив держави на економічну рівновагу. Модель економічної рівноваги за методом “витрати-випуск” для змішаної закритої економіки.
  11. Голографическая модель
  12. Даталогічна модель

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

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

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

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

Постановка задачи и ее математическая модель. Некоторый однородный продукт, сосредоточенный у т поставщиков в количестве (), необходимо доставить п потребителям в количестве (). Известно стоимость перевозки единицы груза от го поставщика му потребителю. Необходимо составить план перевозок, имеющий минимальную стоимость. Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции. Модель транспортной задачи представлена на рис 7.1.

 
 
 
 
m
n

 

Рис. 7.1. Транспортная модель

 

На рис. 7. 1. изображена транспортная модель в виде сети с т поставщиками некоторого однородного груза и п потребителями этого груза. При этом поставщикам груза и потребителям соответствуют вершины сети. Дуга, соединяющая поставщик груза с потребителем, представляет условный маршрут, по которому перевозится продукция. Количество продукции, производимой поставщиком , обозначено через , а количество продукции, потребляемой потребителем через ; стоимость перевозки единицы продукции из в .

Запишем математическую модель задачи:

1) Объем поставок го поставщика должен равняться ко­личеству имеющегося у него груза:

, (88)

2) Объем поставок му потребителю должен быть равен его спросу:

, (89)

3) Запас груза у поставщиков должен равняться суммарно­му спросу потребителей:

, (90)

4) Размер поставок должен выражаться неотрицательным числом:

;(7.4).

5) общая сумма затрат на перевозку груза должна быть минимальной:

(91)

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

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

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

В случае превышения запас продукции над потребностью, т. е. если , вводится фиктивный (n+1) – й потребитель с потребностью

(91)

 

а соответствующие стоимости перевозок считаются равными нулю. Аналогично, при , вводится фиктивный (m+1) – й поставщик с запасом груза а соответствующие стоимости перевозок считаются равными нулю. Этими действиями задача сводится к сбалансированной транспортной задаче, из оптимального плана которой, получается оптимальный план исходной задачи.

Модель транспортной задачи представляет собой задачу линейного прогпаммирования и, етественно, ее можно решать с использованием метода последовательного улучшения плана или методом использованием метода последовательного улучшения оценок (симплексным методом). Но в этом случае основная трудность связана с числом переменных задачи . Поэтому специальные алгоритмы, например, такие как метод потенциалов и венгерский метод, оказываются более эффективными.

Алгоритм метода потенциалов, (его называют еще модифицированным распределительным алгоритмом) начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла или метод минимального элемента. На конкретной задаче рассмотрим метод северо-западного угла. Он позволяет найти некоторый допустимый план перевозок.

Задача. На трех складах () имеется соответственно 140, 180 и 160 единиц однородного груза. Этот груз требуется перевести к пяти потребителям () соответственно в количествах 60, 70, 120, 130, 100 единиц. Стоимость перевозки от складов к потребителям приведена в табл. 7.2. (в правом верхнем углу каждой клетки). Например, сто­имость перевозки единицы груза со склада потребителю равна 2 у. е.

Таблица 7.2

Исходные данные для решения транспортной задачи

Поставщики Потребители Запасы продукции
 
 
 
Потребности            

 

Найти допустимый план перевозок.

Для решения задачи на первом этапе составляется система огра­ничений и целевая функция. Система ограничений в общем виде (для задачи) имеет вид:

 

причем для

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

= 2 + 3 +4. + 2 + 4 + 2 , (92)

Далее перераспределяются объемы поставок грузов методом «северо-западного угла», т.е. первой заполняется верхняя левая (севе­ро-западная) клетка исходной таблицы. Примем объем перевозки со склада к потребителю максимально возможным из условий задачи и равным 60 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу «» в табл.7.3 можно исключить из даль­нейшего рассмотрения.

В таблице 7.3. найдем «северо-западный угол» (теперь это клетка )и укажем максимально возможное значение. Оно рассчитывает­ся следующим образом: со склада уже перевезено 60 ед. груза, поэто­му остаток на этом складе составляет 80 ед. (140—60). Вносим в клетку вместо значение, равное 70 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу «» в табл. 7.3. можно исключить из даль­нейшего рассмотрения. Остаток продукции на складе 10 ед. (140 – 60 – 70) припишем потребителю .Таким образом, весь груз со скла­да перевезен потребителям и первая строка табл. 7.3 исключается из дальнейшего рассмотрения.

В нашей табл.7.3 найдем новый «северо-западный угол» (клетка )и укажем в нем максимально воз­можное значение это 110 ед. (120 – 10). Остаток продукции на складе 70 ед. (180 – 110) припишем потребителю . Тем самим потребитель полностью удовлетворил свою потребность, и поэтому графу «» в табл. 7.3 можно исключить из даль­нейшего рассмотрения.

В оставшейся части табл. № найдем новый «северо-западный угол» (клетка ) и укажем в нем максимально воз­можное значение это 60 ед. (130 – 70). Остаток продукции на складе в количестве 100 ед. припишем потребителю .

Результаты проведенных операций сведены в табл. 7.3.

 

Таблица 7.3

Распределение поставок

Поставщики Потребители Запасы продукции
      2  
     
     
Потребности            

 

В результате получили опорный план (семь занятых клеток).

.

 

В результате дальнейших вычислений мы получим оптимальное минимальное значение целевой функции. Расчеты громоздки, но лег­ко реализуются с использованием компьютерных программ.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.)