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.