solve the linear programming problem using the simplex method

max Z = 3x1 + 5x2 + 4x3 subject to 2x1 + 3x2 2x2 + 5x3 3x1 + 2x2 + 4x3 and x1,x2,x3 >= 0
max Z = 5x1 + 10x2 + 8x3 subject to 3x1 + 5x2 + 2x3 4x1 + 4x2 + 4x3 2x1 + 4x2 + 5x3 and x1,x2,x3 >= 0
max Z = 4x1 + 3x2 subject to 2x1 + x2 x1 + x2 x1 x2 and x1,x2 >= 0
=,>=`4,7`');">min Z = x1 + x2 subject to 2x1 + 4x2 >= 4 x1 + 7x2 >= 7 and x1,x2 >= 0
=,>=`80,60`');">min Z = 600x1 + 500x2 subject to 2x1 + x2 >= 80 x1 + 2x2 >= 60 and x1,x2 >= 0
=`12,10,10`');">min Z = 5x1 + 3x2 subject to 2x1 + 4x2 2x1 + 2x2 = 10 5x1 + 2x2 >= 10 and x1,x2 >= 0
max Z = x1 + 2x2 + 3x3 - x4 subject to x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + x3 + x4 = 10 and x1,x2,x3,x4 >= 0
max Z = 3x1 + 9x2 subject to x1 + 4x2 x1 + 2x2 and x1,x2 >= 0
max Z = 3x1 + 2x2 + x3 subject to 2x1 + 5x2 + x3 = 12 3x1 + 4x2 = 11 and x2,x3 >= 0 and x1 unrestricted in sign
max Z = 3x1 + 3x2 + 2x3 + x4 subject to 2x1 + 2x2 + 5x3 + x4 = 12 3x1 + 3x2 + 4x3 = 11 and x1,x2,x3,x4 >= 0
=`30,24,3`');">max Z = 6x1 + 4x2 subject to 2x1 + 3x2 3x1 + 2x2 x1 + x2 >= 3 and x1,x2 >= 0
=`6,10,1`');">max Z = 3x1 + 5x2 subject to x1 - 2x2 x1 x2 >= 1 and x1,x2 >= 0
=`5,8`');">max Z = 6x1 + 4x2 subject to x1 + x2 x2 >= 8 and x1,x2 >= 0
=,>=`-5,8`');">max Z = 6x1 + 4x2 subject to -x1 - x2 >= -5 x2 >= 8 and x1,x2 >= 0

school Campus Bookshelves
menu_book Bookshelves
perm_media Learning Objects
login Login
how_to_reg Request Instructor Account
hub Instructor Commons
Download Page (PDF)
Download Full Book (PDF)
Periodic Table
Physics Constants
Scientific Calculator
Reference & Cite
Tools expand_more
Readability

selected template will load here

This action is not available.

4.2: Maximization By The Simplex Method

Learning Objectives

In this section, you will learn to solve linear programming maximization problems using the Simplex Method:

In the last chapter, we used the geometrical method to solve linear programming problems, but the geometrical approach will not work for problems that have more than two variables. In real life situations, linear programming problems consist of literally thousands of variables and are solved by computers. We can solve these problems algebraically, but that will not be very efficient. Suppose we were given a problem with, say, 5 variables and 10 constraints. By choosing all combinations of five equations with five unknowns, we could find all the corner points, test them for feasibility, and come up with the solution, if it exists. But the trouble is that even for a problem with so few variables, we will get more than 250 corner points, and testing each point will be very tedious. So we need a method that has a systematic algorithm and can be programmed for a computer. The method has to be efficient enough so we wouldn't have to evaluate the objective function at each corner point. We have just such a method, and it is called the simplex method .

The simplex method was developed during the Second World War by Dr. George Dantzig. His linear programming models helped the Allied forces with transportation and scheduling problems. In 1979, a Soviet scientist named Leonid Khachian developed a method called the ellipsoid algorithm which was supposed to be revolutionary, but as it turned out it is not any better than the simplex method. In 1984, Narendra Karmarkar, a research scientist at AT&T Bell Laboratories developed Karmarkar's algorithm which has been proven to be four times faster than the simplex method for certain problems. But the simplex method still works the best for most problems.

The simplex method uses an approach that is very efficient. It does not compute the value of the objective function at every point; instead, it begins with a corner point of the feasibility region where all the main variables are zero and then systematically moves from corner point to corner point, while improving the value of the objective function at each stage. The process continues until the optimal solution is found.

To learn the simplex method, we try a rather unconventional approach. We first list the algorithm, and then work a problem. We justify the reasoning behind each step during the process. A thorough justification is beyond the scope of this course.

We start out with an example we solved in the last chapter by the graphical method. This will provide us with some insight into the simplex method and at the same time give us the chance to compare a few of the feasible solutions we obtained previously by the graphical method. But first, we list the algorithm for the simplex method.

THE SIMPLEX METHOD

Now, we use the simplex method to solve Example 3.1.1 solved geometrically in section 3.1.

Example $\PageIndex{1}$

Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?

In solving this problem, we will follow the algorithm listed above.

STEP 1. Set up the problem. Write the objective function and the constraints.

Since the simplex method is used for problems that consist of many variables, it is not practical to use the variables $x$, $y$, $z$ etc. We use symbols $x_1$, $x_2$, $x_3$, and so on.

It is customary to choose the variable that is to be maximized as $Z$.

The problem is formulated the same way as we did in the last chapter.

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{Z}=40 \mathrm{x}_{1}+30 \mathrm{x}_{2} \\ \textbf { Subject to: } & \mathrm{x}_{1}+\mathrm{x}_{2} \leq 12 \\ & 2 \mathrm{x}_{1}+\mathrm{x}_{2} \leq 16 \\ & \mathrm{x}_{1} \geq 0 ; \mathrm{x}_{2} \geq 0 \end{array}\nonumber \]

STEP 2. Convert the inequalities into equations. This is done by adding one slack variable for each inequality.

For example to convert the inequality $x_1 + x_2 ≤ 12$ into an equation, we add a non-negative variable $y_1$, and we get

\[x_1 + x_2 + y_1 = 12 \nonumber \]

Here the variable $y_1$ picks up the slack, and it represents the amount by which $x_1 + x_2$ falls short of 12. In this problem, if Niki works fewer than 12 hours, say 10, then $y_1$ is 2. Later when we read off the final solution from the simplex table, the values of the slack variables will identify the unused amounts.

We rewrite the objective function $Z = 40x_1 + 30x_2$ as $- 40x_1 - 30x_2 + Z = 0$.

After adding the slack variables, our problem reads

\[\begin{array}{ll} \text { Objective function } & - 40x_1 - 30x_2 + Z = 0 \\ \text { Subject to constraints: } & x_1 + x_2 + y_1 = 12 \\ & 2x_1 + x_2 + y_2 = 16 \\ & x1 ≥ 0; x2 ≥ 0 \end{array} \nonumber \]

