Workshop 1.1
Linear Programming
Linear Programming (LP) Problem
Linear Programming Problem = A method to achieve the best outcome in a mathematical model whose
requirements are represented by linear relationships.
Maximizing or minimizing a linear goal function subject to linear constraints.
How to allocate limited resources among competing activities in a best possible way?
Decision variables
- Which units do you change to reach your objective?
- For example: x1 x2 Example:
Objective function Hit the target by
- Goal of the problem using maximum 3
- Maximum or minimum arrows from
- For example: Maximize profit or minimize costs
minimal 5 meters
Constraints
- Restrictions or limitations on the decision variables distance
- For example: 5x1 + 9x2 ≤ 35
Steps in Linear Programming
Step 1 Step 2 Step 3 Step 4
Determine the Formulate the Write the Solve the LP
variables objective constraints Problem
Mathematical model for LP Different methods
Graphical method
An example of LP problem:
ABC produces two kinds of bicycles: Mountain bikes and street racers. Which amount of each type of
bicycle should be produced to maximize profit?
Two teams of producers with maximum production rate: 2 mountain bikes per day and 3 street racers per
day respectively.
Metal finishing machine requires the same amount of time for both type of bikes and can produce in total
4 bikes per day, of both types.
Mountain bikes generate a profit of $15 per bicycle and street racers $10.
,Step 1: Formulate the LP problem 1. Determine the variables
1. Determine the variables x1 = amount of produced mountain bikes per day
2. Formulate the objective x2 = amount of produced street racers per day
3. Formulate the constraints 2. Formulate the objective
Max z = 15x1 + 10x2
3. Formulate the constraints
x1 ≤ 2 Mountain bike production limit
x2 ≤ 3 Racer’s production limit
x1 + x2 ≤ 4 Metal finishing machine limit
x1,x2 ≥ 0 There can be no negative
production
Step 2: Construct a graph and plot the
constraint lines
The limiting value of each constraint is shown
as a line. Each constraint eliminates part of
the graph.
Step 3: Determine the valid side of each
constraint line
When the constrains says ≤, you have to be
below the line
When the constraint says ≥, you have to be
above the line
This is the area in which the solution should
be found
Step 4: Identify the feasible solution area
The feasible solution region on the graph is
the one which is satisfied by all the
constraints.
Choosing any point in this area would result
in a valid solution for our objective function.
,Step 5: Find the optimum
The optimum is always a corner point
Two ways to find the optimum:
1. Calculate the objective value of each Corner-Point Feasible (CPF)
The most favorable outcome of the objective is the optimum
2. Use the objective line
The optimum is where the objective function has only one point in the feasible region left
Calculate the CPF solutions Use the objective line
Calculate the intersections of the constraints Objective: Max Z = 15x1 + 10x2
and their objective value
Objective: Max Z = 15x1 + 10x2 1. Choose a random number
Hint: choose an easy multiplier of both
CPF (x1, x2) Objective value coefficients, for example 30
O (0,0) Z(0,0) = 0 2. Draw the objective line for the chosen
A (0,3) Z(0,3) = 30 number
B (1,3) Z(1,3) = 45 30 = 15 * 2 + 10 * 0
C (2,2) Z(2,2) = 50 30 = 15 * 0 + 10 * 3
D (2,0) Z(2,0) = 30 So, draw line Z(2,0) and Z(0,3)
3. Shift the objective line such that the objective
line touches only one point of the feasible
region, this will be the optimum
Z(2,2) = 50
Corner-point c is the most favorable outcome
because we want the maximum profit.
• If the goal is to minimize the objective function, find the point of contact of the ruler with the
feasible region, which is the closest to the origin. This is the optimum point for minimizing the
function.
• If the goal is to maximize the objective function, find the point of contact of the ruler with the
feasible region, which is the farthest from the origin. This is the optimum point for maximizing the
function
, LP solver in Excel
Explanation with example
The example:
Two new products have been developed:
- An 8-foot glass door with aluminum framing
- A 4x6 foot glass window with wood framing
Wyndor has three production plants:
- Plant 1 produces aluminum frames and hardware Used for doors
- Plant 2 produces wood frames Used for windows
- Plant 3 produces the glass and assembles the products Used for doors and windows
Objective is to find the optimal mix of these two new products:
- The company could sell as much of either product as could be produced by these plants
- However, both products are competing for the same production capacity in plant 3
- Determine the mix of the two products that would be most profitable
Step 1: Formulate the LP problem and write in Excel sheet
Decision variables:
X1: number of batches of doors produced per week
X2: number of batches of windows produced per week
Objective function:
Z = 3000x1 + 5000x2
Aim: maximize profit
Constraints:
X1 ≤ 4
2X2 ≤ 12
3X1 + 2X2 ≤ 18
X1, X2 ≥ 0
Linear Programming
Linear Programming (LP) Problem
Linear Programming Problem = A method to achieve the best outcome in a mathematical model whose
requirements are represented by linear relationships.
Maximizing or minimizing a linear goal function subject to linear constraints.
How to allocate limited resources among competing activities in a best possible way?
Decision variables
- Which units do you change to reach your objective?
- For example: x1 x2 Example:
Objective function Hit the target by
- Goal of the problem using maximum 3
- Maximum or minimum arrows from
- For example: Maximize profit or minimize costs
minimal 5 meters
Constraints
- Restrictions or limitations on the decision variables distance
- For example: 5x1 + 9x2 ≤ 35
Steps in Linear Programming
Step 1 Step 2 Step 3 Step 4
Determine the Formulate the Write the Solve the LP
variables objective constraints Problem
Mathematical model for LP Different methods
Graphical method
An example of LP problem:
ABC produces two kinds of bicycles: Mountain bikes and street racers. Which amount of each type of
bicycle should be produced to maximize profit?
Two teams of producers with maximum production rate: 2 mountain bikes per day and 3 street racers per
day respectively.
Metal finishing machine requires the same amount of time for both type of bikes and can produce in total
4 bikes per day, of both types.
Mountain bikes generate a profit of $15 per bicycle and street racers $10.
,Step 1: Formulate the LP problem 1. Determine the variables
1. Determine the variables x1 = amount of produced mountain bikes per day
2. Formulate the objective x2 = amount of produced street racers per day
3. Formulate the constraints 2. Formulate the objective
Max z = 15x1 + 10x2
3. Formulate the constraints
x1 ≤ 2 Mountain bike production limit
x2 ≤ 3 Racer’s production limit
x1 + x2 ≤ 4 Metal finishing machine limit
x1,x2 ≥ 0 There can be no negative
production
Step 2: Construct a graph and plot the
constraint lines
The limiting value of each constraint is shown
as a line. Each constraint eliminates part of
the graph.
Step 3: Determine the valid side of each
constraint line
When the constrains says ≤, you have to be
below the line
When the constraint says ≥, you have to be
above the line
This is the area in which the solution should
be found
Step 4: Identify the feasible solution area
The feasible solution region on the graph is
the one which is satisfied by all the
constraints.
Choosing any point in this area would result
in a valid solution for our objective function.
,Step 5: Find the optimum
The optimum is always a corner point
Two ways to find the optimum:
1. Calculate the objective value of each Corner-Point Feasible (CPF)
The most favorable outcome of the objective is the optimum
2. Use the objective line
The optimum is where the objective function has only one point in the feasible region left
Calculate the CPF solutions Use the objective line
Calculate the intersections of the constraints Objective: Max Z = 15x1 + 10x2
and their objective value
Objective: Max Z = 15x1 + 10x2 1. Choose a random number
Hint: choose an easy multiplier of both
CPF (x1, x2) Objective value coefficients, for example 30
O (0,0) Z(0,0) = 0 2. Draw the objective line for the chosen
A (0,3) Z(0,3) = 30 number
B (1,3) Z(1,3) = 45 30 = 15 * 2 + 10 * 0
C (2,2) Z(2,2) = 50 30 = 15 * 0 + 10 * 3
D (2,0) Z(2,0) = 30 So, draw line Z(2,0) and Z(0,3)
3. Shift the objective line such that the objective
line touches only one point of the feasible
region, this will be the optimum
Z(2,2) = 50
Corner-point c is the most favorable outcome
because we want the maximum profit.
• If the goal is to minimize the objective function, find the point of contact of the ruler with the
feasible region, which is the closest to the origin. This is the optimum point for minimizing the
function.
• If the goal is to maximize the objective function, find the point of contact of the ruler with the
feasible region, which is the farthest from the origin. This is the optimum point for maximizing the
function
, LP solver in Excel
Explanation with example
The example:
Two new products have been developed:
- An 8-foot glass door with aluminum framing
- A 4x6 foot glass window with wood framing
Wyndor has three production plants:
- Plant 1 produces aluminum frames and hardware Used for doors
- Plant 2 produces wood frames Used for windows
- Plant 3 produces the glass and assembles the products Used for doors and windows
Objective is to find the optimal mix of these two new products:
- The company could sell as much of either product as could be produced by these plants
- However, both products are competing for the same production capacity in plant 3
- Determine the mix of the two products that would be most profitable
Step 1: Formulate the LP problem and write in Excel sheet
Decision variables:
X1: number of batches of doors produced per week
X2: number of batches of windows produced per week
Objective function:
Z = 3000x1 + 5000x2
Aim: maximize profit
Constraints:
X1 ≤ 4
2X2 ≤ 12
3X1 + 2X2 ≤ 18
X1, X2 ≥ 0
