Linear Programming:
Model Formulation and
Graphic Solution
Chapter 2
Linear Programming
A Linear Programming model seeks to
maximize or minimize a linear function,
subject to a set of linear constraints.
The linear model consists of the
follow
ing components:
A set of decision variables. An objective
function.
A set of constraints.
Formulation of LPP
Formulation of LPP
A Maximization Model Example
Example :
The Beaver Creek Pottery Company
Given these limited resources, the company desires to know how
many bowls and mugs to produce each day in order to maximize
profit.
There are 40 hours of labor and 120 kg of clay available each day
for production.
5
Resource Requirements
Product Labor Clay Profit
(hr/unit) (kg/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50
6
Modeling
Decision Variables Objective Function
x1 : number of bowls to produce Total Profit = 40 x1 + 50 x2
x2 : number of mugs to produce
40 x1 = profit from bowls
50 x2 = profit from mugs
Maximize Z = 40 x1 + 50 x2
7
Model Constraints
Labor Constraint
Total Labor used in production = 1 x1 + 2 x2
1 x1 + 2 x2 ≤ 40 hr
Clay Constraint
Total Clay used in production = 4 x1 + 3 x2
4 x1 + 3 x2 ≤ 120 lb
Non-negativity Constraint
x1 ≥ 0, x2 ≥ 0
8
Linear Programming Model
Maximize Z = 40 x1 + 50 x2
Subject to:
1 x1 + 2 x2 ≤ 40
4 x1 + 3 x2 ≤ 120
x1, x2 ≥ 0
9
Feasible / Infeasible
If x1 = 5, x2 = 10 Z = 40 . 5 + 50 . 10 = 700
If x1 = 2, x2 = 2 Z = 40 . 2 + 50 . 2 = 180
If x1 = 10, x2 = 20 Z = 40 . 10 + 50 . 20 = 1400
If x1 = 20, x2 = 20 Z = 40 . 20 + 50 . 20 = 1800
10
Graphical Solution of
Linear Programming Models
60
50
40
30
Coordinates for 20
graphical
analysis 10
0 10 20 30 40 50 60
11
x2
Graph of the labor constraint line
60
50
40
30
20
x1 + 2 x2 = 40
10
0 10 20 30 40 50 60 x1
12
x2
The labor constraint area
60
50 M
40
30 L
20
x1 + 2 x2 ≤ 40
10 K
0 10 20 30 40 50 60 x1
13
x2
Graph of the labor constraint line
60
50
40
30
4 x1 + 3 x2 = 120
20
10
0 10 20 30 40 50 60 x1
14
x2
The clay constraint area
60
50 M
40
30 L
20
4 x1 + 3 x2 ≤ 120
10 K
0 10 20 30 40 50 60 x1
15
x2
Graph of both model constraints
60
50
40 4 x1 + 3 x2 = 120
30
20
10
x1 + 2 x2 = 40
0 10 20 30 40 50 60 x1
16
x2
The feasible solution area constraints
60
50
T: Infeasible
40 4 x1 + 3 x2 = 120
S: Infeasible
30
T
R: Feasible
20
S
10
R
x1 + 2 x2 = 40
0 10 20 30 40 50 60 x1
17
x2
Objective function line for Z = $ 800
60
50
40
30
800 = 40 x1 + 50 x2
20
10
0 10 20 30 40 50 60 x1
18
Alternative
x objective function lines for profits, Z,
2
of $ 800, $ 1200, $ 1600
40
800 = 40 x1 + 50 x2
30
1200 = 40 x1 + 50 x2
20
1600 = 40 x1 + 50 x2
10
0 10 20 30 40 x1
19
x2
Identification of optimal solution point
60
50
40
800 = 40 x1 + 50 x2
30
Optimal solution point
20
10
B
0 10 20 30 40 50 60 x1
20
x2 40
Optimal solution coordinates
35
4 x1 + 3 x2 = 120
30
25
20
A
15
10
B
8
x1 + 2 x2 = 40
5
C
0 5 10 15 20 25 30 35 40 x1
21
24
Prof. [Link]
x2 40 Solutions at all corners points
35
4 x1 + 3 x2 = 120
30 x1 = 0 bowls
x2 = 20 mugs
25 Z = $ 1,000
x1 = 24 bowls
20
A x2 = 8 mugs
Z = $ 1,360
x1 = 30 bowls
15
x2 = 0 mugs
Z = $ 1,200
10
B
8
5
x1 + 2 x2 = 40
C
22 0 5 10 15 20 24 25
Prof. [Link] 30 35 40 x1
x2 40 The optimal solution with Z = 70 x1 + 20 x2
35
4 x1 + 3 x2 = 120
30
25
20
A
Optimal solution point
x1 = 30 bowls
15
x2 = 0 mugs
Z = $ 1,200
10
B
5
x1 + 2 x2 = 40
C
0
23 5 10 15 20 [Link]
Prof. 25 30 35 40 x1
24
A Minimization Model Example
The Farmer’s Field
The farmer’s field requires at least 16 kg. of nitrogen
and 24 kg. of phosphate.
Super-gro costs $6 per bag, and Crop-quick costs $3.
The farmer wants to know how many bags of each brand to
purchase in order to minimize the total cost of fertilizing.
25
Example: The Farmer’s Field
Chemical Contribution
Brand Nitrogen Phosphate
(kg./bag) (kg./bag)
Super-gro 2 4
Crop-quick 4 3
26
Linear Programming Model
Minimize Z = 6 x1 + 3 x2
Subject to:
2 x1 + 4 x2 ≥ 16
4 x1 + 3 x2 ≥ 24
x1, x2 ≥ 0
27
Constraint lines for fertilizer model
x2
12
10
8
4 x1 + 3 x2 = 24
2
2 x1 + 4 x2 = 16
28 0 2 4 6 8 10
Prof. [Link] 12 14 16 x1
Feasible solution area
x2
12
10
8
4 x1 + 3 x2 = 24
6
Feasible solution area
2
2 x1 + 4 x2 = 16
x1
0 2 4 6 8 10 12
29
The optimal solution point
x2
12 Optimal solution point
x1 = 0 bags of Super-gro
10 x2 = 8 bags of Crop-quick
Z = $ 24
A
8
6
Z = 6 x1 + 3 x2
4
2 B
C
x1
0 2 4 6 8 10 12
30
Irregular Types of
Linear Programming
Problems
x2 40 Multiple Optimal Solutions
35
30
Point B Point C
25
x1 = 24 x1 = 30 bowls
20
A x2 = 8 x2 = 0 mugs
Z = $ 1,200 Z = $ 1,200
15
10
B
5
C
0
32 5 10 15 20 [Link]
Prof. 25 30 35 40 x1
An Infeasible Problem
x2
12 x1 = 4
10
C
8
6 x2 = 6
4 B
4 x1 + 2 x2 = 8
2
A
x1
0 2 4 6 8 10 12
33
An Unbounded Problem
x2 x1 = 4
12 Maximize Z = 4 x1 + 2 x2
Z=
10 Subject to:
4 x1
x1 ≥ 4
+2
8 x2 ≤ 6
x2
x 1, x 2 ≥ 0
6 x2 = 6
x1
0 2 4 6 8 10 12
34
35
