4. Linear Programming (2).pdf

Quantitative Methods in Management (Operations Research)

Linear Programming Josephine Q. Borja, PhD

Introduction Linear programming (LP)  a widely used mathematical modeling technique  designed to help managers in planning and decision making  a technique that helps in resource allocation decisions

Programming refers to  modeling and solving a problem mathematically.

2/8/2019

2

Introduction Linear programming (LP)  Development of a production schedule that will:  Satisfy future demands for a firm’s production  Minimize total production and inventory cost

 Selection of a product mix in a factory that will:  Make best use of machine hours and labor hours available  Maximize the firm’s products

 Determination of grades of petroleum products to yield the maximum profit

2/8/2019

3

Introduction Linear programming (LP)  Selection of different blends of raw materials to feed mills to produce finished feed combinations at minimum cost

 Determination of distribution system that will minimize total shipping cost from several warehouses to various market locations

2/8/2019

4

Introduction Basic Assumptions in LP  Certainty  numbers in the objective and constraints are known with certainty and do not change during the period being studied

 Proportionality  Exists in the objective and constraints  Constancy between production increases resource utilization

and

 Additivity  Total of all activities equals the sum of individual activities

2/8/2019

5

Introduction Basic Assumptions in LP  Divisibility  Solutions need not be in whole numbers  Solutions are divisible and may take any fractional value

 Non-negativity  All answers or variables are greater than or equal to zero.  Negative values of physical quantities are impossible

2/8/2019

6

Formulating Linear Programming Problems 1. Completely problem

understand

the

managerial

2. Identify the objective and the constraints. 3. Define the decision variables.

4. Use the decision variables to write mathematical expressions for the objective function and the constraints.

2/8/2019

7

Formulating Linear Programming Problems Basic Components

1. Decision variables that we seek to determine 2. Objective (goal) that we need to optimize (maximize or minimize) 3. Constraints that solution must satisfy

2/8/2019

8

Two-Variable LP Model (Graphical Method) Reddy Mix produces both interior and exterior paints from two raw materials M1 and M2. The following table provides the basic data for the problem Raw Material

Tons of raw material per ton of:

Exterior paint

Interior paint

Maximum daily availability, tons

M1

6

4

24

M2

1

2

6

Profit per Ton ($1000)

5

4

A market survey indicates that the daily demand for interior paint can not exceed that for exterior paint by more than 1 ton. Also, the maximum daily demand for interior paint is 2 tons. Reddy Mix wants to determine the optimum product mix of interior and exterior paint that maximizes the total daily profit. 2/8/2019

9

Two-Variable LP Model (Graphical Method)

Reddy Mix Problem (Maximization)

• Variables of the Model x1  Tons of exterior paint produced daily x2  Tons of interior paint produced daily • Objective Function: maximize total daily profit (z)

maximize z  5x1  4 x2

2/8/2019

10

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Constraints

Usage of M1 by both paints  6 x1  4 x2 tons/day Usage of M2 by both paints  x1  2x2 tons/day

6 x1  4 x2  24 (Raw material M1)

x1  2 x2  6

(Raw material M2)

x2  x1  1

(Market limit)

x2  2

(Demand limit)

x1  0, x2  0 (Non-negativity restrictions)

2/8/2019

11

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Complete Model

maximize : z  5x1  4 x2 Subject to

6 x1  4 x2  24

Raw M aterial1

x1  2 x2  6

Raw M aterial 2

 x1  x2  1

M arket Limit

x2  2 x1  0; x2  0

2/8/2019

Demand Limit Non - negativity

12

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Determination of the Feasible Solution Space

X2 6

5

Line 1: 6x1 + 4x2 ≤ 24

4

Line 2: x1 + 2x2 ≤ 6

3

Line 3: -x1 + x2 ≤ 1

2

Line 4: x2 ≤ 2

1

Non-negativity: x1  0; x2  0

Feasible Region

0 -1

2/8/2019

1

2

3

4

5

6

7

X1

13

Two-Variable LP Model (Graphical Method) Reddy Mix Problem

•

Maximize Objective Function – Look for direction of increasing Z

maximize z  5x1  4 x2 1. Select an arbitrary values of Z and substitute to the objective function. 2. Plot the objective function. Any point on the line that is within the feasible region will give a profit equal to the selected arbitrary value. 3. Repeat (1) and (2) but using higher values of z. Take note that the line must lie within the feasible region. *Note that profit lines are parallel to each other, and lines with higher profit contributions are farther from the origin.

4. The values of M1 and M2 are determined at the point corresponding to the highest profit.

2/8/2019

14

Sensitivity Analysis • Optimal solutions to LP have been determined under deterministic assumptions. • Conditions in most real world situations are dynamic and changing. • After an optimal solution to a problem is found, input data values are varied to assess the sensitivity of the optimal solution to this changes. • Sensitivity analysis determines the effect on optimal solution of changes in parameter values of the objective function and constraint equations. • Changes may be reactions to anticipated uncertainties in the parameters or the new or changed information concerning the model.

2/8/2019

15

Role of Sensitivity Analysis of the Optimal Solution • Is the optimal solution sensitive to changes in input parameters?

• Possible reasons for asking the question: – Parameter values were only best estimates. – Dynamic environment may cause changes – “What if” analysis provide economical and operational information.

2/8/2019

16

Sensitivity Analysis of Objective Function Coefficients • Ranges of Optimality – The value of the objective function will change if the coefficient multiplies a variable whose value is non-zero. – The optimal solution will remain unchanged as long as • An objective function coefficient lies within its range of optimality • There are no changes in any other input parameters

2/8/2019

17

