1

enter image description here

All I got is that

$$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$

and

$y_2 = 0$ because $x_6$ is in basis.

How do I find $y_1$ and $y_3$ without going through the simplex method?

I took the dual and that doesn't seem to help.

I know that $y_1 = z_5 - c_5$ and $y_3 = z_7 - c_7$, but how do I find $z_i - c_i$?

From Chapter 2 here.

BCLC
  • 13,459

2 Answers2

1

HINT: With these values of $x_1,x_2,x_3,x_4$, it is clear that the basic variables are $x_2,x_4$ and $x_6$ (the slack variable for the second constraint).

Therefore, it is easy to find the optimal tableau, from which you can directly read the values of the dual variables (do you see where?).

Kuifje
  • 9,584
  • 1
    Because the second constraint is not tight, which means the slack variable is positive, therefore in the basis. – Kuifje Mar 09 '16 at 13:46
  • 1
    If you replace $x_1,x_2,x_3,x_4$ by their values, you get either an inequality, or an equality. If it is an equality, than the constraint is tight. – Kuifje Mar 09 '16 at 14:38
  • Thanks @Kuifje. So $y_2=0$ but what about $y_1$ and $y_3$? – BCLC Mar 22 '16 at 21:48
  • $-y_1$ and $-y_3$ equal the reduced cost of slack variables $x_5$ and $x_7$, respectively. – Kuifje Mar 30 '16 at 16:56
  • 2 and 3 you mean? – BCLC Mar 30 '16 at 20:39
  • No, $y_1$ is the dual variable associated with constraint $1$, with slack variable $x_5$, and $y_3$ is dual variable associated with with constraint $3$, with slack variable $x_7$. – Kuifje Mar 30 '16 at 20:47
  • Oh right zj-cj. I remember now. So how do I get those? – BCLC Mar 30 '16 at 20:48
  • In the optimal tableau…that you need to compute knowing that variables $x_2$, $x_4$ and $x_6$ are the basic optimal variables. – Kuifje Mar 30 '16 at 20:54
  • Kuifje, I thought the whole point of the problem is not using the simplex method. I could easily answer this with a computer which would give me the $z_j - c_j$'s. – BCLC Mar 30 '16 at 23:20
  • I never said you should use the simplex method :) once you know the basic variables, you only have to inverse the initial matrix to get the optimal tableau. – Kuifje Mar 31 '16 at 01:09
  • Oh wait I think I remember. Is this something like coefficients of the x's multiplied to the inverse of the original matrix? – BCLC Mar 31 '16 at 01:25
  • Kuifje, should we use complementary slackness like what was done here? I posted an answer – BCLC May 07 '16 at 10:21
  • You said inverse. did you mean transpose? – BCLC May 07 '16 at 10:22
0

Consider the dual:

$$\min z' = 12y_1 +7y_2 + 10y_3$$

s.t.

$$\begin{bmatrix} 3 & 1 & 2\\ 1 & 3 & 1\\ 1 & 2 & 3\\ 4 & 3 & -1 \end{bmatrix}\begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix} \ge \begin{bmatrix} 2\\ 4\\ 3\\ 1 \end{bmatrix}$$

Since the dual of the dual is the primal, the dual of the dual variables are the primal variables.

Using complementary slackness on the dual, we have:

$$x_1 \mathcal{S}_1 = 0$$

$$x_2 \mathcal{S}_2 = 0$$

$$x_3 \mathcal{S}_3 = 0$$

$$x_4 \mathcal{S}_4 = 0$$

$$\because x_2, x_4 > 0, \mathcal{S}_2 = \mathcal{S}_4 = 0$$

Thus,

$$\begin{bmatrix} 1 & 3 & 1\\ 4 & 3 & -1 \end{bmatrix}\begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}$$

$$\to \begin{bmatrix} 1 & 3 & 1\\ 4 & 3 & -1 \end{bmatrix}\begin{bmatrix} y_1\\ 0\\ y_3 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}$$

$$\to \begin{bmatrix} 1 & 1\\ 4 & -1 \end{bmatrix}\begin{bmatrix} y_1\\ y_3 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}$$

$$\to y_1 = 1, y_3 = 3$$

BCLC
  • 13,459