Topo-Geometric Model MZ: Feeded Objects

Topo-Geometric Model MZ: Feeded Objects

Andrianarizaka Marc Tiana,

Doctoral School in Engineering and Innovation Science and Technology (ED-STII)

Doctoral Research Team for Cognitive Science

and Application (EAD-SCA) University of Antananarivo, MADAGASCAR

Robinson Matio,

Doctoral School in Engineering and Innovation Science and Technology (ED-STII)

Doctoral Research Team for Cognitive Science and

Application (EAD-SCA)

University of Antananarivo, MADAGASCAR

Andriamanohisoa Hery Zo,

Doctoral School in Engineering and Innovation Science and Technology (ED-STII) Doctoral Research Team for Cognitive Science and Application (EAD-SCA)

University of Antananarivo, MADAGASCAR

Summary : The Topo-geometric 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 Topo-geometric 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 Topo-geometric 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 Topo-geometric model MZ, algorithm.

1 INTRODUCTION

This paper constitutes the basis of the Topo-geometric

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 Topo-Geometric MZ model published in MADA-ETI, ISSN 2220-0673, Vol.2,

2016, www.madarevues.gov.mg which develops the basic concept of Topo-geometric 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 half-spaces 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

1. 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 unknown-real 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)

2. Postulate

   In the topo-geometric 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 non-negativity constraints.

     Definition 3.01: decision-action-point-vectors We call decision-action any n-tuple :

     x1

     However, following a presolved analysis, it may be possible that n changes, which completely modifies the LPP problem.

1. OPERATIONS ON ACTION-DECISIONS

Given an LPP problem, according to definition 3.01, a decision is represented by a point in the decision-action 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 stock-decisions based on existing stock-decisions

2

x Whose

x

n

x1, x2 ,…, xn are elements of

The search for other decision-actions 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 decision-action 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 decision-action benchmark, the positive orthonormal geometric benchmark, noted :

O,U ,U , ….,U

1. Amplifier of an action decision

   Let the decision-action 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

2. Addition of two decision-actions

   Let X0 and X1 be two decision-actions 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 action-decisions. Let the decision-actions 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

3. Search axe defined by decision-action Xo and direction the vector decision-action V

   Let X0 and V be action-decisions.

   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 decision-action X0, and a given search direction V, one can search the points in the universe of

1. THE TECHNICAL CONSTRAINTS

   In practice, any action-decision always has an impact. In the field of linear programming, two categories of impacts can be distinguished :

   • Impact-performance.

   • Resource impacts.

     In this study, we only deal with the impact-resources.

     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 half-space delimited by the noted affine hyperplane. HP (A, b) defined by:

     1. Plan of research starting from a decision-action X0 and directions V1 and V2

        HP (A, b) = X n /

        A, X

        b

        (5.02)

        Let X0 be a decision-action point and V1 and V2 two decision-action 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 action-decision it is linked to a

        given resource and allows to calculate the impact of an action X decision on this resource

2. The constraints of non-negativity

The non-negativity 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 :

1. Research of X0 direction and V1, V2… Vk, vectors decisions

Let X0 be a decision-action 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 non-negativity constraint can also be considered as a resource constraint delimited by ZR Ui , 0 called non-negativity zone ZNNi.

However the combination of all non-negativity constraints has a particular geometric meaning that we call " non- negativity cone ".

1. non-negativity cone

   0

   We call non-negativity cone noted C the cone of search

   from point-decision 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

2. Non-negativity 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 non-negativity 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

3. Non-negativity axes

   For all i = 1, 2… n, we call non-negativity 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.

1. 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.

2. 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 point-decisions and point-vectors have already been seen. Therefore, only the following points will be dealt with:

• The relation between a decision-point 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 point-decision is represented with a point, and a zone of technical constraints is represented by a half-space, a set of decision-point, 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 decision-point 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 decision-point.

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.

  1. 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

1. 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.

2. 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.

1. 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

1. 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

2. 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 non-empty 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

      1. 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 :

      1. 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.

    1. Where X0 is outside ZCTi and where V is inward ZCTi

    The equation :

    1. 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.

    2. 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).

    1. 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

    2. Where X0 is on the ZCTi border and where V is parallel oriented to

    HP (Ai, bi)

    The equation :

    1. 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 .

    2. 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 non-negativity 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 search-plane 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

1. Frontier of the ZNNi non-negativity 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 non-negativity 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 non-negativity.

   Note further that

   MCNNj HP U j ,0

   So

   MCNN j Fr ZNN j

2. 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 non-negativity zone ZNN only if IN (V) is non-empty. 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 topo-geometric modeling MZ and the mean objectives associated with Topo-geometric definitions, as well as the conventional operations and properties of constraints LPP defining hyperplanes, are mentioned.

   REFERENCES

   Which is good non-negative

   [1] Zionts, S 1965 "Size reduction technology of linear

   i j

   because xo 0 and v 0 .

3. 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. 315-326 1979.

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

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

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

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

5. 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.