# Linear programming with equality constraints

I want to find a solution to the minimisation problem

$$\text{min } c^Tx \qquad \text{subject to } Ax=b$$

I have implemented the parametric self-dual simplex by R. Vanderbei in Matlab and it works perfectly with inequality constraints (tested it with multiple examples)

It solves a maximisation problem $$\text{max } c^Tx \qquad \text{subject to } Ax\leq b$$

I also want it to work with equality constraints, so I've rewritten the equality constraints as inequality constraints (with slack variables $w$): $$Ax + w\leq b \\ -Ax - w \leq -b$$

(and for the minimisation problem I will need to take $-c^T$). So then the constraints will look like $$\begin{bmatrix} A & I & 0\\ -A & 0 &-I \end{bmatrix} = \begin{bmatrix} x \\ w \\ w \end{bmatrix} = \begin{bmatrix} b \\ -b \end{bmatrix}$$

Is this the correct approach? Either my implementation or the method is wrong, because my algorithm doesn't work for equality constraints.

• Solved; replace $-I$ with $I$ and the second slack variable should be different, e.g. $v$ May 3, 2015 at 15:53

I replaced $-I$ with $I$ and used a different slack variable $v$, then the algorithm works fine