Linear Programming for FSc Students

Linear programming is the mathematics of making the best decision when resources are limited. A factory owner wants the most profit from limited machine hours, a dietitian wants the cheapest meal plan that still meets nutritional needs, and a transport company wants the fewest kilometres driven. In FSc, linear programming is a short but very practical chapter, and once you learn the method it becomes one of the most dependable sources of marks in the second-year course.

The Building Blocks

Linear Inequalities in Two Variables

An inequality such as \( 2x + 3y \le 12 \) describes a whole region of the plane, not just a line. To graph it:

1. Draw the boundary line \( 2x + 3y = 12 \). Find two easy points, such as the intercepts \( (6, 0) \) and \( (0, 4) \).
2. Use a solid line for \( \le \) or \( \ge \) (the boundary is included) and a dashed line for \( < \) or \( > \).
3. Test a point not on the line, usually the origin. Here \( 2(0) + 3(0) = 0 \le 12 \) is true, so the region containing the origin is the solution side.

Key Vocabulary

• Decision variables: the quantities you choose, such as \( x \) and \( y \).
• Constraints: the inequalities that limit the choices.
• Non-negative constraints: \( x \ge 0, \; y \ge 0 \), because you cannot produce a negative number of items.
• Feasible region: the set of points satisfying every constraint at once.
• Corner points (vertices): the points where boundary lines of the feasible region meet.
• Objective function: the linear expression to maximise or minimise, such as profit \( f = 2x + 5y \).

The Corner Point Theorem

The central idea of the chapter is this: if a linear objective function has a maximum or minimum on a feasible region bounded by straight lines, that optimum occurs at a corner point. So instead of checking infinitely many points, you only need to check a handful of vertices.

The Step-by-Step Method

1. Define the decision variables in words.
2. Write all constraints, including \( x \ge 0 \) and \( y \ge 0 \).
3. Write the objective function.
4. Graph each constraint and shade the feasible region.
5. Find every corner point, solving pairs of boundary equations simultaneously where needed.
6. Evaluate the objective function at each corner point.
7. Choose the largest value (for maximisation) or smallest (for minimisation) and state the answer in context.

Worked Example 1: Maximising Profit

A small workshop in Sialkot makes footballs and volleyballs in batches. Let \( x \) be the number of football batches and \( y \) the number of volleyball batches made per day. Each football batch needs 1 hour of stitching-machine time and 1 hour of finishing; each volleyball batch needs 1 hour of stitching and 3 hours of finishing. Each day, 4 stitching hours and 6 finishing hours are available. The profit is 2 units (say, ten thousand rupees) per football batch and 5 units per volleyball batch. How many batches of each should be made?

Step 1. Constraints.

• Stitching: \( x + y \le 4 \)
• Finishing: \( x + 3y \le 6 \)
• Non-negativity: \( x \ge 0, \; y \ge 0 \)

Step 2. Objective function. Maximise \( f = 2x + 5y \).

Step 3. Boundary lines.

• \( x + y = 4 \) passes through \( (4, 0) \) and \( (0, 4) \).
• \( x + 3y = 6 \) passes through \( (6, 0) \) and \( (0, 2) \).

Testing the origin shows both regions lie towards \( (0, 0) \), so the feasible region is the area in the first quadrant below both lines.

Step 4. Corner points. Three are easy to read: \( (0, 0) \), \( (4, 0) \) and \( (0, 2) \). The fourth is where the two lines cross. Subtract the first equation from the second:

$$ (x + 3y) - (x + y) = 6 - 4 \;\Rightarrow\; 2y = 2 \;\Rightarrow\; y = 1 $$

Then \( x = 4 - 1 = 3 \), giving the vertex \( (3, 1) \).

Step 5. Evaluate the objective function.

Step 6. Conclusion. The maximum profit is 11 units (PKR 110,000 per day), achieved by making 3 football batches and 1 volleyball batch.

Sanity check. At \( (3, 1) \): stitching uses \( 3 + 1 = 4 \) hours and finishing uses \( 3 + 3 = 6 \) hours. Both resources are fully used, which is typical of an optimal production plan.

Worked Example 2: Minimising Cost

A poultry farmer mixes two feeds, A and B. Each bag of A provides 2 units of protein and 1 unit of minerals; each bag of B provides 1 unit of protein and 3 units of minerals. The flock needs at least 8 units of protein and 9 units of minerals. Feed A costs PKR 4,000 per bag and feed B costs PKR 3,000 per bag; we measure cost in hundreds of rupees to keep the numbers small. Find the cheapest mix.

Step 1. Variables. Let \( x \) bags of A and \( y \) bags of B.

Step 2. Constraints.

• Protein: \( 2x + y \ge 8 \)
• Minerals: \( x + 3y \ge 9 \)
• \( x \ge 0, \; y \ge 0 \)

Step 3. Objective. Minimise \( C = 40x + 30y \).

Step 4. Feasible region. Testing the origin gives \( 0 \ge 8 \), which is false, so the feasible region lies away from the origin, above both lines. It is unbounded, stretching upward and to the right.

Step 5. Corner points.

• Where \( 2x + y = 8 \) meets the \( y \)-axis: \( (0, 8) \). Check minerals: \( 0 + 24 = 24 \ge 9 \). Feasible.
• Where \( x + 3y = 9 \) meets the \( x \)-axis: \( (9, 0) \). Check protein: \( 18 \ge 8 \). Feasible.
• Intersection of the two lines. From the first, \( y = 8 - 2x \). Substitute into the second:

$$ x + 3(8 - 2x) = 9 \;\Rightarrow\; x + 24 - 6x = 9 \;\Rightarrow\; -5x = -15 \;\Rightarrow\; x = 3 $$

Then \( y = 8 - 6 = 2 \), giving \( (3, 2) \).

Step 6. Evaluate cost.

Step 7. Conclusion. The minimum cost is 180 hundred rupees, that is PKR 18,000,, using 3 bags of feed A and 2 bags of feed B.

Why does minimum make sense here but not maximum? Because the region is unbounded, the cost can be made as large as you like by buying more feed. A minimum exists, but no maximum does. Always think about this when the feasible region is open.

Common Mistakes

• Forgetting the non-negative constraints, which can create false corner points with negative values.
• Shading the wrong side of a line. Always test a point.
• Reading intersection points from a rough sketch instead of solving the equations.
• Giving a number as the answer without stating what it means in the problem.

Did You Know?

• The Soviet mathematician Leonid Kantorovich developed early linear programming ideas in 1939 to plan plywood production, and later shared a Nobel Prize in Economics.
• George Dantzig invented the simplex method in 1947, which solves linear programmes with thousands of variables. It moves from corner to corner, just like the graphical method, but in many dimensions.
• Airlines use linear programming to schedule crews and aircraft, saving very large sums every year.

Key Takeaways

• Linear programming finds the best value of a linear objective under linear constraints.
• The optimum of a bounded feasible region always lies at a corner point.
• Find intersection vertices algebraically, not by eye.
• Test a point to decide which side of each boundary line to shade.
• An unbounded region may have a minimum but no maximum, or the reverse, so think before concluding.

Want your linear programming exercises or assignments checked and explained? Amathify's subject experts and PhD scholars offer step-by-step solutions. Message us on WhatsApp or use the Ask a Question form.