PROGRAMACION LINEAL ENTERA

PROGRAMACIÓN LINEAL ENTERA

Clase de problemas que se modelan como programas lineales con el REQUERIMIENTO ADICIONAL de que una o más variables deben ser números enteros.

1. TIPOS DE MODELOS DE PLE:

PROGRAMA LINEAL SOLO CON ENTEROS Si todas las variables deben ser enteras.

PROGRAMA LINEAL ENTERO MIXTO Si alguna de las variables, pero no todas, deben ser enteros.

PROGRAMA LINEAL CON ENTEROS 0-1 Si las variables enteras solo pueden tomar el valor 0-1 (VARIABLES BINARIAS) .Las variables 0-1 proporcionan capacidad adicional de modelado. En algunos problemas las variables 0-1 se utilizan para modelar los cambios en la línea de producción; las variables continuas modelan las cantidades de producción.

*EL PROGRAMA LINEAL QUE RESULTA DE OMITIR LOS REQUERIMIENTOS DE ENTEROS SE LLAMA RELAJACIÓN PL DEL PROGRAMA LINEAL ENTERO.

-Las variables enteras, EN ESPECIAL LAS VARIABLES 0-1, proporcionan una flexibilidad de modelado considerable. Como resultado de ello, el número de aplicaciones que pueden tratarse con la metodología de la PL aumenta.

-La PE da un COSTO DE LA FLEXIBILIDAD DE MODELADO AGREGADO y es que los problemas que involucran variables enteras con frecuencia son mucho más difíciles de resolver. (Un problema de PL con varios miles de variables continuas puede resolverse con cualquiera de los solucionadores de programación lineal comerciales. Sin embargo, un problema de PL solo con ENTEROS con menos de 100 variables puede ser sumamente difícil de resolver)

-Debido a que los PLE son más difíciles de resolver que los PL, no es conveniente tratar de resolver un problema como un PE cuando es razonable redondear la solución de la PL. En muchos problemas de PL, es redondeo tiene poca consecuencia económica sobre la FO, y la factibilidad no es un problema. Pero en problemas como la determinación de cuántos motores de avión fabricar, las consecuencias del redondeo pueden ser significativas, y debe emplearse la metodología de la PE.

-Algunos problemas de PL tienen una estructura especial que garantiza que las variables tendrán valores enteros (TRANSPORTE, TRANSBORDO y ASIGNACIÓN)

Para estos problemas estructurados de manera especial, se puede utilizar la metodología de la PL para encontrar soluciones enteras óptimas.

2. REDONDEO PARA OBTENER UNA SOLUCIÓN CON ENTEROS:

-En muchos casos, una SOLUCIÓN NO ENTERA puede redondearse para obtener una solución aceptable CON ENTEROS.

-De hecho, siempre que el redondeo tiene un IMPACTO MÍNIMO sobre la función objetivo y las restricciones, la mayoría de los administradores o gerentes lo considera aceptable. Una solución CASI ÓPTIMA está bien.

- Sin embargo, el REDONDEO NO SIEMPRE es una buena estrategia. Cuando las variables de decisión adoptan valores pequeños que tienen un impacto importante en el valor de la FO o en la FACTIBILIDAD, se necesita una solución con enteros óptimos.

- EL REDONDEO A UN SOLUCIÓN CON ENTEROS es un método de prueba y error.

Para cada solución redondeada debe evaluarse:

 la factibilidad

 El impacto en el valor de la FO.

Incluso en casos donde una solución redondeada es factible, NO TENEMOS GARANTÍA de que hemos encontrado la solución con enteros óptima.

3. USO DE LA RELAJACIÓN PL PARA ESTABLECER LÍMITES:

-Para los PLE que involucran MAXIMIZACIÓN, el valor de la:

SOLUCIÓN ÓPTIMA CON RELAJACIÓN >= SOLUCIÓN ÓPTIMA CON ENTEROS

-LA PROPIEDAD RESTRICTIVA de la relajación PL nos permite concluir que si, por casualidad, la solución a una relajación PL resulta ser con ENTEROS, también es ÓPTIMA para el PLE.

Esta PROPIEDAD RESTRICTIVA también es útil en la determinación de si una solución redondeada es “suficientemente buena” Si una solución de relajación PL redondeada es factible y proporciona un valor de la FO que es “casi tan bueno” como el valor de la FO para la relajación PL, sabemos que la solución redondeada es una solución con enteros casi óptima. En este caso, podemos evitar resolver el problema como un PLE.

4. APLICACIONES QUE INVOLUCRAN VARIABLES 0-1:

-Gran parte de la flexibilidad de modelado proporcionada por la PLE se debe al uso de variables 0-1.

-En muchas aplicaciones, las variables 0-1 proporcionan selecciones u opciones con el valor de la variable igual a 1 SI SE REALIZA UNA ACTIVIDAD correspondiente, e igual a 0 SI NO SE REALIZA DICHA ACTIVIDAD.

a) ELABORACIÓN DEL PRESUPUESTO DE CAPITAL/PROBLEMA DEL PRESUPUESTO/PROBLEMA DE LA MOCHILA/KNAPSACK PROBLEM:

-Lo tienen todas las empresas (a principios o a fin de año las empresas se preguntan qué proyecto hacer, pero tenemos un PRESUPUESTO DE INVERSIÓN).

-Se respeta una ecuación de igualdad #=# o una ecuación de menor igual  #<= # (que es un presupuesto)

-Típicamente tiene una sola restricción y es la del PRESUPUESTO.

OBJETIVO  Optimizar rendimiento/costos.

OBJETOS SELECCIONADOS  Proyectos.

*BENEFICIO Valor presente neto (VPN)

*COSTO  Fondos a invertir para ejecutar proyectos

CAPACIDAD  PRESUPUESTO.

*VARIABLES DE DECISIÓN:

Xj= [0; 1] 1= se hace el proyecto.

0= no se hace el proyecto

-En un problema de ELABORACIÓN DEL PRESUPUESTO DE CAPITAL, la FO de la empresa es MAXIMIZAR el VPN DE LOS PROYECTOS de la elaboración del presupuesto de capital.

b) COSTO FIJO/PROBLEMA DEL CARGO FIJO/ FIXED-CHARGE PROBLEM:

-En una fábrica tenemos varias líneas de producción, pero para activarlas tenemos que gastar diferentes precios. Para activar una actividad determinada hay que incurrir siempre EN UN CARGO FIJO.

-En muchas aplicaciones, el costo de producción tiene 2 componentes:

 Un costo de preparación  COSTO FIJO

 Volumen de

...