10 Linear Programming

Linear Programming (LP) is a mathematical optimization technique designed to solve problems where an objective function needs to be maximized or minimized under a set of constraints, all of which are linear relationships. LP has a long history in operations research and is increasingly becoming a critical component in the toolkit of data scientists, particularly when optimization and resource allocation problems arise.

In data science, LP bridges mathematical theory with practical application, enabling data-driven decision-making in industries such as logistics, finance, manufacturing, healthcare, and technology. By integrating LP into analytical workflows, businesses and organizations can harness the power of structured optimization to improve efficiency, reduce costs, and make more effective decisions.

10.1 Basic Concepts of LP

LP relies on linear mathematical models involving decision variables, an objective function, and constraints. A Linear Programming problem can be structured as follows:

10.1.1 Objective Function

The objective function defines what needs to be optimized (maximized or minimized):

\[Z = c_1x_1 + c_2x_2 + \dots + c_nx_n\]

Where:

$Z$: Objective function value
$x_1, x_2, \dots, x_n$: Decision variables
$c_1, c_2, \dots, c_n$: Coefficients of decision variables (representing costs, profits, etc.)

Example: Maximize \[Z = 5x + 3y\], where $x$ and $y$ are the decision variables.

10.1.2 Constraints

Constraints restrict the values that decision variables can take:

\[ \begin{aligned} & a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1 \\ & a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \geq b_2 \\ & a_{31}x_1 + a_{32}x_2 + \dots + a_{3n}x_n = b_3 \end{aligned} \]

Where:

$a_{ij}$: Coefficients for the constraints
$b_1, b_2, \dots, b_m$: Limits or capacities of the constraints

Example:
\[ \begin{aligned} & 2x + 3y \leq 60 \, \text{(Labor constraint)} \\ & x + y \leq 20 \, \text{(Material constraint)} \end{aligned} \]

10.1.3 Non-Negativity Restriction

All decision variables must be non-negative, as negative quantities are usually not feasible:
\[x_1, x_2, \dots, x_n \geq 0\]

10.2 Complete Example

A manufacturing company produces two types of products: Product A and Product B. Each product requires working hours and raw materials, which are limited based on the available capacity. Let consider the following video:

Product A requires 2 hours of labor and 1 unit of raw material to be produced.
Product B requires 3 hours of labor and 2 units of raw material to be produced.

The company has a total of 45 hours of labor and 16 units of raw material available.

The company wants to maximize the profit obtained from selling the products: - Profit from each Product A is $2. - Profit from each Product B is $5.

Determine the number of Product A and Product B to be produced in order to maximize the profit, subject to the following constraints:

The total labor hours used for producing Product A and Product B cannot exceed 45 hours.
The total raw material used for producing Product A and Product B cannot exceed 16 units.
The number of products produced cannot be negative, i.e., the number of Product A and Product B must be >= 0.

10.2.1 Linear Programming Model

Let: - $x$ be the number of Product A to be produced. - $y$ be the number of Product B to be produced.

Objective Function

The goal is to maximize profit from the production of both products. The objective function is: \[ Z = 2x + 5y \]

Where:

2 is the profit from each unit of Product A.
5 is the profit from each unit of Product B.

Constraints

The problem has the following constraints based on available labor and materials:

Labor constraint: The total labor hours for both products should not exceed 45 hours: \[ 2x + 3y \leq 45 \]

Where:

$2x$ is the labor hours required for Product A.
$3y$ is the labor hours required for Product B.

Raw material constraint: The total raw material for both products should not exceed 16 units: \[ x + 2y \leq 16 \]

Where:

$x$ is the raw material used for Product A.
$2y$ is the raw material used for Product B.

Non-negativity constraints: The number of products produced cannot be negative: \[ x \geq 0 \]
\[ y \geq 0 \]

Therefore, complete Linear Programming Model

Maximize: \[ Z = 2x + 5y \]

Subject to: \[ \begin{aligned} 2x + 3y & \leq 45 \\ x + 2y & \leq 16 \\ x & \geq 0 \\ y & \geq 0 \end{aligned} \]

10.3 Graphical Method

We will solve this problem step by step using the Graphical Method.

10.3.1 Step 1: Plot the Constraints

Constraint 1: $2x + 3y \leq 45$

Convert this to an equation: \[2x + 3y = 45\]

Solve for $y$ in terms of $x$:

\[y = \frac{45 - 2x}{3}\]
- For $x = 0$, $y = 15$ (Point $(0, 15)$).
- For $y = 0$, $x = 22.5$ (Point $(22.5, 0)$).
Plot the line passing through these points: $(0, 15)$ and $(22.5, 0)$.
Constraint 2: $x + 2y \leq 16$

Convert this to an equation: \[x + 2y = 16\]

Solve for $y$ in terms of $x$: \[y = \frac{16 - x}{2}\]
- For $x = 0$, $y = 8$ (Point $(0, 8)$).
- For $y = 0$, $x = 16$ (Point $(16, 0)$).
Plot the line passing through these points: $(0, 8)$ and $(16, 0)$.

10.3.2 Step 2: Find the Feasible Region

The feasible region is the area where all constraints are satisfied, which is the intersection of the regions determined by:

The area under the line $x + 2y = 16$.
The area under the line $2x + 3y = 45$.
The non-negative region (since $x \geq 0$ and $y \geq 0$).

The feasible region is the area bounded by:

$(0, 8)$, where the second constraint intersects the y-axis.
$(16, 0)$, where the second constraint intersects the x-axis.
The point where the two constraints intersect.

10.3.3 Step 3: Find the Intersection of the Constraints

To find the intersection of the two lines $2x + 3y = 45$ and $x + 2y = 16$, we solve the system of equations:

From $x + 2y = 16$, solve for $x$: \[ x = 16 - 2y \]
Substitute $x = 16 - 2y$ into $2x + 3y = 45$: \[ 2(16 - 2y) + 3y = 45 \] \[ 32 - 4y + 3y = 45 \] \[ -y = 13 \] \[ y = -13 \]

So, the lines intersect at the point $(x, y) = (16, 0)$.

10.3.4 Step 4: Evaluate the Objective Function at Each Vertex

The vertices of the feasible region are the following points:

$(0, 8)$
$(16, 0)$

Now, we substitute these values into the objective function $Z = 2x + 5y$.

At $(0, 8)$: \[Z = 2(0) + 5(8) = 0 + 40 = 40\]
At $(16, 0)$: \[Z = 2(16) + 5(0) = 32 + 0 = 32\]

10.3.5 Step 5: Identify the Optimal Solution

From the calculations, the maximum value of $Z$ occurs at the vertex $(0, 8)$, where $Z = 40$.

Thus, the optimal solution is:

$x = 0$ (no Product A)
$y = 8$ (8 units of Product B)
Maximum Profit = 40

The optimal solution is to produce 0 units of Product A and 8 units of Product B to maximize the profit, which will be 40.

10.4 Simplex Method

The Simplex Method is a widely used algorithm to solve Linear Programming (LP) problems. It is designed to find the optimal solution to problems where the objective function and constraints are linear, which means it optimizes a linear objective function subject to a set of linear constraints.

10.4.1 Key Concepts of the Simplex Method:

Standard Form of Linear Programming Problem: Linear programming problems are typically written in standard form, which ensures all constraints are in the form of inequalities and all variables are non-negative.

A general LP problem can be written as:
- Maximize: \[ Z = c_1x_1 + c_2x_2 + \dots + c_nx_n \]
- Subject to: \[ \begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n & \leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n & \leq b_2 \\ & \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n & \leq b_m \\ x_1, x_2, \dots, x_n & \geq 0 \end{aligned} \]
where:
- ( c_1, c_2, , c_n ) are the coefficients in the objective function,
- ( a_{ij} ) are the coefficients of the constraints,
- ( b_1, b_2, , b_m ) are the constants in the constraints,
- ( x_1, x_2, , x_n ) are the decision variables.
Initial Simplex Table:

The initial Simplex table represents the problem with all variables, including the slack variables (introduced to convert inequalities to equalities). The columns of the table represent the decision variables, slack variables, and the right-hand side of the system.

The general form of the initial Simplex tableau is:

\[ \begin{array}{|c|c|c|c|c|c|} \hline \text{Basic Variables} & x_1 & x_2 & \dots & x_n & \text{RHS} \\ \hline s_1 & a_{11} & a_{12} & \dots & a_{1n} & b_1 \\ s_2 & a_{21} & a_{22} & \dots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ s_m & a_{m1} & a_{m2} & \dots & a_{mn} & b_m \\ \hline Z & c_1 & c_2 & \dots & c_n & 0 \\ \hline \end{array} \]