STEP 3. Construct the initial simplex tableau . Each inequality constraint appears in its own row. (The non-negativity constraints do not appear as rows in the simplex tableau.) Write the objective function as the bottom row.

Now that the inequalities are converted into equations, we can represent the problem into an augmented matrix called the initial simplex tableau as follows.

$Example4.2.1a.png$

Here the vertical line separates the left hand side of the equations from the right side. The horizontal line separates the constraints from the objective function. The right side of the equation is represented by the column C.

The reader needs to observe that the last four columns of this matrix look like the final matrix for the solution of a system of equations. If we arbitrarily choose $x_1 = 0$ and $x_2 = 0$, we get

\[\left[\begin{array}{ccccc} y_{1} & y_{2} & Z & | & C \\ 1 & 0 & 0 & | & 12 \\ 0 & 1 & 0 & | & 16 \\ 0 & 0 & 1 & | & 0 \end{array}\right]\nonumber \]

which reads

\[y_1 = 12 \quad y_2 = 16 \quad Z = 0 \nonumber \]

The solution obtained by arbitrarily assigning values to some variables and then solving for the remaining variables is called the basic solution associated with the tableau. So the above solution is the basic solution associated with the initial simplex tableau. We can label the basic solution variable in the right of the last column as shown in the table below.

$Example4.2.1b.png$

STEP 4. The most negative entry in the bottom row identifies the pivot column.

The most negative entry in the bottom row is -40; therefore the column 1 is identified.

$Example4.2.1c.png$

Question Why do we choose the most negative entry in the bottom row?

Answer The most negative entry in the bottom row represents the largest coefficient in the objective function - the coefficient whose entry will increase the value of the objective function the quickest.

The simplex method begins at a corner point where all the main variables, the variables that have symbols such as $x_1$, $x_2$, $x_3$ etc., are zero. It then moves from a corner point to the adjacent corner point always increasing the value of the objective function. In the case of the objective function $Z = 40x_1+ 30x_2$, it will make more sense to increase the value of $x_1$ rather than $x_2$. The variable $x_1$ represents the number of hours per week Niki works at Job I. Since Job I pays $40 per hour as opposed to Job II which pays only $30, the variable $x_1$ will increase the objective function by $40 for a unit of increase in the variable $x_1$.

STEP 5. Calculate the quotients. The smallest quotient identifies a row. The element in the intersection of the column identified in step 4 and the row identified in this step is identified as the pivot element.

Following the algorithm, in order to calculate the quotient, we divide the entries in the far right column by the entries in column 1, excluding the entry in the bottom row.

$Example4.2.1e.png$

The smallest of the two quotients, 12 and 8, is 8. Therefore row 2 is identified. The intersection of column 1 and row 2 is the entry 2, which has been highlighted. This is our pivot element.

Question Why do we find quotients, and why does the smallest quotient identify a row?

Answer When we choose the most negative entry in the bottom row, we are trying to increase the value of the objective function by bringing in the variable $x_1$. But we cannot choose any value for $x_1$. Can we let $x_1 = 100$? Definitely not! That is because Niki never wants to work for more than 12 hours at both jobs combined: $x_1 + x_2 ≤ 12$. Can we let $x_1 = 12$? Again, the answer is no because the preparation time for Job I is two times the time spent on the job. Since Niki never wants to spend more than 16 hours for preparation, the maximum time she can work is 16 ÷ 2 = 8.

Now you see the purpose of computing the quotients; using the quotients to identify the pivot element guarantees that we do not violate the constraints.

Question Why do we identify the pivot element?

Answer As we have mentioned earlier, the simplex method begins with a corner point and then moves to the next corner point always improving the value of the objective function. The value of the objective function is improved by changing the number of units of the variables. We may add the number of units of one variable, while throwing away the units of another. Pivoting allows us to do just that.

The variable whose units are being added is called the entering variable , and the variable whose units are being replaced is called the departing variable . The entering variable in the above table is $x_1$, and it was identified by the most negative entry in the bottom row. The departing variable $y_2$ was identified by the lowest of all quotients.

STEP 6. Perform pivoting to make all other entries in this column zero.

In chapter 2, we used pivoting to obtain the row echelon form of an augmented matrix. Pivoting is a process of obtaining a 1 in the location of the pivot element, and then making all other entries zeros in that column. So now our job is to make our pivot element a 1 by dividing the entire second row by 2. The result follows.

$Example4.2.1f.png$

To obtain a zero in the entry first above the pivot element, we multiply the second row by -1 and add it to row 1. We get

$Example4.2.1g.png$

To obtain a zero in the element below the pivot, we multiply the second row by 40 and add it to the last row.

$Example4.2.1h.png$

We now determine the basic solution associated with this tableau. By arbitrarily choosing $x_2 = 0$ and $y_2 = 0$, we obtain $x_1 = 8$, $y_1 = 4$, and $z = 320$. If we write the augmented matrix, whose left side is a matrix with columns that have one 1 and all other entries zeros, we get the following matrix stating the same thing.

\[\left[\begin{array}{ccccc} \mathrm{x}_{1} & \mathrm{y}_1 & \mathrm{Z} & | & \mathrm{C} \\ 0 & 1 & 0 & | & 4 \\ 1 & 0 & 0 & | & 8 \\ 0 & 0 & 1 & | & 320 \end{array}\right] \nonumber \]

We can restate the solution associated with this matrix as $x_1 = 8$, $x_2 = 0$, $y_1 = 4$, $y_2 = 0$ and $z = 320$. At this stage of the game, it reads that if Niki works 8 hours at Job I, and no hours at Job II, her profit Z will be $320. Recall from Example 3.1.1 in section 3.1 that (8, 0) was one of our corner points. Here $y_1 = 4$ and $y_2 = 0$ mean that she will be left with 4 hours of working time and no preparation time.

STEP 7. When there are no more negative entries in the bottom row, we are finished; otherwise, we start again from step 4.

Since there is still a negative entry, -10, in the bottom row, we need to begin, again, from step 4. This time we will not repeat the details of every step, instead, we will identify the column and row that give us the pivot element, and highlight the pivot element. The result is as follows.

$Example4.2.1i.png$

We make the pivot element 1 by multiplying row 1 by 2, and we get

$Example4.2.1j.png$

Now to make all other entries as zeros in this column, we first multiply row 1 by -1/2 and add it to row 2, and then multiply row 1 by 10 and add it to the bottom row.

$Example4.2.1k.png$

We no longer have negative entries in the bottom row, therefore we are finished.

Question Why are we finished when there are no negative entries in the bottom row?

Answer The answer lies in the bottom row. The bottom row corresponds to the equation:

\[\begin{array}{l} 0 x_{1}+0 x_{2}+20 y_{1}+10 y_{2}+Z=400 \quad \text { or } \\ z=400-20 y 1-10 y 2 \end{array}\nonumber \]

Since all variables are non-negative, the highest value $Z$ can ever achieve is 400, and that will happen only when $y_1$ and $y_2$ are zero.

STEP 8. Read off your answers.

