Linear Programming and Simplex Methods

Linear Programming (LP) is a powerful mathematical technique used to optimize a linear objective function, subject to a set of linear constraints. It is widely used in various fields such as business, economics, engineering, and operations research to make optimal decisions regarding resource allocation, production planning, scheduling, and more. The core idea is to find the best possible outcome (maximum profit, minimum cost, etc.) in a mathematical model whose requirements and objective are represented by linear relationships.

1. Introduction to Linear Programming

At its heart, Linear Programming deals with problems where we want to maximize or minimize a linear function of decision variables, while satisfying a system of linear inequalities or equalities. These inequalities represent the limitations or requirements of the system.

1.1 Components of a Linear Programming Problem (LPP)

Every LPP consists of three fundamental components:

• Decision Variables: These are the variables we need to determine the optimal values for. They represent the quantities of different activities or choices. For example, if a company produces two products, the decision variables might be the number of units of each product to produce.
• Objective Function: This is the linear function that we aim to maximize or minimize. It expresses the goal of the problem in terms of the decision variables. For instance, the objective function could represent the total profit to be maximized or the total cost to be minimized.
• Constraints: These are the linear inequalities or equalities that restrict the values of the decision variables. They represent limitations on resources (like labor, raw materials, machine time), demand, or other operational requirements.

1.2 Standard Form of an LPP

An LPP is said to be in standard form if it satisfies the following conditions:

• The objective function is a maximization problem (minimization can be converted to maximization by multiplying the objective function by -1).
• All constraints are of the 'less than or equal to' (≤) type.
• All decision variables are non-negative (≥ 0).

If an LPP is not in standard form, it can be converted. For example, a 'greater than or equal to' (≥) constraint can be converted to a 'less than or equal to' (≤) constraint by multiplying the entire inequality by -1. An equality constraint ( = ) can be replaced by two inequalities: one of '≤' type and one of '≥' type.

1.3 Formulation of an LPP: An Example

Let's consider a company that manufactures two products, A and B. Each unit of product A requires 2 hours of machine time and 1 hour of labor, and yields a profit of $5. Each unit of product B requires 3 hours of machine time and 2 hours of labor, and yields a profit of $7. The company has 100 hours of machine time and 80 hours of labor available per week. The company can sell at most 40 units of product A and at most 30 units of product B per week. Formulate this problem as a Linear Programming Problem.

Step 1: Define Decision Variables Let x₁ be the number of units of product A to produce per week. Let x₂ be the number of units of product B to produce per week.

Step 2: Define the Objective Function The company wants to maximize its profit. Maximize Z = 5x₁ + 7x₂

Step 3: Define the Constraints Machine time constraint: 2x₁ + 3x₂ ≤ 100 Labor constraint: 1x₁ + 2x₂ ≤ 80 Demand constraint for A: x₁ ≤ 40 Demand constraint for B: x₂ ≤ 30 Non-negativity constraints: x₁ ≥ 0, x₂ ≥ 0

Complete LPP Formulation: Maximize Z = 5x₁ + 7x₂ Subject to: 2x₁ + 3x₂ ≤ 100 x₁ + 2x₂ ≤ 80 x₁ ≤ 40 x₂ ≤ 30 x₁ ≥ 0, x₂ ≥ 0

2. Graphical Method for Solving LPP

The graphical method is suitable for LPPs with only two decision variables. It involves plotting the constraints on a graph, identifying the feasible region, and then finding the optimal solution at one of the corner points of this feasible region.

2.1 Steps for Graphical Method

1. Plot the Constraints: For each linear inequality constraint, treat it as an equation and plot the corresponding line on a graph. For example, for 2x₁ + 3x₂ ≤ 100, plot the line 2x₁ + 3x₂ = 100.
2. Identify the Feasible Region: For each constraint, determine which side of the line satisfies the inequality. The feasible region is the area on the graph where all constraints are satisfied simultaneously. This region is usually a polygon.
3. Determine the Corner Points: The corner points (or vertices) of the feasible region are the points where the boundary lines intersect. These points represent potential optimal solutions.
4. Evaluate the Objective Function: Substitute the coordinates of each corner point into the objective function.
5. Find the Optimal Solution: The corner point that yields the maximum value for a maximization problem (or minimum value for a minimization problem) is the optimal solution.

2.2 Example using Graphical Method

