Linear Programming Intro

Learning Objective: Solve simple optimization problems using graphical method

A furniture workshop in Bhaktapur makes tables and chairs. Each table earns Rs. 3,000 profit and each chair earns Rs. 2,000 profit. But the workshop has limited wood, limited labor hours, and limited workspace. How many tables and chairs should they produce to maximize profit? This is exactly the type of problem linear programming (LP) solves.

What Is Linear Programming?

Linear programming is a mathematical technique used to find the best outcome (maximum profit or minimum cost) given a set of constraints (limitations). It is widely used in business for production planning, resource allocation, and logistics.

Key Components of an LP Problem

1. Decision Variables

The quantities we want to find. Let:

• x = number of tables produced
• y = number of chairs produced

2. Objective Function

The expression we want to maximize or minimize.

Maximize: Z = 3,000x + 2,000y (total profit)

3. Constraints

The limitations on resources, written as linear inequalities.

• Wood constraint: 4x + 2y ≤ 40 (kg of wood available)
• Labor constraint: 3x + 3y ≤ 36 (labor hours available)
• Non-negativity: x ≥ 0, y ≥ 0 (cannot produce negative quantities)

Solving by Graphical Method

The graphical method works for problems with two decision variables. Here are the steps:

Step 1: Plot the constraints as straight lines.

For 4x + 2y = 40: When x = 0, y = 20; When y = 0, x = 10. Plot (0, 20) and (10, 0). For 3x + 3y = 36: When x = 0, y = 12; When y = 0, x = 12. Plot (0, 12) and (12, 0).

Step 2: Identify the feasible region.

The feasible region is the area on the graph that satisfies ALL constraints simultaneously. It is typically a polygon.

Step 3: Find corner points (vertices) of the feasible region.

The corner points for our problem are: (0, 0), (10, 0), (0, 12), and the intersection point.

To find the intersection of 4x + 2y = 40 and 3x + 3y = 36: From the second equation: x + y = 12, so y = 12 - x Substituting: 4x + 2(12 - x) = 40 → 4x + 24 - 2x = 40 → 2x = 16 → x = 8, y = 4

Corner points: (0, 0), (10, 0), (8, 4), (0, 12)

Step 4: Evaluate the objective function at each corner point.

| Corner Point (x, y) | Z = 3,000x + 2,000y | Profit (Rs.) | |---------------------|---------------------|-------------| | (0, 0) | 0 | 0 | | (10, 0) | 30,000 | 30,000 | | (8, 4) | 24,000 + 8,000 | 32,000 | | (0, 12) | 0 + 24,000 | 24,000 |

Step 5: Select the maximum.

The maximum profit of Rs. 32,000 occurs at (8, 4), meaning the workshop should produce 8 tables and 4 chairs.

Important Concepts

• Feasible region: The set of all points that satisfy all constraints
• Optimal solution: The point in the feasible region where the objective function has the best value
• Corner point theorem: The optimal solution always occurs at a corner point of the feasible region
• Infeasible problem: When no point satisfies all constraints simultaneously

Key Term: The Feasible Region is the set of all possible solutions that satisfy every constraint in a linear programming problem. The optimal solution is always found at one of its corner points.

Summary

• Linear programming finds the best outcome (max profit or min cost) subject to constraints.
• The graphical method involves plotting constraints, finding the feasible region, and evaluating corner points.
• The optimal solution always occurs at a corner point of the feasible region.
• LP is used in production planning, resource allocation, and transportation problems.