Linear programming

Question

So far, we are using elementary row operations to solve for BFS. First describe an LP problem in standard form, and then explain how matrix inverse can be used to solve for BFS at any iteration. You need to specify how to create the matrix that you want to find the inverse of.

Answer 1

Hi Sarah,

Here's what you need to do:

Standard Form LP Problem:

An LP in standard form requires:

1. Maximization objective (min problems convert via -cᵀx)
2. Equality constraints (Ax = b)
3. Non-negative variables (x ≥ 0)
4. Example:
5. Maximize cᵀx
6. Subject to Ax = b
7. x ≥ 0

Matrix Inverse for BFS:

At any iteration, the basis matrix B consists of the columns of A corresponding to basic variables. The key steps:

1. Construct B: Select m linearly independent columns from A (where m = rank(A))
2. Compute B⁻¹: This gives the coefficients for the current basic variables
3. Calculate x B = B⁻¹b (current BFS)
4. Reduced costs: c N - c_BᵀB⁻¹N

Why This Matters for You:

1. Many students struggle with basis selection and inversion stability
2. My students learn:
3. • Pivot selection heuristics
4. • Numerical stability tricks (LU decomposition > explicit inverse)
5. • Phase I/II transition shortcuts

If you book a session with me this week you will receive:

✓ My LP Cheat Sheet (all standard forms + common pitfalls)

✓ MATLAB/Python code for stable B⁻¹ calculation

✓ Simplex Method flowchart (with basis tracking)