Where:
- Basic variables: Variables currently in the solution (such as slack variables).
- Non-basic variables: Variables not in the solution, but can potentially enter it.
- RHS (Right-Hand Side): The constants from the constraints.
- Z row: The coefficients of the objective function.
Simplex Algorithm Steps:
1. Initialization: The first Simplex tableau is constructed by converting the problem into a standard form (if necessary) and introducing slack variables to change inequalities into equalities.
2. Iterative Process:
  - Select Pivot Column: Choose the most negative value in the objective row (Z row), since we want to maximize $Z$. This column identifies the variable that should enter the basis.
  - Select Pivot Row: Compute the ratio of the RHS (right-hand side) value to the coefficients of the pivot column for each row. The smallest non-negative ratio indicates the row (constraint) where the pivot should happen.
  - Pivoting: Update the tableau by performing row operations to eliminate the pivot column values, so that only one positive entry remains in the pivot column, representing the entering variable. This process is repeated iteratively.
3. Termination: The algorithm stops when no negative values remain in the objective function row, which means the solution is optimal.

10.4.2 Example Using Simplex Method:

Consider the following LP problem:

Maximize: \[ Z = 3x_1 + 2x_2 \]

Subject to: \[ \begin{aligned} x_1 + x_2 & \leq 4 \\ 2x_1 + x_2 & \leq 5 \\ x_1, x_2 & \geq 0 \end{aligned} \]

Introduce Slack Variables: We introduce slack variables $s_1$ and $s_2$ to convert the inequalities into equalities:

\[ x_1 + x_2 + s_1 = 4 \] \[ 2x_1 + x_2 + s_2 = 5 \]
Formulate the Initial Simplex Table:

We now formulate the initial Simplex tableau:

\[ \begin{array}{|c|c|c|c|c|c|} \hline \text{Basic Variables} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 1 & 1 & 1 & 0 & 4 \\ s_2 & 2 & 1 & 0 & 1 & 5 \\ \hline Z & -3 & -2 & 0 & 0 & 0 \\ \hline \end{array} \]

Where:

Slack variables $s_1$ and $s_2$ are the basic variables,
The last row represents the objective function, with negative coefficients indicating the direction to improve $Z$.

First Iteration:
- We look at the objective function row (Z row). The most negative coefficient is $-3$, so we choose column 1 (representing $x_1$) to enter the basis.
- Now, calculate the ratios for the pivot row: $\frac{RHS}{\text{Pivot Column Value}}$:
  - For row 1: $\frac{4}{1} = 4$
  - For row 2: $\frac{5}{2} = 2.5$
So, we choose row 2 (since the ratio is smaller) for the pivot.
Second Iteration: Repeat the process until no more negative coefficients are found in the Z row.
Optimal Solution: The optimal solution occurs when no more negative values remain in the Z row.

The Simplex method is an efficient iterative process for finding the optimal solution to Linear Programming problems. By updating the tableau step by step, we ensure that each iteration moves closer to the optimal solution. Once there are no more negative coefficients in the Z row, we can declare the solution as optimal.

10.5 Dual Simplex Method

Consider the following Linear Programming (LP) problem:

Maximize: \[ Z = 3x_1 + 2x_2 \]

Subject to: \[ \begin{aligned} x_1 + x_2 & \geq 4 \\ 2x_1 + x_2 & \geq 5 \\ x_1, x_2 & \geq 0 \end{aligned} \]

10.5.1 Step 1: Reformulate to Standard Form

We convert the inequalities into equalities by introducing surplus variables $s_1$ and $s_2$.

\[ \begin{aligned} x_1 + x_2 - s_1 & = 4 \\ 2x_1 + x_2 - s_2 & = 5 \\ x_1, x_2, s_1, s_2 & \geq 0 \end{aligned} \]

Thus, the objective function and constraints become:

Maximize:

\[Z = 3x_1 + 2x_2\]

Subject to: \[ \begin{aligned} x_1 + x_2 - s_1 & = 4 \\ 2x_1 + x_2 - s_2 & = 5 \\ x_1, x_2, s_1, s_2 & \geq 0 \end{aligned} \]

10.5.2 Step 2: Initial Simplex Table

The initial simplex tableau for this problem is:

\[ \begin{array}{|c|c|c|c|c|c|} \hline \text{Basic Variables} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 1 & 1 & -1 & 0 & 4 \\ s_2 & 2 & 1 & 0 & -1 & 5 \\ \hline Z & -3 & -2 & 0 & 0 & 0 \\ \hline \end{array} \]

