Learn & Review: Operation Research 3: Linear Programming Model Formulation

Lesson 3: Linear Programming Formulation

This lesson introduces the concept of Linear Programming (LP), a mathematical technique used for the optimal allocation of scarce resources to achieve maximum satisfaction or utility. It explains how to formulate real-world problems into LP models to find optimal solutions.

1. Introduction to Linear Programming

• Definition: LP is a mathematical technique for the optimum allocation of scarce resources.
• Purpose: To achieve maximum satisfaction or utility from limited resources when demands are unlimited.
• Applications: Production mix, diet problems, media selection, transportation problems, etc.

2. Assumptions of Linear Programming Models

For an LP model to work effectively, the following assumptions must be satisfied:

• Linearity: The relationship between decision variables in the objective function and constraints is linear.
• Divisibility: Non-integer or fractional values of decision variables are acceptable.
• Certainty: The values of all parameters in the model are known and constant.
• Non-negativity: All decision variables must be greater than or equal to zero.

3. Components of Linear Programming Models

LP models consist of four main components:

• Constraints: Limitations or available resources that restrict the achievement of the objective.
• Decision Variables: Variables that represent the ultimate solution to the problem (e.g., quantities to produce).
• Objective Function: A mathematical representation of the goal (e.g., profit or cost), denoted by 'Z'. It can be either a maximization or minimization problem.
• Non-negativity Restrictions: A statement that all decision variables must be greater than or equal to zero.

4. Standard Form of a Linear Programming Model

The standard form typically includes:

• An objective function (maximization or minimization).
• A set of constraints representing limitations.
• Non-negativity constraints for all decision variables.

5. Steps for Linear Programming Formulation

The process of formulating an LP model from a real-world problem involves these steps:

1. Define Decision Variables: Identify and define the variables that represent the quantities or decisions to be made (e.g., $X_1, X_2, ..., X_n$).
2. State the Objective Function: Express the goal (profit maximization or cost minimization) mathematically, including the decision variables and their contribution to the objective.
3. List the Constraints: Formulate mathematical expressions for all limitations or resource availabilities (e.g., $B_1, B_2, ..., B_n$).
4. State Non-negativity Restrictions: Explicitly state that all decision variables must be greater than or equal to zero.

6. Examples of Linear Programming Formulation

Example 1: Bakery Production (Maximization)

• Problem: A bakery produces two types of burgers (A and B) using flour and meat. Each burger type has specific resource requirements and yields a certain profit. The bakery has limited amounts of flour and meat.
• Data:
  • Burger A: 2 units flour, 3 units meat, Profit = BR 8/unit
  • Burger B: 1 unit flour, 2 units meat, Profit = BR 7/unit
  • Available Resources: 5 units flour, 12 units meat
• Formulation:
  • Decision Variables:
    • $X_1$ = number of units of Burger A
    • $X_2$ = number of units of Burger B
  • Objective Function: Maximize $Z = 8X_1 + 7X_2$ (Total Profit)
  • Constraints:
    • Flour: $2X_1 + X_2 \le 5$
    • Meat: $3X_1 + 2X_2 \le 12$
  • Non-negativity: $X_1 \ge 0, X_2 \ge 0$

Example 2: Workshop Manufacturing (Maximization)

• Problem: A workshop manufactures three products (A1, A2, A3) using cutting, drilling, and polishing machines. Each product requires different processing times on each machine, and the machines have limited weekly availability. Each product yields a specific profit.
• Data:
  • Product A1: 10 hrs cutting, 8 hrs drilling, 9 hrs polishing, Profit = $2.5/unit
  • Product A2: 15 hrs cutting, 10 hrs drilling, 12 hrs polishing, Profit = $35/unit
  • Product A3: 10 hrs cutting, 12 hrs drilling, 15 hrs polishing, Profit = $40/unit
  • Available Hours: Cutting = 80 hrs/week, Drilling = 70 hrs/week, Polishing = 60 hrs/week
• Formulation:
  • Decision Variables:
    • $X_1$ = production volume of Product A1
    • $X_2$ = production volume of Product A2
    • $X_3$ = production volume of Product A3
  • Objective Function: Maximize $Z = 25X_1 + 35X_2 + 40X_3$ (Total Profit)
  • Constraints:
    • Cutting: $10X_1 + 15X_2 + 10X_3 \le 80$
    • Drilling: $8X_1 + 10X_2 + 12X_3 \le 70$
    • Polishing: $9X_1 + 12X_2 + 15X_3 \le 60$
  • Non-negativity: $X_1 \ge 0, X_2 \ge 0, X_3 \ge 0$

Example 3: Special Diet (Minimization)

• Problem: A person on a special diet needs to meet minimum daily requirements for four nutrients (Vitamin C, Calcium, Iron, Magnesium) using two supplements (Vega Vita and Happy Health). Each supplement has a different nutrient content and cost. The goal is to minimize the daily cost.
• Data:
  • Daily Requirements: Vitamin C = 60 mg, Calcium = 1000 mg, Iron = 18 mg, Magnesium = 360 mg
  • Vega Vita: 20 mg Vit C, 500 mg Calcium, 9 mg Iron, 60 mg Magnesium, Cost = $0.2/tablet
  • Happy Health: 30 mg Vit C, 250 mg Calcium, 2 mg Iron, 90 mg Magnesium, Cost = $0.3/tablet
• Formulation:
  • Decision Variables:
    • $X_1$ = number of Vega Vita tablets
    • $X_2$ = number of Happy Health tablets
  • Objective Function: Minimize $Z = 0.2X_1 + 0.3X_2$ (Total Cost)
  • Constraints:
    • Vitamin C: $20X_1 + 30X_2 \ge 60$
    • Calcium: $500X_1 + 250X_2 \ge 1000$
    • Iron: $9X_1 + 2X_2 \ge 18$
    • Magnesium: $60X_1 + 90X_2 \ge 360$
  • Non-negativity: $X_1 \ge 0, X_2 \ge 0$

The lesson concludes by emphasizing that after formulating the LP model, the next step is to find the feasible and optimal solution, which will be covered in subsequent lessons.