ECS 511
NUMERICAL ANALYSIS & FINITE ELEMENT METHOD
TOPIC 4
LEARNING OUTCOMES
At the end of this topic, students should be able to:
1. Understand how to apply optimization in engineering
problem solving.
2. To outline optimization, linear programming, objective
function, and constraints.
3. To adopt and apply Simplex method to solve linear
programming problems.
(CO1 – PO2)
OPTIMIZATION
Root location involves searching for zeros of a function or functions. In contrast,
optimization involves searching for either the minimum or the maximum.
The optimum is the point where the curve is flat. In Mathematical terms, this corresponds
to the x value where the derivative f’(x) = 0. Additionally, the second derivative, f’’(x),
indicates whether the optimum is a minimum or a maximum: if f’’(x) < 0, the point is a
maximum; if f’’(x) > 0, the point is a minimum.
OPTIMIZATION
An optimization approach that deals with meeting a desired objective such
as maximizing profit or minimizing cost in presence of constraints such as
limited resources.
Some common examples of optimization problems in civil engineering;
1. Design civil engineering structures for minimum weight,
maximum strength and minimum cost.
2. Design water-resource projects like dams to mitigate flood
damage while yielding maximum hydropower.
3. Design waste treatment systems to meet water-quality
standards at least cost.
LINEAR PROGRAMMING
The term linear means that the mathematical functions
representing both the objective and the constraints are linear. The
term programming does not mean “computer programming,” but
rather, means “scheduling” or “setting an agenda”.
Basic linear programming problem consists of two major parts
which represent in mathematical functions:
1. The objective function
2. A set of constraints
LINEAR PROGRAMMING
For a maximization problem, the objective function is
generally expressed as;
Eqn. 1
where
cj= payoff of each unit of the jth activity that is undertaken
xj= magnitude of the jth activity
Z= total payoff due to the total number of activities
LINEAR PROGRAMMING
The constraints can be represented generally as;
Eqn. 2
Where aij=amount of the ith resource that is consumed for each
unit of the jth activity and bi=amount of the ith resource that is
available.
The general second type of constraint specifies that all activities
must have a positive value, xi>0 (negative activity is physically
impossible).
Together, the objective function and the constraints specify the
linear programming problem.
LINEAR PROGRAMMING
LINEAR PROGRAMMING
Possible outcomes that can be generally obtained in a linear
programming problem;
1. Unique solution
- The maximum objective function
intersects a single point.
LINEAR PROGRAMMING
2. Alternate solutions.
- Problem has an infinite number
of optima corresponding to
a line segment.
LINEAR PROGRAMMING
3. No feasible solution
- No solution can satisfy all the
constraints. This can be due to
dealing with an unsolvable
problem or due to errors in
setting up the problem.
LINEAR PROGRAMMING
4. Unbounded problems
- Problem is under constrained
and therefore open-ended.
SIMPLEX METHOD
Assumes that the optimal solution will be an extreme point.
The approach must discern whether during problem solution
an extreme point occurs.
To do this, the constraint equations are reformulated as
equalities by introducing slack variables.
SIMPLEX METHOD
A slack variable measures how much of a constrained resource is available,
e.g.;
7x1+ 11x2 ≤ 77 Eqtn. 3
If we define a slack variable S1 as the amount of resource that is not used
for a particular production level (x1, x2) and add it to the left side of the
constraint, it makes the relationship exact;
7x1+ 11x2 + S1 = 77 Eqtn. 4
If slack variable is positive, it means that we have some slack that is we
have some surplus that is not being used.
If it is negative, it tells us that we have exceeded the constraint.
If it is zero, we have exactly met the constraint. We have used up all the
allowable resource.
SIMPLEX METHOD
– SLACK VARIABLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
Obtain the solution using simplex method
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
Eliminate these
values
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD (MAXIMIZE) - EXAMPLE
SIMPLEX METHOD - MINIMIZE
SIMPLEX METHOD (MINIMIZE) - EXAMPLE
SIMPLEX METHOD (MINIMIZE) - EXAMPLE
SIMPLEX METHOD (MINIMIZE) - EXAMPLE
SIMPLEX METHOD (MINIMIZE) - EXAMPLE
