Advanced Business Modeling CIS 418
Linear Programming:
Production problems
Simon Business School CIS 418 Professor Ricky Roet-Green
Why Linear Programming?
• Linear programming (LP) is a tool to solve decision problems where • relationships between decision variables and the objective are linear
• relationships between decision variables and constraints are linear
• Widely used in for a variety of applications. For example: • production planning
• Portfolio optimization • Scheduling
• Algorithms exist to find globally optimal solutions
Simon Business School Professor Ricky Roet-Green
2
Linear vs. Non-linear
• Linear: sum of variables, multiple by scalar (coefficient) x
• Non-linear:
1
5x 1
5x 3x 12
5x 3x x 100x 2.33x … 12345
x2 3x ln(x) sin(x) ex1 5xln(x) xx 11111212
This formulation is linear But this one is not
x1 + x3 ≥ x2 (x1+x3)/x2 ≥ 1
LP: constraints and objective are linear functions
Simon Business School Professor Ricky Roet-Green
3
Example: Desks or Tables?
A manufacturer makes wooden desks and tables.
Each desk requires 4 hours to cut and 2 hours to assemble.
Each table requires 3 hours to cut and 5 hours to assemble.
The manufacturer can do only up to 12 hours of cutting and 10 hours of assembling per day.
Profit is 15$ per desk and 12$ per table.
What would be the production plan that maximizes the profit?
Simon Business School Professor Ricky Roet-Green
4
Formulate the problem
Variables: Desks -x1 Tables -x2 Constraints:
Cutting: 4x 3x 12 12
Assembling: 2x 5x 10 12
Non-negative production: x 0, 12
Linear
Objective: max profit
15x 12x 12
Linear
Simon Business School
Professor Ricky Roet-Green
5
x 0
Graphic Solution
Tables x2 4
3 2
1
0
Simon Business School
Can we produce (3,2)? Can we produce (1,2)? Can we produce (1,1)? Should we produce (1,1)?
Cutting
4x 3x 12 12
(1,2)
(1,1)
Isoprofit
15x 12x 12
Optimal solution
Nodes
Profit
(0,0)
0
(0,2)
24
(3,0)
45
(2.14,1.14)
45.78
x 0 1
(3,2)
Assembling
2x 5x 10 1 2
Feasible 15x 12x 15 Area
12
1 𝑥 =02 3
Professor Ricky Roet-Green
4 x5 Desks 21
6
Feasible area and optimal solution
• Feasible area – the set of all possible variable combinations.
• Binding constraints – constraints that define the edges of the feasible set.
• Not all constraints are binding. For example: x2
This constraint is not binding
New Optimal
Relax
0
Feasible Area
solution
Optimal solution
x1
• If we relax a constraint (if we have more resources), the feasible area
might change and so is the solution.
Simon Business School Professor Ricky Roet-Green
7
Solution properties
• An LP problem could have either:
• A unique solution – only if the feasible set is bounded and has no holes.
• Multiple solutions – if the isoprofit line is parallel to a binding constraint line.
• No solution – for example, if the feasible set is not bounded, or if the feasible set is null.
Multiple solutions
No solution
Simon Business School
Professor Ricky Roet-Green
8
Solution properties – Summary
• Isoprofit line – the line that represents the objective function.
• The isoprofit lines are parallel to each other
• A unique solution would be found on the intersection between binding constraints.
• The solution can change if:
• A binding constraint is relaxed
• Another constraint is added
• The profitability ratios between variables change (and therefore the objective function changes).
Simon Business School Professor Ricky Roet-Green
9
Example: Go-Green!
• Go-Green! company provides all the ingredients plus the recipes for cooking your own meals at home. Customers can choose between Organic, Vegan and Green meals.
• Each meal is built from a mix of ingredients in inventory: • Peppers
• Kale
• Tomatoes
• Butternut squash • Arugula
• Your goal is to produce the mix of meals which will maximize profits, given the inventory.
All parameters are detailed in the excel file LP_problems.xlsx
Simon Business School Professor Ricky Roet-Green
10
Formulate the problem
1. What are the variables? Name them (x , x , …) 12
2. What are the constraints? Write them in a mathematical form (inequalities)
3. What is the objective function? Write it in a mathematical form.
4. Do we maximize or minimize the objective? Simon Business School Professor Ricky Roet-Green
11
Formulate the problem
1. What are the variables? Name them (x , x , …) 12
Organic- x1 Vegan- x2 Green- x3
2. What are the constraints? Write them in a mathematical form (inequalities)
x x 450 12
• Peppers
• Kale
• Tomatoes
• Butternut squash
• Arugula
• Non-negative production:
x 250 1
2x 2x x 800 123
x x 450 12
2x x x 600 123
3. What is the objective function? Write it in a mathematical form.
75x 50x 35x 123
4. Do we maximize or minimize the objective? Maximize Simon Business School Professor Ricky Roet-Green
Profit:
x0, x0, x0 123
12
Feasibility
• Build a spreadsheet to calculate the profit from a mix of 200 Organic meals,
200 Vegan meals, and 10 Green meals.
• Is it feasible to build this combination of products? How do you know?
Simon Business School Professor Ricky Roet-Green
13
Feasibility check
PARAMETERS
Bill of Materials
Profit Margin
Peppers
Kale
T omatoes
Butternut squash
Arugula
Organic dinner
$ 75.00
Organic dinner
1
1
2
1
2
Vegan dinner
$ 50.00
Vegan dinner
1
0
2
1
1
Green dinner
$ 35.00
Green dinner
0
0
1
0
1
Inventory
Peppers
Kale
T omatoes
Butternut squash
Arugula
450
250
800
450
600
Decision Variables
Organic dinner
Vegan dinner
Green dinner
Peppers
Kale
T omatoes
Butternut squash
Arugula
Simon Business School Professor Ricky Roet-Green
14
200
200
10
200
810
400
610
<
<
>
<
>
Objective
Organic dinner
Vegan dinner
Green dinner
450
250
800
450
600
Profit
$ 15,000.00
$ 10,000.00
$ 350.00
Calculations
Used
400
Total Profit
Avaliable
$ 25,350.00
Solving the optimization problem
• The problem has more than two variables – therefore it is more difficult to solve on paper (we would need to draw a 3D graph…)
• Therefore we solve it by using Excel Solver.
When we solve an optimization problem using excel, we do the following: • Choose arbitrary variables (Guess!)
• Calculate the constraints using those arbitrary variables
• Calculate the objective using those arbitrary variables
• Use solver and define the variables, objective and constraints • Let solver find the solution for you
Simon Business School Professor Ricky Roet-Green
15
LP using vector and matrix notation
n decision variables as a column vector
x1 x
2
x
Product of a row vector and a column vector as the objective
n x1
x
n
m constraints, all constraints are linear combinations of the n decision
variables
c
c
c
1
2
1
1
2
2
n
n
c x
x
n c
x
c
x
2
a11 a12
a1n x a11x1a12x2 a1nxn b1 a 1 axax ax b
a a 21
22
2nx2 21 1 22 2 2n n 2
a a
x
m1 m2 Simon Business School
a n axax ax b mn m1 1 m2 2 mn n m
Professor Ricky Roet-Green
16
Very brief review of matrix (array) multiplication
Array dimensions are denoted as [number of rows x number of columns]
[n x 1] x1
[1 x n]
[m x n]
x
2
x
n
Two matrices can be multiplied if their internal dimensions match. The result has the same number of rows as the first matrix and the same number of columns as the second.
[1 x n] x
[n x 1] = [1 x 1] 𝑥1
×𝑥2 =𝑐𝑥+𝑐𝑥+⋯+𝑐𝑥 :1122 𝑛𝑛
𝑥𝑛
𝑐1 𝑐2
… 𝑐𝑛
Simon Business School
Professor Ricky Roet-Green 17
A very brief review of how to multiply matrices
Matrix multiplication is not commutative: AxB ≠ BxA
[n x 1] x 𝑥1
𝑥2 ×𝑐1 𝑐2 𝑥𝑛
[1 x n] = [n x n] 𝑥1 𝑐1 𝑥1 𝑐2
𝑐𝑛 =𝑥2𝑐1 𝑥2𝑐2 𝑥𝑛𝑐1 𝑥𝑛𝑐2
[n x 1] = [1 x 1] 𝑥1
𝑥1 𝑐𝑛 𝑥2𝑐𝑛
𝑥𝑛𝑐𝑛
[1 x n] 𝑐1 𝑐2
x
𝑐𝑛 × 𝑥2 =𝑐1𝑥1+𝑐2𝑥2+⋯+𝑐𝑛𝑥𝑛 𝑥𝑛
The element in row r and column m of the result is the matrix product of
• row r of the first matrix and
• column m of the second matrix.
Simon Business School Professor Ricky Roet-Green
18
Useful excel functions
• SUMPRODUCT – sum the product of two arrays. The dimension of the two arrays must be equal!
• Array1 = [1 2 3 5]
• Array2 = [4 5 6 2]
Sumproduct(Array1, Array2)=1*4+2*5+3*6+5*2=42 • TRANSPOSE – transpose a matrix. 1
• Array1 = [1 2 3 5] TRANSPOSE(Array1) = 2
• Matrix2 = 3 2 1 7 2 4 5 1
TRANSPOSE(Matrix2) =
3 2 6 2 4 5
152
6 5 2 1
7 1 1
If you are using the TRANSPOSE function, you must enter the formula in as an array formula, i.e. use
Simon Business School Professor Ricky Roet-Green
19
3 5
Useful excel functions (cont.)
• Mmult – the product of two matrices.
The inner dimensions of the two matrices must be equal! Matrix1: [5 3 2] – it is a 1×3 matrix
Matrix2: 3 2 1 7 – it is a 3×4 matrix
2 4 5 1
6 5 2 1
Mmult(Matrix1, Matrix2)= [33 32 24 40] -1×4 matrix (=vector in this case) • For array operations the first step is to select the area that will have the correct
dimensions for the result.
• After entering the function use
• Use MMULT(A,B) to multiply two matrices: A and B. Remember MMULT(A,B)≠ MMULT(B,A). To multiply more than two matrices, you can nest MMULT() operations.
Simon Business School Professor Ricky Roet-Green
20
Setting up decision variables as a row vector
PARAMETERS
Bill of Materials
Profit Margin
Peppers
Kale
T omatoes
Butternut squash
Arugula
Organic dinner
$ 75.00
Organic dinner
1
1
2
1
2
Vegan dinner
$ 50.00
Vegan dinner
1
0
2
1
1
Green dinner
$ 35.00
Green dinner
0
0
1
0
1
Inventory
Peppers
Kale
T omatoes
Butternut squash
Arugula
450
250
800
450
600
Objective: profit 75
𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 𝑥𝑉𝑒𝑔𝑎𝑛 𝑥𝐺𝑟𝑒𝑒𝑛 × 50 =75𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 +50𝑥𝑉𝑒𝑔𝑎𝑛 +35𝑥𝐺𝑟𝑒𝑒𝑛
35
Constraints: inventory
𝑥 11212 𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 𝑥𝑉𝑒𝑔𝑎𝑛 𝐺𝑟𝑒𝑒𝑛 ×1 0 2 1 1=
00101
= (𝑥𝑂𝑟+𝑥𝑉) (𝑥𝑂𝑟) (2𝑥𝑂𝑟 + 2𝑥𝑉 + 𝑥𝐺) (𝑥𝑂𝑟 + 𝑥𝑉) (2𝑥𝑂𝑟 + 𝑥𝑉 + 𝑥𝐺)
Simon Business School Professor Ricky Roet-Green
21
Setting up decision variables as a column vector
PARAMETERS
Bill of Materials
Profit Margin
Peppers
Kale
T omatoes
Butternut squash
Arugula
Organic dinner
$ 75.00
Organic dinner
1
1
2
1
2
Vegan dinner
$ 50.00
Vegan dinner
1
0
2
1
1
Green dinner
$ 35.00
Green dinner
0
0
1
0
1
Inventory
Peppers
Kale
T omatoes
Butternut squash
Arugula
450
250
800
450
600
Objective: profit
75 50 35
Constraints: inventory
1 1 0
1 0 0
2 2 1 ×
1 1 0
2 1 1
𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 𝑥𝑉𝑒𝑔𝑎𝑛 𝑥𝐺𝑟𝑒𝑒𝑛
×
=75𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 +50𝑥𝑉𝑒𝑔𝑎𝑛 +35𝑥𝐺𝑟𝑒𝑒𝑛 𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 + 𝑥𝑉𝑒𝑔𝑎𝑛
𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐
= 2𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 + 2𝑥𝑉𝑒𝑔𝑎𝑛 + 𝑥𝐺𝑟𝑒𝑒𝑛
𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 + 𝑥𝑉𝑒𝑔𝑎𝑛 2𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 + 𝑥𝑉𝑒𝑔𝑎𝑛 + 𝑥𝐺𝑟𝑒𝑒𝑛
𝑥𝑂𝑟𝑔𝑎𝑛𝑖𝑐 𝑥𝑉𝑒𝑔𝑎𝑛 𝑥𝐺𝑟𝑒𝑒𝑛
Simon Business School
Professor Ricky Roet-Green 22
Robustness
• Problem: if something changes in the data, the solution might change
• If you are running a business, you want to make sure that small changes in
prices would not drag you into a completely different production setting.
• Would the current solution still be optimal?
• How robust is the solution?
• Answer: by sensitivity analysis.
• Go back to the spreadsheet, in risk solver choose
Reports ->Optimization -> Sensitivity
Simon Business School Professor Ricky Roet-Green
23
Sensitivity Report
Simon Business School Professor Ricky Roet-Green
24
What happens if the profit margins change?
These capture a change in the isoprofit function.
As long as profit margins stay in the allowable region, the optimal solution does not change.
If the Organic dinner profit margin rose up to $100 per dinner or fell to $70 per dinner (while other profit margins did not change), it would still be optimal to produce 200 Organic dinners and 200 Vegan dinners.
The optimal mix would change if the Organic dinner profit margin increased past $100, or decreased below $70.
Simon Business School Professor Ricky Roet-Green
25
What is the reduced cost?
Holding all else constant, the profit margin for Green dinners will have to increase by $2.50 before we would consider producing any Green dinners out of our inventory.
Simon Business School Professor Ricky Roet-Green
26
Shadow prices
Non-zero shadow prices (aka dual variables) are associated with binding constraints.
Just ONE more tomato would increase profits by $12.50, one extra arugula would increase profits by $25.
If the supply of arugula increases past 650 units, or decreases past 400 units, the shadow price associated with the arugula changes.
Simon Business School Professor Ricky Roet-Green 27
Shadow prices
Lets assume we do not have the sensitivity report. How can we figure out the shadow price of tomatoes?
Simon Business School Professor Ricky Roet-Green
28
Shadow prices
Lets assume we do not have the sensitivity report. How can we figure out the shadow price of tpmatoes?
Solution:
• We add one more tomato to the inventory.
• We keep everything else fixed.
• We calculate the optimal profit with the additional tomato.
• The shadow price of a tomato is the difference between the new profit and the
previous profit.
• If the profit did not change the price would be 0. It happens if the constraint over
tomatoes is not binding.
Simon Business School Professor Ricky Roet-Green
29