University:
Whitman College
Course:
MATH-339 | Operations Research
Academic year:

2024
Views:

231

Pages:

22
Author:

Jesse Chung

Goal Programming Example The Dewright company is considering three new products. Goals and penalties are shown in the table: Product Factor 1 2 3 Goal Penalty Profit 12 9 15 ≥ 125 5 Employment 5 3 4 = 40 2(+), 4(−) Capital 5 7 8 ≤ 55 3 Formulate a system for goal programming. Let x1 , x2 , x3 be the prod. rates. Then we will min z = 5s1 + 4s2 + 2e2 + 3e3 12x1 +9x2 +15x3 +s1 − e1 = 125 5x1 +3x2 +4x3 +s2 − e2 = 40 5x1 +7x2 +8x3 +s3 − e3 = 55 We could easily solve this in LINDO or a spreadsheet. The Maple worksheet is Example 2 online. x1 = 100 , 7 x2 = 0, x3 = 145 7 Goal Programming Example (Exercise 4, 4.16) A company produces two products, where the labor and profit are: Prod 1 Prod 2 Labor (hrs) 4 2 Profit ($) 4 2 Demand 7 10 Target 32 48 The company incurs a penalty of $1 for each dollar it falls short of the profit. A $2 penalty is incurred for each hour of overtime, and a $1 penalty is incurred for each hour of labor that is not used. A penalty of $5/unit is assessed for any shortfall in meeting demand. Formulate an LP to minimize the penalty. SOLUTION: We minimize: z = s1 + 2e1 + s2 + 5s3 + 5s4 4x1 +2x2 4x1 +2x2 x1 x2 +s1 +s2 +s3 +s4 −e1 −e2 −e3 −e4 = 32 Labor = 48 Profit =7 = 10 SOLUTION: We minimize: z = s1 + 2e1 + s2 + 5s3 + 5s4 4x1 +2x2 4x1 +2x2 x1 x2 +s1 +s2 +s3 +s4 −e1 −e2 −e3 −e4 = 32 Labor = 48 Profit =7 = 10 In LINDO, we get x1 = 7, x2 = 10, e1 = 16 SOLUTION: We minimize: z = s1 + 2e1 + s2 + 5s3 + 5s4 4x1 +2x2 4x1 +2x2 x1 x2 +s1 +s2 +s3 +s4 −e1 −e2 −e3 −e4 = 32 Labor = 48 Profit =7 = 10 In LINDO, we get x1 = 7, x2 = 10, e1 = 16 reasonable considering heavy penalty on not meeting demand. Goal Programming Now we’ll try the same problem, except that we set the following goals (in order of importance): I Goal 1: Avoid underutilization of labor. I Goal 2: Meet demand for product 1. I Goal 3: Meet demand for product 2. I Goal 4: Do not use any overtime. We see profit is no longer a constraint. Setting up the Tableau: 4x1 +2x2 +s1 −e1 = 32 Labor x1 +s2 −e2 = 7 x2 +s3 −e3 = 10 Goals: P1 s1 P2 s2 P3 s3 P4 e1 From our equations, we get  x1 x2 s1 s2  0 0 P1 0   0 0 0 P2   0 0 0 0   0 0 0 0   4 2 1 0   1 0 0 1 0 1 0 0 the tableau (max):  s3 e1 e2 e3 rhs 0 0 0 0 0   0 0 0 0 0   P3 0 0 0 0   0 P4 0 0 0   0 −1 0 0 32   0 0 −1 0 7  1 0 0 −1 10 Choose a set of variables for the BFS, and row reduce to get columns of the identity matrix. From our equations, we get  x1 x2 s1 s2  0 0 P1 0   0 0 0 P2   0 0 0 0   0 0 0 0   4 2 1 0   1 0 0 1 0 1 0 0 the tableau (max):  s3 e1 e2 e3 rhs 0 0 0 0 0   0 0 0 0 0   P3 0 0 0 0   0 P4 0 0 0   0 −1 0 0 32   0 0 −1 0 7  1 0 0 −1 10 Choose a set of variables for the BFS, and row reduce to get columns of the identity matrix. Current basic variables: s1 = 32, s2 = 7, s3 = 10. Clearing those columns, here  x1 x2 s1 s 2  −4P1 −2P1 0 0   −P2 0 0 0   0 −P 0 0 3   0 0 0 0   4 2 1 0   1 0 0 1 0 1 0 0 is the result:  s 3 e1 e2 e3 rhs 0 P1 0 0 −32P1   0 0 P2 0 −7P2   0 0 0 P3 −10P3   0 P4 0 0 0   0 −1 0 0 32   0 0 −1 0 7  1 0 0 −1 10 Using the first row as Row 0, pivot in column 1, row 6 (use the ratio test). This will bring in x1 as BV, and move s2 to NBV.              x1 x2 s1 s 2 s 3 e1 e2 e3 rhs 0 −2P1 0 4P1 0 P1 −4P1 0 −4P1   0 0 0 P2 0 0 0 0 0   0 0 0 0 P3 −10P3  0 −P3 0  0 0 0 0 0 P4 0 0 0   0 2 1 −4 0 −1 4 0 4   1 0 0 1 0 0 −1 0 7  0 1 0 0 1 0 0 −1 10 Now bring in e2 as basic, and move s1 to NBV. That is, pivot in Column 7, Row 5.              x1 x2 s1 s2 s 3 e1 e2 e3 rhs 0 0 P1 0 0 0 0 0 0   0 0 0 P2 0 0 0 0 0   0 0 0 0 0 P3 −10P3  0 −P3  0 0 0 0 0 P4 0 0 0   0 1/2 1/4 −1 0 −1/4 1 0 1   1 1/2 1/4 0 0 −1/4 0 0 8  0 1 0 0 1 0 0 −1 10 Goals 1 and 2 now complete. Proceed to Priority 3. Bring in x2 as basic, take e2 back out again.              x1 x2 s1 s2 s3 e1 e2 e3 rhs 0 0 P1 0 0 0 0 0 0   0 0 0 P2 0 0 0 0 0   0 0 P3 /2 −2P3 0 −P3 /2 2P3 P3 −8P3   0 0 0 0 0 P4 0 0 0   0 1 1/2 −2 0 −1/2 2 0 2   1 0 0 1 0 0 −1 0 7  0 0 −1/2 2 1 1/2 −2 −1 8 We can’t bring in s2 without messing up P2 . Are we done?              x1 x2 s1 s2 s3 e1 e2 e3 rhs 0 0 P1 0 0 0 0 0 0   0 0 0 P2 0 0 0 0 0   0 0 P3 /2 −2P3 0 −P3 /2 2P3 P3 −8P3   0 0 0 0 0 P4 0 0 0   0 1 1/2 −2 0 −1/2 2 0 2   1 0 0 1 0 0 −1 0 7  0 0 −1/2 2 1 1/2 −2 −1 8 We can’t bring in s2 without messing up P2 . Are we done? Bring in e1 , take out s3 .              x1 x2 s1 s2 s 3 e1 e2 e3 rhs 0 0 P1 0 0 0 0 0 0   0 0 0 P2 0 0 0 0 0   0 0 0 0 P3 0 0 0 0   0 0 P4 −4P4 −2P4 0 4P4 2P4 −16P4   0 1 0 0 1 0 0 −1 10   1 0 0 1 0 0 −1 0 7  0 0 −1 4 2 1 −4 −2 16 Optimal?              x1 x2 s1 s2 s 3 e1 e2 e3 rhs 0 0 P1 0 0 0 0 0 0   0 0 0 P2 0 0 0 0 0   0 0 0 0 P3 0 0 0 0   0 0 P4 −4P4 −2P4 0 4P4 2P4 −16P4   0 1 0 0 1 0 0 −1 10   1 0 0 1 0 0 −1 0 7  0 0 −1 4 2 1 −4 −2 16 Optimal? x1 = 7, x2 = 10, e1 = 16 Solving in LINDO Let’s look at solving the goal programming LP in LINDO. We first ask LINDO to min z = s1 such that 4x1 + 2x2 + s1 − e1 = 32 x1 + s2 − e2 = 7 x2 + s3 − e3 = 10 Type the following into LINDO, then “Solve”: min s1 st 4x1+2x2+s1-e1=32 x1+s2-e2=7 x2+s3-e3=10 end LINDO returns: x1 = 7 and x2 = 2. Now we ask LINDO to solve the following system (just make the changes “live”) min s2 st 4x1+2x2+s1-e1=32 x1+s2-e2=7 x2+s3-e3=10 s1=0 end LINDO returns: x1 = 8 and x2 = 0. Continuing, we have: min s3 st 4x1+2x2+s1-e1=32 x1+s2-e2=7 x2+s3-e3=10 s1=0 s2=0 end LINDO returns: x1 = 7 and x2 = 10. Finally, we ask LINDO: min e1 st 4x1+2x2+s1-e1=32 x1+s2-e2=7 x2+s3-e3=10 s1=0 s2=0 s3=0 end LINDO basically returns the same answer: x1 = 7, x2 = 10, (So we’re not able to get e1 to zero). e1 = 16

Goal Programming Example - Study Guide

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock