Математическая постановка

ТРАНСПОРТНАЯ ЗАДАЧА С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

(В СЕТЕВОЙ ПОСТАНОВКЕ)

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

Поэтому разработана транспортная модель, в которой допускаются перевозки через промежуточные пункты. В этой модели для каждого пункта составляется уравнение материального отношения с учётом завоза (вывоза) и потребления (производства). Алгоритм решения задачи в сетевой постановке существенно не отличается от задачи в матричной постановке.

 

Математическая постановка

Дано: пунктов (производства, потребления и промежуточных) или вершин. В каждом пункте объём производства равен Q_i (i = 1, …, N);

Для пунктов производства Q_i > 0;

Для пунктов потребления Q_i < 0;

Для промежуточных пунктов Q_i = 0;

r – участков сети (дуг), каждый участок s (s = 1,…, r) связывает пункт производства is с пунктом потребления js;

(C_s) – матрица себестоимости перевозки единицы груза по s –тому участку (s = 1,…,r).

Считается, что можно по каждому участку осуществлять перевозки из is в js в одном направлении. Если перевозки допускаются в двух направлениях, то каждый участок фигурирует дважды.

Требуется:определить план P = (X₁, X₂, …, X_r), показывающий объём перевозок по каждому участку сети.

Уравнение материального баланса для каждого j-го пункта выражает то обстоятельство, что объём вывезенного груза минус объём завезённого груза равен «чистому» объёму груза, произведённого в этом пункте (если разность положительна), или «чистому» объёму потребления (если разность отрицательна).

∑ _{I ≠ j} X_ij + Q_j* = ∑ _{k ≠ j} X_jk + V_j * = X_jj *

Где:

X_ij – общий объём перевозок из i в j для i ≠ j;

X_jj * - суммарный объём поставки в j;

Q_j * - объём производства в пункте j;