Simplex method calculator

SolutionHelp

Solution

Solution provided by AtoZmath.com

1. Find solution using simplex method.
Maximize Z = 3x1 + 5x2 + 4x3
subject to the constraints
2x1 + 3x2 ≤ 8
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15
and x1, x2, x3 ≥ 0

2. Find solution using BigM (penalty) method.
Minimize Z = 5x1 + 3x2
subject to the constraints
2x1 + 4x2 ≤ 12
2x1 + 2x2 = 10
5x1 + 2x2 ≥ 10
and x1, x2 ≥ 0

Example

1. Find solution using Simplex method
MAX Z = 3x1 + 5x2 + 4x3
subject to
2x1 + 3x2 <= 8
2x2 + 5x3 <= 10
3x1 + 2x2 + 4x3 <= 15
and x1,x2,x3 >= 0

Solution:
Problem is

Max `Z`

`=`

`3`

`x_1`

` + `

`5`

`x_2`

` + `

`4`

`x_3`

subject to

``	`2`	`x_1`	` + `	`3`	`x_2`				≤	`8`
			``	`2`	`x_2`	` + `	`5`	`x_3`	≤	`10`
``	`3`	`x_1`	` + `	`2`	`x_2`	` + `	`4`	`x_3`	≤	`15`

and `x_1,x_2,x_3 >= 0; `

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

1. As the constraint-1 is of type '`<=`' we should add slack variable `S_1`

2. As the constraint-2 is of type '`<=`' we should add slack variable `S_2`

3. As the constraint-3 is of type '`<=`' we should add slack variable `S_3`

After introducing slack variables

Max `Z`

`=`

`3`

`x_1`

` + `

`5`

`x_2`

` + `

`4`

`x_3`

` + `

`0`

`S_1`

` + `

`0`

`S_2`

` + `

`0`

`S_3`

subject to

`2`

`x_1`

` + `

`3`

`x_2`

` + `

`S_1`

`8`

`2`

`x_2`

` + `

`5`

`x_3`

` + `

`S_2`

`10`

`3`

`x_1`

` + `

`2`

`x_2`

` + `

`4`

`x_3`

` + `

`S_3`

`15`

and `x_1,x_2,x_3,S_1,S_2,S_3 >= 0`

Iteration-1		`C_j`	`3`	`5`	`4`	`0`	`0`	`0`
`B`	`C_B`	`X_B`	`x_1`	`x_2` Entering variable	`x_3`	`S_1`	`S_2`	`S_3`	MinRatio `(X_B)/(x_2)`
`S_1` Leaving variable	`0`	`8`	`2`	`(3)` (pivot element)	`0`	`1`	`0`	`0`	`(8)/(3)=2.67``->`
`S_2`	`0`	`10`	`0`	`2`	`5`	`0`	`1`	`0`	`(10)/(2)=5`
`S_3`	`0`	`15`	`3`	`2`	`4`	`0`	`0`	`1`	`(15)/(2)=7.5`
`Z=0` `0=` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`0` `0=0xx2+0xx0+0xx3` `Z_j=sum C_B x_1`	`0` `0=0xx3+0xx2+0xx2` `Z_j=sum C_B x_2`	`0` `0=0xx0+0xx5+0xx4` `Z_j=sum C_B x_3`	`0` `0=0xx1+0xx0+0xx0` `Z_j=sum C_B S_1`	`0` `0=0xx0+0xx1+0xx0` `Z_j=sum C_B S_2`	`0` `0=0xx0+0xx0+0xx1` `Z_j=sum C_B S_3`
		`C_j-Z_j`	`3` `3=3-0`	`5` `5=5-0``uarr`	`4` `4=4-0`	`0` `0=0-0`	`0` `0=0-0`	`0` `0=0-0`

Positive maximum `C_j-Z_j` is `5` and its column index is `2`. So, the entering variable is `x_2`.

Minimum ratio is `2.67` and its row index is `1`. So, the leaving basis variable is `S_1`.

`:.` The pivot element is `3`.

Entering `=x_2`, Departing `=S_1`, Key Element `=3`

`R_1`(new)`= R_1`(old)`-: 3`

`R_2`(new)`= R_2`(old)`- 2 R_1`(new)

`R_3`(new)`= R_3`(old)`- 2 R_1`(new)

