This document introduces a course on foundations of optimization that will cover topics such as linear programming, mathematical modeling, and algorithms for solving complex decision problems, providing an example of using linear programming to determine the optimal production levels that maximize profit given supply and demand constraints.
This document introduces a course on foundations of optimization that will cover topics such as linear programming, mathematical modeling, and algorithms for solving complex decision problems, providing an example of using linear programming to determine the optimal production levels that maximize profit given supply and demand constraints.
This document introduces a course on foundations of optimization that will cover topics such as linear programming, mathematical modeling, and algorithms for solving complex decision problems, providing an example of using linear programming to determine the optimal production levels that maximize profit given supply and demand constraints.
This document introduces a course on foundations of optimization that will cover topics such as linear programming, mathematical modeling, and algorithms for solving complex decision problems, providing an example of using linear programming to determine the optimal production levels that maximize profit given supply and demand constraints.
Napat Rujeerapaiboon Semester I, AY2019/2020 Course Information
• Lecturer: Napat Rujeerapaiboon
(napat.rujeerapaiboon@nus.edu.sg) • Teaching assistant: Najakorn Khajonchotpanya (najakorn.k@u.nus.edu) • Lecture slides are available on LumiNUS. • In addition to mid-term (25%) and final (50%) exams, there will be five assessed courseworks (5% each). • Active participation is strongly encouraged! What is Optimization?
Optimization is a multidisciplinary branch
of mathematics involving • mathematical modelling, • statistics and • algorithms in order to find “good” solutions for com- plex decision problems.
Typical objectives in OR are:
• maximize profit, minimize cost, maximize bandwidth, minimize risk, maximize efficiency, minimize completion time etc. Mathematical Programming
OR solves mathematical programming models:
minimize f (x) subject to x ∈ X ,
where • x ∈ Rn are the decision variables • f : Rn → R is the objective function (e.g., cost) • X ⊆ Rn is the feasible set (set of admissible decisions) Linear Programming (LP)
Optimal Decision Tool
• Linear objective function • Linear constraints (equalities and inequalities)
Amongst the most popular mathematical models:
85% of Fortune 500 firms said they use LP Example 1
Manufacturer produces: A (acid) and C (caustic).
Ingredients used for producing A and C are: X and Y.
• Each ton of A requires: 2lb of X; 1lb of Y
• Each ton of C requires: 1lb of X ; 3lb of Y • Supply of X limited to: 11lb/week • Supply of Y limited to: 18lb/week • A sells for: $1000/ton • C sells for: $1000/ton
Market research: max 4 tons of A/week can be sold.
Maximize weekly value of sales of A and C. Example 1 (MP Model)
How much A and C to produce?
⇒ Formulate a mathematical programming model!
• Decision variables • x1 = weekly production of A (in tons) • x2 = weekly production of C (in tons) • Objective function • f (x1 , x2 ) = weekly profit (in 1000 $) • Feasible set • X = set of all implementable/admissible production plans x = (x1 , x2 ) • e.g., x = (27, 2) is not possible (not enough supply!) Example 1 (Decision Variables)
A production plan is representable as x = (x1 , x2 )
Example 1 (Objective Function)
Profit: f (x1 , x2 ) = x1 + x2 (in 1000 $)
Example 1 (Feasible Set)
Amount of A produced is non-negative: x1 ≥ 0
Example 1 (Feasible Set)
Amount of C produced is non-negative: x2 ≥ 0
Example 1 (Feasible Set)
x1 tons of A & x2 tons of C require 2x1 + x2 lb of X
X is limited to 11lb/week: 2x1 + x2 ≤ 11 Example 1 (Feasible Set)
x1 tons of A & x2 tons of C require x1 + 3x2 lb of Y
Y is limited to 18lb/week: x1 + 3x2 ≤ 18 Example 1 (Feasible Set)
Cannot sell more than 4 tons of A/week: x1 ≤ 4
Example 1 (Feasible Set)
To obtain the overall feasible set,
intersect the feasible sets of all individual constraints Example 1 (Feasible Set)
• The feasible set is a convex polygon
• The corners O,P,Q,R,S of the feasible set are termed
extreme points or vertices • Each vertex is given by the intersection of two blue lines; its coordinates can be computed by jointly solving the two linear equations defining the blue lines • We obtain O=(0,0), P=(0,6), Q=(3,5), R=(4,3), S=(4,0) Example 1 (Summary)
The best production plan is obtained by solving the following
linear program:
maximize x1 + x2 : objective function
subject to 2x1 + x2 ≤ 11 : constraint on availability of X x1 + 3x2 ≤ 18 : constraint on availability of Y x1 ≤ 4 : constraint on demand of A x1 , x2 ≥ 0 : non-negativity constraints Example 1 (Graphical Solution) Example 1 (Graphical Solution)
All feasible points satisfy f (x1 , x2 ) ≤ 8
Q is the only feasible point (x1 , x2 ) with f (x1 , x2 ) = 8 Linear Programming
• A Linear program (LP) is a mathematical program that
• optimizes (maximizes or minimizes) a linear objective function • over a polyhedral feasible set described by linear equality/inequality constraints. • The feasible set has finitely many vertices. • One can prove that every LP (with a bounded nonempty feasible set) has a vertex solution.
⇒ To solve the LP it is sufficient to examine only the vertices of
its feasible set! Variants of Example 1
• minimize 3x1 − x2 over feasible set of Example 1
O=(0,0) P=(0,6) Q=(3,5) R=(4,3) S=(4,0)
0 -6 4 9 12
⇒ P: x1 = 0, x2 = 6 is optimal.
• maximize 2x1 + x2 over feasible set of Example 1:
Any point on the line segment QR is optimal.
⇒ points other than vertices can be optimal, but there is always
an optimal vertex Simplex Algorithm
• The number of vertices of the feasible set is always finite,
but it is typically exponential in the problem dimensions. • The Simplex Algorithm is an efficient method for finding an optimal vertex without necessarily examining all vertices.
