INTRODUCTION TO LINEAR PROGRAMMING

- Flair Furniture produces inexpensive tables and

INTRODUCTION chairs,
- Many management decisions involve making the - Processes are similar, both require carpentry work
most effective use of limited resources. and painting and varnishing.
- Linear Programming (LP) - Each table takes 4 hours of carpentry and 2 hours of
– Widely used mathematical modeling technique painting and varnishing.
Interest rates - Each chair requires 3 of carpentry and 1 hour of
– Planning and decision making relative to painting and varnishing.
resource allocation. - There are 240 hours of carpentry time available and
- Broader field of mathematical programming. 100 hours of painting and varnishing.
– Here programming refers to modeling and - Each table yields a profit of $70 and each chair a profit
solving a problem mathematically of $50
- The company wants to determine the best
REQUIREMENTS OF A LINEAR PROGRAMMING PROBLEM combination of tables and chairs to produce to reach
- Four properties in common: the maximum profit.
– Seek to maximize or minimize some quantity (the Hours required to
objective function). produce 1 unit
– Restrictions or constraints are present.
– Alternative courses of action are available. Department Tables Chairs Avail hours
– Linear equations or inequalities. (T) (C) this week
Carpentry 4 3 240
LP PROPERTIES AND ASSUMPTIONS Paint/Varnish 2 1
Profit per unit $70 $50
PROPERTIES OF LINEAR PROGRAMS
1. One objective function - The objective is to MAXIMIZE PROFIT
2. One or more constraints - The constraints are:
3. Alternative courses of action 1. The hours of carpentry time used cannot exceed
4. Objective function and constraints are linear – 240 hours per week.
proportionality and divisibility 2. The hours of painting and varnishing time used
5. Certainty cannot exceed 100 hours per week.
6. Divisibility - The decision variables are:
7. Nonnegative variables T = number of tables to be produced per week
C = number of chairs to be produced per week
FORMULATION LP PROBLEMS - Create objective function in terms of T and C
- Developing a mathematical model to represent the – Maximize Profit = $70T + $50C
managerial problem. - Develop mathematical relationships for the two
- Steps in formulating a LP problem: constraints.
1. Completely understand the managerial problem – For carpentry, total time used is:
being faced. (4 hrs per table)( # of Tables produced) + (3 hrs
2. Identify the objective and the constraints. per chair) ( # of chairs produced)
3. Define the decision variables.
4. Use the decision variables to write mathematical – First constraint is:
expressions for the objective function and the Carpentry time used ≤ Carpentry time available
constraints.
4T + 3C ≤ 240 (hours of carpentry time)
COMMON LP APPLICATION
- Product mix problem – Similarly
- Two or more products are produced using limited Painting and varnishing time used ≤ Painting
resources. and varnishing time available
- Maximize profit based on the profit contribution per
unit of each product. 2 T + 1C ≤ 100 (hours of painting and varnishing time)
- Determine how many units of each product to
produce. – Both of these constraints restrict production
capacity and affect total profit.
FOR EXAMPLE: – The values of T and C must be nonnegative.

1|P a ge
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)

- To complete the problem stated mathematically

Maximize Profit = $70T + $50C

- Subject to:
– 4T + 3C ≤ 240 (Carpentry constraint)
– 2T + 1c ≤ 100 (Paint/Varnish constraint)
– T, C ≥ 0 ( Nonnegative constraint)

GRAPHICAL SOLUTION TO A 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.
- 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

- 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.

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

solutions. - Any point inside this region is a feasible solution.
2. Plot each constraint equation on a graph. Any point outside the region is an infeasible solution.
3. Graph the equality portion of the constraint
equations 4T + 3C = 240.
4. Solve for the axis intercepts and draw the line

- 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 - For the point (30, 20)
– Carpentry constraint
- This line is shown on the following graph. 4T + 3C ≤ 240 hours available (4)(30) + (3)(20) = 180
hours used ✓
– Painting constraint
2T + 1C ≤ 100 hours available (2)(30) + (1)(20) = 80
hours used ✓

2|P a ge
 – Carpentry constraint
4T + 3C ≤ 240 hours available (4)(70) + (3)(40) = 400
hours used X
– Painting constraint
2T + 1C ≤ 100 hours available (2)(70) + (1)(40) = 180
hours used X

- For the point (50, 5)

– Carpentry constraint
4T + 3C ≤ 240 hours available (4)(50) + (3)(5) = 215
hours used ✓ CORNER POINT SOLUTION METHOD
– Painting constraint - The corner point method for solving LP problems
2T + 1C ≤ 100 hours available (2)(50) + (1)(5) = 105 - Look at the profit at every corner point of the
hours used X feasible region
- Mathematical theory is that an optimal solution
ISPROFIT LINE SOLUTION METHOD must lie at one of the corner points or extreme
- Find the optimal solution from the many possible points
solutions.
- Speediest method is to use the isoprofit line.
- Starting with a small possible profit value, graph the
objective function.
- Move the objective function line in the direction of
increasing profit while maintaining the slope.
- The last point it touches in the feasible region is the
optimal solution.
- Choose a profit of $2,100
- The objective function is $2,100 = 70T + 50C - Solve for the intersection of the two constraint lines
- Solving for the axis intercepts, draw the graph - Using the elimination method to solve simultaneous
- Obviously not the best possible solution equations method, select a variable to be eliminated
- Further graphs can be created using larger profits – - Eliminate T by multiplying the second equation by –2
The further we move from the origin, the larger the and add it to the first equation
profit
- The highest profit ($4,100) will be generated when – 2(2T + 1C = 100) = – 4T – 2C = –200
the isoprofit line passes through the point (30, 40)
4T + 3C = 240 (carpentry)
– 4T – 2C = –200 (painting)
C = 40
- Substitute C = 40 into either equation to solve for T

4T + 3(40) = 240
4T + 120 = 240
4T = 120
T = 30

# of Tables (T) # of Chairs (T) Profit = $70T +

$50C
0 0 $0
50 0 $3500
0 80 $4000
30 40 $4100
Highest Profit – Optimal Solution

SLACK
- It is the amount of a resource that is not used.
- For a less-than-or-equal constraint.

3|P a ge
Slack = (Amount of resource available) – (Amount of resource USING EXCEL’S SOLVER
used) - The Solver tool in Excel can be used to find solutions
to:
- Flair decides to produce 20 tables and 25 chairs – LP problems
- – Integer programming problems
4(20) + 3(25) = 155 (carpentry time used) – Noninteger programming problems
240 = (carpentry time available) – Solver is limited to 200 variables and, in
240 – 155 = 85 (Slack time in carpentry) some situations, 100 constraints

- At the optimal solution, slack is 0 as all 240 hours are USING SOLVER
used. - Recall the model for Flair Furniture is

SURPLUS Maximize profit = $70T + $50C

- It is used with a greater-than-or-equal-to constraint
to indicate the amount by which the right-hand side Subject to
of the constraint is exceeded. 4T + 3C ≤ 240 2T + 1C ≤ 100

Surplus = (Actual Amount) – (Minimum Amount) - To use Solver, it is necessary to enter data and
formulas.
- New constraint:
T + C ≥ 42 STEPS:
- If T = 20 and C = 25, then 1. Enter problem data
20 + 25 = 45 – Variable names, coefficients for the
Surplus = 45 – 42 = 3 objective function and constraints, RHS
values for each constraint.
SUMMARIES OF GRAPHICAL SOLUTION METHODS 2. Designate specific cells for the values of the decision
variables.
ISOPROFIT METHOD 3. Write a formula to calculate the value of the
1. Graph all constraints and find the feasible region. objective function.
2. Select a specific profit (or cost) line and graph it to 4. Write a formula to compute the left-hand sides of
find the slope. each of the constraints.
3. Move the objective function line in the direction of
increasing profit (or decreasing cost) while - Excel Data Input
maintaining the slope. The last point it touches in
the feasible region is the optimal solution.
4. Find the values of the decision variables at this last
point and compute the profit (or cost).

CORNER POINT METHOD

1. Graph all constraints and find the feasible region.
2. Find the corner points of the feasible reason.
3. Compute the profit (or cost) at each of the feasible
corner points.
4. Select the corner point with the best value of the
objective function found in Step 3. This is the
optimal solution. - Formulas

SOLVING FLAIR FURNITURE’S LP PROBLEM

- Most organizations have access to software to solve
big LP problems.
- There are differences between software
implementations, the approach is basically the same.
- With experience with computerized LP algorithms, it
is easy to adjust to minor changes.

4|P a ge
- Excel Spreadsheet - Solver Add Constraint Dialog Box

- Solver Results Dialog Box

- Starting Solver

- Solver Parameters Dialog Box

- Solution

5|P a ge