We now read off our answers, that is, we determine the basic solution associated with the final simplex tableau. Again, we look at the columns that have a 1 and all other entries zeros. Since the columns labeled $y_1$ and $y_2$ are not such columns, we arbitrarily choose $y_1 = 0$, and $y_2 = 0$, and we get

\[\left[\begin{array}{ccccc} \mathrm{x}_{1} & \mathrm{x}_{2} & \mathrm{Z} & | & \mathrm{C} \\ 0 & 1 & 0 & | & 8 \\ 1 & 0 & 0 & | & 4 \\ 0 & 0 & 1 & | & 400 \end{array}\right] \nonumber \]

The matrix reads $x_1 = 4$, $x_2= 8$ and $z = 400$.

The final solution says that if Niki works 4 hours at Job I and 8 hours at Job II, she will maximize her income to $400. Since both slack variables are zero, it means that she would have used up all the working time, as well as the preparation time, and none will be left.

Solve Linear Programming Problem Using Simplex Method

The given below is the online simplex method calculator which is designed to solve linear programming problem using the simplex algorithm as soon as you input the values.

Linear Programming Simplex Algorithm Calculation

Linear Programming: It is a method used to find the maximum or minimum value for linear objective function. It is a special case of mathematical programming. Simplex Method: It is one of the solution method used in linear programming problems that involves two variables or a large number of constraint. The solution for constraints equation with nonzero variables is called as basic variables. It is the systematic way of finding the optimal value of the objective function. Simplex Algorithm Calculator: Try this online Simplex method calculator to solve a linear programming problem with ease. This Linear programming calculator can also generate the example fo your inputs.

Related Calculators:

Calculators and Converters

Top Calculators

Popular calculators.

Top Categories

Online Calculator: Simplex Method

Traveling Salesman Problem

Dynamic Programming

Mobile app:

Solve linear programming tasks offline!

Solution example

Next, you need to get rid of inequalities, for which we introduce compensating variables in the left-hand side of the inequalities. If an inequality of the form ≤, then the compensating variable has the sign +, if the inequality of the form ≥, then the compensating variable has the sign -. Compensating variables are included in the objective function of the problem with a zero coefficient.

Transfer to the table the basic elements that we identified in the preliminary stage:

Each cell of this column is equal to the coefficient, which corresponds to the base variable in the corresponding row.

At this stage, no calculations are needed, just transfer the values from the preliminary stage to the corresponding table cells:

P 3 = 1000;

x 4,6 = -1;

x 5,7 = -1;

We calculate the value of the objective function by elementwise multiplying the column Cb by the column P, adding the results of the products.

We calculate the estimates for each controlled variable, by element-wise multiplying the value from the variable column, by the value from the Cb column, summing up the results of the products, and subtracting the coefficient of the objective function from their sum, with this variable.

Max x 1 = ((Cb 1 * x 1,1 ) + (Cb 2 * x 2,1 ) + (Cb 3 * x 3,1 ) + (Cb 4 * x 4,1 ) + (Cb 5 * x 5,1 ) ) - k x 1 = ((0 * 2) + (0 * 0) + (0 * 5) + (-M * 0) + (-M * 0) ) - 3 = -3;

Max x 2 = ((Cb 1 * x 1,2 ) + (Cb 2 * x 2,2 ) + (Cb 3 * x 3,2 ) + (Cb 4 * x 4,2 ) + (Cb 5 * x 5,2 ) ) - k x 2 = ((0 * 1) + (0 * 0) + (0 * 4) + (-M * 2) + (-M * 0) ) - 4 = -2M-4;

Max x 3 = ((Cb 1 * x 1,3 ) + (Cb 2 * x 2,3 ) + (Cb 3 * x 3,3 ) + (Cb 4 * x 4,3 ) + (Cb 5 * x 5,3 ) ) - k x 3 = ((0 * 1) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Max x 4 = ((Cb 1 * x 1,4 ) + (Cb 2 * x 2,4 ) + (Cb 3 * x 3,4 ) + (Cb 4 * x 4,4 ) + (Cb 5 * x 5,4 ) ) - k x 4 = ((0 * 0) + (0 * 1) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Max x 5 = ((Cb 1 * x 1,5 ) + (Cb 2 * x 2,5 ) + (Cb 3 * x 3,5 ) + (Cb 4 * x 4,5 ) + (Cb 5 * x 5,5 ) ) - k x 5 = ((0 * 0) + (0 * 0) + (0 * 1) + (-M * 0) + (-M * 0) ) - 0 = 0;

Max x 6 = ((Cb 1 * x 1,6 ) + (Cb 2 * x 2,6 ) + (Cb 3 * x 3,6 ) + (Cb 4 * x 4,6 ) + (Cb 5 * x 5,6 ) ) - k x 6 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * -1) + (-M * 0) ) - 0 = M;

Max x 7 = ((Cb 1 * x 1,7 ) + (Cb 2 * x 2,7 ) + (Cb 3 * x 3,7 ) + (Cb 4 * x 4,7 ) + (Cb 5 * x 5,7 ) ) - k x 7 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * -1) ) - 0 = M;

Max x 8 = ((Cb 1 * x 1,8 ) + (Cb 2 * x 2,8 ) + (Cb 3 * x 3,8 ) + (Cb 4 * x 4,8 ) + (Cb 5 * x 5,8 ) ) - k x 8 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 1) + (-M * 0) ) - -M = 0;

Max x 9 = ((Cb 1 * x 1,9 ) + (Cb 2 * x 2,9 ) + (Cb 3 * x 3,9 ) + (Cb 4 * x 4,9 ) + (Cb 5 * x 5,9 ) ) - k x 9 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 1) ) - -M = 0;

Since there are negative values among the estimates of the controlled variables, the current table does not yet have an optimal solution. Therefore, in the basis we introduce the variable with the smallest negative estimate.

The number of variables in the basis is always constant, so it is necessary to choose which variable to derive from the basis, for which we calculate Q.

The elements of the Q column are calculated by dividing the values from column P by the value from the column corresponding to the variable that is entered in the basis:

Q 1 = P 1 / x 1,2 = 600 / 1 = 600;

Q 2 = P 2 / x 2,2 = 225 / 0 = ∞;

Q 3 = P 3 / x 3,2 = 1000 / 4 = 250;

Q 4 = P 4 / x 4,2 = 150 / 2 = 75;

Q 5 = P 5 / x 5,2 = 0 / 0 = ∞;

We deduce from the basis the variable with the least positive value of Q.

At the intersection of the line that corresponds to the variable that is derived from the basis, and the column that corresponds to the variable that is entered into the basis, is the resolving element.

For the results of the calculations of the previous iteration, we remove the variable from the basis x 8 and put in her place x 2 . All other cells remain unchanged.

We transfer the row with the resolving element from the previous table into the current table, elementwise dividing its values into the resolving element:

P 4 = P 4 / x 4,2 = 150 / 2 = 75;

x 4,1 = x 4,1 / x 4,2 = 0 / 2 = 0;

x 4,2 = x 4,2 / x 4,2 = 2 / 2 = 1;

x 4,3 = x 4,3 / x 4,2 = 0 / 2 = 0;

x 4,4 = x 4,4 / x 4,2 = 0 / 2 = 0;

x 4,5 = x 4,5 / x 4,2 = 0 / 2 = 0;

x 4,6 = x 4,6 / x 4,2 = -1 / 2 = -0.5;

x 4,7 = x 4,7 / x 4,2 = 0 / 2 = 0;

x 4,8 = x 4,8 / x 4,2 = 1 / 2 = 0.5;

x 4,9 = x 4,9 / x 4,2 = 0 / 2 = 0;

The remaining empty cells, except for the row of estimates and the column Q, are calculated using the rectangle method, relative to the resolving element:

P 1 = (P 1 * x 4,2 ) - (x 1,2 * P 4 ) / x 4,2 = ((600 * 2) - (1 * 150)) / 2 = 525;

P 2 = (P 2 * x 4,2 ) - (x 2,2 * P 4 ) / x 4,2 = ((225 * 2) - (0 * 150)) / 2 = 225;

P 3 = (P 3 * x 4,2 ) - (x 3,2 * P 4 ) / x 4,2 = ((1000 * 2) - (4 * 150)) / 2 = 700;

P 5 = (P 5 * x 4,2 ) - (x 5,2 * P 4 ) / x 4,2 = ((0 * 2) - (0 * 150)) / 2 = 0;

x 1,1 = ((x 1,1 * x 4,2 ) - (x 1,2 * x 4,1 )) / x 4,2 = ((2 * 2) - (1 * 0)) / 2 = 2;

x 1,2 = ((x 1,2 * x 4,2 ) - (x 1,2 * x 4,2 )) / x 4,2 = ((1 * 2) - (1 * 2)) / 2 = 0;

x 1,4 = ((x 1,4 * x 4,2 ) - (x 1,2 * x 4,4 )) / x 4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x 1,5 = ((x 1,5 * x 4,2 ) - (x 1,2 * x 4,5 )) / x 4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x 1,6 = ((x 1,6 * x 4,2 ) - (x 1,2 * x 4,6 )) / x 4,2 = ((0 * 2) - (1 * -1)) / 2 = 0.5;

x 1,7 = ((x 1,7 * x 4,2 ) - (x 1,2 * x 4,7 )) / x 4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x 1,8 = ((x 1,8 * x 4,2 ) - (x 1,2 * x 4,8 )) / x 4,2 = ((0 * 2) - (1 * 1)) / 2 = -0.5;

x 1,9 = ((x 1,9 * x 4,2 ) - (x 1,2 * x 4,9 )) / x 4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x 2,1 = ((x 2,1 * x 4,2 ) - (x 2,2 * x 4,1 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 2,2 = ((x 2,2 * x 4,2 ) - (x 2,2 * x 4,2 )) / x 4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x 2,4 = ((x 2,4 * x 4,2 ) - (x 2,2 * x 4,4 )) / x 4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

x 2,5 = ((x 2,5 * x 4,2 ) - (x 2,2 * x 4,5 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 2,6 = ((x 2,6 * x 4,2 ) - (x 2,2 * x 4,6 )) / x 4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x 2,7 = ((x 2,7 * x 4,2 ) - (x 2,2 * x 4,7 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 2,8 = ((x 2,8 * x 4,2 ) - (x 2,2 * x 4,8 )) / x 4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x 2,9 = ((x 2,9 * x 4,2 ) - (x 2,2 * x 4,9 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 3,1 = ((x 3,1 * x 4,2 ) - (x 3,2 * x 4,1 )) / x 4,2 = ((5 * 2) - (4 * 0)) / 2 = 5;

x 3,2 = ((x 3,2 * x 4,2 ) - (x 3,2 * x 4,2 )) / x 4,2 = ((4 * 2) - (4 * 2)) / 2 = 0;

x 3,4 = ((x 3,4 * x 4,2 ) - (x 3,2 * x 4,4 )) / x 4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x 3,5 = ((x 3,5 * x 4,2 ) - (x 3,2 * x 4,5 )) / x 4,2 = ((1 * 2) - (4 * 0)) / 2 = 1;

x 3,6 = ((x 3,6 * x 4,2 ) - (x 3,2 * x 4,6 )) / x 4,2 = ((0 * 2) - (4 * -1)) / 2 = 2;

x 3,7 = ((x 3,7 * x 4,2 ) - (x 3,2 * x 4,7 )) / x 4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x 3,8 = ((x 3,8 * x 4,2 ) - (x 3,2 * x 4,8 )) / x 4,2 = ((0 * 2) - (4 * 1)) / 2 = -2;

x 3,9 = ((x 3,9 * x 4,2 ) - (x 3,2 * x 4,9 )) / x 4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x 5,1 = ((x 5,1 * x 4,2 ) - (x 5,2 * x 4,1 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 5,2 = ((x 5,2 * x 4,2 ) - (x 5,2 * x 4,2 )) / x 4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x 5,4 = ((x 5,4 * x 4,2 ) - (x 5,2 * x 4,4 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 5,5 = ((x 5,5 * x 4,2 ) - (x 5,2 * x 4,5 )) / x 4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x 5,6 = ((x 5,6 * x 4,2 ) - (x 5,2 * x 4,6 )) / x 4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x 5,7 = ((x 5,7 * x 4,2 ) - (x 5,2 * x 4,7 )) / x 4,2 = ((-1 * 2) - (0 * 0)) / 2 = -1;

x 5,8 = ((x 5,8 * x 4,2 ) - (x 5,2 * x 4,8 )) / x 4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x 5,9 = ((x 5,9 * x 4,2 ) - (x 5,2 * x 4,9 )) / x 4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

Max x 1 = ((Cb 1 * x 1,1 ) + (Cb 2 * x 2,1 ) + (Cb 3 * x 3,1 ) + (Cb 4 * x 4,1 ) + (Cb 5 * x 5,1 ) ) - k x 1 = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0) ) - 3 = -3;

Max x 2 = ((Cb 1 * x 1,2 ) + (Cb 2 * x 2,2 ) + (Cb 3 * x 3,2 ) + (Cb 4 * x 4,2 ) + (Cb 5 * x 5,2 ) ) - k x 2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Max x 3 = ((Cb 1 * x 1,3 ) + (Cb 2 * x 2,3 ) + (Cb 3 * x 3,3 ) + (Cb 4 * x 4,3 ) + (Cb 5 * x 5,3 ) ) - k x 3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 4 = ((Cb 1 * x 1,4 ) + (Cb 2 * x 2,4 ) + (Cb 3 * x 3,4 ) + (Cb 4 * x 4,4 ) + (Cb 5 * x 5,4 ) ) - k x 4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 5 = ((Cb 1 * x 1,5 ) + (Cb 2 * x 2,5 ) + (Cb 3 * x 3,5 ) + (Cb 4 * x 4,5 ) + (Cb 5 * x 5,5 ) ) - k x 5 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 6 = ((Cb 1 * x 1,6 ) + (Cb 2 * x 2,6 ) + (Cb 3 * x 3,6 ) + (Cb 4 * x 4,6 ) + (Cb 5 * x 5,6 ) ) - k x 6 = ((0 * 0.5) + (0 * 0) + (0 * 2) + (4 * -0.5) + (-M * 0) ) - 0 = -2;

Max x 7 = ((Cb 1 * x 1,7 ) + (Cb 2 * x 2,7 ) + (Cb 3 * x 3,7 ) + (Cb 4 * x 4,7 ) + (Cb 5 * x 5,7 ) ) - k x 7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Max x 8 = ((Cb 1 * x 1,8 ) + (Cb 2 * x 2,8 ) + (Cb 3 * x 3,8 ) + (Cb 4 * x 4,8 ) + (Cb 5 * x 5,8 ) ) - k x 8 = ((0 * -0.5) + (0 * 0) + (0 * -2) + (4 * 0.5) + (-M * 0) ) - -M = M+2;

Max x 9 = ((Cb 1 * x 1,9 ) + (Cb 2 * x 2,9 ) + (Cb 3 * x 3,9 ) + (Cb 4 * x 4,9 ) + (Cb 5 * x 5,9 ) ) - k x 9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Q 1 = P 1 / x 1,1 = 525 / 2 = 262.5;

Q 2 = P 2 / x 2,1 = 225 / 0 = ∞;

Q 3 = P 3 / x 3,1 = 700 / 5 = 140;

Q 4 = P 4 / x 4,1 = 75 / 0 = ∞;

Q 5 = P 5 / x 5,1 = 0 / 0 = ∞;

For the results of the calculations of the previous iteration, we remove the variable from the basis x 5 and put in her place x 1 . All other cells remain unchanged.

P 3 = P 3 / x 3,1 = 700 / 5 = 140;

x 3,1 = x 3,1 / x 3,1 = 5 / 5 = 1;

x 3,2 = x 3,2 / x 3,1 = 0 / 5 = 0;

x 3,3 = x 3,3 / x 3,1 = 0 / 5 = 0;

x 3,4 = x 3,4 / x 3,1 = 0 / 5 = 0;

x 3,5 = x 3,5 / x 3,1 = 1 / 5 = 0.2;

x 3,6 = x 3,6 / x 3,1 = 2 / 5 = 0.4;

x 3,7 = x 3,7 / x 3,1 = 0 / 5 = 0;

x 3,8 = x 3,8 / x 3,1 = -2 / 5 = -0.4;

x 3,9 = x 3,9 / x 3,1 = 0 / 5 = 0;

P 1 = (P 1 * x 3,1 ) - (x 1,1 * P 3 ) / x 3,1 = ((525 * 5) - (2 * 700)) / 5 = 245;

P 2 = (P 2 * x 3,1 ) - (x 2,1 * P 3 ) / x 3,1 = ((225 * 5) - (0 * 700)) / 5 = 225;

P 4 = (P 4 * x 3,1 ) - (x 4,1 * P 3 ) / x 3,1 = ((75 * 5) - (0 * 700)) / 5 = 75;

P 5 = (P 5 * x 3,1 ) - (x 5,1 * P 3 ) / x 3,1 = ((0 * 5) - (0 * 700)) / 5 = 0;

x 1,1 = ((x 1,1 * x 3,1 ) - (x 1,1 * x 3,1 )) / x 3,1 = ((2 * 5) - (2 * 5)) / 5 = 0;

x 1,3 = ((x 1,3 * x 3,1 ) - (x 1,1 * x 3,3 )) / x 3,1 = ((1 * 5) - (2 * 0)) / 5 = 1;

x 1,4 = ((x 1,4 * x 3,1 ) - (x 1,1 * x 3,4 )) / x 3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x 1,5 = ((x 1,5 * x 3,1 ) - (x 1,1 * x 3,5 )) / x 3,1 = ((0 * 5) - (2 * 1)) / 5 = -0.4;

x 1,6 = ((x 1,6 * x 3,1 ) - (x 1,1 * x 3,6 )) / x 3,1 = ((0.5 * 5) - (2 * 2)) / 5 = -0.3;

x 1,7 = ((x 1,7 * x 3,1 ) - (x 1,1 * x 3,7 )) / x 3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x 1,8 = ((x 1,8 * x 3,1 ) - (x 1,1 * x 3,8 )) / x 3,1 = ((-0.5 * 5) - (2 * -2)) / 5 = 0.3;

x 1,9 = ((x 1,9 * x 3,1 ) - (x 1,1 * x 3,9 )) / x 3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x 2,1 = ((x 2,1 * x 3,1 ) - (x 2,1 * x 3,1 )) / x 3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x 2,3 = ((x 2,3 * x 3,1 ) - (x 2,1 * x 3,3 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 2,4 = ((x 2,4 * x 3,1 ) - (x 2,1 * x 3,4 )) / x 3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

x 2,5 = ((x 2,5 * x 3,1 ) - (x 2,1 * x 3,5 )) / x 3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x 2,6 = ((x 2,6 * x 3,1 ) - (x 2,1 * x 3,6 )) / x 3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x 2,7 = ((x 2,7 * x 3,1 ) - (x 2,1 * x 3,7 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 2,8 = ((x 2,8 * x 3,1 ) - (x 2,1 * x 3,8 )) / x 3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x 2,9 = ((x 2,9 * x 3,1 ) - (x 2,1 * x 3,9 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 4,1 = ((x 4,1 * x 3,1 ) - (x 4,1 * x 3,1 )) / x 3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x 4,3 = ((x 4,3 * x 3,1 ) - (x 4,1 * x 3,3 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 4,4 = ((x 4,4 * x 3,1 ) - (x 4,1 * x 3,4 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 4,5 = ((x 4,5 * x 3,1 ) - (x 4,1 * x 3,5 )) / x 3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x 4,6 = ((x 4,6 * x 3,1 ) - (x 4,1 * x 3,6 )) / x 3,1 = ((-0.5 * 5) - (0 * 2)) / 5 = -0.5;

x 4,7 = ((x 4,7 * x 3,1 ) - (x 4,1 * x 3,7 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 4,8 = ((x 4,8 * x 3,1 ) - (x 4,1 * x 3,8 )) / x 3,1 = ((0.5 * 5) - (0 * -2)) / 5 = 0.5;

x 4,9 = ((x 4,9 * x 3,1 ) - (x 4,1 * x 3,9 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 5,1 = ((x 5,1 * x 3,1 ) - (x 5,1 * x 3,1 )) / x 3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x 5,3 = ((x 5,3 * x 3,1 ) - (x 5,1 * x 3,3 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 5,4 = ((x 5,4 * x 3,1 ) - (x 5,1 * x 3,4 )) / x 3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x 5,5 = ((x 5,5 * x 3,1 ) - (x 5,1 * x 3,5 )) / x 3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x 5,6 = ((x 5,6 * x 3,1 ) - (x 5,1 * x 3,6 )) / x 3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x 5,7 = ((x 5,7 * x 3,1 ) - (x 5,1 * x 3,7 )) / x 3,1 = ((-1 * 5) - (0 * 0)) / 5 = -1;

x 5,8 = ((x 5,8 * x 3,1 ) - (x 5,1 * x 3,8 )) / x 3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x 5,9 = ((x 5,9 * x 3,1 ) - (x 5,1 * x 3,9 )) / x 3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

Max x 1 = ((Cb 1 * x 1,1 ) + (Cb 2 * x 2,1 ) + (Cb 3 * x 3,1 ) + (Cb 4 * x 4,1 ) + (Cb 5 * x 5,1 ) ) - k x 1 = ((0 * 0) + (0 * 0) + (3 * 1) + (4 * 0) + (-M * 0) ) - 3 = 0;

Max x 2 = ((Cb 1 * x 1,2 ) + (Cb 2 * x 2,2 ) + (Cb 3 * x 3,2 ) + (Cb 4 * x 4,2 ) + (Cb 5 * x 5,2 ) ) - k x 2 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Max x 3 = ((Cb 1 * x 1,3 ) + (Cb 2 * x 2,3 ) + (Cb 3 * x 3,3 ) + (Cb 4 * x 4,3 ) + (Cb 5 * x 5,3 ) ) - k x 3 = ((0 * 1) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 4 = ((Cb 1 * x 1,4 ) + (Cb 2 * x 2,4 ) + (Cb 3 * x 3,4 ) + (Cb 4 * x 4,4 ) + (Cb 5 * x 5,4 ) ) - k x 4 = ((0 * 0) + (0 * 1) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 5 = ((Cb 1 * x 1,5 ) + (Cb 2 * x 2,5 ) + (Cb 3 * x 3,5 ) + (Cb 4 * x 4,5 ) + (Cb 5 * x 5,5 ) ) - k x 5 = ((0 * -0.4) + (0 * 0) + (3 * 0.2) + (4 * 0) + (-M * 0) ) - 0 = 0.6;

Max x 6 = ((Cb 1 * x 1,6 ) + (Cb 2 * x 2,6 ) + (Cb 3 * x 3,6 ) + (Cb 4 * x 4,6 ) + (Cb 5 * x 5,6 ) ) - k x 6 = ((0 * -0.3) + (0 * 0) + (3 * 0.4) + (4 * -0.5) + (-M * 0) ) - 0 = -0.8;

Max x 7 = ((Cb 1 * x 1,7 ) + (Cb 2 * x 2,7 ) + (Cb 3 * x 3,7 ) + (Cb 4 * x 4,7 ) + (Cb 5 * x 5,7 ) ) - k x 7 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Max x 8 = ((Cb 1 * x 1,8 ) + (Cb 2 * x 2,8 ) + (Cb 3 * x 3,8 ) + (Cb 4 * x 4,8 ) + (Cb 5 * x 5,8 ) ) - k x 8 = ((0 * 0.3) + (0 * 0) + (3 * -0.4) + (4 * 0.5) + (-M * 0) ) - -M = M+0.8;

Max x 9 = ((Cb 1 * x 1,9 ) + (Cb 2 * x 2,9 ) + (Cb 3 * x 3,9 ) + (Cb 4 * x 4,9 ) + (Cb 5 * x 5,9 ) ) - k x 9 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Q 1 = P 1 / x 1,6 = 245 / -0.3 = -816.67;

Q 2 = P 2 / x 2,6 = 225 / 0 = ∞;

Q 3 = P 3 / x 3,6 = 140 / 0.4 = 350;

Q 4 = P 4 / x 4,6 = 75 / -0.5 = -150;

Q 5 = P 5 / x 5,6 = 0 / 0 = ∞;

For the results of the calculations of the previous iteration, we remove the variable from the basis x 1 and put in her place x 6 . All other cells remain unchanged.

P 3 = P 3 / x 3,6 = 140 / 0.4 = 350;

x 3,1 = x 3,1 / x 3,6 = 1 / 0.4 = 2.5;

x 3,2 = x 3,2 / x 3,6 = 0 / 0.4 = 0;

x 3,3 = x 3,3 / x 3,6 = 0 / 0.4 = 0;

x 3,4 = x 3,4 / x 3,6 = 0 / 0.4 = 0;

x 3,5 = x 3,5 / x 3,6 = 0.2 / 0.4 = 0.5;

x 3,6 = x 3,6 / x 3,6 = 0.4 / 0.4 = 1;

x 3,7 = x 3,7 / x 3,6 = 0 / 0.4 = 0;

x 3,8 = x 3,8 / x 3,6 = -0.4 / 0.4 = -1;

x 3,9 = x 3,9 / x 3,6 = 0 / 0.4 = 0;

P 1 = (P 1 * x 3,6 ) - (x 1,6 * P 3 ) / x 3,6 = ((245 * 0.4) - (-0.3 * 140)) / 0.4 = 350;

P 2 = (P 2 * x 3,6 ) - (x 2,6 * P 3 ) / x 3,6 = ((225 * 0.4) - (0 * 140)) / 0.4 = 225;

P 4 = (P 4 * x 3,6 ) - (x 4,6 * P 3 ) / x 3,6 = ((75 * 0.4) - (-0.5 * 140)) / 0.4 = 250;

P 5 = (P 5 * x 3,6 ) - (x 5,6 * P 3 ) / x 3,6 = ((0 * 0.4) - (0 * 140)) / 0.4 = 0;

x 1,1 = ((x 1,1 * x 3,6 ) - (x 1,6 * x 3,1 )) / x 3,6 = ((0 * 0.4) - (-0.3 * 1)) / 0.4 = 0.75;

x 1,2 = ((x 1,2 * x 3,6 ) - (x 1,6 * x 3,2 )) / x 3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x 1,3 = ((x 1,3 * x 3,6 ) - (x 1,6 * x 3,3 )) / x 3,6 = ((1 * 0.4) - (-0.3 * 0)) / 0.4 = 1;

x 1,4 = ((x 1,4 * x 3,6 ) - (x 1,6 * x 3,4 )) / x 3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x 1,5 = ((x 1,5 * x 3,6 ) - (x 1,6 * x 3,5 )) / x 3,6 = ((-0.4 * 0.4) - (-0.3 * 0.2)) / 0.4 = -0.25;

x 1,6 = ((x 1,6 * x 3,6 ) - (x 1,6 * x 3,6 )) / x 3,6 = ((-0.3 * 0.4) - (-0.3 * 0.4)) / 0.4 = 0;

x 1,8 = ((x 1,8 * x 3,6 ) - (x 1,6 * x 3,8 )) / x 3,6 = ((0.3 * 0.4) - (-0.3 * -0.4)) / 0.4 = 0;

x 1,9 = ((x 1,9 * x 3,6 ) - (x 1,6 * x 3,9 )) / x 3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x 2,1 = ((x 2,1 * x 3,6 ) - (x 2,6 * x 3,1 )) / x 3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x 2,2 = ((x 2,2 * x 3,6 ) - (x 2,6 * x 3,2 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 2,3 = ((x 2,3 * x 3,6 ) - (x 2,6 * x 3,3 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 2,4 = ((x 2,4 * x 3,6 ) - (x 2,6 * x 3,4 )) / x 3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

x 2,5 = ((x 2,5 * x 3,6 ) - (x 2,6 * x 3,5 )) / x 3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x 2,6 = ((x 2,6 * x 3,6 ) - (x 2,6 * x 3,6 )) / x 3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x 2,8 = ((x 2,8 * x 3,6 ) - (x 2,6 * x 3,8 )) / x 3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x 2,9 = ((x 2,9 * x 3,6 ) - (x 2,6 * x 3,9 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 4,1 = ((x 4,1 * x 3,6 ) - (x 4,6 * x 3,1 )) / x 3,6 = ((0 * 0.4) - (-0.5 * 1)) / 0.4 = 1.25;

x 4,2 = ((x 4,2 * x 3,6 ) - (x 4,6 * x 3,2 )) / x 3,6 = ((1 * 0.4) - (-0.5 * 0)) / 0.4 = 1;

x 4,3 = ((x 4,3 * x 3,6 ) - (x 4,6 * x 3,3 )) / x 3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x 4,4 = ((x 4,4 * x 3,6 ) - (x 4,6 * x 3,4 )) / x 3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x 4,5 = ((x 4,5 * x 3,6 ) - (x 4,6 * x 3,5 )) / x 3,6 = ((0 * 0.4) - (-0.5 * 0.2)) / 0.4 = 0.25;

x 4,6 = ((x 4,6 * x 3,6 ) - (x 4,6 * x 3,6 )) / x 3,6 = ((-0.5 * 0.4) - (-0.5 * 0.4)) / 0.4 = 0;

x 4,8 = ((x 4,8 * x 3,6 ) - (x 4,6 * x 3,8 )) / x 3,6 = ((0.5 * 0.4) - (-0.5 * -0.4)) / 0.4 = 0;

x 4,9 = ((x 4,9 * x 3,6 ) - (x 4,6 * x 3,9 )) / x 3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x 5,1 = ((x 5,1 * x 3,6 ) - (x 5,6 * x 3,1 )) / x 3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x 5,2 = ((x 5,2 * x 3,6 ) - (x 5,6 * x 3,2 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 5,3 = ((x 5,3 * x 3,6 ) - (x 5,6 * x 3,3 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 5,4 = ((x 5,4 * x 3,6 ) - (x 5,6 * x 3,4 )) / x 3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x 5,5 = ((x 5,5 * x 3,6 ) - (x 5,6 * x 3,5 )) / x 3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x 5,6 = ((x 5,6 * x 3,6 ) - (x 5,6 * x 3,6 )) / x 3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x 5,8 = ((x 5,8 * x 3,6 ) - (x 5,6 * x 3,8 )) / x 3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x 5,9 = ((x 5,9 * x 3,6 ) - (x 5,6 * x 3,9 )) / x 3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

Max x 1 = ((Cb 1 * x 1,1 ) + (Cb 2 * x 2,1 ) + (Cb 3 * x 3,1 ) + (Cb 4 * x 4,1 ) + (Cb 5 * x 5,1 ) ) - k x 1 = ((0 * 0.75) + (0 * 0) + (0 * 2.5) + (4 * 1.25) + (-M * 0) ) - 3 = 2;

Max x 5 = ((Cb 1 * x 1,5 ) + (Cb 2 * x 2,5 ) + (Cb 3 * x 3,5 ) + (Cb 4 * x 4,5 ) + (Cb 5 * x 5,5 ) ) - k x 5 = ((0 * -0.25) + (0 * 0) + (0 * 0.5) + (4 * 0.25) + (-M * 0) ) - 0 = 1;

Max x 6 = ((Cb 1 * x 1,6 ) + (Cb 2 * x 2,6 ) + (Cb 3 * x 3,6 ) + (Cb 4 * x 4,6 ) + (Cb 5 * x 5,6 ) ) - k x 6 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Max x 8 = ((Cb 1 * x 1,8 ) + (Cb 2 * x 2,8 ) + (Cb 3 * x 3,8 ) + (Cb 4 * x 4,8 ) + (Cb 5 * x 5,8 ) ) - k x 8 = ((0 * 0) + (0 * 0) + (0 * -1) + (4 * 0) + (-M * 0) ) - -M = M;

Since there are no negative values among the estimates of the controlled variables, the current table has an optimal solution.

X* = (0; 250)

Simplex Method Calculator

Solve optimization problems using the simplex method.

The calculator will solve the given optimization problem using the simplex algorithm. It will add slack, surplus and artificial variables, if needed. In case of artificial variables, the Big M method or the two-phase method is used to determine the starting solution. Steps are available.

If the calculator did not compute something or you have identified an error, or you have a suggestion/feedback, please write it in the comments below.

Maximize $$$ Z = 3 x_{1} + 4 x_{2} $$$ , subject to $$$ \begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \geq 0 \\ x_{2} \geq 0 \end{cases} $$$ .

The problem in the canonical form can be written as follows:

Add variables (slack or surplus) to turn all the inequalities into equalities:

Write down the simplex tableau:

The entering variable is $$$ x_{2} $$$ , because it has the most negative coefficient $$$ -4 $$$ in the Z-row.

The leaving variable is $$$ S_{1} $$$ , because it has the smallest ratio.

Divide row $$$ 1 $$$ by $$$ 2 $$$ : $$$ R_{1} = \frac{R_{1}}{2} $$$ .

Add row $$$ 2 $$$ multiplied by $$$ 4 $$$ to row $$$ 1 $$$ : $$$ R_{1} = R_{1} + 4 R_{2} $$$ .

Subtract row $$$ 2 $$$ from row $$$ 3 $$$ : $$$ R_{3} = R_{3} - R_{2} $$$ .

The entering variable is $$$ x_{1} $$$ , because it has the most negative coefficient $$$ -1 $$$ in the Z-row.

The leaving variable is $$$ S_{2} $$$ , because it has the smallest ratio.

Multiply row $$$ 2 $$$ by $$$ 2 $$$ : $$$ R_{2} = 2 R_{2} $$$ .

Add row $$$ 3 $$$ to row $$$ 1 $$$ : $$$ R_{1} = R_{1} + R_{3} $$$ .

Subtract row $$$ 3 $$$ multiplied by $$$ \frac{1}{2} $$$ from row $$$ 2 $$$ : $$$ R_{2} = R_{2} - \frac{R_{3}}{2} $$$ .

None of the Z-row coefficients are negative.

The optimum is reached.

The following solution is obtained: $$$ \left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right) $$$ .

$$$ Z = 20 $$$ A is achieved at $$$ \left(x_{1}, x_{2}\right) = \left(4, 2\right) $$$ A .

Optimizing resources with Linear Programming

Example (part 1): Simplex method

Solve using the Simplex method the following problem:

Consider the following steps:

A change is made to the variable naming, establishing the following correspondences:

As the independent terms of all restrictions are positive no further action is required. Otherwise there would be multiplied by "-1" on both sides of the inequality (noting that this operation also affects the type of restriction).

The inequalities become equations by adding slack , surplus and artificial variables as the following table:

In this case, a slack variable (X 3 , X 4 and X 5 ) is introduced in each of the restrictions of ≤ type, to convert them into equalities, resulting the system of linear equations:

Match the objective function to zero. Z - 3·X 1 - 2·X 2 - 0·X 3 - 0·X 4 - 0·X 5 = 0

The initial tableau of Simplex method consists of all the coefficients of the decision variables of the original problem and the slack, surplus and artificial variables added in second step (in columns, with P 0 as the constant term and P i as the coefficients of the rest of X i variables), and constraints (in rows). The C b column contains the coefficients of the variables that are in the base.

The first row consists of the objective function coefficients, while the last row contains the objective function value and reduced costs Z j - C j .

The last row is calculated as follows: Z j = Σ(C bi ·P j ) for i = 1..m, where if j = 0, P 0 = b i and C 0 = 0, else P j = a ij . Although this is the first tableau of the Simplex method and all C b are null, so the calculation can simplified, and by this time Z j = -C j .

If the objective is to maximize, when in the last row (indicator row) there is no negative value between discounted costs (P 1 columns below) the stop condition is reached.

In that case, the algorithm reaches the end as there is no improvement possibility. The Z value (P 0 column) is the optimal solution of the problem.

Another possible scenario is all values are negative or zero in the input variable column of the base. This indicates that the problem is not limited and the solution will always be improved.

Otherwise, the following steps are executed iteratively.

First, input base variable is determined. For this, column whose value in Z row is the lesser of all the negatives is chosen. In this example it would be the variable X 1 (P 1 ) with -3 as coefficient.

If there are two or more equal coefficients satisfying the above condition (case of tie), then choice the basic variable.

The column of the input base variable is called pivot column (in green color).

Once obtained the input base variable, the output base variable is determined. The decision is based on a simple calculation: divide each independent term (P 0 column) between the corresponding value in the pivot column, if both values are strictly positive (greater than zero). The row whose result is minimum score is chosen.

If there is any value less than or equal to zero, this quotient will not be performed. If all values of the pivot column satisfy this condition, the stop condition will be reached and the problem has an unbounded solution (see Simplex method theory ).

In this example: 18/2 [=9] , 42/2 [=21] and 24/3 [=8]

The term of the pivot column which led to the lesser positive quotient in the previous division indicates the row of the slack variable leaving the base. In this example, it is X 5 (P 5 ), with 3 as coefficient. This row is called pivot row (in green ).

If two or more quotients meet the choosing condition (case of tie), other than that basic variable is chosen (wherever possible).

The intersection of pivot column and pivot row marks the pivot value , in this example, 3.

The new coefficients of the tableau are calculated as follows:

So the pivot is normalized (its value becomes 1), while the other values of the pivot column are canceled (analogous to the Gauss-Jordan method).

Calculations for P 4 row are shown below:

The tableau corresponding to this second iteration is:

It is noted that in the last row, all the coefficients are positive, so the stop condition is fulfilled.

The optimal solution is given by the val-ue of Z in the constant terms column (P 0 column), in the example: 33. In the same column, the point where it reaches is shown, watching the corresponding rows of input decision variables: X 1 = 3 and X 2 = 12.

Undoing the name change gives x = 3 and y = 12.

Solve with PHPSimplex .

PHPSimplex Version 0.81

Developed by: Daniel Izquierdo Granja Juan José Ruiz Ruiz

English translation by: Luciano Miguel Tobaria

French translation by: Ester Rute Ruiz

Portuguese translation by: Rosane Bujes

IMAGES

Solved C. Use graphical method to solve the following linear
Linear programming with excel solver examples
😀 How to solve linear programming problems using simplex method. How to Carry out the Simplex
[Solved] Solve the Linear Programming model using Simplex method Maximize Z = 61 + 52 Subject
😀 Solve linear programming problems. How to solve linear programming problems by using simplex
🎉 Solve the linear programming problem by the simplex method. Simplex Calculator. 2019-03-06

VIDEO

Simplex Method Optimal Solution
Linear Programming, The Big M method
Linear Programming: The Simplex Method
Linear Programming 21: The simplex method
Lec 3: Linear Programming: Simplex with solved example
Linear Programming: Why simplex method? [EP0a]

COMMENTS

What Are the Six Steps of Problem Solving?
The six steps of problem solving involve problem definition, problem analysis, developing possible solutions, selecting a solution, implementing the solution and evaluating the outcome. Problem solving models are used to address issues that...
How Is Linear Programming Used in the Real World?
Linear programming is used daily in the real world to optimize the allocation of resources or activities to generate the most benefit or profit. Linear programming can take multiple factors into account into the thousands and is used extens...
How Do You Solve a Problem When You Have Different Bases With the Same Exponents?
When multiplying or dividing different bases with the same exponent, combine the bases, and keep the exponent the same. For example, X raised to the third power times Y raised to the third power becomes the product of X times Y raised to th...
Simplex method calculator
Simplex method calculator - Solve the Linear programming problem using Simplex method, step-by-step online.
How to Solve a Linear Programming Problem using the ...
... we first learn the concept of slack variables and then we learn how to solve a linear programming problem using the simplex method.
How to use the simplex method to solve maximization ...
... use the simplex method to solve the linear programming problem. ... Set up the initial simplex tableau: i. the constraint equations are
4.2: Maximization By The Simplex Method
Set up the problem. · Convert the inequalities into equations. · Construct the initial simplex tableau. · The most negative entry in the bottom row
Explanation of Simplex Method
solution and has three requirements: (1) must be a maximization problem
Solve Linear Programming Problem Using Simplex Method
Simplex Method: It is one of the solution method used in linear programming problems that involves two variables or a large number of constraint. The solution
Use the simplex method to solve the following linear programming
2x + y + v = 18 x + 3y + w = 24 . We can now reformulate the problem as follows: among all solutions to the system. 3x + y + u = 24. 2x +
Online Calculator: Simplex Method
Finding the optimal solution to the linear programming problem by the simplex method. Complete, detailed, step-by-step description of solutions.
Simplex Method Calculator
The calculator will solve the given optimization problem using the simplex algorithm. It will add slack, surplus and artificial variables, if needed.
Linear programming: Simplex method example
Example (part 1): Simplex method · Make a change of variables and normalize the sign of the independent terms. · Normalize restrictions. · Match the objective
Simplex Method Calculator
The simplex method is universal. It allows you to solve any linear programming problems. Тhe solution by the simplex method is not as difficult as it might