Answer to Question #235314 in Operations Research for mona

Question

Solve the following problem by simplex method and check for alternative solution. If possible,

find the alternative solution also. Does this problem has infinite number of solutions ?

Maximize Z = 4x₁ + 10x₂

Subject to

2x₁ + x₂ ≤ 10

2x₁+ 5x₂ ≤ 20

2x₁ + 3x₂ ≤ 18

where x₁, x₂ are unrestricted in sign.

Answer 1

Solution:

Max Z=4x1+10x2 subject to

2x1+x2≤10

2x1+5x2≤20

2x1+3x2≤18 and 

x1,x2 unrestricted in sign

Since x1,x2 are unrestricted in sign, introduce the non-negative variables x1′,x1′′,x2′,x2′′

so that x1=x1′-x1′′,x2=x2′-x2′′;x1′,x1′′,x2′,x2′′≥0.

The standard form of the LP problem becomes:

Max Z=4x1′-4x1′′+10x2′-10x2′′ subject to

2x1′-2x1′′+x2′-x2′′≤10

2x1′-2x1′′+5x2′-5x2′′≤20

2x1′-2x1′′+3x2′-3x2′′≤18 and 

x1′,x1′′,x2′,x2′′≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropriate

1. As the constraint-1 is of type '≤' we should add slack variable S1

2. As the constraint-2 is of type '≤' we should add slack variable S2

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables

Max Z=4x1′-4x1′′+10x2′-10x2′′+0S1+0S2+0S3 subject to

2x1′-2x1′′+x2′-x2′′+S1=10

2x1′-2x1′′+5x2′-5x2′′+S2=20

2x1′-2x1′′+3x2′-3x2′′+S3=18 and 

x1′,x1′′,x2′,x2′′,S1,S2,S3≥0

Since all Zj-Cj≥0

Hence, optimal solution is arrived with value of variables as :

x1′=0, x1′′=0, x2′=4, x2′′=0

Max Z=40

Since, we get one optimal solution, only one solution exists, no alternative solution is there.

It has just one solution.