Linear Optimization in Applications

7. Goal Programming Formulation

GOAL PROGRAMMING FORMULATION 7.1 linear Programming Versus Goal Programming 10 previous chapters, all examples involvcd the maximization or minimization of onc singlc objective undcr conslrainls. In goaJ programming, il is possible for us 1 0 optimize more than one obj血泊 ve in a problem. ln facI, an ordin訂y linear programming modcl (with only onc objeclivc) can also be formulated as a goal programming model. The 伍的t example in this chapter will iIlustrate this. From the second example onward, we will see how multiple obj血lives are optimizcd under a number of constraints Example 7.1 A fumilure cQmpany sells two types of annchairs, the standard and the deluxe Each of Ihese armch割的 requires time in the woodwork and Ihe painting departments. The markcting manager of the company indicatcs that 00 more than 50 deluxe anndmirs can be sold in the next week and is not sure about the situation for standard amlchairs. The unit prorit for the standard and deluxe annchairs are $4叩，nd 自由問pectively. A standard annchair requires 1 man hour ìn the w ∞dwork d叩 artment 祖d 1 man-hour in the painting department A deluxc armchair, on the other hand, requires 2 個d 1 man-hours in thesc re，p凹tive departmcnts. The number of man-hours in the woodwork department is limited to 120 and that in painting 10 80 in the week. These are regular working hours avaìlable. Fonnulate the problem as (的 a Iinear programming model, and (b) a goal programming model 的 max imize the company's profit in that week $olution 7. 1 Let XI = number of standard annchairs pr. 吋uced X2 = number of delux巳 armchairs produced 118 Linear Optimization in Applications (a) Linear programming model: Max 400x1 + 500x2 subject to X1 + 2x2 三 120 X2 至 50 (man-hours, woodwork) (man-hours, painting) (m訂ket) X1 + X2 三三 80 X.. X~ ~。 l' ....2 The above model has a solution that X 1 40 Xz = 40 maximum profit 狗，000 (b) Goal programming model: Instead of formulating a linear programming model as shown in (吋 above， the problem can be formulated as a goal programming model. In order to do 鉤， we must set a target for our profit goal (i.e. the only goal in this problem). This target is an arbitrary large figure, say, $100,000 in this case. We can now define our goal in the form of a constraint as fol1ows: 400x1 + 500x2 + dl- . dl+ = 100,000 where dl - = under-achievement ofprofit goal in $ dl " = over-achievement ofprofit goal in $ Our objective is to minimize the amount of under-achievement of the profit goal and we do not care about the over-achievement (see notes below). We have: Mindl subject to 400x1 + 500x2 + dl- - dl+ = 100,000 X 1 + 2x2 三 120 、 、 ' ， ' ， ••• A J S E 、 (1) (2) Goal Programming Formulation Xl + X2 X2 三 80 至 50 X}, X2, d1-, d1+ 去。 The solution for this goal programming model is: d1- = 64,000 Xl = 40 X2 = 40 dt = 0 Readers should comp訂e this solution with the one in part (a). 且湛藍S 119 (3) (4) Two important notes in formulating the objective function of a goal programming model 訂e: 1. If over-achievement of a certain goal is acceptable, the positive deviation variable (d/) from the goal should not be included in the Qbjective functiQn. The above example is of such a case. 2. If under-achievement of a certain goal is acceptable, the negative deviation variable (dj-) from the goal should not be included in the Qbjectjye functjQn. We will see this in later examples. Examples 7.1 (b) has shown the formulation of a simple goal programming problem. However, the usual practice in goal programming is that we always write “=" signs in constraints instead of “豆 or “這"signs. The model in example 7.1 (b) can therefore be written as: 弘1ind 1- (0) subject to 400x1 + 500x2 + dl" - dl+ = 100,000 (1) x1 + 2x2 + d2 " = 120 (2) x1 + x2 + d3 " = 80 (3) x2 + d4 " = 50 (4) 120 Línear Optimization 的 Applications Xl , X2, d1-, d1+, d2-, d3-, <4- ~ 0 where d2- under-achievernent of woodwork rnan-hours d3- = under-achievernent of painting rnan-hours d4- under-achievernent of the sales of deluxe arrnchairs The solution for this rnodel is exact1y the sarne as that for the previous rnodel (i.e. the one without d2\ d3- and d4-). It should be noted that d2+，也+ and d/ 缸e not in the constraints because 120, 80 and 50 are rnaxirnurn possible values and there cannot be over-achievernents. These are called “absolute goals". 7.2 Multiple Goal Problems In the previous exarnples, there was only one goal to be optirnized. Now, let us see how rnultiple goals can be optirnized. Example 7.2 This exarnple is a continuation of Exarnple 7.1. It is possible to increase the nurnber of rnan-hours available by working overtirne. The rnanagernent of the cornpany, however, wishes that the overtirne hours should be within 80 hours in the two departrnents as far as possible. Furtherrnore, the rnanagernent establishes a list, in the order of decreasing priority, on goal attainrnent as follows: Priority 1 total overtime hours should be within 80 as f:缸 as possible; Priority 2 production of deluxe arrn chair should be 1irnited to the sales forecast but this lirnited rnarket should be as saturated as possible; Priority 3 a target profit of $100,000 should be achieved as f;訂 as possible; Priority 4 overtirne hours should be avoided as far as possible. Forrnulate this problem as a prioritized goal prograrnrning rnodel. Solution 7.2 Prjority 1 (1 st goal) : total overtirne hours should be within 80 as f;訂 as possible. So, we rnust add the following constraint to the set of constraints in Exarnple 7.1: Goal Programming Formu/afion 121 AU OO -- + r3 AU ' 、 J AU + + 句 3 .G + + 勻 ， & •• ', dH pv hu w (5) d/ = over-achievement of woodwork man-hours (i.e. overtime for woodwork) d3+ = over-achievement of painting man-hours (i.e. overtime for painting) ds- under-achievement ofthe 1st goal d/ = over-achievement ofthe 1st goal and constraints (2) and (3) will change to: x1 + 2x2 + d2- - d/ 120 x1 + x2 + d3- - d/ = 80 (2) (3) Note that these two are no more absolute goals because overtime is now possible. Moreover, the pt goal is to minimize d/. We will put this as priority 1 in the objective function. Prioritv 2 (2nd goal.ì : production of deluxe armchair should be limited to the sales forecast but this limited market should be as saturated as possible. For the 2nd goal, no additional constraint is necess訂y. However, since the 2nd goal is to minimize d4-, we will include it as priority 2 in the objective function. Prioritv 3 (3吋 goal.ì :achieve profit target of $100,000. The 3rd goal also needs no additional constraint, but we have to include a priority 3 that d1- be minimized in the objective function. Prioritv 4 (4th goal) : avoid overtime. Again, the 4出 goal needs no additional constraint, but we have to minimize (d2+ + d3+) and inc1ude it as priority 4 in the objective function. 122 Linear Optimization in Applications We can now summarize the goal programming model as follows: Min P\ds+ + P2d4- + P3d\- + P4(d2+ + subject to 400x 圳\ + 500X2 + d 向\- - d 也\+ = 100,000 自 m ………咀一…呵~…" x\ + 2X2 + d2- - d2+ = 120..._..- …仰的 “ 叮叮叮…一...。…_.__._--一一…叮叮叮叮…--_._-一…一 (2) 、 ‘ 圖 ， ' ， nu / a ‘ 、 X\ + X2 + d3- - d3 + = 80 ……_._.-.-...._._....-..一_.-._._--……一…一一一一一一.."…… (3) X2 + d4- 50 ...... (4) d2++ d3+ + ds" - ds+ = 80..... (5) X\, X2, d\-, d\\d2-, d2+, d3-, d3+, d4-, ds-, ds+去。 The solution for this model is: x\ 65 X2 = 50 d\- = 49000 d2+ = 45 d3+ = 35 other deviation variables = 0 In solving a prioritized goal programming model, the goal of the highest priority must firstly be optimized to the fullest possible extent. When no further improvement is possible in the highest goal, we then optimize the second highest goal, and so on. Goals of lower priorities must not be optimized at the expenses of goals of higher priorities. The detailed method for solving a prioritized goal programming model will be discussed in Chapter 8. 7.3 Additivity of Deviation Variables When two goals are assigned the same priority, we must make sure that the units of measure of the goals are commensurable. In other words, goals can be assigned to a same priority level only if they can be expressed in terms of a common unit of measure like priority 4 in Example 7.2; if not, some conversion has to be devised so that the addition will make sense. This can be Goal Programmíng Formulatíon 123 accomplished by multíplying the priority coefficient by a relatíve weightíng factor. The following example will illustrate this. Example 7.3 This example is a continuation of Example 7.2. Assume that the number of priority levels is reduced from four to three such that the profit göal (originally goal 3) and the avoidance of overtime goal (originally goal 4) are both assigned a priority of 3. Moreover, suppose that the marginal cost of working one hour overtime in the woodwork dep旺tment is $75 and that in the painting department is $65. Modify the model formulated in solution 7.2 to a new model according to the new conditions. $olution 7.3 So, priorities 1 and 2 remain the same. Priority 3 now is to achieve a profit target of $100,000 and to avoid overtime hours. These two things are not of a common unit of measure, that is, dollars cannot be added to hours in a meaningful sense. So, some conversion is necessary before these items can be added. Since the marginal cost of working one hour overtime in the woodwork dep缸tment is $75 and that in the painting department is $65, one hour overtime in woodwork and that in painting are equiva1ent to $75 and $65 respectively in profits. The coefficients in the objective function for goa13 will change to (d1-+ 75d2+ + 65d3+) because it is sensible to have profit added to profits. Therefore, the new goal programming model is: Min P1ds+ + P2d4- + P3(d1-+ 75d2+ + 65d3+卜 一一一一 (0) subject to 400Xl + 500X2 + d1- - d1+ = 100,000 妞.'………一"……一個_....-曰“ ……(1) Xl + 2X 2 + d2- - d2+ = 120 ……一一一……一一_...-一………………一……… (2) Xl + X2 + d3- - d/ = 80 一一 X2 + d4- = 50 (3) - (4) 124 Linear Optimization in Applications d2++ d3+ + d5- - d5+ = 80 (5) x\, X2, d\-, d\+, d2-, d2+, d3-, d3+, <4-, d5-, d5+ 這 O The solution for this model is: x\ = 65 X2 = 50 d\- = 49,000 d2+ = 45 dt =35 other deviation variables = 0 The additivity problem is not confined to di旺'erent units of measure in a given priority. Sometimes, conversions have to be made even if deviation variables are of the same units of mesure in the same priority. The next example (i.e. Example 7.4) wiU illustrate this and readers should note priority 1 of the example. Example 7.4 A company produces two products 1 and n. The estimated sales for the next month are 24 units and 8 units of products 1 and n respectively. Each unit of products 1 and n contributes a profit of $4,000 and 5,000 respectively. The man-hours needed to produce each unit of products in two work centres A and B are given in the following table. The man-hours available of the two work centres are also given in the table. Man-hours per unit Man-hours available H Monthly regular time Monthly overtime I Work centre A 32 56 768 376 Work centre B 10 15 300 80 The management of the company has the following priority of goals: Goal Programm的'g Formulation 125 Pl: 1imit the production to the sa1es forecast but the limited market should be as saturated as possible; P2 : avoid the under-utilization of regular man-hour capacity to maintain stable employment; P3 : limit overtime operation as f;訂 as possible. Formulate the problem as a goa1 programming model for determining the optimal number of each product to be produced in the next month. Solution 7.4 Let Xl = number of product 1produced for the next month X2 = number of product nproduced for the next month QQ.aLl: limit the production to the sales forecast but the 1imited market should be as saturated as possible. Goal 1 is an absolute goal and can be expressed by the following two constramts: x[ + d1- = 24 … X2 + d2- = 8 .._where d1- = under-achievement in monthly production ofproduct 1 d2- = under-achievement in monthly production of product n (1) (2) The objective is to minimize P1(4dl - + 5d2-). Weightages 4 and 5 are used because the management has a greater desire to minimize d2- than d1- since the profits for each unit of product 1and that for product nare in the ratio of 4:5. QQ益主: avoid the under-utilization of regular man-hour capacity. Goal 2 can be expressed by the following two constraints: 32xl + 56x2 + d3- - d3+ = 768 一一一一一…一一一一一一一一一………一一…… (3) 126 Linear Optimization in Applications 10Xl + 15x2 + d4- - d/ = 300 (4) where d3- = under-utilization of regular rnan-hour capacity of work centre A d3+ rnan-hours of overtirne in work centre A d4- under-utilization of regular rnan-hour capacity of work centre B d4+ rnan-hours of overtirne in work centre B The objective is to rninirnize P2(也- + ~-) G:ruù...3. : lirnit overtirne operation as far as possible. Goal 3 can be expressed by the following two constraints: d3+ + ds- - ds+ = 376ω (5) d/ + d6- 峙 d6+ = 80 ““一一一一一一一一一一一一一一一一一一一一 (6) where ds- under-utilization of overtirne capacity in work centre A ds+ over-utilization of overtirne capacity in work centre A dι= under-utilization of overtirne capacity in work centre B d6+ = over-utilization of overtirne capacity in work centre B The objective is to rninirnize P3(也+ + d6+). The following is a surnrn訂y of the goal prograrnrning rnodel: Min P1(4d1- + 5d2-) + P2(d3- + d4-) + P3(ds+ + d6+) -“ …_....-…間一 (0) subject to X1 + d1- = 24 .......-一一一一。"一…一一一一一…一一 一 (1) X2 + d2- = 8 月一 32xl + 56x2 + d3 ‘ - dt = 768 一一一一 - (2) (3) 10Xl + 15x2 + d4- - d/ = 300 叫 一…"“……一…但巴巴… (4) d3+ + ds- - d/ = 376 一一一一 一一一一 一 (5) d/ + dι - d 6 + 80 叮 叮叮叮。"…。M'_'M'_…一個一個-_..._._-…………… … "…-…一…一…… (6) Xl ，肉， d1-，也-， d3\ dt, d4-, d/, ds-, ds+，也\d6+ ~ 0 Goal Programming Formulation The solution for this model is: x] = 24 x2 = 8 d/ = 448 d4 + 60 ds+ 72 d戶 20 all other deviation variables 0 7.4 Integer Goal Programming 127 As in linear programming models, goal programming may involve decision variables which are of integers or zero-one values. The next example will show the formulatìon of such kìnd ofproblems. Example 7.5 A company's management is considering undertaking three plans 1, II and III. A plan must be either selected or rejected (i.e. partial adoption of a plan is not allowed). The plans are of two ye缸s duration and the budget allowed for each year appears to be insufficient to support all the three plans. The net profit, market share and the cost of each plan are given in the following table: Plan N(eutnpirtos)fit Market share Cost in Year 1 Cost in Year 2 (units) (units) (units) 8 5 7 5 II 4 3 2 3 III 9 3 5 4 The allowable total budget for year 1 is 10 units, while that for year 2 is 9 units. It is required that these budget levels should not be exceeded. The company's management considers that profit maximization is most important. The second important consideration is that the market shares should be within the limits as 128 Linear Optimization in Applications f缸 as possible. Formulate the problem as an integer goa1 programming model for determining which plan(s) should be adopted. Solution 7.5 ， 且 n u ' A A U ， E a - - 、 ， E S E - 、 == A 弓 ， h xx h plan 1 is adopted plan 1 is not adopted plan 11 is adopted plan 11 is not adopted t a 仇 υ '.2.t = 句 3 x plan 111 is adopted plan 111 is not adopted Bl!d斟 There are two absolute goa1s: 7x\ + 2X2 + 5X3 + d\- = 10 .5x \ + 3X2 + 4X3 + d2- = 9 where d\- = under-achievement of total budget in ye缸 l d2- = under-achievement of tota1 budget in ye缸 2 (1) (2) fuúï1 The profit goal can be expressed as: 8x\ + 4X2 + 9X3 + d3- - dt = 21 一一一一一一一一一一一一一…一 (3) where d3- = under-achievement of profit goal d3+ over-achievement of profit goa1 The objective is to minimize P\d3-. The RHS value of 21 in constraint (3) is the sum of the net profits of the three plans. Market share The market share can be expressed as: 5x\ + 3X2 + 3X3 + d4- - d/ = 11 where (4) Goal Programming Formulation <4- = under-achievement of market share d4+ = over-achievement of market share 129 The objective is to minimize P2<4+. The RHS value of 11 in constraint (4) is the sum of the market sh訂的 of the three plans. The following is a summ訂y of the integer goal programming model: Min P1d3- + P2d/ 一 (0) subject to 7Xl + 2X2 + 5X3 + d1- = 10 5Xl + 3X2 + 4X3 + d2- 9 (1) (2) 8Xl + 4X2 + 9X3 + d3- - dt = 21 … (3) 5Xl + 3X2 + 3X3 + <4- - <4+ 11 …一…一……一一一一……………一 (4) X1, b X3={;;dl\ d2 - , d3-，趴缸，也+言。 The solution for this model is: Xl = 0 X2 = 1 X3 = 1 d1 - = 3 d2 2 d3 - = 8 <4- = 5 all other deviation variables = 0 Exercise 1. A company runs a production line with 1000 man-hours of regular production time available per day. Overtime may be worked. Two products, 1 and IT, are to be produced. Each product requires 2 man-hours of production time per item. Sales forecast reviews that a maximum of 250 130 Linear Optimization in Applications items of product 1 and 350 items of product 11 can be sold in a day. The contribution of 1is $20 per item and that of 11 is $15 per item. The management has set three goals in order of priority: P1 : avoid under-utilization of regular production time; P2 : sell as many items as possible; P3 : reduce overtime. Formulate a goal programming model to optimize the production of 1 and 11 using decision variables x1 and X2 as the number of products 1 and 11 respectively produced per day. 2. A factory manufactures two types of products 1 and 11. Type 1 requires 2 man-hours in the assembly line while type 11 requires 4 man-hours. Marketing surveys predict that no more than 30 units of type 1 and 20 units of type 11 should be produced in the next week. The net profit from type 1is $800 each and th前 from type 11 is $1,200 each. The regular-time assembly operation is limited to 96 man-hours in the next week. The factory manager has the following goals arranged in the order of decreasing priority: P1 : the number of products should never exceed the predicted market demand; P2 : the total profit should be maximized; P3 : the overtime operation of the assembly line should be minimized; P4 : the limited market should be as saturated as possible (i.e. sell as many products as possible). Formulate a goal programming model which will satisfy the factory manager's goals and optimize the number of products produced in the next week. ...