The paper deals with the transportation problem in stochastic formulation. The problem solved by using the two-stage approach. The second stage is formulated as a complementarity problem. The algorithm for transportation problem solving is received. The solution based on stochastic gradient and Monte Carlo method.
It is important to consider the linear complementarity problem LCP(B; q) in the form [Bazaraa et al., 1998]: w − By = q; wj ≥ 0; yj ≥ 0; wj yj = 0; j = 1; :::; l:
Condition wj yj = 0; j = 1; :::; l; is similar to the condition of complementarity in the duality theory for inequalities By + q ≥ 0 and y ≥ 0. That means, in a pair of conjugate inequalities, at least one should be implanted as equality.
Non-negative definiteness of the matrix B ensures the solvability of problem LCP(B; q). When B is positive definite, problem LCP has a unique solution y of problem LCP(B; q).
The algorithm can be used as an additional conversion Lemke for the formulation of LCP problem solution [Bazaraa et al., 1998]. It can be shown as an analogy of the simplex algorithms for linear programming problem. 3
Let us consider the classical transportation problem: minimize the total cost for specified volumes of homogeneous product transportation X = {xij } i = 1; m; j = 1; n with restrictions: m n ∑∑cij xij → min i=1 j=1 n ∑xij = ai; i = 1; m; j=1 m ∑xij = bj ; j = 1; n; i=1 xij ≥ 0; i = 1; m; j = 1; n:
Conditions (2) determine the distribution of transportation X in accordance to reserves a = (a1; a2; : : : ; am): Conditions (3) ensure the fulfillment of the demand b = (b1; b2; : : : ; bn):
We introduce the matrix of the transportation plan X and matrices C by using vector of the transportation plan x and vector c, and sticking rows of matrix to vector
xij = x(i−1)n+j ; cij = c(i−1)n+j : cx → min; Ax = a; x ≥ 0; where matrix A corresponds to constraints (2). 4
It is important to consider the stochastic formulation of the transportation problem (1) – (4).
Let b = b(!) be the demand which presented as a random variable and c = c(!) be the cost of product transportation, which is also random.
Transportation problem with random demand can be presented as the following two-stage stochastic programming problem [Zykina et al., 2016]: where
F (x) = M {cx + f (x; b)} → xm∈iDn;
D = {x ∈ Rnm |Ax = a; x ≥ 0}; f (x; b) = {p+y+(x; b) + p−y−(x; b)} → y+; y
min ; w− − B−y− = q−; w− ≥ 0; y− ≥ 0; wj−yj− = 0; j ∈ J −: We show the following meaningful interpretation of the problem by using the terms of the transportation problem: – the components of vectors q+ or q− with coordinates and qj+ = m ∑ xij − bj ; j ∈ J +; i=1 qj− = bj − m ∑ xij ; j ∈ J −; i=1 that specify the amount of the deficit or excess of the resource that can occur with certain plan x ∈ D and in the realization of a random variable b;
– the components of vectors y+ = y+(x; b) or y− = y−(x; b) determine as the compensation plan of the deficit for each item of resource consumption;
– element bij of matrix B+ or B− specifies the amount of resource purchasing for i-th consumer under the compensation plan y = (0; :::; 1; :::; 0), where the positive unit located on j-th place; – the components of vectors p+ or p− determine fines for conducting corrective actions.
For the solvability of the second stage problem (7)–(9) for all implementations of a random variable b and for any preliminary plan x ∈ D, it is necessary and sufficient that the matrix B+ and B− be positive definite. Under such conditions there are a unique solutions y+(x; b) and y−(x; b) for each complementarity problem LCP(B+; q+) and LCP(B−; q−). In this case problem (5)–(9) is a nonlinear problem of stochastic programming with the following linear constraints in the form:
F (x) = M {cx + p+y+(x; b) + p−y−(x; b)} → xm∈iDn;
D = {x|Ax = a; x ≥ 0} ; here y+(x; b); y−(x; b) are unique solutions of the corresponding complementarity problems. The objective function F (x) is the expectation of a random function which depends on a random vector from a certain probability space. The feasible set D; D ̸= ∅; is a bounded convex linear set.
To solve the problem (10) – (11), we can use methods of stochastic approximation [Sakalauskas, 2004]. 5
h(i−1)n+j = Hij ; i = 1; m; j = 1; n:
Hij = h(i−1)n+j ; i = 1; m; j = 1; n: Problem LCP(B; q): qjs+(Xk) = m ∑xikj − bjs; j ∈ J s+; i=1 qjs−(Xk) = bjs − m ∑xikj ; j ∈ J s−: i=1 w − Bl×ly = q; wj ≥ 0; yj ≥ 0; wj yj = 0; j = 1; l: (9) (10) (11) (12) (13) (14) (15) (16) 6.1
Starting 1) Input: a matrix M C of dimension m × n which contains values of transport costs, a matrix DC of dimension m × n of variances, M b – vector with values of demand in points j = 1; n, Db – vector of variances, a – warehouse stock vector i = 1; m.
2) Let "ˆ, ˆ and be positive defined: "ˆ > 0, ˆ > 0 and > 0.
3) Define the matrix of corrective measures Bn×n, vectors p+ and p− (of dimension n) are fines for conducting corrective actions.
4) Select an initial volume N 0 of Monte Carlo estimates samples.
6) Find the initial approximation x0 ∈ Rnm as a solution of the linear programming problem: c¯x → min; Ax = a; x ≥ 0: (17) 7) Set k = 0 and turn to the main step. 6.2
Main Steps Step 1.
1. Let xk, N k and ∆k > 0 are given. Transform the vector xk into the matrix Xk by the rule (13). 2. Generate N k values of the random vector b: b1; b2; : : : ; bNk and the random matrix C: C1; C2; : : : ; CNk . 3. For each implementation s = 1; N k of a random vector b: (a) form the index sets J s+ and J s− from the elements j = 1; n according to the following rule: if then the corresponding index j is placed in the set J s+; if then the corresponding index j is placed in the set J s−; m ∑ xikj < bjs; i=1 m ∑ xikj > bjs; i=1 pjs+; j ∈ J s+; pjs−; j ∈ J s−; (b) form the matrix Bs+ by the elements of the matrix B at the intersection of rows and columns with numbers from the set J s+, and similarly form the matrix Bs− in terms of the index set J s−; (c) form vectors: (d) form the vectors qs+(Xk) and qs−(Xk) in accordance to (14) and (15) respectively; (e) for each t = 1; nm i. transform the vector (x1k; x2k; : : : ; xtk + ∆k; : : : ; xknm) into the matrix Xtk by the rule (13); ii. compute ys+(Xk; bs) as a solution of the complementarity problem LCP (Bs+; qs+(Xk)); iii. compute ys−(Xk; bs) as a solution of the complementarity problem LCP (Bs−; qs−(Xk)); iv. compute ys+(Xtk; bs) as a solution of the complementarity problem LCP (Bs+; qs+(Xtk)); v. compute ys−(Xtk; bs) as a solution of the complementarity problem LCP (Bs−; qs−(Xtk)); vi. calculate the coordinate t of the stochastic gradient gs(Xk; bs) according to the following formula: gts(Xk; bs) = c¯t + ps+ ys+(Xtk; bs) − ys+(Xk; bs) ∆k + ps− ys−(Xtk; bs) − ys−(Xk; bs)
; ∆k (f) calculate the values:
m n f (Xk; Cs; bs) = ∑ ∑ cisj xikj + ps+ys+(Xk; bs) + ps−ys−(Xk; bs);
i=1 j=1 4. after calculating all N k values of the objective function f (Xk; Cs; bs) and the stochastic gradients gs(Xk; bs) we find the following estimates:
Fe(Xk) = 1 N k
Nk ∑ f (Xk; Cs; bs); s=1 De 2(Xk) = 1 Nk
∑(f (Xk; Cs; bs) − Fe(Xk))2;
N k − 1 s=1 ∇e F (Xk) = 1 N k
Nk ∑ gs(Xk; bs); s=1 Q(Xk) = 1 N k
Nk ∑(gs(Xk; bs) − ∇e F (Xk))(gs(Xk; bs) − ∇eF (Xk))T s=1 7. determine Φ as – quantile of the Fisher distribution with degrees of freedom (N k − n; n). Determine as -quantile of the standard normal distribution; 8. if (N k − n)( ∇eF (Xk))T (Q(Xk))−1 ∇eF (Xk) ≤ Φ and 2 De(Xk) √ Nk ≤ then STOP. Otherwise go to step 2.
Step 2. 1. Calculate the value "xk ( ∇eF (Xk)) = "b∇e Ftm(Xakx)≥0;{min{xtk; b ∇e Ft(Xk)}}:
1≤t≤nm 2. Find the "−possible direction dk by solving the following problem:
dj ≤ 0; j ∈ J k; here J k is the set of indices j for which inequality is specified. 3. Compute k. If ∃t for which dtk > 0, then
else k = b:
and
∥d − ∇e F (Xk)∥ → min
Ad = 0; 0 ≤ xj ≤ "xk (∇e F (Xk)) k
xk k = min{b; dmtk>in0; ( dtkt )};
kdk N k+1 =
bΦ k(dk)T (Q(Xk))−1dk
: Convergence of the proposed algorithm provided [Sakalauskas, 2004] by determining the sample size from the conditions (18). In this case the objective function (10) must be differentiable. And it’s gradient must satisfy the Lipschitz condition. As mentioned above, when choosing the positive definite matrixs B+ and B− there is unique solutions y+(x; b) and y−(x; b) of the corresponding complementarity problem. In this case it is possible to obtain a linear dependence of the functions y+(x; b) and y−(x; b) [Kaneva, 2005]. This fact ensures differentiability of the objective function (10) and the Lipschitz condition for the gradient. 8
The effectiveness of the proposed numerical method for solving stochastic transportation problem stipulated by the following cases:
– We use two-step scheme where the choice of compensation plan of the second stage satisfy the conditions of the linear complementarity problem. This fact allows us compensate not only in the case when the demand is not satisfied, but when the supply exceed the demand. In addition, using the complementarity problem provides compensation on the limit of compatibility, which allows us to reduce costs of compensation.
– Under defined conditions of the compensation scheme choice (the positive definiteness of the matrix in the complementarity problem) ensures the uniqueness of the complementarity problem solution. This fact allows us use the solution of the complementarity problem to construct the stochastic gradient.
Acknowledgements This work was supported by Russian Foundation for Basic Research, Project 15-41-04436-a-Siberia and by
[Koopmans, 1949] Koopmans, T.C. (1949) Uptimum utilization of the transportation system. Econometrica, 3-4. [Williams, 1963] Williams, A. C. (1963). A stochastic transportation problem. Operations Research, 759 – 770. [Judin, 2010] Judin, D.B. (2010). Mathematical methods of control under incomplete information. Objectives and methods of stochastic programming. Moscow: Krasand.