Lecture Linear Programming
Operational Research 2 • What is LP?
Programming: Planning or scheduling activities and tasks under our
control
Linear: All restrictions (or constraints) are linear functions of the
decision variables. The objective function is linear too.
Introduction to Linear Programming • What does an LP problem involve?
- A set of activities, whose levels we need to determine
- A cost (or benefit) on each activity.
- Limiting resources to carry out activities
- Requirements on activities (individually or as a group)
- Logical, physical, logistic or other type of constraints
Mümtaz Karataş 2
1
Optimization Modeling Optimization Nomenclature
“Word problem” Mathematical
• Decision variables: Unknowns that are under our control.
formulation • We want to determine the best values for the decision variables;
maximize: z x1 x2 y
these values are the output of our model.
s. t.: x1 2 x2 5
• Any term we have control over is a decision variable.
y x12 0
• A solution is a set of values for the decision variables.
x1 , x2 0
y {0,1} • Parameters/data: Values that are fixed in the model, i.e., input.
• Parameter: An aspect of a model that is fixed.
Computer Post-optimality • Data: Specific values for the parameters.
implementation analysis • Any term we have no control over is a parameter.
• Constraints: Restrictions imposed on the decision variables.
• A feasible solution satisfies all constraints.
• Objective function: A measure indicating the value of a solution.
• The optimal solution gives the best possible value of the objective function
while satisfying all of the constraints.
What does an LP model include? LP Example
• Activities for which we need to determine values
Decision variables max : z x1 x2 y
x1 , x2 , y
•A cost (benefit) for each activity. s. t.: x1 2 x2 5
•Limited resources for activities. y x12 0
•Requirements for activities. x1 , x2 0
y {0,1}
•Logical, physical, logistical or other constraints.
5 6
Types of Optimization Problems Optimization Problem Types
• You will study three basic types of optimization problems:
LP: Linear Program
• Linear programs
• The objective function and all constraints are ILP: Integer Linear Program
linear functions of the decision variables.
• Decision variables are continuous, i.e., they can take on MILP: Mixed Integer Linear Program
fractional values.
NLP: Non Linear Program
• Integer linear programs
• The objective and constraints are still linear, but INLP: Integer Non Linear Program
• Some decision variables can only take on integer values.
• Nonlinear programs MINLP: Mixed Integer Non Linear Program
• Nonlinear functions appear in the objective or constraints.
8
Linear Programming Classification of Mathematical Models
a ) max 3x1 14 x2 7 x3 b) max 3x1 14 x2 7 x3 c ) max 7 x1 x2 17 x2 x3 27 x1 x3
x1 , x2 , x3
x1 , x2 , x3 x1 , x2 , x3
x1 4 x2 3.49287 x3 x1 x2 s.t. 10 x1 5 x2 18 x3 25 s.t. 10 x1 5 x2 18 x3 25 s.t. x1 x2 x3 2
x j {0,1} j 1, 2,3 x j 0 j 1, 2,3 x j {0,1} j 1, 2,3
x12 x22
log( x1 )
x log (7) x
1 2 2
1 1
d ) min
x1 , x2 , x3
7 x1 sin( x2 ) 8 / x3
s.t. 4 x1 16 x2 x3 29
e) min 12 x1 4 x2
x1 , x2 , x3
s.t. x1 x2 x3 1
f ) max x1 2 x2
x1 , x2 , x3
s.t. x1 / x2 5
x1 x2 0 x j 1 j 1, 2,3 0 x j j 1, 2 0 x j j 1, 2,3
x3 {0,1}
x1 x2
9 10
A Note on Mixed Integer Programs (MIPs)
Four Key Assumptions of LP and Nonlinear Programs (NLPs)
• Proportionality: Changing the value of any decision In a MIP, some decision variables cannot take on fractional
variable increases the costs (or profits, or resources values.
used...) by a proportional amount:
- Which of the four key assumptions for LP do we need to relax?
y=kx + b; k, b constant
- Can you think of an example where binary variables (i.e., variables
• Additivity: Interaction between variables is additive; that are only allowed to be 0 or 1) may be useful?
variables are never multiplied together, divided, etc. - As we will see, MIPs are much harder to solve than LPs.
• Divisibility: Decision variables are allowed to take on
An NLP uses nonlinear functions of some decision variables.
fractional values.
- Which of the four key assumptions for LP do we need to relax?
• Certainty: Data are known constants.
- Can you think of an example where a nonlinear function is useful?
- No algorithm exists that guarantees an optimal solution to every NLP.
12
Modeling LP problems LP modeling example-1
• A furniture company produces tables and chairs.
Product mix problems
• Both items are produced with a similar process
involving:
• One or more products will be produced using • carpentry
limited resources. • painting
• Each table production requires:
• Our objective is to maximize the total profit by 4 hours carpentry, 2 hours painting
taking into account the unit contribution of each • Each chair production requires:
product. 3 hours carpentry, 1 hour painting
• A total of 240 hours of carpentry and 100 hours of
• Decide how much will be produced painting is available.
• The profit from a table is 70 TL, and a chair is 50 TL
13 14
LP modeling example-1 LP modeling example-1
The furniture company aims to identify the optimal • Our objective
combination for producing tables and chairs, with the Maximize total profit
goal of maximizing total profit. • Constraints
1. Carpentry time spent cannot exceed 240 hours
2. Painting hours spent cannot exceed 100 hours
• Decision variables
T=Number of tables to be produced
C=Number of chairs to be produced
15 16
LP modeling example-1 LP modeling example-2
• Write the objective function in terms of T and C A poultry farm is considering buying two different chicken feeds
and mixing them to obtain a low-cost and nutritious feed mix.
Write an LP that determines how many kg. of which feed should
be purchased.
• Write the mathematical equations for constraints
blank Feed Content per kg blank
Amount Needed per
Protein Feed 1 Content Feed 2 Content
Chicken
A 5 10 90
B 4 3 48
C 0.5 0 1.5
price per kg 2TL 3TL blank
• T and C values must be positive
17 18
LP modeling example-2
Decision variables
Obj.Function
Constraints
19
