Linear Programming:
Model Formulation
Management Science
Eunji Kim
eunjikim@cau.ac.kr
College of Business Administration, CAU
Introduction to Optimization 2
Optimization Example 3
▪ Given a collection of numbers, partition them into two groups such
that the difference in the sums is as small as possible
▪ Example: 7, 10, 13, 17, 20, 22
• These numbers sum to 89.
▪ I can split them into … {7, 10, 13, 17} → sum is 47
{20, 22} → sum is 42
▪ Difference = 5
▪ Can we do better?
Optimization 4
▪ Mathematical optimization
• The selection of a best element, with regard to some criterion, from some set
of available alternatives.
• A.k.a. mathematical programming
BEST DECISION
A set of possible decisions
A problem
Optimization is Everywhere 5
▪ Personal choices
• Best career choice
• Best use of our time
• Best strategies
• Best value for the money
▪ Company choices
• Maximize values to shareholders
• Determine optimal mix of products or services
• Minimize production costs
• Minimize cost of getting product to customers
• Maximize value of advertising
• Hire the best workers
What kinds of problems can be solved? 6
▪ Lots of problems can be solved by optimization!
Production quantity
Production Order quantity
Scheduling
Product
Design
Logistics
Component mix ratio
Shipment volume
Transportation
Marketing
Investment
Advertisement Strategy
Portfolio management Channel distribution
Site scoring Human
Resource
Team building
Assignment
The Optimization paradigm 7
▪ Decision variables: the elements that are under the control of the
decision maker
• The work schedules of each employee
• The level of investments in a portfolio
• What subjects a student should take in each semester
▪ A single objective function (of the decision variables)
• Minimize cost or …
• Maximize expected return or …
• Make the last semester as enjoyable as possible or …
The Optimization paradigm 8
▪ Constraints: restrictions on the decision variables
• “Resources”: time, money, material, labor, …
• The labor hours of a worker is limited up to 8 hours per day
• Seed money is $10,000
• “Business rules”
• No worker can work more than 5 consecutive days
• There is at most 2% investment in any stock in the portfolio
• Students must take a prerequisite of a subject before taking the subject
• “Physical laws”
• No worker can work a negative amount of time
• The amount of a goods in inventory at the end of period j is
the amount of goods arriving during period j plus
the amount of goods in inventory in period j-1 minus
the amount of goods that are sold in the period.
Optimization model 9
Typical Maximization (Minimization) Model
Maximize objective function (of decision variables)
(Minimize)
subject to: satisfying constraints
Optimization model 10
Let x1, x2, …, xn be the decision variables.
Typical Optimization Model
Maximize f(x1, x2, …, xn)
(or minimize) Objective function (of decision variables)
subject to: gi(x1, x2, …, xn) ≤ bi (i=1, …, k)
Satisfy the constraints
x1, x2, …, xn ≥ 0
Typically but not always the case
Optimization Example 11
▪ Example (Hamburger eating contest)
• Max is in a hamburger eating contest that lasts 1 hour.
• Each cheese burger that he eats takes 2 minutes.
• Each Bulgogi burger that he eats takes 3 minutes.
• He receives 4 points for each cheese burger and 5 points for each Bulgogi
burger.
• What should Max eat so as to get the most points?
Model Formulation Steps 12
Step 1 : Define the decision variables
Step 2 : Define the objective function
Step 3 : Define the constraints
Optimization Example 13
▪ Step 1 : Define the decision variables
• Let x be the number of cheese burgers eaten by Max.
• Let y be the number of Bulgogi burgers eaten by Max.
In general, these are quantities you can control to improve your objective
which should completely describe the set of decisions to be made.
▪ Step 2 : Define the objective function
Maximize z = 4x + 5y (objective function)
▪ Step 3 : Define the constraints
subject to 2x + 3y ≤ 60 (constraint)
subject to x, y ≥ 0 (non-negativity constraints)
Optimization Example 14
▪ Optimization Model
Maximize z = 4x + 5y (objective function)
subject to 2x + 3y ≤ 60 (constraint)
subject to x, y ≥ 0 (non-negativity constraints)
▪ Terminologies
• A feasible solution satisfies all of the constraints.
x=10, y=10 is feasible; x=10, y=15 is infeasible.
• An optimal solution is the best feasible solution.
The optimal solution is x=30, y=0. Here, the total score is maximized with
z=120.
Model Components 15
▪ Decision variables: e.g., x and y
• Quantities you can control to improve your objective which should completely
describe the set of decisions to be made.
▪ Constraints: e.g., to 2x + 3y ≤ 60, x ≥ 0, y ≥ 0
• Requirements or restrictions placed on the firm by the operating environment,
stated in linear relationships of the decision variables.
▪ Objective Function: e.g., 4x + 5y
• A value measure used to rank alternatives
• Seek to maximize or minimize this objective
• Examples: maximize expected return, minimize cost
▪ Parameters
• Numerical coefficients and constants used in the objective function and
constraints (data).
Linear Programming 16
Linear Function and LP 17
A linear function is a function of the form:
f(x1, x2, …, xn) = c1x1 + c2x2 + … + cnxn
f(x1, x2, …, xn) = ∑k=1 to n ckxk
e.g., 3x1 + 4x2 – 3x4
A mathematical program is a linear program (LP)
if the objective is a linear function and the
constraints are linear equalities or inequalities.
LP Model 18
Let x1, x2, …, xn be the decision variables.
Typical Optimization Model
Maximize f(x1, x2, …, xn)
(or minimize) Objective function (of decision variables)
subject to: gi(x1, x2, …, xn) ≤ bi (i=1, …, k)
Satisfy the constraints
x1, x2, …, xn ≥ 0
Typically but not always the case
This program is a LP model if f and g are linear
functions.
LP vs NLP 19
▪ Optimization models represent a firm’s decisions, given a business
objective, and resource constraints.
▪ Linear Programming (LP)
• The process of solving an optimization problem where all the constraints and
the objective function are linear.
▪ Nonlinear programming (NLP)
• The process of solving an optimization problem where some of the
constraints or the objective function are nonlinear.
Examples: LP and NLP 20
Linear Programming Model Example:
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2 40
4x2 + 3x2 120
x1, x2 0
Nonlinear Programming Model Example:
Maximize Z = $(4 - 0.1x1)x1 + (5 - 0.2x2)x2
subject to: x1 + 2x2 = 40
x1, x2 0
Characteristics of LP Problems 21
• A decision among alternative courses of action is required.
• The decision is represented in the model by decision variables.
• The problem encompasses a goal, expressed as an objective
function, that the decision maker wants to achieve.
• Restrictions (represented by constraints) exist that limit the
extent of achievement of the objective.
• The objective and constraints must be definable by linear
mathematical functional relationships.
Properties of LP Models 22
• Proportionality - The rate of change (slope) of the objective
function and constraint equations is constant.
• Additivity - Terms in the objective function and constraint
equations must be additive.
• Divisibility - Decision variables can take on any fractional value and
are therefore continuous as opposed to integer in nature.
• Certainty - Values of all the model parameters are assumed to be
known with certainty (non-probabilistic).
Optimization Model
Formulation 23
Example: Product mix problem 24
▪ How many bowls and mugs should be produced to maximize profits
given labor and materials constraints?
Beaver Creek Pottery Company
Example: Product mix problem 25
▪ How many bowls and mugs should be produced to maximize profits
given labor and materials constraints?
▪ Product resource requirements and unit profit:
Resource Requirements
Labor Clay Profit
Product
(Hr./Unit) (Lb./Unit) ($/Unit)
Bowl 1 4 40
Mug 2 3 50
▪ Resource Availability:
• 40 hrs of labor per day
• 120 lbs of clay
Model Formulation: A Maximization 26
▪ Step 1 : Define the decision variables
x1 = number of bowls to produce per day
x2 = number of mugs to produce per day
▪ Step 2 : Define the objective function
Maximize Z = profit per day = $40x1 + $50x2
▪ Step 3 : Define the constraints
Resource Constraints:
1x1 + 2x2 40 hours of labor
4x1 + 3x2 120 pounds of clay
Non-Negativity Constraints:
x1 0; x2 0
Model Formulation: A Maximization 27
Complete Model:
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2 40
4x2 + 3x2 120
x1 , x 2 0
Example: Product mix problem 28
▪ How much of each brand to purchase to minimize total cost of
fertilizer given
following data ?
Fertilizing farmer’s field
Example: Product mix problem 29
▪ How much of each brand to purchase to minimize total cost of
fertilizer given
following data ?
◼ Two brands of fertilizer available - Super-gro,
Crop-quick.
◼ Field requires at least 16 pounds of nitrogen
and 24 pounds of phosphate.
◼ Super-gro costs $6 per bag, Crop-quick $3 per
bag.
Chemical Contribution
Nitrogen Phosphate
Brand
(lb/bag) (lb/bag)
Super-gro 2 4
Crop-quick 4 3
Model Formulation: A Minimization 30
Decision Variables:
x1 = bags of Super-gro
x2 = bags of Crop-quick
The Objective Function:
Minimize Z = $6x1 + 3x2
Where: $6x1 = cost of bags of Super-Gro
$3x2 = cost of bags of Crop-Quick
Model Constraints:
2x1 + 4x2 16 lb (nitrogen constraint)
4x1 + 3x2 24 lb (phosphate constraint)
x1, x2 0 (non-negativity constraint)
Model Formulation: A Minimization 31
Complete Model:
Minimize Z = $6x1 + $3x2
subject to: 2x1 + 4x2 16
4x2 + 3x2 24
x1 , x 2 0
QnA
