# 2.8 Linear Programming

## Detailed Theory: Linear Programming

### **1. Introduction to Linear Programming**

#### **1.1 What is Linear Programming?**

Linear Programming (LP) is a mathematical method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by **linear relationships**.

#### **1.2 Key Components of LP**

Every linear programming problem consists of:

1. **Objective Function:** The function to be maximized or minimized
   * Example: Maximize $$Z = 3x + 4y$$
2. **Decision Variables:** The variables we can control
   * Example: $$x$$ and $$y$$
3. **Constraints:** Restrictions or limitations on the variables
   * Example: $$2x + y \leq 10$$, $$x + 3y \leq 15$$
4. **Non-negativity Conditions:** Variables must be non-negative
   * Example: $$x \geq 0$$, $$y \geq 0$$

#### **1.3 Standard Form of LP Problem**

A linear programming problem is in standard form if:

1. It is a **maximization** problem
2. All constraints are **equations** (not inequalities)
3. All variables are **non-negative**
4. All right-hand side constants are **non-negative**

**Standard Form:** Maximize $$Z = c\_1x\_1 + c\_2x\_2 + \cdots + c\_nx\_n$$

Subject to:

$$
a\_{11}x\_1 + a\_{12}x\_2 + \cdots + a\_{1n}x\_n = b\_1
$$

$$
a\_{21}x\_1 + a\_{22}x\_2 + \cdots + a\_{2n}x\_n = b\_2
$$

$$\vdots$$

$$
a\_{m1}x\_1 + a\_{m2}x\_2 + \cdots + a\_{mn}x\_n = b\_m
$$

$$
x\_1, x\_2, \ldots, x\_n \geq 0
$$

$$
b\_1, b\_2, \ldots, b\_m \geq 0
$$

***

### **2. Formulation of Linear Programming Problems**

#### **2.1 Steps in Formulation**

1. **Identify decision variables**
2. **Formulate objective function**
3. **Formulate constraints**
4. **Add non-negativity conditions**

#### **2.2 Example: Production Problem**

**Problem:** A company produces two products, A and B. Each unit of A gives profit of Rs. 40, each unit of B gives profit of Rs. 30. Machine time: A needs 2 hours, B needs 3 hours. Total machine time available: 60 hours. Labor: A needs 1 hour, B needs 2 hours. Total labor available: 40 hours. Find optimal production mix.

**Formulation:**

**Step 1:** Decision variables: Let $$x\_1$$ = number of units of A produced Let $$x\_2$$ = number of units of B produced

**Step 2:** Objective function (maximize profit): Maximize $$Z = 40x\_1 + 30x\_2$$

**Step 3:** Constraints: Machine time: $$2x\_1 + 3x\_2 \leq 60$$ Labor time: $$x\_1 + 2x\_2 \leq 40$$

**Step 4:** Non-negativity: $$x\_1 \geq 0$$, $$x\_2 \geq 0$$

**Complete LP:** Maximize $$Z = 40x\_1 + 30x\_2$$

Subject to:

$$
2x\_1 + 3x\_2 \leq 60
$$

$$
x\_1 + 2x\_2 \leq 40
$$

$$
x\_1, x\_2 \geq 0
$$

***

### **3. Graphical Method**

#### **3.1 When to Use Graphical Method**

The graphical method can be used only when there are **two decision variables**.

#### **3.2 Steps in Graphical Method**

1. **Plot constraints** as straight lines
2. **Identify feasible region** (area satisfying all constraints)
3. **Find corner points** of feasible region
4. **Evaluate objective function** at each corner point
5. **Select optimal solution**

#### **3.3 Example Using Graphical Method**

Solve: Maximize $$Z = 3x + 4y$$

Subject to:

$$
x + y \leq 5
$$

$$
2x + y \leq 8
$$

$$
x \geq 0, \quad y \geq 0
$$

**Step 1: Plot constraints**

Constraint 1: $$x + y \leq 5$$

* Line: $$x + y = 5$$
* Intercepts: (5,0) and (0,5)
* Shade below line (since $$\leq$$)

Constraint 2: $$2x + y \leq 8$$

* Line: $$2x + y = 8$$
* Intercepts: (4,0) and (0,8)
* Shade below line

Non-negativity: $$x \geq 0$$, $$y \geq 0$$ (first quadrant only)

**Step 2: Identify feasible region** Feasible region is the intersection of all shaded areas.

**Step 3: Find corner points**

1. Origin: (0,0)
2. X-intercept of constraint 1: (5,0)
3. Y-intercept of constraint 1: (0,5)
4. Intersection of constraints: Solve $$x + y = 5$$ and $$2x + y = 8$$

Subtract first from second: $$x = 3$$ Then $$3 + y = 5 \Rightarrow y = 2$$ Intersection: (3,2)

Check if (0,5) satisfies constraint 2: $$2(0) + 5 = 5 \leq 8$$ ✓

Check if (4,0) satisfies constraint 1: $$4 + 0 = 4 \leq 5$$ ✓

So corner points: (0,0), (5,0), (0,5), (3,2)

**Step 4: Evaluate objective function**

At (0,0): $$Z = 3(0) + 4(0) = 0$$

At (5,0): $$Z = 3(5) + 4(0) = 15$$

At (0,5): $$Z = 3(0) + 4(5) = 20$$

At (3,2): $$Z = 3(3) + 4(2) = 9 + 8 = 17$$

**Step 5: Select optimal solution** Maximum $$Z = 20$$ at (0,5)

So optimal solution: $$x = 0$$, $$y = 5$$, $$Z = 20$$

#### **3.4 Special Cases in Graphical Method**

**a) Multiple Optimal Solutions**

When objective function line is parallel to a constraint line forming one side of feasible region.

**Example:** Maximize $$Z = 2x + 2y$$ with same constraints as above.

Then at (0,5): $$Z = 10$$, at (3,2): $$Z = 10$$

All points on line segment between (0,5) and (3,2) give same $$Z = 10$$

**b) Unbounded Solution**

When feasible region extends infinitely in direction of increasing/decreasing objective function.

**Example:** Maximize $$Z = x + y$$ with constraints $$x \geq 0$$, $$y \geq 0$$ only.

**c) Infeasible Problem**

When no point satisfies all constraints simultaneously (feasible region is empty).

**Example:** $$x + y \leq 2$$ and $$x + y \geq 3$$ with $$x,y \geq 0$$

***

### **4. Simplex Method**

#### **4.1 Introduction to Simplex Method**

The simplex method is an **iterative algorithm** for solving linear programming problems with any number of variables.

#### **4.2 Converting to Standard Form**

To use simplex method, we need to convert inequalities to equations by adding **slack, surplus, and artificial variables**.

**a) Slack Variables (for ≤ constraints)**

Add slack variable to convert inequality to equation.

Example: $$2x + 3y \leq 10$$ becomes $$2x + 3y + s = 10$$ with $$s \geq 0$$

**b) Surplus and Artificial Variables (for ≥ constraints)**

1. Subtract surplus variable to convert to equation
2. Add artificial variable to get initial basic feasible solution

Example: $$x + y \geq 5$$ becomes $$x + y - s + a = 5$$ with $$s \geq 0$$, $$a \geq 0$$

**c) Artificial Variables (for = constraints)**

Add artificial variable directly.

Example: $$x + 2y = 8$$ becomes $$x + 2y + a = 8$$

#### **4.3 Simplex Algorithm Steps**

**Step 1: Convert to standard form**

**Step 2: Set up initial simplex tableau**

**Step 3: Identify entering variable** (most negative coefficient in objective row for maximization)

**Step 4: Identify leaving variable** using minimum ratio test

**Step 5: Perform pivot operation**

**Step 6: Repeat until** all coefficients in objective row are non-negative

#### **4.4 Example Using Simplex Method**

Maximize $$Z = 3x + 4y$$

Subject to:

$$
x + y \leq 5
$$

$$
2x + y \leq 8
$$

$$
x, y \geq 0
$$

**Step 1: Convert to standard form** Add slack variables $$s\_1$$ and $$s\_2$$:

Maximize $$Z = 3x + 4y + 0s\_1 + 0s\_2$$

Subject to:

$$
x + y + s\_1 = 5
$$

$$
2x + y + s\_2 = 8
$$

