Linear Programming Overview

Key Concepts

• Linear programming (LP) is a mathematical technique for maximizing or minimizing a linear objective function, subject to linear inequalities (constraints).
• Applications include economics, logistics, and resource allocation.

Example Problem: Farmer's Crops

• Resources: 3 tons of potato seeds, 4 tons of carrot seeds, and 5 tons of fertilizer.
• Profit per kg: 1.2$ for potatoes and 1.7$ for carrots.
• Objective: Maximize profit by determining how much of each crop to plant.

Formalization of the Problem

• Variables:
  • Let x_p = amount of potatoes planted (in kg)
  • Let x_c = amount of carrots planted (in kg)
• Constraints:
  1. x_p <= 3000 (3 tons of potatoes)
  2. x_c <= 4000 (4 tons of carrots)
  3. x_p + x_c <= 5000 (5 tons of fertilizer)
• Objective Function:
  Maximize Profit = 1.2*x_p + 1.7*x_c

Geometric Interpretation

• The feasible region is defined by the intersection of half-planes created by the inequalities.
• The objective function is also a linear function, which indicates a direction of increase.
• The optimal solution occurs at the last intersection point reached when moving in the direction of maximum profit.

Solution

• Optimal planting: 1000 kg of potatoes and 4000 kg of carrots yields a profit of $8000.

Simplex Method

• An algorithmic approach to solving linear programs.
• Pivoting: Move from vertex to vertex in the feasible region, always moving toward increasing profit until no further improvement is possible.
• George B. Dantzig: Inventor of the simplex algorithm, known for solving two unsolved problems by mistake.

Steps of the Simplex Method

1. Identify tight and loose variables (tight = non-basic, loose = basic).
2. Loosen one variable using Dantzig’s pivot rule (largest positive coefficient).
3. Tighten another variable using the ratio of constants to maintain validity.
4. Update equalities and the objective function.
5. Repeat the process until no positive coefficients remain in the objective function.

Dual Linear Programming

• The concept of duality in LP:
  • Weak Duality Theorem: Solutions to the primal LP are always less than or equal to solutions of the dual LP.
  • Strong Duality Theorem: If the primal has an optimum, the dual will provide a proof of optimality.

Integer Linear Programming (ILP)

• Some problems require integer solutions (e.g., planting whole trees).
• The Knapsack Problem: An NP-hard problem framed as an ILP.
  • Goal: Maximize price without exceeding weight limit using binary decision variables for items.

Implementation Example

• Using the pulp Python package to solve linear programs efficiently.
• Example solutions provided for both the farmer’s problem and the knapsack problem.

Conclusion

• Covered key topics in linear programming: simplex method, duality, and integer linear programming.
• Future topics may include deeper nuances of each concept and potential polynomial-time solutions for certain classes of problems.