Iteration-2		`C_j`	`3`	`5`	`4`	`0`	`0`	`0`
`B`	`C_B`	`X_B`	`x_1`	`x_2`	`x_3` Entering variable	`S_1`	`S_2`	`S_3`	MinRatio `(X_B)/(x_3)`
`x_2`	`5`	`8/3` `8/3=8-:3` `R_1`(new)`= R_1`(old)`-: 3`	`2/3` `2/3=2-:3` `R_1`(new)`= R_1`(old)`-: 3`	`1` `1=3-:3` `R_1`(new)`= R_1`(old)`-: 3`	`0` `0=0-:3` `R_1`(new)`= R_1`(old)`-: 3`	`1/3` `1/3=1-:3` `R_1`(new)`= R_1`(old)`-: 3`	`0` `0=0-:3` `R_1`(new)`= R_1`(old)`-: 3`	`0` `0=0-:3` `R_1`(new)`= R_1`(old)`-: 3`	---
`S_2` Leaving variable	`0`	`14/3` `14/3=10-2xx8/3` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`-4/3` `-4/3=0-2xx2/3` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`0` `0=2-2xx1` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`(5)` `5=5-2xx0` (pivot element) `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`-2/3` `-2/3=0-2xx1/3` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`1` `1=1-2xx0` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`0` `0=0-2xx0` `R_2`(new)`= R_2`(old)`- 2 R_1`(new)	`(14/3)/(5)=0.93``->`
`S_3`	`0`	`29/3` `29/3=15-2xx8/3` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`5/3` `5/3=3-2xx2/3` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`0` `0=2-2xx1` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`4` `4=4-2xx0` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`-2/3` `-2/3=0-2xx1/3` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`0` `0=0-2xx0` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`1` `1=1-2xx0` `R_3`(new)`= R_3`(old)`- 2 R_1`(new)	`(29/3)/(4)=2.42`
`Z=40/3` `40/3=5xx8/3` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`10/3` `10/3=5xx2/3+0xx(-4/3)+0xx5/3` `Z_j=sum C_B x_1`	`5` `5=5xx1+0xx0+0xx0` `Z_j=sum C_B x_2`	`0` `0=5xx0+0xx5+0xx4` `Z_j=sum C_B x_3`	`5/3` `5/3=5xx1/3+0xx(-2/3)+0xx(-2/3)` `Z_j=sum C_B S_1`	`0` `0=5xx0+0xx1+0xx0` `Z_j=sum C_B S_2`	`0` `0=5xx0+0xx0+0xx1` `Z_j=sum C_B S_3`
		`C_j-Z_j`	`-1/3` `-1/3=3-10/3`	`0` `0=5-5`	`4` `4=4-0``uarr`	`-5/3` `-5/3=0-5/3`	`0` `0=0-0`	`0` `0=0-0`

Positive maximum `C_j-Z_j` is `4` and its column index is `3`. So, the entering variable is `x_3`.

Minimum ratio is `0.93` and its row index is `2`. So, the leaving basis variable is `S_2`.

`:.` The pivot element is `5`.

Entering `=x_3`, Departing `=S_2`, Key Element `=5`

`R_2`(new)`= R_2`(old)`-: 5`

`R_1`(new)`= R_1`(old)

`R_3`(new)`= R_3`(old)`- 4 R_2`(new)

Iteration-3		`C_j`	`3`	`5`	`4`	`0`	`0`	`0`
`B`	`C_B`	`X_B`	`x_1` Entering variable	`x_2`	`x_3`	`S_1`	`S_2`	`S_3`	MinRatio `(X_B)/(x_1)`
`x_2`	`5`	`8/3` `8/3=8/3` `R_1`(new)`= R_1`(old)	`2/3` `2/3=2/3` `R_1`(new)`= R_1`(old)	`1` `1=1` `R_1`(new)`= R_1`(old)	`0` `0=0` `R_1`(new)`= R_1`(old)	`1/3` `1/3=1/3` `R_1`(new)`= R_1`(old)	`0` `0=0` `R_1`(new)`= R_1`(old)	`0` `0=0` `R_1`(new)`= R_1`(old)	`(8/3)/(2/3)=4`
`x_3`	`4`	`14/15` `14/15=14/3-:5` `R_2`(new)`= R_2`(old)`-: 5`	`-4/15` `-4/15=(-4/3)-:5` `R_2`(new)`= R_2`(old)`-: 5`	`0` `0=0-:5` `R_2`(new)`= R_2`(old)`-: 5`	`1` `1=5-:5` `R_2`(new)`= R_2`(old)`-: 5`	`-2/15` `-2/15=(-2/3)-:5` `R_2`(new)`= R_2`(old)`-: 5`	`1/5` `1/5=1-:5` `R_2`(new)`= R_2`(old)`-: 5`	`0` `0=0-:5` `R_2`(new)`= R_2`(old)`-: 5`	---
`S_3` Leaving variable	`0`	`89/15` `89/15=29/3-4xx14/15` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`(41/15)` `41/15=5/3-4xx(-4/15)` (pivot element) `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`0` `0=0-4xx0` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`0` `0=4-4xx1` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`-2/15` `-2/15=(-2/3)-4xx(-2/15)` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`-4/5` `-4/5=0-4xx1/5` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`1` `1=1-4xx0` `R_3`(new)`= R_3`(old)`- 4 R_2`(new)	`(89/15)/(41/15)=2.17``->`
`Z=256/15` `256/15=5xx8/3+4xx14/15` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`34/15` `34/15=5xx2/3+4xx(-4/15)+0xx41/15` `Z_j=sum C_B x_1`	`5` `5=5xx1+4xx0+0xx0` `Z_j=sum C_B x_2`	`4` `4=5xx0+4xx1+0xx0` `Z_j=sum C_B x_3`	`17/15` `17/15=5xx1/3+4xx(-2/15)+0xx(-2/15)` `Z_j=sum C_B S_1`	`4/5` `4/5=5xx0+4xx1/5+0xx(-4/5)` `Z_j=sum C_B S_2`	`0` `0=5xx0+4xx0+0xx1` `Z_j=sum C_B S_3`
		`C_j-Z_j`	`11/15` `11/15=3-34/15``uarr`	`0` `0=5-5`	`0` `0=4-4`	`-17/15` `-17/15=0-17/15`	`-4/5` `-4/5=0-4/5`	`0` `0=0-0`

Positive maximum `C_j-Z_j` is `11/15` and its column index is `1`. So, the entering variable is `x_1`.

Minimum ratio is `2.17` and its row index is `3`. So, the leaving basis variable is `S_3`.

`:.` The pivot element is `41/15`.

Entering `=x_1`, Departing `=S_3`, Key Element `=41/15`

`R_3`(new)`= R_3`(old)`xx15/41`

`R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)

`R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)

Iteration-4		`C_j`	`3`	`5`	`4`	`0`	`0`	`0`
`B`	`C_B`	`X_B`	`x_1`	`x_2`	`x_3`	`S_1`	`S_2`	`S_3`	MinRatio
`x_2`	`5`	`50/41` `50/41=8/3-2/3xx89/41` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`0` `0=2/3-2/3xx1` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`1` `1=1-2/3xx0` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`0` `0=0-2/3xx0` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`15/41` `15/41=1/3-2/3xx(-2/41)` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`8/41` `8/41=0-2/3xx(-12/41)` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)	`-10/41` `-10/41=0-2/3xx15/41` `R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)
`x_3`	`4`	`62/41` `62/41=14/15+4/15xx89/41` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`0` `0=(-4/15)+4/15xx1` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`0` `0=0+4/15xx0` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`1` `1=1+4/15xx0` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`-6/41` `-6/41=(-2/15)+4/15xx(-2/41)` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`5/41` `5/41=1/5+4/15xx(-12/41)` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)	`4/41` `4/41=0+4/15xx15/41` `R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)
`x_1`	`3`	`89/41` `89/41=89/15xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`1` `1=41/15xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`0` `0=0xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`0` `0=0xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`-2/41` `-2/41=(-2/15)xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`-12/41` `-12/41=(-4/5)xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`	`15/41` `15/41=1xx15/41` `R_3`(new)`= R_3`(old)`xx15/41`
`Z=765/41` `765/41=5xx50/41+4xx62/41+3xx89/41` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`3` `3=5xx0+4xx0+3xx1` `Z_j=sum C_B x_1`	`5` `5=5xx1+4xx0+3xx0` `Z_j=sum C_B x_2`	`4` `4=5xx0+4xx1+3xx0` `Z_j=sum C_B x_3`	`45/41` `45/41=5xx15/41+4xx(-6/41)+3xx(-2/41)` `Z_j=sum C_B S_1`	`24/41` `24/41=5xx8/41+4xx5/41+3xx(-12/41)` `Z_j=sum C_B S_2`	`11/41` `11/41=5xx(-10/41)+4xx4/41+3xx15/41` `Z_j=sum C_B S_3`
		`C_j-Z_j`	`0` `0=3-3`	`0` `0=5-5`	`0` `0=4-4`	`-45/41` `-45/41=0-45/41`	`-24/41` `-24/41=0-24/41`	`-11/41` `-11/41=0-11/41`

Since all `C_j-Z_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=89/41,x_2=50/41,x_3=62/41`

Max `Z = 765/41`