Linear Programming: Graphical Method, Constraints, Optimization

TAKEAWAYS:

• Linear programming solves problems by maximizing/minimizing a linear objective function under constraints.
• The graphical method works only for problems with two variables and linear constraints.
• The feasible region is the area where all constraints are satisfied, and the optimal solution lies at its corner points.
• Shadow prices (or dual values) help understand how changes in constraints affect the objective function.
• Applications include production planning, diet problems, and transportation logistics.
• Always check corner points to find the best solution, as the optimal value occurs there.

---

What is Linear Programming?

Linear programming (LP) is a mathematical technique used to find the best possible outcome (maximum profit or minimum cost) in a given situation. It is widely used in business for decision-making.

Key Terms

1. Objective Function: The goal we want to maximize (profit) or minimize (cost).
   • Example: Maximize $Z=3x+4y$ (where $x$ and $y$ are products).
2. Constraints: Restrictions or limitations on the problem.
   • Example: $2x+y\le 100$ (limited resources).
3. Decision Variables: Variables we control (e.g., number of products to make).
4. Feasible Region: The area where all constraints are satisfied.
5. Optimal Solution: The best value of the objective function within the feasible region.

---

Steps to Solve a Linear Programming Problem (Graphical Method)

The graphical method is used when there are only two variables. Here’s how it works:

Step 1: Identify the Objective Function and Constraints

• Write the objective function (e.g., maximize profit).
• List all constraints (e.g., resource limits, non-negativity).

Step 2: Plot the Constraints on a Graph

• Convert each inequality into an equation (e.g., $2x+y=100$).
• Find the intercepts (where $x=0$ and $y=0$) for each constraint.
• Draw the lines and shade the feasible region (the area that satisfies all constraints).

Step 3: Identify the Feasible Region

• The feasible region is the overlapping area where all constraints are met.
• If no feasible region exists, the problem has no solution.

Step 4: Find the Corner Points

• The optimal solution always lies at one of the corner points of the feasible region.
• Solve the equations of the boundary lines to find these points.

Step 5: Evaluate the Objective Function at Each Corner Point

• Plug the coordinates of each corner point into the objective function.
• The highest (or lowest) value gives the optimal solution.

---

Example 1: Production Planning Problem

Problem: A factory produces two products, A and B.

• Each unit of A requires 2 hours of labor and 3 kg of material.
• Each unit of B requires 4 hours of labor and 1 kg of material.
• The factory has 80 hours of labor and 36 kg of material available.
• Profit per unit of A is Rs. 50, and for B, it is Rs. 40.
• How many units of A and B should be produced to maximize profit?

Step 1: Define Variables and Objective Function

• Let $x$ = number of units of A.
• Let $y$ = number of units of B.
• Objective Function (Maximize Profit): $Z=50x+40y$

Step 2: Write Constraints

1. Labor constraint: $2x+4y\le 80$
2. Material constraint: $3x+y\le 36$
3. Non-negativity: $x\ge 0,y\ge 0$

Step 3: Plot the Constraints

We plot the lines:

1. $2x+4y=80$ → Intercepts: $(40,0)$ and $(0,20)$
2. $3x+y=36$ → Intercepts: $(12,0)$ and $(0,36)$

Step 4: Find the Feasible Region

The feasible region is the shaded area where both constraints overlap.

Step 5: Find Corner Points

Solve the equations of the boundary lines:

1. Intersection of $2x+4y=80$ and $3x+y=36$:
   • From $3x+y=36$, $y=36-3x$.
   • Substitute into $2x+4y=80$: $2x+4(36-3x)=80$ $2x+144-12x=80$ $-10x=-64$ → $x=6.4$ $y=36-3(6.4)=16.8$
   • So, one corner point is $(6.4,16.8)$.

Other corner points are:

• $(0,0)$ (origin)
• $(0,20)$ (from labor constraint)
• $(12,0)$ (from material constraint)

Step 6: Evaluate the Objective Function

Optimal Solution:

• Produce 6.4 units of A and 16.8 units of B for a maximum profit of Rs. 992.

---

Example 2: Diet Problem

Problem: A person needs at least 40 units of protein and 50 units of vitamins per day.

• Food X provides 10 units of protein and 5 units of vitamins per serving and costs Rs. 2.
• Food Y provides 5 units of protein and 10 units of vitamins per serving and costs Rs. 3.
• How many servings of X and Y should be eaten to meet the requirements at minimum cost?

Step 1: Define Variables and Objective Function

• Let $x$ = servings of X.
• Let $y$ = servings of Y.
• Objective Function (Minimize Cost): $Z=2x+3y$

Step 2: Write Constraints

1. Protein: $10x+5y\ge 40$
2. Vitamins: $5x+10y\ge 50$
3. Non-negativity: $x\ge 0,y\ge 0$

Step 3: Plot the Constraints

Convert inequalities to equations:

1. $10x+5y=40$ → Intercepts: $(4,0)$ and $(0,8)$
2. $5x+10y=50$ → Intercepts: $(10,0)$ and $(0,5)$

Step 4: Find Corner Points

Solve the equations:

1. Intersection of $10x+5y=40$ and $5x+10y=50$:
   • Multiply first equation by 2: $20x+10y=80$
   • Subtract second equation: $15x=30$ → $x=2$
   • Substitute back: $10(2)+5y=40$ → $y=4$
   • Corner point: $(2,4)$

Other corner points:

• $(4,0)$ (from protein constraint)
• $(0,5)$ (from vitamins constraint)

Step 5: Evaluate the Objective Function

Optimal Solution:

• Eat 4 servings of X and 0 servings of Y for a minimum cost of Rs. 8.

---

Advantages and Disadvantages of Linear Programming

---

Applications of Linear Programming

1. Production Planning: Deciding how much of each product to make.
2. Diet Problems: Meeting nutritional requirements at minimum cost.
3. Transportation Problems: Optimizing routes for delivery.
4. Investment Planning: Allocating funds to maximize returns.
5. Blending Problems: Mixing ingredients to achieve desired properties.

---

Shadow Prices (Dual Values)

• Shadow prices tell us how much the objective function value changes if a constraint is relaxed by one unit.
• Example: If the labor constraint in the production problem is increased by 1 hour, the profit increases by the shadow price of labor.

---

Exam Tip: How to Score Full Marks in NEB Exams

1. Understand the Problem: Always read the question carefully and identify the objective function and constraints.
2. Draw the Graph Accurately: Use a ruler and label all intercepts and feasible regions clearly.
3. Find All Corner Points: Solve the equations correctly to find all possible corner points.
4. Evaluate the Objective Function: Plug in all corner points and compare the results.
5. Check for Errors: Ensure all constraints are satisfied and the feasible region is correctly shaded.
6. Write Clear Steps: Show all calculations and reasoning in your answer.
7. Practice Numerical Problems: Solve as many problems as possible to build confidence.

---

NEB Board-Style Questions

Short Answer Questions

1. What is the difference between an objective function and a constraint in linear programming?
2. Why is the feasible region important in solving a linear programming problem?
3. What are the limitations of the graphical method in linear programming?

Numerical Problems

1. A company produces two products, P and Q. Each unit of P requires 3 hours of labor and 2 kg of material, while each unit of Q requires 2 hours of labor and 4 kg of material. The company has 120 hours of labor and 160 kg of material available. If the profit per unit of P is Rs. 40 and for Q is Rs. 50, how many units of each should be produced to maximize profit?
2. A farmer has 100 hectares of land to grow wheat and rice. Each hectare of wheat requires 4 units of fertilizer and yields a profit of Rs. 2000, while each hectare of rice requires 6 units of fertilizer and yields a profit of Rs. 3000. The farmer has only 500 units of fertilizer available. How should the farmer allocate the land to maximize profit?

Theoretical Questions

1. Explain the steps involved in solving a linear programming problem using the graphical method.
2. What is the role of corner points in determining the optimal solution in linear programming?
3. How can shadow prices be useful in business decision-making?

---

This note covers all key concepts, examples, and exam tips for Linear Programming in Business Mathematics. Practice the numerical problems to master the graphical method!