In this section, we will discuss some special cases of simplex method in linear programming (LP).

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 x_{1} is unrestricted in sign, then

Put x_{1} = x_{1}^{'} - x_{1}''

Maximize z = 2x_{1} + 3x_{2}

subject to

-x_{1} + 2x_{2} ≤
4

x_{1} + x_{2 }≤ 6

x_{1} + 3x_{2} ≤ 9

x_{1}, x_{2} are unrestricted in sign

Solution.

Since x_{1} and x_{2} are unrestricted in sign, we
can replace them by non-negative variables x_{1}^{'} , x_{1}'', x_{2}^{'} , x_{2}^{''} .

Put x_{1} = x_{1}^{'} - x_{1}''

x_{2} = x_{2}^{'} - x_{2}''

The given problem can be written as

Max. z = 2(x_{1}^{'} - x_{1}'') + 3(x_{2}^{'} - x_{2}'')

subject to

-(x_{1}^{'} - x_{1}'')_{} + 2(x_{2}^{'} - x_{2}'') ≤ 4

(x_{1}^{'} - x_{1}'') + (x_{2}^{'} - x_{2}'') ≤ 6

(x_{1}^{'} - x_{1}'')_{} + 3(x_{2}^{'} - x_{2}'') ≤ 9

Introducing slack variables

Max. z = 2x_{1}^{'} - 2x_{1}'' + 3x_{2}^{'} - 3x_{2}''

subject to

-x_{1}^{'} + x_{1}''_{} + 2x_{2}^{'} - 2x_{2}'' + x_{3} = 4

x_{1}^{'} - x_{1}'' + x_{2}^{'} - x_{2}'' + x_{4} = 6

x_{1}^{'} - x_{1}''_{} + 3x_{2}^{'} - 3x_{2}'' + x_{5} = 9

Where x_{3}, x_{4} and x_{5} are slack variables

c_{j} |
2 | -2 | 3 | -3 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1}^{'} |
x_{1}'' |
x_{2}^{'} |
x_{2}'' |
x_{3} |
x_{4} |
x_{5} |
Solution values b (=X _{B}) |

0 | x_{3} |
-1 | 1 | 2 | -2 | 1 | 0 | 0 | 4 |

0 | x_{4} |
1 | -1 | 1 | -1 | 0 | 1 | 0 | 6 |

0 | x_{5} |
1 | -1 | 3 | -3 | 0 | 0 | 1 | 9 |

z_{j}-c_{j} |
-2 | 2 | -3 | 3 | 0 | 0 | 0 |

Key column = x_{2}^{'} column.

Minimum (4/2, 6/1, 9/3) = 2

Key row = x_{3} row.

Pivot element =
2

x_{3} departs and x_{2}^{'} enters.

Table 2

c_{j} |
2 | -2 | 3 | -3 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1}^{'} |
x_{1}'' |
x_{2}^{'} |
x_{2}'' |
x_{3} |
x_{4} |
x_{5} |
Solution values b (=X _{B}) |

3 | x_{2}^{'} |
-1/2 | 1/2 | 1 | -1 | 1/2 | 0 | 0 | 2 |

0 | x_{4} |
3/2 | -3/2 | 0 | 0 | -1/2 | 1 | 0 | 4 |

0 | x_{5} |
5/2 | -5/2 | 0 | 0 | -3/2 | 0 | 1 | 3 |

z_{j}-c_{j} |
-7/2 | 7/2 | 0 | 0 | 3/2 | 0 | 0 |

Table 3

c_{j} |
2 | -2 | 3 | -3 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1}^{'} |
x_{1}'' |
x_{2}^{'} |
x_{2}'' |
x_{3} |
x_{4} |
x_{5} |
Solution values b (=X _{B}) |

3 | x_{2}^{'} |
0 | 0 | 1 | -1 | 1/5 | 0 | 1/5 | 13/5 |

0 | x_{4} |
0 | 0 | 0 | 0 | 2/5 | 1 | -3/5 | 11/5 |

2 | x_{1}^{'} |
1 | -1 | 0 | 0 | -3/5 | 0 | 2/5 | 6/5 |

z_{j}-c_{j} |
0 | 0 | 0 | 0 | -3/5 | 0 | 7/5 |

Table 4

c_{j} |
2 | -2 | 3 | -3 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1}^{'} |
x_{1}'' |
x_{2}^{'} |
x_{2}'' |
x_{3} |
x_{4} |
x_{5} |
Solution values b (=X _{B}) |

3 | x_{2}^{'} |
0 | 0 | 1 | -1 | 0 | -1/2 | 1/2 | 3/2 |

0 | x_{3} |
0 | 0 | 0 | 0 | 1 | 5/2 | -3/2 | 11/2 |

2 | x_{1}^{'} |
1 | -1 | 0 | 0 | 0 | 3/2 | -1/2 | 9/2 |

z_{j}-c_{j} |
0 | 0 | 0 | 0 | 0 | 3/2 | 1/2 |

The optimal solution is:

x_{1}^{'} = 9/2, x_{1}'' = 0, x_{2}^{'} = 3/2, x_{2}'' = 0.

Solution of the original problem is:

x_{1} = x_{1}^{'} - x_{1}'' = 9/2 -
0 = 9/2

x_{2} = x_{2}^{'} - x_{2}'' = 3/2 -
0 = 3/2

z = 2 X 9/2 + 3 X 3/2 = 27/2.