Winston Chapter 14.1, Page 784, Number 10 (Goal Programming)

 /  / 1

Winston Chapter 14.1, Page 784, Number 10 (Goal Programming)

Problem Statement: Deancorp produces sausage by blending beef head, pork chuck, mutton, and water. The cost per pound, fat per pound, and protein per pound for these ingredients are given in Table 8. Deancorp needs to produce 100 lbs. of sausage and has set the following goals, listed in order of priority:

Goal 1: Sausage should consist of at least 15% protein.

Goal 2: Sausage should consist of at most 8% fat.

Goal 3: Cost per pound of sausage should not exceed 8¢.

Table 8: / Head / Chuck / Mutton / Moisture
Fat (per lb.): / 0.05 / 0.24 / 0.11 / 0.00
Protein (per lb.): / 0.20 / 0.26 / 0.08 / 0.00
Cost (in cents): / 12.00 / 9.00 / 8.00 / 0.00

Formulate a preemptive goal-programming model for Deancorp.

  1. Summarize the problem and formulate it.

B.  Change the problem to an LP problem as explained here. Consider Goal 3 to be the objective function that you want to minimize. Consider Goal 1 and 2 as just constraints. Input this version of the problem into the LP option of Quant and solve it. Print input and output information.

  1. Write a report of your solution for a hypothetical manager. Use a language understandable to most people.

A.  Problem summarized in a table and its formulation:

Fat (per lb.) / Protein (per lb.) / Cost (in cents)
Head, x1 / 0.05 / 0.20 / 12.00
Chuck, x2 / 0.24 / 0.26 / 9.00
Mutton, x3 / 0.11 / 0.08 / 8.00
Moisture, x4 / 0.00 / 0.00 / 0.00
At most 8% / At least 15% /

Not to exceed 8 cents

Variables: x1 = Percent of Head used in Mixture.

x2 = Percent of Chuck used in Mixture.

x3 = Percent of Mutton used in Mixture.

x4 = Percent of Moisture used in Mixture.

Objective Function: Min Z1 = P1(S1-)

Min Z2 = P2(S2+)

Min Z3 = P3(S3+)

Subject To: 0.20x1 + 0.26x2 + 0.08x3 + 0.00x4 + S1- - S1+ = 0.15 (Protein)

0.05x1 + 0.24x2 + 0.11x3 + 0.00x4 + S2- - S2+ = 0.08 (Fat)

12.0x1 + 9.00x2 + 8.00x3 + 0.00x4 + S3- - S3+ = 8.00 (Cost)

x1 + x2 + x3 + x4 = 1 (Sausage is made of 100% ingredients)

Quant Input: Free Format Model for 0784n10

> Min 1S1N

> Min 1S2P

> Min 1S3P

>Subject to

> (1) .2X1+ .26X2+ .08X3+ 1S1N-1S1P = .15

> (2) .05X1+ .24X2+ .11X3+ 1S2N-1S2P = .08

> (3) 12X1+ 9X2+ 8X3+ 1S3N-1S3P = 8

> (4) 1X1+ 1X2+ 1X3+ 1X4+ 1S1N = 1

Quant Output:

|------|

| Summarized Solution for 0784n10 Page : 1 |

|------|

| | | |Opportunity|Opportunity|Opportunity|Opportunity|

|Number | Variable | Solution |Cost-Obj. 1|Cost-Obj. 2|Cost-Obj. 3|Cost-Obj. 4|

|------+------+------+------+------+------+------|

| 1 | X1 | +.45883885| 0| 0| 0| |

| 2 | X2 | +.19584055| 0| 0| 0| |

| 3 | X3 | +.09142111| 0| 0| 0| |

| 4 | X4 | +.25389948| 0| 0| 0| |

| 5 | S1N | 0| +1.0000001| 0| 0| |

| 6 | S1P | 0| 0| 0| 0| |

| 7 | S2N | 0| 0| 0| 0| |

| 8 | S2P | 0| 0| +1.0000000| 0| |

| 9 | S3N | 0| 0| 0| 0| |

| 10 | S3P | 0| 0| 0| +1.0000000| |

|------|

| Priority Level 1: Minimized Objective Function (Goal) = 0 |

| Priority Level 2: Minimized Objective Function (Goal) = 0 |

| Priority Level 3: Minimized Objective Function (Goal) = 0 |

| Iteration = 12 Elapsed CPU second = 0 |

|------|

|------|

| Analysis of OBJ Coefficients for 0784n10 Page : 2 |

|------|

| | | Priority |Opportunity| Objective | Minimum | Maximum |

|Number | Variable | Level | Cost |Coefficient|Obj. Coeff.|Obj. Coeff.|

|------+------+------+------+------+------+------|

| 1 | S1N | 1 | +1.0000001| +1.0000000| -1.192E-07| + Infinity|

| 2 | S2P | 2 | +1.0000000| +1.0000000| 0| + Infinity|

