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.