Infeasible Solution

Infeasible Solution
In the next example we will illustrate how to identify the infeasible solution using simplex method.
Example
Consider the following problem.
Minimize 200 x1 + 300 x2
Subject to:
2 x1 + 3 x2 ? 1200
x1 + x2 ? 400
2 x1 + 3/2 x2 ? 900
x1, x2 ? 0
Solution
Since it is a minimization problem we have to convert it into maximization problem and introduce the slack, surplus and artificial variables.
Minimize -200 x1 - 300 x2
Subject to:
2 x1 + 3 x2 – S3 + a6 = 1200
x1 + x2 + S4 = 400
2 x1 + 3/2 x2 – S5 + a7 = 900
x1, x2, S3, S4, S5 , a6 , a7 ? 0
Here the a6 and a7 are the artificial variables. We use two phase method to solve this problem.
Phase I

Maximize - a6 – a7
Subject to:
2 x1 + 3 x2 – S3 + a6 = 1200
x1 + x2 + S4 = 400
2 x1 + 3/2 x2 – S5 + a7 = 900
x1, x2, S3, S4, S5 , a6 , a7 ? 0
The calculation of simplex procedures and tables are as follows:



Note that zj - cj ? 0 for all the variables but the artificial variable a7 is still a basic variable. This situation indicates that the problem has no feasible solution.
Exercises:
Q1. A soft drinks company has a two products viz. Coco-cola and Pepsi with profit of $2 and $1 per unit. The following table illustrates the labour, equipment and materials to produce per unit of each product. Determine suitable product mix which maximizes the profit using simplex method.

Q2. Solve the following linear programming problem using two phase and M method.

Q3. Solve the following linear programming problem using simplex method.