Programación Lineal Entera

Modelos de PL que tienen la condición de que algunas o todas sus variables tienen que asumir valores enteros.
Tambien surge ante la necesidad de utilizar variables de decisión que deben ser "binarias", con el fin de modelar situaciones de opciones/alternativas.

Si en el PL posee tanto variables de desición enteras, como no enteras, podemos se trata, de un problema de programación lineal entera Mixta. Y a su vez, cuando solo pueden asumir varibles binarias, recibe el nombre de programación lineal entera binaria.

PE: Programación Entera

Relajación Lineal (RPL)

Es un estado de los PL que se obtiene al omitir la condición que exige que las variables sean enteras, obteniendo una transformación del problema en un PL continuo (una versión menos restringida del problema entero).

• PE de maximización: El valor objetivo óptimo de la RLP es siempre
  $\ge$ que el valor objetivo óptimo del PE. El valor objetivo óptimo del RLP seria una cota superior del de PE.
• PE de minimización: El valor objetivo óptimo de la relajacion lineal es una cota inferior para valor objetivo optimo del PE.

Soluciones Enteras vs Soluciones Redondeadas

Una solución redondeada resulta en aproximar el valor de la solución optima, a su proximo entero, sacrificando optimicidad.
En general el redondeo resulta más aceptable a medida que crece el valor de la variable en cuestión. Esto es debido a que no siempre la solución redondeada es la mejor, en valores pequeños, el cambio de redondear un número puede repercutir/impactar fuertemente en la solución resultando no muy aceptable dicho elemento, debido a que representa un porcentaje alto en el total.

Por ejemplo, redondear, una solucion con 12843.45 (un valor fraccionario grande)casas a construir, a 12843 casas a construir, resulta mas aceptable que, redondear una solución donde debamos construir 2.45 casas y nos aproximemos a 2 casas.

El método de redondeo puede conducir a situaciones como:

• Un punto no factible, por haber redondeado al entero más próximo.

• Uno o más puntos enteros cercanos factibles pero que…

  • No necesariamente serán óptimos para el PE.
  • No necesariamente estarán cerca de la solución óptima.

• Situación en la cual, el redondeo deja de ser una tecnica válida para encontrar la solución, y es necesario, recurrir a la busqueda de la solución optima entera.

Las situaciónes por las cuales es necesario encontrar la solución optima entera pueden deberse a la dependencia entre insumos para la fabricación de dos productos. Es decir, la dependencia funcional entre dos variables de decisión debido a sus restricciones.

Por ejemplo, construir 4.5 producto A, y 2.8 producto B, pero tanto el producto A como el B comparten insumos, y podrían los recursos obtenidos de el 0.5 del producto A, mas el 0.8 del producto B ser utiles para producir uno de alguno de los dos.

Método de Ramificación y Acotamiento

• Si la región factible para la RPL de un PE puro es acotada,
  entonces la región factible del PE estará formada por un número finito de
  puntos.

En teoría se podría resolver el PE calculando los valores de la
función objetivo para cada uno de los puntos factibles y elegir el mejor. Sin
embargo, el problema con este método es que la mayoría de los PE
tienen regiones factibles que consisten en billones y billones de puntos
factibles.

Lo que se utiliza para solucionar esto, es encontrar un método que nos permita, a partir del RLP, ir explorando las soluciones enteras, como el método branch and bound O ramificación y acotación.

Desglozando el nombre, la parte de "ramificación" consiste en ir agregando restricciones excluyentes a la RPL para alguna de las variables no enteras con el objetivo de dividir a la región factible en dos partes (eliminando en el proceso los valores no enteros de dicha variable en ambas partes), hasta encontrar la solucion entera óptima.

La "acotación" se basa en el hecho de que las regiones factibles de los problemas que surjan de "ramificar", son considerados subconjuntos del conjunto de soluciones del RPL y por lo tanto, el valor óptimo Z que estamos buscando en los dos subconjuntos actuales, será siempre menor/mayor al valor Z de la RPL, siendo el Z óptimo una cota superior/inferior para las soluciones que obtengamos.

Pasos de Implementación:

• Se resuelve la RPL, si todos lso valores son enteros, entonces esta es también la solución óptima del PE.
• Si existe alguna variable con valor fraccionario entonces se divide el problema en dos nuevos subproblemas agregándole a cada uno una nueva restricción, de manera tal que se excluya el valor fraccionario.
• Se obtendran cuatro posibles resultados para cada subproblema:
  • Problema no factible, no se investiga más.
  • La solución del RPL, es entera, por lo tanto se la considera la mejor solución posible y se la guarda como cota inferior (en caso de ser maximización)
  • Si la solución del RPL es peor que alguna solución entera ya conocida, por lo que no se investiga más.
  • Si la solución de la relajación de PL es fraccionaria pero mejor que cualquier solución entera que se conoce hasta ese momoento, se divide la región factible para ese subproblema, de manera que se exluya una parte de la solución, y se repite el procedimiento hasta que no existan más subproblemas para investigar.
    

Uso de Variables Binarias

Variables que asumen 2 valores, 0-1. Representan todo o nada, hacer o no hacer, y se utilizan para representar condiciones lógicas, de tamaño del lote de producción y para incluir en la función objetivo costos fijos de producción.

Situaciónes con imprescindible uso de Variables Binarias:

• Restricciones de elección múltiple: Se utilizan para representar elecciones mutuamente excluyentes, por ejemplo elegir un proyecto u otro…
  

  $$x_i+x_j=1$$

• No más de k de entre n alternativas de un conjunto: Comprenden lso casos en los cuales, por ejemplo, se deben seleccionar no más de k proyectos de un conjunto de n proyectos factibles…
  

  $$x_1+x_2+\cdots +x_n\le k$$

• Decisiones dependientes (condicionales):

  • No se desea elegir la opción k a menos que se elija primero la opción m. Sin embargo la opción m puede ser elegida sin que lo sea la opción k.
    
    $$x_k\le x_m\text{ ó }{x}_k-x_m\le 0$$
  • Si se elige la opción m entonces la opción k también. A este tipo de restricciones se las suele llamar restricciones de correquisito, siempre que se elija la opción m, también debe ser elegida la opción k y viceversa.
    $$x_k-x_m=0$$
  • Si elige la inversión m, no podrá elegir la k y viceversa. Sin embargo puede no seleccionarse ninguna de las dos.
    $$x_k+x_m\le 1$$

• Restricciones en el tamaño del lote: Restricciones del tipo, "Si realizo esta acción

  $y_j$, hacerlo con un recurso
  $x_j$ de al menos o no más de esta cantidad
  $n$."
  
  $$x_j\le n\text{ ó }{x}_j\ge n$$

• Restricciones de costo fijo: Cuando existen costos de producción con dos componentes, uno fijo y otro variable. La variable con valor 0-1, nos permite incluir el componente fijo del costo, y condicionar el variable.

Análisis de Sensibilidad en Programas Lineales Enteros

falta eto ciro altoki