291. Non-Linear Programming
291.0.0.1. EOQ
Parameters
- : annual demand (units)
- : unit ordering cost ($)
- : unit holding cost per year ($)
- : unit purchasing cost ($)
Decision Variable
- : order quantity per order (units)
Objective
Minimize annual total cost
-
: average inventory level
-
: annual holding cost
-
: annual purchasing cost
-
: number of orders in a year
-
: annual ordering cost
Objective Function
is just a constant, so:
-
As increases:
- Inventory costs increase
- Ordering cost decease
-
As decreases:
- Inventory costs decrease
- Ordering cost increase
291.0.0.2. Portfolio Optimization
Objective
Invest dollars in stocks while managing risk and meeting required return
Notation
- : budget ($)
- : required minimum expected return
-
For each stock
- : current price
- : expected future price
- : variance of ruturn per share
- : Covariance between assets and
- : number of shares to buy (decision variable)
Model
291.0.1. Linearizing Maximum/Minimum Functions
- When the maximum function is on the smaller side of inequality
General Form
- This rule holds regardless of whether , , are variables, constants, or expressions
- You’re ensuring that is greater than or equal to all values in the maximum function, so it must be greater than or equal to each term individually
Generalized form with more than two elements
Example
- When the minimum function is on the larger side of inequality
General Form
- This rule holds regardless of whether , , are variables, constants, or expressions
- You’re ensuring that is smaller than or equal to all values in the minimum function, so it must be smaller than or equal to each term individually
Generalized form with more than two elements
Example
Cases Where Linearization Does Not Apply
- Maximum or minimum function in an equality
291.0.2. Linearize Objective Function
- Minimize a Maximum Function
|
|
|
|
- Maximize a Minimum Function
|
|
|
|
Cases Where Linearization Does Not Apply
Absolute Function
The absolute value is equivalent to a maximum function:
Thus, it can be linearized when it appears on the smaller side of an inequality:
Example
We want to allocate $1000 to 2 people in a fair way
-
Fairness criterion: Minimize the difference between the amounts each person receives.
-
Let be amount to allocate to person for
We write the problem as:
- The absolute value makes the objective nonlinear
Linearizing the Problem
We now reformulate the problem to make it linear
Step 1.: Introduce a new variable
Let be the absolute difference:
Step 2. Relax the equality
We replace the equality with an inequality:
Step 3. Replace absolute value with maximum
Recall:
Therefore:
Now the problem is fully linear:
Reformulating in One Variable
using , we can express everything in terms of :
We are minimizing , which represents the difference between the two allocations. The solution occurs when the two inequalities intersect — that is, when both are equal:
So:
This is the fair allocation: each person receives $500, and the difference between the two amounts is 0.
291.0.3. Linearizing Products of Decision Variables
Products of decision variables can be linearized if:
- A binary and a continuous variable
- Two binary variables
Cannot be linearized if:
- Two continuous variables