Visualización de la matriz de restricciones en un programa lineal entero

Question

Supongamos que tenemos un programa lineal entero de la forma

$\begin{equation*} \begin{aligned} & \text{minimize} & & \sum\limits_{i=1}^n \sum\limits_{j=1}^n c_{ij}x_{ij}\\ & \text{s.t.} & & \mathbf{A}\mathbf{x}\geq \mathbf{b} \\ &&&\mathbf{dx}=\mathbf{g} \\ &&& x_{ij}\geq 0, x_{ij} \text{ integer} \end{aligned} \end{equation*} $

¿Cómo podemos formular la matriz de restricciones para este problema? Mi idea es convertir todas las restricciones en restricciones de igualdad añadiendo variables de holgura, y luego tomar los coeficientes de cada $x_{ij}$ (por ejemplo $a_{ij}$ , $d_{ij}$ ) y ponerlo en la matriz, que parece:

$\begin{bmatrix} a_{11} \ \ \ \ \ \ \ \ a_{12} \ \dots \ \ \ a_{1n}\\ \vdots \\ a_{n1} \ \ \ \ \ \ \ a_{n2} \ \dots \ \ \ a_{nn}\\ d_{n+1, 1} \ d_{n+1,2} \ \dots \ d_{n+1,n} \end{bmatrix} $

¿Tengo razón en esto? ¡Alguna aclaración sería genial!

Answer 1

Para introducir las variables de holgura ( $s_i$ ) es una buena idea. Entonces las dos restricciones se pueden escribir con dos igualdades matriciales. Supongo que $d$ es un $1\times n$ vectorial.

$$\underbrace{\begin{pmatrix}{} a_{11}&a_{12}&\ldots & a_{1n} & -s_{1} & 0 & \ldots & 0 \\ \vdots & \vdots &\vdots &\vdots & \vdots &\vdots &\vdots &\vdots \\ a_{n1}&a_{n2}&\ldots & a_{1n} & 0 & 0 & \ldots & -s_{n} \end{pmatrix}}_{n\times 2n=\color{blue}A}\cdot \underbrace{\begin{pmatrix}{} x_1\\ x_2\\\vdots \\ x_n \\1 \\1 \\ \vdots \\ 1\end{pmatrix}}_{2n \times 1=\color{blue}B}=\begin{pmatrix}{} b_1\\ b_2\\\vdots \\ b_n\end{pmatrix} $$

$$\begin{pmatrix}{}d_{n+1} & d_{n+2} & \ldots & d_{2n-1} & d_{2n} \end{pmatrix}=\color{blue}C $$ $$\begin{pmatrix}{}x_{n+1} & 0 &\ldots& 0 \\ 0&x_{n+1} &\ldots& 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0& \ldots & x_{2n}\end{pmatrix}=\color{blue}D$$

$x_{i}, s_{i} \in \mathbb N_0$

Tal vez una matriz de bloques podría hacer el trabajo. Uso las letras azules A,B,C y D de arriba. $O$ son vectores nulos o matrices nulas. El lado derecho es

$$\begin{pmatrix} A0\\0C \end{pmatrix}\cdot \begin{pmatrix} B0\\0D \end{pmatrix}=\ldots$$