How do i convert this LP $$\text{maximize }x_4$$ $$\text{subject to }\epsilon\leq x_1\leq 1\\\epsilon{x_{j-1}}\leq x_j\leq 1-\epsilon{x_{j-1}}, \quad j=2,...,4 $$ to the standard form $$\text{minimize } c^Tx\\\text{subject to Ax=b}\\x\geq 0$$
Asked
Active
Viewed 46 times
0
-
So $x$ = <$x_1,x_2,x_3,x_4$>, right? – quasi Mar 08 '17 at 10:01
-
And therefore $c^T$ = ...? – quasi Mar 08 '17 at 10:01
-
Yes x = x1, x2, x3. c is the coefficients of x1, x2, x3. so e.g: c^Tx = ax1+bx2+.... – Yin Gong Mar 08 '17 at 10:03
-
Yes, but $c^T$ is forced since you want the dot product to equal $x_4$. So you can write $c^T$ as what numerical $4$-tuple? – quasi Mar 08 '17 at 10:04
-
No, $x$ is not <$x_1,x_2,x_3$>. You need all 4 variables. Similarly, $c$ is a $4$-tuple, not a triple. – quasi Mar 08 '17 at 10:06
-
c^Tx = [0; 0; 0; 1]^T*[x1 x2 x3 x4] = x4 – Yin Gong Mar 08 '17 at 10:07
-
Right, good start. – quasi Mar 08 '17 at 10:08
-
Actually, a few more variables will be needed (slack variables), but that can be fixed later. – quasi Mar 08 '17 at 10:08
-
Before getting the matrix $A$, rewrite all the inequalities in $\le$ form, or, to save time, in equation form with slack variables. – quasi Mar 08 '17 at 10:09
-
ok. so do i break up the inequality to form two inequalities? – Yin Gong Mar 08 '17 at 10:11
-
Yep. And the rest is easy. – quasi Mar 08 '17 at 10:11
-
When done, the vector $x$ has to be adjusted to incorporate the new slack variables. Similarly, $c^T$ has to be adjusted. – quasi Mar 08 '17 at 10:14
-
Each inequality gets its own private slack variable. – quasi Mar 08 '17 at 10:16
-
so for the first inequality i can write $$x_1\leq 1\quad x_1\geq \epsilon\ x_1+\alpha=1\quad x_1-\beta=\epsilon$$ – Yin Gong Mar 08 '17 at 10:17
-
yes, you got it. – quasi Mar 08 '17 at 10:17
-
You're welcome. You can get $A$ now, right? – quasi Mar 08 '17 at 10:19
-
Yes. I can get A now – Yin Gong Mar 08 '17 at 10:21
-
Just to check, what will the dimensions of $c,x,A,b$ be? – quasi Mar 08 '17 at 10:21
-
The new $x$ needs to include the slack variables. – quasi Mar 08 '17 at 10:23
-
$$c = m\times 1, \quad x = m\times 1, A= m\times m, b= m\times 1$$. yes x will include the slack variables – Yin Gong Mar 08 '17 at 10:25
-
No, A is not square. Also, $m$ is not a variable -- it's a number. – quasi Mar 08 '17 at 10:26
-
Start with $x$. How many components does it have? – quasi Mar 08 '17 at 10:26
-
sorry. yes A is not square – Yin Gong Mar 08 '17 at 10:28
-
So what is the dimension of the new $x$? – quasi Mar 08 '17 at 10:28
-
$x$ needs components for the old variables $x_1,x_2,x_3,x_4$ as well as the new slack variables, There is one slack variable for each equation, hence the dimension of the new $x$ is [what]? – quasi Mar 08 '17 at 10:35