The simplex method of linear optimization simply explained

Modeling of linear programs

When modeling linear programs, various parameters such as B. Processing times of workpieces or machine capacities can be determined. Then an objective function is defined, which is to be maximized under certain constraints. The objective function is often the profit function, as maximizing net profit is a key objective for companies. The constraints are described by the scarcity of resources (e.g. B. Capacity, time, space). You can then solve the problem using the simplex method.

• You can learn the procedure for creating linear models particularly easily if you make yourself a simple example: Assume you have three machines M₁, M₂ and M₃ on which the two products P₁ and P₂ should be produced. The machines have different capacities, and it takes time to process a certain product on the machines for different lengths of time and the finished end products generate different profits away.
  instagram viewer
• We are now looking for the production program with the maximum profit, i.e. the production program in which the greatest profit is achieved.

Example with numerical values ​​and introduction to the simplex method

In the next step you need concrete numerical values ​​to model your problem. Assume that for editing P₁ on M₁ 2 hours accrue on M₂ 3 hours and on M₃ 4 hours. For P₂ fall on M₁ 4 hours on, on M₂ 5 hours and on M₃ 3 hours. The machine capacities for M₁ 500 hours, for M₂ 300 hours and for M3 600 hours. The profits for the finished end products P₁ are 3 euros / piece, for the finished end products P₂ 4 euros / piece.

1. It is best to create a table with three rows and three columns, with additional space for the headings of the rows and columns. Should leave columns. For example, the processing time of P is in the "Column 1 and Row 1" field₁ on M₁, in the field "Column 2 and Line 3" the processing time of P₂ on M₃. Column 3 shows the machine capacities of the three machines.


The Gaussian algorithm of linear systems of equations explained in a nutshell

You will encounter linear systems of equations for the first time in middle school on ...

2. Now you need two variables x₁, x₂ define the production quantities of P₁ and P₂ correspond.
3. So you get the constraints 2x₁+ 4x₂ ≤ 500 (machine 1), 3x₁+ 5x₂ ≤ 300 (machine 2) and 4x₁+ 3x₂ ≤ 600 (machine 3). In each case, there are inequalities, since the capacities do not have to be fully exhausted.
4. The objective function (profit) to be maximized is G (x₁, x₂) = 3x₁+ 4x₂ -> max.
5. In addition, the non-negativity conditions of x apply to the production quantity₁, x₂ ≥ 0. You see, all equations are linear equations. If you look at them together, you get a linear optimization problem.

Linear optimization and application of the simplex method

The idea for solving a linear program is that the inequalities are eliminated by introducing "slack variables" in Equations and the modified optimization problem is solved as LGS. The simplex method is therefore very similar to the Gaussian algorithm for solving LGS.

1. Example: An airplane is divided by three goods G₁, G₂, G₃ to be loaded with the highest possible total freight value. These have a space requirement of 1, 0.2 or 6 dm³, have a weight of 1, 0, 4 and 8 kg and a value of 10, 3 or 50 Euros. How is the aircraft ideally loaded when the cargo space is 2000dm³ and it can carry a maximum of 3000 kg of cargo?
2. You define x₁, x₂, x₃ as quantities of goods G₁, G₂, G₃.
3. You can now set up the constraints with slack variables as follows: x₁+ 0.4x₂+ 8x₃+ x₄ = 3000 and x₁+ 0.2x₂+ 6x₃+ x₅ = 2000. The objective function (total freight value) is G (x₁, x₂, x₃) = 10x₁+ 3x₂+ 50x₃ -> max. You can change this by bringing all variables to one page (G-10x₁-3x₂-50x₃ = 0).
4. Then set up the Simplex panel. It has 3 rows and 7 columns. On the left side you enter x in the columns₁, x₂, x₃, x₄, x₅ and G as headings. On the right, b is the only column. This is where the optimal quantities of goods and the highest possible total freight value are listed. The third line is the target line. (Check: in the three lines with the above-mentioned headings there are the numbers: Line 1: 1, 0.4, 8, 1, 0, 0, 3000, Line 2: 1, 0.2 6, 0, 1, 0, 2000 and Line 3: -10, -3, -50, 0, 0, 1, 0).
5. Now proceed as when using the Gaussian method to solve an LGS. In the first step you change line 1 resp. Line 2 is sent around and added to the other line so that only a 1 appears in "Line 1 + Column 1" and a 0 in "Line 2 + Column 1". This also changes the values ​​in the target line automatically.
6. In this case, for example, you could multiply row 2 by -1 and add it to row 1 and multiply row 2 by 10 and add to line 3 (control: line 1: 0, 0.2, 2, 1, -1, 0, 1000, line 2: remains the same, line 3: 0, -1, 10, 0, 10, 1, 20.000).
7. In the second step, take column 2 and create a 0 by transforming "Row 2 + Column 2" and then a 1 in "Row 1 and Column 2". Again, it should be noted how the target line changes.
8. For example, the transformation steps would be to multiply row 1 by -1 and add to row 2 and multiply row 1 by 5 and add to row 3 (Check: after performing both steps, the result is: line 1: 0, 1, 10, 5, -5, 0, 5000, line 2: 1, 0, 4, -1, 2, 0, 1000 and line 3: 0, 0, 20, 5, 5, 1, 25.000).
9. You can now read the solutions on the right-hand side of the panel. This results in a total freight value of 25,000 euros, 5000 units of good 1, 1000 units of good 2 and no unit of good 3 are transported.

Please note that solving the simplex tableau only results in an optimal solution if only positive results are shown in the target line on the left after the last reshaping step Counting stand. You have internalized the system after 2-3 other examples and will be able to solve such tasks in a playful way in the future.