Linear Programming

Why it matters

Linear Programming (LP) is crucial in industrial engineering as it helps in optimizing resource allocation, minimizing costs, and maximizing profits. It is widely used in various industries for decision-making processes, such as production planning, transportation, and scheduling.

Key ideas

• Objective Function: The function that needs to be maximized or minimized, representing the goal of the LP problem.
• Constraints: These are the restrictions or limitations on the decision variables, usually expressed as linear inequalities or equations.
• Feasible Region: The set of all possible points that satisfy the constraints, representing all potential solutions.
• Optimal Solution: The point within the feasible region that optimizes the objective function.
• Simplex Method: A popular algorithm used to solve LP problems by moving along the edges of the feasible region to find the optimal solution.
• Duality: Every LP problem has a corresponding dual problem, which provides insights into the properties of the original problem.

Formulas

• Objective Function: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
  • Z: Objective function value (unit depends on context)
  • c₁, c₂, ..., cₙ: Coefficients of the decision variables
  • x₁, x₂, ..., xₙ: Decision variables
• Constraints: a₁x₁ + a₂x₂ + ... + aₙxₙ ≤ b
  • a₁, a₂, ..., aₙ: Coefficients of the decision variables
  • b: Right-hand side constant (unit depends on context)

Basic LP assumes a linear objective, linear constraints and continuous decision variables. Integer requirements need an integer model; rounding an LP result need not preserve feasibility or optimality. Problems may be infeasible, unbounded or have multiple optima. In this bounded two-variable example, checking all feasible vertices establishes the optimum.

Worked example

Problem: Maximize Z = 3x₁ + 2x₂ subject to constraints:

1. x₁ + x₂ ≤ 4
2. x₁ ≤ 2
3. x₂ ≤ 3
4. x₁, x₂ ≥ 0

Solution:

1. Identify the feasible region by plotting the constraints on a graph.
2. Determine the corner points of the feasible region.
3. Evaluate the objective function at each corner point.
4. Select the point that gives the maximum value of Z.

Calculation:

• Corner points: (0,0), (2,0), (2,2), (1,3), (0,3)
• Evaluate Z:
  • At (0,0): Z = 3(0) + 2(0) = 0
  • At (2,0): Z = 3(2) + 2(0) = 6
  • At (0,3): Z = 3(0) + 2(3) = 6
  • At (1,3): Z = 3(1) + 2(3) = 9
  • At (2,2): Z = 3(2) + 2(2) = 10

Optimal Solution: Z = 10 at (2,2)

Common mistakes

• Misidentifying the feasible region by incorrectly plotting constraints.
• Ignoring non-negativity constraints on decision variables.
• Failing to evaluate the objective function at all corner points.

For GATE ME

Questions on linear programming often involve formulating the LP problem, identifying the feasible region, and finding the optimal solution using graphical or simplex methods. Practice solving problems with different constraints and objective functions to gain proficiency.

Quick check

1. What is the objective function in linear programming?
2. How do you identify the feasible region?
3. What is the role of the simplex method?

Answers: 1. The function to be maximized or minimized. 2. By plotting the constraints on a graph. 3. To find the optimal solution by moving along the edges of the feasible region.