6s-1 Linear Programming
Linear
Programming
McGraw-Hill/Irwin
6s-2 Linear Programming
Used to obtain optimal solutions to
problems that involve restrictions or
limitations, such as:
Materials
Budgets
Labor
Machine time
6s-3 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
6s-4 Linear Programming
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
6s-5 Linear Programming
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
6s-6 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
6s-7 Linear Programming
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
6s-8 Linear Programming
Assembly Constraint
4X1 +10X2 = 100
12
10
Product X2
8
6
4
2
0
0
8
10
12
14
16
18
20
22
24
Product X1
6s-9 Linear Programming
Add Inspection Constraint
2X1 + 1X2 = 22
25
20
Product X2
15
10
5
0
0
8
10
12
14
16
18
20
22
24
Product X1
6s-10 Linear Programming
Add Storage Constraint
3X1 + 3X2 = 39
25 Inspection
20 Storage
Product X2
Assembly
15
10
5
0
Feasible solution space
0
8
10
12
14
16
18
20
22
24
Product X1
6s-11 Linear Programming
Add Profit Lines
25
20 Z=900
Product X2
15
10
5
0 Z=300 Z=600
0
8
10
12
14
16
18
20
22
24
Product X1
6s-12 Linear Programming
The intersection of inspection and storage
Solve two equations in two unknowns
2X1 + 1X2 = 22
3X1 + 3X2 = 39
X1 = 9
X2 = 4
Z = $740
6s-13 Linear Programming
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
6s-14 Linear Programming
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
6s-15 Linear Programming
Simplex: a linear-programming
algorithm that can solve problems having
more than two decision variables
6s-16 Linear Programming
Figure 6S.15
6s-17 Linear Programming
Figure 6S.17
6s-18 Linear Programming
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
6s-19 Linear Programming
Pls. watch and study
1.
https://www.youtube.com/watch?v=0TD9EQcheZM&list=RDC
MUC1S4Jeodbr5EbsCOIgBWJPQ&start_radio=1&t=13
2.
https://www.youtube.com/watch?v=pP0Qag694Go&list=RDC
MUC1S4Jeodbr5EbsCOIgBWJPQ&index=2
3.
https://www.youtube.com/watch?v=4hp0mJgzmgc
4.
https://www.youtube.com/watch?v=4hp0mJgzmgc&list=RDC
MUC1S4Jeodbr5EbsCOIgBWJPQ&index=1
5.
https://www.youtube.com/watch?v=_eMA0LWsRQQ&t=131s
6s-20 Linear Programming
