Linear Programming

Linear Programming Problem: Definition and Components

A **Linear Programming Problem (LPP)** is an optimization problem concerned with finding the optimal value (maximum or minimum) of a linear function (called the **objective function**) of several variables, subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called **linear constraints**).

**Key Features:**

All mathematical relations must be linear

Decision variables are always non-negative (x ≥ 0, y ≥ 0)

The objective function is linear: Z = ax + by (where a, b are constants)

Constraints are linear inequalities or equations

**Real-Life Application Example (Furniture Dealer):**

A furniture dealer has Rs 50,000 capital and storage for 60 pieces. A table costs Rs 2,500 (profit Rs 250) and a chair costs Rs 500 (profit Rs 75). How many tables (x) and chairs (y) should he buy to maximize profit?

Objective Function: Maximize Z = 250x + 75y

Constraints: 5x + y ≤ 100 (investment), x + y ≤ 60 (storage), x ≥ 0, y ≥ 0

Variables x and y are called **decision variables**

Mathematical Formulation of Linear Programming Problems

**Step 1: Identify Decision Variables**

Define variables clearly. Let x and y represent the quantities to be determined.

**Step 2: Formulate the Objective Function**

Express the quantity to be maximized or minimized as a linear combination: Z = ax + by

**Step 3: State the Constraints**

Write all restrictions as linear inequalities:

Resource constraints (e.g., budget, time, space)

Non-negativity constraints: x ≥ 0, y ≥ 0

**Standard Form of LPP:**

Optimize Z = ax + by

Subject to:

c₁x + d₁y ≤ (or ≥ or =) e₁

c₂x + d₂y ≤ (or ≥ or =) e₂

x ≥ 0, y ≥ 0

**Exam Tip:** Always clearly define variables and write constraints in simplified form (divide by GCD of coefficients).

Graphical Method: Feasible Region and Corner Points

**Feasible Region:** The common region determined by all constraints (including non-negativity) is called the **feasible region** or **solution region**. Every point within and on the boundary of this region represents a feasible solution.

**Identifying the Feasible Region (Step-by-Step):**

1. Convert each inequality to an equation and draw its boundary line

2. For each inequality, shade the region satisfying it

3. The intersection of all shaded regions is the feasible region

4. The feasible region is always a **convex polygon** in 2D problems

**Corner Points (Vertices):** These are the vertices of the feasible region polygon, found by:

Inspection from the graph, OR

Solving pairs of boundary line equations simultaneously

**Example:** For constraints x + y ≤ 50, 3x + y ≤ 90, x ≥ 0, y ≥ 0

Corner points are found at intersections: O(0,0), A(30,0), B(20,30), C(0,50)

These points are candidates for optimal solutions

Fundamental Theorems of Linear Programming

**Theorem 1 (Optimal Value at Corner Point):**

If the feasible region R (a convex polygon) is non-empty, and the objective function Z = ax + by has an optimal value (maximum or minimum), this optimal value must occur at a corner point (vertex) of the feasible region.

**Theorem 2 (Bounded Region):**

If the feasible region R is **bounded** (can be enclosed within a circle), then the objective function Z = ax + by has both a maximum and minimum value, and each occurs at a corner point of R.

**Important Remark on Unbounded Regions:**

If the feasible region is unbounded:

An optimal value may or may not exist

If it exists, it must occur at a corner point

Must verify using the half-plane test (see Example 4 below)

Corner Point Method: Complete Procedure

The **Corner Point Method** is the standard graphical approach for solving LPPs in two variables.

**Step 1:** Graph the feasible region by plotting all constraint inequalities and identifying their common region.

**Step 2:** Find all corner points either by inspection or by solving the equations of intersecting boundary lines.

**Step 3:** Evaluate the objective function Z = ax + by at each corner point.

**Step 4:** Determine the optimal solution:

**If feasible region is bounded:** The maximum value is the largest Z-value; the minimum is the smallest Z-value obtained at step 3.

**If feasible region is unbounded:**

For maximum: Check if the half-plane ax + by > M (where M is largest corner value) intersects the feasible region. If no intersection, M is maximum; otherwise, no maximum exists.

For minimum: Check if the half-plane ax + by < m (where m is smallest corner value) intersects the feasible region. If no intersection, m is minimum; otherwise, no minimum exists.

Worked Example 1: Maximization Problem (Bounded Feasible Region)

**Problem:** Maximize Z = 4x + y subject to x + y ≤ 50, 3x + y ≤ 90, x ≥ 0, y ≥ 0

**Solution:**

*Graphical Setup:*

Line 1: x + y = 50 passes through (50,0) and (0,50)

Line 2: 3x + y = 90 passes through (30,0) and (0,90)

Feasible region is intersection of x + y ≤ 50 and 3x + y ≤ 90 with x,y ≥ 0

*Finding Corner Points:*

O = (0, 0): intersection of x = 0, y = 0

A = (30, 0): intersection of 3x + y = 90 and y = 0

B: intersection of x + y = 50 and 3x + y = 90

From first: y = 50 - x

Substitute: 3x + 50 - x = 90 → 2x = 40 → x = 20, y = 30

B = (20, 30)

C = (0, 50): intersection of x = 0 and x + y = 50

*Evaluating Z at each corner point:*

| Corner Point | Z = 4x + y |

|---|---|

| O(0,0) | 0 |

| A(30,0) | 120 |

| B(20,30) | 110 |

| C(0,50) | 50 |

**Answer:** Maximum value of Z is **120 at point (30, 0)**

Worked Example 2: Minimization Problem (Bounded Feasible Region)

**Problem:** Minimize Z = 200x + 500y subject to x + 2y ≥ 10, 3x + 4y ≤ 24, x ≥ 0, y ≥ 0

**Solution:**

*Finding Corner Points (where boundary lines intersect):*

From x + 2y = 10 and x = 0: A = (0, 5)

From x + 2y = 10 and 3x + 4y = 24:

From first: x = 10 - 2y

Substitute: 3(10 - 2y) + 4y = 24 → 30 - 6y + 4y = 24 → y = 3, x = 4

B = (4, 3)

From 3x + 4y = 24 and y = 0: 3x = 24 → x = 8, but check x + 2(0) ≥ 10? No

From 3x + 4y = 24 and x = 0: C = (0, 6)

*Evaluating Z at feasible corner points:*

| Corner Point | Z = 200x + 500y |

|---|---|

| A(0,5) | 2,500 |

| B(4,3) | 2,300 |

| C(0,6) | 3,000 |

**Answer:** Minimum value of Z is **2,300 at point (4, 3)**

Worked Example 3: Multiple Optimal Solutions

**Problem:** Minimize and Maximize Z = 3x + 9y subject to x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0, y ≥ 0

**Solution:**

*Corner Points:*

A = (0, 10): intersection of x = 0 and x + y = 10

B = (5, 5): intersection of x = y and x + y = 10

C = (15, 15): intersection of x = y and x + 3y = 60

D = (0, 20): intersection of x = 0 and x + 3y = 60

*Evaluating Z at corner points:*

| Corner Point | Z = 3x + 9y |

|---|---|

| A(0,10) | 90 |

| B(5,5) | 60 |

| C(15,15) | 180 |

| D(0,20) | 180 |

**Answer:**

**Minimum:** Z = 60 at point B(5, 5)

**Maximum:** Z = 180 at points C(15, 15) and D(0, 20) - **multiple optimal solutions**

**Key Point:** Every point on line segment CD also gives Z = 180 (optimal solutions form a line segment)

Worked Example 4: Unbounded Feasible Region (No Optimal Value)

**Problem:** Minimize Z = -50x + 20y subject to 2x - y ≥ -5, 3x + y ≥ 3, 2x - 3y ≤ 12, x ≥ 0, y ≥ 0

**Solution:**

*Corner Points:*

(0, 5), (0, 3), (1, 0), (6, 0)

*Evaluating Z:*

| Corner Point | Z = -50x + 20y |

|---|---|

| (0,5) | 100 |

| (0,3) | 60 |

| (1,0) | -50 |

| (6,0) | -300 |

*Checking for Unboundedness:*

The feasible region is **unbounded**. The smallest corner value is -300 at (6, 0).

To verify if this is truly the minimum, check the half-plane: -50x + 20y < -300

Simplify: -5x + 2y < -30

If this open half-plane intersects the feasible region, then no minimum exists.

**Answer:** Since the half-plane -5x + 2y < -30 has points in common with the unbounded feasible region, **Z has no minimum value**.

Worked Example 5: Inconsistent Constraints (No Feasible Solution)

**Problem:** Minimize Z = 3x + 2y subject to x + y ≥ 8, 3x + 5y ≤ 15, x ≥ 0, y ≥ 0

**Solution:**

Plotting the constraints:

x + y ≥ 8: region above/on the line x + y = 8

3x + 5y ≤ 15: region below/on the line 3x + 5y = 15

x ≥ 0, y ≥ 0: first quadrant

**Check feasibility:** The region where x + y ≥ 8 and 3x + 5y ≤ 15 do not intersect in the first quadrant (line x + y = 8 lies entirely above line 3x + 5y = 15 in relevant region).

**Answer:** **No feasible region exists.** The problem has **no solution**.

Important Properties and Remarks

1. **Feasible Region is Convex:** The intersection of half-planes determined by linear inequalities always forms a convex polygon (for 2D problems).

2. **Optimal Value Location:** The maximum or minimum of a linear objective function over a convex polygon always occurs at a vertex. This is fundamental to the graphical method's efficiency.

3. **Multiple Optimal Solutions:** If two adjacent corner points give the same optimal value, then every point on the line segment joining them is also optimal. This occurs when the objective function line is parallel to a constraint boundary.

4. **Unbounded Feasible Regions:** In such cases, the optimal value may not exist even though corner points are computed. The half-plane test is mandatory.

5. **Degenerate Cases:**

No feasible region (inconsistent constraints)

Unbounded feasible region with no optimal solution

Unique optimal solution at a single corner point

Multiple optimal solutions on an edge

Summary of Corner Point Method

| Step | Action |

|---|---|

| 1 | Formulate constraints as system of inequalities |

| 2 | Graph each inequality and shade feasible region |

| 3 | Identify corner points (vertices) of feasible region |

| 4 | Evaluate objective function Z at each corner point |

| 5 | For bounded region: max = largest Z, min = smallest Z |

| 6 | For unbounded region: use half-plane test to verify optimality |

| 7 | State the optimal solution (point and Z-value) |