Question

Пусть задана транспортная задача, в которой т пунктов отправления (складов) с объемами ai (i=l,…,m) и п пунктов потребления с объемами bj (j=l,…,n), стоимость перевозки единицы груза от i-го поставщика j-му потребителю равна сij , а объемы поставок обозначены хij . Выберите формулу для вычисления общей стоимости транспортировки груза ( Z=? ).​

Answer 1

Пошаговое объяснение:

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

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

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

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

определим значение сij стоимости прохождения единицы потока по дуге.

Транспортная модель может рассматриваться как задача наиболее

экономичного распределения потока по дугам транспортной сети.

Если в сети выделен источник sV и сток t V , то задачу поиска

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

v по сети, формально можно представить в виде

cijxij  min, (1.1)

при условиях











 





   

, ,

0, , ,

, ,

v i t

i s t

v i s

x x

j

ji

j

ij (1.2)

ij dij 0  x  . (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) и условию

i

j

ji

j

ij x x  s , i V . (1.4)

Результирующий “чистый” поток, протекающий через узел 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 , полагаем равными j

s , дуг (j,t),

j T – (– j

s ). Условия (1.4) определяют тогда поток максимальной величины

из источника в сток и задача (1.1), (1.3), (1.4) становится полностью идентичной