# An Effective Generalization of the Direct Support Method

Authors: Sonia Radjef; Mohand Ouamer Bibi
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

The main objective of our paper is to solve a problem which was
encountered in an industrial firm. It concerns the conception of a weekly
production planning with the aim to optimize the quantities to be launched.
Indeed, one of the problems raised in that company could be modeled as a linear multiobjective program where the decision variables are of two kinds: the
first ones are upper and lower bounded, and the second ones are nonnegative.
During the resolution process of the multiobjective case, we were faced with the
necessity of developing an effective method to solve the mono-objective case
without any increase in the linear program size, since the industrial case to
solve is already very large. So, we propose an extension of the direct support
method presented in this paper. Its particularity is that it avoids the preliminary transformation of the decision variables. It handles the bounds as
they are initially formulated. The method is really effective, simple to use, and
permits  speeding up the resolution process.


---

## Body

## 1. Introduction

The company Ifri is one of the largest and most important Algerian companies in the agroalimentary field.Ifri products mainly mineral water and various drinks.From January to October of the year 2003, the company production was about 175 million bottles. Expressed in liters, the production in this last period has exceeded the 203 million liters of finishedproducts (all products included). Having covered the national market demand,Ifrileft to the acquisition of new international markets.The main objective of our application [1] is to conceive a data-processing application to carry out an optimal weekly production planning which will replace the planning based primarily on the good management and the experiment of the decision makers.This problem relates to the optimization problem of the quantities to launch in production. It is modeled as a linear multi-objective program where the objective functions involved are linear, the constraints are linear and the decision variables are of two kinds: the first ones are upper and lower bounded, and the second ones are nonnegative.Multicriteria optimization problems are a class of difficult optimization problems in which several different objective functions have to be considered at the same time. It is seldom the case that one single point will optimize all the several objective functions. Therefore, we search the so-calledefficient points, that is, feasible points having the property that no other feasible point improves all the criteria without deteriorating at least one.In [2], we developed a method to solve the multi-objective linear programming problem described above. To avoid the preliminary transformation of the constraints, hence the augmentation of the problem dimension, we propose to extend the direct support method of Gabasov et al. [3] known in single-objective programming.In [2], we proposed a procedure for finding an initial efficient extreme point, a procedure to test the efficiency of a nonbasic variable, and a method to compute all the efficient extreme points, the weakly efficient extreme points, and the ϵ-weakly efficient extreme points of the problem.A multiobjective linear program with the coexistence of the two types of the decision variables can be presented in the following canonical form:(1.1)Cx+Qy⟶max⁡,Ax+Hy=b,d-≤x≤d+,y≥0,
where C and Q are k×nx and k×ny matrices, respectively, A and H are matrices of order m×nx and m×ny, respectively, with rang(A∣H)=m<nx+ny, b∈ℝm, d-∈ℝnx, and d+∈ℝnx.We denote byS the set of feasible decisions: (1.2)S={(x,y)∈Rnx+ny,Ax+Hy=b,d-≤x≤d+,y≥0}.Definition 1.1.
A feasible decision(x0,y0)∈ℝnx+ny is said to be efficient (or Pareto optimal) for the problem (1.1), if there is no other feasible solution (x,y)∈S such that Cx+Qy≥Cx0+Qy0 and Cx+Qy≠Cx0+Qy0.Definition 1.2.
A feasible decision(x0,y0)∈ℝnx+ny is said to be weakly efficient (or Slater optimal) for the problem (1.1), if there is no other feasible solution (x,y)∈S such that Cx+Qy>Cx0+Qy0.Definition 1.3.
Letϵ∈ℝk, ϵ≥0. A feasible decision (xϵ,yϵ)∈S is said to be ϵ-weakly efficient for the problem (1.1), if there is no other feasible solution (x,y)∈S such that Cx+Qy-Cxϵ-Qyϵ>ϵ.The multiobjective linear programming consists of determining the whole set of all the efficient decisions, all weakly efficient decisions and allϵ-weakly efficient decisions of problem (1.1) for given C,Q,A,H,b,d-,andd+.During the resolution process, we need to use an efficiency test of nonbasic variables. This problem can be formulated as a single-objective linear program where the decision variables are of two types: upper and lower bounded variables and nonnegative variables. We propose in this paper to solve this latter problem by an adapted direct support method. Our approach is based on the principle of the methods developed by Gabasov et al.[3], which permit to solve a single-objective linear program with nonnegative decision variables or a single-objective linear program with bounded decision variables. Our work aims to propose a generalization for the single-objective linear program with the two types of decision variables: the upper and lower bounded variables and the nonnegative variables.This work is devoted to present this method. Its particularity is that it avoids the preliminary transformation of the decision variables. It handles the constraints of the problems such as they are initially formulated. The method is really effective, simple to use, and direct. It allows us to treat problems in a natural way and permits speeding up the whole resolution process. It generates an important gain in memory space and CPU time. Furthermore, the method integrates a suboptimal criterion which permits to stop the algorithm with a desired accuracy. To the best of our knowledge, no other linear programming method uses this criterion which could be useful in practical applications.The principle of this iterative method is simple: starting with an initial feasible solution and an initial support, each iteration consists of finding an ascent direction and a step along this direction to improve the value of the objective function without leaving the problem’s feasible space. The initial feasible solution and the initial support could be computed independently. In addition to this, the initial feasible point need not to be an extreme point such as in the simplex method. The details of our multiobjective method will be presented in our future works.


