Question

$\text{Consider the linear Programme (LP)}$

$\text{Max 4x + 6y}$

$\text{Subject to :}$

$3x+2y\le 6$

$2x+3y\le 6$

$x,y\ge 0$

After introducing slack variables s and t, the initial basic feasible solution is represented by the table below (basic variables are $\text{s = 6 and t = 6,}$ and the objective function value is 0).

	-4	-6	0	0	0
s	3	2	1	0	6
t	2	3	0	1	6
	x	y	s	t	RHS

$\text{After some simplex iterations, the following table is obtained}$

	0	0	0	2	12
S	5/3	0	1	-1/3	2
y	2/3	1	0	1/3	2
	x	y	s	t	RHS

$\text{From this, one can conclude that}$

• A. the LP has an optimal solution that is not unique
• B. the LP has a unique optimal solution
• C. the LP is infeasible
• D. the LP is unbounded

Answer 1

The correct option is A the LP has an optimal solution that is not unique

$\text{Method I:}$

Since zero has appeared in the optimal solution below a non-basic variable, it means there are alternate solutions. The LP has an optimal solution that is not unique.

$\text{Method II:}$

Given problem can be modified in terms of linear programming problem as,

$\text{Max z = 4x + 6y}$

$3x+2y\le 6...\left(1\right)$

$2x+3y\le 6...\left(2\right)$

$x,y\le 0$



$\text{At point B(6/5, 6/3),}$

$Maxz=4\times \frac{6}{5}+6\times \frac{6}{5}=12$

$\text{At point C(0, 2)}$

$\text{Max z = 4 × 0 + 6 × 2 = 12}$

$\text{Points to Remember:}$

It is also important to note that maximization z and constraint (2) $2x+3y\le 6$ have the same slope.

So we can also say that linear programing has multiple optimal solutions.