6s-1 Linear Programming
Operations Management
William J. Stevenson
8th edition
S.P.CHHEDA & CO.
6s-2 Linear Programming
S.P.CHHEDA & CO.
6s-3 Linear Programming
Linear Programming
Used to obtain optimal solutions to
problems that involve restrictions or
limitations, such as:
Materials
Budgets
Labor
Machine time
S.P.CHHEDA & CO.
6s-4 Linear Programming
Linear Programming
Linear programming (LP) techniques
consist of a sequence of steps that will
lead to an optimal solution to problems, in
cases where an optimum exists
S.P.CHHEDA & CO.
6s-5 Linear Programming
Linear Programming Model
Objective: the goal of an LP model is maximization or
minimization
Decision variables: amounts of either inputs or
outputs
Feasible solution space: the set of all feasible
combinations of decision variables as defined by the
constraints
Constraints: limitations that restrict the available
alternatives
Parameters: numerical values
S.P.CHHEDA & CO.
6s-6 Linear Programming
Linear Programming Assumptions
Linearity: the impact of decision variables is
linear in constraints and objective function
Divisibility: noninteger values of decision
variables are acceptable
Certainty: values of parameters are known and
constant
Nonnegativity: negative values of decision
variables are unacceptable
S.P.CHHEDA & CO.
6s-7 Linear Programming
Graphical Linear Programming
1. Set up objective function and
constraints in mathematical format
2. Plot the constraints
3. Identify the feasible solution space
4. Plot the objective function
5. Determine the optimum solution
S.P.CHHEDA & CO.
6s-8 Linear Programming
Linear Programming Example
Objective - profit
Maximize Z=60X1 + 50X2
Subject to
Assembly 4X1 + 10X2 <= 100 hours
Inspection 2X1 + 1X2 <= 22 hours
Storage 3X1 + 3X2 <= 39 cubic feet
X1, X2 >= 0
S.P.CHHEDA & CO.
6s-9 Linear Programming
Linear Programming Example
Assembly Constraint
4X1 +10X2 = 100
12
10
Product X2
8
6
4
2
0
0 2 4 6 8 10 12 14 16 18 20 22 24
Product X1
S.P.CHHEDA & CO.
6s-10 Linear Programming
Linear Programming Example
Add Inspection Constraint
2X1 + 1X2 = 22
25
20
Product X2
15
10
5
0
0 2 4 6 8 10 12 14 16 18 20 22 24
Product X1
S.P.CHHEDA & CO.
6s-11 Linear Programming
Linear Programming Example
Add Storage Constraint
3X1 + 3X2 = 39
25
Inspection
20
Product X2
15
Storage
Assembly
10
5
0
0 2 4 6 8 10 12 14 16 18 20 22 24
Feasible solution space Product X1
S.P.CHHEDA & CO.
6s-12 Linear Programming
Linear Programming Example
Add Profit Lines
25
20
Z=900
Product X2
15
10
5
0
0
14
10
12
16
18
20
22
24
Product X1
Z=300 Z=600
S.P.CHHEDA & CO.
6s-13 Linear Programming
Solution
The intersection of inspection and storage
Solve two equations in two unknowns
2X1 + 1X2 = 22
3X1 + 3X2 = 39
X1 = 9
X2 = 4
Z = $740
S.P.CHHEDA & CO.
6s-14 Linear Programming
Constraints
Redundant constraint: a constraint that
does not form a unique boundary of the
feasible solution space
Binding constraint: a constraint that forms
the optimal corner point of the feasible
solution space
S.P.CHHEDA & CO.
6s-15 Linear Programming
Slack and Surplus
Surplus: when the optimal values of decision
variables are substituted into a greater than or
equal to constraint and the resulting value
exceeds the right side value
Slack: when the optimal values of decision
variables are substituted into a less than or
equal to constraint and the resulting value is less
than the right side value
S.P.CHHEDA & CO.
6s-16 Linear Programming
Simplex Method
Simplex: a linear-programming
algorithm that can solve problems
having more than two decision
variables
S.P.CHHEDA & CO.
6s-17 Linear Programming
MS Excel Worksheet for
Microcomputer
Figure 6S.15
Problem
S.P.CHHEDA & CO.
6s-18 Linear Programming
MS Excel Worksheet Solution
Figure 6S.17
S.P.CHHEDA & CO.
6s-19 Linear Programming
Sensitivity Analysis
Range of optimality: the range of values for
which the solution quantities of the decision
variables remains the same
Range of feasibility: the range of values for
the fight-hand side of a constraint over which
the shadow price remains the same
Shadow prices: negative values indicating
how much a one-unit decrease in the original
amount of a constraint would decrease the
final value of the objective function
S.P.CHHEDA & CO.
