Linear Programming: Simplex Method – Graphs, Tables & Optimization

What is Linear Programming?

Linear programming (LP) is a mathematical method to find the best possible outcome (maximum profit, minimum cost, etc.) in a problem where:

• The objective function (what you want to maximize/minimize) is linear.
• The constraints (limitations) are also linear inequalities.

Key Terms:

• Objective Function: The function to maximize (e.g., profit) or minimize (e.g., cost).
• Constraints: Restrictions (e.g., time, resources, demand).
• Feasible Region: The area where all constraints are satisfied (shaded region in graphs).
• Optimal Solution: The best value of the objective function within the feasible region.

---

Step 1: Formulating the Problem

Before solving, we must write the problem mathematically.

Example Problem:

A factory produces two products, A and B. Each unit of A requires 2 hours of labor and 1 kg of material, while B requires 1 hour of labor and 3 kg of material. The factory has 100 hours of labor and 150 kg of material available. If A gives a profit of Rs. 40 and B gives Rs. 30, how many units of A and B should be produced to maximize profit?

Solution:

1. Define Variables: Let $x$ = number of units of A Let $y$ = number of units of B

2. Objective Function: Maximize $Z=40x+30y$ (Profit)

3. Constraints:

   • Labor: $2x+y\le 100$
   • Material: $x+3y\le 150$
   • Non-negativity: $x\ge 0,y\ge 0$

---

Step 2: Graphical Method (For 2 Variables)

If the problem has only 2 variables, we can solve it by graphing.

Steps:

1. Plot the constraints as lines (treat inequalities as equalities first).
2. Shade the feasible region (area satisfying all constraints).
3. Find corner points (vertices of the feasible region).
4. Evaluate the objective function at each corner point.
5. The best value is at one of these points.

Worked Example:

Solve the above problem graphically.

Step 1: Plot Constraints

• Labor Constraint: $2x+y=100$
  • When $x=0$, $y=100$
  • When $y=0$, $x=50$
• Material Constraint: $x+3y=150$
  • When $x=0$, $y=50$
  • When $y=0$, $x=150$

Step 2: Find Corner Points

The feasible region is a polygon with vertices at:

1. $(0,0)$
2. $(0,33.\overline{3})$ (Intersection of $y$-axis and material constraint)
3. $(40,20)$ (Intersection of labor and material constraints)
4. $(50,0)$

Step 3: Evaluate Objective Function

Maximum Profit = Rs. 2200 at $(40,20)$.

---

Step 3: Simplex Method (For 3+ Variables)

When there are more than 2 variables, we use the Simplex Method, an algebraic approach.

Standard Form Requirements:

1. Objective function must be maximization (if minimization, multiply by -1).
2. All constraints must be ≤ inequalities.
3. All variables must be ≥ 0.
4. Add slack variables to convert inequalities to equalities.

Example Problem (3 Variables):

Maximize $Z=3x+2y+4z$ Subject to:

• $x+y+z\le 10$
• $2x+y\le 8$
• $x,y,z\ge 0$

Step 1: Convert to Standard Form

Add slack variables $s_1,s_2$:

• $x+y+z+s_1=10$
• $2x+y+s_2=8$
• $Z-3x-2y-4z=0$

Step 2: Initial Simplex Tableau

Write the tableau:

Step 3: Identify Pivot Column and Row

• Pivot Column: Most negative in $Z$-row → $z$ (coefficient -4).
• Pivot Row: Smallest positive ratio $\frac{RHS}{PivotColumn}$:
  • $\frac{10}{1}=10$ (for $s_1$)
  • $\frac{8}{2}=4$ (for $s_2$) → Choose $s_2$ row.

Step 4: Perform Row Operations

Make the pivot element (2 in $s_2$-row) equal to 1:

• Divide $s_2$-row by 2: $s_2$-row: $1,0.5,0,0,0.5,4$

Now, eliminate other entries in the pivot column:

• Subtract $0.5\times s_2$-row from $s_1$-row: $s_1$-row: $0,0.5,1,1,-0.5,6$
• Add $4\times s_2$-row to $Z$-row: $Z$-row: $5,0,-4,0,2,16$

