1. общие свойства транспортных задач


Download 141.5 Kb.
bet1/2
Sana15.06.2023
Hajmi141.5 Kb.
#1481896
  1   2
Bog'liq
Математические модели логистике

1. ОБЩИЕ СВОЙСТВА ТРАНСПОРТНЫХ ЗАДАЧ



    1. Постановка задач

Пусть дана сеть (V, D), где V={1,…,n} – множество узлов, D – множество



дуг, пропускная способность дуги (i,j) равна
dij
 0 . Для каждой дуги (i,j)

определим значение сij стоимости прохождения единицы потока по дуге. Транспортная модель может рассматриваться как задача наиболее экономичного распределения потока по дугам транспортной сети.
Если в сети выделен источник s V и сток t V , то задачу поиска
дуговых потоков, минимизирующих стоимость прохождения потока величины
v по сети, формально можно представить в виде
cij xij  min, (1.1)

при условиях


v,




i s,

xij
j

  • x ji j

0,


v,
i s,t, i t,
(1.2)

0  xij dij . (1.3)
Задачу (1.1) – (1.3) обычно называют линейной сетевой задачей.
Обобщим задачу на случай нескольких источников и стоков. Пусть каждому узлу i сети сопоставлено некоторое число si, называемое
интенсивностью узла, и V S R T . Элементы множеств S, T и R называются
источниками, стоками и нейтральными узлами соответственно. Для всех i S
si>0, в узлах i T si<0, нейтральные узлы имеют нулевую интенсивность.
Потоком в такой сети называется совокупность определенных для всех дуг величин xij , удовлетворяющих (1.3) и условию

xij
j
x ji si , i V . (1.4)
j

Результирующий “чистый” поток, протекающий через узел i, вычисляется как разность выходящего и входящего потоков. Соотношение (1.4) означает, что для любого узла сети результирующий поток через узел равен его интенсивности.
Задача (1.1), (1.3), (1.4) называется сетевой транспортной задачей.
Очевидно, задача (1.1) – (1.3) – частный случай задачи (1.1), (1.3), (1.4). С другой стороны, сеть с несколькими источниками и стоками можно свести к сети с одним обобщенным источником s и одним обобщенным стоком t, вводя дополнительные дуги с нулевой стоимостью от s к источникам и от стоков к t.

Пропускные способности новых дуг (s,i),
i S , полагаем равными
s j , дуг (j,t),

j T – (– s j ). Условия (1.4) определяют тогда поток максимальной величины из источника в сток и задача (1.1), (1.3), (1.4) становится полностью идентичной

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

называется производственным,
ai si
интерпретируется как запасы или

производство некоторого продукта; величина
bi  si ,
i T , трактуется как

потребность в некотором продукте, а соответствующий пункт называется

пунктом потребления. Если
si  0 , то i – перевалочный пункт.

Для каждого звена сети известны стоимости
cij
перевозки единицы

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

План перевозок определяется заданием величины
xij
для каждого звена

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

ai , i S ,

(1.5)

 0 , i R ,

(1.6)

bi , i T .

(1.7)



xij x ji

j
xij
j
j

  • x ji j

x ji xij
j j
Ограничения (1.5) означают, что из пунктов отправления вывозится объем грузов, равный запасу в этом пункте. Ограничения (1.7) гарантируют доставку необходимого количества груза в каждый из пунктов назначения.
Благодаря указанной интерпретации транспортная задача и получила свое название. Транспортная модель применяется также для описания ситуаций, связанных с управлением запасами, составлением расписаний, управлением движением капиталов, назначением персонала и других. Задачу о максимальном потоке, например, можно рассматривать как частный случай задачи о потоке минимальной стоимости (1.1)–(1.3), в которой все дуговые стоимости равны нулю, а v совпадает с величиной максимального потока.

Download 141.5 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling