Linear Programming

Linear Programming (LP) is a mathematical technique used to find the best possible outcome (like maximum profit or lowest cost) given a set of limitations.

A. Objective Function

Meaning: The mathematical expression that represents the main goal of the problem.

• Simple Explanation: It’s your "target" (e.g., maximize profit or minimize expenses).
• Key Points: Always a linear equation, usually denoted by Z.
• Example: Z = 3x + 5y (where Z is profit, x and y are quantities).

Real-Life Use: Logistics companies use it to minimize total distance traveled to reduce fuel costs.

B. Constraints

Meaning: The restrictions or limitations placed on the variables.

• Simple Explanation: Real-world limits like money, time, and space.
• Key Points: Written as inequalities (≤, ≥, or =).
• Example: x + y ≤ 10 (Available labor hours).

Real-Life Use: A bakery's limited amount of flour and sugar restricts how many cakes can be baked.

C. Optimization

Meaning: Finding the best possible value (maximum or minimum) of the objective function.

• Maximization: Used for profit, efficiency, or output.
• Minimization: Used for cost, time, or waste.

Real-Life Use: Airlines optimizing flight crew assignments to minimize hotel costs.

Formulation is the process of converting a word problem into a mathematical model.

Steps to Formulate:

1. Identify Decision Variables: Define what you are deciding (e.g., x = units of Product A).
2. Write the Objective Function: State the goal (e.g., Maximize Z = 10x + 15y).
3. List the Constraints: Define the limits (e.g., 2x + 3y ≤ 60).
4. Add Non-Negativity Restrictions: Ensure physical quantities aren't negative (x ≥ 0, y ≥ 0).

A. Feasible and Infeasible Regions

• Feasible Region: The area on the graph where all constraints are satisfied. Any point here is a possible solution.
• Infeasible Region: The area where one or more constraints are violated.

B. Feasible vs. Optimal Solution

• Feasible Solution: Any point (x, y) within the feasible region.
• Optimal Solution: The specific feasible solution that gives the best value for Z. This is almost always located at a corner (vertex).

Real-Life Use: An architect designing a room based on a fixed budget (feasible region) to maximize natural light (optimal solution).

Step 1: Formulation

Maximize Z = 50x + 30y

Constraints:
1. 2x + 1y ≤ 100 (Time)
2. 4x + 2y ≤ 80 (Material)
3. x ≥ 0, y ≥ 0

Step 2: Boundary Lines

• Line 1 (2x + y = 100): Points (0, 100) and (50, 0)
• Line 2 (4x + 2y = 80): Points (0, 40) and (20, 0)

Step 3: Identify Feasible Region

The region is bounded by (0,0), (20,0), and (0,40).

Step 4: Testing Corner Points (Z = 50x + 30y)

Final Answer: Optimal solution is 0 Tables and 40 Chairs for a maximum profit of $1,200.

Formulas & Equations

• Objective Function: Max/Min Z = ax + by
• General Constraint: cx + dy ≤ k (or ≥ k)
• Non-negativity: x, y ≥ 0

Comparison: Maximization vs. Minimization

In industry, we solve problems with thousands of variables using:

• Simplex Method: An algebraic algorithm for complex LP.
• Software Tools:
  • Excel Solver: Standard for small business.
  • LINGO/Lindo: For large-scale professional optimization.
  • Python (SciPy.optimize): For automation and data science.

Industry Apps: Supply Chain (Warehouse locations), Agriculture (Crop mix), Finance (Portfolio risk/return).

Scenario: Green-Go Logistics uses Electric Vans (EV) and Hybrid Trucks (HT) to maximize package delivery.

Formulation:
Maximize Z = 40x + 70y
Constraints:
1. 3x + 2y ≤ 60
2. 50x + 100y ≤ 2000
3. x + y ≤ 25
4. x, y ≥ 0

Analysis: By plotting these constraints, the manager avoids wasting budget on expensive trucks or charging slots on low-capacity vans, turning a guess into mathematical certainty.

1. The objective function in LP is always: (b) Linear
2. Constraints in LP are usually expressed as: (b) Inequalities
3. The region that satisfies all constraints simultaneously is called: (c) Feasible Region
4. The optimal solution of an LP problem always lies on: (c) The corners (vertices) of the feasible region
5. Non-negativity constraints (x, y ≥ 0) ensure that: (d) All of the above
6. If a point satisfies some but not all constraints, it is in the: (b) Infeasible Region
7. Which of these is a minimization goal? (c) Minimum Cost
8. Linear Programming cannot be used if: (b) The objective function is non-linear
9. The "Simplex Method" is used when: (b) There are more than 2 variables
10. An "Infeasible Solution" means: (b) No point satisfies all constraints

1. Q: Define Linear Programming. Why is it called "Linear"?
   Ans: LP is a mathematical method to determine the best outcome in a model represented by linear relationships. It's "Linear" because the objective function and constraints are linear equations (variables are to the power of 1).
2. Q: Distinguish between Feasible Solution and Optimal Solution.
   Ans: A feasible solution satisfies all constraints; there can be many. An optimal solution is the specific feasible solution that maximizes or minimizes the objective function.
3. Q: What is the role of non-negativity constraints in LP?
   Ans: They ensure physical reality. Example: You cannot produce -5 cars. Therefore, x ≥ 0.
4. Q: Explain the "Corner Point Theorem".
   Ans: It states that if an optimal solution exists, it must occur at one of the vertices (corners) of the feasible region.
5. Q: Formulate: Product A ($10 profit, 2hr machine), Product B ($15 profit, 3hr machine), Total time 120hrs.
   Ans: Max Z = 10x + 15y; Subject to: 2x + 3y ≤ 120; x, y ≥ 0.
6. Q: What happens if the feasible region is "unbounded"?
   Ans: A maximum value might not exist, but a minimum value can still be found if bounded towards the origin.
7. Q: What is an "Infeasible Solution"?
   Ans: When no single point satisfies all constraints. Example: Wanting a $500 phone but only having $300.
8. Q: How does the objective function change the optimal point?
   Ans: It changes the "slope" of the target line, potentially shifting the optimal solution from one corner point to another.
9. Q: Name two software tools used for large-scale LP.
   Ans: Excel Solver and LINGO.
10. Q: Can a problem have more than one optimal solution?
    Ans: Yes, if the objective function line is parallel to a constraint line forming the boundary of the feasible region.

Mnemonic for Formulation: "V-O-C-N"

• V $\rightarrow$ Variables (What are x and y?)
• O $\rightarrow$ Objective (Goal: Max or Min?)
• C $\rightarrow$ Constraints (Limits: ≤ or ≥?)
• N $\rightarrow$ Non-negativity (x, y ≥ 0)

Quick Graphing Tip:
- ≤ (Less than) $\rightarrow$ Shade TOWARDS origin (0,0).
- ≥ (Greater than) $\rightarrow$ Shade AWAY from origin (0,0).