## Simplex Algorithm

### Input

pivot search: most negative

algorithm: default

max f(x) = 3 x_{1} + 5 x_{2} + 4 x_{3}

R_{1}: 2 x_{1} + 3 x_{2} + 0 x_{3} ≤ 8

R_{2}: 0 x_{1} + 2 x_{2} + 5 x_{3} ≤ 10

R_{3}: 3 x_{1} + 2 x_{2} + 4 x_{3} ≤ 15

x_{1}, x_{2}, x_{3} ∈ ℚ

### Initial Table

x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | x_{6} | b | ||
---|---|---|---|---|---|---|---|---|

z | -3 | -5 | -4 | 0 | 0 | 0 | 0 | |

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

x_{5} | 0 | 2 | 5 | 0 | 1 | 0 | 10 | 5 |

x_{6} | 3 | 2 | 4 | 0 | 0 | 1 | 15 | 15/2 |

R_{x4} / 3 → R_{x2}

R_{x5} + (-2/3) · R_{x4} → R_{x5}

R_{x6} + (-2/3) · R_{x4} → R_{x6}

### Iteration 1

x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | x_{6} | b | ||
---|---|---|---|---|---|---|---|---|

z | 1/3 | 0 | -4 | 5/3 | 0 | 0 | 40/3 | |

x_{2} | 2/3 | 1 | 0 | 1/3 | 0 | 0 | 8/3 | inf |

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

x_{6} | 5/3 | 0 | 4 | -2/3 | 0 | 1 | 29/3 | 29/12 |

R_{x2} + 0 · R_{x5} → R_{x2}

R_{x5} / 5 → R_{x3}

R_{x6} + (-4/5) · R_{x5} → R_{x6}

### Iteration 2

x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | x_{6} | b | ||
---|---|---|---|---|---|---|---|---|

z | -11/15 | 0 | 0 | 17/15 | 4/5 | 0 | 256/15 | |

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

x_{3} | -4/15 | 0 | 1 | -2/15 | 1/5 | 0 | 14/15 | inf |

x_{6} | 41/15 | 0 | 0 | -2/15 | -4/5 | 1 | 89/15 | 89/41 |

R_{x2} + (-10/41) · R_{x6} → R_{x2}

R_{x3} + 4/41 · R_{x6} → R_{x3}

R_{x6} / 41/15 → R_{x1}

### Iteration 3

x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | x_{6} | b | |
---|---|---|---|---|---|---|---|

z | 0 | 0 | 0 | 45/41 | 24/41 | 11/41 | 765/41 |

x_{2} | 0 | 1 | 0 | 15/41 | 8/41 | -10/41 | 50/41 |

x_{3} | 0 | 0 | 1 | -6/41 | 5/41 | 4/41 | 62/41 |

x_{1} | 1 | 0 | 0 | -2/41 | -12/41 | 15/41 | 89/41 |

### Solution

f(x*) | 765/41 |

x*_{1} | 89/41 |

x*_{2} | 50/41 |

x*_{3} | 62/41 |

x*_{4} | 0 |

x*_{5} | 0 |

x*_{6} | 0 |

### Maximum

Cap | Δf(x) | Δx_{1} | Δx_{2} | Δx_{3} | |
---|---|---|---|---|---|

R_{1} | 45/41 | 45/41 | -2/41 | 15/41 | -6/41 |

R_{2} | 24/41 | 24/41 | -12/41 | 8/41 | 5/41 |

R_{3} | 11/41 | 11/41 | 15/41 | -10/41 | 4/41 |

### Minimum

Floor | Δf(x) | Δx_{1} | Δx_{2} | Δx_{3} | |
---|---|---|---|---|---|

x_{1} | 0 | 0 | 0 | 0 | 0 |

x_{2} | 0 | 0 | 0 | 0 | 0 |

x_{3} | 0 | 0 | 0 | 0 | 0 |

### Economic Interpretation

**89/41** item **x _{1}**,

**50/41**item

**x**, and

_{2}**62/41**item

**x**should be produced and sold to achieve a value of

_{3}**18.66**monetary units.

For an additional unit of **x _{4}**, a maximum of

**1.10**monetary units should be spent. This increases the amount of

**x**items produced by

_{1}**-2/41**units,

**x**items produced by

_{2}**15/41**units, and

**x**items produced by

_{3}**-6/41**units.

For an additional unit of **x _{5}**, a maximum of

**0.59**monetary units should be spent. This increases the amount of

**x**items produced by

_{1}**-12/41**units,

**x**items produced by

_{2}**8/41**units, and

**x**items produced by

_{3}**5/41**units.

For an additional unit of **x _{6}**, a maximum of

**0.27**monetary units should be spent. This increases the amount of

**x**items produced by

_{1}**15/41**units,

**x**items produced by

_{2}**-10/41**units, and

**x**items produced by

_{3}**4/41**units.

No additional units of **x _{1}** should be produced and sold.

No additional units of **x _{2}** should be produced and sold.

No additional units of **x _{3}** should be produced and sold.