Skip to content

Linear Programming Problem Formulation

What is Problem Formulation in Linear Programming?

Linear Programming Problem Formulation refers to the process of translating a real-world problem into a mathematical model with the goal of optimizing an objective (such as maximizing profit or minimizing cost). This model includes:

  1. Objective Function: A linear function that needs to be optimized, either maximized or minimized.
  2. Decision Variables: The variables that represent the quantities to be determined.
  3. Constraints: A set of linear inequalities or equalities that represent limitations or restrictions on the decision variables.
  4. Non-Negativity Restrictions: Decision variables cannot be negative, which is usually a realistic assumption for most real-world problems.

Steps for Formulating a Linear Programming Problem:

  1. Identify the decision variables: Determine the quantities that need to be determined.
  2. Formulate the objective function: Write the objective function that needs to be maximized or minimized using the decision variables.
  3. Set up the constraints: Identify the limitations or requirements of the problem and express them as linear equations or inequalities.
  4. Include non-negativity constraints: Ensure that the decision variables are non-negative since negative quantities typically do not make sense in real-world scenarios (e.g., negative products, hours, or costs).

Example 1: Factory Production Problem

Problem:

A factory produces two products, A and B. Each unit of product A requires 2 hours of labor and 1 unit of raw material. Each unit of product B requires 1 hour of labor and 2 units of raw material. The factory has a total of 100 hours of labor and 120 units of raw material available. The profit from each unit of product A is $30, and from each unit of product B is $20. How many units of each product should the factory produce to maximize its profit?

Step-by-Step Formulation:

  1. Decision Variables:
    Let:
  2. \(x_1\) be the number of units of product A produced.

  3. \(x_2\) be the number of units of product B produced.

  4. Objective Function:
    The objective is to maximize profit, which is $30 for each unit of product A and $20 for each unit of product B. The objective function is: [ Z = 30x_1 + 20x_2 ]

  5. Constraints:
    The problem has two main constraints: labor and raw materials.

  6. Labor constraint: Each unit of A requires 2 hours of labor and each unit of B requires 1 hour of labor. The factory has 100 hours of labor available. [ 2x_1 + x_2 \leq 100 ]

  7. Raw material constraint: Each unit of A requires 1 unit of raw material and each unit of B requires 2 units of raw material. The factory has 120 units of raw material available. [ x_1 + 2x_2 \leq 120 ]

  8. Non-Negativity Constraints:
    The number of units produced cannot be negative. [ x_1 \geq 0, \quad x_2 \geq 0 ]

Final Formulation:

[ \text{Maximize } Z = 30x_1 + 20x_2 ] [ \text{Subject to: } 2x_1 + x_2 \leq 100 ] [ x_1 + 2x_2 \leq 120 ] [ x_1 \geq 0, \quad x_2 \geq 0 ]

Example 2: Diet Optimization Problem

Problem:

A dietitian wants to create a meal plan that meets daily nutritional requirements at the minimum cost. Two foods are available: Food X and Food Y. Food X provides 4 units of protein and 3 units of carbohydrates per serving, while Food Y provides 2 units of protein and 5 units of carbohydrates per serving. The cost per serving of Food X is $3, and the cost per serving of Food Y is $4. The diet must provide at least 24 units of protein and 30 units of carbohydrates per day. How many servings of each food should be consumed to minimize the total cost?

Step-by-Step Formulation:

  1. Decision Variables:
    Let:
  2. \(x_1\) be the number of servings of Food X.

  3. \(x_2\) be the number of servings of Food Y.

  4. Objective Function:
    The objective is to minimize the total cost. The cost per serving of Food X is $3, and the cost per serving of Food Y is $4. The objective function is: [ Z = 3x_1 + 4x_2 ]

  5. Constraints:
    The diet must meet the daily nutritional requirements for protein and carbohydrates:

  6. Protein requirement: Each serving of Food X provides 4 units of protein, and each serving of Food Y provides 2 units. The diet must provide at least 24 units of protein. [ 4x_1 + 2x_2 \geq 24 ]

  7. Carbohydrate requirement: Each serving of Food X provides 3 units of carbohydrates, and each serving of Food Y provides 5 units. The diet must provide at least 30 units of carbohydrates. [ 3x_1 + 5x_2 \geq 30 ]

  8. Non-Negativity Constraints:
    The number of servings of each food cannot be negative. [ x_1 \geq 0, \quad x_2 \geq 0 ]

Final Formulation:

[ \text{Minimize } Z = 3x_1 + 4x_2 ] [ \text{Subject to: } 4x_1 + 2x_2 \geq 24 ] [ 3x_1 + 5x_2 \geq 30 ] [ x_1 \geq 0, \quad x_2 \geq 0 ]

Conclusion:

Linear Programming Problem Formulation helps in transforming real-world optimization problems into mathematical models. By defining decision variables, objective functions, and constraints, we can systematically solve these problems using mathematical techniques like the Simplex Method or Graphical Method.

Hive Chat
Hi, I'm Hive Chat, an AI assistant created by CollegeHive.
How can I help you today?
🎶
Hide