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\) or \(s_2\) 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\)?


Edit based on answer:

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$$


From Chapter 2 here.

asked 19 Apr '16, 14:03

BCLC's gravatar image

BCLC
8313
accept rate: 0%

edited 07 May '16, 06:20


Try using complementary slackness. And I don't think posting your homework here is optimal.

link

answered 19 Apr '16, 14:26

Jeff%20Linderoth's gravatar image

Jeff Linderoth
4412
accept rate: 40%

This is not homework. This is an exercise in our handouts. Also, Jeff Linderoth, complementary slackness is I guess what allows me to conclude that $y_2 = 0$. But what about $y_1$ and $y_3$? All complementary slackness gives me is that $y_1x_5 = 0 = y_3x_7$. Also, I edited

(19 Apr '16, 14:44) BCLC

Use the complementary slackness theorem on the dual. Since $x_2$ and $x_4$ are positive, this tells you something about the dual inequalities corresponding to those primal variables.

(20 Apr '16, 10:34) Jeff Linderoth

I edited. Thanks Jeff Linderoth ^-^

(07 May '16, 06:22) BCLC
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×20
×17
×6
×6

Asked: 19 Apr '16, 14:03

Seen: 718 times

Last updated: 07 May '16, 06:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.