Simplex Multiplier

Question

I am reading through a book which provides an example of a linear program given by \begin{align}\min&\quad-24y_{1}-28y_{2}\\\text{s.t.}&\quad6y_{1}+10y_{2} \leq 2400\\&\quad8y_{1}+5y_{2} \leq 1600\\&\quad0\leq y_{1} \leq 500\\&\quad0\leq y_{2} \leq 100.\end{align}

The solution is $-6100{\rm(objective\ value)}, y^{\top} = (137.5,100), \pi^{\top} = (0,-3,0,-13)$ where $\pi$ is the simplex multiplier associated with the solution.

I can solve the LP to find the feasible values of $y$ but I do not understand how to find the values of the simplex multiplier. Reading some papers I found out that the simplex multiplier is calculated as:

$$\pi^{\top} = c_{B}^{\top} B^{-1}.$$

I have attempted to use this by writing this LP in the standard form but I cannot match the values of the $\pi$: \begin{align}\min&\quad C^\top X\\\text{s.t.}&\quad A\cdot X=b\\&\quad A = \begin{pmatrix} 6 & 10 & 1 & 0 & 0 &0 \\ 8 & 5 & 0 & 1 & 0 &0\\ 1 & 0 & 0 & 0 & 1 &0\\ 0 & 1 & 0 & 0 & 0 &1 \end{pmatrix}\\&\quad b = \begin{pmatrix} 2400 \\ 1600 \\ 500\\ 100 \end{pmatrix}\\&\quad c = \begin{pmatrix} -24 \\ -28 \\ 0\\ 0\\ 0\\ 0 \end{pmatrix}\\&\quad B = \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0\\ 0 & 0 & 1 &0\\ 0 & 0 & 0 &1 \end{pmatrix}\quad{\rm(Basis\,Matrix)}.\end{align}

Can anyone please explain how to calculate the simplex multiplier in this example?

Answer 1

It is explained in this link as:

• Simplex multipliers are essentially the shadow prices associated with a particular basic solution. Those are the multiples of their initial system of equations such that, when all of these equations are multiplied by their respective simplex multipliers and subtracted from the initial objective function, the coefficients of the basic variables are zero.
• On the other hand, the shadow prices were readily available from the final system of equations. In essence, since varying the righthand side value of a particular constraint is similar to adjusting the slack variable, it was argued that the shadow prices are the negative of the objective-function coefficients of the slack (or artificial) variables in the final system of equations.
• Similarly, the simplex multipliers at each intermediate iteration are the negative of the objective-function coefficients of these variables.

An example of how to calculate simplex multipliers in each intermediate iterations is given here.

In your example for the final iteration of the simplex, you need to consider all the matrix operations that affected the $B$ matrix. In other words, the $B$ matrix should reflect the final basis of the simplex.