What is an isoprofit line

Linear Programming Models: Graphical and Computer Methods

7

To accompany Quantitative Analysis for Management, Twelfth Edition,

by Render, Stair, Hanna and Hale

Power Point slides created by Jeff Heyl

Copyright ©2015 Pearson Education, Inc.

After completing this chapter, students will be able to:

LEARNING OBJECTIVES

Copyright ©2015 Pearson Education, Inc.

7 – 2

Understand the basic assumptions and properties of linear programming (LP).

Graphically solve any LP problem that has only two variables by both the corner point and isoprofit line methods.

Understand special issues in LP such as infeasibility, unboundedness, redundancy, and alternative optimal solutions.

Understand the role of sensitivity analysis.

Use Excel spreadsheets to solve LP problems.

Copyright ©2015 Pearson Education, Inc.

7 – 3

7.1 Introduction

7.2 Requirements of a Linear Programming Problem

7.3 Formulating LP Problems

7.4 Graphical Solution to an LP Problem

7.5 Solving Flair Furniture’s LP Problem using QM for Windows, Excel 2013, and Excel QM

7.6 Solving Minimization Problems

7.7 Four Special Cases in LP

7.8 Sensitivity Analysis

CHAPTER OUTLINE

Introduction

Many management decisions involve making the most effective use of limited resources

Linear programming (LP)

Widely used mathematical modeling technique

Planning and decision making relative to resource allocation

Broader field of mathematical programming

Here programming refers to modeling and solving a problem mathematically

Copyright ©2015 Pearson Education, Inc.

7 – 4

Requirements of a Linear Programming Problem

Four properties in common

Seek to maximize or minimize some quantity (the objective function)

Restrictions or constraints are present

Alternative courses of action are available

Linear equations or inequalities

Copyright ©2015 Pearson Education, Inc.

7 – 5

LP Properties and Assumptions

PROPERTIES OF LINEAR PROGRAMS
1. One objective function
2. One or more constraints
3. Alternative courses of action
4. Objective function and constraints are linear – proportionality and divisibility
5. Certainty
6. Divisibility
7. Nonnegative variables
TABLE 7.1

Copyright ©2015 Pearson Education, Inc.

7 – 6

Formulating LP Problems

Developing a mathematical model to represent the managerial problem

Steps in formulating a LP problem

Completely understand the managerial problem being faced

Identify the objective and the constraints

Define the decision variables

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

Copyright ©2015 Pearson Education, Inc.

7 – 7

Formulating LP Problems

Common LP application – product mix problem

Two or more products are produced using limited resources

Maximize profit based on the profit contribution per unit of each product

Determine how many units of each product to produce

Copyright ©2015 Pearson Education, Inc.

7 – 8

Flair Furniture Company

Flair Furniture produces inexpensive tables and chairs

Processes are similar, both require carpentry work and painting and varnishing

Each table takes 4 hours of carpentry and 2 hours of painting and varnishing

Each chair requires 3 of carpentry and 1 hour of painting and varnishing

There are 240 hours of carpentry time available and 100 hours of painting and varnishing

Each table yields a profit of $70 and each chair a profit of $50

Copyright ©2015 Pearson Education, Inc.

7 – 9

Flair Furniture Company

The company wants to determine the best combination of tables and chairs to produce to reach the maximum profit

HOURS REQUIRED TO PRODUCE 1 UNIT
DEPARTMENT (T) TABLES (C) CHAIRS AVAILABLE HOURS THIS WEEK
Carpentry 4 3 240
Painting and varnishing 2 1 100
Profit per unit $70 $50
TABLE 7.2

Copyright ©2015 Pearson Education, Inc.

7 – 10

Flair Furniture Company

The objective is

Maximize profit

The constraints are

The hours of carpentry time used cannot exceed 240 hours per week

The hours of painting and varnishing time used cannot exceed 100 hours per week

The decision variables are

T = number of tables to be produced per week

C = number of chairs to be produced per week

Copyright ©2015 Pearson Education, Inc.

7 – 11

Flair Furniture Company

Create objective function in terms of T and C

Maximize profit = $70T + $50C

Develop mathematical relationships for the two constraints

For carpentry, total time used is

(4 hours per table)(Number of tables produced) + (3 hours per chair)(Number of chairs produced)

First constraint is

Carpentry time used ≤ Carpentry time available

4T + 3C ≤ 240 (hours of carpentry time)

Copyright ©2015 Pearson Education, Inc.

7 – 12

Flair Furniture Company

Similarly

Painting and varnishing time used ≤ Painting and varnishing time available

2 T + 1C ≤ 100 (hours of painting and varnishing time)

This means that each table produced requires two hours of painting and varnishing time

Both of these constraints restrict production capacity and affect total profit

Copyright ©2015 Pearson Education, Inc.

7 – 13

Flair Furniture Company

The values for T and C must be nonnegative

T ≥ 0 (number of tables produced is greater than or equal to 0)

C ≥ 0 (number of chairs produced is greater than or equal to 0)

The complete problem stated mathematically

Maximize profit = $70T + $50C

subject to

4T + 3C ≤ 240 (carpentry constraint)

2T + 1C ≤ 100 (painting and varnishing constraint)

T, C ≥ 0 (nonnegativity constraint)

Copyright ©2015 Pearson Education, Inc.

7 – 14

Graphical Solution to an LP Problem

Easiest way to solve a small LP problems is graphically

Only works when there are just two decision variables

Not possible to plot a solution for more than two variables

Provides valuable insight into how other approaches work

Nonnegativity constraints mean that we are always working in the first (or northeast) quadrant of a graph

Copyright ©2015 Pearson Education, Inc.

7 – 15

Graphical Representation of Constraints

100 –

–

80 –

–

60 –

–

40 –

–

20 –

–

C

| | | | | | | | | | | |

0 20 40 60 80 100

T

Number of Chairs

Number of Tables

This Axis Represents the Constraint T ≥ 0

This Axis Represents the Constraint C ≥ 0

FIGURE 7.1 – Quadrant Containing All Positive Values

Copyright ©2015 Pearson Education, Inc.

7 – 16

Graphical Representation of Constraints

The first step is to identify a set or region of feasible solutions

Plot each constraint equation on a graph

Graph the equality portion of the constraint equations

4T + 3C = 240

Solve for the axis intercepts and draw the line

Copyright ©2015 Pearson Education, Inc.

7 – 17

Graphical Representation of Constraints

When Flair produces no tables, the carpentry constraint is:

4(0) + 3C = 240

3C = 240

C = 80

Similarly for no chairs:

4T + 3(0) = 240

4T = 240

T = 60

This line is shown on the following graph

Copyright ©2015 Pearson Education, Inc.

7 – 18

Graphical Representation of Constraints

100 –

–

80 –

–

60 –

–

40 –

–

20 –

–

C

| | | | | | | | | | | |

0 20 40 60 80 100

T

Number of Chairs

Number of Tables

(T = 0, C = 80)

FIGURE 7.2 – Graph of Carpentry Constraint Equation

(T = 60, C = 0)

Copyright ©2015 Pearson Education, Inc.

7 – 19

FIGURE 7.3 – Region that Satisfies the Carpentry Constraint

Graphical Representation of Constraints

100 –

–

80 –

–

60 –

–

40 –

–

20 –

–

C

| | | | | | | | | | | |

0 20 40 60 80 100

T

Number of Chairs

Number of Tables

Any point on or below the constraint plot will not violate the restriction

Any point above the plot will violate the restriction

(30, 40)

(30, 20)

(70, 40)

Copyright ©2015 Pearson Education, Inc.

7 – 20

Graphical Representation of Constraints

The point (30, 40) lies on the line and exactly satisfies the constraint

4(30) + 3(40) = 240

The point (30, 20) lies below the line and satisfies the constraint

4(30) + 3(20) = 180

The point (70, 40) lies above the line and does not satisfy the constraint

4(70) + 3(40) = 400

Copyright ©2015 Pearson Education, Inc.

7 – 21

Graphical Representation of Constraints

100 –

–

80 –

–

60 –

–

40 –

–

20 –

–

C

| | | | | | | | | | | |

0 20 40 60 80 100

T

Number of Chairs

Number of Tables

(T = 0, C = 100)

FIGURE 7.4 – Region that Satisfies the Painting and Varnishing Constraint

(T = 50, C = 0)

Copyright ©2015 Pearson Education, Inc.

7 – 22

Graphical Representation of Constraints

To produce tables and chairs, both departments must be used

Find a solution that satisfies both constraints simultaneously

A new graph shows both constraint plots

The feasible region is where all constraints are satisfied

Any point inside this region is a feasible solution

Any point outside the region is an infeasible solution