Sensitivity Analysis of Objective Function Coefficients • The optimality range for an objective coefficient is the range of values over which the current optimal solution point will remain optimal. • For 2-variable LP problems the optimality ranges of the objective function coefficients can be found by setting the slope of the objective function equal to the slopes of each of the binding constraints.

2/8/2019

18

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Change in coefficient of objective Function

maximize z C1x1  C2 x2 – If C1 and C2 changes, the optimal corner point maybe possibly changed – As long as the slope of Z is within the slope of Eq. 1 & Eq. 2, the optimal point is unchanged 7

6

Linear (1)

5

M1: 6x1 + 4x2 ≤ 24

4

Linear (2)

3

M2: x1 + 2x2 ≤ 6

2

1 0 -2 2/8/2019

0

2

4

6

8 19

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – If C1  0, then

4 C2 2   6 C1 1

Objective function can not be horizontal – If C2  0, then

1 C1 6   2 C2 4

Objective function can not be vertical – As long as the ratio are within the specified range the optimum point remains unchanged

2/8/2019

20

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Optimal range for one of the coefficients – Given C2 = 4, what is the optimal range of C1?

1 C1 6   2 C2 4

2  C1  6

– Given C1 = 5, what is the optimal range of C2

4 C2 2   6 C1 1

2/8/2019

20  C2  10 6

21

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Change in availability of resources – Amount of M1 at the intersections (2,2) and (6,0), corresponding to the line for M1

Usage of M1 by both paints  6 x1  4 x2 tons/day

M1: 6x1 + 4x2 ≤ 24

at (2,2): M1 = (6 x 2) + (4 x 2) = 20 at (6,0): M1 = (6 x 6) + (4 x 0) = 36

M2: x1 + 2x2 ≤ 6 7 6 5 4 3 2 1 0 -2 2/8/2019

– Given M2 = 6, the feasibility range for M1 is

20  M1  36 Since M1 = 24, it can be decreased by 4 or increased by 12

0

2

4

6

8 22

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Change in availability of resources – Given M1 = 24, the feasibility range for M1 is delineated by

Usage of M2 by both paints  x1  2x2 tons/day

M1: 6x1 + 4x2 ≤ 24

Amount of M1 at the intersections (4,0) and (8/3,2), corresponding to the line for M2

M2: x1 + 2x2 ≤ 6 7 6 5 4 3 2 1 0 -2 2/8/2019

at (4,0): M2 = 4 + 0 =4 at (8/3,2): M2 = 8/3 + (2 x 2) = 20/3

4  M 2  20 / 3 Since M2= 6, it can be decreased by 2 or increased by 2/3

0

2

4

6

8 23

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Unit worth of a resource – rate of change in the optimum objective that results from making changes in the available amount of a resource.

change in Z corresponding to the feasible range of resource y feasible range of resource

2/8/2019

24

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Feasible Range of M1:

20  M1  36

change in Z from (2,2) to (6,0) y change in M 1 (2,2) to (6,0) Z at (2,2): Z = (5 x 2) + (4 x 2) = 18 Z at (6,0): Z = (5 x 6) + (4 x 0) = 30

30  18 y  0.75 36  20 Therefore, 1 ton change in the range will change the optimum Z by 750

2/8/2019

20  M1  36

25

Two-Variable LP Model (Graphical Method) Reddy Mix Problem • Sensitivity Analysis – Feasible Range of M2:

4  M 2  20 / 3

change in Z from (4,0) to (8 / 3,2) y change in M 2 (4,0) to (8 / 3,2) Z at (4,0): Z = (5 x 4) + (4 x 0) = 20 Z at (8/3,2): Z = (5 x 8/3) + (4 x 2) = 64/3

64 / 3  20 y  0.50 20 / 3  4 Therefore, 1 ton change in the range will change the optimum Z by 500

2/8/2019

4  M 2  20 / 3

26

Two-Variable LP Model Reddy Mix Problem • Slack Variables – Any unused or idle capacity associated with the constraint Constraint (material)

Amount required

Material Available

M1

24

M2

6

Unused material

Amount required is based on optimal solution

2/8/2019

27

Multiple Changes • The range of optimality is valid only when a single objective function coefficient changes. • When more than one variable changes, the 100% rule applies

2/8/2019

28

Multiple Changes – 100% Rule • For increase (decrease) in an objective function coefficient, calculate (and express as a percentage) the ratio of the change in the coefficient to the maximum possible increase (decrease) as determined by the limits of the range of optimality. • Sum all these percentage changes. If the total is less than or equal to 100%, the optimal solution will not change. If this total is greater than 100%, the optimal solution may change.

2/8/2019

29

Two-Variable LP Model (Graphical Method) Minimization Problem M&D Chemicals produces two products that are sold as raw materials to companies manufacturing both bath soaps and laundry detergents. Based on the analysis of current inventory levels and potential demand for the coming month, M&D’s management has specified that the combined production for products A and B must total at least 350 gallons. Separately, a major customer’s order for 125 gallons of product A must also be satisfied. Product A requires 2 hours of processing per gallon while product B requires 1 hour of processing time per gallon, and for the coming month, 600 hours of processing time are available. M&D’s objective is to satisfy these requirements at a minimum total production cost. Production costs are $2 per gallon of product A and $3 per gallon of product B. 2/8/2019

30

Two-Variable LP Model (Graphical Method) M&D Minimization Problem Decision Variables: A = number of gallons of product A B = number of gallons of product B Objective Function: Minimize: Z = 2A + 3B Constraints: 1A  125 1A + 2B  350 2A + 1B ≤ 600 A, B  0

2/8/2019

demand for product A total production processing time limit non-negativity

31

Two-Variable LP Model (Graphical Method) M&D Minimization Problem 700 Linear ((2) A + B = 350) 600

