University:
Whitman College
Course:
MATH-339 | Operations Research
Academic year:

2022
Views:

169

Pages:

3
Author:

Laura Werner

Examples, Big M Method 1. See the Maple file: BigM_Example01.mw Here is the LP: max z = −x1 +2x2 st x1 +x2 ≥ 2 −x1 +x2 ≥ 1 x2 ≤3 Initial tableau using Big-M a1 a2 s1 x1 x2 e1 e2 s1 a1 a2 1 −2 0 0 0 M M 1 1 −1 0 0 1 0 −1 1 0 −1 0 0 1 0 1 0 0 1 0 0 0 2 1 3 Ending tableau: e2 x2 e1 x1 x2 e1 e2 s1 a1 a2 1 0 0 0 2 M M 0 1 0 0 1 1 0 −1 2 0 1 0 0 1 0 0 3 1 0 1 0 1 −1 0 1 And our optimal solution is given as x1 = 0, x2 = 3, with z = 6. 1 2. See BigM_Example02.mw on the class website. This is the LP: max z = st x1 +3x2 +x3 x1 +x2 +2x3 ≤ 4 −x1 +x3 ≥ 4 x3 ≥ 3 Where the initial tableau is given by: s1 a1 a2 x1 x2 x3 s1 e1 e2 a1 a2 rhs −1 −3 −1 0 0 0 M M 1 1 2 1 0 0 0 0 4 −1 0 1 0 −1 0 1 0 4 0 0 1 0 0 −1 0 1 3 Here’s the final tableau, through Maple: − 12 x3 a1 a2 x1 x2 x 3 5 + 2M − 2 + M 0 1/2 1/2 1 −3/2 −1/2 0 −1/2 −1/2 0 1 2 s1 e1 e2 a1 a2 rhs + M M M 0 0 2 − 3M 1/2 0 0 0 0 2 −1/2 −1 0 1 0 2 −1/2 0 −1 0 1 1 Since M is an arbitrarily large positive number, all Row 0 Coefficients are now considered non-negative. Additionally, we failed to remove the artificial variables from the BFS, so therefore, the LP is infeasible. 2 3. See BigM_Example03.mw from the class website. Here is the LP max z = st x1 +x2 x1 −x2 −x3 =1 −x1 +x2 +2x3 −x4 = 1 Construct the tableau, then remove the M’s: x 1 x 2 x 3 x 4 a1 a2 −1 −1 0 0 M M 0 1 −1 −1 0 1 0 1 −1 1 2 −1 0 1 1 And the final tableau: x1 x3 x1 x2 x3 x4 a1 a2 0 −2 0 −1 2 + M 1 + M 3 1 −1 0 −1 2 1 3 0 0 1 −1 1 1 2 The artificial variables can now be safely deleted (they are non-basic variables). We see that normally we would go into the Simplex Method with our current BFS, but we are unable to pivot in either column 2 or column 4. The LP is unbounded, which is clear if we write the system of equations: We maximize z = 3 + x2 + x4 such that:     x= 3 0 2 0        + x2    1 1 0 0        + x4    1 0 1 1      so x2 , x4 can each be increased without bound (and remain feasible). 3

Big M Method - Cheat Sheet

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock