We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > Revised Simplex method example
9. Revised Simplex method example ( Enter your problem )
( Enter your problem )
  1. Standard form-1 : Example-1
  2. Standard form-1 : Example-2
  3. Standard form-1 : Example-3
  4. Standard form-2 using Two-Phase method : Example-1
  5. Standard form-2 using Two-Phase method : Example-2
  6. Standard form-2 using Two-Phase method : Example-3
  7. Standard form-2 using Big M method : Example-1
  8. Standard form-2 using Big M method : Example-2
  9. Standard form-2 using Big M method : Example-3
 		Other related methods
  1. Formulate linear programming model
  2. Graphical method
  3. Simplex method (BigM method)
  4. Two-Phase method
  5. Primal to dual conversion
  6. Dual simplex method
  7. Integer simplex method
  8. Branch and Bound method
  9. 0-1 Integer programming problem
  10. Revised Simplex method
8. Standard form-2 using Big M method : Example-2
(Previous example)

9. Standard form-2 using Big M method : Example-3


Find solution using Revised Simplex (BigM) method
MIN Z = 3x1 + 2x2 + x3
subject to
x1 + x2 + x3 >= 4
x2 - x3 <= 2
x1 + x2 + 2x3 = 6
and x1,x2,x3 >= 0

Solution:
Problem is
Min `Z``=````3``x_1`` + ``2``x_2`` + ````x_3`
subject to
`````x_1`` + ````x_2`` + ````x_3`≥`4`
`````x_2`` - ````x_3`≤`2`
`````x_1`` + ````x_2`` + ``2``x_3`=`6`
and `x_1,x_2,x_3 >= 0; `
`:.` Max `Z``=`` - ``3``x_1`` - ``2``x_2`` - ````x_3`


Step-1 :
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

After introducing slack,surplus,artificial variables
`````x_1`` + ````x_2`` + ````x_3`` - ````S_1`` + ````A_1`=`4`
`````x_2`` - ````x_3`` + ````S_2`=`2`
`````x_1`` + ````x_2`` + ``2``x_3`` + ````A_2`=`6`


The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

After introducing slack,surplus,artificial variables
`````Z'`` + ``3``x_1`` + ``2``x_2`` + ````x_3`` - ``M``A_1`` - ``M``A_2`=`0`
`````x_1`` + ````x_2`` + ````x_3`` - ````S_1`` + ````A_1`=`4`
`````x_2`` - ````x_3`` + ````S_2`=`2`
`````x_1`` + ````x_2`` + ``2``x_3`` + ````A_2`=`6`


Now represent the new system of constraint equations in the matrix form
`[[1,3,2,1,0,0,-M,-M],[0,1,1,1,-1,0,1,0],[0,0,1,-1,0,1,0,0],[0,1,1,2,0,0,0,1]][[Z'],[x_1],[x_2],[x_3],[S_1],[S_2],[A_1],[A_2]]=[[0],[4],[2],[6]]`

or
`[[1,-c],[0,A]][[Z],[x]]=[[0,b]]; x>=0`

where `e=beta_0,a_4=beta_1,a_5=beta_2,a_6=beta_3`

Step-2 : The basis matrix `B_1` of order `(3+1)=4` can be expressed as

`B_1=[beta_0,beta_1,beta_2,beta_3]=[[1,-M,0,-M],[0,1,0,0],[0,0,1,0],[0,0,0,1]]`

Then, `B_1^(-1)=[[1,C_B B^(-1)],[0,B^(-1)]]=1; B=[[1,0,0],[0,1,0],[0,0,1]]=[beta_1,beta_2,beta_3]; C_B=[0,0,0]`

Basis Inverse `B_1^(-1)`Additional table
`B``X_B``beta_0`
`Z'`		`beta_1`
`A_1`		`beta_2`
`S_2`		`beta_3`
`A_2`		`y_1`
 		Min Ratio
`(X_B)/(y_1)`		`x_1``x_2``x_3``S_1`
`Z'``0``1``-M``0``-M`---`3``2``1``0`
`A_1``4``0``1``0``0`---`1``1``1``-1`
`S_2``2``0``0``1``0`---`0``1``-1``0`
`A_2``6``0``0``0``1`---`1``1``2``0`