Let's solve the following LPP graphically: Maximize Z = 3x₁ + 2x₂ Subject to: x₁ + x₂ ≤ 4 x₁ - x₂ ≤ 2 x₁ ≥ 0, x₂ ≥ 0

Step 1: Plot the lines Line 1: x₁ + x₂ = 4 (Intercepts at (4,0) and (0,4)) Line 2: x₁ - x₂ = 2 (Intercepts at (2,0) and (0,-2)) Non-negativity: x₁ ≥ 0 (y-axis), x₂ ≥ 0 (x-axis)

Step 2: Identify the Feasible Region For x₁ + x₂ ≤ 4, the region is below or on the line. For x₁ - x₂ ≤ 2, the region is above or on the line (test (0,0): 0-0 ≤ 2, true). The feasible region is the area bounded by the x₁-axis, the x₂-axis, and the two lines, satisfying all inequalities.

Step 3: Determine Corner Points The corner points are: A: (0,0) - Intersection of x₁=0 and x₂=0 B: (2,0) - Intersection of x₁ - x₂ = 2 and x₂=0 C: Intersection of x₁ + x₂ = 4 and x₁ - x₂ = 2 Adding the two equations: 2x₁ = 6 => x₁ = 3. Substituting x₁=3 into x₁ + x₂ = 4 => 3 + x₂ = 4 => x₂ = 1. So, C = (3,1). D: (0,4) - Intersection of x₁ + x₂ = 4 and x₁=0

Step 4 & 5: Evaluate Objective Function and Find Optimal Solution Evaluate Z = 3x₁ + 2x₂ at each corner point: At A(0,0): Z = 3(0) + 2(0) = 0 At B(2,0): Z = 3(2) + 2(0) = 6 At C(3,1): Z = 3(3) + 2(1) = 9 + 2 = 11 At D(0,4): Z = 3(0) + 2(4) = 8

The maximum value of Z is 11, which occurs at point C(3,1). So, the optimal solution is x₁ = 3 and x₂ = 1, with a maximum profit of $11.

3. The Simplex Method

The Simplex Method is an algebraic procedure for solving LPPs. It is more versatile than the graphical method and can handle problems with any number of variables. It iteratively moves from one basic feasible solution to another, seeking to improve the objective function value at each step, until the optimal solution is reached.

3.1 Key Concepts in Simplex Method

• Basic Variables: In a system of 'm' linear equations with 'n' variables (n > m), a basic solution is obtained by setting (n-m) variables to zero and solving for the remaining 'm' variables. The 'm' variables that are solved for are called basic variables, and the (n-m) variables set to zero are called non-basic variables.
• Basic Feasible Solution (BFS): A basic solution that also satisfies all the non-negativity constraints (all variables ≥ 0) is called a basic feasible solution.
• Feasible Region: The set of all points satisfying the constraints of an LPP.
• Optimal Solution: A feasible solution that optimizes (maximizes or minimizes) the objective function.

3.2 Steps for Simplex Method (Maximization Problem)

To apply the Simplex method, the LPP must be converted into a specific format, often called the "canonical form" or "standard form for simplex".

1. Convert to Standard Form:
   • Objective function should be maximization.
   • All constraints must be equalities. Introduce slack variables for '≤' constraints and surplus variables for '≥' constraints.
   • All variables (original, slack, surplus) must be non-negative.
   Slack Variables: For a constraint of the form a₁x₁ + ... + a_nx_n ≤ b, add a non-negative slack variable s_i to make it an equality: a₁x₁ + ... + a_nx_n + s_i = b. The slack variable represents the unused amount of the resource. Surplus Variables: For a constraint of the form a₁x₁ + ... + a_nx_n ≥ b, subtract a non-negative surplus variable e_i to make it an equality: a₁x₁ + ... + a_nx_n - e_i = b. The surplus variable represents the amount by which the left side exceeds the right side.
2. Set up the Initial Simplex Tableau: The tableau is a table that organizes the coefficients of the LPP.
   • The first column typically indicates the basic variables.
   • The next columns represent the coefficients of the variables (original, slack, surplus).
   • The last column is the 'Right Hand Side' (RHS) values of the constraints.
   • The bottom row (often called the Z_j - C_j row or Row 0) represents the objective function coefficients and their current values.
   The initial basic feasible solution usually consists of the slack variables as basic variables and all original variables as non-basic.
