 Open Access
 Total Downloads : 37
 Authors : Andrianarizaka Marc Tiana , Robinson Matio , Andriamanohisoa Hery Zo
 Paper ID : IJERTV7IS030092
 Volume & Issue : Volume 07, Issue 03 (March 2018)
 Published (First Online): 22032018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
TopoGeometric Model MZ: Feeded Objects
Andrianarizaka Marc Tiana,
Doctoral School in Engineering and Innovation Science and Technology (EDSTII)
Doctoral Research Team for Cognitive Science
and Application (EADSCA) University of Antananarivo, MADAGASCAR
Robinson Matio,
Doctoral School in Engineering and Innovation Science and Technology (EDSTII)
Doctoral Research Team for Cognitive Science and
Application (EADSCA)
University of Antananarivo, MADAGASCAR
Andriamanohisoa Hery Zo,
Doctoral School in Engineering and Innovation Science and Technology (EDSTII) Doctoral Research Team for Cognitive Science and Application (EADSCA)
University of Antananarivo, MADAGASCAR
Summary : The Topogeometric approach MZ requires notions of both vector geometry and affine geometry, and also uses topology concepts to transform the elementary notions of presenting a linear program problem. These different forms or presentation models of problems related to the Topogeometric approach MZ are initially presented in this article and will be followed by elementary results demonstrated by the use of the supported objects of the supported model. Thus, this article is the precursor of the determination of redundant constraints by the Topogeometric model MZ. The energized objects will thus constitute the language of the proofs of the subsequent propositions.
Keywords : Linear programming, mathematical writing of the model, writing of the Topogeometric model MZ, algorithm.
1 INTRODUCTION
This paper constitutes the basis of the Topogeometric
2.2 Indexes
It is a positive or null integer that will be attached to an object of a model, as a unique identifier. Symbolically the indexes will be represented by i, j, k…
To represent the possible values of an index, the following notions will be used:
xi
i = 1, 2…n meaning that the index i varies from 1 to n. When an objective x of a model is an index, one writes:
i1,…,n
which is a condensed representation of :
x1
x :
2
model MZ in search of redundant constraints in a problem of linear programming. This article follows the work on the TopoGeometric MZ model published in MADAETI, ISSN 22200673, Vol.2,
2016, www.madarevues.gov.mg which develops the basic concept of Topogeometric models, and presents the powered objects in search of the redundant constraints of a linear programming problem. All the mathematical object classes will first be presented
from the simplest to the most complicated, to model the real concept allowing the decision
x
i1
An object can have two indexes as identifiers. This is the case with matrices, for example.
It is represented by
aij i 1,…,m
j 1,…,m
which designates the matrix :
a11…..ain
a
a
i
making. Together with the presentation of each class,
m1
….a
mn
the existing operations and relationships will be analyzed; the representation of technical constraints by affine halfspaces is the most important part of this work.
2 THE MEAN OBJECTIVES
To fully exploit the indexes, the symbol (summation)
will also be used.
So, to represent
c1x1 c2 x2 ….. cn xn , it will be simply written:
2.1 The scalars
A scalar is any real number. Symbolically, a scalar will be represented with a Latin or Greek or lowercase letter.
Examples: x, y, z,….,,….
n
j 1
c j .x j
3 THE ELEMENTARY OBJECTS

Decision spaces
Take again the problems LPP in its known form which
To each decision, variable xj
vector U j .
corresponds the unit
consists of finding the unknownreal x1 , x2 ,….., xn , and maximize:
The affine space n , equipped with the reference O,U1 ,U2 ,….,Un is called the decision space
Z c1.x1 c2 x2 …. cn xn
(3.01)
relating to the LPP problem to be solved.
And which satisfy the following
a x a x …. a x b
Despite this striking resemblance to Euclidean affine geometry, a limiting aspect will be presented from the start.
11 1 i2 2 1n n 1
conditions :
a21 x1 a22 x2 … a2n xn b2
a x a x …. a x b
(3.02)

Postulate
In the topogeometric theory MZ, the orthonormal affine
m1 1
m2 2
mn n n
frame of the decision space action of the problem LPP to be
i) x1 0, x2 0….., xn 0
where the coefficients:
cj j 1, …, n
(3.03)
solved is unique.
This assumption means that :

The concept of basic change does not exist.

The concept of change of origin does not exist.
aij i 1, …., n j 1, …., n
bi i 1, n
Each line of the conditions (3.02) is called a technical constraint.
Conditions (3.03) are called nonnegativity constraints.
Definition 3.01: decisionactionpointvectors We call decisionaction any ntuple :
x1
However, following a presolved analysis, it may be possible that n changes, which completely modifies the LPP problem.


OPERATIONS ON ACTIONDECISIONS
Given an LPP problem, according to definition 3.01, a decision is represented by a point in the decisionaction space and / or by a vector of the vector space n
This dual nature (both affine and vectorial) of decision actions is very important.
It allows to express :
The creation of other stockdecisions based on existing stockdecisions
2
x Whose
x
n
x1, x2 ,…, xn are elements of
The search for other decisionactions according to a given direction.
It will be noted later :
x j j 1, …, n
Mathematically, we see that it is an element of n relative to a given base. It is also a point in the affine space n relative to a given landmark.
An action decision will be represented by an affine
point. Which brings us to the decisionaction definition? Notation : an action decision is noted using a capital Greek letter: A, B, X, Y
Definition 3.02: decision marker – action – decision space
We call decisionaction benchmark, the positive orthonormal geometric benchmark, noted :
O,U ,U , ….,U

Amplifier of an action decision
Let the decisionaction space relate to the reference.
Let X0 be an action decision and a given positive real number.
We call amplifier of X0 using , the generation of an action decision X such that
X = X0
Mathematically, it is therefore the multiplier of vector X0 by the scalar

Addition of two decisionactions
Let X0 and X1 be two decisionactions in a LPP problem. The addition of X0 and X1 is called the creation of a new action decision X such that
X = X0 + X1
Note 4.01
1 2 n
related to the aforementioned LPP problem. In this reference, the geometric origin O has a particular meaning : it represents the decision to do nothing, that is, if
xo1
O = x , x x x …. x = 0
The combination of 2.3.1 and 2.3.2 allows us to model the conic combination concept of two or more actiondecisions. Let the decisionactions X 1, X 2… X k.
The conic combination of these decisions is the new decision X defined by:
X = 1 X 1 + 2 2 + … + k X k
o2
01 02 03 0n
x
0n
1, 2 …., k are positive real numbers or zero.
Note 4.02
From the previous remark, it is clear that the decision satisfies the constraint (2.03) if it is a conic combination of U1, U2 … Un, that is to say:
X = 1U1 + 2U2 + … + nUn with 1 0, 2 0 n 0 Let's show that it is reciprocal and true.
Let X be an action decision satisfying the constraint (2.03)
X = (x ji ) with x ji 0
but
n
(xj) x jU j with x j 0
j 1

Search axe defined by decisionaction Xo and direction the vector decisionaction V
Let X0 and V be actiondecisions.
We call search axis starting from X o and direction U the set of decision actions, noted (X0, V) defined by
(X0, V) = {X n / X = X0 + V, with and 0}
Mathematically, it is the affine ray derived from X0 and the vector V.
Conceptually, the research idea is justified by the fact that in practice, any solver is based on a search algorithm starting from an initial point.
Thus, from a given decisionaction X0, and a given search direction V, one can search the points in the universe of

THE TECHNICAL CONSTRAINTS
In practice, any actiondecision always has an impact. In the field of linear programming, two categories of impacts can be distinguished :

Impactperformance.

Resource impacts.
In this study, we only deal with the impactresources.
Definition 5.01 resource impact
Let X be an action decision point of a given LPP problem. Let V be a null vector of n .We call resource impact according to V, the scalar product of X and V in n
noted:
(X, V) = <X, V>
Where <X, V> denotes the scalar product U with V.
The vector V is called unit consumption vector V of the given resource.
Definition 5.02 constraint resources
In our theory, we assume that a constraint that is logical or material may be associated with a resource that is always limited in the associated LPP problem.
Let A = (aj) j = 1… n be a vector V of consumption of a given resource.
Let b be the limit value of the resource, the zone of respect of the consumption of the resource limited by b is the set noted ZR (A, b) defined by :
decisions that will satisfy the constraints (3.02) and (3.03).
This research idea is not confined to a single research
ZR (A, b) = X n /
A, X
b
(5.01)
direction. It is also possible to adopt simultaneously two
search directions V1 and V2. Hence the concept of research plan ", Starting from X0 and direction V1 and V2.
In affine geometry, this set is none other than the negative halfspace delimited by the noted affine hyperplane. HP (A, b) defined by:

Plan of research starting from a decisionaction X0 and directions V1 and V2
HP (A, b) = X n /
A, X
b
(5.02)
Let X0 be a decisionaction point and V1 and V2 two decisionaction vectors of it.
We call search plane starting from X0 and directions V1 and V2 , the set noted P (X0 ,V1, V2 ) defined as follows :
P (X0, V1, V2,) = {X n / X = X0 + 1 V1 + 2 V2, where
1 + and 2 +}
NB: The vector A is not an actiondecision it is linked to a
given resource and allows to calculate the impact of an action X decision on this resource



The constraints of nonnegativity
The nonnegativity constraints translate the fact that the elementary decisions xi, where i = 1… n must be non negatives, is :
By generalizing, we have :
xi 0
i = 1, 2… n
Let us note immediately that the relations :

Research of X0 direction and V1, V2… Vk, vectors decisions
Let X0 be a decisionaction point associated with a LPP.
Let V1, V2…Vk, k decision action vectors of the same problem LPP.
We call vertex cone X0 and directions V1 , V2 , ….,Vk , the action decision set denoted:
C (X0, V1, V2… Vk) defined as follows: C (X0, V1, V2… Vk).
It should be noted at once that research axes and research
plans are only special cases of research axes.
xi 0 i = 1, 2… n can be written:
xi 0 i = 1, 2… n Expression equivalent to:
Ui , X 0
Therefore, a nonnegativity constraint can also be considered as a resource constraint delimited by ZR Ui , 0 called nonnegativity zone ZNNi.
However the combination of all nonnegativity constraints has a particular geometric meaning that we call " non negativity cone ".

nonnegativity cone
0
We call nonnegativity cone noted C the cone of search
from pointdecision O and direction of all decision vectors :
Ui , i 1, 2,…., n
Geometrically we have:
The acceptable solution area associated to the constraint :
Ai X bi, i = 1 , 2 , . . . , m, i / k
of the system .
The kth constraint :
Ak X b k (1 k m)
is redundant for the system (7.01) if and only if S = Sk.

n n
C0 X
/ X iUi i1
where i 0
(6.01)
Definition 7.01
CÃ´ne(O,U1 ,U2 ,.. .,Un )
Note 6.01:
Redondant constraints can be classified as weak and strong redundant constraints. 1.3.2
It is obvious that

i
C
o i1
ZNNi
Low redundancy constraints The constraint ATi X bi is
weakly redundant if she is redundant and


Nonnegativity face
It is to be recalled that the geometric topo reference of the LPP problem is immutable (O, U0, U2…, Un).
This means that we cannot change the place of a vector Ui of this reference, for all i, for all
i = 1, 2…, n.
We call the nonnegativity face, denoted by FNNi, the decision point set defined as follows:
P O,U1,Un for i 1
FNNi
P O,Ui 1 ,Ui for i 2, 3,…, n

Nonnegativity axes
For all i = 1, 2… n, we call nonnegativity axis, ANNi , the set of decision point defined as follows :
ANNi =R (O, Ui) i = 1.2… n (6.02)
Note that ANNi is none other than the search axis starting from O and with the direction Ui.
Recall the concept of redundant constraints.

REDUNDANT CONSTRAINTS
A redundant constraint is a
constraint which can be deleted from a system of
linear constraints without changing the feasible region or acceptable solution area.
If we look at the next system of m and n constraints
of linear inequality, no negative (m n), we can adopt the matrix writing:
ATi X = bi for all X S.

RELATIONSHIP BETWEEN MZ OBJECTS
The relationships described in this section are the basic ones. More complex relationships will be discussed in the next chapter.
Moreover, the combinations between pointdecisions and pointvectors have already been seen. Therefore, only the following points will be dealt with:

The relation between a decisionpoint and a constraint technical zone.

The relation between a research axis and a zone of technical constraints.

The relation between a research plan and a zone of technical constraints.
8.1 Relationship between a decision point and a technical constraint zone
Since a pointdecision is represented with a point, and a zone of technical constraints is represented by a halfspace, a set of decisionpoint, the essential same basic relation between one of these two object classes, is the ensemblist relation of belonging.
Let X0 be a decision point and ZCT (A, b) a constraint zone. The relationship
X0 ZCTA, b means A, X0 b
But
AX B, X 0, (7.0)
Since in the LPP problem model, the constraints are indexed, i.e. numbered from 1 to n, the corresponding
A R m x n, b m n
technical constraints areas will also be noted. :
And 0 n
R , X R ,
ZCTi
i = 1,2… n
R .
Let
AT i bi
be the i th constraint of system (7.01) and let
S = {X n
This makes it possible to represent the system of techniques as follows:
Let X0 be a decisionpoint satisfying all the technical constraints of the problem.
We have :
R /ATi X bi, X 0}
The acceptable solution area associated with the system (7 .01).
Let
S k = {X R n/ ATi X b, X 0, i k}
Ai , X0 bi for i 1, 2,…, n
This can be written :
X0 ZCTi For everything i = 1, 2… n From where,
X
m
0 i 1
ZCTi
(8.01)
Relationship that is a basis for redundancy and infeasibility analysis.
Moreover, when X0 does not belong to a ZCTi, we also say that X0 is exterior to ZCTi as the outer term, and its inner
Is X0 ' the projection of We have :
X 0 on
X ' X
HP Ai , bi
i i
bi Ai , X 0 A
i
opposite has a topological connotation, the topological
definitions of these terms will be recalled.
0 0 A , A
b A , X
X X '
i i 0 A
0 0 A , A i
8.1.1 Projection of a point on a hyperplane
Let ZCTi be the area of technical constraints delimited by the HP hyperplane (Ai, bi) and let X0 be any decisionpoint.
i i
The product of X0 X0 ' with Ai is :
i
i i
b A , X
We call projection of X0 on the hyperplane HP (Ai, bi), the point noted X0 such that :
X 0 X 0
', A
i i 0
i i
A , A
A , A
X0 belongs to HP (Ai, bi) and is collinear to the vector Ai. X'0 is the intersection of HP (Ai, bi) with the straight line passing through X0 and whose direction vector is Ai.
X 0 X 0 ', Ai bi Ai , X 0
but X0 ZCTi
which means :
Proof :
Mathematically this right is defined by :
Ai , X0 bi and X0 HP Ai , bi
So Ai , X0 bi
X n with X X A
0 i,
Therefore we have: Ai , X0 bi
The intersection is written,
From where
bi Ai , X0 0
X'0 = X0 + Ai
Finally we get the following relation:
Ai , X '0 bi
X X ', A 0
Ai , X 0 Ai bi
0 0 i

8.1.3
Ai , X 0 Ai , Ai bi
Ai , Ai bi Ai ,
X 0
Direction of a decision vector with respect to ZCTi
Let V be a decision vector, and let ZCTi be a technical constraint zone V parallel to HP (Ai; bi), that is to say at the
bi
Finally, we have :

Ai ,
Ai , Ai
X 0
ZCTi boundary.

External orientation
We say that V has an external orientation with respect to
X X

bi Ai ,


X0 A
(8. 02)
ZCTi, if <V, Ai> is strictly positive.
0 0 A , A i
i i
Moreover, the distance between X0 and X'0 denoted d (X0, X'0) is equal to :
bi A , X

Parallel orientation
We say that V has a parallel orientation with respect to ZCTi, if <V, Ai> is equal to 0.
Note 8.01:
d X0 , X '0
d X0 , X '0
i 0
Ai , Ai
bi Ai , X 0
Ai , Ai
Ai , Ai
(8.03)
The qualification parallel refers to the fact that V is parallel to HP (Ai ; bi), that is to say at the ZCTi border.

Internal orientation
We say that V has an internal orientation with respect
This distance is also called the distance from the point Xo to the hyperplane HP (Ai, bi).
8.1.2 Orientation of the vector Ai with respect to ZCTi Proposition 8.01
The vector is always oriented from inside to outside of
to ZCTi, if <V, Ai> is strictly negative.

Characterization of an Inner Point of ZCTi
Proposition 8.02
X0 is an inner point of ZCTi if and only if :
ZCTi.
Proof:
Let X0 a ZCTi point that does not belong to the
Proof:
Ai , X0
< bi
hyperplane HP Ai , bi :
X0 ZCTi and X0 HP Ai ,bi

Let X0 be a point inside ZCTi.
According to 2.7.1.3.1, there exists a strictly positive reality r such that the ball whose center is X0 and with a radius r is entirely contained in ZCTi.
Logically, this means that if X0' designates the projection of
X0 on HP Ai , bi , then the distance between X0 and X0 ' is equal to :
Proof:
Let's first show the first inclusion :
Fr ZCTi HP(Ai ,bi )
bi Ai , X0
Ai , Ai
Let Xo be an element of Fr (ZCTi), that means that X0 is also an element of ZCTi so,
Ai , X0 bi
And
If Xo HP A , b , this means that A , X
b
r bi Ai , X0
but r is strictly positive,
i i
From where,
i 0 i
Ai , Ai
Ai , X0 bi
, meaning that X0 is an inner point of
bi Ai , X0
Ai , Ai
is strictly positive from where
ZCTi, which contradicts the fact that X0 is a border point of ZCTi.
Reciprocal :
bi Ai , X0
is alsostrictly positive .
HP Ai ,bi Fr ZCTi

Reciprocally, X0 is a point of ZCTi such that A , X b
Let X0 be a point of HP (Ai,bi) which means that :
Ai , X0 bi
i 0 i
Let r be any strictly positive real number and X
the point
Let us show that this is an inside point of ZCTi.
Let X0' be the projection of X0 on the hyperplane. We saw
1
defined by :
that :
The distance between X0
and X0' is equal to:
X1 X0

r . 2
Ai
Ai , Ai
Let
bi Ai , X 0
Ai , Ai
Note that the distance between X0 which is strictly less than r.
and X1
is equal to r ,
2
r 1 bi Ai , X 0
2 Ai , Ai
We have r> 0 ;
and it is obvious that the ball whose center is X0 and radius r is entirely included in ZCTi, which means that X0 is an
Moreover, according to Proposition 8.01, Ai is always oriented towards the outside of ZCTi so X1 do not belong to ZCTi.
So X1 belongs to the open ball of center X0 and radius r. Finally, let us show that the open ball of center X0 and radius r contains points of ZCTi other than X0.
Let X2 the point defined by :
internal point of ZCTi .
8.1.4.1 S border point

X2 X0

r . 2
Ai
Ai , Ai
A point X0 n is said to be a border point of S if :
X0 is an element of Set ;
i
i i
Whatever the positive real number r is, the open ball of center X0 and radius r contains both elements of S other than
We obtain:
i 2 i
A , X A , X

r . Ai
i i
0 2 A , A
X0 and elements of S (the complement of S in Euclidean
affine space n ).
A , X 0
r . 2
1
i i
A , A
A , A
8.1.5 S border
Let S be a nonempty set in the Euclidean affine space with the orthonormal coordinate system
(O, U ,U ,…,U ). We call the boundary of S the set noted
A , X
i
2
But
Ai , X 0
r
2
1 2 n
A , X b A , X b r
Fr (S) containing all the boundary points of S.
Proposition 8.03
We characterize the border points of the ZCTi by:
r
Fr (ZCTi) = HP (Ai; bi)
i 0 i i 2 i 2
As
r 0 r 0
2
From where
bi 2 bi
We can write :
Ai , X2 bi
Which means that X2 belongs to ZCTi.
In summary, every strictly positive real number in the open ball of center X0 and radius r contains both elements of ZCTi other than X0 and elements of ZCTi.
This means that X0 is a frontier point of ZCTi.
Finally, in combination with the two way, we

Relationship between a search axis R (X0, V) and a technical constraint zone ZCTi
Consider an area of ZCTi technical constraints. Let also be the radius R(X0, V) coming from X0 and direction vector V, representing a search axis. This relationship is based on the existence and uniqueness of the solution of the equation :
have :
A , V b A , X , is the unknown.
Fr ZCTi
and
Fr ZCTi
So we have
Fr ZCTi
Proposition 8.04
HP Ai ,bi
HP Ai ,bi
HP Ai , bi
i i i 0
Proof:
Since the two objects are sets of decision points, the main combination that can be imagined between them is the intersection. In addition, since the area of technical constraint is closed and the hyperplane HP (Ai, bi) is closed, we will be much more interested in the intersection of the
The zone of technical constraints ZCTi is topologically
closed.
Proof :
Let X0 be a point not belonging to ZCTi (where ZCTi denotes the complement of ZCTi in the affine space).
As
X0 ZCTi
radius R (X0, V) with this boundary HP (Ai, bi). Indeed, if X0 is outside of ZCTi, then such an intersection gives us the point of entry from the outside to the inside of ZCTi along the radius. On the other hand, if X0 is inside ZCTi, it gives the exit point of ZCTi.
Let I denote this point of intersection : as I belongs to R
(X0, V)
We have I X0 V avec 0
So Since I also belongs to HP (Ai, bi), we can write :
Ai , X0 bi
Ai , I bi
Let X0' be the projection of X0 on HP Ai , bi . We showed
By combining these two relationships, we have
that :
The distance between Xo and X0 is equal to :
Ai , X0
V bi
b A X
By developing, we get
i i 0 . A , X A ,V b
A , A i
0 i i
i i
but
which is an equation where is the unknown. This equation gives :
i 0
i
A , X b
b A , X 0
A , V b A , X (8.04)
i i i 0
i i 0
so
bi Ai ,
X0 bi


Ai ,
X 0
The existence and uniqueness of depend on the values of b i – (Ai, X o) and (Ai,V), hence X0 and V.
Ai , X0 bi
The distance between X0 and the border HP Ai , bi is equal to :

Where X0 is outside ZCTi and where V is not facing inwards from ZCTi
Ai , X0 bi
The equation :
Ai ,
Ai
Ai , V
bi
Ai , X0
Let :
r 1 . Ai , X0 bi be
has no solution.
Proof:
2 Ai , Ai
It is easy to show that the open ball of center X0 and radius r is entirely contained in ZCTi .
This case is mathematically translated by :
i
0
A , X b
Therefore ZCT is open.
i and A , X b
i
So ZCTi is closed.
Ai , V
leads that,
0 i 0 i
b A , X 0
In summary of Proposition 8.03 and Proposition 8.04, each zone of ZCTi technical constraints is closed and their
i i 0
Also as
0 et A , V b


A ,
X O
boundary is none other than the hyperplane HP Ai , bi .
i i i 0
which is impossible.
In this case I do not exist.

Where X0 is outside ZCTi and where V is inward ZCTi
The equation :

Where X0 is on the ZCTi border and where V is inward ZCTi
The equation :
Ai , V bi Ai , X0
has a unique solution.
A , V b A , X
i i i 0
has a unique solution.
Proof :
b A , X
i i 0 0
Ai , V
In this case
b A , X 0
et A ,V 0
Proof:
i i
which leads to
0 i
0
We have :
That is to say I X
, unique solution.
b A , X 0 et A ,V 0 0
i i 0 i
which gives
bi
Ai , X0 0
Ai , V
which is in addition a unique value.

Where X0 is inside ZCTi and where V is outside ZCTi
The equation :
A , V b A , X
In this case we say that we have a single point of entry starting from X0, and moving along the axis of R (X0, V).

Where X is on ZCT and where V is outside ZCT
i i i 0
has a unique solution
bi Ai , X 0
0 i i
The equation :
Ai , V bi Ai , X0
admits a null solution.
Ai , V
Proof :
This case results
i
in Ai , X 0 b et Ai ,V 0 :
Proof:
Which leads to:
b A ,
X 0
This case results in :
i i 0
b A , X 0 and A , V 0
Hence the unique solution
i i 0 i
The only solution available is :
bi
Ai , X 0
(2.12)
0
Meaning that,
I X0
Ai , V

Where X0 is on the ZCTi border and where V is parallel oriented to
HP (Ai, bi)
The equation :

Case where Xo is inside ZCTi and where V is parallel oriented to ZCTi
The equation :
Ai , V bi Ai , X0
has no solution.
Proof :
A , V b A , X
i i i 0
As in the previous case, we have :
has an infinity of solutions.
b Ai ,
X 0 but
Ai ,V 0
i
0
Proof :
Mathematically we translate this case by :
i i 0 i
b A , X 0 and A , V 0
Which leads to an impossibility, meaning that R X 0 ,V will never intercept the border of ZCTi .

Where X0 is inside ZCTi and where V is inward ZCTi
The equation :
This gives us infinity of solutions. In fact, R(X0, V) is included in HP (Ai ; bi), and the intersection is none other than R (X0, V).
A , V b A , X
i i i 0
has no solution.
Proof :
As for 2.6.2, the existence and uniqueness of the solutions to this problem depend on the
As recently,
three objects X0 ,V1 et V2 .
i i
0
i
b A , X 0 and A , V 0
– For X0, there are three possible situations : to be outside
In this case, the equation
A , V b A , X
of ZCTi, or be on the border of ZCTi or be inside of ZCTi.
– For V1 there are three possibilities : be outward facing
i i i 0
has no positive solution, meaning that R X 0 ,V will never intercept the border of ZCTi .
from ZCTi or be oriented parallel to ZCTi or be oriented towards the inside of ZCTi
– For V2 the possibilities are the same as for V1.
8.2. 9 Algorithm for determining the intersection of a search
All in all, we have 3 3 3 , that is to say, 27 possible cases to be made.
axis R (X0, V) with the technical constraint zone ZCTi
The previous eight cases can be summarized in the following algorithm :

Case where there is no intersection.
No intersection :

Case with
8.4 Search along an axis R (X0, V) in the ZNN non negativity one
The ZNN nonnegativity zone has been defined as
n
ZNN ZNNi
j 1
i i
0
Ai , X b and A , V 0
where
We have a single point of intersection
ZNNi
ZR Ui ,
(8.05)
X
0



bi
Ai , X 0
Ai ,V
V
Conceptually, this means that we assimilate ZNNi to a resource constraint zone, and if a X0 point belongs
i
– If Ai , X0 b and Ai ,V 0 .
There is unique solution :
X0
i
If Ai , X0 b and Ai ,V 0 . There is unique solution:
0
X bi Ai , X 0 V
Ai , V
If A , X b and A ,V 0
to ZNNi this means that X0 satisfies the constraint associated with ZNNi . It is therefore a stage situation.
The concept of research implies that there is a situation or
state of deposition, and that from this situation, one move to another situation or state. And we have already seen that this research, when it is linear, can be modeled by the concept of axis of research starting from a given point and moving according to a given vector R X 0 ,V
i 0 i i
No solution :
8.3 Relationship between a searchplane C(X0, V 1, V 2) with linearly independent to V1 and V2 and a of ZCTi technical constraints zone
As for section 8.2, these two objects are sets of decision
points, so this section will describe their intersection. Let I be such a point. It is thus of the form :
In this section, the starting point of the search is the point X0, which is supposed to be located in the ZNN non negativity zone. Since the new decisions found must have remained in ZNN, it is logical to study the conditions under which this search leads us out of ZNN. And as in the case of ZCTi technical constraint zones, we will need to define the boundary concept in ZNN.
For ZNNi, there is no problem. Indeed,
I X V V with and are positives.
Fr ZNN P U , 0
0 1 1 2 2 1 2 i i
More like I belongs to the border of ZCTi , we can write :
given that ZNN is only half affine delimited by the
A , I b i
i i
Which leads to :
hyperplane P Ui , O .
Ai , X0 1V1 2V2
From where
bi
And as HP (Ui, 0) is included in that ZNNi is a closed area.
ZNNi , we know
A , X A ,V ( A ,V ) b
i 0 1 i 1 2 i 2 i
Let
A ,V A ,V b A , X

Frontier of the ZNNi nonnegativity zone
Proposition 8.05
1 1 1 2 i 2
i i 0
0
n
which is a linear equation with two unknowns
variables, 1 et 2 positive.
Fr ZNN
j 1
HP U j ,0
C
Proof :
It suffices to show that for every j, HP U j
function of ZNN.
,0 C
is a
Let X j be the projection of X on HP (Uj, 0) and dj the distance between X and Xj.
As
X j X j 1,…, n
0
Step 1:
Let us show that every X point of HP U j
border point of ZNN.
,0 C is a
Then dj o Let
r
j 1,…, n
1 min(dj)
2
j 1,…, n
0
Let r be any positive real number. This is to show that the open ball of center X and radius r denoted B (X, r), contains both an element of ZNN other than X and an element of ZNN other than X is:
X = (xi) i = 1 …, n
The fact that X HP (Uj, o) Co means that xi 0, i = 1… n and that xj0
Let us take the point X' = (x'i) i = 1… n defined as follows :
It is obvious that r> 0 and that the open ball B (X, r) is included in ZNN.
There fore,
n
j
0
HP(U , 0) C ) Fr(ZNN )
j 1
Note 8.02
xi
for all i j
HP U ,0 C is the cone
x' = j 0
i 1
if i j
C O,U ,U , …,U ,U
, …,U
2
1 2 j 1 j 1 n
Similarly let us take the point:
X'' = (x''i) i = 1… n defines as follows :
We will call it " conic wall of nonnegativity j Noted MCNNj.
Proof :
x for all i j
MCNN HP U ,0 C
i
x''i = 1
if i j
j j 0
n
2
et ZNN MCNN j j 1
It is obvious that :
X' ZNN and has X'' ZNN Moreover, it is also obvious that :
X' B (X, r) and X'' B (X, r)
This shows that the open ball B (x, r) contains both the point X 'which is the element outside ZNN and the point X'' which is the element in ZNN, and it is obvious that X' is different from X and that X'' is different from X.
Therefore X is a border point of ZNN.
2nd step:
Let us show that HP (U , 0) C
In other words, the ZNN border is none other than the conic wall meeting of nonnegativity.
Note further that
MCNNj HP U j ,0
So
MCNN j Fr ZNN j

Exit point of ZNN following R (X0, V) Proposition 8.06
j 0 We assume that X0 is in ZNN. Since ZNN is closed, the exit
And in summary, HP (Uj, 0) is indeed a ZNN border and point is the point of contact or intersection
their meeting is also a border of ZNN.
In addition, let X be a point of ZNN such that :
n
C
0
X HP(Uj, 0)
j 1
between R X0 ,V and Fr ZNN j .
Proof
It means that :
n
Let Fj be the point
0
X HP(Uj, 0) C )
j 1
0
Given that C = ZNN, it means that
n
of R X0 , V et Fr ZNN j which is none other than HP U j ,0 ,
I j R X 0 ,V , so Ij is the form
X HP(U , 0) C
j 0
j 1
Ij X0 jV with j 0
Similarly
I HP U j ,0 ,
Hence the proposal :
So we check the equation :
U j , I 0 ou U j , I j
From where, U j , X 0 , jV 0
0
Proposition 8.07
The research axis is in the nonnegativity zone ZNN only if IN (V) is nonempty. In this case, the exit point I is given by :
U j , X 0 j U j ,V 0
I X0 V ,
xo
Finally, we obtain the equation:
min i
j U j ,V U j , X0
with the condition j 0 .
Based on the results of section 5.2, we can say that the
Or
Proof:
v j
j In V
(8.08)
research axis R X0 ,V leads us outside of ZNNj only if V is oriented outside ZNNj,
that is, if
U j , v 0 , in which case,
Given that R X0 ,V is a totally ordered set, the exit point of I such that verify:
I min I j
j IN V where I X X V
(8.09)
0
i
j 0
Let X
U j , X0
j
U j ,V
0 0
Xi i 1,…, n
(8.06)
The Proof is immediate. The output point I is none other
than the first smallest Ij.
9 CONCLUSION
Through this article, we presented all the art mathematical
i j 0 i
V v i 1,…, n and U , X x0
Ui , V vj
The expression of j becomes :
xo
j
i
vj
(8.07)
object classes required for topogeometric modeling MZ and the mean objectives associated with Topogeometric definitions, as well as the conventional operations and properties of constraints LPP defining hyperplanes, are mentioned.
REFERENCES
Which is good nonnegative
[1] Zionts, S 1965 "Size reduction technology of lineari j
because xo 0 and v 0 .

ZNN exit point following R (X0, V)
programming and Their Applications", PhD Thesis, Carnegie Institute o Technology.
 [2] T. Gal, "Weakly redundant constraints and their impact on optimal post analysis," European journal of operational R
We assume that X0 is in ZNN. Still based on previous results, R X0 ,V leads us out of at least one
ZNNj, that is, there exists a j such that v j 0 noting :
V v j j 1, …, n .
Let IN (V) denote the set of indices j such that vj 0 .
IN V j 1, n tel que v j 0
FSS, vol. 60, pp. 315326 1979.

G. Brearley, G. Mitra, HP and Williams, "Analysis of mathematical programming problems prior to Applying the simplex algorithm," Mathe matical Programming, Vol. 8, pp. 5483, 1975.

N.V. Stojkovic and PS Stanimirovic, "Two Direct methods in linear programming," 'European Journal of Operational Research, Vol. 131, no. 2, pp. 417439 2001.

J. Telgen, "Identifying redundant constraints and implicit Equalities in system of linear constraints," Management Science, Vol. 29, no. 10, pp. 12091222, 1983.

T.Gal, "Weakly redundant constraints and their impact on optimal post analysis," European Journal of Operational Research, vol. 60, pp. 315326 1979.

S. Paulraj, P. Sumathi, "A Comparative Study of Redundant constraints Identification Methods in Linear Programming Problems ", Mathematical Problems in Engineering, Hindawi Publishing Corporation, Article ID 723402, 2.