LESSON 3. Big M Method- Special Case

1.4 Special Case:

Unrestricted (unconstrained) Variables

Sometimes decision variables are unrestricted in sign (positive, negative or zero). In all such cases, the decision variables can be expressed as the difference between two non-negative variables. For example, if x1 is unrestricted in sign, then Put x1 = x1' - x1''

Example:

Maximize z = 2x1 + 3x2

Subject to

-x1 + 2x2≤  4
 x1 + x2  ≤ 6
  x1 + 3x2 ≤ 9

x1, x2 are unrestricted in sign

Solution:

Since x1 and x2 are unrestricted in sign, we can replace them by non-negative variables x1' , x1'', x2' , x2'' .

Put x1 = x1' - x1''
      x2 = x2' - x2''

The given problem can be written as

Max. z = 2(x1' - x1'') + 3(x2' - x2'')

Subject to

-(x1' - x1'') + 2(x2' - x2'') ≤  4
 (x1' - x1'') + (x2' - x2'') ≤ 6
   (x1' - x1'') + 3(x2' - x2'') ≤ 9

Introducing slack variables

Max. z = 2x1' - 2x1'' + 3x2' - 3x2''

Subject to

  -x1' + x1'' + 2x2' - 2x2'' + x3 = 4
     x1’ - x1'' + x2'- x2'' + x4 = 6
   x1' - x1'' + 3x2' - 3x2'' + x5 = 9

where x3, x4 and x5 are slack variables

Iteration 1:

    

cj

2

-2

3

-3

0

0

0

    

cB

Basic variables
B

x1'

x1''

x2'

x2''

x3

x4

x5

Solution values
b (=XB)

0

x3

-1

1

2

-2

1

0

0

4

0

x4

1

-1

1

-1

0

1

0

6

0

x5

1

-1

3

-3

0

0

1

9

zj-cj

 

-2

2

-3

3

0

0

0

 

 Key column = x2' column.
Minimum (4/2, 6/1, 9/3) = 2
Key row = x3 row.
Pivot element = 2
x3 departs and x2' enters.

Iteration 2:

 

cj

2

-2

3

-3

0

0

0

 

cB

Basic variables
B

x1'

x1''

x2'

x2''

x3

x4

x5

Solution values
b (=XB)

3

x2'

-1/2

1/2

1

-1

1/2

0

0

2

0

x4

3/2

-3/2

0

0

-1/2

1

0

4

0

x5

5/2

-5/2

0

0

-3/2

0

1

3

zj-cj

 

-7/2

7/2

0

0

3/2

0

0

 

Iteration 3:

 

cj

2

-2

3

-3

0

0

0

 

cB

Basic variables
B

x1'

x1''

x2'

x2''

x3

x4

x5

Solution values
b (=XB)

3

x2'

0

0

1

-1

1/5

0

1/5

13/5

0

x4

0

0

0

0

2/5

1

-3/5

11/5

2

x1'

1

-1

0

0

-3/5

0

2/5

6/5

zj-cj

 

0

0

0

0

-3/5

0

7/5

 

 

Iteration 4:

 

cj

2

-2

3

-3

0

0

0

 

cB

Basic variables
B

x1'

x1''

x2'

x2''

x3

x4

x5

Solution values
b (=XB)

3

x2'

0

0

1

-1

0

-1/2

1/2

3/2

0

x3

0

0

0

0

1

5/2

-3/2

11/2

2

x1'

1

-1

0

0

0

3/2

-1/2

9/2

zj-cj

 

0

0

0

0

0

3/2

1/2

 

Result:

      The optimal solution is x1' = 9/2, x1'' = 0, x2' = 3/2, x2'' = 0.

Solution of the original problem is
                               x1 = x1' - x1'' = 9/2 - 0 = 9/2
                                x2 = x2' - x2'' = 3/2 - 0 = 3/2
                               Max z = 2 x 9/2 + 3 x 3/2 = 27/2.          

 

Last modified: Thursday, 3 October 2013, 6:42 AM