Linear ((1) A = 125) Linear ((1) A = 125)

500 400

300 200 100 0 0

2/8/2019

100

200

300

400

32

Introduction to Simplex Method  Convert inequalities to equalities   constraint  Right-hand side represents the limit on the availability of a resource  Difference between the right-hand side and the left-hand side represents unused or slack amount of resources  To convert  to an equation, a non-negative slack variable is added to the left-hand side

2/8/2019

33

Introduction to Simplex Method  Convert inequalities to equalities  ≥ constraint  Set a lower limit on the activities of the LP  amount by which the left-hand side exceeds the minimum limit represents a surplus  to convert ≥ to an equation, a non-negative surplus variable is subtracted from the lefthand side

2/8/2019

34

Introduction to Simplex Method  Example 6x1 + 4x2  24 6x1 + 4x2 + S1 = 24

x1 + x2 ≥ 800 X1 + X2 – S1 = 800  The right-hand side of the equation must be

non-negative. If it is negative, multiply the whole equation with (- 1)

2/8/2019

35

Transition from Graphical to Algebraic Solution Let m = number of equations n = number of variables If m = n and equations are consistent, system has only one solution

If m  n, the system of equation (if consistent) yields infinite solution In a set of m x n equations (m  n), if n-m variables is set to zero and solve the m equation for the remaining m variables, the resulting solution if unique, must correspond to the corner point of the solution space.

2/8/2019

36

Transition from Graphical to Algebraic Solution Example: Maximize Z = 2x1 + 3x2 Subject to: 2x1 + x2  4 x1 + 2x2  5 x1, x2 ≥ 0 2x1 + x2 + S1 = 4 x1 + 2x2 + S2 = 5 m = 2 equations n = 4 variables (x1, x2, S1, S2)

Set n – m = 4 - 2 = 2 variables to zero and solve the remaining n = 2 variables 2/8/2019

37

Transition from Graphical to Algebraic Solution Example:

 Set n - m variables to zero to target a specific corner point  Which n – m variable?  consider all combinations in which n – m variables are set to zero and solve the resulting equation  the optimum solution is the feasible corner point that yields the best objective value.

 n – m variables that are set to zero are known as non-basic variables  If the remaining variables have a unique solution they are called basic variables.

2/8/2019

38

Transition from Graphical to Algebraic Solution Non-basic (zero variables)

Basic Variables

X1, X2

S1, S2

X1, S1

X2, S2

X1, S2

X2, S1

X2, S1

X1, S2

X2, S2

X1, S1

S1, S2

X1, X2

Basic solution

Associated corner pt.

Feasible? Yes or No

Objective value, Z

Basic solution represents the values of the basic variables given that the non-basic variables are set to zero

2/8/2019

39

Simplex Method Rather than enumerating all the basic solutions (corner points) of the LP problem, the Simplex method investigates only a “select few” of these solutions  Iterative nature of the Simplex method  From the solution space, start at the origin where the decision variables are zero and Z = 0.  Increase one decision variable at a time and solve for Z.  For example, if X1 is increased, it will reach a corner point. Once this point is reached, increase X2 to reach an improved corner point. The largest positive objective coefficient is first targeted for increase

2/8/2019

40

Simplex Method Reddy Mix Problem OF: maximize Z = 5X1 + 4X2 Starting from origin, increase the value of the variable with the most positive coefficient. In this case, it is X1.

7 6

6x1 + 4x2 ≤ 24 x1 + 2x2 ≤ 6 -x1 + x2 ≤ 1 x2 ≤ 2

5 4 3 2

C 1

Feasible solution space 0

-2 2/8/2019

-1

0

X1

B

A 1

2

3

4

5

6

7 41

Simplex Method Changes in Basic and Non-Basic Variables pt. A

B

C

Non-basic

X 1, X 2

S1 , X 2

S1 , S 2

Basic

S1 , S2

X 1 , S2

X 1, X 2

S1 leaves

S2 leaves

– At pt. A, S1, S2 are basic; X1, X2 are non-basic – X1 is increased above zero to reach pt. B – Simultaneously, S1 will become non-basic and assumes zero value at pt. B 2/8/2019

42

Simplex Method Reddy Mix Problem • Complete Model

maximize z  5x1  4 x2 Subject to

6 x1  4 x2  24 x1  2 x2  6  x1  x2  1

x2  2 x1  0, x2  0

2/8/2019

43

Simplex Method Reddy Mix Problem • Complete Model

maximize z  5x1  4 x2  0S1  0S2  0S3  0S4 Objective function : z  5x1  4 x2  0 Subject to: 6 x  4 x  S  24 1 2 1 x1  0, x2  0 x1  2 x2  S2  6  x1  x2  S3  1 x2  S4  2

2/8/2019

Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

-5

-4

0

0

0

0

0

S1

0

6

4

1

0

0

0

24

S2

0

1

2

0

1

0

0

6

S3

0

-1

1

0

0

1

0

1

S4

0

0

1

0

0

0

1

2 44

Simplex Method  Optimality Condition: The entering variable in a maximization (minimization) problem is the non-basic variable with the most negative (positive) coefficient in the Z-row. Ties are broken arbitrarily. The optimum is reached at the iteration where all the Z-row coefficients of the non-basic variables are non-negative (non-positive)  Feasibility Condition – For both maximization and minimization problems, the leaving variable is the basic variable associated with the smallest non-negative ratio (with strictly positive denominator) Ties are broken arbitrarily.

2/8/2019

45

Simplex Method 

Gauss-Jordan Row Operation

1. Pivot Row a. replace the leaving variable in the Basic column with the entering variable. b. New pivot row = current pivot row divided by pivot element 2. All other rows including Z New Row = (current row) – (pivot column coefficient)(new pivot row)

