Make your own free website on Tripod.com

Two Variable Goal Programming Model with Penalties

 

The example we are looking at is a two variable problem where goals are have  penalties associated with them and there is no prior solution given (more information here).

We are looking at a problem modified from Ignizio (1976)[1].

Problem

 A small paint company manufactures two types of paint, latex and enamel. In production, the company uses 10 hours of labor to produce 100 gallons of latex and 15 hours of labor to produce 100 gallons of enamel. The company has 40 hours of daily labor and 30 hours of overtime labour available each week. Furthermore, if enamel paint is produced, latex paint must also be produced. Each paint generates a profit at the rate of $1.00 per gallon. The company has the following objectives:

·        avoid the use of overtime

·        achieve a weekly profit of $1000

·        produce at least 700 gallons of enamel paint each week

For every hour that objective 1 goes over, the company has to pay a penalty of $3. For the profit objectives, the company associates a $1 penalty for every dollar that falls below the minimum $1000 profit. There is a potential lost of $0.50 for every gallon that falls short of the required 700 enamel gallons production.

a)      Formulate the linear goal programming model

b)     Solve the goal programming model using a graphical method

c)      Using the solution to the model, determine the deviation from the goal

Note: In this example we did not say the objectives were stated in any order of importance

 

Solution to the problem

We proceed with this problem just as we did with two variable goal programming model with priorities. We do Steps 1-2, and Steps 4-8 exactly the same. Step 3 and Step 9- Step 10 are slightly different.

 Step 1: Rewrite information in a table format

You may skip this step if you can easily find the information in the problem, but it helps in organizing your thoughts.

 

 

Latex

Enamel

Labour for 100 gallons (hours)

10

15

Profit for 1 gallon

$1

$1

 

Step 2: State your (functional) constraints

Remember these are your constraints not your goals. Goals do not have to be met (i.e they can go over or under the required amount) but constraints must always be met. These constraints are sometimes call functional constraints or hard constraints.

 Constraint 1: Labour ≤ 70 hours/ wk    (i.e. daily labour/ wk + overtime labour / wk)

Constraint 2: Latex paint ≥ Enamel paint (i.e. this ensures that if enamel paint is produced, latex paint is also produced)  

 

Step 3: Rewrite your goals as constraints if not given in that form

We do not know the priority of the goal but we do know the penalties. At this point we just state our goals in any order we wish. The order in which the goals are listed does not anyway indicate their importance.

 Goal 1 - Avoid using overtime i.e. labour has to be ≤ 40 hrs/wk

 Goal 2 - Achieve a weekly profit of $1000 i.e. profit ≥ $1000

 Goal 3 - Produce at least 700 gallons/wk of enamel paint i.e. enamel paint ≥ 700 gallons/wk

 We have named the each objective as Goals 1-3. The number (i.e. 1, 2, 3) does not in anyway indicate its importance in this problem.

 

Step 4: Decide decision variables

The decision variables we choose must be used to formulate all goals. In this case, we goals related to labour, profit and production. All of these goals are determined by the number of latex and enamel paint we produce each week. Therefore:

 L = no. of 100 gallons of latex paint produced per week

E = no. of 100 gallons of enamel paint produced per week

 Note: we could have used L = no. of gallons of latex paint produced per week, which will require us to divide the labour hours by 100

 

 Step 5: Rewrite your functional constraints using your decision variables

Constraint 1:  10 L + 15 E ≤ 70                                    (Labour constraint)

Constraint 2:  L E

Rewriting:

Constraint 2:  L E ≥ 0                                                (Production Constraint)

Note: You must always rewrite your constraints such that all decision variables are on the LHS and all constants are on the RHS.

 

Step 6: Rewrite your goal constraints using your decision variables

Goal 1: 10 L + 15 E ≤ 40                                             (Avoid Overtime)

Goal 2: 100 L + 100 E ≥ 1000                                     (Profit)

Note: Remember L is the no. of 100 gallons of latex paint produced per week, therefore since the profit is $1 per gallon, then the profit for 100 gallons of latex paint is $100

 Goal 3: E ≥ 7                                                               (Enamel Paint Production)

Note: Remember E is the no. of 100 gallons of enamel paint produced per week, therefore 7 batches of 100 gallons of enamel has to be produced to get 700 gallons

 

Step 7: Add deviation variables to the goal constraints

In formulating a goal programming model, the goal constraints are always converted to “equality constraints” i.e. and equal sign is used. If you recall, we did a similar step when solving LP problems using the simplex algorithm, where we incorporated slack and excess variables into the constraints (see Step 1 of Simplex Algorithm)

 Let us look at Goal 1

 10 L + 15 E ≤ 40

 To make this an equality constraint:

10 L + 15 E + Y1-   – Y1+ = 40

 where Y1- is the slack deviation variable and Y1+ is the excess deviation variable for Goal 1

 Yi- : represents how much we must add to make up the goal i.e. the slack (we use the negative sign to represent we have fallen short of the goal)

Yi+ : represents how much we must subtract to make up the goal i.e. the excess (we use the positive sign to represent we have exceeded the goal)

 Note: We added both deviation variables to the goal constraints unlike what we would have done for the functional (hard) constraints. This is because, goal constraints are allowed to go over and go under their constraint value.

Note: The deviation variables have the same units as E and L, that is they are measured in 100 gallons of paint.

 This means if the final RHS of Goal 1 was 60 hours i.e.

 10 L + 15 E = 60

 Then

