Linear Optimization in Applications

Appendix D. Examples of Special Cases

ExamDle1 No feasible solution Maximize Z 5Xl + 6X2 subject to Xl + X2 三 7 Xl 三 4 X2 :5 2 Xl , X2 ;::: 0 (0) (1) (2) (3) If the graphical method is used to solve this problem, one will find th剖 no feasible space can be drawn (see Section 1.2.1 of Chapter 1). There is no feasible space that can satisfy all the three constraints. So, this problem has no feasible solution. Ifthe simplex method is used to solve the problem, the initial and “final" tableaus are shown in Figures Dl and D2 respectively. Basic Xl X2 SI S2 S3 A 1 RHS 主且S Variable Cj 5 6 。 。 。 .恥f aij A 1 -M 。 。 。 7 C幻 S2 。 。 。 。 。 4 00 S3 。 。 。 。 。 2 2 Zj 。 。 。 。 。 。 。 Cj - Zj 5 6 。 。 。 -M Fig. D 1 Initial simplex tableau for Example 1 Basic Xl X2 SI S2 S3 A1 RHS Variable Cj 5 6 。 。 。 -M A1 .恥f 。 。 。 3 Xl 5 。 。 。 。 4 X2 6 。 。 。 。 2 ZJ 5 6 。 5 6 -M 32-3M Cj - Zj 。 。 。 -5 -6 。 Fig. D2 “Final" simplex tableau for Example 1 The “final" tableau in Figure D2 is supposed to be the “final" or “optimal" solution because the (Cj - Zj) row has no positive value. However, it can be seen that A 1 remains to be a basic variable. This means that the constraint Xl + X2 主 7 is not satisfied, as a feasible solution should not incur the M penalties. Therefore, when an artificial variable stays as basic and cannot leave to become non-basic, it indicates that there is no feasible solution for the problem. Linear Optimization In Applications 163 Examnle2 Unbounded situation 弓 ， M X F 、 d + x oo -Z430 e E O > 一 -ut2 mdxb M ﹒ 戶 + . r ab--h MUxh7 (0) (1) (2) If the graphical method is used and a graph is drawn, one will see that the feasible space continues without limit in the X2 direction. The objective function therefore can move without limit away from the origin. In this situation we say that the optimal solution is unbounded. If the simplex method is used to solve the problem, the initial and “final" tableaus are shown in Figures 03 and 04. Basic Xl X2 Sl S2 A2 RHS RHS Variable Çj 8 5 。 。 .恥4 aij Sl 。 。 。 。 4 4 A2 -M 。 3 3 月 。 。 。 。 。 。 Cj-勾 8 5 。 。 -M Fig. 03 Initial simplex tableau for Example 2 Basic Xl X2 Sl S2 A2 RHS RHS Variable Cj 8 5 。 。 -M aij S2 。 。 Xl 8 。 。 。 4 00 勾 8 。 8 。 -M 32 Cj-勾 。 5 -8 。 。 Fig.04 “Final" simplex tableau for Example 2 The “final" tableau shown in Fig. 04 shows th到 there is still a positive value in the (Cj Zj ) row, but in the RHS/aij column there is no finite positive value. It means that there is no leaving variable, and the simplex method cannot continue. This indicates an unbounded situation. Examnle J.. Degeneracy Max Z = 10Xl + 8X2 su吋 ect to 5Xl + 3X2 :$; 624 6Xl + 4X2 三 800 2Xl + 3X2 三 480 Xl, X2 ~ 0 (0) (1) (2) (3) 164 Linear Optimization In Applications This example is a modification of Example 1. 1 of Chapter 1. For the above model, all the three resources (storage space, raw material and working hours) are fully utilized at the optimal solution. For such a case, in the final or optimal simplex tableau, there is a basic variable with a zero value (see Figure 05). This corresponds geometrically to the fact that in Figure 1.1 of Chapter 1 three lines are passing through Point A rather than usually two. The phenomenon is known as degeneracy. Basic Xl X2 Sl Variable q 10 8 。 Sl 。 。 。 Xl 10 。 。 X2 8 。 。 ZJ 10 8 。 CJ - ZJ 。 。 。 Fig. 05 Final simplex tableau for Example 3 Examole!... More than one optimal solution Max Z 2Xl + 4X2 subject to Xl + 2X2 三 4 Xl ::; 3 X2 三 l Xl , X2 ~ 0 S2 S3 。 。 -0.9 0.2 0.3 -0.4 -0.2 0.6 1.4 0.8 -1.4 -0.8 RHS 。 48 128 1504 (0) (1) (2) (3) In the above example, when the objective function line moves as far from the origin as possible, it lies along (or it is parallel to) one of the lines bounding the feasible space. The two corner points (Xl = 2, X2 = 1) and (Xl = 3, X2 = 0.5) are optimal solutions, having the same objective function value of 8. If the simplex method...