2/8/2019

46

Simplex Method  Steps 1. Determine a starting basic feasible solution 2. Select an entering variable using the optimality condition (most negative/positive coefficient in the Z-row). Stop if there is no entering variable . The last solution is optimal. Else, go to step 3. 3. Select a leaving variable using the feasibility condition (smallest non-negative ratio) 4. Determine the new basic solution by using the appropriate Gauss-Jordan computations. Go to step 2.

2/8/2019

47

Simplex Method  Select the non-basic variable with the most negative coefficient as the entering variable.  Calculate the ratio of the solution to the coefficient of the entering variable.

 The basic variable corresponding to the minimum nonnegative ratio becomes the leaving variable.  The rule associated with the ratio computation is referred to as the feasibility condition.  The row of the leaving variable becomes the pivot row and the column of the entering variable is the pivot column. The intersection of the pivot row and pivot column is the pivot element.

2/8/2019

48

Simplex Method Simplex Tableau Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

-5

-4

0

0

0

0

0

S1

0

6

4

1

0

0

0

24

S2

0

1

2

0

1

0

0

6

S3

0

-1

1

0

0

1

0

1

S4

0

0

1

0

0

0

1

2

 The non-basic variable corresponding to the most negative value is X1. This is the entering variable.

2/8/2019

49

Simplex Method

Basic

X1

Soln

Ratio

S1

6

24

X1 = 24/6 = 4 (minimum)

S2

1

6

X1 = 6/1 = 6

S3

-1

1

X1 = 1/-1 = -1 (ignore)

S4

0

2

X1 = 2/0 =  (ignore)

 The basic variable corresponding to the minimum non-negative ratio becomes the leaving variable. This is S1.  The S1 row becomes the pivot row and the X1 column is the pivot column. The intersection of the pivot row and pivot column is the pivot element.

2/8/2019

50

Simplex Method Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

-5

-4

0

0

0

0

0

S1

0

6

4

1

0

0

0

24

S2

0

1

2

0

1

0

0

6

S3

0

-1

1

0

0

1

0

1

S4

0

0

1

0

0

0

1

2

1. Pivot Row  Replace the leaving variable in the Basic column with the entering variable  New pivot row = Current pivot row  Pivot element

2. All other rows including z  New row = (Current row) – (its pivot column coef.)(new pivot row)

2/8/2019

51

Simplex Method Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

0

-2/3

5/6

0

0

0

20

X1

0

1

2/3

1/6

0

0

0

4

S2

0

0

4/3

-1/6

1

0

0

2

S3

0

0

5/3

1/6

0

1

0

5

S4

0

0

1

0

0

0

1

2

Using optimality condition, X2 is the entering variable. Basic

X2

Soln

Ratio

X1

-2/3

4

X2 = 4/(2/3) = 6

S2

4/3

2

X2 = 2/(4/3) = 1.5 (min)

S3

5/3

5

X2 = 5/(5/3) = 3

S4

1

2

X2 = 2/1 = 2

Using feasibility condition, S2 is the leaving variable and. 2/8/2019

52

Simplex Method Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

0

-2/3

5/6

0

0

0

20

X1

0

1

2/3

1/6

0

0

0

4

S2

0

0

4/3

-1/6

1

0

0

2

S3

0

0

5/3

1/6

0

1

0

5

S4

0

0

1

0

0

0

1

2

1. Pivot Row  Replace the leaving variable in the Basic column with the entering variable  New pivot row = Current pivot row  Pivot element

2. All other rows including z  New row = (Current row) – (its pivot column coef.)(new pivot row) 53

Simplex Method Basic

Z

X1

X2

S1

S2

S3

S4

Soln

Z

1

0

0

3/4

1/2

0

0

21

X1

0

1

0

1/4

-1/2

0

0

3

X2

0

0

1

-1/8

3/4

0

0

3/2

S3

0

0

0

3/8

-5/4

1

0

5/2

S4

0

0

0

1/8

-3/4

0

1

1/2

Based on optimality condition, none of the z-row coefficient associated with the non-basic variables S1 and S2 are negative, hence the last tableau is optimal.

2/8/2019

Basic

Optimum value

Recommendation

X1

3

Produce 3 tons of exterior paint

X2

3/2

Produce 1.5 tons of exterior paint

Z

21

Daily profit is $21 54

Management Scientist: Reddy Mix Optimal solution

2/8/2019

55

Management Scientist: Reddy Mix

Slack – unused capacity.

2/8/2019

56

Management Scientist: Reddy Mix

Reduced Cost – indicates by how much the objective function coefficient of each decision variable would have to improve before it would be possible for that variable to assume a positive value in the optimal solution. If the decision variable is already positive in the optimal solution, its reduced cost is zero.

2/8/2019

57

Management Scientist: Reddy Mix For X1 (Exterior Paint): The range 2-6 provides the objective function coefficient range for exterior paint. Assuming that all other aspects of the original problem do not change, the profit contribution of X1 can be from 2-6 per ton and the optimal solution remains the same. For X2 (Interior Paint): Assuming that the profit contribution of X1 is $5/ton and all other aspects of the original problem remains unchanged, the OF coefficient for X2 can be 3.33-10.

2/8/2019

58

Management Scientist: Reddy Mix

Dual Price is the improvement in the value of the optimal solution per unit increase in the right hand side of the constraint. For constraint 1 (M1) the Dual Price is 0.75. This means that if we increase the right hand side (RHS) of M1 by 1 ton, the value of the optimal solution will improve by $0.75. Conversely, if we decrease the RHS of M1 by 1 ton, the value of the optimal solution will worsen by $0.75. For constraints 3 & 4, the dual price are both zero. Increasing the value of the RHS for these constraints will just add to the amount of slack and will not change the value of the optimal solution. 2/8/2019

