Irregular Types of Linear Programming Problems
A25
not part of the basic feasible solution. This means that if some mugs (x_{2}) were produced, we would have a new product mix but the same total profit. Thus, a multiple optimal solu t i o n i s i n d i c a t e d b y a ( o r ) r o w v a l u e o f z e r o f o r a n o n b a s i c v a r i a b l e . z j  c j c j  z j
0 40
s x
1 1
10 30
0 1
5/4 3/4
1 0
 1>4  1>4
z
j
1,200
40
30
0
10
c j  z j
0
0
0

10
0 s_{2 }
Table A25 The Optimal Simplex Tableau
c j
30
0
x_{2 }
s_{1 }
40 x_{1 }
Basic Variables
Quantity
An alternate optimal solution is determined by selecting the non basic variable with c_{j } z_{j }= 0 as the entering variable.
To determine the alternate endpoint solution, let x_{2 }be the entering variable (pivot column) and select the pivot row as usual. This selection results in the s_{1 }row being the pivot row. The alternate solution corresponding to point B in Figure A5 is shown in Table A26.
Table A26
The Alternate Optimal Tableau
c j
30 40
x
2
x
1
Basic Variables
z j
c j  z j
8
0
24
1
Quantity
40 x_{1 }
1,200
40
0
1
4/5
1>5
0
3>5
2/5
30
0
10
0
0
 10
30
0
0
x_{2 }
s_{1 }
s_{2 }
An Infeasible Problem Another linear programming irregularity is the case in which a problem has no feasible solution area; thus, there is no basic feasible solution to the problem.
An infeasible problem does not have a feasible solution space.
An example of an infeasible problem is formulated next and depicted graphically in Figure A6:
maximize Z = 5x_{1 }+ 3x_{2 }
subject to
x 1 , x 2 Ú 0 x 2 Ú 6 x 1 Ú 4 4 x 1 + 2 x 2 … 8
The three constraints do not overlap to form a feasible solution area. Because no point satisfies all three constraints simultaneously, there is no solution to the problem. The final simplex tableau for this problem is shown in Table A27.
An infeasible problem has an artificial variable in the final simplex tableau.
T h e t a b l e a u i n T a b l e A  2 7 h a s a l l z e r o o r n e g a t i v e v a l u e s i n t h e r o w , i n d i c a t i n g t h a t c j  it is optimal. However, the solution is x_{2 }= 4, A_{1 }= 4, and A_{2 }= 2. Because the existence of artificial variables in the final solution makes the solution meaningless, this is not a real z j