Applied Mathematical
Programming
ENCE 677
OR Models in Transportation Systems Analysis
Mathematical Programming
• Mathematical programming, and especially linear programing is one of the
best developed and most used techniques in Management Science
(Operations Research).
• Management science is characterized by the use of mathematical models
in providing guidelines to managers for making effective decisions within
the state of current information, or in seeking further information if
current knowledge is insufficient to reach a proper decision.
• Models are simplified representations of real world.
• Mathematical models attempt to capture the most significant features of
the decision under consideration by the means of mathematical
abstraction.
ENCE 677
OR Models in Transportation Systems Analysis
Classification of Analytical and Simulation
Models
Strategy Evaluation Strategy Generation
• Deterministic simulation • Linear programming
• Econometric models • Network models
• •
Certainty
Systems of simultaneous equations Integer and mixed-integer programming
• Input-output models • Nonlinear programming
• Control theory
• Monte Carlo simulation • Decision theory
Uncertainty
• Econometric models • Dynamic programming
• Stochastic processes • Inventory theory
• Queueing theory • Stochastic programming
• Reliability theory • Stochastic programming
• Stochastic control theory
ENCE 677
OR Models in Transportation Systems Analysis
Linear Programming
Linear Programming is a technique used in decision making to allocate limited resources
among competing objectives in an optimal manner. It is a planning of activities to obtain
the best possible results among the feasible alternatives
Definitions:
A function f(X1, X2, …, Xn) of X1, X2, …, Xn is a linear function if and only if for some set of
constants C1, C2, …, Cn
f(X1, X2, …, Xn) = C1 X1 + C2 X2 + … + Cn Xn
Example: f(X1, X2) = X1 + 3 X2 is a linear function, f(X1, X2, X3) = X1 X2 /X3 is not a linear
function
For any linear function f(X1, X2, …, Xn) and any number b, the inequalities < b or > b are
linear inequalities.
Example: X1 + 3 X2 > 2 is a linear inequality, X1 X2 < 3 is not a linear inequality
ENCE 677
OR Models in Transportation Systems Analysis
Linear Programming
• A Linear Programming Problem (LP) is an optimization problem for which we do
the following:
• Attempt to minimize or maximize a linear function of decision variables, this
function is the Objective Function
• The values of decision variables must satisfy a set of constraints. Each constraint
must be a linear equation or linear inequality
• A sign restriction is associated with each variable. That means for every variable
Xi we either have Xi > 0, Xi < 0, or Xi is unrestricted.
ENCE 677
OR Models in Transportation Systems Analysis
An LP Prototype Example
• A company has 3 plants and sells 2 products. Each product is produced in two
plants and uses some of the available capacity of the plants which in turn will not
be available to the other product.
• The percent capacity of each plant used per unit production of products and the
percent available capacity of the plants as well that profit from sale of each unit
of products is given in the table below.
Plant % capacity used for unit % capacity used for unit % available capacity
production of product 1 production of product 2
1 1 0 4
2 0 2 12
3 3 2 18
Unit profit ($) 3 5
ENCE 677
OR Models in Transportation Systems Analysis
An LP Prototype Example
• Problem: How many units of each product should be produced in order to
maximize profit?
• Note: The above table is sometimes referred to as the cost and requirement
table.
Linear Programming formulation
• Decision variables:
X1 = No. of units of product 1 produced
X2 = No. of units of product 2 produced
ENCE 677
OR Models in Transportation Systems Analysis
An LP Prototype Example
• Objective function:
We must choose the values of X1 and X2 so as to maximize profit therefore the
objective function is:
Maximize Z = 3 X 1 + 5 X2
• Constraints:
Plant 1 capacity X1 < 4
Plant 2 capacity 2X2 < 12
Plant 3 capacity 3X1 + 2X2 < 18
Non-negativity X1 > 0
X2 > 0
ENCE 677
OR Models in Transportation Systems Analysis
Prototype Formulation Summary
Objective function
Maximize Z = 3 X1 + 5 X2
Right-hand Side (RHS) of constraint
Subject to: X1 < 4 Capacity
constraints
2X2 < 12
3X1 + 2X2 < 18
X1 > 0
Variable domain
X2 > 0 constraints
ENCE 677
OR Models in Transportation Systems Analysis
Steps of Formulating LPs
• Defining decision variables
• Decision variables: elements under control of the decision-maker, that their values
1 determine the solution to the model.
• Determining the objective function
• Objective function: the criterion the decision-maker will use to evaluate solutions of
2 the problem.
• Determining the constraints
• Constraints: restrictions imposed upon the values of the decision variables by the
3 characteristics of the problem under study.
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Steel Production
A steel fabrication plant produces 4 different types of specialized steel assemblies. Each require a
certain amount of Angle Iron, Steel Plate, and Fastening Brackets. Any number of assemblies that
is produced can be sold. The pertinent problem information are shown in the table below.
Specialized Angle Iron Steel Plate Fastening Profit
Assembly (lbs/unit) (lbs/unit) Bracket (lbs/unit) ($/unit)
_______________________________________________________________________
A 150 200 75 10
B 200 250 60 12
C 100 125 80 8
D 250 175 65 6
_______________________________________________________________________
The total available amounts of Angle Iron, Steel Plate , and Fastening Bracket are 100,000 lbs,
200,000 lbs, and 50,000 lbs respectively.
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Steel Production (Cont’d)
Formulate a model to determine how much of each product should be produced given that:
• Due to inventory problems, at least 100,000 lbs of steel plate must be used
• Usage of assemblies requires that 2 units of assembly A must be produced for each unit of
assembly B.
Solution:
Decision Variables:
X1 = No. of units of assembly A produced
X2 = No. of units of assembly B produced
X3 = No. of units of assembly C produced
X4 = No. of units of assembly D produced
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Steel Production (Cont’d)
The objective is to maximize profit so the objective function can be written as:
Maximize Z = 10 X1 + 12 X2 + 8 X3 + 6 X4
Constraints:
Amount of Angle Iron Available: 150 X1 + 200 X2 + 100 X3 + 250 X4 < 100,000
Amount of Steel Plate available: 200 X1 + 250 X2 + 125 X3 + 175 X4 < 200,000
Amount of Fastening Bracket available: 75 X1 + 60 X2 + 80 X3 + 65 X4 < 50,000
Minimum use of Steel Plate: 200 X1 + 250 X2 + 125 X3 + 175 X4 > 100,000
Assembly usage limitation: X1 = 2 X2 or 0.5 X1 - X2 = 0
Non-negativity: Xi > 0 for i = 1, 2, 3, 4
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production
A concrete production plant must schedule the production of a certain size concrete sewer pipe
over the next 5 months.
• Pipes can be produced in any month to meet the demand for later months. Any pipe on hand at
the beginning of the first month has been subtracted from the first month’s requirement.
• The goal is to meet the projected demand over the five months at minimum cost so that no
pipes will remain after the fifth month.
• Pipes can be produced in regular or over time. There are limits on material availability for each
month and the amount of regular time for processing pipes.
• Producing each pipe requires 75 hours of processing time.
• It costs $20 to store one unit of pipe for one month. No pipes will be stored after the 5th month.
• Determine how many pipes need to be produced in regular time and over time in each month
and how many pipes have to be stored from month i to month i +1
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production (Cont’d)
The other pertinent information of the problem are in the following table.
Months
1 2 3 4 5
_______________________________________________________________________________
Pipes required (units) 20 30 40 20 40
Cost of regular time processing ($/unit) 150 150 150 160 160
Cost of overtime processing ($/unit) 170 170 170 185 185
Regular time available for processing (hr) 2000 2000 2000 2000 2000
Material availability (possible units) 40 50 50 10 30
_______________________________________________________________________________
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production (Cont’d)
Decision variables:
XRj = No. of units of pipe produced in regular time in month j
XOj = No. of units of pipe produced in overtime in month j
XSi = No. of units of pipe stored from month i to month i +1
Objective function:
The objective function, which is to be minimized, reflects the total cost of regular and overtime
processing and the storage cost.
Minimize Z = 150 XR1 + 150 XR2 + 150 XR3 + 160 XR4 +160 XR5
+ 170 XO1 + 170 XO2 + 170 XO3 + 185 XO4 +185 XO5
+ 20 XS1 + 20 XS2 + 20 XS3 + 20 XS4
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production (Cont’d)
Constraints:
Resource availability Time availability Non-negativity
XR1 + XO1 < 40 75 XR1 < 2000 XRj > 0 for all j
XR2 + XO2 < 50 75 XR2 < 2000 XOj > 0 for all j
XR3 + XO3 < 50 75 XR3 < 2000 XSi > 0 for all i
XR4 + XO4 < 10 75 XR4 < 2000
XR5 + XO5 < 30 75 XR5 < 2000
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production (Cont’d)
Constraints:
Demand requirements
During any particular month in the first 4 months, the No. of units of pipe available at the beginning
of the month plus the No. of units of pipe produced during the month must be equal to the No. of
units of pipe demanded during the month plus the No. of units of pipe stored for carryover to next
month. The number of units of pipe available at the beginning of first month is zero and the No. of
units of pipe stored for carryover to next month at the end of month 5 is zero as well. The demand
constraints are as follows:
ENCE 677
OR Models in Transportation Systems Analysis
LP Formulation Example
Example: Concrete Pipe Production (Cont’d)
Demand requirements
XR1 + XO1 = 20 + XS1
XR2 + XO2 + XS1 = 30 + XS2
XR3 + XO3 + XS2 = 40 + XS3
XR4 + XO4 + XS3 = 20 + XS4
XR5 + XO5 + XS4 = 40
ENCE 677
OR Models in Transportation Systems Analysis
