## Linear Optimization: The Simplex WorkbookThe Subject A little explanation is in order for our choice of the title Linear Opti- 1 mization (and corresponding terminology) for what has traditionally been called Linear Programming.Theword programming in this context can be confusing and/or misleading to students. Linear programming problems are referred to as optimization problems but the general term linear p- gramming remains. This can cause people unfamiliar with the subject to think that it is about programming in the sense of writing computer code. It isn’t. This workbook is about the beautiful mathematics underlying the ideas of optimizing linear functions subject to linear constraints and the algorithms to solve such problems. In particular, much of what we d- cuss is the mathematics of Simplex Algorithm for solving such problems, developed by George Dantzig in the late 1940s. The word program in linear programming is a historical artifact. When Dantzig ?rstdevelopedthe Simplex Algorithm to solvewhat arenowcalled linear programming problems, his initial model was a class of resource - location problems to be solved for the U.S. Air Force. The decisions about theallocationswerecalled‘Programs’bytheAirForce,andhencetheterm. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

2 The Simplex Algorithm | 29 |

3 Geometry | 58 |

4 The Duality Theorem | 73 |

5 Matrix Environment | 89 |

6 General Form | 106 |

7 Unsolvable Systems | 119 |

8 Geometry Revisited | 129 |

11 Combinatorics | 182 |

12 Economics | 195 |

13 Integer Optimization | 209 |

A Linear Algebra Review | 231 |

B Equivalence of Auxiliaryand Shortcut Methods | 235 |

C Complexity | 241 |

D Software | 246 |

257 | |

### Other editions - View all

### Common terms and phrases

acres ai,j Algorithm to solve AugMat Auxiliary Barbie Barbie’s basic variable basis bipartite graph Branch-and-Bound Algorithm certificate Chapter column Compute conic Consider the following convex combination corresponding cost Cutting Plane Algorithm define doubly stochastic matrix dual LOP entry Euler tour example extreme points feasible region Find floptimal following LOP free variables G. H. Hurlbert GLOP HINT ILOP inequalities infeasible integer Ken’s least subscript leaving variable Lemma Linear Optimization linear problem MAPLE matching maximization Media LLC 2010 negative node objective function objective row optimal solution optimal strategies optimum payoff matrix permutation permutation matrices Phase pivot operation player polyhedron polynomial polytope primal proof pseudocode resp result row operations Science+Business Media LLC Shortcut Method Simplex Algorithm slack variables solve the following spanning tree Springer Science+Business Media standard form tableau vectors Verify Theorem vertices vhull(X vspan(X WebSim Workout Write