5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Why negative values in your $b$ vector? $\endgroup$ – RobPratt Jul 30 '20 at 1:07
  • $\begingroup$ @RobPratt right it should be positive... $\endgroup$ – Oguz Toragay Jul 30 '20 at 5:01
  • $\begingroup$ @RobPratt It was a typo $\endgroup$ – Simply op Jul 30 '20 at 6:20
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks @Orguz Toragay In the worked example link that you provided, c3 is taken as zero on page 7 when calculating the reduced cost of the non basic variables x3, x4 &x5. Shouldn't this be 6 instead of zero as that would correspond to the coefficient of x3 in the objective? $\endgroup$ – Simply op Jul 30 '20 at 15:45
  • $\begingroup$ @Simplyop you are right, it should be 6 and the reduced cost should be 5.8125 $\endgroup$ – Oguz Toragay Jul 30 '20 at 15:58
  • 1
    $\begingroup$ Thanks you for checking! $\endgroup$ – Simply op Jul 30 '20 at 16:02
  • $\begingroup$ @Simplyop You are very welcome. $\endgroup$ – Oguz Toragay Jul 30 '20 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.