Chapter 4, Problem 27RP

Explanation of Solution

Linear Programming (LP) formulation:

• The following example of LP is to show that it has more than one optimal solution.
• It also contains nondegenerate basic feasible solution and there is non-basic variable in row 0 with a zero coefficient.
  • max z=6x₁+4x₂
• Such that
  • $x_1+2x_2\le 16$
  • $3x_1+2x_2\le 24$
  • $x_1,x_2\ge 0$
• Solving by the simplex method, the initial table is,

		cj	6	4	0	0	Ratio
cj	xj	Bj	x1	x2	S1	S2	$\left(\frac{B_i}{x_1}\right)$
0	S1	16	1	2	1	0	16
0	S2	24	3	2	0	1	8
		$z_j-c_j$	-6	-4	0	0

• Here x₁ will enter as it is the greatest negative value