Apunte Programación Lineal (Investigación Operativa)

Un PPL es un problema de programación lineal, el cual consiste en la maximización o minimización de una función objetivo sujeta a una serie de restricciones, todas ellas lineales. Se busca obtener el valor del óptimo así como de las variables en dicho punto.

Representaciones

Las siguientes son las fórmulas involucradas en las representaciones y resoluciones de un PPL, así como de su problema dual cuando corresponda.

Formas Standard

Formas estandar de expresar un PPL, todas ellas equivalentes y convertibles entre sí. Para pasar entre las dos primeras basta con multiplicar por -1. Para ir hacia la tercera se agregan slacks, para volver se convierte la igualdad en dos desigualdades.

min cx
st Ax >= 0
    x >= 0

max cx
st Ax <= 0
    x >= 0

min/max cx
st Ax = 0
    x >= 0

Representación por diccionarios

En cada iteración del simplex utilizando diccionarios, lo que se tiene es el siguiente sistema de ecuaciones. El conjunto B es el de las variables básicas y N es el de no básicas.

$x_{i}={\bar {b_{i}}}-\sum _{j\in N}{\bar {a_{ij}}}x_{j}\;\;(\forall x_{i}\in B)$
$z={\bar {d}}+\sum _{j\in N}{\bar {c_{j}}}x_{j}$

El problema dual asociado resulta entonces el siguiente. Los conjuntos básicos y no básicos están invertidos respecto del primal.

$y_{j}=-{\bar {c_{j}}}+\sum _{i\in B}{\bar {a_{ij}}}x_{i}\;\;(\forall y_{j}\in N)$
$-w=-{\bar {d}}-\sum _{i\in B}{\bar {b_{i}}}x_{i}$

Representación matricial

Análoga a la anterior pero usa notación matricial, correspondiente al simplex revisado.

$x_{B}=B^{-1}b-B^{-1}A_{N}x_{N}$
$z=cB^{-1}b+(c_{N}-c_{B}B^{-1}A_{N})x_{N}$

Análisis de Sensibilidad

En esta sección se supone un problema de maximización usual.

Consiste en modificar el problema original una vez obtenido el óptimo, y analizar qué modificaciones pueden realizarse sin que cambie la composición de la base, y si cambia, cómo proseguir. Recordar la representacion matricial:

$x_{B}=B^{-1}b-B^{-1}A_{N}x_{N}$
$z=cB^{-1}b+(c_{N}-c_{B}B^{-1}A_{N})x_{N}$

Variar coeficientes del funcional

En este caso se modifican los coeficientes $c_{j}$ del funcional y se analiza hasta qué punto se puede mantener la misma base como óptima. En este caso no puede perderse factibilidad ya que las restricciones no se modifican, solamente está en riesgo la optimalidad.

En caso de que el delta sea mayor que el permitido, entonces se toma el óptimo anterior como solución para la iteración actual (pues se preserva factibilidad) y se continúa aplicando simplex hasta llegar al nuevo óptimo. Esto se debe a que se presume que al modificar ligeramente un coeficiente, entonces el nuevo óptimo debe encontrarse relativamente cerca.

Notar que el restringir el valor del delta a un rango hace que se mantenga la composición de la base, aunque el valor del óptimo cambia, ya que cambia la función objetivo. Lo que interesa preservar es la composición de la solución.

Variar coeficientes del funcional no básicos

Si varia un coeficiente no básico en un delta, pasando de $c_{j0}$ a $c_{j0}+\Delta$, para que el óptimo se preserve todos los coeficientes deben mantenerse negativos. Como el único que cambia es el j0, basta con pedir que:

$c_{j0}+\Delta -yA_{j0}\leq 0\Longleftrightarrow \Delta \leq yA_{j0}-c_{j0}$

Recordar del simplex revisado que $yB=c_{B}$, es decir, $y=c_{B}B^{-1}$.

Variar coeficientes del funcional básicos

El modificar un coeficiente del funcional correspondiente a una variable básica provoca cambios en todos los coeficientes no básicos en el diccionario óptimo. Ahora debe pedirse para todo j no básico que:

$c_{j}-(c_{B}+\Delta e_{p})B^{-1}A_{j}\leq 0$

Donde $e_{p}$ es un vector nulo con un 1 en la posición p, que corresponde al coeficiente a afectar, y $A_{j}$ es la columna j de la matriz de coeficientes de las restricciones.

A partir de lo anterior se calcula $rB=e_{p}$, es decir, $r=e_{p}B^{-1}$. Esto permite expresar las restricciones de la siguiente manera:

$c_{j}-c_{B}*A_{j}-\Delta *r*A_{j}\leq 0$

Lo anterior se instancia para cada uno de los $c_{j}$ no básicos y se resuelven las restricciones sobre delta, lo que determina el rango posible que puede tomar sin que se altere la base.

Variar término independiente

Supongo un problema de maximizacion con slacks ya agregadas (todas las restricciones son por igualdad, excepto que las variables sean positivas).

Como los coeficientes de las no básicas en el funcional no dependen de b, entonces optimalidad no se ve afectada, pero sí factibilidad. Los valores de las variables básicas en el óptimo son $B^{-1}b$, con lo que es necesario pedir que estos valores se mantengan positivos.