59

Exercise RMC Inc. is a small firm that produces a variety of chemicalbased products. In a particular production process, three raw materials are used to produce two products: a fuel additive and a solvent base. The fuel additive is sold to oil companies and is used in the production of gasoline and related fuels. The solvent base is sold to a variety of chemical firms and is used in both home and industrial cleaning products. The three raw materials are blended to form the fuel additive and solvent base as indicated in Table 1. RMC’s production is constrained by the availability of three raw materials shown in the Table. Requirement per ton of product

Material

Fuel Additive

Solvent Base

Material 1

0.4

0.5

20 tons

0.2

5 tons

0.3

21 tons

Material 2 Material 3 2/8/2019

Amount Available

0.6

60

Exercise (RMC) Because of spoilage and the nature of the production process, any materials not used for current production are useless and must be discarded. The accounting department analyzed the production figures, assigned all relevant costs, and arrived at prices for both products that will result in a profit contribution of $40 for every ton of fuel additive produced and $30 for every ton of solvent bas produced. How many tons of each product should be produced to maximize the total profit?

2/8/2019

61

Exercise (RMC) Let F = tons of fuel additive S = tons of solvent base

LP M odel : M aximize Z  40 F  30 S Subject to : 0.4 F  0.5S  20 0.2 S  5 0.6 F  0.3S  21 F  0, S  0

2/8/2019

M aterial1 M aterial 2 M aterial 3

62

Exercise (RMC) Optimal solution

2/8/2019

63

Exercise (RMC)

Slack – unused capacity. Reduced Cost – indicates by how much the objective function coefficient of each decision variable would have to improve before it would be possible for that variable to assume a positive value in the optimal solution. If the decision variable is already positive in the optimal solution, its reduced cost is zero.

2/8/2019

64

Exercise (RMC) For F (FUEL ADDITIVE): The range 24-60 provides the objective function coefficient range for the fuel additive. Assuming that all other aspects of the original problem do not change, the profit contribution of F can be from 24 to 60 per ton and the optimal solution remains the same.

For S (SOLVENT BASE): Assuming that the profit contribution of F is $40/ton and all other aspects of the original problem remains unchanged, the OF coefficient for S can be 20-50.

2/8/2019

65

Exercise (RMC) DV

LL

CV

UL

Allowable decrease

Allowable increase

F

24

40

60

16

20

S

20

30

50

10

20

Based on the assumption that only one objective function coefficient changes at a time and all other aspects of the original problem remains the same. If there is simultaneous change in OF coefficient, apply the 100% rule

2/8/2019

66

Exercise (RMC) DV

LL

CV

UL

Allowable decrease

Allowable increase

F

24

40

60

16

20

S

20

30

50

10

20

100% Rule for OF coefficient: For all OF coefficient that are changed, if the sum of the percentages of the allowable increases and allowable deceases is less than or equal to 100%, the optimal solution will not change.

If profit contribution of F is increased to $48/ton and that of S is decreased to $27/ton: •Increase in F = 48-40 = 8; allowable increase = 20 % increase = (8/20)(100) = 40% of allowable increase •Decrease in S = 30 – 27 = 3; allowable decrease = 10 % decrease = (3/10)(100) = 30% •40% + 30%  100%, therefore optimal solution is not changed. 2/8/2019

67

Exercise (RMC) DUAL PRICE •improvement in the value of the optimal solution per unit increase in the RHS constant. •Tells us what will happen to the value of the optimal solution if we make 1 unit change in the RHS. RHS Ranges (Constraints) For one change at a time of the RHS ranges: Suppose an additional 4.5 tons of M3 is available, •constraint M3 becomes: 0.6F + 0.3S  25.5 •New optimal condition: F = 37.5 & S = 10 •Value of Optimal solution: $1800 •Original Optimal solution: $1600 •Increase in M3 increases the Optimal solution by 1800 – 1600 = 200 •Rate of increase of Optimal solution = 200/4.5 = 44.44 (Dual Price) For M2, dual prize is zero. This means that additional unit of M2 will just add to the slack and will not change the optimal solution. 2/8/2019

68

Exercise (RMC) • Dual price maybe applicable only to small increases in the RHS. As more resources are available and the RHS continue to increase, other constraints will become binding. • As long as the RHS of a constraint stays within its corresponding RHS range, the dual price is applicable. • For M2, dual price of zero is applicable as long as M2 is at least 4 tons.

2/8/2019

Constraint

LL

CV

UL

Allowable decrease

Allowable increase

M1

14

20

21.5

6

1.5

M2

4

5

No UL

1

M3

18.75

21

30

2.25

9 69

Exercise (RMC) Constraint

LL

CV

UL

Allowable decrease

Allowable increase

M1

14

20

21.5

6

1.5

M2

4

5

No UL

1

M3

18.75

21

30

2.25

9

• For simultaneous increase in RHS constant, 100% Rule applies. • Assume additional 0.5 ton of M1 and additional 4.5 tons of M3. • increase in M1 = (0.5/1.5)(100) = 33.33% • increase in M3 = (4.5/9)(100) = 50% • 33.3% + 50%  100% • Dual price of M1 and M2 will not change. • Improvement in the OF: 0.5(33.33) + 4.5(44.44) = 216.65 2/8/2019

70

Minimization Problem M&D Chemicals produces two products that are sold as raw materials to companies manufacturing both bath soaps and laundry detergents. Based on the analysis of current inventory levels and potential demand for the coming month, M&D’s management has specified that the combined production for products A and B must total at least 350 gallons. Separately, a major customer’s order for 125 gallons of product A must also be satisfied. Product A requires 2 hours of processing per gallon while product B requires 1 hour of processing time per gallon, and for the coming month, 600 hours of processing time are available. M&D’s objective is to satisfy these requirements at a minimum total production cost. Production costs are $2 per gallon of product A and $3 per gallon of product B. 2/8/2019

