Transcript 3.1 A Linear Programming Problem

1.
2.
3.
4.
5.
6.
7.
8.
The Problem
Tabulate Data
Translate the Constraints
The Objective Function
Linear Programming Problem
Production Schedule
No Waste
Feasible Set
1

A furniture manufacturer makes two types of
furniture - chairs and sofas. The manufacture of a
chair requires 6 hours of carpentry, 1 hour of
finishing, and 2 hours of upholstery. Manufacture
of a sofa requires 3 hours of carpentry, 1 hour of
finishing, and 6 hours of upholstery. Each day the
factory has available 96 labor hours for carpentry,
18 labor-hours for finishing, and 72 labor-hours for
upholstery. The profit per chair is $80 and per sofa
is $70. How many chairs and sofas should be
produced each day to maximize the profit?
2

It is helpful to tabulate data given in the problem.
Chair
Sofa
Available time
Carpentry
6 hours
3 hours
96 labor-hours
Finishing
1 hour
1 hour
18 labor-hours
Upholstery
2 hours
6 hours
72 labor-hours
$80
$70
Profit
3


Translate each of the constraints (restrictions on
labor-hours available) into mathematical
language.
Let x be the number of chairs and y be the
number of sofas manufactured each day,
respectively.
4




Carpentry: [number of labor-hours per day]
= (number of hours required per chair) 
(number of chairs per day) + (number of hours
required per sofa)  (number of sofas per day)
= 6x + 3y
[number of labor-hours per day] < [maximum
available]
 6x + 3y < 96
5


Similarly,
Finishing:


x + y < 18
Upholstery:
2x + 6y < 72
Number of chairs and sofas cannot be
negative:

x > 0, y > 0


6



The objective of the problem is to optimize
profit. Translate the profit (objective function) into
mathematical language.
[profit] = [profit from chairs] + [profit from
sofas]
= [profit per chair][number of chairs] +
[profit per sofa][number of sofas]
 = 80x + 70y
7


The manufacturing problem can now be
written as a mathematical problem.
Find x and y for which 80x + 70y is as large as
possible, and for which the following hold
simultaneously:

3 y  96
6 x
x

y  18



6 y  72
2 x
 x  0, y  0.
This is called a linear programming problem.
8

In the manufacturing problem, each pair of
numbers (x,y) that satisfies the system of
inequalities is called a production schedule.
9

Which of the following is a production
schedule for

3 y  96
6 x
x

y  18



6 y  72
2 x
 x  0, y  0

(11,6)?
Yes
(6,11)?
No
10


It seems clear that a factory will operate most
efficiently when its labor is fully utilized (no
waste).
This would require x and y to satisfy the system
6 x  3 y  96

 x  y  18
2 x  6 y  72.

11

 3 y  96

 x  y  18
2 x  6 y  72.

6x
Solve 
According to the graph of the three
equations, there is no common
intersection and therefore no solution.
12

The set of solutions to the system of
inequalities is called the feasible set of the
system. This represents all possible production
schedules.
13

Find the feasible set for
6 x  3 y  96
x

y  18


2 x  6 y  72
 x  0 , y  0.
14






Notice that (0,0)
satisfies all the
inequalities.
Graph the boundaries:
y < -2x + 32
y < -x + 18
y < -x/3 + 12
x > 0, y > 0
Feasible Set
15

A linear programming problem asks us to find
the point (or points) in the feasible set of a
system of linear inequalities at which the value
of a linear expression involving the variables,
called the objective function, is either maximized
or minimized.
16