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.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_i = \bar{b_i} - \sum _{j \in N} \bar{a_{ij}} x_j \; \; (\forall x_i \in B)}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle y_j = - \bar{c_j} + \sum _{i \in B} \bar{a_{ij}} x_i \; \; (\forall y_j \in N)}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle -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.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_B = B^{-1} b - B^{-1} A_N x_N}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle z = c B^{-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:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_B = B^{-1} b - B^{-1} A_N x_N}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle z = c B^{-1} b + (c_N - c_B B^{-1} A_N) x_N}

Variar coeficientes del funcional

En este caso se modifican los coeficientes Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_{j0}} a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_{j0} + \Delta - y A_{j0} \leq 0 \Longleftrightarrow \Delta \leq y A_{j0} - c_{j0}}

Recordar del simplex revisado que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle yB = c_B} , es decir, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_j - (c_B + \Delta e_p) B^{-1} A_j \leq 0}

Donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e_p} es un vector nulo con un 1 en la posición p, que corresponde al coeficiente a afectar, y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_j} es la columna j de la matriz de coeficientes de las restricciones.

A partir de lo anterior se calcula Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle rB = e_p} , es decir, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r = e_p B^{-1}} . Esto permite expresar las restricciones de la siguiente manera:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_j - c_B * A_j - \Delta * r * A_j \leq 0}

Lo anterior se instancia para cada uno de los Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B^{-1}b} , con lo que es necesario pedir que estos valores se mantengan positivos.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_{n+1} x_{n+1}} al funcional y una columna Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_{n+1} x_{n+1}} a las restricciones.

Si a partir de una solución óptima Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x^*} se la extiende con la nueva variable en cero a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \bar{x} = (x^*, 0)} es trivial ver que la factibilidad se mantiene:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle [A A_{n+1}] (x^*, 0) = A x^* + 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_{n+1}} , que entra como no básico.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_j} representa cuánto se produce del producto j, con lo que está expresado en unidades de producto j.
• Cada Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle b_i} es el disponible de un determinado recurso, entonces est'a en unidades de recurso i.
• Por lo tanto, el Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{ij}} debe estar expresado en unidades de recurso i necesarias por cada unidad de producto j.
• Y los coeficientes Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_j} en ganancia por cada unidad de producto j.
• Una slack Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle y_i} .

Como la sumatoria de los Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{ij}y_i} debe resultar expresada en ganancia por unidad de producto j (para poder compararlas con los Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_j} que actúan de término independiente en el dual), entonces cada Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle y_i} debe estar expresado en ganancia por recurso i.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (x_B, 0_N)} con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_B = B^{-1} b} , si B es inversible y los valores resultantes para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x + \lambda d} pertenece, para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda \geq 0} .

Para toda dirección vale que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Ad = 0} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d \geq 0} .

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

Vale que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \bar{d} = \alpha d} , con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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.