| 3 | S3P | 3 | +1.0000000| +1.0000000| 0| + Infinity|

|------|

Deancorp needs to produce 100 lbs. of sausage using the set of goals listed above and in order of priority. The constraints of the problem and the results given by Quant show that all of the goals have been met.


0.20(.459) + 0.26(.196) + 0.08(.091) + 0.00(.254) = 0.15 (Protein)

0.05(.459) + 0.24(.196) + 0.11(.091) + 0.00(.254) = 0.08 (Fat)

12.0(.459) + 9.00(.196) + 8.00(.091) + 0.00(.254) = 8.00 (Cost)

Additionally, the results given by Quant suggest that 45.8% of the sausage be made with head, 19.6% of the sausage be made with chuck, 9.1% of the sausage be made with mutton, and the remaining 25.4% be made with moisture. The results to make 100 lbs. are as follows:

Ingredient / Percent of Total Sausage / Pounds Required for 100 lbs.
Head / 45.9% / 45.9 lbs.
Chuck / 19.6% / 19.6 lbs.
Mutton / 9.1% / 9.1 lbs.
Moisture / 25.4% / 25.4 lbs.

B.  Change the problem to an LP problem: Consider goal 3 to be the objective function to minimize. Consider goals 1 and 2 as constraints. Input this version of the problem into the LP option of Quant and solve it. Print input and output information.

Obj. Function: Minimize the cost per pound of sausage (should not exceed 8¢).

Constraint 1: Sausage should consist of at least 15% protein.

Constraint 2: Sausage should consist of at most 8% fat.

Obj. Function: Min Z = 12.0x1 + 9.00x2 + 8.00x3 + 0.00x4

Constraint 1: 0.20x1 + 0.26x2 + 0.08x3 + 0.00x4 ³ 0.15 (Protein)

Constraint 2: 0.05x1 + 0.24x2 + 0.11x3 + 0.00x4 £ 0.08 (Fat)

Constraint 3: x1 + x2 + x3 + x4 = 1 (Sausage is made of 100% ingredients)

Quant Input: Free Format Model for 0784n10c

> Min 12X1+ 9X2+ 8X3

>Subject to

> (1) .2X1+ .26X2+ .08X3 >= .15

> (2) .05X1+ .24X2+ .11X3 <= .08

> (3) 1X1+ 1X2+ 1X3+ 1X4 = 1

Quant Output:

|------|

| Summarized Report for 0784n10c Page : 1 |

|------|

| | | |Opportunity| Objective | Minimum | Maximum |

|Number | Variable | Solution | Cost |Coefficient|Obj. Coeff.|Obj. Coeff.|

|------+------+------+------+------+------+------|

| 1 | X1 | +.43428576| 0 | +12.000000| +6.9230771| + Infinity|

| 2 | X2 | +.24285713| 0 | +9.0000000| - Infinity| +15.599999|

| 3 | X3 | 0 | +6.5942855| +8.0000000| +1.4057145| + Infinity|

| 4 | X4 | +.32285711| 0 | 0 | - Infinity| +8.7424240|

|------|

| Minimized OBJ = 7.397143 Iteration = 3 Elapsed CPU second = 0 |

|------|


|------|

| Summarized Report for 0784n10c Page : 2 |

|------|

| | | | Shadow | Slack or | Minimum | Maximum |

|Constr.| Status | RHS | Price | Surplus | RHS | RHS |

|------+------+------+------+------+------+------|

| 1 | Tight | >+.15000001| +69.428566| 0 | +.08666667| +.20947368|

| 2 | Tight | <+.08000000| -37.714283| 0 | +.03750000| +.13846155|

| 3 | Tight | =+1.0000000| 0 | 0 | +.67714286| + Infinity|

|------|

| Minimized OBJ = 7.397143 Iteration = 3 Elapsed CPU second = 0 |

|------|

C.  The results of this problem indicate that the minimum cost of pound for sausage will be 7.39¢ when the sausage is made of 43.4% head, 24.3% chuck, 32.3% moisture, and no mutton. Since no mutton is used, it will have an opportunity cost. The opportunity cost of mutton is 6.59¢, meaning that some mutton would be used as an ingredient only if the current 8¢ cost is reduced by 6.59¢ to a new cost of less than 1.41¢. Additionally, the two constraints derived from the original goals are both binding. This means that the right-hand-side of either constraint could be modified to be within the minimum or maximum right-hand-side values specified and still retain the basis of each of the variables. On the other hand, the basic feasible solution would change regardless of whether or not the right-hand-side values remained within these limits. The results that obtain the minimum cost of sausage are listed below:

Ingredient / Percent of Total Sausage / Pounds Required for 100 lbs.
Head / 43.4% / 43.4 lbs.
Chuck / 24.3% / 24.3 lbs.
Mutton / 0% / 0 lbs.
Moisture / 32.3% / 32.3 lbs.