$$
x, y, s\_1, s\_2 \geq 0
$$

**Step 2: Initial simplex tableau**

| Basis | x  | y  | s₁ | s₂ | RHS |
| ----- | -- | -- | -- | -- | --- |
| s₁    | 1  | 1  | 1  | 0  | 5   |
| s₂    | 2  | 1  | 0  | 1  | 8   |
| Z     | -3 | -4 | 0  | 0  | 0   |

**Step 3: Entering variable** Most negative in Z-row: -4 (column y)

**Step 4: Leaving variable** Minimum ratio test: For s₁ row: 5/1 = 5 For s₂ row: 8/1 = 8 Minimum is 5, so s₁ leaves

**Step 5: Pivot operation** Pivot on element at intersection of y-column and s₁-row (value = 1)

New tableau after making pivot element = 1 and other elements in column = 0:

| Basis | x | y | s₁ | s₂ | RHS |
| ----- | - | - | -- | -- | --- |
| y     | 1 | 1 | 1  | 0  | 5   |
| s₂    | 1 | 0 | -1 | 1  | 3   |
| Z     | 1 | 0 | 4  | 0  | 20  |

**Step 6: Check optimality** All coefficients in Z-row are non-negative (1, 0, 4, 0 ≥ 0), so optimal.

**Optimal solution:** $$y = 5$$, $$s\_2 = 3$$, $$x = 0$$, $$Z = 20$$

This matches graphical solution.

***

### **5. Duality in Linear Programming**

#### **5.1 Primal and Dual Problems**

Every linear programming problem (called **primal**) has a corresponding **dual** problem.

**Primal (Maximization):** Maximize $$Z = c^Tx$$

Subject to: $$Ax \leq b$$, $$x \geq 0$$

**Dual (Minimization):** Minimize $$W = b^Ty$$

Subject to: $$A^Ty \geq c$$, $$y \geq 0$$

#### **5.2 Rules for Forming Dual**

| Primal (Maximization)    | Dual (Minimization)      |
| ------------------------ | ------------------------ |
| n variables              | n constraints            |
| m constraints            | m variables              |
| Coefficients cⱼ          | RHS bᵢ                   |
| RHS bᵢ                   | Coefficients cⱼ          |
| Constraint i: ≤          | Variable yᵢ ≥ 0          |
| Constraint i: ≥          | Variable yᵢ ≤ 0          |
| Constraint i: =          | Variable yᵢ unrestricted |
| Variable xⱼ ≥ 0          | Constraint j: ≥          |
| Variable xⱼ ≤ 0          | Constraint j: ≤          |
| Variable xⱼ unrestricted | Constraint j: =          |

#### **5.3 Example: Primal to Dual**

**Primal:** Maximize $$Z = 40x\_1 + 30x\_2$$

Subject to:

$$
2x\_1 + 3x\_2 \leq 60
$$

$$
x\_1 + 2x\_2 \leq 40
$$

$$
x\_1, x\_2 \geq 0
$$

**Dual:** Let $$y\_1$$, $$y\_2$$ be dual variables

Minimize $$W = 60y\_1 + 40y\_2$$

Subject to:

$$
2y\_1 + y\_2 \geq 40
$$

$$
3y\_1 + 2y\_2 \geq 30
$$

$$
y\_1, y\_2 \geq 0
$$

#### **5.4 Duality Theorems**

**a) Weak Duality Theorem**

If $$x$$ is feasible for primal and $$y$$ is feasible for dual, then:

$$
c^Tx \leq b^Ty
$$

**b) Strong Duality Theorem**

If either primal or dual has an optimal solution, then so does the other, and:

$$
\text{Optimal } Z = \text{Optimal } W
$$

**c) Complementary Slackness**

At optimality:

1. If primal constraint is not binding (slack > 0), then corresponding dual variable = 0
2. If dual constraint is not binding (surplus > 0), then corresponding primal variable = 0

***

### **6. Sensitivity Analysis**

#### **6.1 What is Sensitivity Analysis?**

Study of how changes in parameters affect optimal solution.

#### **6.2 Types of Changes Analyzed**

1. **Changes in objective function coefficients**
2. **Changes in right-hand side constants**
3. **Addition of new variables**
4. **Addition of new constraints**