Final Tableau:

Step 5: Check for Optimality

• If all coefficients in $Z$-row are ≥ 0, the solution is optimal.
• Here, $z$ has a negative coefficient (-4), so we repeat the process.

Step 6: Next Iteration

• Pivot column: $z$ (coefficient -4).
• Pivot row: $\frac{6}{1}=6$ (for $s_1$).
• Perform row operations to get the final tableau.

Final Solution:

After iterations, we get:

• $x=4$, $y=0$, $z=6$
• Maximum $Z=3(4)+2(0)+4(6)=36$

---

Comparison: Graphical vs. Simplex Method

---

Advantages and Disadvantages

Advantages of Linear Programming:

• Efficient: Finds optimal solutions quickly.
• Versatile: Used in business, engineering, economics.
• Scalable: Works for large problems (thousands of variables).

Disadvantages:

• Assumptions: Requires linearity (real problems may be nonlinear).
• Complexity: Simplex method can be tedious for large problems (computer software is used in practice).
• Integer Solutions: May not give whole numbers (requires Integer Programming).

---

Applications of Linear Programming

1. Business: Maximizing profit, minimizing cost.
2. Transportation: Optimal routing for delivery trucks.
3. Agriculture: Allocating resources for maximum crop yield.
4. Manufacturing: Scheduling production to meet demand.
5. Diet Planning: Minimizing cost while meeting nutritional needs.

---

Exam Tip

What to Expect in NEB Exams:

1. Problem Formulation:

   • You may be given a word problem and asked to write the objective function and constraints.
   • Example Question: "A company produces two products. Product X requires 3 hours of labor and Product Y requires 2 hours. The company has 120 hours available. If X gives a profit of Rs. 50 and Y gives Rs. 40, formulate the problem to maximize profit."

2. Graphical Solution:

   • You may be asked to graph the feasible region and find the optimal solution.
   • Example Question: "Solve graphically: Maximize $Z=2x+3y$ subject to $x+y\le 10$, $x\le 6$, $y\le 8$, $x,y\ge 0$."

3. Simplex Method:

   • You may be given a tableau and asked to perform row operations to find the optimal solution.
   • Example Question: "Solve using the simplex method: Maximize $Z=5x+4y$ subject to $2x+y\le 20$, $x+y\le 15$, $x,y\ge 0$. Show the final tableau."

4. Interpretation:

   • You may be asked to explain the meaning of the solution (e.g., "How many units should be produced?").
   • Example Question: "In the above problem, what is the maximum profit, and how many units of each product should be produced?"

Common Mistakes to Avoid:

• Forgetting slack variables in the simplex method.
• Incorrect pivot selection (always choose the most negative in the $Z$-row).
• Not checking optimality (if negative coefficients remain, the solution is not optimal).
• Misplotting constraints in the graphical method (always shade the correct region).

---

Practice Questions (NEB Style)

1. Formulation: A farmer has 100 hectares of land. He can grow wheat or rice. Wheat requires 2 workers per hectare and rice requires 3 workers per hectare. The farmer has 240 workers. If the profit per hectare is Rs. 500 for wheat and Rs. 600 for rice, formulate the problem to maximize profit.

2. Graphical Solution: Solve graphically: Maximize $Z=3x+5y$ Subject to: $x+y\le 8$ $2x+y\le 10$ $x,y\ge 0$

3. Simplex Method: Solve using the simplex method: Maximize $Z=4x+3y$ Subject to: $x+2y\le 20$ $3x+y\le 25$ $x,y\ge 0$

4. Interpretation: A company produces two products, A and B. The profit for A is Rs. 3 per unit and for B is Rs. 5 per unit. The constraints are: $2x+y\le 100$ (labor) $x+2y\le 120$ (material) $x,y\ge 0$

   • Formulate the problem.
   • Solve graphically.
   • What is the maximum profit, and how many units of A and B should be produced?

---

Summary

• Linear programming helps find the best solution under given constraints.
• For 2 variables, use the graphical method.
• For 3+ variables, use the simplex method.
• Always check optimality and interpret the solution correctly.
• Practice formulating problems from word descriptions.

---

Good luck with your NEB exam! 🚀