J. Numer. Anal. Approx. Theory, vol. 46 (2017) no. 2, pp. 181–192 ictp.acad.ro/jnaat
A NUMERICAL COMPARISON BETWEEN TWO EXACT SIMPLICIAL METHODS FOR SOLVING A CAPACITATED 4-INDEX TRANSPORTATION PROBLEM
RACHID ZITOUNI∗and MOHAMED ACHACHE†
Abstract. In this paper, we deal with a numerical comparison between two ex- act simplicial methods for solving a capacitated four-index transportation prob- lem. The first method was developed by R. Zitouni and A. Keraghel for solving this problem [Resolution of a capacitated transportation problem with four sub- scripts, Kybernetes, Emerald journals, 32, 9/10: 1450-1463 (2003)]. The second approach is the well-known simplex method. We show across some obtained nu- merical results that the first algorithm competes well with the simplex method.
MSC 2010. 90C05, 90C08.
Keywords. Capacitated transportation problem, four-index transportation problem, linear programming, simplicial algorithms.
1. INTRODUCTION
The transportation problem is an important subject in real-world life that covers many important problems in economy, telecommunication and local- ization, among others. As a special case, the transportation problem with two-dimensional index has been extensively studied and solved by L. V. Kan- torovich and M. K. Gavurin (1949, [4]) and G. B. Dantzig (1951, [2]). Next, the study and the solution have been extended to transportation problems where the dimension of the index is higher than two. Since the sixties, several papers have been published for uncapacitated problems with a three-dimensional in- dex and a general multi-dimensional index, see for instance [3], [5], [6] and [7].
Recently, Zitouni [10], first introduced an algorithm for solving a capacitated transportation problem with 4-index (four subscripts). The choice for the index transportation problem allows us to getting an idea for the more general multi-dimensional transportation problem case.
∗Laboratoire de Math´ematiques Fondamentales et Num´eriques, Universit´e Ferhat Abbas- S´etif 1, S´etif, Alg´erie, e-mail: [email protected].
†Laboratoire de Math´ematiques Fondamentales et Num´eriques, Universit´e Ferhat Abbas- S´etif 1, S´etif, Alg´erie, e-mail: achache [email protected].
Our aim in this paper is to examine two exact simplicial methods for the solution of the capacited 4-index transportation problem, the method devel- oped in [10] and the simplex method. Because the algorithm developed in [10], tackles directly the problem, and shows its elegant computation and its rapidity convergence to provide a solution of this problem. For the comparison purpose, the obtained numerical results are compared with those obtained by the classical simplex approach applied to the reformulation of this problem as a linear program.
The outline of the paper is as follows. In Section 2, the 4-index capacited transportation problem formulation is stated. In section 3, the transporta- tion problem solution is given. In section 4, the detailed description of two exact simplicial algorithms and the convergence of the second algorithm are presented. In section 5, some computational results are reported, followed by an important numerical comparison between their performances. Finally, a conclusion and future researchers are drawn in the last section.
Some notation used throughout the paper is as follows. Rr denotes the space of r-dimensional real vectors whereas the set of all matrices with type (r1, r2) is denoted byRr1×r2. Ifx, z ∈Rr,then xTz denote their usual inner product. IfS ∈Rr1×r2, then its rank is defined as rank(S) =r ≤min(r1, r2).
2. THE CAPACITATED 4-INDEX TRANSPORTATION PROBLEM FORMULATION
The capacitated transportation problem with a four-dimensional index, de- noted by (T4C), is formulated as the following constrained optimization prob- lem:
(1) MinimizeZ =
m
X
i=1 n
X
j=1 p
X
k=1 q
X
l=1
cijklxijkl
subject to the constraints:
n
X
j=1 p
X
k=1 q
X
l=1
xijkl = αi for all i= 1, ..., m (2)
m
X
i=1 p
X
k=1 q
X
l=1
xijkl = βj for all j= 1, ..., n (3)
m
X
i=1 n
X
j=1 q
X
l=1
xijkl = γk for all k= 1, ..., p (4)
m
X
i=1 n
X
j=1 p
X
k=1
xijkl = δl for all l= 1, ..., q (5)
(6) 0≤xijkl ≤dijkl for all (i, j, k, l),
where αi,βj,γk,δl,dijkl and cijkl are given and such that for alli,j,k, and l,αi>0, βj >0, γk>0, δl>0, dijkl >0 andcijkl ≥0.
TheT4C problem can be also reformulated as the following linear program:
(7) min
x Z=cTx s.t. Ax=b,0≤x≤d, with
• x= (x1111, ..., xmnpq)T ∈RN,
• c= (c1111, ..., cmnpq)T ∈RN,
• d= (d1111, ..., dmnpq)T ∈RN,
• b= (α1, ..., αm, β1, ..., βn, γ1, ..., γp, δ1, ..., δq)T ∈RM,
• A∈RM×N, whereM =m+n+p+q and N =mnpq.
In this representation x = (x1111, x1211, ..., xmnpq) has been associated to a vector x ∈ RN. To do that, we associate to each (i, j, k, l) ∈ {1, .., m} × {1, .., n} × {1, .., p} × {1, .., q} a vector Pijkl ∈ RM. Only four entries of the vector Pijkl are nonzero, they are located on lines i, m+j, m+n+k and m+n+p+l, and their common value is 1. Note that Pijkl are the columns of A, they are called coefficients vectors.
In the sequel, we quote the following useful definitions (see [13]).
Definition 1. A feasible solution x of T4C is called basic solution if the columns of the sub-matrix Ax obtained from A by keeping only the columns corresponding to the variables xijkl such that
0< xijkl < dijkl
are linearly independent.
Definition 2. A basic feasible solution is said to be non degenerate if rank(Ax) = rank(A).
Definition 3. Given a basic feasible solution x = (xijkl), the 4-tuple (i, j, k, l) is called interesting if
0< xijkl< dijkl.
Throughout the paper, we assume that the following feasibility assumption forT4C,
(8)
m
X
i=1
αi =
n
X
j=1
βj =
p
X
k=1
γk=
q
X
l=1
δl=H holds.
As a consequence, it results that
rank(A) =M−3.
Unlike the transportation problem with two-dimensional index, the matrix Ais not totally unimodular since some of its minors do not belong to{−1,0,1}.
It is useful to present the data of the problem thanks to the following trans- portation table. It consists of an array of M rows and N columns, three additional rows and an additional column. The entries of these N columns of the first, second, and third additional rows are reserved for the data of the
quantitiesdijkl,cijkl, and xijkl, respectively. The additional column is for the data of quantities αi, βj, γk, and δl, respectively. Finally, the entry of the array on the line corresponding to αi0 and the columnPijklis 1 ifi=i0 and 0 otherwise. Same things forβj0,γ
k0, andδl0. We illustrate that by the following example.
d1111 .
d1211 .
... dmnpq
. c1111
.
c1211 .
... cmnpq
. x1111
.
x1211
.
... xmnpq
.
1 1 ... 0 α1 .
: : ... : :
0 0 ... 1 αm .
1 0 ... 0 β1 .
0 1 ... 0 β2 .
: : ... : :
0 0 ... 1 βn .
1 1 ... 0 γ1 .
: : ... : :
0 0 ... 1 γp .
1 1 ... 0 δ1 .
: : ... : :
0 0 ... 1 δq .
Table 1. T4C - Transportation table.
3. TRANSPORTATION PROBLEM SOLUTION
3.1. Feasibility conditions. We begin first to give a useful theorem that ensures the feasibility of T4C problem (see [13]).
Theorem 4. (Feasibility)
1. A necessary condition for the feasibility of the problem T4C i.e., it has a feasible solution if the condition (8) holds and the following conditions
(9)
αi≤ Pn
j=1 p
P
k=1 q
P
l=1
dijkl for i= 1, ..., m, βj ≤ Pm
i=1 p
P
k=1 q
P
l=1
dijkl for j= 1, ..., n, γk≤ Pm
i=1 n
P
j=1 q
P
l=1
dijkl for k= 1, ..., p, δl≤ Pm
i=1 n
P
j=1 p
P
k=1
dijkl for l= 1, ..., q,
are satisfied.
2. A sufficient condition for the feasibility of the problem T4C, i.e., it has a feasible solution if the condition (8) holds and the following conditions (10) αiβjγkδl
H3 ≤dijkl, for all(i, j, k, l) are satisfied.
Proof. 1. It is clear that if x= (xijkl) is a feasible solution for the problem T4C, then conditions (8) and (9) hold.
2. Assume thatx= (xijkl) is a vector ofRN such that xijkl= αiβjγkδl
dijkl , for all (i, j, k, l).
We can easily verify that x is a feasible solution for the problem T4C. Note that if the set of feasible solutions of the problem T4C is non empty, then it is a polytopes. Since the objective function is continuous, then the set of the solution of the problem T4C is non empty, i.e., there exists at least an optimal
solution of it.
3.2. Optimality conditions. In this subsection, we give a theorem that en- sures when a feasible solution, is an optimal solution of T4C.
Theorem 5. Assume that the problem T4C is feasible. Then a feasible solution x of T4C is optimal if and only if there exists a vector
y= (u1, . . . , um, v1, . . . , vn, w1, . . . , wp, t1, . . . , tq)T ∈RM such that:
ui+vj+wk+tl≤cijkl if xijkl = 0,
ui+vj+wk+tl=cijkl if 0< xijkl < dijkl, ui+vj+wk+tl≥cijkl if xijkl =dijkl.
Proof. For that, we consider the following formulation of the problemT4C:
(11) min
x [cTx: Ax=b,−x≥ −d, x≥0], and its dual problem is given by
(12) max
(y, z)[bTy−dTz:ATy−z≤c, z≥0].
Let (y, z) an optimal solution of the problem (12). Then a feasible solutionx of the problem (11) is optimal if and only if the two following complementarity conditions are satisfied
(13) (ATy−z−c)ijklxijkl = 0, and
(14) (d−x)ijklzijkl = 0.
• If xijkl = 0, then xijkl < dijkl and (14) imply zijkl = 0. So (ATy)ijkl≤cijkl.
• If 0< xijkl < dijkl then (14) implies zijkl = 0 and (13) leads to (ATy−z−c)ijkl= 0.So (ATy)ijkl=cijkl.
• If xijkl = dijkl then xijkl > 0 and (13) imply (ATy−z−c)ijkl = 0, consequently (ATy−c)ijkl=zijkl.Finally, we get (ATy)ijkl≥cijkl.
4. DESCRIPTION OF TWO SIMPLICIAL ALGORITHMS FORT4C
4.1. The simplex algorithm. In this subsection, in order to apply the tech- nical of the simplex algorithm for solving T4C problem, we need first to put T4C in the framework of a special linear program. The simplex algorithm, is referred to us as Algorithm 1. It is well-known that the problem T4C, according to (7), can be easily reformulated as the following linear program:
(15) min
ˆ
x Z = ˆcTxˆ s.t. ˆAˆx= ˆb,xˆ≥0,
in adding to the constraints those of the form: xijkl +yr = dijkl, (see (6) above), for i= 1, . . . , m, j = 1, . . . , n, k = 1, . . . , p, l= 1, . . . , q, r = 1, ..., N, where
• yr is the gap variable,
• xˆ= (xT, yT)T ∈R2N withy = (y1,. . . , yN)T,
• ˆc= (cT,0T)T ∈R2N where 0 is aN-null vector,
• ˆb= (bT, dT)T ∈RM+N,withdis the vector of N componentsdijkl.
• Aˆ=
A 0 IN IN
∈RM+N×2N with rank( ˆA) =M+N −3.
• IN ∈RN×N is the identity matrix.
4.2. Algorithm 2. According to the particularities of T4C problem, Zitouni [10], proposed a modification of the simplex algorithm. This algorithm is referred here as Algorithm 2, which shares with the simplex algorithm, a structure consists also of two phases such as the finite convergence and the use of the pivot principle. The advantage of this new algorithm is that it tackles the T4C directly without passing by other reformulations. For more comprehension of this new algorithm, we detail its fundamental ingredients (steps) as follows.
Phase 1. (It finds a basic feasible solution or declare that T4C is not solv- able)
Step 1:
Initialization: for all (i, j, k, l), αˆi = αi, βˆj = βj, γˆk = γk, ˆδl = δl and bijkl = 0, (bijkl is a boolean variable equal to 1 if xijkl has already been determined and 0 if not yet),
E={(i, j, k, l), such that bijkl= 0}.
Iteration:
WhileE is non empty do
• Choose an 4-tuple (¯i,¯j,k,¯ ¯l)∈E,such thatc¯i¯jk¯¯l= min
(i,j,k,l)∈Ecijkl, (see Remark 6)
• Take x¯i¯jk¯¯l = min( ˆα¯i,βˆ¯j,γˆ¯k,δˆ¯l, d¯i¯j¯k¯l), and b¯i¯j¯k¯l = 1, (i.e., x¯i¯j¯k¯l is determined),
• Update ˆα¯i,βˆ¯j,ˆγ¯k,and ˆδ¯l by the procedure (P1)below.
Step 2:
a)Determine ξ as shown in the procedure (P2) below.
Ifξ = 0,thenx= (xijkl) is aninitial basic feasible solution for the problemT4C,we denote it by x(0).Go to Phase 2.
Else,construct the problemT4C( ˜M) (as shown in the proce- dure (P3) below) and determine for it an initial basic feasible solution x(0) as in step 1 by taking x¯(0)m+1,n+1,p+1,q+1 = 0.
Note thatx(0) = (x(0)ijkl),withi= 1, . . . , m+ 1,j = 1, . . . , n+ 1, k= 1, . . . , p+ 1 and l= 1, . . . , q+ 1. If x(0) is optimal then the problemT4C is not solvable. Stop.
b) Improvement of a basic feasible solution for T4C( ˜M).
Initialization: r= 1, ξ >0is known, 1) Determinex(r) as in Phase 2.
2) If x¯(r)m+1,n+1,p+1,q+1 = ξ, then x(r) = (x(r)ijkl) with i = 1, . . . , m, j = 1, . . . , n, k = 1, . . . , p, and l = 1, . . . , q, is an initial basic feasible solutionfor the problem (T4C).Go to Phase 2.
3) If x(r) is optimal (Phase 2), then the problem T4C is not solvable. Stop. 4) Dor =r+ 1 and repeat 1), to 3).
Next, we describe the second phase.
Phase 2. (Research of an optimal solution for T4C)
When Phase 2 starts, we know an initial basic feasible solution x(0).Taker = 0.
a)Determine the setI(r)of the interesting 4-tuple (i, j, k, l), (see Remark 7).
b) For all (i, j, k, l)∈I(r), solve the linear system u(r)i +vj(r)+wk(r)+t(r)l =cijkl. c) For all (i, j, k, l)∈/ I(r) determine
4(r)ijkl =cijkl−(u(r)i +vj(r)+wk(r)+t(r)l ).
d)Apply the procedure described in (P4)below.
Ifthe optimality condition holds then thefeasible solution x(r) is optimal. stop.
Else determine a vector Pi0j0k0l0 entering at the base, it corresponds to4(r)i
0j0k0l0.
e)Construct a cycleµ(r)via the procedure described in (P5) and determine a new feasible solution as the procedure (P6) shows.
f) Do r = r+ 1 and repeat a), to e) until the optimality condition holds.
Remark 6. If there are several elements corresponding to the minimum of cijkl, we choose one, for instance the first found in the transportation table by
going from the left to the right.
Remark7. If the feasible solution is degenerate, i.e., the number of columns ofAx is strictly less than rank(A), we completeAx with additional columns so that we obtain a matrix having rank(A) linearly independent columns. Next I(r) can be determined. Thus will be done in the procedure(P7).
Also, the algorithm makes appeal to the following procedures.
(P1) - Updating of αˆ¯i,βˆ¯j,ˆγk¯, and δˆ¯l. 1) ˆα¯i = ˆα¯i−x¯i¯j¯k¯l,
if ˆα¯i = 0 then take x¯ijkl = 0 for all (j, k, l) 6= (¯j,k,¯ ¯l) and b¯ijkl= 1 for all (j, k, l),
2) ˆβ¯j = ˆβ¯j −x¯i¯jk¯¯l,
if ˆβ¯j = 0 then take xi¯jkl = 0 for all (i, k, l) 6= (¯i,k,¯ ¯l) and bi¯jkl= 1 for all (i, k, l),
3) ˆγ¯k= ˆγ¯k−x¯i¯j¯k¯l,
if ˆγ¯k = 0 then take xij¯kl = 0 for all (i, j, l) 6= (¯i,¯j,¯l) and bij¯kl= 1 for all (i, j, l),
4) ˆδ¯l= ˆδ¯l−x¯i¯j¯k¯l,
if ˆδ¯l = 0 then take xijk¯l = 0 for all (i, j, k) 6= (¯i,¯j,¯k) and bijk¯l= 1 for all (i, j, k).
(P2) - Determination of ξ. ξ = Pm
i=1
ai= Pn
j=1
bj =
p
P
k=1
ek =
q
P
l=1
fl, such that:
ai=αi− Pn
j=1 p
P
k=1 q
P
l=1
xijkl with i= 1, ..., m, bj =βj− Pm
i=1 p
P
k=1 q
P
l=1
xijkl with j= 1, ..., n, ek=γk− Pm
i=1 n
P
j=1 q
P
l=1
xijkl with k= 1, ..., p, fl=δl− Pm
i=1 n
P
j=1 p
P
k=1
xijkl with l= 1, ..., q.
Note that the numbersai, bj, ek and fl are nonnegative.
(P3) - Construction of the problem T4C( ˜M).
The problemT4C( ˜M) is obtained from problem T4C by adding four fictitious points with indicesm+ 1, n+ 1, p+ 1,andq+ 1 such that: cm+1,n+1,p+1,q+1 = 0,and cm+1,jkl =ci,n+1,kl = cij,p+1,l =cijk,q+1 = ˜M , where ˜M is a very large number and there are no limitation on the capacities for the paths involving a fictitious point.
(P4) - Determination of a vector Pi0j0k0l0 entering at the base or con- firming that the feasible solution x(r) is optimal.
Take Γ(r)0 and Γ(r)d as two tables such that Γ(r)0 =n4(r)ijkl such that x(r)ijkl= 0o, Γ(r)d =n4(r)ijkl such that x(r)ijkl=dijklo,
and elements 4(r)ijkl are represented as variables xijkl in the transportation table.
By going from the left to the right in Γ(r)0 ,choose 4(r)i
0j0k0l0 as the first element4(r)ijkl<0 found,
if all elements of Γ(r)0 are nonnegative then choose in Γ(r)d sim- ilarly,
4(r)i
0j0k0l0 as the first element4(r)ijkl>0 found.
If all elements of Γ(r)d are non positive, thenthe feasible so- lutionx(r) is optimal. Stop.
(P5) - Determination of a cycle.
A cycleµ(r) containing some interesting 4-tuple (i, j, k, l) and the non inter- esting 4-tuple (i0, j0, k0, l0) corresponding to4(r)i
0j0k0l0 is determined by solving the linear system P
(i,j,k,l)∈I(r)
α(r)ijklPijkl=−Pi0j0k0l0
The non null solutionsα(r)ijkl are called coefficients of the cycle µ(r). (P6) - Determination of a new feasible solution.
Take
σ(r)=n(i, j, k, l) such that (i, j, k, l) is a case of the cycle µ(r)o σ(r)−=n(i, j, k, l) such that (i, j, k, l)∈σ(r), withα(r)ijkl<0o σ(r)+=n(i, j, k, l) such that (i, j, k, l)∈σ(r), withα(r)ijkl>0o
If 4(r)i
0j0k0l0 ∈Γ(r)0 , determine θ(r)1 = min
(i,j,k,l)∈σ(r)−
x(r)ijkl.−α(r)ijkl, θ(r)2 = min
(i,j,k,l)∈σ(r)+
dijkl−x(r)ijkl.α(r)ijkl, θ(r) = min(θ1(r), θ2(r)).
Next, take
x(r+1)=nx(r)ijkl, (i, j, k, l)∈/ σ(r)o∪nx(r)ijkl +α(r)ijklθ(r), (i, j, k, l)∈σ(r)o. Else (4(r)i
0j0k0l0 ∈Γ(r)d ),determine θ(r)1 = min
(i,j,k,l)∈σ(r)+
x(r)ijkl.α(r)ijkl, θ(r)2 = min
(i,j,k,l)∈σ(r)−
dijkl−x(r)ijkl.−α(r)ijkl, θ(r)= min(θ1(r), θ(r)2 ).
Next, take
x(r+1)=nx(r)ijkl, (i, j, k, l)∈/ σ(r)o∪nx(r)ijkl −α(r)ijklθ(r), (i, j, k, l)∈σ(r)o. (P7) - Determination of a set I(r) in a degenerate case.
1. Take
• Eb the set of vectors corresponding to variablesx(r)ijkl verifying 0< x(r)ijkl < dijkl
andNb is its element number.
• Eh the set of vectors corresponding to variablesx(r)ijkl verifying x(r)ijkl= 0 or x(r)ijkl=dijkl
andNh is its element number. We areNh=N−Nb, withN =mnpq.
• Es any subset with s = rank(A)−Nb elements of Eh, for example the first s elements in Eh by going from the left to the right in the transportation table.
2. At the beginning of this procedure, we know a subset Es ofEh. i) Ifthe set(Es∪Eb) is a free base, then a setI(r)is determined.
Stop.
ii) Replace the first (the second, the third,..., or the sth) ele- ment inEs by the (s+ 1)th element in Eh, or take any other subset Es of Eh, and repeat i) until a set I(r) will be deter- mined. Stop.
4.3. The convergence of Algorithm 2. Assume that the problemT4C is non degenerate. Observe that ifx(r)andx(r+1)are two successive feasible solutions of the problem T4C with Z(r) and Z(r+1) are respectively the corresponding objective values then
Z(r+1)=Z(r)−(−1)ηθ(r)4(r+1)i
0j0k0l0
with
η=
1 if x(r)i
0j0k0l0 = 0, 0 if x(r)i
0j0k0l0 =di0j0k0l0. So Z(r+1)< Z(r).
Hence the Algorithm 2 guaranties that the same base never appear in two distinct iterations and since the number of the visited vertices is necessarily finite (at mostCNM−3), then it converges finitely.
5. COMPUTATIONAL RESULTS
The implementation of the two algorithms is running on a Pentium IV with a Microsoft Windows Environment, they are totally written with Borland Del- phi. Table 2 summarizes the results obtained for a few numerical experiments.
Ex. Dimension of Number Optimal Time in
no. the problem of iterations value (Z∗) seconds Alg. 1 Alg. 2 Alg. 1 Alg. 2 Alg. 1 Alg. 2
1 22×32 22 6 41.6025 41.6025 0.078 0.016
2 46×72 26 8 1317.79 1317.79 0.391 0.031
3 121×216 38 10 369.536 369.536 0.172 0.078
4 149×270 46 11 22.25 22.25 0.282 0.125
5 167×300 55 16 40 40 0.375 0.172
6 198×360 67 17 10.25 10.25 0.609 0.266
7 257×480 81 26 10.4375 10.4375 2.281 0.329
8 318×600 54 15 38.75 38.75 1.282 0.485
9 378×720 102 35 95.0625 95.0625 3.609 0.687 10 469×900 178 55 11.3125 11.3125 6.437 1.000 11 560×1080 257 83 46.25 46.25 10.438 1.406 12 741×1440 383 117 48.75 48.75 22.890 8.672
Table 2. Comparison between Algorithm 1 and Algorithm 2.
6. CONCLUSION AND FUTURE RESEARCHES
In this paper, we presented two exact simplicial methods for solving the ca- pacited 4-index transportation problem. The numerical experiments showed that Algorithm 2 is more efficient than Algorithm 1 with respect to the num- ber of iterations and also to the computational time. Moreover, as we have successfully done in some experiments, the arrangements made on Algorithm 2
have appropriately treated the degeneracy problems and led to a considerable reduction of the computational results.
Finally, we point out that our obtained results are independent of the num- ber of indices of the problem, so we can extend Algorithm 2 for solving ca- pacitated transportation problems with the number of indices that are greater than four.
REFERENCES
[1] G. B. Dantzig,Linear Programming and Extensions, Linear Programming and Exten- sions, 1963.
[2] G. B. Dantzig,Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation. Koopmans, T.C., Ed., John Wiley and Sons, New York, 1951.
[3] K. B. Haley,The multi-index transportation problem, Oper. Res.,11(1963), pp. 368–
379.
[4] L.V. Kantorovich andM.K. Gavurin,Application of mathematical methods to prob- lems of analysis of freight flows, Problems of raising the efficiency of transport perfor- mance, Moscow-Leningrad, (in Russian), 1949.
[5] M.K. Kravtsov,A Counter example to the Hypothesis of Maximum Number of Integer Vertices of the Multi-index Axial Transportation Polyhedron, Discrete Math. Appl., 10 (2000) no. 1, pp. 109–114.
[6] M.K. Kravtsov andE.V. Lukshin,On the non-integer polyhedron vertices of the three- index axial transportation problem, Autom. Remote Control,65(2004) no. 3, pp. 422–430.
[7] M. Queyranne and F. C. R. Spieksma, Approximation algorithms for multi-index transportation problems with decomposable costs, Discrete Appl. Math., 76 (1997), pp. 239–253.
[8] R.R.K. Sharma and Saumya Prasad, Obtaining a good primal solution to the un- capacitated transportation problem, European J. Oper. Res., 144 (2003), pp. 560–564.
[9] Tuyet-Hoa Pham and Philippe Dott, An exact method for solving the four index transportation problem and industrial application, American Journal of Operational Re- search,3(2013) no. 2, pp. 28–44.
[10] R. ZitouniandA. Keraghel,Resolution of a capacitated transportation problem with four subscripts, Kybernetes, (Emerald journals),32(2003) no. 9/10, pp. 1450–1463.
[11] R. Zitouni andA. Keraghel,A note on the algorithm of resolution of a capacitated transportation problem with four subscripts, Far East Journal of Mathematical Sciences (FJMS),26(2007) no. 3, pp. 769–778.
[12] R. Zitouni, A. Keraghel and D. Benterki, Elaboration and implementation of an algorithm solving a capacitated four-index transportation problem, Appl. Math. Sci.
(Ruse),1(2007) no. 53, pp. 2643–2657.
[13] R. Zitouni,Etude qualitative de mod`eles de transport et localisation, Th`ese de Doctorat d’´etat, Universit´e ferhat Abbas-S´etif 1, S´etif, Alg´erie. 2007.
Received by the editors: March 26, 2017.