## 2. Statement of the Problem and Definitions

The canonical form of the program is as follows:(2.1)z(x,y)=ctx+kty⟶max⁡,(2.2)Ax+Hy=b,(2.3)d-≤x≤d+,(2.4)y≥0,
where c and x are nx-vectors, k and y are ny-vectors, b an m-vector, A=A(I,Jx) an m×nx-matrix, H=H(I,Jy) an m×ny-matrix, with rank(A∣H)=m<nx+ny; I={1,2,…,m},  Jx={1,2,…,nx},  Jy={nx+1,nx+2,…,nx+ny}.Let us setJ=Jx∪Jy, such that Jx=JxB∪JxN, Jy=JyB∪JyN, with JxB∩JxN=ϕ, JyB∩JyN=ϕ and |JxB|+|JyB|=m.We setJB=JxB∪JyB, JN=J∖JB=JxN∪JyN, and we note by AH the m×(nx+ny)-matrix (A∣H).Let the vectors and the matrices be partitioned in the following way:(2.5)x=x(Jx)=(xj,j∈Jx),y=y(Jy)=(yj,j∈Jy),x=(xBxN),xB=x(JxB)=(xj,j∈JxB),xN=x(JxN)=(xj,j∈JxN),y=(yByN),yB=y(JyB)=(yj,j∈JyB),yN=y(JyN)=(yj,j∈JyN),c=(cBcN),cB=c(JxB)=(cj,j∈JxB),cN=c(JxN)=(cj,j∈JxN),k=(kBkN),kB=k(JyB)=(kj,j∈JyB),kN=k(JyN)=(kj,j∈JyN),A=A(I,Jx)=(aij,1≤i≤m,1≤j≤nx)=(aj,j∈Jx)=(AB∣AN),AB=A(I,JxB),AN=A(I,JxN),ajisthejthcolumnofA,H=H(I,Jy)=(hij,1≤i≤m,nx+1≤j≤nx+ny)=(hj,j∈Jy)=(HB∣HN),HB=H(I,JyB),HN=H(I,JyN),hjisthejthcolumnofH,AH=AH(I,J)=(aHij,1≤i≤m,1≤j≤nx+ny)=(aHj,j∈Jx∪Jy)=(AHB∣AHN),AHB=AH(I,JxB∪JyB)=(AB∣HB),AHN=AH(I,JxN∪JyN)=(AN∣HN).Definition 2.1.
(i) A vector(x,y), satisfying the constraints (2.2)–(2.4), is called a feasible solution of the problem (2.1)–(2.4).
(ii) A feasible solution(x0,y0) is said to be optimal if z(x0,y0)=ctx0+kty0=max(ctx+kty), where (x,y) is taken among all the feasible solutions of the problem (2.1)–(2.4).
(iii) On the other hand, a feasible solution(xϵ,yϵ) is called  ϵ-optimal or suboptimal if
(2.6)z(x0,y0)-z(xϵ,yϵ)=ctx0-ctxϵ+kty0-ktyϵ≤ϵ,
where (x0,y0) is an optimal solution of the problem (2.1)–(2.4), and ϵ is a nonnegative number, fixed in advance.
(iv) The setJB=JxB∪JyB⊂J,|JB|=m is called a support if detAHB=det(AB,HB)≠0.
(v) A pair{(x,y),(JxB,JyB)}, formed by a feasible solution (x,y) and a support (JxB,JyB), is called a support feasible solution.
(vi) The support feasible solution is said to benondegenerate, if
(2.7)dj-<xj<dj+,foranyj∈JxB,yj>0,foranyj∈JyB.


