The paper deals with the transportation logistics problems in the conditions of incomplete information. The research includes several formulations of the stochastic optimization problem for different variants of the relationship "Resources reserves - Resources consumption". For the solvability of these problems we propose two-stage scheme for solving stochastic transportation problem. The novelty of the two-stage problem stochastic programming formulation has been contained in the statement of the second stage problem. Choosing of compensation plan is determined from the solution of the linear complementarity problem. Transportation problem; two-stage stochastic problems; linear complementarity problem.
another word stochastic problem with compensation of residuals [7]. The process of solving the problem can be divided into two stages: on the first stage we select the preliminary plan from deterministic conditions, on the second stage we implement compensation discrepancies, that have been identified after the implementation of random events. This approach can be used for stochastic problems where a preliminary decision should be taken and put into the implementation before we have know the value of random parameters. For the transportation problem with random demand the preliminary decision can be determined by the distribution of materials supplies taking into account the determined reserves of the materials.
In general the difficulties with the analysis of the two-stage stochastic transport problems are determined by the need to choose the best preliminary plan of the original problem, which would guarantee the existence of residual compensation for all implementations of parameters of uncertainty.
In this paper a two-stage stochastic transport problem is considered, where the choice of compensation plan subjects to the terms which are determined by a linear complementarity problem. Statement of the Linear Complementarity Problem
It is important to consider the linear complementarity problem in the form [8]:
v Bz q, v j 0, z j 0, v j z j 0, j 1,..., p.
There B – given a square matrix with size р, (v j , z j ) – is a couple of additional variables. Condition vj z j 0, j 1,..., p, analogous to the condition of complementarity in the duality theory for inequalities Bz q 0 and z 0.This means that 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 (
For the solution building of problem (
It is necessary to consider the classical transport problem: minimize the total cost
m n for specified volumes of transportation of a homogeneous product X {xij }, i 1,...,m, j 1,...,n, with restrictions: cij xij i1 j1 n xij ai , i 1,...,m, j1 m xij bj , j 1,...,n, i1 xij 0, i 1,...,m, j 1,...,n.
Conditions (
Conditions (
It is necessary to introduce the vector representation of the transportation plan x and vector c with the matrix representation of the transportation plan X and matrices C , by sticking rows of matrix to vector in accordance with reserves xij x((i1)n j) , cij c((i1)n j).
Then a group of equations (
Two-stage StochasticTransport Problem
(
Let the demand b b( ) is a random variable. Also C C( ) – the cost of transportation of product is also random.
~
Define by bj , j 1,...,n
– some implication of a random variable
bj , using
~x , i 1,..., m, j 1,..., n, – a transportation plan that satisfies to the deterministic conditions (
Case 1. For some j J ,J 1,...,n following inequality holds:
Then there are two cases of the choice of compensation plan from the terms and conditions
determined by the linear problem of complementarity (
m ~ ~xij b j .
i1
Condition (
the demand is not satisfied.
For such constraintsit is necessary to introduce a penalty s j , j J for one unit of compensation plan of the product deficit and carry out compensation of obtained discrepancy as follows:
E ~x b~ M y .
Where E – is a matrix and b
correspond to set J , M – is positive definite matrix and y
– a vector which were composed by the restrictions (
Labeling
we will receive linear complementarity problem (
Case 2. For some j J , J 1,...,n the following inequality is satisfied z y , B M , q E ~x b~ , i1 m ~ ~ x b .
ij j
The condition (
For such constraints we introduce a penalty s j , j J excess product and hold compensation of obtained discrepancy by following:
E ~x b~ M y .
there is a need to store excess product.
for one unit of compensation plan Where E – is a matrix and b
correspond to set J , M – is positive definite matrix and y
– a vector which were composed by the restrictions (
By analogy in case 1, when
z y , B M , q E ~x b~ ,
we will receive linear complementarity problem (
Transportation problem with random demand can be presented as the following two-stage stochastic programming problem:
nm
M k1 ck xk ym ,iny (s y s y ) mxin (
j j
For the solvability of the second stage with all implementations of a random variable b and with any preliminary plan x it is necessary and sufficient that the matrix M and M was positive definite. Under such conditions, there is a unique solution y (x,b) and y (x,b) for each complementarity problem where y (x,b),
y (x,b) – solutions of the corresponding complementarity problems, the objective space, and the feasible set D x | Ax a, x 0 is a bounded and convex linear set. function is an expectation of a random function depending on a random vector from a certain probability
For solving the problem (14) – (15) can use the methods of stochastic approximation [9, 10].
Monte-Carlo estimators of the objective function and d projection of the gradient estimate to the -feasible set).
Step 2. Go to the next point
Let the initial approximation of the solution x0 D and some initial Monte-Carlo sample size N 0 be given. Put k 0 and move on to the main stage.
Step 1. Let the vector x is known. We generate N k values of a random variable b andcalculated k k k is an -feasible direction at the point x (i.e., xk 1 x ( xk k d k ).
N k 1 k d Where C is a certain constant k x k ( d k ) , d k projection of the gradient estimate to the -feasible set).
is an -feasible direction at the point x k (i.e., of the problem for the positive semi definite matrix M preliminary plan x .
The novelty of the two-stage schemes stochastic transportation problem formulation contains in the statement of the second stage problem. Two-stage scheme can be applied for solving the stochastic transportation problem in following case. Conditions (15) give the distribution of the known deterministic reserves. This is a preliminary plan. After the values of the random demand becomes known, we have a possibility of the occurring residuals.
On the first stage we look for a preliminary plan without taking into account the random parameters. On the second stage the residual vector is searched for correction. The residual is parameterized with using of a compensation matrix in new formulation which is proposed in the article,. Basically it allows us to interpret the correcting process of the residuals in the following way – with the emerging shortage of resources. An additional purchase is carried out without excess.
The construction of the linear complementarity problem (12) and (13) for the second stage in a new production of non-linear two-stage schemes stochastic transportation problem ensures the solvability and M under all implementations b and any
If matrix M and M is positive defined, then there is a unique solution of the linear complementarity problem (12) and (13) in all implementations of the uncertainty parameters and preliminary plan. This research was supported by the Russian Foundation for Basic Research (project no.15-41-04436).
Литература
Владимировна, заведующий кафедрой прикладной математики и фундаментальной Омского государственного технического университета, доктор физико-математических наук, профессор, avzykina@mail.ru;