1
Introduction to Modeling &
Linear Programming
BY… ASSOC. PROF. CHOMPOONOOT KASEMSET, [Link].
© 2020 Department of Industrial Engineering, Chiang Mai University
Operations Research (OR) 2
A scientific approach to decision making that seeks to best
design and operate a system, usually under conditions
requiring the allocation of scarce resources.
The scientific approach to decision making usually involves
the use of one or more mathematical models.
A mathematical model is a mathematical representation of
an actual situation that may be used to make better
decisions or simply to understand the actual situation better.
© 2020 Department of Industrial Engineering, Chiang Mai University
Prescriptive or Optimization Models 3
A prescriptive model “prescribes” behavior for an
organization that will enable it to best meet its goal(s).
The components of a prescriptive model include
Objective function(s)
Decision variables
Constraints
© 2020 Department of Industrial Engineering, Chiang Mai University
Type of Models 4
Static and Dynamic Models
Linear and Nonlinear Models
Integer and Noninteger Models
Deterministic and Stochastic Models
© 2020 Department of Industrial Engineering, Chiang Mai University
Model-Building Process 5
Step 1: Formulate the Problem
Step 2: Observe the System
Step 3: Formulate a Mathematical Model of the Problem
Step 4: Verify the Model and Use the Model for Prediction
Step 5: Select a Suitable Alternative
Step 6: Present the Results and Conclusion of the Study to
the Organization
Step 7: Implement and Evaluate Recommendations
© 2020 Department of Industrial Engineering, Chiang Mai University
What Is a Linear Programming Problem (LP)? 6
© 2020 Department of Industrial Engineering, Chiang Mai University
Example 1: Giapetto’s Woodcarving 7
© 2020 Department of Industrial Engineering, Chiang Mai University
Example 1: Solution 8
Model Formulation:
Decision Variables:
Objective Function:
Constraints
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Assumptions 9
The Proportionality and Additivity Assumptions
The Divisibility Assumption
The Certainty Assumption
© 2020 Department of Industrial Engineering, Chiang Mai University
Solutions in LP 10
Feasible Region and Optimal Solution
© 2020 Department of Industrial Engineering, Chiang Mai University
The Graphical Solution of Two-Variable Linear 11
Programming Problems
Finding the Feasible Solution
For a point (x1, x2) to be in the feasible region,
(x1, x2) must satisfy all the inequalities (2)–(6).
© 2020 Department of Industrial Engineering, Chiang Mai University
The Graphical Solution of Two-Variable Linear 12
Programming Problems
Find the Optimal Solution
Max Z = 3X1 + 2X2
Slope = -3/2
Optimal Solution:
(X1 = 20, X2 = 60)
Max Z = 3(20)+2(60) = 180
© 2020 Department of Industrial Engineering, Chiang Mai University
The Graphical Solution of Two-Variable Linear 13
Programming Problems
Binding and Nonbinding Constraints
© 2020 Department of Industrial Engineering, Chiang Mai University
The Graphical Solution of Two-Variable Linear 14
Programming Problems
Convex Sets, Extreme Points, and LP
© 2020 Department of Industrial Engineering, Chiang Mai University
The Graphical Solution of Minimization 15
Problems
© 2020 Department of Industrial Engineering, Chiang Mai University
Example 2: Dorain Auto 16
© 2020 Department of Industrial Engineering, Chiang Mai University
Example 2: Dorain Auto 17
Find the Optimal Solution
Min Z = 50X1 + 100X2
Slope = -1/2
Optimal Solution:
(X1 = 3.6, X2 = 1.4)
Min Z = 50(3.6)+100(1.4) = 320
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 18
Do not have unique optimal solutions.
1. Some LPs have an infinite number of optimal solutions
(alternative or multiple optimal solutions).
2. Some LPs have no feasible solutions (infeasible LPs).
3. Some LPs are unbounded: There are points in the feasible
region with arbitrarily large (in a max problem) z-values.
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 19
1. Alternative or Multiple Optimal Solutions
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 20
Example 3
the entire line segment AE
Max Z = 120
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 21
2. Infeasible LP
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 22
Example 4
© 2020 Department of Industrial Engineering, Chiang Mai University
Special Cases 23
3. Unbounded LP
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: A Diet Problem 24
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: A Work-scheduling Problem 25
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: Blending Problems 26
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: Production Process Model 27
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: Multi-period Inventory Model 28
© 2020 Department of Industrial Engineering, Chiang Mai University
LP Formulation: Multi-period Work Scheduling 29
© 2020 Department of Industrial Engineering, Chiang Mai University
Q&A 30
© 2020 Department of Industrial Engineering, Chiang Mai University