**Example 1:** Consider the following simplex tableau:

x_1 | x_2 | x_3 | s_1 | s_2 | s_3 | |
---|---|---|---|---|---|---|

-2 | 1 | 4 | 1/2 | 0 | 0 | 24 |

3 | 0 | 3 | -3/2 | 1 | 0 | 9 |

2 | 0 | -1 | -1 | 0 | 1 | 8 |

-4 | 0 | -5 | 3 | 0 | 0 | 64 |

The basic feasible solution corresponding to this tableau is

x_1 = 0, x_2 = 24, x_3=0, s_1 = 0, s_2 = 9, s_3 = 8.If x_1 is made a basic variable, the replacement quantities are

9/3 = 3, 8/2 = 4.Note that only a row having a positive entry in the column of the entering variable will produce a replacement quantity.

The 3 in row 2 column 1 will be the pivot. The next tableau is

x_1 | x_2 | x_3 | s_1 | s_2 | s_3 | |
---|---|---|---|---|---|---|

0 | 1 | 6 | -1/2 | 2/3 | 0 | 30 |

1 | 0 | 1 | -1/2 | 1/3 | 0 | 3 |

0 | 0 | -3 | 1/2 | -2/3 | 1 | 2 |

0 | 0 | -1 | 1 | 4/3 | 0 | 76 |

The solution is not optimal because one entry in the objective row is negative.

**Example 2 (Degenerate linear program): **A solution to linear program is said to be degenerate if one of the basic variables is 0.

Maximize: 50x_1 + 40x_2 ; Subject to: 3x_1 + 2x_2 \le 120, x_1 + 6x_2 \le 120, 2x_1 + x_2 \le 80, x_1 \ge 0, x_2 \ge 0.

The simplex tableau is

x_1 | x_2 | s_1 | s_2 | s_3 | |
---|---|---|---|---|---|

3 | 2 | 1 | 0 | 0 | 120 |

1 | 6 | 0 | 1 | 0 | 120 |

2 | 1 | 0 | 0 | 1 | 80 |

-50 | -40 | 0 | 0 | 0 | 0 |

Choose x_1 as the entering variable, the replacement quantities are

120/3 = 40, 120/1 = 120, 80/2 = 40.Entry 3 in row 1 column 1 will the pivot. The next tableau is

x_1 | x_2 | s_1 | s_2 | s_3 | |
---|---|---|---|---|---|

1 | 2/3 | 1/3 | 0 | 0 | 40 |

0 | 16/3 | -1/3 | 1 | 0 | 80 |

0 | -1/3 | -2/3 | 0 | 1 | 0 |

0 | -20/3 | 50/3 | 0 | 0 | 2000 |

Since a basic variable s_3 = 0, the basic solution is degenerate.

Choose x_2 as the entering variable, the replacement quantities are

40/(2/3) = 60, 80/(16/3) = 15.Entry 16/3 in row 2 column 2 will be the pivot. The next tableau is

x_1 | x_2 | s_1 | s_2 | s_3 | |
---|---|---|---|---|---|

1 | 0 | 3/8 | -1/8 | 0 | 30 |

0 | 1 | -1/16 | 3/16 | 0 | 15 |

0 | 0 | -11/16 | 1/16 | 1 | 5 |

0 | 0 | 65/4 | 5/4 | 0 | 2100 |

The basic solution x_1 = 30, x_2 = 15, s_1 = 0, s_2 = 0, s_3 = 5 is optimal and unique.