Lecture
Lecture
Lecture
Systems Analysis in
Construction
CB312
Construction & Building Engineering Department- AASTMT
by
3. Linear Programming
Optimization
Graphical Solution
Simplex Method
Network Models
68
1
2/20/2018
Introduction to LP
• Linear Programming Problem
• Problem Formulation
• A Maximization Problem
• Graphical Solution Procedure
• Extreme Points and the Optimal Solution
• A Minimization Problem
• Special Cases
• Introduction to Sensitivity Analysis
• Graphical Sensitivity Analysis
69
Introduction to LP
• If both the objective function and the constraints are linear,
the problem is referred to as a linear programming
problem.
• Linear functions are functions in which each variable
appears in a separate term raised to the first power and is
multiplied by a constant (which could be 0).
• Linear constraints are linear functions that are restricted to
be "less than or equal to", "equal to", or "greater than or
equal to" a constant.
70
2
2/20/2018
Introduction to LP
• The maximization or minimization of some quantity is the
objective in all linear programming problems.
• All LP problems have constraints that limit the degree to
which the objective can be pursued.
• A feasible solution satisfies all the problem's constraints.
• An optimal solution is a feasible solution that results in
the largest possible objective function value when
maximizing (or smallest when minimizing).
• A graphical solution method can be used to solve a linear
program with two variables.
71
Introduction to LP
72
3
2/20/2018
Introduction to LP
73
Introduction to LP
• Is the most widely used of these mathematical methods (for
optimization).
• All relationships considered in L.P. must be linear functions.
74
4
2/20/2018
Introduction to LP
• In Appling L.P. we should have:
• A set of linear constraints (equations);
• A linear objective function which is to be maximized or minimized; and
• A set of variables that affect both the objective function and the constraints.
Or
Profit Efficiency ROR
Minimized
75
Problem Formulation
Problem formulation or modeling is the process of translating a
verbal statement of a problem into a mathematical statement.
76
5
2/20/2018
77
Max 5 x1 + 7 x2
s.t. 1 x1 + 0 x2 < 6
2 x1 + 3 x2 < 19
1 x1 + 1 x2 < 8
x1 , x2 >0
78
6
2/20/2018
x2 x2
8 8 (0, 6 1/3)
7
7
x1 < 6
6 6
5 5
4 2x1 + 3x2 < 19
4
3 3
2 (6, 0)
2 (9 1/2, 0)
1 1
x1 x1
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
79
x2 x2
(0, 8)
x1 + x2 < 8
8 8
7 x1 + x2 < 8 7
x1 < 6
6 6
5 5
4 4
3 3 2x1 + 3x2 < 19
2 2
1 (8, 0) 1
1 2 3 4 5 6 7 8 9 10
x1 1 2 3 4 5 6 7 8 9 10
x1
80
7
2/20/2018
x2 x2
8 8
7 7 (0, 5)
6 6
5 5
4 4
3 3
Feasible
2 2
Region (7, 0)
1 1
x1 x1
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
81
82
8
2/20/2018
84
9
2/20/2018
Extreme Points
85
86
10
2/20/2018
87
11
2/20/2018
4x1 - x2 > 12
5 5
4 x1 + x2 > 4 4
3 3
2x1 + 5x2 > 10
2 2
1 1
x1 x1
1 2 3 4 5 6 1 2 3 4 5 6
89
90
12
2/20/2018
91
Example 3: Solve
• Solve graphically for the optimal solution:
Max 2 x1 + 6 x2
s.t. 4x1 + 3x2 < 12
2 x1 + x2 > 8
x1 , x2 > 0
92
13
2/20/2018
Example 3: Solve
• There are no points that satisfy both constraints, hence this
problem has no feasible region, and no optimal solution.
Infeasible Problem
93
Example 4: Solve
• Solve graphically for the optimal solution:
94
14
2/20/2018
Example 4: Solve
• The feasible region is unbounded and the objective function
line can be moved parallel to itself without bound so that z
can be increased infinitely.
Unbounded Problem
95
Feasible Region
• The feasible region for a two-variable LP problem can be
nonexistent, a single point, a line, a polygon, or an
unbounded area.
• Any linear program falls in one of three categories:
• is infeasible
• has a unique optimal solution or alternate optimal solutions
• has an objective function that can be increased without bound
• A feasible region may be unbounded and yet there may be
optimal solutions. This is common in minimization
problems and is possible in maximization problems.
96
15
2/20/2018
Special Cases
• Alternative Optimal Solutions
In the graphical method, if the objective function line is parallel to a
boundary constraint in the direction of optimization, there are
alternate optimal solutions, with all points on this line segment being
optimal.
• Infeasibility
A linear program which is over constrained so that no point satisfies
all the constraints is said to be infeasible.
• Unboundedness
97
Extra Examples: E1
98
16
2/20/2018
99
100
17
2/20/2018
If 2X + Y = 10 Y=0
X=0
X=5
Y = 10
If 2X + Y = 20
Y=0 X = 10
X=0 Y = 20
102
18
2/20/2018
Extra Examples: E2
• A builder has a hydraulic press.
• The press produce 125 slabs/day
• Unpressed precast slabs to produce 200 slabs/day
104
19
2/20/2018
S1 ≤ 2
S2 ≤ 1.25
8 S1 + 4 S2 ≤ 18
105
106
20
2/20/2018
107
108
21
2/20/2018
Sensitivity Analysis
• Sensitivity analysis (or post-optimality analysis) is used to
determine how the optimal solution is affected by changes,
within specified ranges, in:
• the objective function coefficients
• the right-hand side (RHS) values
• Sensitivity analysis is important to the manager who must
operate in a dynamic environment with imprecise estimates
of the coefficients.
• Sensitivity analysis allows to ask certain what-if questions
about the problem.
109
Sensitivity Analysis
s.t. x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 , x2 > 0
110
22
2/20/2018
Sensitivity Analysis
Objective Function Coefficients
• Let us consider how changes in the objective function
coefficients might affect the optimal solution.
• The range of optimality for each coefficient provides the
range of values over which the current solution will remain
optimal.
• Managers should focus on those objective coefficients that
have a narrow range of optimality and coefficients near the
endpoints of the range.
111
Sensitivity Analysis
• Changing Slope of Objective Function
Max 5 x1 + 7 x2
Slope -5/7
112
23
2/20/2018
Sensitivity Analysis
• Changing Slope of Objective Function
123
Sensitivity Analysis
Range of Optimality
• Graphically, the limits of a range of optimality are found
by changing the slope of the objective function line
within the limits of the slopes of the binding constraint
lines.
• The slope of an objective function line, Max c1x1 + c2x2,
is -c1/c2, and the slope of a constraint, a1x1 + a2x2 = b, is
-a1/a2.
114
24
2/20/2018
Example 1
s.t. x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 , x2 > 0
115
Example 1 Solution
• Range of Optimality for c1
The slope of the objective function line is -c1/c2. The slope of the
first binding constraint, x1 + x2 = 8, is -1/1 and the slope of the
second binding constraint, 2x1 + 3x2 = 19, is -2/3.
Find the range of values for c1 (with c2 staying 7) such that the
objective function line slope lies between that of the two binding
constraints: -C1/7
-1 < -c1/7 < -2/3
-1/1 -2/3
25
2/20/2018
Example 1 Solution
• Range of Optimality for c2
Find the range of values for c2 ( with c1 staying 5) such that the
objective function line slope lies between that of the two binding
constraints:
-1 < -5/c2 < -2/3
117
Computer Solution
• Computer programs designed to solve LP problems are now
widely available.
• Most large LP problems can be solved with just a few
minutes of computer time.
• Small LP problems usually require only a few seconds.
• Linear programming solvers are now part of many
spreadsheet packages, such as Microsoft Excel.
118
26
2/20/2018
s.t. x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 , x2 > 0
119
27
2/20/2018
28
2/20/2018
x1, x2 > 0
123
124
29
2/20/2018
125
Question
Suppose the profit on deluxe frames is increased to $20. Is
the above solution still optimal? What is the value of the
objective function when this unit profit is increased to
$20?
126
30
2/20/2018
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$B$8 Deluxe 15 0 10 12.5 2.5
$C$8 Profess. 17.500 0.000 15 5 8.33333333
Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$B$13 Aluminum 100 3.125 100 60 46.66666667
$B$14 Steel 80 1.25 80 70 30
127
• Range of Optimality
Answer
The output states that the solution remains optimal as
long as the objective function coefficient of x1 is between
7.5 and 22.5. Since 20 is within this range, the optimal
solution will not change. The optimal profit will change:
20x1 + 15x2 = 20(15) + 15(17.5) = $562.50.
128
31
2/20/2018
• Range of Optimality
Question
If the unit profit on deluxe frames were $6 instead of $10,
would the optimal solution change?
129
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$B$8 Deluxe 15 0 10 12.5 2.5
$C$8 Profess. 17.500 0.000 15 5 8.33333333
Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$B$13 Aluminum 100 3.125 100 60 46.66666667
$B$14 Steel 80 1.25 80 70 30
130
32
2/20/2018
• Range of Optimality
Answer
The output states that the solution remains optimal as
long as the objective function coefficient of x1 is between
7.5 and 22.5. Since 6 is outside this range, the optimal
solution would change.
131
132
33
2/20/2018
Question
If simultaneously the profit on Deluxe frames was raised to
$16 and the profit on Professional frames was raised to $17,
would the current solution be optimal?
133
134
34
2/20/2018
?
3. Linear Programming
Optimization
Simplex Method
135
35