Linear

Programming
Problems
Graphical Method
Example - designing a diet
A dietitian wants to design a breakfast menu for
certain hospital patients. The menu is to
include two items A and B. Suppose that
each ounce of A provides 2 units of vitamin C
and 2 units of iron and each ounce of B provides
1 unit of vitamin C and 2 units of iron. Suppose
the cost of A is 4$/ounce and the cost of B is
3$/ounce. If the breakfast menu must provide
at least 8 units of vitamin C and 10 units of iron,
how many ounces of each item should be
provided in order to meet the iron and vitamin C
requirements for the least cost? What will this
breakfast cost?
 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
8 iron: 2x + 2y
≥10
x ≥ 0, y ≥ 0

Min z = 4x+3y
2x+y = 8 2x+2y = 10
If x=0,then y=8 If x=0,then y=10/2=5
If y =0 then x=8/2=4 If y =0 then x=10/2=5
Finally (4,8) Finally (5,5)

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
vit. c 8 iron:2x + 2y ≥10
x ≥ 0, y ≥ 0

Cost = C = 4x+3y

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
vit. c 8 iron:2x + 2y ≥10
x ≥ 0, y ≥ 0

Cost = C = 4x+3y

iron

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
vit. c 8 iron:2x + 2y ≥10
x ≥ 0, y ≥ 0

Cost = C = 4x+3y

iron

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
vit. c 8 iron:2x + 2y ≥10
x ≥ 0, y ≥ 0

iron

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B

corner pt. C = 4x + 3y
vit. c (0,8)
(5,0)
(3,2)

iron

COPYRIGHT © 2006 by LAVON B. PAGE

 x = #oz. of A
y = #oz. of B
corner pt.
(0,8)
(5,0)
(3,2)
X =0 ,y = 8 X = 5 ,y = 0 X = 3,y = 2
C= 4x+3y C= 4x+3y C= 4x+3y
C= 4(0)+3(8) C= 4(5)+3(0) C= 4(3)+3(2)
C= 0+24 C= 20+0 C= 12+6
C= 24 C= 20 C= 18
COPYRIGHT © 2006 by LAVON B. PAGE
 x = #oz. of A
y = #oz. of B
The cost will be minimized if the
vit. C: followed
strategy 2x +isy the
≥ one
vit. c corresponding
8 iron:2x + to2y this
≥ corner
point
10
x ≥ 0, y ≥Cost
0 = C = 4x+3y
The 3 blue lines are
48 = 4x+3y
36 = 4x+3y
24 = 4x+3y
iron
 x = #oz. of A
y = #oz. of B

vit. C: 2x + y ≥
vit. c 8 iron:2x + 2y ≥10
x ≥ 0, y ≥ 0

2x + y = 8
2x + 2y = 10
Solution: x=3, y=2
C = 4x + 3y = 18$
iron
Example - bicycle factories
A small business makes 3-speed and 10-speed
bicycles at two different factories. Factory A
produces 16 3-speed and 20 10-speed bikes in
one day while factory B produces 12 3-speed
and 20 10-speed bikes daily. It costs
$1000/day to operate factory A and $800/day
to operate factory B. An order for 96
3-speed bikes and 140 10-speed bikes has
just arrived.
How many days should each factory be
operated in order to fill this order at a minimum
cost? What is the minimum cost?

x = # days factory A is operated

y = # days factory B is operated
Minimize Z = 1000x + 800y

3-speed constraint: 16x + 12y ≥96

.

3-speed constraint: 16x + 12y ≥ 96

10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
 x = # days factory A is operated
y = # days factory B is operated

Minimize Z = 1000x + 800y

Sub to:
16x + 12y ≥ 96
20x + 20y ≥140
x ≥ 0, y ≥ 0
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

16x + 12y ≥96

