|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Транспортная модельТранспортная модель (транспортная задача) используют при рассмотрении различных практических ситуаций в логистическом управлении, связанных: с составлением наиболее экономичного плана перевозок продукции, управление запасами, назначением служащих на рабочее места, оборотом наличного капитала и многими другими. Кроме того, модель можно изменить, чтобы она учитывала перевозку нескольких видов продукции. В то же время транспортная модель и ее обобщение представляют собой частные случаи сетевых моделей. Транспортная задача по существу представляет собой задачу линейного программирования, которую можно решать симплекс – методом. Однако специфическая структура условий задачи позволяет использовать более эффективные вычислительные алгоритмы. Сущность транспортной задачи линейного программирования состоит в наивыгоднейшем прикреплении поставщиков однородного продукта ко многим потребителям этого продукта. На практике постоянно возникает необходимость решения таких задач, особенно когда количество пунктов отправления и получения грузов увеличивается. Условие транспортной задачи обычно записывается в виде матрицы, в которой потребители однородного груза размещаются по столбцам, а поставщики - по строкам. В последнем столбце матрицы проставляют запас груза, имеющийся у каждого поставщика, а в последней строке - потребность в нем потребителей. На пересечении строк со столбцами (в клетках матрицы) записывают размер поставки, а также расстояние пробега по всем возможным маршрутам время доставки груза или затраты на перевозку единицы груза по этим маршрутам. Постановка задачи и ее математическая модель. Некоторый однородный продукт, сосредоточенный у т поставщиков в количестве (), необходимо доставить п потребителям в количестве (). Известно стоимость перевозки единицы груза от го поставщика му потребителю. Необходимо составить план перевозок, имеющий минимальную стоимость. Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции. Модель транспортной задачи представлена на рис 7.1.
Рис. 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 Распределение поставок
В результате получили опорный план (семь занятых клеток). .
В результате дальнейших вычислений мы получим оптимальное минимальное значение целевой функции. Расчеты громоздки, но легко реализуются с использованием компьютерных программ.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |