transition from graphical to algebraic solution

The ideas conveyed by the graphical LP solution lay the foundation for the development of the algebraic 

simplex method . Figure 3.1 draws a parallel between the two methods . in the graphical method . 

the solution space is delineated by the half- spaces.

Figure 3.1

representing the constraint and in the simplex method the solution space  is represented  by m  simultaneous linear equations  and n non-negative  variable .

you will  get to appreciated  the meaning of the information in 

 Figure 3.1  as you proceed with the remainder of the section. 

we can see visually why the graphical solution space has infinity of solution points, but how can we draw  a similar conclusion from the algebraic representation of the solution

space?the answer is that in the algebraic representation 

the number of the equations m is always less than or equal to the number of variable n.1

if m =n,and the equations are consistent .

the system has only one solution ;but if m < n

( which represents the majority of LPs ). then the system of equations again of 

consistent will yield infinity  of solutions . 

LP solution space in Equation Form

For the sake of standardization . the algebraic representation of the LP
solution Space is made under two condition:

1. All the constraints ( with the exception of the nonnegativity restrictions ) are equations with
a nonnegative right-hand side .
2- All the variables are Nonnegative .

Converting Inequalities into Equations
in(≤) constraints the right-hand side  can be thought of as representing the limit on the availability of a resource in
which case the left hand side would represent  the usage of this limited resource by the activities ( variables) of
the model. the difference between the right hand side and the left hand side of the (اق من) constraints thus the unused
or slake amount of resource.

To convert a ( ≤  ) inequality to an equation a nonnegative slake variable is added to the left-hand side of the
constraints . 'For example in the reddy mikks model ,

the constraints associated with the use of raw material M1 is given as

   6X₁  +     4X₂   ≤ 24

defining s_{1  as the slak or unused amount of M1 ,the constraint can be converted to the following equation}                                                      6X₁  +     4X₂   + S_{1 =  24 ,} S₁ ≥  0

next a( ≥) constraint normally sets a lower limit on 

the on the activities of LP model. AS such the amount by which the left hand side exceeds the

minimum limit represents a surplus.

The conversion from ( ≥) to (=) is achieved by subtracting a nonnegative surplus variable from

the left hand side of the inequality .

For example in the diet model ( Example 202-2 ) , the constraint representing the 

minimum feed requirements is given as  X₁  +     X₂   ≥  800

Defining  S_{1   as the surplus variable, the constraint can be converted to the following eqution} 

X₁  +     X₂   - S_{1 =  800 ,} S₁  ≥   0

Note importantly that the slack and surplus variable , _{s1 and S1}

_{are always  non-negative.}

The only remaining requirement is for the right-hand side of the resulting equation to be non-negative.

The condition can always be satisfied  by multiplying both sides of the resulting equation by -1 where necessary.

For example  the constraint   -X₁  +     X₂   ≤   -3

is equivalent to the equation 

  -X₁  +     X₂  + S_{1  = -3,}S₁ ≥   0

Now multiplying both sides by -1 will render a non-negative right-hand side as desired that is

X₁  -     X₂   - _s1  =3

Example 2.2-2 This example solves the reddy mikks Model

the simplex method

the graphical method  shows that the optimum LP solution is always associated 

with a corner point of solution space.

this result is key to the development of the general algebraic simplex method for solving any LP

model.

The transition from the geometric corner-point solution to the simplex method entails a computational
procedure that determines the corner points algebraically.

This is accomplished by first converting all the inequality constraints into equations and then manipluating 
the resulting equations in systematic manner.

A main feature of the simplex method is that it solves the LP in iterations.

Each iteration moves the solution to a new corner point that has the potential
to improve the value of the objective fuction .

The process ends when no further improvements can be realized .

The simplex method involves tedious and voluminous computations .

Which makes the computer  an essential tool for solving LP Problems.

The computational rules of the simplex method are thus designed to facilitate automatic computations.