Escribiendo un programa lineal en forma estándar

Question

Por lo general, se me pide que escriba problemas en forma estándar que tengan desigualdades involucradas. Sin embargo, este problema no tiene ninguna y me preguntaba si alguien tenía idea de cómo resolverlo.

Considera este sistema:

$$ e_{i} = b_{i} - \sum_{j=1}^na_{i,j}x_{j} \\(i=1,2,...m) $$

donde $a_{i,j}$ $(1 \leq i \leq m\,,\ 1 \leq\ j \leq n)$ y $b_{i}$ $(1 \leq i \leq m)$ son datos. El problema es encontrar una asignación de valores a las variables $x_{1}, ...,x_{n}$ que minimice max$|e_{j}|$. Expresa este problema como un programa lineal en forma estándar.

Así que no hay desigualdades y tanto $i$ como $j$ son siempre positivos, así que no sé por dónde empezar a introducir nuevas variables.

Answer 1

Deje $e=\begin{bmatrix}e_1\\\vdots\\ e_m\end{bmatrix}$, $b=\begin{bmatrix}b_1\\\vdots\\ b_m\end{bmatrix}$, $A=\begin{bmatrix}a_{11}&\ldots&a_{1n}\\\vdots\\ a_{m1}&\ldots&a_{mn}\\\end{bmatrix}$, $x=\begin{bmatrix}x_1\\\vdots\\ x_n\end{bmatrix}$

Entonces puede escribir su sistema de manera equivalente como:

$$e=b-Ax$$

Deje, el escalar $t$ sea el valor de $\max_j |e_j|$, entonces tendrá:

$$e_j\leq t~~\forall j=1,\ldots,m\\ -e_j\leq t ~~\forall j=1,\ldots,m$$

Ahora deje $\bf{1}= \begin{bmatrix}1\\\vdots\\ 1\end{bmatrix}$ ser un vector de $m$ unos apilados, entonces estas restricciones pueden escribirse como:

$$e\leq t1\\ -e\leq t1$$

donde $\leq$ es el menos que o igual elemento a elemento. De manera equivalente tiene:

$$b-Ax\leq t1\\ Ax-b\leq t1$$

el programa lineal que está buscando será:

$$\max_{x,t} ~~t\quad\text{sujeto a}\\b-Ax\leq t1 \\ Ax-b\leq t1$$

$$\max_{x,t} ~~t\quad\text{sujeto a}\\-Ax-t1\leq -b \\ Ax-t1\leq b$$

Si desea estandarizarlo aún más, haga lo siguiente: deje $z=[x^Tt]^T$, $c=[\underbrace{0\ldots 0}_{n \text{ veces}}1]^T$, $d=[-b^T~~b^T]^T$, $H=\begin{bmatrix}-A& -1\\A& -1\\\end{bmatrix}$, ahora puede escribirlo como:

$$\max_{z} ~~c^Tz\quad\text{sujeto a}\\Hz\leq d$$