LINEAR PROGRAMMING SOLUTION METHODS
1
Presentation Outline
• Solution techniques
– Graphical solution
– Excel solver
2
Graphical Solution
• Possible with two decision variables
• Establish feasible region
– Constraints
• Optimal solution
– Objective function
3
Graphical Solution – Concentrate Production
• Objective function
max z = 4000x1 + 5000x2
Subject to:
1.0x1 + 1.5x2 ≤ 1,000,000
2.5x1 + 2.2x2 ≤ 3,000,000
1x1 + 0x2 ≥ 200,000
0x1 + 1x2 ≥ 300,000
1x1 + 0x2 ≤ 500,000
0x1 + 1x2 ≤ 800,000
1x1 + 0x2 ≥ 0
0x1 + 1x2 ≥ 0
4
Graphical Solution – Feasible Region
x2
• 1.0x1 + 1.5x2 = 1000000
• If x1 = 0, x2 = 667000
– (0, 667000)
• If, x2 = 0, x1 = 1000000
– (1000000, 0)
x1
5
Graphical Solution – Feasible Region
x2
• 2.5x1 + 2.2x2 = 3000000
• If x1 = 0, x2 = 1363636
– (0, 1363636)
• If, x2 = 0, x1 = 1200000
– (1200000, 0)
x1
6
Graphical Solution – Feasible Region
x2
• 1x1 + 0x2 = 200000
• (200000, 0)
x1
7
Graphical Solution – Feasible Region
x2
• 0x1 + 1x2 = 300000
• (0, 300000)
x1
8
Graphical Solution – Feasible Region
x2
• 1x1 + 0x2 = 500000
• (500000, 0)
x1
9
Graphical Solution – Feasible Region
x2
• 0x1 + 1x2 = 800000
• (0, 800000)
x1
10
Graphical Solution – Feasible Region
x2
x1
11
Graphical Solution – Feasible Region
x2
x1
12
Graphical Solution – Optimum Solution
• Optimum solution x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
– Corner point of feasible region
– Point of intersection
– Objective function
• Maximise z = 4000x1 + 5000x2
0𝑥1 + 1𝑥2 ≥ 300000
x1
13
Graphical Solution – Optimum Solution
𝟏𝒙𝟏 + 𝟏. 𝟓𝒙𝟐 = 𝟏𝟎𝟎𝟎𝟎𝟎𝟎
𝟏𝒙𝟏 + 𝟎𝒙𝟐 = 𝟐𝟎𝟎𝟎𝟎𝟎 x2 𝟏𝒙𝟏 + 𝟏. 𝟓𝒙𝟐 = 𝟏𝟎𝟎𝟎𝟎𝟎𝟎
1𝑥1 + 0𝑥 2 ≥ 200000
1𝑥1 + 0𝑥 2 ≤ 500000
⟹ 𝑥1 = 200000 𝟏𝒙𝟏 + 𝟎𝒙𝟐 = 𝟓𝟎𝟎𝟎𝟎𝟎
S𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑒 𝑥1 = 200000 𝑖𝑛 1𝑥1 + 1.5𝑥2 = 1000000 ⟹ 𝑥1 = 500000
1000000 200000 S𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑒 𝑥1 = 500000 𝑖𝑛 1𝑥1 + 1.5𝑥2 = 1000000
⟹ 𝑥2 = − = 533333.34
1.5 1.5 1000000 500000
⟹ 𝑥2 = − = 333333.34
𝑧 = 4000𝑥1 + 5000𝑥2 @ 𝑥1 = 200000 𝑎𝑛𝑑 𝑥2 = 533333.34 1.5 1.5
𝑧 = $3,466,666,667 𝑧 = 4000𝑥1 + 5000𝑥2 @ 𝑥1 = 500000 𝑎𝑛𝑑 𝑥2 = 333333.34
𝒛 = $𝟑, 𝟔𝟔𝟔, 𝟔𝟔𝟔, 𝟕𝟎𝟎
0𝑥1 + 1𝑥 2 ≥ 300000
x1
𝟎𝒙𝟏 + 𝟏𝒙𝟐 = 𝟑𝟎𝟎𝟎𝟎𝟎 𝟎𝒙𝟏 + 𝟏𝒙𝟐 = 𝟑𝟎𝟎𝟎𝟎𝟎
𝟏𝒙𝟏 + 𝟎𝒙𝟐 = 𝟐𝟎𝟎𝟎𝟎𝟎 𝟏𝒙𝟏 + 𝟎𝒙𝟐 = 𝟓𝟎𝟎𝟎𝟎𝟎
⟹ 𝑥1 = 200000 𝑎𝑛𝑑 𝑥2 = 300000 ⟹ 𝑥1 = 500000 𝑎𝑛𝑑 𝑥2 = 300000
𝑧 = 4000𝑥1 + 5000𝑥2 @ 𝑥1 = 200000 𝑎𝑛𝑑 𝑥2 = 300000 𝑧 = 4000𝑥1 + 5000𝑥2 @ 𝑥1 = 500000 𝑎𝑛𝑑 𝑥2 = 300000
𝑧 = $2,300,000,000 𝑧 = $3,500,000,000
14
Graphical Solution – Optimum Solution
• Optimum solution x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
– Corner point of feasible region
– Point of intersection
– Objective function
• Assume: 4000x1 + 5000x2 =
2000000000
– If x1 = 0, x2 = 400000
– If x2 = 0, x1 = 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
15
Graphical Solution – Optimum Solution
x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
16
Graphical Solution – Optimum Solution
x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
17
Graphical Solution – Optimum Solution
x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
18
Graphical Solution – Optimum Solution
x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
19
Graphical Solution – Optimum Solution
x2
1𝑥1 + 0𝑥2 ≥ 200000
1𝑥1 + 0𝑥2 ≤ 500000
0𝑥1 + 1𝑥2 ≥ 300000
x1
20
Graphical Solution – Optimum Solution
• Point of intersection
– 1x1 + 0x2 = 500,000
– 1x1 + 1.5x2 = 1,000,000
– x1 = 500,000 tonne
– x2 = 333,333 tonne
21
Graphical Solution – Post Solution Analysis
• Binding constraints
– 1x1 + 0x2 ≤ 500,000
– 1x1 + 1.5x2 ≤ 1,000,000
22
Graphical Solution – Post Solution Analysis
• Non-binding constraints
– 1x1 + 0x2 ≥ 200,000
– 0x1 + 1x2 ≥ 300,000
– 0x1 + 1x2 ≤ 800,000
– 2.5x1 + 2.2x2 ≤ 3,000,000
23
Graphical Solution – Post Solution Analysis
• Redundant constraints
– 2.5x1 + 2.2x2 ≤ 3,000,000
– 0x1 + 1x2 ≤ 800,000
24
Graphical Solution – Minimisation Problem
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒 𝑧 = 30𝑥1 + 20𝑥2
500𝑥1 + 100𝑥2 ≥ 1000000
200𝑥1 + 200𝑥2 ≥ 1200000
100𝑥1 + 400𝑥2 ≥ 1200000
1𝑥1 + 0𝑥2 ≥ 0
0𝑥1 + 1𝑥2 ≥ 0
25
Graphical Solution – Minimisation Problem
26
Graphical Solution – Minimisation Problem
27
Graphical Solution – Minimisation Problem
28
Graphical Solution – Minimisation Problem
29
Graphical Solution – Minimisation Problem
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒 𝑧 = 30𝑥1 + 20𝑥2
500𝑥1 + 100𝑥2 ≥ 1000000
200𝑥1 + 200𝑥2 ≥ 1200000
100𝑥1 + 400𝑥2 ≥ 1200000
1𝑥1 + 0𝑥2 ≥ 0
0𝑥1 + 1𝑥2 ≥ 0
𝟓𝟎𝟎𝒙𝟏 + 𝟏𝟎𝟎𝒙𝟐 = 𝟏𝟎𝟎𝟎𝟎𝟎𝟎
𝟐𝟎𝟎𝒙𝟏 + 𝟐𝟎𝟎𝒙𝟐 = 𝟏𝟐𝟎𝟎𝟎𝟎𝟎
⟹ 𝑥1 = 2000 − 0.2𝑥2
S𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑒 𝑥1 𝑖𝑛 200𝑥1 + 200𝑥2 = 1200000
200 2000 − 0.2𝑥2 + 200𝑥2 = 1200000
400000 − 40𝑥2 + 200𝑥2 = 1200000
1200000 400000
⟹ 𝑥2 = − = 5000
160 160
⟹ 𝑥1 = 2000 − 0.2 5000 = 1000
𝒛 = 𝟑𝟎𝒙𝟏 + 𝟐𝟎𝒙𝟐 @ 𝒙𝟏 = 𝟏𝟎𝟎𝟎 𝒂𝒏𝒅 𝒙𝟐 = 𝟓𝟎𝟎𝟎
𝒛 = $𝟏𝟑𝟎, 𝟎𝟎𝟎
30
Excel Solver – Concentrate Production
31
Excel Solver – Concentrate Production
32
Excel Solver – Concentrate Production
33
Excel Solver – Concentrate Production
34
Excel Solver – Concentrate Production
35
Excel Solver – Concentrate Production
36
Excel Solver – Concentrate Production
37
Excel Solver – Concentrate Production
38