$B^{-1}(b+\Delta e_{k})=B^{-1}b+\Delta B^{-1}e_{k}\geq 0$

El primer término es conocido: son los valores de las variables básicas en el óptimo. El segundo término puede calcularse resolviendo $B*r=e_{k}$, y luego aplicando las restricciones necesarias.

En caso de que el delta salga del rango y la base no mantenga factibilidad, es necesario correr simplex dual sobre el problema partiendo de la ultima solucion, que si bien es no factible en el primal, lo es en el dual.

Agregado de una variable

Dado un problema de maximización con restricciones por igualdad, agregar una variable implica tener una variable nueva que puede o no participar en las restricciones y en el funcional. Es decir, se agrega un término $c_{n+1}x_{n+1}$ al funcional y una columna $A_{n+1}x_{n+1}$ a las restricciones.

Si a partir de una solución óptima $x^{*}$ se la extiende con la nueva variable en cero a ${\bar {x}}=(x^{*},0)$ es trivial ver que la factibilidad se mantiene:

$[AA_{n+1}](x^{*},0)=Ax^{*}+A_{n+1}0=b$

Para optimalidad, es necesario que los coeficientes de las variables no básicas en el funcional en el diccionario óptimo sean todos menores o iguales a cero. Como los existentes no cambian, el único a chequear es el de $x_{n+1}$, que entra como no básico.

$c_{n+1}-c_{B}B^{-1}A_{n+1}\leq 0$

Si vale, entonces la solución sigue siendo la óptima. Si no, se puede aplicar simplex a la solución ampliada e iterar hasta llegar al nuevo óptimo.

Agregado de una restricción

En este caso, al no cambiar el funcional, se preserva optimalidad si se mantiene factibilidad. Basta con verificar que el óptimo hallado verifique la nueva restricción. Si lo hace, se mantiene la base y además con el mismo valor del funcional. Si no, entonces se puede correr simplex dual a partir del óptimo anterior.

Interpretación Económica

La interpretación económica de las variables y los parámetros generalmente puede deducirse a partir del análisis de las dimensiones de cada una.

Generalmente un problema de maximización en el que se desea optimizar beneficio en la producción de determinados productos que consumen ciertos recursos se puede analizar de la siguiente forma:

• Cada $x_{j}$ representa cuánto se produce del producto j, con lo que está expresado en unidades de producto j.
• Cada $b_{i}$ es el disponible de un determinado recurso, entonces est'a en unidades de recurso i.
• Por lo tanto, el $a_{ij}$ debe estar expresado en unidades de recurso i necesarias por cada unidad de producto j.
• Y los coeficientes $c_{j}$ en ganancia por cada unidad de producto j.
• Una slack $s_{i}$ entonces representa cuánto no se consume del recurso i.

Interpretación del Dual

Siguiendo del problema anterior, se puede generar el dual asociado al sistema y realizar un análisis similar para obtener el significado de las variables duales $y_{i}$.

Como la sumatoria de los $a_{ij}y_{i}$ debe resultar expresada en ganancia por unidad de producto j (para poder compararlas con los $c_{j}$ que actúan de término independiente en el dual), entonces cada $y_{i}$ debe estar expresado en ganancia por recurso i.

${\frac {U_{i}}{U_{j}}}*Y={\frac {G}{U_{j}}}\Longrightarrow Y={\frac {G}{U_{j}}}*{\frac {U_{j}}{U_{i}}}={\frac {G}{U_{i}}}$

En otras palabras, la variable dual expresa cuál es el valor relativo de un recurso respecto al beneficio total.

Convexidad

Corresponde al análisis geométrico del poliedro formado por las restricciones que componen el modelo a resolver.

Definiciones

Punto Extremo

Un punto es extremo sii no puede escribirse como combinación convexa de otros puntos del poliedro. Un punto es extremo sii es solución básica, por lo que un poliedro tiene finitos puntos extremos.

Todos los puntos extremos pueden calcularse tomando los de la forma $(x_{B},0_{N})$ con $x_{B}=B^{-1}b$, si B es inversible y los valores resultantes para $x_{B}$ son mayores o iguales a cero.

Dirección

Un vector d es dirección de un poliedro X sii para todo punto x del poliedro, $x+\lambda d$ pertenece, para todo $\lambda \geq 0$.

Para toda dirección vale que $Ad=0$ y $d\geq 0$.

Una dirección es extrema sii no puede expresarse como combinación lineal positiva de otras direcciones.

Vale que ${\bar {d}}=\alpha d$, con $\alpha$ mayor a cero, es dirección extrema sii d es, para alguna base B y un j no básico:

$d=(d_{1},\ldots ,d_{n})$

Donde si $y_{i}$ son el resultado de $-B^{-1}*a_{j}$, siendo i los valores de los índices de las variables de la base, entonces $d_{i}=y_{i}$ y $d_{j}=1$. Para todos los demás, vale cero.

Es necesario que $B^{-1}*a_{j}\leq 0$, o no es dirección extrema.

Un método que se deduce de esta definición para hallar direcciones extremas es iterar por todas las posibles combinaciones de bases y j y realizar el cálculo para verificar si se cumple la condición.