Optimization: Linear Programming & Simplex
Optimization: Linear Programming & Simplex
💡 Key Takeaways
- Model real problems by defining decision variables, an objective, and linear constraints.
- Solve with the simplex method, moving between feasible corner points to reach the optimum.
- Interpret the results: the optimal objective value, decision values, and what dual prices imply about resources.
- Handle standard forms and common LP cases: convert inequalities, check feasibility, boundedness, and degeneracy.
❓ Frequently Asked Questions
What is linear programming?
A method to maximize or minimize a linear objective function subject to linear constraints and nonnegativity. The feasible region is a convex polytope, and an optimal solution, if it exists, lies at a vertex.
What is the simplex method?
An algorithm that moves from one basic feasible solution (vertex) to an adjacent one by pivoting, improving the objective until no better move exists. It uses a tableau to update basic/nonbasic variables and reduced costs.
What is a basic feasible solution (BFS) and why is it important?
A BFS corresponds to a vertex of the feasible region. It is obtained by selecting a set of basic variables from the constraints (forming a full-rank basis) and setting the rest to zero. The optimum, when it exists, occurs at a BFS (or along an edge between BFSs).
What are reduced costs and the simplex optimality condition?
Reduced costs (c_j − z_j) indicate how much the objective would improve if a nonbasic variable j became basic. For a maximization problem, an optimal solution has all reduced costs ≤ 0; if any are positive, entering variables exist and the algorithm continues.