Lecture notes, lectures 7 - Goal Programming PDF

Preview

Summary

slides from class...

Description

Go a lPr ogr ammi ng

Chapter 17

Goal Programming Definition 

An extension of LP that permits more than one objective to be stated defined as goals;



Involves “soft” requirements that are represented as goal constraints (goal to be achieved if possible);



Can be formulated as LP and solved by a standard LP solver.

Components 

Economic Constraints



Goal Constraints



Objective Function

Goal Programming Terms 

Deviational Variables represent overachieving or underachieving the desired level of each goal





d+

Represents overachieving level of the goal



d-

Represents underachieving level of the goal

General form of goal constraint:

Decision Variables 

- d+ + d-

=

Desired Goal Level

Objective function minimizes the sum of the weighted deviations from the target values – this is ALWAYS the objective for Goal Programming

Goal Programming Summary 

Multiple objectives



Satisfy rather than optimize



Minimize some function of deviation variables



Two approaches •

Weighted models

•

Ranked models

Goal Programming Steps 

Define decision variables



Define Deviational Variable for each goal



Formulate Constraint Equations





Economic constraints



Goal constraints

Formulate Objective Function

Example 1 – Wilson Doors Company The Wilson Doors company manufacturers three styles of doors – exterior , interior and commercial. Each door requires a certain amount of steel and two separate production steps : forming and assembly. EXTERIORINTERIORCOMMERCIAL AVAILABILITY Steel (lb/door)

4

3

7

9,000 pounds

Forming (hr/door) 2 Assembly (hr/door)2

4 3

3 4

6,000 hours 5,200 hours

$110

$110

Selling price/door$70

Wilson sets the following goals : Goal 1:

Achieve total sales of at least $180,000

Goal 2: Goal 3:

Achieve exterior doors sales of at least $70,000 Achieve interior doors sales of at least $60,000

Goal 4:

Achieve commercial doors sales of at least $35,000

Example 1 – Wilson Doors Company- Formulation dT - = amountbywhi cht het ot alsal esgoali sunder achi eved cht het ot alsal esgoali sover achi ev ed dT + = amountbywhi cht heext er i ordoor ss al esgoali sunder achi ev ed dE- = amountbywhi cht heext er i ordoor ss al esgoali sov er achi ev ed dE+ = amountbywhi dI - =

amountbywhi cht hei nt er i ordoor ssal esgoali sunder achi ev ed

dI + = amountbywhi cht hei nt er i ordoor ssal esgoali sov er achi ev ed dC- = amountbywhi cht hecommer ci al door ssal esgoali sunder achi ev ed dC+ = amountbywhi cht hecommer c i al door ssal esgoali sov er achi ev ed 70E +110I +110C +dT- -dT+

=

180, 000

70E +dE- -dE +

=

70, 000

( ex t er i ordoor ss al esgoal )

110I +dI- -dI +

=

60, 000

( i nt er i ordoor ssal esgoal )

110C +dC- -dC+

=

35, 000

( commer c i aldoor ssal esgoal )

4E +3I +7C

≤

9, 000

( s t eel usage)

2E +4I +3C

≤

6, 000

( f or mi ngt i me)

2E +3I +4C

≤

5, 200

( assembl yt i me)

E,I,C,dT-,dT+,dE -,dE+, dI -,dI+,dC-,dC+

≥

0

( t ot al sal esgoal )

Mi ni mi z et ot alunder achi ev ementofgoal s=dT- +dE- +dI -+dC-

Example 1 – Wilson Doors Company- weighted model Formulating a weighted model using the following weights :

Goal

Weight

1 – Achieve total sales of at least $180,000 2 – Achieve exterior doors sales of at least $70,000

5 1

3 – Achieve interior doors sales of at least $60,000

1

4 – Achieve commercial doors sales of at least $35,000 1

Example 1 – Wilson Doors Company For mul at i onoft heobj ect i vef unct i onf orwei ght edmodel : Mi ni mi z et ot al wei ght edunder ac hi ev ementofgoal s=5dT- +dE- +dI- +dC-

Example 1 – Wilson Doors Company

 Check excel formulation : Wilson Doors.xls