#### **6.3 Range of Optimality**

For objective function coefficient $$c\_j$$, the **range of optimality** is the range of values for which current optimal solution remains optimal.

**Example:** For $$Z = 3x + 4y$$ with optimal solution (0,5):

* Current coefficient of $$x$$: 3
* Range of optimality for $$c\_x$$: $$c\_x \leq 4$$ (If $$c\_x > 4$$, then (0,5) is no longer optimal)

#### **6.4 Shadow Price**

**Shadow price** of a resource is the increase in optimal value per unit increase in availability of that resource.

Mathematically: Shadow price = optimal value of corresponding dual variable.

**Example:** For constraint $$x + y \leq 5$$ with RHS = 5, if we increase to 6:

* New optimal: (0,6) gives $$Z = 24$$
* Increase: 24 - 20 = 4
* Shadow price = 4

***

### **7. Transportation Problem**

#### **7.1 Introduction**

Transportation problem deals with distributing goods from multiple sources to multiple destinations at minimum cost.

#### **7.2 Mathematical Formulation**

Let:

* $$m$$ sources with supplies $$a\_1, a\_2, \ldots, a\_m$$
* $$n$$ destinations with demands $$b\_1, b\_2, \ldots, b\_n$$
* $$c\_{ij}$$ = cost to transport one unit from source $$i$$ to destination $$j$$
* $$x\_{ij}$$ = amount transported from source $$i$$ to destination $$j$$

Minimize total cost:

$$
Z = \sum\_{i=1}^m \sum\_{j=1}^n c\_{ij} x\_{ij}
$$

Subject to: Supply constraints:

$$
\sum\_{j=1}^n x\_{ij} = a\_i \quad \text{for } i = 1,2,\ldots,m
$$

Demand constraints:

$$
\sum\_{i=1}^m x\_{ij} = b\_j \quad \text{for } j = 1,2,\ldots,n
$$

Non-negativity:

$$
x\_{ij} \geq 0
$$

#### **7.3 Balanced Transportation Problem**

When total supply = total demand:

$$
\sum\_{i=1}^m a\_i = \sum\_{j=1}^n b\_j
$$

If unbalanced, add dummy source or destination.

#### **7.4 Solution Methods**

1. **North-West Corner Method**
2. **Least Cost Method**
3. **Vogel's Approximation Method (VAM)**
4. **MODI Method (Modified Distribution)** for optimality test

#### **7.5 Example: Transportation Problem**

**Problem:** Sources: S1 (supply 30), S2 (supply 50) Destinations: D1 (demand 20), D2 (demand 30), D3 (demand 30)

Cost matrix:

| From/To | D1 | D2 | D3 |
| ------- | -- | -- | -- |
| S1      | 2  | 3  | 4  |
| S2      | 5  | 1  | 2  |

**Using North-West Corner Method:**

Step 1: Start at NW corner (S1-D1) Allocate min(30,20) = 20 to S1-D1 S1 supply left: 10, D1 satisfied

Step 2: Move right to S1-D2 Allocate min(10,30) = 10 to S1-D2 S1 exhausted, D2 demand left: 20

Step 3: Move down to S2-D2 Allocate min(50,20) = 20 to S2-D2 D2 satisfied, S2 supply left: 30

Step 4: Move right to S2-D3 Allocate min(30,30) = 30 to S2-D3

All allocations done.

Total cost = $$20\times2 + 10\times3 + 20\times1 + 30\times2 = 40 + 30 + 20 + 60 = 150$$

***

### **8. Assignment Problem**

#### **8.1 Introduction**

Special case of transportation problem where:

* Number of sources = number of destinations
* Each source supplies exactly 1 unit
* Each destination demands exactly 1 unit

#### **8.2 Mathematical Formulation**

Minimize

$$
Z = \sum\_{i=1}^n \sum\_{j=1}^n c\_{ij} x\_{ij}
$$

Subject to:

$$
\sum\_{j=1}^n x\_{ij} = 1 \quad \text{for } i = 1,2,\ldots,n
$$

$$
\sum\_{i=1}^n x\_{ij} = 1 \quad \text{for } j = 1,2,\ldots,n
$$

$$
x\_{ij} = 0 \text{ or } 1
$$

#### **8.3 Hungarian Method**

Algorithm for solving assignment problems:

**Step 1:** Row reduction - subtract smallest element in each row from all elements in that row

**Step 2:** Column reduction - subtract smallest element in each column from all elements in that column

**Step 3:** Cover all zeros with minimum number of lines

**Step 4:** If number of lines = n, optimal solution found. Otherwise, adjust matrix and repeat.

#### **8.4 Example: Assignment Problem**

Assign 4 jobs to 4 workers with cost matrix:

| Worker/Job | J1 | J2 | J3 | J4 |
| ---------- | -- | -- | -- | -- |
| W1         | 9  | 2  | 7  | 8  |
| W2         | 6  | 4  | 3  | 7  |
| W3         | 5  | 8  | 1  | 8  |
| W4         | 7  | 6  | 9  | 4  |

**Solution using Hungarian method:**

Row reduction:

* Row 1: Subtract 2: \[7, 0, 5, 6]
* Row 2: Subtract 3: \[3, 1, 0, 4]
* Row 3: Subtract 1: \[4, 7, 0, 7]
* Row 4: Subtract 4: \[3, 2, 5, 0]

Column reduction:

* Col 1: Subtract 3: \[4, 0, 1, 0]
* Col 2: Subtract 0: \[0, 1, 7, 2]
* Col 3: Subtract 0: \[5, 0, 0, 5]
* Col 4: Subtract 0: \[6, 4, 7, 0]

Cover zeros with minimum lines (need 4 lines for optimal).

Optimal assignment: W1 → J2, W2 → J3, W3 → J1, W4 → J4 Total cost = 2 + 3 + 5 + 4 = 14

***

### **9. Integer Programming**

#### **9.1 Introduction**

Linear programming with additional requirement that some or all variables must take integer values.

#### **9.2 Types**

1. **Pure Integer Programming:** All variables integer
2. **Mixed Integer Programming:** Some variables integer
3. **Binary Integer Programming:** Variables 0 or 1

#### **9.3 Solution Methods**

1. **Branch and Bound Method**
2. **Cutting Plane Method**
3. **Gomory's Cutting Plane Method**

#### **9.4 Example: Integer Programming**

Maximize $$Z = 3x + 2y$$

Subject to:

$$
2x + y \leq 6
$$

$$
x + 2y \leq 8
$$

$$
x, y \geq 0 \text{ and integer}
$$

**LP relaxation solution** (without integer constraint): $$x = \frac{4}{3}$$, $$y = \frac{10}{3}$$, $$Z = \frac{32}{3}$$

**Branch and Bound:**

1. Branch on $$x$$: $$x \leq 1$$ and $$x \geq 2$$
2. Solve each subproblem
3. Continue until integer solutions found

Optimal integer solution: $$x = 2$$, $$y = 2$$, $$Z = 10$$

***

### **10. Applications of Linear Programming**

#### **10.1 Business and Economics**

* **Production planning:** Optimal product mix
* **Inventory management:** When and how much to order
* **Portfolio selection:** Maximize return, minimize risk
* **Blending problems:** Optimal mix of ingredients

#### **10.2 Engineering**

* **Structural design:** Minimum weight structures
* **Network flows:** Maximum flow, shortest path
* **Scheduling:** Optimal timetables

#### **10.3 Agriculture**

* **Crop planning:** Land allocation to maximize profit
* **Feed mix:** Minimum cost animal feed

#### **10.4 Healthcare**

* **Resource allocation:** Hospital staff scheduling
* **Diet planning:** Minimum cost nutritious diet

***

### **11. Important Theorems and Concepts**

#### **11.1 Fundamental Theorem of Linear Programming**

If an LP problem has an optimal solution, then it has an optimal solution at a **corner point** (extreme point) of the feasible region.

#### **11.2 Extreme Point Theorem**

The feasible region of an LP problem is a convex polyhedron, and the optimal solution occurs at an extreme point.

#### **11.3 Complementary Slackness Theorem**

At optimality of primal and dual:

* If a primal variable is positive, corresponding dual constraint is tight
* If a dual variable is positive, corresponding primal constraint is tight

#### **11.4 Farkas' Lemma**

