# Primal-dual correspondence in the simplex method

I am trying to understand the dual simplex method and after reading a few different books I got stuck when trying to understand the primal variable to dual constraint correspondence. A lot of sources simply state the following table as the definition of the dual problem:

1. primal $x_j = 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} <> c_j$
2. primal $x_j \geq 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} \leq c_j$
3. primal $x_j \leq 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} \geq c_j$
4. primal free variable $x_j$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} = c_j.$

The $<>$ simply means the variable is unrestricted (aka free). I understand the derivation of the dual objective as the bound on the primal objective and where the constraints come from in the dual, but I'm struggling to see why the signs of the constraints change the way they do.

Can someone please help explain how to get a better intuition and understanding of the correspondence between primal variable types and the dual constraint types?

Thanks!

EDIT:

I decided to clarify the question based on the comments. Following the Lagrangian approach I decided to take a look at simple examples and see what their tightest dual bounds should be. Please see case 2 for an example of my wrong result.

1. First scenario $$min\ x\\s.t.\ x = b.$$ Lagrangian is $$\mathcal{L} = x + \lambda (x - b)$$

Since $x = b,$ and $\mathcal{L} = b.$ No constraints on the $\lambda$ appear and it is a free variable.

1. Second scenario: $$min\ x\\ s.t.\ x \geq k.$$ Introduce slack variable $s \leq 0$ into $x \geq k$ to get $$min\ x\\ s.t.\ x + s = k,\\ -s \geq 0$$

This results in Lagrangian $$\mathcal{L} = x + \lambda_1 (x + s -k) + \lambda_2 s = \\ \qquad = (1 + \lambda_1)x + s\lambda_1 - k\lambda_1 + s\lambda_2.$$

Again, $\frac{\partial\mathcal{L}}{\partial x} = 0 \rightarrow \lambda_1 = -1$.

This introduces a constraint on $\lambda_1 = -1$ and $\lambda_2$ is free.

2. Fourth scenario: (free x) $$min\ x\\s.t.\ x.$$ Lagrangian is $$\mathcal{L} = x + \lambda x = (1 + \lambda)x.$$ Minimum of the function is obtained when $1+\lambda=0$ so $\lambda=-1.$ We obtain the constant $c_j$ for the constraint.
• If $<>$ denotes $\neq$ then the "dual constraint" in 1. is not linear... – Math1000 Aug 15 '18 at 4:02
• In your second scenario $\lambda_2$ is not free because you forgot to include the partial derivative over $s$. – Michal Adamaszek Aug 16 '18 at 6:56