16X+12Y =96
If X= 0, 16(0)+12Y=96
0+12Y=96,Y=96/12=8
If Y= 0 , 16X+12(0)=96
16X+0=96, X=96/16= 6
X=6,Y=8
3-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y
20x + 20y ≥140
20X+20Y=140
If X=0, 20(0)+20Y=140
0+20Y=140,
Y=140/20=7
If y=0
20x+0=140,X=7
3-speed X=7,Y=7
10-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

3-speed
10-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

corner pts C = 1000x + 800y

3-speed
10-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

corner pts C = 1000x + 800y

(0,8) 1000(0)+800(8)
0+6400
=6400

3-speed
10-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

corner pts C = 1000x + 800y

(0,8) $6400
(7,0) 1000(7)+800(0)
7000

3-speed
10-speed
 x = # days factory A is operated
y = # days factory B is operated
3-speed constraint: 16x + 12y ≥ 96
10-speed constraint: 20x + 20y ≥140
x ≥ 0, y ≥ 0
Minimize: C = 1000x + 800y

corner pts C = 1000x + 800y

(0,8) $6400
(7,0) $7000
1000(3)+800(4)
3000+3200= 6200
(3,4)
3-speed
10-speed
Example - manufacturing
AGDM &Co makes Tables and beds.A table
requires 2 man-hours for cutting, 1 man-hour for
shaping and 3 man-hours for finishing while a bed
requires 2 man-hours for cutting, 2 man-hours for
shaping and 1 man-hour for finishing. Each day
the company has available 140 man-hours for
cutting, 120 man-hours for shaping and 150
man-hours for finishing.How many each type of
item should the company manufacture each day in
order to maximize profit if a table yields a profit of
$10 and a bed yields a profit of $8?
 x = # table
y = # bed

cutting: 2x + 2y ≤ 140
shaping: x + 2y ≤ 120
finishing: 3x + y ≤ 150
x≥0,y≥0

Max Z = 10x + 8y
 x = # table
y = # bed

cutting: 2x + 2y = 140
shaping: x + 2y = 120
finishing: 3x + y = 150
x≥0,y≥0
P = 10x + 8y
2X+2Y=140
If X=0,
2(0)+2y=140, 2Y=140,
Y=140/2= 70
If Y=0, 2X+0=140
X=140/2= 70
cutting
 x = # table
y = # bed

cutting: 2x + 2y = 140
shaping: x + 2y = 120
finishing: 3x + y = 150
x≥0,y≥0
P = 10x + 8y
X+2Y=120, If X=0
0+2Y=120, Y=120/2= 60
IF Y=0, X+0=120, X=120

shaping
cutting
 x = # table
y = # bed

cutting: 2x + 2y = 140
shaping: x + 2y = 120
finishing: 3x + y = 150 x
≥0,y≥0
finishing P = 10x + 8y
3X+Y=150, IF X=0
0+Y=150, Y =150
IF Y=0, 3X+0=150
X=150/3= 50

shaping
cutting
 x = # table
y = # bed

cutting: 2x + 2y " 140

shaping: x + 2y " 120
finishing: 3x + y " 150
x≥0,y≥0
finishing
P = 10x + 8y

shaping
cutting
 x = # table
y = # bed

cutting: 2x + 2y " 140

shaping: x + 2y " 120
finishing: 3x + y " 150
x≥0,y≥0
finishing
P = 10x + 8y

shaping
cutting
 x = # table
y = # bed

cutting: 2x + 2y " 140

shaping: x + 2y " 120
finishing: 3x + y " 150
x≥0,y≥0
finishing
P = 10x + 8y
corners P = 10x + 8y
(0,0) 10(0)+8(0)$0
(0,60) $480
(20,50) $600
shaping (40,30) $640
cutting (50,0) $500
 x = # of TABLE
y = # of BED

cutting: 2x + 2y " 140

shaping: x + 2y " 120
finishing: 3x + y " 150
x≥0,y≥0
finishing
P = 10x + 8y
Make 40 TABLES corners P = 10x + 8y
and 30 BEDS for (0,0) $0
a profit of $640
(0,60) $480
cutting (20,50) $600
(40,30) $640
(50,0) $500