10 L + 15 E + Y1-  – Y1+ = 60 20  = 40

 This means we would have exceeded the goal by 20 hours (60 40 = 20 hrs), i.e. we would be in excess of the goal. Therefore, we  have no slack which means our slack deviation variable, Y1- = 0. Our excess deviation variable would be Y1+ = 60 – 40 = 20.  

 Therefore, adding deviation variables to all goal constraints we would have 

Goal 1:  

10 L

+ 15 E

+ Y1-

– Y1+

= 40

(Overtime)

Goal 2: 

100 L

+ 100 E

+ Y2-

– Y2+

= 1000

(Profit)

Goal 3:

 

E

+ Y3-

     – Y3+

= 7

(Enamel Prod.)

  

Step 8: Determine the variables need to be minimized in the objective function

 The objective function of a goal programming model requires us to always minimize the variables.

 We need now to determine which variables we are required to minimize. The variables we are required to minimize are always located in the goals.

 Let us again look at Goal 1

 10 L + 15 E + Y1-   – Y1+ = 40

 From this goal, if you recall we do not want to go over the 40 daily labour hours available per week i.e.

 10 L + 15 E ≤ 40

 Therefore, we want to ensure that there is no excess. Since the corresponding excess deviation variable for this goal is Y1+, we want to make this as small as possible, i.e. minimize this variable.

 For Goal 2 (Profit)

 100 L + 100 E ≥ 1000

100 L + 100 E + Y2- – Y2+ = 1000

 We require the profit to be more than $1000, in other words, we do want it to fall under $1000. The variable that corresponds to us fallen under our goal, is our slack deviation variable, Y2-. We thus want to make this as small as possible, i.e. minimize Y2-.

  For Goal 3 (Enamel Paint Production)

E ≥ 7  

E + Y3-  – Y3+  =  7

 We require that enamel paint production be always above 700 gallons. We thus have to ensure that our slack deviation variable, Y3-, is as small as possible, i.e. minimized.

Note: Remember Y3- and Y3+ are both measured in 100 gallons of paint.

 

Step 9: Write the objective function with penalties

Thus we are required to minimize Y1+, Y2-, Y3-. By minimizing these variables we will be able to possibly satisfy our goals.

 Now we are almost near to writing our objective function. This is where we are required to use the penalties. Let's write the penalties associated for each goal in a list

Goal 1 Penalty: $3 / hr for every hour over 40 hrs

Goal 2 Penalty: $1 / every dollar for every dollar under $1000

Goal 3 Penalty: $0.50 / gallon for every gallon under 700 gallons of enamel paint

Now from Step 8 above, you will recall, that Y1+ is the number of hours that labour goes over the normal daily labour hours,  Y2- is the amount of dollars that the profit falls short of for every 100-gallon of paint and Y3- is the no. of 100-gallons of enamel paint that production falls short by.

Therefore the total penalty from this model is thus as follows

3Y1++ 100 Y2- + 50 Y3-

Note: For Y2- , represents how much the profit falls short off for every 100-gallon of paint, this will then be $1× 100 = $100.  Similarly, for Y3- , since $0.50/ gallon, then for 100 gallons it will be $0.50 × 100 = $50

Now, the sum of penalties indicates money lost by not meeting the goals. Therefore, we will like to minimize our lost and thus our objective function stands as

min 3Y1++ 100 Y2- + 50 Y3-

You will notice that Y2- has the largest penalty of $100, and thus we will like to minimize the deviation in that goal first or in other words, ensure that Goal 2 is met first. Goal 3 has the next largest penalty of $50, and thus we this will be the second goal we will like to minimize. Goal 1 which has a penalty of $3, will be the least important goal.

Note: We can list these goals according to importance (i.e. priority) based on their importance we will have

 P2: Goal 2 - Achieve a weekly profit of $1000 i.e. profit ≥ $1000

P3: Goal 3 - Produce at least 700 gallons/wk of enamel paint i.e. enamel paint ≥ 700 gallons/wk

P1: Goal 1 - Avoid using overtime i.e. labour has to be ≤ 40 hrs/wk

Therefore, similarly to goal programming models with priorities, we can say that  P2 ≥ P3 ≥ P1, where Pi represented the goal priorities.

Where in this case P2 = 100, P3 = 50 and P1 = 3. This, thus corresponds to

Min      P1Y1+ + P2Y2- + P3Y3-

 

 Step 10. Write the Goal Programming Model

 We need to combine all parts i.e. the functional constraints, goal constraints and the objective function for producing the goal programming model. You will notice that the only difference between this problem with penalties and the problem with priorities is its objective function.

Min

 

 

 

3 Y1+

+ 100 Y2-

 

+ 50 Y3-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

s.t.

 

 

 

 

 

 

 

 

 

 

 

     10 L

+ 15 E

 

 

 

 

 

 

≤ 70

(Labour)

 

L

– E

 

 

 

 

 

 

≥ 0

(Production)

Goal 1: 

10 L

+ 15 E

+ Y1-

– Y1+

 

 

 

 

= 40

(Overtime)

Goal 2: 

100 L

+ 100 E

 

 

+ Y2-

– Y2+

 

 

= 1000

(Profit)

Goal 3:

 

E

 

 

 

 

+ Y3-

– Y3+

= 7

(Enamel Prod.)

 

 

 

All variables ≥ 0