DL-CO pset 1

Q: Legyen $A\in {\mathbb{R}}^{m\times n},b\in {\mathbb{R}}^m$, és $c_1,\dots ,c_k\in {\mathbb{R}}^n$. Fogalmazzuk meg a következő feladatot LP feladatként: $Ax=b,x\ge 0$, $\min f(x)$, ahol $f(x):=\max \{c_{1}x,\dots ,c_{k}x\}$.

Legyen

$$Q=\left[\begin{array}{c}A\\ -A\\ -I_n\\ I_n\end{array}\right],\hat{x}=x,\hat{b}=\left[\begin{array}{c}b\\ -b\\ \underline{0}\\ \underline{\alpha }\end{array}\right]$$

Ahol $\underline{0}=[0,\dots ,0{]}^T$, $\underline{\alpha }=[\alpha ,\dots ,\alpha ]$, $\underline{0},\underline{\alpha }\in {\mathbb{R}}^n$.

Q: Vezessük vissza a következő egyenlőtlenség rendszereket egymásra (abban az értelemben, hogy ha az egyiket meg tudjuk oldani, akkor az összeset meg tudjuk):

$$Ax=b,x\ge 0$$ $$Bx\le b,x\ge 0$$ $$Qy\le b$$ $$P{x}_0=b_0,Qx\le b_1$$

A felsorolt négy különböző feladat ekvivalenciáját úgy fogjuk bemutatni, hogy visszavezetjük mindegyiket a $Qx\le b$ alakra.

a) Az $Ax=b,x\ge 0$ alakot úgy tudjuk visszavezetni $Qx\le b$ alakra, ha

undefined

Q = \begin{bmatrix}
B \
-I_{n}
\end{bmatrix},
\hat{x} = x,
\hat{b} = \begin{bmatrix}
b \
0
\end{bmatrix}

undefined

\hat{Q} = \begin{bmatrix}
P && 0\
-P && 0\
0 && Q
\end{bmatrix},
\hat{x} = \begin{bmatrix}
x_{0} \
x
\end{bmatrix},
\hat{b} = \begin{bmatrix}
b_{0} \
-b_{0} \
b_{1}
\end{bmatrix}

undefined