Linear Optimization in Applications

8. Goal Programming Solution

8.1 The Revised Simplex Method as a Tool for Solving Goal Programming Models In this chapter we will see how a goal programming model is solved. The revised simplex method (Appendix B) will be used as the too1. The example given below wi1l i1lustrate the solutioning process. The model formulated in Example 7.2 of the previous chapter is used. Example 8.1 Solve the following goal programming model: Min P1dt + P2d4- + P3dl- + P4 d2+ +肌肉+白白白白白白 的.........._.一 " “ (0) subject to: 400Xl + 500X2 + d1- - d1+ = 100,000 Xl + 2X2 + d2- - d2+ 120 Xl + X2 + d3- - d3+ 80 X2 + d4- = 50 d2+ + d3+ + d5- - d5+ = 80 Xl, X2, d1\ d1\ d2-, d2\ d3-, dt, d4-, d5\ d5+ 三 O Solution 8. 1 (1) ...... (2) 一一一一一一…一一一一一… (3) ............... (4) (5) We will use the revised simplex method (Appendix B) to solve this mode1. The solutioning process will be discussed step by step. 品且i As there are five constraints, there wi1l be five basic variables. The negative deviation variables, dj - , are analogous to slack variables (for absolute goals) or artificial variables (for non-absolute goals) in linear programming models (see Appendix C). In other words, dj - always appe訂 as the basic variables in the initial goal programming tableau. In this example, the initial tableau is shown in Fig.8.1. 132 Linear Optímízatíon ín App1ícatíons Basic X\ X2 d\- d\+ d2 - d/ d3 - d/ d4- ds- d/ RHS RHS Variable Cj O O P3 O O P4 O P4 P2 O P\ aij L d.- P3 400 500 O O O O O O O 100000 d2 - O 2 O O O O O O O 120 d3 - 。 O O O O O O O 80 d4 - P2 O O O O O O O O O 50 ds- O O O O O O O O 80 Cj-高 P4 P3 P2 P\ Fig.8.1 Initial goal programming tableau (a) In ordinary linear programming simplex tableau, we have 月 and Cj . Zj rows 剖 the bottom (see Appendix B). In goal programming, however, we omit the Zj row in order to simplify the tableau. It requires a little more ca1culation in our heads. Moreover, instead of having one Cj -月 row as in linear prograrnming, we now have four rows 丸， P3' P2and P\ ofCj - 系 values arranged in increasing order ofpriority. 坐盟主 We now ca1culate the Cj - Zj values at the bottom of the initial tableau. Zj values, as explained in Appendix B, are products of the sum of Cj times coefficient. Thus, Zj value in the x\ column is 400P3. Cj value in the x\ column is O. Therefore, Cj - Zj value for the x\ column is -400P3. Hence, we put -400 at the P3 row in the x\ column (see Fig. 8.2). 月 value in the x2 column is 500P3 + P2. Cj value in the x2 column is O. Therefore, Cj ﹒見 for the x2 column is -500P3 - P2' Since P2 and P3 denote different priorities, we must list them separately in the P2 and P3 rows for Cj -角­ Consequently, Cj - Zj value is -1 at the P2row and -500 at the P3 row in the x2 column (see Fig. 8.2). Goal Programming Solution 133 For column dt -, 2月 value is P3• Cj value in the dt - column is 尬。 P3. Therefore, Cj -角 is O. Hence, we put 0 value for all the four rows under this column. For column dt+，有叫ue is -P3. Since Cj is 0, Cj - zj is therefore P3. So, we put 1 at the P3 row in the dt+ column. By the similar methodology, we can obtain Cj -有 values of Pt, P2, P3 and P4 rows for a11 the remaining columns. Basic Xt X2 dt - dt + d2 - d2 + d3 - d3 + d4 - ds- ds+ RHS Variable Cj O O P3 O O P4 O P4 P2 O Pt RHS aij dt - P3 400 500 O O O O O O O 100000 ig5E0Q0Q=200 d2 - O 2 O O O O O O O 120 且企 =60 2 d3 - O O O O O O 。 O 80 皇Q = 80 d4 - P2 O G O O O O O O O O 50 ~ 是b ds- O O O O O O O O 80 直Q O =c開 Cj - Zj P4 O O O O O O O O O O P3 -400 -500 O O O O O O O O 100000 P2 O Qj O O O O O O...