Транспортная задача с промежуточными пунктами ( в сетевой постановке)
В матричной транспортной задаче перевозки осуществляются из пунктов производства только к пунктам потребления. Перевозки между пунктами производства или между пунктами потребления в ней не рассматриваются. Однако на практике перевозки могут осуществляться и через несколько промежуточных пунктов.
Поэтому разработана транспортная модель, в которой допускаются перевозки через промежуточные пункты. В этой модели для каждого пункта составляется уравнение материального отношения с учётом завоза (вывоза) и потребления (производства). Алгоритм решения задачи в сетевой постановке существенно не отличается от задачи в матричной постановке.
§ 1. Математическая постановка
Дано: пунктов (производства, потребления и промежуточных) или вершин. В каждом пункте объём производства равен Qi ( i = 1, …, N );
Для пунктов производства Qi > 0;
Для пунктов потребления Qi < 0;
Для промежуточных пунктов Qi = 0;
r – участков сети (дуг), каждый участок s ( s = 1,…, r ) связывает пункт производства is с пунктом потребления js;
(Cs ) – матрица себестоимости перевозки единицы груза по s –тому участку (s = 1,…,r).
Считается, что можно по каждому участку осуществлять перевозки из is в js в одном направлении. Если перевозки допускаются в двух направлениях, то каждый участок фигурирует дважды.
Требуется: определить план P = ( X1, X2, …, Xr ), показывающий объём перевозок по каждому участку сети.
Уравнение материального баланса для каждого j-го пункта выражает то обстоятельство, что объём вывезенного груза минус объём завезённого груза равен «чистому» объёму груза, произведённого в этом пункте (если разность положительна), или «чистому» объёму потребления (если разность отрицательна).
∑ I ≠ j Xij + Qj* = ∑ k ≠ j Xjk + Vj * = Xjj *
Где:
Xij – общий объём перевозок из i в j для i ≠ j;
Xjj * - суммарный объём поставки в j;
Qj * - объём производства в пункте j;
Vj * - объём потребления в пункте j.
«Чистый» объём производства Qj и потребления Vj выражаются через Qj* и Vj* следующим образом:
Qj = Qj* - min (Qj* , Vj* );
Vj = Vj* - min (Vj* , Vj* ).
1) Xs ≥ 0 (s = 1, …, r);
2) ∑sj Xs - ∑si Xs = | Qi | (s = 1, …, r);
По каждому i –му пункту, отправляющему данный груз, разность между суммой пустот на всех выходах из него и суммой пустот на всех подходах к нему равна ресурсам груза, подлежащим отправлению из пункта i.
Транспортная задача в сетевой форме впервые была поставлена советскими экономистами в 1929 – 30 гг., но точной математической формулировки она тогда ещё не получила.
Условия допустимости плана:
1) Xs ≥ 0 (перевозки не отрицательны);
2) ∑I ≠ j Xij - Xjj = Vj
(общее количество направляемого в пункт j груза минус объём транзитного груза равно «чистому» потреблению);
3) ∑k ≠ j Xjk - Xjj = Qj
(общее количество вывезенного из j груза минус объём транзитного груза равно «чистому» производству).
R
Допустимый план является оптимальным, если ∑ s = i Cs Xs - минимальна ( т.е. суммарные затраты минимальны).