Either $$Ax = b$$, $$x \geq 0$$ has a solution, or $$A^Ty \geq 0$$, $$b^Ty < 0$$ has a solution, but not both.

***

### **12. Practice Problems**

#### **Problem 1: Graphical Method**

Maximize $$Z = 5x + 3y$$

Subject to:

$$
3x + 5y \leq 15
$$

$$
5x + 2y \leq 10
$$

$$
x, y \geq 0
$$

**Solution:** Corner points: (0,0), (2,0), (0,3), intersection point

Solve:

$$
3x + 5y = 15
$$

$$
5x + 2y = 10
$$

Multiply first by 2: $$6x + 10y = 30$$ Multiply second by 5: $$25x + 10y = 50$$ Subtract: $$19x = 20 \Rightarrow x = \frac{20}{19}$$ Then $$3(\frac{20}{19}) + 5y = 15 \Rightarrow 5y = 15 - \frac{60}{19} = \frac{225}{19} \Rightarrow y = \frac{45}{19}$$

Evaluate:

* (0,0): Z = 0
* (2,0): Z = 10
* (0,3): Z = 9
* $$(\frac{20}{19}, \frac{45}{19})$$: Z = $$5\times\frac{20}{19} + 3\times\frac{45}{19} = \frac{100}{19} + \frac{135}{19} = \frac{235}{19} \approx 12.37$$

Optimal: $$x = \frac{20}{19}$$, $$y = \frac{45}{19}$$, $$Z = \frac{235}{19}$$

#### **Problem 2: Simplex Method**

Maximize $$Z = 2x\_1 + 3x\_2$$

Subject to:

$$
x\_1 + x\_2 \leq 4
$$

$$
x\_1 - x\_2 \leq 2
$$

$$
x\_1, x\_2 \geq 0
$$

**Solution:** Add slack variables $$s\_1, s\_2$$:

Maximize $$Z = 2x\_1 + 3x\_2 + 0s\_1 + 0s\_2$$

Subject to:

$$
x\_1 + x\_2 + s\_1 = 4
$$

$$
x\_1 - x\_2 + s\_2 = 2
$$

Initial tableau:

| Basis | x₁ | x₂ | s₁ | s₂ | RHS |
| ----- | -- | -- | -- | -- | --- |
| s₁    | 1  | 1  | 1  | 0  | 4   |
| s₂    | 1  | -1 | 0  | 1  | 2   |
| Z     | -2 | -3 | 0  | 0  | 0   |

Entering: x₂ (most negative -3) Leaving: s₁ (min ratio: 4/1 = 4 vs 2/(-1) invalid)

Pivot on (1,2):

New tableau:

| Basis | x₁ | x₂ | s₁ | s₂ | RHS |
| ----- | -- | -- | -- | -- | --- |
| x₂    | 1  | 1  | 1  | 0  | 4   |
| s₂    | 2  | 0  | 1  | 1  | 6   |
| Z     | 1  | 0  | 3  | 0  | 12  |

Optimal (all coefficients ≥ 0)

Solution: $$x\_1 = 0$$, $$x\_2 = 4$$, $$Z = 12$$

***

### **13. Exam Tips and Common Mistakes**

#### **13.1 Common Mistakes**

1. **Forgetting non-negativity constraints**
2. **Incorrect conversion** of inequalities to equations
3. **Wrong direction** of inequality when forming dual
4. **Incorrect pivot element** selection in simplex
5. **Not checking** for multiple or unbounded solutions

#### **13.2 Problem-Solving Strategy**

1. **Understand the problem:** Identify objective, variables, constraints
2. **Choose appropriate method:** Graphical (2 variables), Simplex (more variables)
3. **Solve systematically:** Show all steps
4. **Interpret solution:** What do the numbers mean in context?
5. **Check feasibility:** Does solution satisfy all constraints?

#### **13.3 Quick Checks**

* **Feasible region:** Should be convex polygon
* **Optimal solution:** At corner point for LP
* **Shadow prices:** Non-negative for maximization
* **Dual variables:** Non-negative for ≤ constraints in primal maximization

This comprehensive theory covers all aspects of linear programming with detailed explanations and examples, providing complete preparation for the entrance examination.