Vj *- объём потребления в пункте j.

«Чистый» объём производства Q_j и потребления V_j выражаются через Q_j* и V_j* следующим образом:

Q_j = Q_j* - min (Q_j*, V_j*);

V_j = V_j* - min (V_j*, V_j*).

1) X_s ≥ 0 (s = 1, …, r);

2) ∑_sj X_s - ∑_si X_s = | Q_i ‌ ‌| (s = 1, …, r);

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

Транспортная задача в сетевой форме впервые была поставлена советскими экономистами в 1929 – 30 гг., но точной математической формулировки она тогда ещё не получила.

 

Условия допустимости плана:

1) X_s ≥ 0 (перевозки не отрицательны);

2) ∑_{I ≠ j} X_ij - X_jj = V_j

(общее количество направляемого в пункт j груза минус объём транзитного груза равно «чистому» потреблению);

3) ∑_{k ≠ j} X_jk - X_jj = Q_j

(общее количество вывезенного из j груза минус объём транзитного груза равно «чистому» производству).

R

Допустимый план является оптимальным, если ∑ _{s = i} C_s X_s - минимальна (т.е. суммарные затраты минимальны).

§ 2. Критерий оптимальности плана

Для оптимальности допустимого плана необходимо и достаточно, чтобы существовали оценочные числа (потенциалы) а_1, а_2, …, а _n ,удовлетворяющие условиям:

а) а_js – а_is = C_s (s = 1, …, r) – для Х_s > 0, т.е. для участков, где существует перевозка;

б) а_js – а_is ≤ C_s - для Х_s = 0, т.е. для участков, где перевозка не осуществляется (разность потенциалов не превосходит затрат по перемещению единицы груза на данном участке).

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