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?

$\endgroup$
3
  • $\begingroup$ Why negative values in your $b$ vector? $\endgroup$
    – RobPratt
    Commented Jul 30, 2020 at 1:07
  • $\begingroup$ @RobPratt right it should be positive... $\endgroup$ Commented Jul 30, 2020 at 5:01
  • $\begingroup$ @RobPratt It was a typo $\endgroup$
    – Jonn
    Commented Jul 30, 2020 at 6:20

2 Answers 2

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.

$\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$
    – Jonn
    Commented Jul 30, 2020 at 15:45
  • $\begingroup$ @Simplyop you are right, it should be 6 and the reduced cost should be 5.8125 $\endgroup$ Commented Jul 30, 2020 at 15:58
  • 1
    $\begingroup$ Thanks you for checking! $\endgroup$
    – Jonn
    Commented Jul 30, 2020 at 16:02
  • $\begingroup$ @Simplyop You are very welcome. $\endgroup$ Commented Jul 30, 2020 at 16:04
0
$\begingroup$

I guess you are reading the example on page 185 of Introdution of stochastic programming by John R. Birge. After reading the explanation above by Oguz Toragay, I would like to represent my opinion on the so-called $\pi$.

In fact, $\pi$ is generated in this way. Let

$A = \left( \begin{array}{c} 6 & 10 & 1 & 0 \\ 8 & 5 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{array} \right) \quad c =\left( \begin{array}{c} -24 \\ -28 \\ 0 \\ 0 \end{array} \right),$

Then we got $\pi = c^T \times A^{-1} = \left[ 0,-3,0,-13\right]$.

Note that there are four constraints in the origin problem, and with the optimal solution of the LP, constraints $8y_1+5y_2 \leq 1600$ and $y_2\leq100$ are tight, and the other two constraints have redundance, which leaves space to descend. The corresponding slack variables, namely $y_3$ and $y_5$, are checked in the last step of simplex algorithm. That's why we put these two columns into matrix $A$, rather than the others. You can also observe that all items in $\pi$ are no bigger than $0$ because it is the termination condition of the simplex algorithm, and also represents the (negative) shadow price. Consequently, only $\pi_2$ and $\pi_4$ are negative because only the second and the fourth constraints are tight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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