Общая формулировка транспортной задачи

Пусть имеется m-пунктов производства с объемом производства а_i (i=1,m) и n пунктов потребления с объемом потребления b_j (j=1,n). Сбалансированной моделью называется транспортная задачи, в которой

          S_i=1 ^m a_i= S _j=1ⁿ b_j

(Сколько произвели, столько и продали). Стоимость транспортировки C_ij, тогда задача заключается в нахождении таких X_ij, которые удовлетворяют следующим соотношениям:

         S_j=1ⁿX_ij=a_i>0  (i=1,m)

         S_i=1^mX_ij=b_j    (j=1,n)

Необходимо минимизировать функцию

                C=S_i=1^mS_j=1ⁿC_ijX_ij

Так как выполняются условия

  S_i=1^ma_i=S_i=1^mS_j=1ⁿX_ij=S_j=1ⁿS_i=1^mX_ij=S_j=1ⁿb_j, то имеется (m+n-1) ограничений, следовательно (m+n-1) базисных переменных. Если задача не сбалансирована, то для приведения ее к стандартному виду вводят фиктивные пункты производства или потребления, стоимость перевозки на которые полагается равной нулю. Решение транспортной задачи похоже на симплекс-метод.

Шаги:

1)нахождение начального допустимого решения

2)выделение из числа небазисных переменных новой, вводимой в базис переменной

3)выбор выводимой из базиса переменной с нахождением нового базисного решения и переходом на шаг 2.

Для шага 1 применяют три метода:

1.правило северо-западного угла

2.метод минимальной стоимости

3.метод Фогеля.

1 метод- начинают решение с левого верхнего элемента.

2 метод- выбирают переменную, которой соответствует наименьшая стоимость (самая дешевая продукция реализуется первой).

3 метод основан на понятии штрафа для каждой строки.

Шага 2 делается с помощью метода потенциалов.

Пример: Рассмотрим 2 склада и 2 магазина.

Ограничения на неотрицательность

x₁₁>=0,x₁₂>=0,x₂₁>=0,x₂₂>=0

x₁₁+x₁₂=a₁       a_i- количество грузов у поставщика i

x₂₁+x₂₂=a₂       b_i-количество  грузов, необходимое

x₁₁+x₁₂=b₁       потребителю j

x₁₂+x₂₂=b₂

Стоимость перевозки C_ij

Z=C₁₁+x₁₁+C₁₂x₁₂+C₂₁x₂₁+C₂₂x₂₂

a₁+a₂=b₁+b₂- модель сбалансирована

Алгоритм решения задачи

(вещ Z, вещтаб C[1:2,1:2],X[1:2,1:2],A[1:2},B[1:2],лит y)

арг C,A,B

рез X,Y,Z

начало вещ v1,v2,v3,v4,x

v1=-b(1)+A(2)

v2=c(1,1)+C(2,2)-C(2,1)-C(1,2)

v3=c(1,2)*A(1)+C(2,1)*B(1)+C(2,2)*v1

если A(1)<B(1) то v4=A(1) иначе v4=B(1) все

если v2<=0 то если V4+v1>=0 то v4=v1 все все

если v2<>0 то y="решение одно" иначе y="решений много" все

если v2>0 то x=0;Z=v3 иначе h=v4;Z=v3+v2*v4 все

X(1,1)=x;X(1,2)=A(1)-x;X(2,1)=B(1)-x;X(2,2)=A(2)-B(1)+x

конец