Consider the system of linear constraints 2x1x2

Consider the system of linear constraints

2x₁+x₂<=100

x₁+x₂<=80

x₁<=40

x₁, x₂>=0

(i) Write the system of contraints in standard form, and determine all the basic solutions (feasible and infeasible).

(ii) Determine the extreme points of the feasible region (corresponding to both the standard form of the constraints, as well as the original version).

Solution

Transform the following LP into the standard form required by the simplex method

2x1 +x2 + S1=100 -------------------equation 1

x1 + x2 + S2=80 -------------------equation 2

Setting x1 , x 2 equal to zero we have .

S1 = 100 and S 2 = 80

Therefore x1 = x 2 = 0, S1 = 100, S 2 = 16

is a basic solution. Since all four variables satisfy the non negativity restrictions, this is a basic feasible solution .

With x1 , S1 non basic variables and

x2 , S 2

basic variables.

Suppose x2 and S1 are set equal to zero ,then

2x1 = 100

x1 + s2 = 80

x1 =50 x2 = 0 s1=0 s2=30