Programación lineal con muchas restricciones y pocas variables desconocidas

Question

Vectores $x, y \in \mathbb{R}^{n\times 1}$ satisfacer $$ \forall_{i,j}\; x_i + y_j \leq a_{i,j} $$ donde $a\in \mathbb{R}^{n\times n}$ es una matriz dada. La cuestión es encontrar el valor máximo de $\sum_i x_i + \sum_j y_j$ .

Mi idea

Supongamos que $t$ es una biyección definida en $\{1,..,n\}\mapsto \{1,..,n\}$ entonces tenemos $$ \sum_i x_i + \sum_j y_j \leq \sum_k a_{k\,t(k)} $$ que introducen además $$ \sum_i x_i + \sum_j y_j \leq \min_t \sum_k a_{k\,t(k)} $$

Lo que queda es demostrar que $\min_t \sum_k a_{k\,t(k)}$ se puede llegar. Es decir, demostrar que existen vectores $x, y$ tal que $$ \begin{cases} x_i + y_j \leq a_{i,j},\;\;\forall_{i,j}\\ \sum_i x_i + \sum_j y_j = \min_t \sum_k a_{k\,t(k)} \end{cases} $$

Answer 1

Tu límite superior es bueno y corresponde a encontrar una coincidencia de peso mínimo sobre matrices de permutación. O puedes demostrar directamente un límite superior relacionado:

Límite superior relacionado (de hecho, idéntico)

Sea $P=(p_{ij})$ sea un "doble estocástico" $n \times n$ de forma que \begin{align} \sum_{j=1}^n p_{ij} &= 1 \quad \forall i \in \{1, ..., n\} \\ \sum_{i=1}^n p_{ij} &=1 \quad \forall j \in \{1, ..., n\} \\ p_{ij} &\geq 0 \quad \forall i, j \end{align} Entonces, si $(x_i), (y_j)$ son valores que satisfacen $x_i + y_j \leq a_{ij}$ para todos $i,j \in \{1, ..., n\}$ entonces puedes demostrar (usando métodos similares a tu límite superior existente) que: $$\sum_{i=1}^n x_i + \sum_{j=1}^n y_j \leq \sum_{ij} p_{ij} a_{ij} $$ Por tanto, el mejor límite superior de este tipo se resuelve mediante el siguiente programa lineal

\begin{align} \mbox{Minimize:} & \quad \sum_{ij} p_{ij}a_{ij} \\ \mbox{Subject to:} & \sum_{j=1}^n p_{ij} = 1 \quad \forall i \in \{1, ..., n\} \\ &\sum_{i=1}^n p_{ij} =1 \quad \forall j \in \{1, ..., n\} \\ &p_{ij} \geq 0 \quad \forall i, j \end{align} Resulta que este límite superior es idéntico a su límite superior de la coincidencia min-peso sobre la matriz $(a_{ij})$ porque toda matriz doblemente estocástica $(p_{ij})$ puede expresarse como una combinación convexa de matrices de permutación (que a veces se denomina Teorema de Birkhoff-Von Neumann ), por lo que minimizar una función lineal sobre matrices doblemente estocásticas puede reducirse a minimizar la misma función sobre matrices de permutación (ya que las matrices de permutación son los "puntos extremos" del conjunto de matrices doblemente estocásticas).

Límite inferior de coincidencia

Intente utilizar la dualidad del programa lineal para tomar el dual del programa lineal anterior con $p_{ij}$ variables para convertirlo en un programa lineal con variables duales $x_i,y_j$ .

Answer 2

Dado que esto parece no ser una tarea para casa, puede ser útil tener el siguiente "apéndice" a mi respuesta (aunque esto también puede ser un spoiler para el sabor "hágalo usted mismo" de mi respuesta anterior). Doy esto porque algunos tratamientos de la teoría de la dualidad asumen una estructura particular que no es conveniente para este problema.

---

Tienes el LP (primario): \begin{align} \mbox{Minimize:} &\quad -\left(\sum_{i=1}^n x_i + \sum_{i=1}^n y_i\right) \\ \mbox{Subject to:} &\quad x_i + y_j \leq a_{ij} \quad \forall i,j \in \{1, ..., n\} \end{align} El valor objetivo óptimo es el mismo que: \begin{align} &\inf_{x,y\in \mathbb{R}^n} \sup_{p\geq 0}\left[-\left(\sum_{i=1}^n x_i + \sum_{j=1}^n y_j\right) + \sum_{ij}p_{ij}\left(x_i+y_j-a_{ij}\right) \right]\\ &\overset{(a)}{=}\inf_{x,y\in \mathbb{R}^n}\sup_{p\geq 0}\left[-\sum_{ij}p_{ij}a_{ij} + \sum_{i=1}^nx_i\left(-1+\sum_{j=1}^np_{ij}\right)+\sum_{j=1}^ny_j\left(-1+\sum_{i=1}^np_{ij}\right) \right]\\ &\overset{(b)}{=}\sup_{p\geq 0}\inf_{x,y\in \mathbb{R}^n} \left[-\sum_{ij}p_{ij}a_{ij} + \sum_{i=1}^nx_i\left(-1+\sum_{j=1}^np_{ij}\right)+\sum_{j=1}^ny_j\left(-1+\sum_{i=1}^np_{ij}\right) \right]\\ \end{align} donde (a) se obtiene cambiando el orden de suma; (b) se obtiene cambiando el orden de $\inf$ y $\sup$ que puede justificarse en este caso por la teoría del punto de silla de montar. El último problema tiene un valor óptimo igual al del LP (dual): \begin{align} \mbox{Maximize:} & \quad -\sum_{ij} p_{ij} a_{ij} \\ \mbox{Subject to:} & \quad \sum_{j=1}^n p_{ij} = 1 \quad \forall i \in \{1, ..., n\} \\ & \quad \sum_{i=1}^n p_{ij} = 1 \quad \forall j \in \{1, ..., n\} \\ &\quad p_{ij} \geq 0 \quad \forall i,j \in \{1, ..., n\} \end{align}

---

¿Por qué el problema primario es equivalente al siguiente "juego de 2 jugadores"? $$\inf_{x,y\in \mathbb{R}^n} \sup_{p\geq 0}\underbrace{\left[-\left(\sum_{i=1}^n x_i + \sum_{j=1}^n y_j\right) + \sum_{ij}p_{ij}\left(x_i+y_j-a_{ij}\right) \right]}_{L(x,y,p)}$$ La razón es que el jugador 1 quiere elegir $x,y\in\mathbb{R}^n$ para minimizar $\sup_{p\geq 0}L(x,y,p)$ . Si elige de una manera que viola la restricción $x_i+y_j\leq a_{ij}$ para al menos una $(i,j)$ entonces el jugador 2 puede "ganar" eligiendo $p_{ij}\rightarrow \infty$ para ese mismo $(i,j)$ par, haciendo $L(x,y,p)\rightarrow\infty$ . Así que el jugador 1 debe elija $x,y$ para satisfacer $x_i + y_j \leq a_{ij}$ para todos $(i,j)$ . El jugador 1 puede optimizar aún más su elección de $x,y$ siempre que se cumplan estas restricciones, lo que corresponde al LP primal.

Desde $L(x,y,p)$ es lineal en $(x,y)$ para fijo $p$ y lineal en $p$ para fijo $(x,y)$ la teoría del punto de silla asegura que podemos cambiar el $\inf$ y $\sup$ ordenar como lo hicimos anteriormente.