Encontrar el mínimo/máximo $\|x\|_{1}$ con sujeción a $Ax = b$ utilizando el método simplex

Question

Dejemos que $Ax = b$ sea un sistema lineal con $a_{i,j} \in \{0,1\}$ y $b_i \in \{0,1,2,3,4,5,6,7,8\}$ . Las limitaciones de $x$ son $x_i \in \{0,1\}$ . Suponemos que el sistema admite al menos una solución.

¿Cómo puedo obtener la cantidad mínima y máxima de $1$ en mi solución ¿Vector?

---

Ejemplo:

$$\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1\\ \end{bmatrix} x = \begin{bmatrix} 1\\ 3\\ 2\\ \end{bmatrix}$$

En este caso está bastante claro que $\|x\|_{1} \geq 3$ pero, ¿cómo puedo generalizar esto? Aparentemente esto se puede hacer con el algoritmo simplex. Nunca he hecho programación lineal y agradecería una explicación de este método (quizás sobre el ejemplo anterior).

Estoy tratando de entender la programación lineal (página 16) del siguiente artículo:

• Andrew Fowler, Andrew Young, Buscaminas: un análisis estadístico y análisis computacional , 2004.

Answer 1

El punto óptimo del problema de minimización está permitiendo como: valor óptimo:3, punto óptimo:{x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 1, x6 -> 0, x7 -> 0, x8 -> 0, x9 -> 1, x10 -> 1, x11 -> 0, x12 -> 0} El punto óptimo del problema de maximización se permite como valor óptimo:4, punto óptimo:{x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 1, x8 -> 0, x9 -> 1, x10 -> 0, x11 -> 1, x12 -> 1} El problema anterior es un tipo de problema de programación lineal binaria pura. Tengo un nuevo y buen algoritmo y software para resolver este problema.

Answer 2

Dado un sistema lineal subdeterminado $\mathrm A \mathrm x = \mathrm b$ en $\mathrm x \in \{0,1\}^n$ nos gustaría extremar el número de unos en la solución. Como $x_i \in \{0,1\}$ no hay necesidad de extremar $\|\mathrm x\|_1$ . En cambio, extremamos $1_n^T \mathrm x$ . Tenemos entonces el programa binario

$$\begin{array}{ll} \text{extremize} & 1_n^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \in \{0,1\}^{n}\end{array}$$

que se puede reescribir como un programa entero (IP)

$$\begin{array}{ll} \text{extremize} & 1^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & 0_n \leq \mathrm x \leq 1_n\\ & \mathrm x \in \mathbb Z^n\end{array}$$

Relajando la restricción de integralidad, tenemos entonces un programa lineal (LP)

$$\begin{array}{ll} \text{extremize} & 1^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & 0_n \leq \mathrm x \leq 1_n\\ & \mathrm x \in \mathbb R^n\end{array}$$

que se puede resolver, por ejemplo, con el método simplex. Por supuesto, no hay garantía de que la solución del LP sea la misma que la solución del IP.