Linear Programming

Linear Programming is a mathematical method used in industrial engineering to optimize resource allocation and decision-making processes.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

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.

Explore Linear Programming

Adjust the sliders to change the coefficients of the objective function and constraints. Observe how the feasible region and optimal solution change.

Equations used
  • Z = c₁x₁ + c₂x₂ — Z is the objective function value
  • a₁x₁ + a₂x₂ ≤ b — Linear constraint
  • Feasible Region — Set of all points satisfying constraints

Try answering each one aloud before you open it.

  1. 1.What is linear programming in the context of industrial engineering?Concept

    Linear programming is a mathematical method used in industrial engineering to optimize a linear objective function, subject to a set of linear equality and inequality constraints. It is widely used for resource allocation, production scheduling, and other decision-making processes where the goal is to maximize or minimize a particular quantity.

  2. 2.Explain the concept of the feasible region in linear programming.Concept

    The feasible region in linear programming is the set of all possible points that satisfy the given constraints of a linear programming problem. It is typically represented as a convex polyhedron in a graphical method, where each point within this region is a potential solution to the problem.

  3. 3.What is the role of the objective function in linear programming?Concept

    The objective function in linear programming is a mathematical expression that defines the goal of the optimization problem, such as maximizing profit or minimizing cost. It is a linear function of the decision variables and is subject to the constraints of the problem. The solution to the linear programming problem is the point in the feasible region that optimizes this objective function.

  4. 4.Why is the simplex method used in solving linear programming problems?Application

    The simplex method is used in solving linear programming problems because it is an efficient algorithm that systematically examines the vertices of the feasible region to find the optimal solution. It is particularly effective for large-scale problems and provides a clear path to the optimal solution by moving along the edges of the feasible region.

  5. 5.What happens if a linear programming problem has no feasible solution?Application

    If a linear programming problem has no feasible solution, it means that there is no point that satisfies all the constraints simultaneously. This situation can occur if the constraints are contradictory or overly restrictive, and it indicates that the problem needs to be reformulated or the constraints need to be relaxed.

  6. 6.How does sensitivity analysis apply to linear programming?Application

    Sensitivity analysis in linear programming examines how the changes in the coefficients of the objective function or the right-hand side of the constraints affect the optimal solution. It helps in understanding the robustness of the solution and in making informed decisions when there are uncertainties in the parameters.

  7. 7.What is the difference between a bounded and an unbounded solution in linear programming?Concept

    A bounded solution in linear programming means that the feasible region is closed and the objective function has a maximum or minimum value. An unbounded solution occurs when the feasible region is open, allowing the objective function to increase or decrease indefinitely, indicating that there is no finite optimal solution.

  8. 8.Explain the duality principle in linear programming.Concept

    The duality principle in linear programming states that every linear programming problem (the primal) has an associated dual problem. The optimal solution to the dual problem provides bounds on the optimal value of the primal problem. Solving the dual can provide insights into the primal problem, such as shadow prices and resource valuations.

  9. 9.A company produces two products, A and B. The profit per unit for A is $3 and for B is $5. The production constraints are: 2A + 3B ≤ 60 and A + B ≤ 20. Formulate the linear programming problem to maximize profit.Numerical

    Objective function: Maximize Z = 3A + 5B. Subject to constraints: 2A + 3B ≤ 60, A + B ≤ 20, A ≥ 0, B ≥ 0. The goal is to find the values of A and B that maximize Z while satisfying these constraints.

  10. 10.Solve the following linear programming problem using the graphical method: Maximize Z = 4x + 3y, subject to constraints x + 2y ≤ 8, 3x + y ≤ 9, x ≥ 0, y ≥ 0.Numerical
    1. Plot the constraints on a graph. 2. Identify the feasible region. 3. Evaluate the objective function at each vertex of the feasible region. 4. The maximum value of Z occurs at the vertex (x, y) = (3, 3), where Z = 4(3) + 3(3) = 21.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?