3. Identify the Entering Variable (Pivot Column): Look at the Z_j - C_j row. For a maximization problem, the variable corresponding to the most negative value in this row is selected as the entering variable. This variable will enter the basis to improve the objective function. If all values in the Z_j - C_j row are non-negative, the current solution is optimal.
4. Identify the Leaving Variable (Pivot Row): For each row where the entry in the pivot column is positive, calculate the ratio of the RHS value to the pivot column entry. The row with the smallest non-negative ratio is selected as the pivot row. The basic variable in this row will leave the basis.
5. Perform Pivot Operation: Use Gaussian elimination (or row operations) to make the pivot element (the element at the intersection of the pivot row and pivot column) equal to 1, and all other elements in the pivot column equal to 0. This updates the tableau to reflect the new basic feasible solution.
6. Repeat: Go back to Step 3 and repeat the process until the optimal solution is found (i.e., all values in the Z_j - C_j row are non-negative).

3.3 Example using Simplex Method (Maximization)

Solve the following LPP using the Simplex method: Maximize Z = 3x₁ + 2x₂ Subject to: x₁ + x₂ ≤ 4 x₁ - x₂ ≤ 2 x₁ ≥ 0, x₂ ≥ 0

Step 1: Convert to Standard Form Introduce slack variables s₁ and s₂. Maximize Z = 3x₁ + 2x₂ + 0s₁ + 0s₂ Subject to: x₁ + x₂ + s₁ = 4 x₁ - x₂ + s₂ = 2 x₁, x₂, s₁, s₂ ≥ 0

Rewrite the objective function as Z - 3x₁ - 2x₂ = 0.

3.4 Initial Simplex Tableau

The initial basic feasible solution is s₁ = 4, s₂ = 2, x₁ = 0, x₂ = 0. Basic variables are s₁, s₂.

Basis	x1	x2	s1	s2	RHS
s1	1	1	1	0	4
s2	1	-1	0	1	2
Zj - Cj	-3	-2	0	0	0

3.5 Iteration 1

Step 3: Entering Variable The most negative value in the Z_j - C_j row is -3, corresponding to x₁. So, x₁ enters the basis.

Step 4: Leaving Variable Calculate ratios: Row s₁: 4 / 1 = 4 Row s₂: 2 / 1 = 2 The smallest ratio is 2, corresponding to row s₂. So, s₂ leaves the basis. The pivot element is 1 (intersection of x₁ column and s₂ row).

Step 5: Pivot Operation The pivot element is already 1. We need to make other elements in the x₁ column zero. New Row s₂ = Old Row s₂ (This row is already the pivot row). New Row s₁ = Old Row s₁ - 1 * (New Row s₂) New Z_j - C_j = Old Z_j - C_j - (-3) * (New Row s₂)

Basis	x1	x2	s1	s2	RHS
s1	0	2	1	-1	2
x1	1	-1	0	1	2
Zj - Cj	0	-5	0	3	6

New Z_j - C_j calculation: Row s₁: [1 1 1 0 4] - 1 * [1 -1 0 1 2] = [0 2 1 -1 2] Row Z_j - C_j: [-3 -2 0 0 0] - (-3) * [1 -1 0 1 2] = [-3 -2 0 0 0] + [3 -3 0 3 6] = [0 -5 0 3 6]

3.6 Iteration 2

Step 3: Entering Variable The most negative value in Z_j - C_j is -5, corresponding to x₂. So, x₂ enters the basis.

Step 4: Leaving Variable Calculate ratios: Row s₁: 2 / 2 = 1 Row x₁: 2 / (-1) = -2 (Ignore negative ratios) The smallest non-negative ratio is 1, corresponding to row s₁. So, s₁ leaves the basis. The pivot element is 2 (intersection of x₂ column and s₁ row).

Step 5: Pivot Operation Divide the pivot row (s₁ row) by the pivot element (2). New Row x₂ = (1/2) * Old Row s₁ Then, make other elements in the x₂ column zero. New Row x₁ = Old Row x₁ - (-1) * (New Row x₂) New Z_j - C_j = Old Z_j - C_j - (-5) * (New Row x₂)

Basis	x1	x2	s1	s2	RHS
x2	0	1	1/2	-1/2	1
x1	1	0	1/2	1/2	3
Zj - Cj	0	0	5/2	1/2	11

New Row x₂: (1/2) * [0 2 1 -1 2] = [0 1 1/2 -1/2 1] New Row x₁: [1 -1 0 1 2] - (-1) * [0 1 1/2 -1/2 1] = [1 -1 0 1 2] + [0 1 1/2 -1/2 1] = [1 0 1/2 1/2 3] New Z_j - C_j: [0 -5 0 3 6] - (-5) * [0 1 1/2 -1/2 1] = [0 -5 0 3 6] + [0 5 5/2 -5/2 5] = [0 0 5/2 1/2 11]

3.7 Optimal Solution

Since all values in the Z_j - C_j row are non-negative (0, 0, 5/2, 1/2), the optimal solution has been reached.

From the final tableau: Basic variables: x₁ = 3, x₂ = 1 Non-basic variables: s₁ = 0, s₂ = 0 Maximum value of Z = 11

This matches the result obtained from the graphical method.

4. Duality in Linear Programming

Every Linear Programming Problem (the primal problem) has an associated Linear Programming Problem called its dual problem. The optimal solution of the dual problem provides valuable insights into the optimal solution of the primal problem.

4.1 Relationship between Primal and Dual Problems

The dual of a maximization problem is a minimization problem, and vice versa. If the primal has 'm' constraints and 'n' variables, the dual will have 'n' constraints and 'm' variables. The constraints of the dual are derived from the coefficients of the primal's objective function, and the objective function of the dual is derived from the RHS values of the primal's constraints.

4.2 Constructing the Dual Problem

Let the primal problem be: Maximize Z = c₁x₁ + c₂x₂ + ... + c_nx_n Subject to: a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁ a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂ ... a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m x_j ≥ 0 for all j = 1, ..., n

The corresponding dual problem is: Minimize W = b₁y₁ + b₂y₂ + ... + b_my_m Subject to: a₁₁y₁ + a₂₁y₂ + ... + a_m1y_m ≥ c₁ a₁₂y₁ + a₂₂y₂ + ... + a_m2y_m ≥ c₂ ... a_1ny₁ + a_2ny₂ + ... + a_mny_m ≥ c_n y_i ≥ 0 for all i = 1, ..., m

Key Transformation Rules:

• The coefficients of the primal's constraints become the coefficients of the dual's objective function (transposed).
• The coefficients of the primal's objective function become the RHS values of the dual's constraints.
• The RHS values of the primal's constraints become the coefficients of the dual's objective function.
• '≤' constraints in primal correspond to '≥' constraints in dual, and variables are non-negative.
• '≥' constraints in primal correspond to '≤' constraints in dual, and variables are non-positive (or convert primal to maximization with negative objective and use standard rules).
• '=' constraints in primal correspond to unrestricted variables in dual.

4.3 Duality Theorem

The Duality Theorem states that:

• If the primal problem has an optimal solution, then the dual problem also has an optimal solution, and the optimal objective function values are equal (Z* = W*).
• If either problem has an unbounded solution, then the other problem has no feasible solution.

Shadow Prices: The optimal values of the dual variables (y_i) are known as shadow prices. The shadow price of a resource (constraint) indicates the marginal increase in the optimal objective function value per unit increase in the availability of that resource. For example, if y₁ is the dual variable corresponding to the first primal constraint (resource 1), and y₁ = $5 at the optimum, it means that increasing the availability of resource 1 by one unit would increase the maximum profit by $5, provided the change is small enough not to alter the optimal basis.

5. Applications and Extensions

Linear Programming is a fundamental tool with broad applications:

• Production Planning: Determining optimal production quantities for different products to maximize profit or minimize cost, given resource limitations.
• Resource Allocation: Allocating limited resources (budget, personnel, machinery) to various projects or activities to achieve the best outcome.
• Diet Problems: Finding the cheapest combination of foods that satisfies nutritional requirements.
• Transportation Problems: Minimizing the cost of shipping goods from multiple sources to multiple destinations.
• Assignment Problems: Assigning tasks to workers to minimize total cost or time.

Extensions of Linear Programming include:

• Integer Programming (IP): Problems where some or all decision variables must be integers.
• Mixed-Integer Programming (MIP): Problems with both integer and continuous variables.
• Non-linear Programming (NLP): Problems where the objective function or constraints are non-linear.