Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Транспортная задача. Транспортные модели описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт

⇐ Предыдущая48495051525354555657Следующая ⇒


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

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

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

Параметры задачи.

Имеется m пунктов производства А1, …, А m однородного продукта и n пунктов потребления В1,…, В n.

Предложение поставщика в каждом i -м пункте составляет аi единиц, i = 1,..., m.

Спрос потребителя в каждого j -ом пункте составляет bj единиц, j = 1,.... n.

Транспортные расходы на перевозку единицы продукции из А i в В j составляет cij (себестоимость, расстояние, тариф, время, расход топлива).

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

Обозначим xij – количество продукции, перевозимой от i -го поставщика j -му потребителю

i = 1,..., m, j = 1,.... n.

Математическая модель задачи

Суммарные затраты на транспортировку из всех пунктов производства во все пункты потребления:

тр

Управляющий параметр: xij ≥ 0 , - количество единиц продукции, поставляемой из А i в В j – перевозки из пунктов потребления в пункты производства исключены.

Ограничения

Суммарное предложение должно быть не меньше суммарного спроса

В каждый пункт потребления доставляется продукции не менее необходимой

,

От каждого поставщика вывозится продукции не более имеющейся

.

Всякое неотрицательное решение систем уравнений называется опорным планом (совокупность чисел xij, , , удовлетворяющая приведенным ограничениям). Решение X*=(xij ), при котором функция S принимает минимальное значение - называется оптимальным планом транспортной задачи.

Это общая задача линейного программирования – ограничения в виде неравенств (несбалансированная транспортная модель).

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

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

Замкнутая транспортная модель предполагает ограничения в виде равенств:

- сумма спроса равна сумме предложений;

- спрос каждого пункта потребления удовлетворяется полностью;

- весь продукт из каждого пункта производства должен быть вывезен.

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

На пересечении i -ой строки и j -го столбца стоит тариф с и сюда же заносится значение х ij – количество продукции, поставляемой от i -го поставщика j -му потребителю.

При большой размерности задачи (m x n) отыскание оптимального плана путем непосредственного перебора становится трудоемкой. Решение транспортной задачи состоит из двух этапов: нахождение начального плана, улучшение его и получение оптимального плана перевозок.

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

Для решения транспортной задачи составляется транспортная таблица.

Номер поставщика Номер потребителя Предло-жение
    ... j ... n
  c 11 x 11 c 12 x 12 ... c 1j x 1j ... c 1n x 1n a 1
  c 21 x 21 c 22 x 22 ... c 2j x 2j ... c 2n x 2n a 2
... ... ... ... ... ... ... ...
i c i1 x i1 c i2 x i2 ... c ij x ij ... c in x in a i
... ... ... ... ... ... ... ...
m c m1 x m1 c m2 x m2 ... c mj x mj ... c mn x mn a m
Спрос b 1 b 2 ... b j ... b n  

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

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

⇐ Предыдущая48495051525354555657Следующая ⇒


Дата публикования: 2014-11-04; Прочитано: 690 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...