Optimization is anything!
Introduction To Optimization
As per Dictionary.com, Optimization [op-tuh-muh-zey-shuh n] refers to:
- The fact of optimizing; making the best of anything.
- The condition of being optimized.
- Mathematics. a mathematical technique for finding a maximum or minimum value of a function of several variables subject to a set of constraints, as linear programming or systems analysis.
Here, I can add a meaning in business that it is the best solving way or result of any problem you face by using professional mathematical methods. Any running business doesn’t use optimization in his process intend to be like a workshop, not a professional business!
In this series of articles, I will try to explain more about this concept using My study knowledge in MIT. actual the main source of all examples and case studies will be MIT materials. I am just trying to write and explain about this subject to understand it easily in our market.
Any running business doesn’t use optimization in his process intend to be like a workshop, not a professional business!
I will start with an overview of unconstrained optimization and how to find extreme point solutions, keeping in mind first order and second order conditions. It also reviews rules in functions such as the power rule.
Then I will review constrained optimization that shares similar objectives of unconstrained optimization but adds additional decision variables and constraints on resources. To solve constrained optimization problems, we will use mathematical programs that are widely used in supply chain for many practices such as designing networks, planning production, selecting transportation providers, allocating inventory, scheduling port and terminal operations, fulfilling orders, etc. The overview of linear programming includes how to formulate the problem, how to graphically represent them, and how to analyze the solution and conduct a sensitivity analysis.
In real supply chains, you cannot use 0.5 bananas in an order or shipment. This means that we must add additional constraints for integer programming where either all of the decision variables must be integers, or in a mixed integer programming where some, but not all, variables are restricted to be an integer.
Unconstrained optimization considers the problem of minimizing or maximizing an objective function that depends on real variables with no restrictions on their values.
- Extreme points are when a function takes on an extreme value – a value that is much smaller or larger in comparison to nearby values of the function.
- They are typically a min or a max (either global or local), or inflection points.
- Extreme point occur where slope (or rate of change) of function = 0.
- Test for Global vs. Local
o Global min/max – for whole range
o Local min/max – only in certain area
Finding Extreme Point Solutions:
Use differential calculus to find extreme point solutions, look for where slope is equal to zero. To find the extreme point, there is a three-step process:
- Take the first derivative of your function
- Set it equal to zero, and
- Solve for X*, the value of x at extreme point.
This is called the First Order Condition.
Instantaneous slope (or first derivative) occurs when:
- dy/dx is the common form, where d means the rate of
- δ (delta) = rate of change.
The Product Rule: If function is constant, it doesn’t have any effect.
Power Rule is commonly used for finding derivatives of complex functions.
First and Second Order Conditions:
In order to determine x* at the max/min of an unconstrained function
- First Order (necessary) condition – the slope must be 0 :
- Second order (sufficiency) condition – determines where extreme point is min or max by taking the second derivative, .
- If > 0 extreme point is a local min
- If < 0 extreme point is a local max
- If = 0 it is inconclusive
- If is convex –> global min
- If is concave –> global max
|In next articles, I will review and explain three examples to understand unconstrained optimization:|
– Example 1: Profit Maximization
– Example 2: Inventory Replenishment Policy
– Example 3: Package Optimization
Similarities with unconstrained optimization:
• Requires a prescriptive model.
• Uses an objective function.
• Solution is an extreme value.
• Multiple decision variables.
• Constraints on resources.
Math programming is a powerful family of optimization methods that is widely used in supply chain analytics. It is readily available in software tools, but is only as good as the data input. It is the best way to identify the “best” solution under limited resources.
Some types of math programming in SCM:
• Linear Programming (LPs)
• Integer Programming
• Mixed Integer and Linear Programming (MILPs)
• Non‐linear Programming (NLPs)
Formulating Linear Programs
1. Decision Variables
• What are you trying to decide?
• What are their upper or lower bounds?
2. Formulate objective function
• What are we trying to minimize or maximize?
• Must include the decision variables and the form of the function determines the approach (linear for LP)
3. Formulate each constraint
• What is my feasible region? What are my limits?
• Must include the decision variable and will almost always be linear functions
See below Figure for an example of problem formulation of a linear program.
The solution of a linear program will always be in a “corner” of the Feasible Region:
• Linear constraints form a convex feasible region.
• The objective function determines in which corner is the solution.
The Feasible Region is defined by the constraints and the bounds on the decision variables (See below Figure ).
Analysis of the Results
Sometimes the original question is the least interesting one, it is often more interesting to dive a little deeper into the structure of the problem.
- Am I using all of my resources?
- Where do I have slack?
- Where I am constrained?
- How robust is my solution?
Sensitivity Analysis: what happens when data values are changed.
- Shadow Price or Dual Value of Constraint: What is the marginal gain in the profitability for an increase of one on the right hand side of the constraint?
- Slack Constraint – For a given solution, a constraint is not binding if total value of the left hand side is not equal to the right hand side value. Otherwise it is a binding constraint
- Binding Constraint – A constraint is binding if changing it also changes the optimal solution
It is important to note that the compact notation is more common than what has been presented thus far in the lesson. This is because mathematical programs tend to get so lengthy that long hand would be too long.
Examples of (compact) notation forms shown in below Figure.
There can be further compaction of the notation just to capture the essence of the model for discussion (See below Figure).
Anomalies in Linear Programming
- Alternative or Multiple Optimal Solutions
- Redundant Constraints -‐ Does not effect the Feasible Region; it is redundant.
- Infeasibility -‐ There are no points in the Feasible Region; constraints make the problem infeasible.
|In next articles, I will review and explain master example to understand constrained optimization:|
– Motivating Problem – Banner Chemicals
- Hillier and Lieberman (2012) Introduction to Operations Research, McGraw
- Taha, H.A. (2010). Operations Research. An introduction. 9th Pearson Prentice Hall.
- Winston (2003) Operations Research: Applications and Algorithms, Cengage Learning. There are many different books by Wayne Winston -‐ they are all pretty good.