Iteration=1 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`

`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`

`="Min"{[[1,-M,0,-M]] [[3,2,1,0],[1,1,1,-1],[0,1,-1,0],[1,1,2,0]]}`

`="Min"{[[-2M+3,-2M+2,-3M+1,M]]}`

`=-3M+1` (correspnds to `z_3-c_3`)

Thus, vector `x_3` is selected to enter into the basis, for `k=3`

Step-4: To select a basic variable to leave the basis, we compute `y_k` for k=3, as follows


`y_3= B_1^(-1) a_3=[[1,-M,0,-M],[0,1,0,0],[0,0,1,0],[0,0,0,1]] [[1],[1],[-1],[2]]=[[-3M+1],[1],[-1],[2]]`

and `X_B = [[0],[4],[2],[6]]`

Now, calculate the minimum ratio to select the basic variable to leave the basis
`x_(Br)/y_(rk)= "Min" {x_(Bi)/y_(ik), y_(ik)>0}`

`="Min"{(4)/(1),(6)/(2)}`

`="Min"{4,3}`

`=3 ("correspnds to " x_(B3)/y_(33))`

Thus, vector `A_2` is selected to leave the basis, for `r=3`

The table with new entries in column `y_3` and the minimum ratio

Basis Inverse `B_1^(-1)`Additional table
`B``X_B``beta_0`
`Z'`		`beta_1`
`A_1`		`beta_2`
`S_2`		`beta_3`
`A_2`		`y_3`
 		Min Ratio
`(X_B)/(y_3)`		`x_1``x_2``x_3``S_1`
`Z'``0``1``-M``0``-M``-3M+1`---`3``2``1``0`
`A_1``4``0``1``0``0``1``4``1``1``1``-1`
`S_2``2``0``0``1``0``-1`---`0``1``-1``0`
`A_2``6``0``0``0``1``2``3``1``1``2``0`


The table solution is now updated by replacing variable `A_2` with the variable `x_3` into the basis.

For this we apply the following row operations in the same way as in the simplex method
`X_B``beta_1``beta_2``beta_3``y_3`
`R_1``0``-M``0``-M``-3M+1`
`R_2``4``1``0``0``1`
`R_3``2``0``1``0``-1`
`R_4``6``0``0``1``2`


`R_4`(new)`= R_4`(old)` -: 2`
`R_4`(old) = `6``0``0``1`
`R_4`(new)`= R_4`(old)` -: 2``3``0``0``1/2`


`R_1`(new)`= R_1`(old) + `(3M-1) R_4`(new)
`R_1`(old) = `0``-M``0``-M`
`R_4`(new) = `3``0``0``1/2`
`3M-1 xx R_4`(new) = `9M-3``0``0``(3M-1)/2`
`R_1`(new)`= R_1`(old) + `(3M-1) R_4`(new)`9M-3``-M``0``(M-1)/2`


`R_2`(new)`= R_2`(old) - `R_4`(new)
`R_2`(old) = `4``1``0``0`
`R_4`(new) = `3``0``0``1/2`
`R_2`(new)`= R_2`(old) - `R_4`(new)`1``1``0``-1/2`


`R_3`(new)`= R_3`(old) + `R_4`(new)
`R_3`(old) = `2``0``1``0`
`R_4`(new) = `3``0``0``1/2`
`R_3`(new)`= R_3`(old) + `R_4`(new)`5``0``1``1/2`


The improved solution is
Basis Inverse `B_1^(-1)`Additional table
`B``X_B``beta_0`
`Z'`		`beta_1`
`A_1`		`beta_2`
`S_2`		`beta_3`
`x_3`		`y_3`
 		Min Ratio
`(X_B)/(y_3)`		`x_1``x_2``A_2``S_1`
`Z'``9M-3``1``-M``0``(M-1)/2`---`3``2``M``0`
`A_1``1``0``1``0``-1/2`---`1``1``0``-1`
`S_2``5``0``0``1``1/2`---`0``1``0``0`
`x_3``3``0``0``0``1/2`---`1``1``1``0`