## 3. Increment Formula of the Objective Function

Let{(x,y),(JxB,JyB)} be a support feasible solution for the problem (2.1)–(2.4), and let us consider any other feasible solution (x¯,y¯)=(x+Δx,y+Δy).We define two subsetsJyN+ and JyN0 of JyN as follows:
(3.1)JyN+={j∈JyN,yj>0},JyN0={j∈JyN,yj=0}.
The increment of the objective function is as follows:
(3.2)Δz=-((cBt,kBt)AHB-1AN-cNt)ΔxN-((cBt,kBt)AHB-1HN-kNt)ΔyN.The potential vectoru and the estimations vector E are defined by
(3.3)ut=(cBt,kBt)AHB-1,Et=(EBt,ENt),EBt=(ExBt,EyBt)=(0,0),ENt=(ExNt,EyNt),ExNt=utAN-cNt,EyNt=utHN-kNt.
Then, the increment formula presents the following final form:
(3.4)Δz=-ExNtΔxN-EyNtΔyN.


## 4. Optimality Criterion

Theorem 4.1.
Let{(x,y),(JxB,JyB)} be a support feasible solution for the problem (2.1)–(2.4). Then, the following relations
(4.1)Exj≥0,ifxj=dj-,j∈JxN,Exj≤0,ifxj=dj+,j∈JxN,Exj=0,ifdj-<xj<dj+,j∈JxN,Eyj≥0,ifyj=0,j∈JyN,Eyj=0,ifyj>0,j∈JyN,
are sufficient for the optimality of the feasible solution (x,y). They are also necessary if the support feasible solution is nondegenerate.Proof.
Sufficiency
Let{(x,y),(JxB,JyB)} be a support feasible solution satisfying the relations (4.1). For any feasible solution (x¯,y¯) of the problem (2.1)–(2.4), the increment formula (3.4) gives the following:
(4.2)Δz=-∑j∈JxNExj(x¯j-xj)-∑j∈JyN+Eyj(y¯j-yj)-∑j∈JyN0Eyj(y¯j-yj).
Sincedj-≤x¯j≤dj+, for all j∈Jx, and from the relations (4.1), we have
(4.3)-∑j∈JxNExj(x¯j-xj)=-∑j∈JxN,Exj>0Exj(x¯j-dj-)-∑j∈JxN,Exj<0Exj(x¯j-dj+)≤0.
On the other hand, the conditiony¯j≥0,forallj∈Jy, implies that
(4.4)-∑j∈JyN+Eyj(y¯j-yj)-∑j∈JyN0Eyj(y¯j-yj)=-∑j∈JyN0Eyjy¯j≤0.
Hence,
(4.5)Δz=z(x¯,y¯)-z(x,y)≤0,z(x¯,y¯)≤z(x,y).
The vector (x,y) is, consequently, an optimal solution of the problem (2.1)–(2.4).
Necessity
Let{(x,y),(JxB,JyB)} be a nondegenerate optimal support feasible solution of the problem (2.1)–(2.4) and assume that the relations (4.1) are not satisfied, that is, there exists at least one index j0∈JN=JxN∪JyN such that
(4.6)Exj0>0,forxj0>dj0-,j0∈JxN,or,Exj0<0,forxj0<dj0+,j0∈JxN,or,Eyj0<0,forj0∈JyN0,or,Eyj0≠0,forj0∈JyN+.
We construct another feasible solution (x¯,y¯)=(x+θlx,y+θly), where θ is a positive real number, and  (lxly)=(l(Jx)l(Jy))=l(J)=l is a direction vector, constructed as follows.
For this, two cases can arise:(i)
ifj0∈JxN, we set
(4.7)lxj0=-sign⁡Exj0,lxj=0,j≠j0,j∈JxN,lyj=0,j∈JyN,lB=(lxBlyB)=AHB-1aj0sign⁡Exj0,
where aj0 is the j0th column of the matrix A;(ii)
ifj0∈JyN, we set
(4.8)lyj0=-sign⁡Eyj0,lyj=0,j≠j0,j∈JyN,lxj=0,j∈JxN,lB=(lxBlyB)=AHB-1hj0sign⁡Eyj0,where hj0 is the j0th column of the matrix H. From the construction of the direction l, the vector (x¯,y¯) satisfies the principal constraint Ax¯+Hy¯=b.
In order to be a feasible solution of the problem (2.1)–(2.4), the vector (x¯,y¯) must in addition satisfy the inequalities d-≤x¯≤d+ and y¯≥0, or in its developed form
(4.9)dj--xj≤θlxj≤dj+-xj,j∈JxB,dj--xj≤θlxj≤dj+-xj,j∈JxN,θlyj≥-yj,j∈JyB,θlyj≥-yj,j∈JyN.
As the support feasible solution {(x,y),(JxB,JyB)} is nondegenerate, we can always find a small positive number θ such that the relations (4.9) are satisfied. Thus, for a small positive number θ, we can state that the vector (x¯,y¯) is a feasible solution for the problem (2.1)–(2.4). The increment formula gives in both cases
(4.10)z(x̅,y̅)-z(x,y)=θEj0sign⁡Ej0=θ|Ej0|>0,
where
(4.11)Ej0=Exj0ifj0∈JxNorEj0=Eyj0ifj0∈JyN.
Therefore, we have found another feasible solution (x¯,y¯)≠(x,y) with the inequality z(x¯,y¯)>z(x,y) which contradicts the optimality of the feasible solution (x,y). Hence the relations (4.1) are satisfied.


## 5. The Suboptimality Condition

In order to evaluate the difference between the optimal valuez(x0,y0) and another value z(x,y) for any support feasible solution {(x,y),(JxB,JyB)}, when Ey≥0, we use the following formula:
(5.1)β((x,y),(JxB,JyB))=∑j∈JxNExj>0Exj(xj-dj-)+∑j∈JxNExj<0Exj(xj-dj+)+∑j∈JyNEyjyj,
which is called the suboptimality condition.Theorem 5.1 (the suboptimality condition).
Let{(x,y),(JxB,JyB)} be a support feasible solution of the problem (2.1)–(2.4) and ϵ an arbitrary nonnegative number.
IfEy≥0 and
(5.2)∑j∈JxNExj>0Exj(xj-dj-)+∑j∈JxNExj<0Exj(xj-dj+)+∑j∈JyNEyjyj≤ϵ,
then the feasible solution (x,y) is  ϵ-optimal.Proof.
We have(5.3)z(x0,y0)-z(x,y)≤β((x,y),(JxB,JyB)).
Then, if
(5.4)β((x,y),(JxB,JyB))≤ϵ,
we will have
(5.5)z(x0,y0)-z(x,y)≤ϵ,
therefore, (x,y) is ϵ-optimal.
In the particular case whereϵ=0, the feasible solution (x,y) is consequently optimal.


## 6. Construction of the Algorithm

Given any nonnegative real numberϵ and an initial support feasible solution {(x,y),(JxB,JyB)}, the aim of the algorithm is to construct an ϵ-optimal solution (xϵ,yϵ) or an optimal solution (x0,y0). An iteration of the algorithm consists of moving from {(x,y),(JxB,JyB)} to another support feasible solution {(x¯,y¯),(J¯xB,J¯yB)}  such that z(x¯,y¯)≥z(x,y). For this purpose, we construct the new feasible solution (x¯,y¯) as follows: (x¯,y¯)=(x,y)+θ(lx,ly), where l=(lx,ly) is the appropriate direction, and θ is the step along this direction.In this algorithm, the simplex metric is chosen. We will thus vary only one component among those which do not satisfy the relations (4.1).In order to obtain a maximal increment, we must takeθ as great as possible and choose the subscript j0 such that
(6.1)|Ej0|=max⁡(|Exj0|,|Eyj0|),
with
(6.2)|Exj0|=max⁡(|Exj|,j∈JxNNO),|Eyj0|=max⁡(|Eyj|,j∈JyNNO),
where JxNNO and JyNNO are the subsets, respectively, of JxN and JyN, whose the subscripts do not satisfy the relations of optimality (4.1).


### 6.1. Computation of the Directionl

We have two cases.(i)
If|Ej0|=|Exj0|, we set:
(6.3)lxj0=-sign⁡Exj0,lxj=0,j≠j0,j∈JxN,lyj=0,j∈JyN,lB=(lxBlyB)=AHB-1aj0sign⁡Exj0.(ii)
If|Ej0|=|Eyj0|, we will set
(6.4)lyj0=-sign⁡Eyj0,lyj=0,j≠j0,j∈JyN,lxj=0,j∈JxN,lB=(lxBlyB)=AHB-1hj0sign⁡Eyj0.


### 6.2. Computation of the Stepθ

The stepθ0 must be taken as follows:
(6.5)θ0=min⁡(θx,θy).(i)
If|Ej0|=|Exj0|, then θx=min(θxj0,θxj1), where
(6.6)θxj0={dj0+-xj0,ifExj0<0,xj0-dj0-,ifExj0>0,θxj1=min⁡(θxj,j∈JxB),
with
(6.7)θxj={dj+-xjlxj,iflxj>0,dj--xjlxj,iflxj<0,∞,iflxj=0.
The number θy will be computed in the following way:
(6.8)θy=θyj1=min⁡(θyj,j∈JyB),
where
(6.9)θyj={-yjlyj,iflyj<0,∞,iflyj≥0.(ii)
If|Ej0|=|Eyj0|, then(6.10)θx=θxj1=min⁡(θxj,j∈JxB),where(6.11)θxj={dj+-xjlxj,iflxj>0,dj--xjlxj,iflxj<0,∞,iflxj=0,θy=min⁡(θyj0,θyj1),
with
(6.12)θyj0={yj0,ifEyj0>0,∞,ifEyj0<0,θyj1=min⁡(θyj,j∈JyB),
where
(6.13)θyj={-yjlyj,iflyj<0,∞,iflyj≥0.The new feasible solution is(6.14)(x¯,y¯)=(x+θ0lx,y+θ0ly).


### 6.3. The New Suboptimality Condition

Let us calculate the suboptimality condition of the new support feasible solution in the case ofEy≥0. We have
(6.15)β((x¯,y¯),(JxB,JyB))=∑j∈JxNExj>0Exj(x¯j-dj-)+∑j∈JxNExj<0Exj(x¯j-dj+)+∑j∈JyNEyjy¯j.(i)
Ifj0∈JxN, then the components x¯j, for j∈JxN, are equal to
(6.16)x¯j={xj,forj≠j0,xj0-θ0,ifExj0>0,xj0+θ0,ifExj0<0,
and the components y¯j are
(6.17)y¯j=yj,∀j∈JyN.
Hence,
(6.18)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0|Exj0|.(ii)
Ifj0∈JyN, then the components x¯j, for j∈JxN, are equal to(6.19)x¯j=xj,∀j∈JxN,and the componentsy¯j, for j∈JyN, are
(6.20)y¯j={yj,forj≠j0,yj0-θ0,forj=j0.Hence,(6.21)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0Eyj0.
In both cases, we will have
(6.22)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0|Ej0|,
with |Ej0|=|Exj0|∨Eyj0.


### 6.4. Changing the Support

Ifβ((x¯,y¯),(JxB,JyB))≤ϵ, then the feasible solution (x¯,y¯) is ϵ-optimal and we can stop the algorithm; otherwise, we will change JB as follows:  (i)
ifθ0=θxj0∨θyj0, then J¯B=JB, x¯=x+θ0lx, y¯=y+θ0ly,(ii)
ifθ0=θxj1∨θyj1, then J¯B=(JB∖j1)∪j0, x¯=x+θ0lx, y¯=y+θ0ly.Then we start a new iteration with the new support feasible solution{(x¯,y¯),(J¯xB,J¯yB)}, where the support J¯B satisfies the algebraic condition
(6.23)det⁡A¯HB=det⁡AHB(I,J¯B)≠0.Remark 6.1.
The stepθ0=∞ may happen only if JxB=∅, |Ej0|=|Eyj0| and θy=∞. In such a case, the objective function is unbounded with respect to y.


## 6.1. Computation of the Directionl

We have two cases.(i)
If|Ej0|=|Exj0|, we set:
(6.3)lxj0=-sign⁡Exj0,lxj=0,j≠j0,j∈JxN,lyj=0,j∈JyN,lB=(lxBlyB)=AHB-1aj0sign⁡Exj0.(ii)
If|Ej0|=|Eyj0|, we will set
(6.4)lyj0=-sign⁡Eyj0,lyj=0,j≠j0,j∈JyN,lxj=0,j∈JxN,lB=(lxBlyB)=AHB-1hj0sign⁡Eyj0.


## 6.2. Computation of the Stepθ

The stepθ0 must be taken as follows:
(6.5)θ0=min⁡(θx,θy).(i)
If|Ej0|=|Exj0|, then θx=min(θxj0,θxj1), where
(6.6)θxj0={dj0+-xj0,ifExj0<0,xj0-dj0-,ifExj0>0,θxj1=min⁡(θxj,j∈JxB),
with
(6.7)θxj={dj+-xjlxj,iflxj>0,dj--xjlxj,iflxj<0,∞,iflxj=0.
The number θy will be computed in the following way:
(6.8)θy=θyj1=min⁡(θyj,j∈JyB),
where
(6.9)θyj={-yjlyj,iflyj<0,∞,iflyj≥0.(ii)
If|Ej0|=|Eyj0|, then(6.10)θx=θxj1=min⁡(θxj,j∈JxB),where(6.11)θxj={dj+-xjlxj,iflxj>0,dj--xjlxj,iflxj<0,∞,iflxj=0,θy=min⁡(θyj0,θyj1),
with
(6.12)θyj0={yj0,ifEyj0>0,∞,ifEyj0<0,θyj1=min⁡(θyj,j∈JyB),
where
(6.13)θyj={-yjlyj,iflyj<0,∞,iflyj≥0.The new feasible solution is(6.14)(x¯,y¯)=(x+θ0lx,y+θ0ly).


## 6.3. The New Suboptimality Condition

Let us calculate the suboptimality condition of the new support feasible solution in the case ofEy≥0. We have
(6.15)β((x¯,y¯),(JxB,JyB))=∑j∈JxNExj>0Exj(x¯j-dj-)+∑j∈JxNExj<0Exj(x¯j-dj+)+∑j∈JyNEyjy¯j.(i)
Ifj0∈JxN, then the components x¯j, for j∈JxN, are equal to
(6.16)x¯j={xj,forj≠j0,xj0-θ0,ifExj0>0,xj0+θ0,ifExj0<0,
and the components y¯j are
(6.17)y¯j=yj,∀j∈JyN.
Hence,
(6.18)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0|Exj0|.(ii)
Ifj0∈JyN, then the components x¯j, for j∈JxN, are equal to(6.19)x¯j=xj,∀j∈JxN,and the componentsy¯j, for j∈JyN, are
(6.20)y¯j={yj,forj≠j0,yj0-θ0,forj=j0.Hence,(6.21)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0Eyj0.
In both cases, we will have
(6.22)β((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0|Ej0|,
with |Ej0|=|Exj0|∨Eyj0.


## 6.4. Changing the Support

Ifβ((x¯,y¯),(JxB,JyB))≤ϵ, then the feasible solution (x¯,y¯) is ϵ-optimal and we can stop the algorithm; otherwise, we will change JB as follows:  (i)
ifθ0=θxj0∨θyj0, then J¯B=JB, x¯=x+θ0lx, y¯=y+θ0ly,(ii)
ifθ0=θxj1∨θyj1, then J¯B=(JB∖j1)∪j0, x¯=x+θ0lx, y¯=y+θ0ly.Then we start a new iteration with the new support feasible solution{(x¯,y¯),(J¯xB,J¯yB)}, where the support J¯B satisfies the algebraic condition
(6.23)det⁡A¯HB=det⁡AHB(I,J¯B)≠0.Remark 6.1.
The stepθ0=∞ may happen only if JxB=∅, |Ej0|=|Eyj0| and θy=∞. In such a case, the objective function is unbounded with respect to y.


## 7. Algorithm

Letϵ be any nonnegative real number and {(x,y),(JxB,JyB)} an initial support feasible solution. The steps of the algorithm are as follows.  (1)
Compute the estimations vector:(7.1)ENt=Et(JN)=(ExNt,EyNt)=(utAN-cNt,utHN-kNt),ut=(cBt,kBt)AHB-1.(2)
Optimality test of the support feasible solution{(x,y),(JxB,JyB)}.
(i)
IfEy≥0, then
(a)
calculate the value of suboptimalityβ((x,y),(JxB,JyB)),(b)
ifβ((x,y),(JxB,JyB))=0, the process is stopped with {(x,y),(JxB,JyB)} as an optimal support solution,(c)
ifβ((x,y),(JxB,JyB))≤ϵ, the process is stopped with {(x,y),(JxB,JyB)} as an ϵ-optimal support solution,(d)
ifβ((x,y),(JxB,JyB))>ϵ, go to (3),(ii)
ifEy≱0, go directly to (3).(3)
Change the feasible solution(x,y) by (x¯,y¯):   x¯=x+θ0lx and y¯=y+θ0ly.
(i)
Choose a subscriptj0.(ii)
Compute the appropriate directionl=(lxly).(iii)
Compute the stepθ0.
(a)
Ifθ0=∞ then the objective function is unbounded with respect to y and the process is stopped.(b)
Otherwise, compute(x¯,y¯)=(x+θ0lx,y+θ0ly).(4)
Optimality test of the new feasible solution(x¯,y¯).
(i)
IfEy≥0, then
(a)
calculateβ((x¯,y¯),(JxB,JyB))=β((x,y),(JxB,JyB))-θ0|Ej0|,(b)
ifβ((x¯,y¯),(JxB,JyB))=0, the process is stopped with {(x¯,y¯),(JxB,JyB)} as an optimal support solution,(c)
ifβ((x¯,y¯),(JxB,JyB))≤ϵ, the process is stopped with {(x¯,y¯),(JxB,JyB)} as an ϵ-optimal support solution,(d)
otherwise, go to (5).(ii)
IfEy≱0, then go to (5).(5)
Change the supportJB by J¯B.
(i)
Ifθ0=θxj0∨θyj0, then
(7.2)J¯xB=JxB,J¯xN=JxN,J¯yB=JyB,J¯yN=JyN,x¯=x+θ0lx,y¯=y+θ0ly.(ii)
Ifθ0=θxj1∨θyj1, then two cases can arise:
(a)
case whereEj0=|Exj0|:
*
ifθ0=θxj1, then
(7.3)J¯xB=(JxB∖j1)∪j0,J¯xN=(JxN∖j0)∪j1,J¯yB=JyB,J¯yN=JyN,*
ifθ0=θyj1, then
(7.4)J¯xB=JxB∪j0,J¯xN=JxN∖j0,J¯yB=JyB∖j1,J¯yN=JyN∪j1.(b)
Case whereEj0=|Eyj0|:
*
ifθ0=θyj1, then
(7.5)J¯yB=(JyB∖j1)∪j0,J¯yN=(JyN∖j0)∪j1,J¯xB=JxB,J¯xN=JxN,*
ifθ0=θxj1, then
(7.6)J¯xB=JxB∖j1,J¯xN=JxN∪j1,J¯yB=JyB∪j0,J¯yN=JyN∖j0.(iii)
Go to (1) with the new support feasible solution{(x¯,y¯),(J¯xB,J¯yB)}, where x¯=x+θ0lx and y¯=y+θ0ly.


## 8. Numerical Example

For the sake of clarity, let us illustrate the theoretical development of the method by considering the following linear program:(8.1)z(x,y)=2x1-3x2-y3+y4⟶max⁡,x1-x2+3y3+2y4=2,-7x1+x2+2y3+3y4=2,-2≤x1≤2,-4≤x2≤4,y3≥0,y4≥0,
where x=(x1,x2) and y=(y3,y4).We defineA=(1-1-71), H=(3223), ct=(2-3), and kt=(-11).Let(x,y)=(1302) be an initial feasible solution of the problem. We set
(8.2)JB={JxB,JyB}={1,3},JN={2,4}.
Let ϵ=0.Thus, we have an initial support feasible solution{(x,y),JB} with
(8.3)AHB=(13-72),AHN=(-1213),z(x,y)=-5.First Iteration
Let us calculate(8.4)ut=(cBt,kBt)AHB-1=(-323-723)ENt=utAHN-(cNt,kNt)=(6523-5023).Choice ofj0:
Among the nonoptimal indicesJxNNO∪JyNNO={2,4}, j0 is chosen such that |Ej0| is maximal; we then have j0=2.
Computation ofl:(8.5)lx2=-1,ly4=0,lB=(lx1ly3)=AHB-1a2=(-523-623).
Hence
(8.6)lx=(-523-1),ly=(-6230).Computation ofθ0:(8.7)θxj0=θx2=x2-d2-=7,θx1=(d1--x1)lx1=695,θy3=-y3ly3=0.
The maximal step is then
(8.8)θ0=θyj1=θy3=0.Computation of(x¯,y¯):(8.9)x¯=x+θ0lx=(13),y¯=y+θ0ly=(02).Change the support:(8.10)J¯xB={1,2},J¯xN=∅,J¯yB=∅,J¯yN={3,4}.Second Iteration
We have(8.11)(x,y)=(1302),JxB={1,2},JxN=∅,JyB=∅,JyN={3,4},AHB=(1-1-71),AHN=(3223).
We compute
(8.12)ut=(cBt,kBt)AHB-1=(19616),ENt=utAHN-(cNt,kNt)=(656356).Computation ofβ((x,y),(JxB,JyB)):(8.13)β((x,y),(JxB,JyB))=Ey3y3+Ey4y4=353.
Then, (x,y) is not optimal.
Choice ofj0: As the set of nonoptimal indices is JxNN0∪JyNN0={4}, we have  j0=4.
Computation ofl:(8.14)ly4=-1,ly3=0,lB=(lx1lx2)=AHB-1h4=(-56-176).
Hence,     lx=(-5/6-17/6),ly=(0-1).
Computation ofθ0:(8.15)θxj1=min⁡(θx1,θx2)=min⁡((d1--x1)lx1,(d2--x2)lx2)=min⁡(185,4217)=4217=θx2,θy3=∞,θyj0=θy4=2.
The maximal step is thus θ0=θy4=2.
Consequently, the support remains unchanged:(8.16)J¯B=JB={1,2},J¯N=JN={3,4}.Computation of(x¯,y¯):(8.17)x¯=x+θ0lx=(-23-83),y¯=y+θ0ly=(00).Computation ofβ((x¯,y¯),(JxB,JyB)):(8.18)β((x¯,y¯),(JxB,JyB))=0.
Then, the vector (x,y)=(-2/3,-8/3,0,0) is an optimal solution and the maximal value of the objective function is  z=20/3.


## 9. Conclusion

The necessity of developing the method presented in this paper occurred during a more complex optimization scheme involving the resolution of a multicriteria decision problem [2]. Indeed, an efficiency test of nonbasic variables is necessary to be executed several times along the resolution process. This efficiency test yields to solve a monocriteria program with two kinds of variables: upper and lower bounded variables and nonnegative ones. This kind of linear models can be found as subproblems in quadratic programming [4] and optimal control for example. In these cases, the use of the simplex method is not suitable since the transformed problems are often degenerated. An other particularity of our method is that it uses a suboptimal criterion which can stop the algorithm with a desired precision. It is effective, fast, simple, and permits a time reduction in the whole optimization process.



---

*Source: 374390-2011-04-27.xml*