71

Minimization Problem M&D Chemicals Decision Variables: A = number of gallons of product A B = number of gallons of product B Objective Function: Minimize: Z = 2A + 3B Constraints: 1A  125 1A + 2B  350 2A + 1B ≤ 600 A, B  0

2/8/2019

demand for product A total production processing time limit non-negativity

72

 Dual price of 1.0 for the processing time constraint: increasing the right hand side of constraint 3 (processing hour) by 1 unit will improve the value of the optimal solution that is, increasing the processing time from 600 to 601 will lower the cost by $1 ($800 - $1 = $799)  Dual price of -4: increasing the right hand side of constraint 2 (total production) will not improve the value of the optimal solution, that is, increasing total production from 350 to 351 will increase the cost ($800 + $4 = $804).

2/8/2019

73

More than 2 Decision Variables RMC Problem Let F = tons of fuel additive S = tons of solvent base

LP M odel : M aximize Z  40 F  30 S Subject to : 0.4 F  0.5S  20 0.2 S  5 0.6 F  0.3S  21 F  0, S  0

M aterial1 M aterial 2 M aterial 3

Modified RMC Problem Suppose that management also is considering producing a carpet cleaning fluid. Estimates are that each ton of carpet cleaning fluid will require 0.6 ton of material 1, 0.1 ton of material 2, and 0.3 ton of material 3. The management believes that the company will realize a profit contribution of $50 for each ton of carpet cleaning fluid. 2/8/2019

74

More than 2 Decision Variables RMC Problem: Modified Model Let F = tons of fuel additive S = tons of solvent base C = tons of carpet cleaning fluid

LP Model : Maximize Z  40F  30S  50C Subject to : 0.4 F  0.5S  0.6C  20 0.2S  0.1C  5 0.6F  0.3S  0.3C  21 F  0, S  0 C  0

2/8/2019

Material 1 Material 2 Material 3

75

More than 2 Decision Variables

Coefficient of X2 in the OF should be improved by at least 12.5

2/8/2019

76

More than 2 Decision Variables

2/8/2019

77

LP Applications • Blending Problems • Production Management – A Make-or-Buy Decision – Production Scheduling – Workforce Assignment

• Marketing Applications – Media Selection – Marketing Research

• Financial Applications – Portfolio Selection – Financial Planning

• Revenue Management

2/8/2019

78

LP Applications • Blending Problems – Arise whenever a manager must decide how to blend two or more resources to produce one or more products – The resources contain one or more essential ingredients that must be blended into final products that will contain specific percentage of each. – Management must decide how much of each resource to purchase to satisfy product specifications and product demands at minimum cost

2/8/2019

79

LP Applications • Production Management – Make-or-Buy Decision •

–

Production Scheduling •

• •

2/8/2019

How much of each of several component parts a company should manufacture and how much it should purchase from an outside supplier. Establishing an efficient low cost production schedule for one or more products over several time periods (weeks or months). Product mix problem for each of several periods in the future The manager determines the production levels that will allow the company to meet product demand requirements given limitations on production capacity, labor capacity, and storage space, while minimizing total production cost. 80

LP Applications • Marketing Applications – Media Selection • • •

Allocation of fixed advertising budget to various advertising media. The objective is to maximize reach, frequency, and quality of exposure. Restriction on the allowable allocation usually arise during consideration of company policy, contract requirements, and media availability.

– Marketing Research • •

2/8/2019

Targets and quotas are established for the number and types of respondents to be surveyed. The marketing firm’s objective is to conduct the survey so as to meet the client’s needs at a minimum cost. 81

LP Applications • Financial Applications – Portfolio Selection •

•

•

•

2/8/2019

Involve situations in which a financial manager must select specific investments, such as stocks and bonds, from a variety of investment alternatives. Managers of mutual funds, credit units, insurance companies, and banks frequently encounter this type of problem. The objective function for portfolio selection problems usually is maximization of expected return or minimization of risk. The constraints usually are restrictions on the type of permissible investments, state laws, company policy, maximum permissible risk, etc.

82

LP Applications • Revenue Management – Involves managing the short-term demand for a fixed perishable inventory in order to maximize the revenue potential for an organization. – First developed by American Airlines to determine how many airline flight seats to sell at an early reservation discount fare and how many airline flight seats to sell at full fare. – The airline is able to increase its average number of passengers per flight and maximize the total revenue generated by the combined sale of discount-fare and full-fare seats. – Other applications include hotels, apartment rentals, car rentals, cruise lines, and golf courses.

2/8/2019

83

Blending Problem Seastrand Oil Company produces two grades of gasoline: regular and high octane. Both gasoline are produced by blending two types of crude oil. Although both types of crude oil contain the two important ingredients required to produce both gasoline, the percentage of important ingredients in each type of crude oil differs, as does the cost per gallon. The percentage of ingredients A and B in each type of crude oil and the cost per gallon are shown:

Crude Oil

Cost

Ingredient A

Ingredient B

1

$0.10

20%

60%

2

$0.15

50%

30%

Each gallon of regular gasoline must contain at least 40% of ingredient A, whereas each gallon of high octane can contain at most 50% of ingredient B. Daily demand for regular and high octane gasoline is 800,000 and 500,000 gallons, respectively. How many gallons of each type of crude oil should be used in the two gasoline to satisfy daily demand at a minimum cost?

2/8/2019

84

Exercise (Edwards Manufacturing) Edwards Manufacturing Co. purchases two component parts from three different suppliers. The suppliers have limited capacity, and no one supplier can meet all the company’s needs. In addition, the suppliers charge different prices for the components. Component price data (in price per unit) are as follows: Supplier Component 1

1

2

3

$12

$13

$14

2 $10 $11 $10 Each supplier has a limited capacity in terms of the total number of components it can supply. However, as long as Edwards provides sufficient advance orders, each supplier can devote its capacity to component 1, component 2 or any combination of the two components, if the total number of units ordered is within its capacity. Supplier capacities are as follows:

2/8/2019

Supplier

1

2

3

Capacity

600

1000

800 85

Exercise (Edwards Manufacturing) If the Edwards production plan for the next period includes 1000 units of component 1 and 800 units of component 2, what purchase do you recommend? That is, how many units of each component should be ordered from each supplier?

2/8/2019

86

Make-or-Buy Decision The Janders Company markets various business and engineering products. Currently, Janders is preparing to introduce two new calculators: one for the business market called the Financial Manager and one for the engineering market called the Technician. Each calculator has three components: a base, an electronic cartridge, and a faceplate or top. The same base is used for both calculators, but the cartridges and tops are different. All components can be manufactured by the company or purchased from outside suppliers. The manufacturing costs and purchase prices for the components are summarized in the table below.

2/8/2019

Cost per unit ($) Component Manufacture Purchase (regular time) Base 0.50 0.60 Financial cartridge 3.75 4.00 Technician cartridge 3.30 3.90 Financial top 0.60 0.65 Technician top 0.75 0.78

87

Make-or-Buy Decision Company forecasters indicate that 3000 Financial Manager calculators and 2000 Technician calculators will be needed. However, manufacturing capacity is limited. The company has 200 hours of regular manufacturing time and 50 hours of overtime that can be scheduled for the calculators. Overtime involves a premium at the additional cost of $9 per hour. The manufacturing times (in minutes) for the components are shown in the table below.

Component Base Financial cartridge Technician cartridge Financial top Technician top

Manufacturing time per unit (min) 1.0 3.0 2.5 1.0 1.5

The problem for Janders is to determine how many units of each component to manufacture and how many units of components to purchase. 2/8/2019

88

Production Scheduling Bollinger Electronics Company produces two different electronic components for a major airplane engine manufacturer. The airplane engine manufacturer notifies the Bollinger sales office each quarter of its monthly requirements for components for each of the next three months. The monthly requirements for the components may vary considerably, depending on the type of engine the airplane engine manufacturer is producing. The order shown in the table below has just been received for the next three-month period. The production cost per unit is the same each month Component

Unit cost

April

May

June

322A

$20

1000

3000

5000

802B

$10

1000

500

3000

After the order is processed, a demand statement is sent to the production control department. The production control department must then develop a three-month production plan for the components. In arriving at the desired schedule, the production manager will want to identify the following: (a) total production cost, (b) inventory holding cost, and (c) change-in-production-level cost 2/8/2019

89

Production Scheduling Bollinger determined that on a monthly basis inventory holding costs are 1.5% of the cost of the product. It is assumed that monthly ending inventories are an acceptable approximation to the average inventory levels throughout the month. After estimating the effects of employee layoffs, turnover, reassignment training costs, and other costs associated with fluctuating production levels, Bollinger estimates that the cost associated with increasing the production level for any month is $0.50 per unit increase. A similar cost associated with decreasing the production level for any month is $0.20 per unit. Suppose that the inventories at the beginning of the three-month scheduling period were 500 units for component 322A and 200 units for component 802B. The demand for both products in the first month (April) was 1000 units. The company specifies a minimum inventory level at the end of the three-month period of 400 units of component 322A and at least 200 units of component 802B.

2/8/2019

90

Production Scheduling Machine, labor, and storage capacity are given in the table below. Month

Machine Capacity (h)

Labor capacity (h)

Storage Capacity (sq. ft)

April

400

300

10,000

May

500

300

10,000

June

600

300

10,000

Machine, labor, and space requirements are given in the following table:

Machine (h/unit)

Labor (h/unit)

Storage (sq. ft./unit)

322A

0.10

0.05

2

802B

0.08

0.07

3

Component

The production level for March had been 1500 units of component 322A and 1000 units of component 802B for a total production of 2500 units. 2/8/2019

91

Marketing Research Market Survey Incorporated (MSI) specializes in evaluating consumer reaction to new products, services, and advertising campaigns. A client firm requested MSI’s assistance in ascertaining consumer reaction to a recently marketed household product. During meetings with the client, MSI agreed to conduct door-to-door personal interviews to obtain responses from households with children and households without children. In addition, MSI agreed to conduct both day and evening interviews. Specifically, the client’s contract called for MSI to conduct 1000 interviews under the following quota guidelines. 1. Interview at least 400 households with children 2. Interview at least 400 households without children 3. The total number of household interviewed during the evening must be at least as great as the number of households interviewed during the day. 4. At least 40% of the interviews for households with children must be conducted during the evening. 5. At least 60% of the interviews for households without children must be conducted during the evening. 2/8/2019

92

Marketing Research Because the interviews for households with children take additional interviewer time and because evening interviewers are paid more that daytime interviewers, the cost varies with the tyoe of interview. Based on previous research studies, estimates of the the interview costs are as follows:

Household

Interview Cost

Day

Evening

With children

$20

$25

No children

$18

$20

What is the household, time-of-day interview plan that will satisfy the contract requirements at a minimum total interviewing cost?

2/8/2019

93

Media Selection Relax-and-Enjoy Lake Development Corporation is developing a lakeside community at a privately owned lake. The primary market for the lakeside lots and homes includes all middle- and upper-income families within approximately 100 miles of the development. Relaxand-Enjoy employed the advertising firm of Boone, Phillips, and Jackson (BPJ) to design the promotional campaign.

After considering possible advertising media and the market to be served, BPJ recommended that the first month’s advertising be restricted to five media. At the end of the month, BPJ will then reevaluate its strategy based on the month’s results. BPJ collected data on the number of potential customers reached, the cost per advertisement, the maximum number of times each medium is available, and the exposure quality rating for each of the five media. The quality rating is measured in terms of an exposure quality unit, a measure of the relative value of one advertisement in each of the media. This measure, based on BPJ experience in the advertising business, takes into account factors such as audience demographics (age, income, and education of the audience reached), image presented, and quality of the advertisement. 2/8/2019

94

Media Selection Relax-and-Enjoy provided BPJ with an advertising budget of $30,000 for the first month’s campaign. In addition, Relax-and-Enjoy imposed the following restrictions on how BPJ may allocate these funds. At least 10 television commercials must be used, at least 50,000 potential customers must be reached, and no more than $18,000 may be spent on television advertisements. What advertising media selection plan should be recommended?

2/8/2019

95

Media Selection The information collected is presented in the table below.

Advertising Media

Number of potential customers reached

Maximum Times Exposure Available per Quality Units month*

Cost ($) per Ad

Daytime TV (1 min), station WKLA

1000

1500

15

65

Evening TV (30 sec), station WKLA

2000

3000

10

90

Daily newspaper (full page) The Morning Journal

1500

400

25

40

Sunday Newspaper Mag (1/2 page color), The Sunday Press

2500

1000

4

60

Radio, 0800 or 1700 news (30 sec), station KNOP

300

100

30

20

*The maximum number of times the medium is available is either the maximum number of times the advertising medium occurs (e.g. four Sundays per month) or the maximum number of times BPJ recommends that the medium be used. 2/8/2019

96

Portfolio Selection Consider the case of Welte Mutual Funds, Inc. Welte just obtained $100,000 by converting industrial bonds to cash and is now looking for other investment opportunities for these funds. Based on Welte’s current investments, the firm’s top financial analyst recommends that all new investments be made in the oil industry, steel industry, or in government bonds. Specifically, the analyst identified five investment opportunities and projected their annual rates of return. The investment and rates of return are shown in the table. Investment

2/8/2019

Projected Rate of Return (%)

Atlantic Oil

7.3

Pacific Oil

10.3

Midwest Steel

6.4

Huber Steel

7.5

Government Bonds

4.5

97

Portfolio Selection Management of Welte imposed the following investment guideline: 1. Neither industry (oil or steel), should receive more than $50,000. 2. Government bonds should be at least 25% of the steel industry investment. 3. The investment in Pacific Oil, the high return but high risk investment, cannot be more than 60% of the total oil industry investment. What portfolio recommendation – investments and amounts – should be made for the available $100,000?

2/8/2019

98

Revenue Management Leisure Air has two Boeing 737-400 airplanes, one based in Pittsburgh and the other in Newark. Both airplanes have a coach section with 132-seat capacity. Each morning the Pittsburgh-based airplane flies to Orlando with a stopover in Charlotte, and the Newark-based plane flies to Myrtle Beach, also with a stopover in Charlotte. At the end of the day, both planes return to their home bases. The logistics of the Leisure situation is shown in the figure below.

Pittsburgh P

Flight Leg 1

Flight Leg 4 Orlando O 2/8/2019

Flight Leg 2

Charlotte C

Newark N

Flight Leg 3 Myrtle M

99

Revenue Management Leisure Air has two fare classes: a discount-fare Q class and a fullfare Y class. Reservations during the discount-fare Q class must be made 14 days in advance and must include a Saturday night stay in the destination city. Reservations using the full-fare Y class may be made anytime, with no penalty for changing the reservation at a latter date. To determine the itinerary and fare alternatives that Leisure Air can offer its customers, we must consider not only the origin and destination of each flight, but also the fare class. For instance, possible products include Pittsburgh to Charlotte using Q-class, Newark to Orlando using Q-class, Charlotte to Myrtle Beach using Y class, and so on. Each product is referred to as an origin-destination itinerary fare (ODIF). For may 5, Leisure Air established fares and developed forecasts of customer demand for each of 16 ODIFs. These data are shown in the Table. Suppose that on April 14 a customer calls the leisure Air reservation office and requests a Q class seat on May 5 flight from Pittsburgh to Myrtle Beach. Should Leisure Air accept the reservation? How many Q and Y seats should be made available in order to operate its reservation system? 2/8/2019

100

ODIF

Origin

Destination

Fare Class

ODIF Code

Fare ($)

Forecasted demand

1

Pittsburgh

Charlotte

Q

PCQ

178

33

2

Pittsburgh

Myrtle Beach

Q

PMQ

268

44

3

Pittsburgh

Orlando

Q

POQ

228

45

4

Pittsburgh

Charlotte

Y

PCY

380

16

5

Pittsburgh

Myrtle Beach

Y

PMY

456

6

6

Pittsburgh

Orlando

Y

POY

560

11

7

Newark

Charlotte

Q

NCQ

199

26

8

Newark

Myrtle Beach

Q

NMQ

249

56

9

Newark

Orlando

Q

NOQ

349

39

10

Newark

Charlotte

Y

NCY

385

15

11

Newark

Myrtle Beach

Y

NMY

444

7

12

Newark

Orlando

Y

NOY

580

9

13

Charlotte

Myrtle beach

Q

CMQ

179

64

14

Charlotte

Myrtle Beach

Y

CMY

380

8

15

Charlotte

Orlando

Q

COQ

224

46

16

Charlotte

Orlando

Y

COY

582

10

2/8/2019

101