Iteration=2 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`

`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`

`="Min"{[[1,-M,0,(M-1)/2]] [[3,2,M,0],[1,1,0,-1],[0,1,0,0],[1,1,1,0]]}`

`="Min"{[[(-M+5)/2,(-M+3)/2,(3M-1)/2,M]]}`

`=(-M+3)/2` (correspnds to `z_2-c_2`)

Thus, vector `x_2` is selected to enter into the basis, for `k=2`

Step-4: To select a basic variable to leave the basis, we compute `y_k` for k=2, as follows


`y_2= B_1^(-1) a_2=[[1,-M,0,(M-1)/2],[0,1,0,-1/2],[0,0,1,1/2],[0,0,0,1/2]] [[2],[1],[1],[1]]=[[(-M+3)/2],[1/2],[3/2],[1/2]]`

and `X_B = [[9M-3],[1],[5],[3]]`

Now, calculate the minimum ratio to select the basic variable to leave the basis
`x_(Br)/y_(rk)= "Min" {x_(Bi)/y_(ik), y_(ik)>0}`

`="Min"{(1)/(1/2),(5)/(3/2),(3)/(1/2)}`

`="Min"{2,10/3,6}`

`=2 ("correspnds to " x_(B1)/y_(12))`

Thus, vector `A_1` is selected to leave the basis, for `r=1`

The table with new entries in column `y_2` and the minimum ratio

Basis Inverse `B_1^(-1)`Additional table
`B``X_B``beta_0`
`Z'`		`beta_1`
`A_1`		`beta_2`
`S_2`		`beta_3`
`x_3`		`y_2`
 		Min Ratio
`(X_B)/(y_2)`		`x_1``x_2``A_2``S_1`
`Z'``9M-3``1``-M``0``(M-1)/2``(-M+3)/2`---`3``2``M``0`
`A_1``1``0``1``0``-1/2``1/2``2``1``1``0``-1`
`S_2``5``0``0``1``1/2``3/2``10/3``0``1``0``0`
`x_3``3``0``0``0``1/2``1/2``6``1``1``1``0`


The table solution is now updated by replacing variable `A_1` with the variable `x_2` into the basis.

For this we apply the following row operations in the same way as in the simplex method
`X_B``beta_1``beta_2``beta_3``y_2`
`R_1``9M-3``-M``0``(M-1)/2``(-M+3)/2`
`R_2``1``1``0``-1/2``1/2`
`R_3``5``0``1``1/2``3/2`
`R_4``3``0``0``1/2``1/2`


`R_2`(new)`= R_2`(old) `xx2`
`R_2`(old) = `1``1``0``-1/2`
`R_2`(new)`= R_2`(old) `xx2``2``2``0``-1`


`R_1`(new)`= R_1`(old) + `((M-3)/2) R_2`(new)
`R_1`(old) = `9M-3``-M``0``(M-1)/2`
`R_2`(new) = `2``2``0``-1`
`(M-3)/2 xx R_2`(new) = `M-3``M-3``0``(-M+3)/2`
`R_1`(new)`= R_1`(old) + `((M-3)/2) R_2`(new)`10M-6``-3``0``1`


`R_3`(new)`= R_3`(old) - `3/2 R_2`(new)
`R_3`(old) = `5``0``1``1/2`
`R_2`(new) = `2``2``0``-1`
`3/2 xx R_2`(new) = `3``3``0``-3/2`
`R_3`(new)`= R_3`(old) - `3/2 R_2`(new)`2``-3``1``2`


`R_4`(new)`= R_4`(old) - `1/2 R_2`(new)
`R_4`(old) = `3``0``0``1/2`
`R_2`(new) = `2``2``0``-1`
`1/2 xx R_2`(new) = `1``1``0``-1/2`
`R_4`(new)`= R_4`(old) - `1/2 R_2`(new)`2``-1``0``1`


The improved solution is
Basis Inverse `B_1^(-1)`Additional table
`B``X_B``beta_0`
`Z'`		`beta_1`
`x_2`		`beta_2`
`S_2`		`beta_3`
`x_3`		`y_2`
 		Min Ratio
`(X_B)/(y_2)`		`x_1``A_1``A_2``S_1`
`Z'``10M-6``1``-3``0``1`---`3``M``M``0`
`x_2``2``0``2``0``-1`---`1``1``0``-1`
`S_2``2``0``-3``1``2`---`0``0``0``0`
`x_3``2``0``-1``0``1`---`1``0``1``0`


Iteration=3 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`

`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`

`="Min"{[[1,-3,0,1]] [[3,M,M,0],[1,1,0,-1],[0,0,0,0],[1,0,1,0]]}`

`="Min"{[[1,M-3,M+1,3]]}`

Since all `Z_j-C_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=0,x_2=2,x_3=2`

Max `Z=-6`

`:.` Min `Z=6`

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here


8. Standard form-2 using Big M method : Example-2
(Previous example)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2024. All rights reserved. Terms, Privacy
 
 

.