Linear Programming

1. Definition • Linear Programming (LP) is the optimization of a linear objective function, subject to a set of linear equality and/or inequality constraints. • Standard form: maximize cᵀx subject to Ax ≤ b, x ≥ 0 where x ∈ ℝⁿ, A ∈ ℝᵐ×ⁿ, b ∈ ℝᵐ, c ∈ ℝⁿ. 2. Key Concepts • Feasible Region: The convex polyhedron defined by the constraints. • Extreme Points: Vertices of the feasible region; an optimal solution (if it exists) occurs at one of these. • Basic Feasible Solution: A corner (basis) with exactly n active constraints (in standard form). 3. Solution Methods • Simplex Algorithm (Dantzig, 1947): Traverses extreme points via pivot operations until optimality. • Interior‐Point Methods (Karmarkar, 1984): Moves through the interior of the feasible region; often polynomial‐time. • Duality: Every LP (“primal”) has a dual; optimal values coincide under mild conditions (strong duality). 4. Duality Theory • Primal (max cᵀx; Ax ≤ b) ↔ Dual (min bᵀy; Aᵀy ≥ c, y ≥ 0). • Economic interpretation: Dual variables y represent shadow prices of resources. • Complementary Slackness: Characterizes optimality via xi·(Aᵀy–ci)=0 and yj·(bj–(Ax)j)=0. 5. Applications • Resource allocation (manufacturing, transportation) • Portfolio optimization in finance • Network flows and scheduling References • G. B. Dantzig, “Linear Programming and Extensions,” Princeton Univ. Press, 1963. • V. Chvátal, “Linear Programming,” W. H. Freeman, 1983.

1. Understand and Define • Read the word problem carefully. Identify the decision variables x₁,…,xₙ (what you control). • Decide what you want to maximize or minimize (profit, cost, time, etc.). 2. Formulate Mathematically • Write the objective function in the form cᵀx (e.g. maximize 5x₁+3x₂). • Translate every requirement into a linear constraint (≤, ≥ or =). • Add nonnegativity constraints xᵢ ≥ 0 unless variables can be negative. 3. Convert to Standard Form (if using Simplex) • Change “≥” constraints by multiplying by –1, and convert equalities into two inequalities. • Introduce slack (or surplus and artificial) variables so all constraints read “=.” 4. Solve by Hand (small n) or Software A. Graphical Method (n=2) – Plot each constraint line in the x₁–x₂ plane. – Shade the feasible region, find its vertices, and evaluate the objective at each. B. Simplex Algorithm – Set up the initial tableau. – Pivot to drive all reduced costs (objective‐row entries) nonnegative (for maximization). – Read off the optimal solution when no further improvements are possible. C. Interior‐Point or Solver – Use Excel Solver, Python + PuLP/CVXOPT, MATLAB linprog, or other LP packages for large problems. 5. Interpret and Verify • Check that your solution satisfies all original constraints. • Use dual variables (shadow prices) to assess sensitivity: how much the objective would change if b changes. • Apply complementary slackness to confirm optimality. 6. Practice and Resources • Work through examples in: – G. B. Dantzig, “Linear Programming and Extensions” (1963) – V. Chvátal, “Linear Programming” (1983) • Try online problem sets (e.g. NEOS Server, MIT OpenCourseWare). • Implement small models in Python/PuLP to build fluency.

Problem. A workshop makes chairs (x₁) and tables (x₂). Profit per chair = \$3, per table = \$5. Available labor: 1 hr per chair, 2 hrs per table, total ≤ 8 hrs. Available wood: 3 hr per chair, 2 hr per table, total ≤ 12 hrs. Maximize profit Z = 3x₁ + 5x₂ Subject to  1) x₁ + 2x₂ ≤ 8  2) 3x₁ + 2x₂ ≤ 12  3) x₁, x₂ ≥ 0 Step 1: Identify corner points. Solve the equalities pairwise: • Intersection of (1) and (2):  x₁ + 2x₂ = 8  3x₁ + 2x₂ = 12 Subtract: 2x₁ = 4 ⇒ x₁ = 2; then x₂ = (8–2)/2 = 3. • With x₁ = 0: from (1) x₂ = 4; from (2) x₂ = 6 ⇒ active is the tighter x₂ = 4. • With x₂ = 0: from (1) x₁ = 8; from (2) x₁ = 4 ⇒ active is x₁ = 4. Thus corners: (0,0), (0,4), (2,3), (4,0). Step 2: Evaluate Z at each corner. • (0,0): Z = 0 • (0,4): Z = 3·0 + 5·4 = 20 • (2,3): Z = 3·2 + 5·3 = 6 + 15 = 21 • (4,0): Z = 3·4 + 5·0 = 12 Step 3: Choose the maximum. Maximum profit Z* = 21 at x₁ = 2 chairs and x₂ = 3 tables. Verification: Constraints: 1) 2 + 2·3 = 8 ≤ 8 ✔ 2) 3·2 + 2·3 = 12 ≤ 12 ✔ Conclusion. Produce 2 chairs and 3 tables for a maximal profit of \$21. Reference for method: • G. B. Dantzig, “Linear Programming and Extensions,” 1963.