How to apply the simplex method

In summary, the conversation discusses the use of the $M$-method to solve a linear programming problem with the canonical form and matrix $A$. The problem is solved using the simplex method, which involves constructing an initial tableau, finding the basic feasible solution, and using the simplex algorithm to determine the entering and leaving variables. This process is repeated until the optimal solution is reached.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

I want to solve the following linear programming problem:

$$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$

In this case we use the $M$-method.The canonical form of the problem is the following:$$-\max (-3y_1+y_2-2y_3) \\ 3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7$$The matrix $A$ ($Ax=b$) is the following:$A=\begin{bmatrix}
3 & 2 & -1 & 1 & 0 & 0 & 0\\
0 & 5 & -1 & 0 & 1 & 0 & 0\\
4 & -1 & 0 & 0 & 0 & -1 &0 \\
1 & 1 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}$It doesn't contain the $4 \times 4$ identity matrix, that's why we introduce an artificial variable $y_8 \geq 0$ at the third equation and we have the new system of restrictions:

$$ 3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6+y_8= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7,8$$Now we will solve the problem with the $M-$method , i.e. we will solve the linear programming problem $\max(-3y_1+y_2-2y_3+MY-8), M<<0$ under the new system of restrictions.I tried to apply the simplex method and I got the following:$$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\
P_4 & 0 & 160 & 2 & 3 & 4 & 1 & 0 & 0 & 0 & 80 & L_1\\
P_5 & 0 & 180 & 3 & 2 & 3 & 0& 1 & 0 & 0 & 60 & L_2\\
P_6 & 0 & 200 & 4 & 3 & 2& 0 & 0 & 1 & 0 & 50 & L_3\\
P_7 & 0 & 120 & 1 & 2 & 1 &0 & 0 & 0 & 1 & 120 & L_4 \\
& z & 0 & -30 & -26 & -28 & 0 & 0& 0& 0 & & L_5
\end{matrix}$$

$P_1$ gets in the basis, while $P_6$ gets out of the basis.$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\
P_4 & 0 & 60 & 0 & \frac{1}{2} & 3 & 1 & 0 & -\frac{1}{2} & 0 & 20 & L_1'=L_1-2L_3'\\
P_5 & 0 & 30 & 0 & -\frac{1}{4} & \frac{3}{2} & 0& 1 & -\frac{3}{4} & 0 & 20 & L_2'=L_2-3L_3'\\
P_1 & 30 & 50 & 1 & \frac{3}{4} & \frac{1}{2}& 0 & 0 & \frac{1}{4} & 0 & 100 & L_3'=\frac{L_3}{4}\\
P_7 & 0 & 120 & 1 & 2 & 1 & 0 & 0 & 0 & 1 & 120 & L_4'=L_4 \\
& z & 1500 & 0 & -\frac{7}{2} & -13 & 0 & 0&\frac{15}{2} & 0 & & L_5'=L_5+30L_3'
\end{matrix}$And then $P_3$ would get in the basis and $P_4$ would go out of the basis.
But I found that the initial tableau should be the following:

View attachment 5130So could you explain how we apply the Simplex method in such a case? (Thinking)
 

Attachments

  • 12516201_764204317057580_1064568285_n.jpg
    12516201_764204317057580_1064568285_n.jpg
    37.3 KB · Views: 84
Physics news on Phys.org
  • #2
Yes, of course. To apply the Simplex method in this case, we start by constructing the initial tableau. This includes writing down our objective function and the constraints in a standard form, with slack/surplus variables added if necessary. Then, you will find the basic feasible solution by assigning a value of 0 to all the artificial and slack variables, and then solving for the other variables. Once you have the basic feasible solution, the next step is to use the simplex algorithm to solve the problem. This involves selecting an entering variable, which is the variable that you want to add to the basis, and a leaving variable, which is the variable that you want to remove from the basis. You can determine which variables should enter or leave the basis by finding the maximum ratio between the right-hand side of a constraint and the coefficient of the entering variable. Once you have chosen an entering and leaving variable, you can compute the values of the other variables in the basis by solving the equations formed by those two variables. Each time you make a new iteration, you need to update your tableau. Then, you repeat the process until you reach the optimal solution.
 

FAQ: How to apply the simplex method

What is the simplex method and how does it work?

The simplex method is an algorithm used to solve linear programming problems. It involves creating a feasible solution and then moving from one feasible solution to another until an optimal solution is found. This is done by identifying and moving along the edges of a feasible region in a systematic way.

What are the steps involved in applying the simplex method?

The steps involved in applying the simplex method are:

  1. Formulate the problem into a standard form
  2. Create an initial feasible solution
  3. Find the pivot element
  4. Update the basic variables and corresponding non-basic variables
  5. Repeat steps 3 and 4 until the optimal solution is found

What are some common applications of the simplex method?

The simplex method is commonly used in industries such as finance, transportation, manufacturing, and telecommunications to optimize resource allocation and production processes. It is also used in network flow problems, game theory, and other mathematical models.

What are the assumptions made when using the simplex method?

The simplex method assumes that the problem is a linear programming problem, meaning that the objective function and constraints are linear. It also assumes that all variables are non-negative and that there is a feasible solution.

What are the limitations of the simplex method?

The simplex method may not always find the optimal solution, especially in cases where there are multiple optimal solutions. It also does not work for nonlinear problems. Additionally, as the number of variables and constraints increase, the time and computational power required to solve the problem also increase.

Similar threads

Replies
32
Views
5K
Replies
4
Views
2K
Replies
25
Views
4K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
17
Views
1K
Replies
4
Views
2K
Replies
15
Views
3K
Back
Top