Optimization Methods for
System 2 Decision-Making
Suri Gurumurthi, Ph.D.
Optimization Steps
• Identify critical decisions for a system (could be more than one)
– Also called DECISION VARIABLES
• Specify the relationship between outcomes and decisions
– ALSO CALLED OBJECTIVE FUNCTION
• Specify constraints on the decision-making
– ALSO CALLED CONSTRAINT FUNCTION
• Identify “best” or “optimal” combination of decisions
– Guide decision-makers by providing better insights
2
Linear Optimization: Different
Example
Maximize
Objective Function: 2x1 + 3x2
Subject to
Constraint: x1 + x2 ≤ 5
Constraint: x2 ≤ 3
Constraint: x1 , x2 ≥ 0
x2
2x1 + 3x2
x2 ≤ 3
x1 + x2 ≤ 5
x1
5A–9
Linear Optimization: Different
Example
Maximize
Objective Function: 2x1 + 3x2
Subject to
Constraint: x1 + x2 ≤ 5
Constraint: x2 ≤ 3
Constraint: x1 , x2 ≥ 0
x2
2x1 + 3x2 = 13
x1 = 2, x2 = 3
x2 ≤ 3
x1 + x2 ≤ 5
x1
5A–10
Fundamental Property of Linear
Optimization
• If an optimal solution exists, it always is at a corner point of
the feasible set
• One can then search through the corner points to find optimal
solution…
x2
x2 ≤ 3
x1 + x2 ≤ 5
x1
5A–11
Non-Linear Optimization
Non-Linear Optimization: Either objective function f , or
constraints g1, g2,…, or gm are not linear in x1 ,x2 …, xn
Maximize
Objective Function: Maximize x12 + x22
Subject to
Constraint: x1 + x2 -5 ≤ 0
Constraint: x2 - 3 ≤ 0
Constraint: -x1 , -x2 ≤ 0
5A–12
Non-Linear Optimization
• Optimal Solution, if it exists, can be either in the interior or on
the boundary of the feasible set
• Many algorithms to find optimal solution; don’t always work!
x2
x2 ≤ 3
x1 + x2 ≤ 5
x1 x1 = 5, x2 = 0
5A–13
Non-Linear Optimization
Iso-profit circles on the 3rd dimension
x2 Centered at the origin (0,0)
As we move away from the origin, z-value increases
x2 ≤ 3
x1 + x2 ≤ 5
x1
5A–14
Types of Optimization Models
Integer Based Optimization: At least one of the decision
variables x1 ,x2 …, xn can only take integer values
Maximize
Objective Function: z= x12 + x22
Subject to
Constraint: x1 + x2 -5 ≤ 0
Constraint: x2 - 3 ≤ 0
Constraint: -x1 , -x2 ≤ 0
Constraint: x1 , x2 Integer 5A–15
Optimization with Integer Decision
Variables
• Optimal Solution, if it exists, can be either in the interior or in
the boundary of the feasible set
• Hardest Problems to Solve in General!
x1
x2 x1 = 5, x2 = 0
5A–16
Non-linear Optimization Problem:
Optimal Replenishment Quantity
𝑇𝑜𝑡𝑎𝑙 𝐶𝑜𝑠𝑡(𝑟𝑎𝑡𝑒) = 𝐹𝑖𝑥𝑒𝑑 𝐶𝑜𝑠𝑡(𝑟𝑎𝑡𝑒) + 𝐼𝑛𝑣𝑒𝑛𝑡𝑜𝑟𝑦 𝐻𝑜𝑙𝑑𝑖𝑛𝑔 𝐶𝑜𝑠𝑡(𝑟𝑎𝑡𝑒) D: Demand rate for product
𝐷 𝑄 K: Fixed Cost of Replenishment
𝐶 =𝐾× +ℎ×
𝑄 2 h: variable cost of holding inventory
𝑑𝐶 −𝐾𝐷 ℎ Q: Replenishment decision
= + =0
𝑑𝑄 𝑄? 2
2×𝐾×𝐷
𝐻𝑒𝑛𝑐𝑒 𝑄∗ =
ℎ
Q/2
Q/D 2Q/D 3Q/D 4Q/D
17
Replenishment Quantity Decision
Costs
Total Costs
Total Inventory Holding Costs
Total Fixed Replenishment Costs
Q* Q
18
How Many Cakes to Bake?
$32 Profit Margin;
Demand =50 /day;
Produce Min 20/day $16 Profit Margin;
Demand=100/day
Produce Min 55/day
$11 Profit Margin;
Demand=150/day
Produce Min 50/day
19
Time of Resources (Available Vs. Consumed)
Mango Chocolate Strawberry
Preparing (mins)
Avail 1150 mins /day 8 4 3.5
Mixing (mins)
Avail 2150 mins /day 14 7.5 6.5
Baking (mins)
Avail 6000 mins /day 40 26.5 22
Decorating (mins)
Avail 550 mins /day 4.5 2.2 1.5
20
Solving the Allocation Problem-
Feasible Solution
21
Solving the Allocation Problem-
Improving the Feasible Solution
22
Assignment Decision Problems
• A company has to decide which truck to assign to different regional
distribution activities.
• Daily cost of allocating a trucking company to a region in HKD:
NT HK KLN Lantau
T1 800 560 430 620
T2 940 500 880 640
T3 940 460 500 400
T4 980 790 710 650
Each truck can serve only one region
• Each region can receive only one truck
• Objective: Minimize Assignment Costs!
23
Assignment Decision Problems
• A company has to decide which truck to assign to different regional
distribution activities.
• Daily cost of allocating a trucking company to a region in HKD:
NT HK KLN Lantau Shenzhen
T1 800 560 430 620 460
T2 940 500 880 640 630
T3 940 460 500 400 550
T4 980 790 710 650 910
T5 610 590 890 980 450
Each truck can serve only one region
• Each region can receive only one truck
• Objective: Minimize Assignment Costs!
24