Where:

The basic variables are $s_1$ and $s_2$.
The objective function is to maximize $Z$, with the negative of the coefficients $-3$ and $-2$ in the Z row.

10.5.3 Step 3: Apply Dual Simplex Method

Check Feasibility of RHS:
We check the RHS of each constraint to ensure it’s feasible (positive).
- Row 1: $RHS = 4$ (positive, feasible)
- Row 2: $RHS = 5$ (positive, feasible)
Since both constraints have positive RHS values, the initial solution is feasible. If any RHS was negative, we would pivot to improve feasibility while maintaining optimality.
Select Pivot Row and Column (if infeasible):
- The Dual Simplex Method would continue with row and column selection if any RHS were negative.
- We would compute the ratios of the RHS to the pivot column and use pivot operations accordingly to make the RHS positive while ensuring the objective function is still optimal.

10.5.4 Step 4: Solution

Since both constraints are feasible, the initial solution is feasible. The tableau for this example indicates we can directly derive the optimal solution.

10.5.5 Final Solution:

The optimal solution is: - $x_1 = 2.5$ - $x_2 = 0$ - $Z = 7.5$

Thus, the maximum value of the objective function is $Z = 7.5$, with $x_1 = 2.5$ and $x_2 = 0$ as the solution.

The Dual Simplex Method is useful for adjusting an existing solution that might not be feasible but is optimal.
By focusing on fixing the feasibility of a solution while maintaining its optimality, we can iteratively improve the solution and arrive at a valid and optimal result.

10.6 Other Methods for Solving LP

10.6.1 Interior Point Method

The Interior Point Method is a class of algorithms used to solve linear programming problems by iterating from the interior of the feasible region. Unlike the Simplex method, which moves along the boundary of the feasible region, the Interior Point method explores the interior.

The Karmarkar’s Algorithm is a well-known example of an interior point method.

Key Steps:

Start with an interior point (a point inside the feasible region).
Gradually approach the optimal solution by traversing the interior of the feasible set.
Iteratively refine the solution until convergence is reached.

This method has proven to be efficient for large-scale linear programming problems, especially those involving millions of variables.

10.6.2 Network Simplex Method

The Network Simplex Method is a specialized version of the Simplex algorithm designed to solve network flow problems. These problems arise in scenarios like transportation, supply chains, and communication networks, where we want to optimize a flow across a network of nodes and arcs.

Key Steps:

Represents the problem in the form of a network with nodes and arcs.
Optimizes flow by updating the arc capacities and node values iteratively.
Focuses on improving flow between different parts of the network to optimize the objective.

This method is particularly effective in network optimization problems like transportation and distribution where the problem can be naturally modeled as a network.

10.6.3 Revised Simplex Method

The Revised Simplex Method is an improvement on the traditional Simplex Method and is especially suitable for problems with large numbers of variables. While the classical Simplex method can become computationally expensive in high-dimensional problems, the Revised Simplex Method reduces the number of matrix operations required.

Key Steps:

Instead of storing the entire simplex tableau, the Revised Simplex Method works with the essential data required to keep track of the current solution, such as the basis matrix.
Iterations proceed by updating the basis matrix as needed while reducing the number of operations.

This method can provide better efficiency in terms of computational cost compared to the traditional Simplex approach.

10.6.4 Karmarkar’s Algorithm

The Karmarkar’s Algorithm is an interior point algorithm introduced by Narendra Karmarkar in 1984. This algorithm is designed to solve convex optimization problems, especially linear programming. It runs in polynomial time and offers significant advantages over the Simplex method, particularly for large-scale problems.

Key Steps:

Starts from an interior point of the feasible region.
Utilizes a series of steps designed to bring the algorithm closer to the optimal solution.
Progressively refines the solution to achieve an optimal outcome within polynomial time.

This method was a breakthrough in the field of Linear Programming due to its polynomial-time performance. It’s particularly helpful in solving very large LP problems.

These methods all offer distinct approaches for solving Linear Programming problems, with advantages and drawbacks depending on the type of problem being solved. While the Simplex Method is commonly used, techniques like Interior Point Methods and the Revised Simplex Method are often better suited for large, complex problems. In certain situations, like network flow problems, specialized algorithms such as the Network Simplex Method can lead to faster solutions.