Example 1 – Wilson Doors Company- ranked goal model at i ngar ankedgoalmodel Achi ev et ot alsal esofatl east$180, 000 Achi ev eext er i ordoor ssal esofatl eas t$70, 000 Achi ev ei nt er i ordoor ssal esofatl east$60, 000 Achi ev ecommer ci aldoor ssal esofatl east$35, 000 Achi ev est eelusageofascl oset o9, 000poundsaspossi bl e owerr ank edgoal sconsi der edonl yaf t erhi gherr ank edgoal sar emet: :Goal1

1

:Goal5

2

:Goal s2,3,and4

3

Example 1 – Wilson Doors Company For mul at i onoft heobj ect i vef unct i onf orr ankedgoalmodel :

Newdevi at i onv ar i abl e dS =amountbywhi cht hest eelusagegoali sunder achi ev ed Obj : dE- + dI- +dC- ) dS - )+R3( Mi ni mi z er ank eddevi at i ons=R1( dT- )+R2(

Example 1 – Wilson Doors Company Solution Procedure for ranked goal model: (First Stage)

Obj ect i v ef unc t i on–fi r s tLPmodel –

Mi ni mi z er ankR1dev i at i ons=dT

Obj ect i v ef unc t i on–secondLPmodel Mi ni mi z er ankR2dev i at i ons=dS

–

(Second Stage)

Addi t i onal const r ai nt –

dT = 0 ( opt i malv al ueofr ankR1goal )

Obj ect i v ef unct i on–t hi r dLPmodel –

–

Mi ni mi z er ankR3 dev i at i ons=dE + dI +dC

–

Addi t i onal cons t r ai nt s –

dT = 0 –

dS = 0

( opt i mal v al ueofr ankR1goal ) ( opt i mal v al ueofr ankR2goal )

(Third Stage)

Example 1 – Wilson Doors Company

 Check excel formulation : Wilson Doors2.xls

Example 1 – Wilson Doors Company

 Check excel formulation : Wilson Doors2.xls

Example 1 – Wilson Doors Company

 Check excel formulation : Wilson Doors2.xls

Example 2 - Problem Statement (1 of 3) A mutual fund manager wants to determine level of future purchases to be made in the following categories:

Growth

Income

New issues

Warrants

Expected price appreciation

15%

10%

20%

15%

Loss exposure

20%

5%

30%

40%

2

1

3

1

1%

5%

2%

5%

Av. Holding time (years) Brokerage cost

There is $ 1 mln to invest, and no more than half of the funds may be invested in a single category. The following investment GOALS should be met: Goal 1: total potential loss exposure should be no greater than $200,000; Goal 2: average portfolio holding time should be at least 1.5 years; Goal 3: total brokerage cost should be $15,000, if possible.

Example 2 - LP formulation (2 of 3) Decision variables: G = unknown amount of $ invested in growth category; I = unknown amount of $ invested in income category; NI = unknown amount of $ invested in new issues; W = unknown amount of $ invested in warrants. Goal constraint 1 (Loss exposure) 0.2G + 0.05I + 0.3NI + 0.4W = 200,000 + dev1(up) - dev1(down) Goal constraint 2 (Average portfolio holding) 2G + I + 3NI + W = 1.5*1000000 + dev2(up) - dev2(down) Goal constraint 3 (Total brokerage cost) 0.01G + 0.05I + 0.02NI + 0.05W = 15000 + dev3(up) - dev3(down) G,I,NI,W,dev1,2,3(up),dev1,2,3(down) >= 0 Objective function Min dev1(up) + dev2(down) + [dev3(up) + dev3(down)]

Example 2 - Solution (3 of 3) Growth (G) Solution Obj. function Goal 1 Goal 2 Goal 3

Income New issues (I) (NI) Warrants (W) dev1(up)

Dev1 (down)

Dev2 dev2(up) (down)

dev3(up)

Dev3 (down) LHS

0.2 2 0.01

0.05 1 0.05

0.3 3 0.02

0.4 1 0.05

Objective Cell (Min) Cell Name $L$3 Obj. function LHS

1 -1

1 -1

1

1 -1

Original Value Final Value 0 0

Variable Cells Cell Name Original Value $B$2 Solution Growth (G) 0 $C$2 Solution Income (I) 0 $D$2 Solution New issues (NI) 0 $E$2 Solution Warrants (W) 0 $F$2 Solution dev1(up) 0 $G$2 Solution dev1(down) 0 $H$2 Solution dev2(up) 0 $I$2 Solution dev2(down) 0 $J$2 Solution dev3(up) 0 $K$2 Solution dev3(down) 0

Constraints Cell Name $L$4 Goal 1 LHS $L$5 Goal 2 LHS

1

1

Final Value

Integer 0 Contin 0 Contin 571428.5714 Contin 71428.57143 Contin 0 Contin 0 Contin 1635714.286 Contin 0 Contin 0 Contin 0 Contin

Cell Value Formula 200000 $L$4=$N$4 150000 $L$5=$N$5

Status Slack Binding 0 Binding 0

1

0 0 0 0

RHS

= = =

200000 150000 15000

Example 3 - LP formulation (1 of 3) A fast-food chain is attempting to determine the best location of a new outlet. Management wants to determine the best location for drawing customers from three population centers. Letting (x1, x2) represent the map coordinates of the three population centers, we can show their locations as: Population center 1: Population center 2: Population center 3:

x1 = 2, x2 = 8 x1 = 6, x2 = 6 x1 = 1, x2 = 1

If the new outlet were located at coordinates (x1 = 3, x2 = 2), it would be (3 - 1) + (2 - 1) = 3 km from population center 3 (distance is measured as the sum of the east-west and north-south differences in coordinates). Formulate a goal programming model to determine the location for the new outlet that will minimize the total distance from the three population centers. Do not solve it.

Example 3 - LP formulation (2 of 3) Decision variables: X1 = unknown coordinate “x1” of a new center; X2 = unknown coordinate “x2” of a new center. Center 1 X1 = 2 + dev1(up) - dev1(down) X2 = 8 + dev2(up) - dev2(down) Center 2 X1 = 6 + dev3(up) - dev3(down) X2 = 6 + dev4(up) - dev4(down) Center 3 X1 = 1 + dev5(up) - dev5(down) X2 = 1 + dev6(up) - dev6(down) All decision variables are non-negative Objective function MIN dev1(up) + dev1(down) + dev2(up) + dev2(down) + dev3(up) + dev3(down) + dev4(up) + dev4(down) + dev5(up) + dev5(down) + dev6(up) + dev6(down)

Example 3 - Solution (3 of 3)

Example 4 - LP formulation (1 of 3) A company manufactures four models of the lawn mower and in the final part of the manufacturing process there are assembly, polishing and packing operations. For each model, the time required for these operations is shown below (in minutes) as is the profit per unit sold. Model

Assembly

Polish

Pack

Profit ($)

1 2

2 4

3 2

2 3

150 250

3

3

3

2

300

4

7

4

5

450

Suppose that the company is free to decide how much time to devote to each of the three operations (assembly, polishing and packing) within the total allowable time of 210000 minutes. In order to take full advantage of new corporate taxation policy, a company plans to achieve a profit of at most $200,000. At the same time, in order to establish its presence in the market niche, it wants that at least $85,000 of its profit is derived from selling models # 3 and 4. How many of each model should the company make per year in order to satisfy these goals? Formulate a goal programming model. Do not solve.

Example 4 - LP formulation (2 of 3) Variables Let : xi be the number of units of model i (i=1,2,3,4) made per year Tass be the number of minutes used in assembly Tpol be the number of minutes used in polishing Tpac be the number of minutes used in packing where xi >= 0 i=1,2,3,4 and Tass, Tpol, Tpac >= 0 Constraints (a) operation time definition Tass = 2x1 + 4x2 + 3x3 + 7x4 (assembly) Tpol = 3x1 + 2x2 + 3x3 + 4x4 (polish) Tpac = 2x1 + 3x2 + 2x3 + 5x4 (pack) (b) operation time limits Tass + Tpol + Tpac 0

Example 5 – Solution (4 of 4)

X1 = 200 Goal 1 achieved X2 = 80 Goal 2 not achieved d1+ = 0 d1- = 0 Z = 40

d2+ = 0 d2- = 40...