Solving linear programming problems

Linear programming is a way to achieve the best results in a mathematical model. This model is represented by linear relationships. The purpose of linear programming is to find the maximum or minimum value of a particular quantity, which can be expressed as an equation in specific constraints. The simplex method is a popular algorithm used to solve linear programming problems.

What is the simplex method?

The simplex method is a step-by-step procedure for solving linear programming problems. It is designed to handle equations with more than two variables and more complex constraints. The beauty of the simplex method is that it turns the problem into a systematic process using a tabular form called a simplex tableau.

Linear programming problem

Before we move further into the simplex method, let's understand what a linear programming problem looks like. A typical linear programming problem will have the following:

1. An objective function to maximize or minimize.
2. Constraints in the form of linear inequalities.
3. Non-negative variables.

For example:

Maximize: Z = 3x + 2y
subject to:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x, y ≥ 0

Here, Z is the objective function you want to maximize. Constraints are represented by inequalities. Both x and y variables must be greater than or equal to zero.

Steps of the simplex method

The simplex method involves several major steps:

Step 1: Convert inequalities into equations

Convert inequalities into equalities by adding slack variables. Slack variables represent the difference between the left and right sides of the inequality.

Consider the constraints:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24

Add the slack variables s1, s2 and s3 to change them:

2x + y + s1 = 18
2x + 3y + s2 = 42
3x + y + s3 = 24

Now, linear equations have slack variables that are initially set to zero.

Step 2: Set up simplex tableau

Create an initial simplex table from the equations you transformed. The table looks something like this:

| x | y | s1 | s2 | s3 | Solution |
, 2 | 1 | 1 | 0 | 0 | 18 |
, 2 | 3 | 0 | 1 | 0 | 42 |
, 3 | 1 | 0 | 0 | 1 | 24 |
, -3 | -2 | 0 | 0 | 0 | 0 |

Note: The bottom row is formed by subtracting the objective function coefficients. This row helps to determine optimization.

Step 3: Identify the pivot element

A pivot element is selected to change the solution in such a way that it takes new dimensions towards the optimal solution. The main points in this process include:

• Select the most negative number in the bottom row of the table. This will be the pivot column.
• Calculate the ratio of the solution values to the coefficients in the pivot column (ignoring zero and negative coefficients). The smallest positive ratio will determine the pivot row.

For example:

Ratio: (18/2) = 9, (42/2) = 21, (24/3) = 8 

The smallest ratio is 8, which corresponds to the pivot row. And for this example, since -3 is the most negative in the bottom row, the pivot column is the one with 3.

Step 4: Perform row operations

Use elementary row operations to change the pivot element to 1 and adjust the other elements in the column to 0. This step ensures convergence toward an optimal solution.

Step 5: Iterate

Repeat steps 3 and 4 until there are no more negative numbers left in the bottom row. When this point is reached, the original feasible solution found is optimal.

A practical example using the simplex method

Crisis

Maximize the function Z = 5x + 4y, subject to:

y + 2x ≤ 20 
2x + 3y ≤ 30 
2x + y ≤ 15 
x, y ≥ 0

Step 1: Convert to equation with slack variable

x + 2y + s1 = 20
2x + 3y + s2 = 30
2x + y + s3 = 15

Step 2: Set up simplex tableau

| x | y | s1 | s2 | s3 | Solution |
, 1 | 2 | 1 | 0 | 0 | 20 |
, 2 | 3 | 0 | 1 | 0 | 30 |
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Step 3: Identify the pivot element

The element with -5 is the pivot column. Calculating the ratio for the third column:

Ratio: (20/1) = 20, (30/2) = 15, (15/2) = 7.5

The smallest positive value is 7.5. The element in (Row 3, Column 1) will be the pivot.

Step 4: Perform row operations

Make the pivot element equal to 1:

| x | y | s1 | s2 | s3 | Solution |
, 1 | 2 | 1 | 0 | 0 | 20 |
| 1 | 1.5| 0 | 0.5| 0 | 7.5 | <- pivot row (pivot element 1 created)
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Adjust the row operations to make the other column elements zero and repeat the process until there are no negatives left in the bottom row.

Step 5: Optimal solution

Through successive iterations, eventually:

| x | y | s1 | s2 | s3 | Solution |
, 1 | 0 | 1 | 1 | 0 | 5 |
| 0 | 1 | 0 | 1.5| 0 | 12.5 |
, 0 | 0 | -1 |-1.5| 1 | -7.5 |
| 0 | 0 | 0 |0.5 | 0 | 35 |

The values x = 5 and y = 12.5 maximize the objective function Z up to a value of 35.

Conclusion

The simplex method is a powerful optimization tool for linear programming. It can handle multiple variables efficiently, guiding towards an optimal point bounded by constraints. The procedural nature allows for in-depth analysis of practical scenarios where resources are limited, ensuring optimal utilization.

Comments