Classical Optimization: Unconstrained Optimization
In this article, we will review and explain three motivating problems. as we have explained in Optimization introduction article, there are two main types of optimization based on its conditions as constrained and unconstrained. Unconstrained optimization considers the problem of minimizing or maximizing an objective function that depends on real variables with no restrictions on their values.
Three Motivating Problems
- Profit Maximization – iWidget
- Given cost and demand functions, find the price for the iWidget that produces maximum
- Inventory Replenishment Policy- Gears Unlimited
- Given annual demand and costs for ordering and holding, calculate the re-order quantity that minimizes total
- Package Optimization – boxy.com
- Calculate the package dimensions that maximize total usable volume given a specific cardboard
- Each of these problems …
- Requires the use of a Prescriptive Model,
- Utilizes a math function to make the decision,
- Looks for an “extreme point” solution, and
- Are unconstrained in that there is not a resource
- What is an extreme point of a function?
- The point, or points, where the function takes on an extreme value, typically either a minimum or a maximum.
- The point(s) where the slope or “rate of change” of the function is equal to zero.
- Types of Extreme points
- Minimum, Maximum, or Inflection Points
- The minimum and maximum points are either global or local.
- Use differential calculus to find extreme solutions
- Look for where the rate of change, the slope, goes to zero.
- Check for sufficiency conditions.
- Continuity and convexity come into play.
- We are manufacturing a product where we know:
- The cost function = f(# made) = 500,000 + 75x
- The demand function = f(price) = 20,000 – 80p
- And therefore the profit function = -80p2 + 26,000p – 2,000,000
- We want to find the price, p, that maximizes profits.
Finding the Instantaneous Slope: The First Derivative
Find the price, p, that maximizes the profit function:
- Take the first derivative:
- Set the first derivative equal to zero:
- Solve for p*:
This means: Set price at 162.5$ then your profits will be maximized. Expected profit will be 112,500$
- How do I know this is a maximum and not a minimum?
- How do I know whether this is global or local?
Necessary and Sufficient Conditions
In order to determine x* at the max/min of an unconstrained function:
- Necessary Condition – the slope has to be zero, that is, f'(x*)=0
- Sufficient Conditions – determines whether extreme point is min or max by taking the Second Derivative, f”(x).
- If f”(x) > 0 then the extreme point is a local minimum
- If f”(x) < 0 then the extreme point is a local maximum
- If f”(x) = 0 then it is inconclusive
- Special Cases:
- If f(x) is convex then f(x*) is a global minimum
- If f(x) is concave then f(x*) is global maximum
By observation, we know that p*=162.50 is a global optimal, but lets do it formally.
- Checking Second Order Conditions:
As the slope is Negative, Then this is Local Maximum. And since f(p) is a concave function, so it is become Global Maximum as well.
Inventory Replenishment Policy
Gears Unlimited distributes specialty gears, derailleurs, and brakes for high-end mountain and BMX bikes. One of their most steady selling items is the PK35 derailleur. They sell about 1500 of the PK35’s a year. They cost $75 each to procure from a supplier and Gears Unlimited assumes that the cost of capital is 20% a year. It costs about $350 to place and receive an order of the PK35s, regardless of the quantity of the order.
How many PK35s should Gears Unlimited order at a time to minimize the average annual cost in terms of purchase cost, ordering costs, and holding costs?
What do we know?
- D = Demand = 1500 items/year
- c = Unit Cost = 75 $/item
- A = Ordering Cost = 350 $/order
- r = Cost of Capital = 0.2 $/$/year
What do we want to find?
- Q = Order Quantity (item/order). Find Q* that minimizes Total Cost.
What is my Objective Function?
Total Cost = Purchase Cost + Order Cost + Holding Cost
- Purchasing Cost = cD = (75)(1500) = 112,500 [$/year]
- Order Cost = A(D/Q) = (350)(1500/Q) = 525,000/ Q [$/year]
- Holding Cost = rc(Q/2) = (0.2)(75)(Q/2) = 7.5Q [$/year]
Gears Unlimited Solution steps:
1- Determine the Objective Function:
2- Take first derivative:
3- Set first derivative equal to zero and solve for Q:
4- Check second order conditions:
Because Q* will always be greater than zero, then this Q* is a Local Minimum.
You are consulting with boxy.com, the premier online corrugated packaging company. They just received a large quantity of heavy duty cardboard from a third party at an extremely low cost. All of the sheets are 1 meter by 1.5 meters in dimension. You have been asked to come up with the design that maximizes the total volume of a box made from this sheet. The only cutting that can be made, however, are equal-sized squares from each of the four corners. The edges then fold up to form the box.
How big should the square cut-outs be to maximize the box’s volume?
What do we know?
- W= Width= 1 m
- L =Length= 1.5 m
- x = Height of box (also the amount cut)
What do we want to find?
Find x* that maximizes Volume V =Volume= (Width)(Length)(Height) = (W-2x)(L-2x)(x)
What is my objective function?
max V = (W-2x)(L-2x)(x) = (WL-2xL -2Wx+4x2)x = 4x3-2Wx2-2Lx2+WLx = 4x3 – 2x2 – 3x2+1.5x =-4-x3-5x2+1.5-x
- Determine the Objective Function
- Take first derivative
- Set 1st derivative equal to zero and solve for x*
- Check 2nd order conditions