Loading...
Loading...
INVESTIGACIONLoading...
DE OPERACIONESLoading...
By Marilyn Alouette Badillo Amaya
3.1. Introducción y casos de aplicación
Hasta ahora solo se han estudiado problemas de programación lineal en los
cuales la solución satisface las restricciones dadas. Estas restricciones incluyen
aditividad proporcional, divisibilidad y no negatividad. La divisibilidad implica que son
permitidas las soluciones fraccionarias para los problemas lineales. Sin embargo,
algunos modelos requieren que la solución, además de cumplir con todas las
restricciones, sea solo de números enteros.
Se considera que los pioneros de la programación entera fueron Wagner (1950)
y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases
de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos
sólo toman valores enteros, por lo que realmente deben considerarse como problemas
de programación entera. El número de modelos lineales enteros y sus métodos de
solución es en la actualidad bastante extenso. No siempre es admisible que las
variables de un PL tomen valores continuos, pudiendo presentarse dos casos:
• Decisiones dicotómicas (si
- no).
• Decisiones que deben tomarse en unidades discretas
.
Si se requiere que todas las variables sean enteras, se habla de Programación
Lineal Entera Pura; si se necesita que solo algunas de las variables de decisión sean
números enteros, se tiene un problema de Programación Lineal Entera Mixta.
En algunas aplicaciones, sólo se permite que todas las variables tomen valores
de cero o uno; se trata en estos casos de Programación Lineal Entera Binaria (Digital).
Si se requiere que solamente algunas de las variables tomen valores de cero o uno, se
tiene un problema de Programación Lineal Entera Binaria Mixta
Un ejemplo típico de este modelo se tiene en cualquier línea de producción en
serie, en la cual todas las variables (piezas) son números enteros (no se puede hablar
de medias piezas o de ¾ de pieza), y la solución óptima debe estar formada con
números enteros.
cuales la solución satisface las restricciones dadas. Estas restricciones incluyen
aditividad proporcional, divisibilidad y no negatividad. La divisibilidad implica que son
permitidas las soluciones fraccionarias para los problemas lineales. Sin embargo,
algunos modelos requieren que la solución, además de cumplir con todas las
restricciones, sea solo de números enteros.
Se considera que los pioneros de la programación entera fueron Wagner (1950)
y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases
de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos
sólo toman valores enteros, por lo que realmente deben considerarse como problemas
de programación entera. El número de modelos lineales enteros y sus métodos de
solución es en la actualidad bastante extenso. No siempre es admisible que las
variables de un PL tomen valores continuos, pudiendo presentarse dos casos:
• Decisiones dicotómicas (si
- no).
• Decisiones que deben tomarse en unidades discretas
.
Si se requiere que todas las variables sean enteras, se habla de Programación
Lineal Entera Pura; si se necesita que solo algunas de las variables de decisión sean
números enteros, se tiene un problema de Programación Lineal Entera Mixta.
En algunas aplicaciones, sólo se permite que todas las variables tomen valores
de cero o uno; se trata en estos casos de Programación Lineal Entera Binaria (Digital).
Si se requiere que solamente algunas de las variables tomen valores de cero o uno, se
tiene un problema de Programación Lineal Entera Binaria Mixta
Un ejemplo típico de este modelo se tiene en cualquier línea de producción en
serie, en la cual todas las variables (piezas) son números enteros (no se puede hablar
de medias piezas o de ¾ de pieza), y la solución óptima debe estar formada con
números enteros.
3.2. Definición y modelos de programación entera.
Definición Y Modelos De Programación Entera La programación entera está relacionada con la resolución de problemas de optimización en los cuales al menos algunas de las variables deben tomar sólo valores enteros. Cuando todos los términos son lineales se habla de programación lineal entera. Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a las formuladas en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final. Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras sólo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones lógicas. Este tipo de modelos permite representar sistemas mucho más complejos. Muchos problemas de naturaleza combinatoria se pueden formular en términos de programación entera
3.3. Método gráfico de programación entera
Para resolver un problema de Programación Entera mediante el Método Gráfico, se siguen estos
siguientes pasos:
1. Se grafican las restricciones originales así como la Función Objetivo. Si en la solución
óptima todas las variables son números Enteros, “Pare” ya se tiene la solución óptima
correcta. Si no es así, continúe al siguiente paso.
2. Analizar todos los puntos Enteros ubicados dentro de la región Factible y sustituir los
valores en cada restricción y en la Función Objetivo para asegurar que cumplan con cada
una de estas restricciones (se recomienda hacerlo en forma tabular).
3. El par de variables Enteras dentro de la Región Factible, que arroje las máximas utilidades
(caso Maximizar) o el menor costo (caso Minimizar), y que satisfaga todas las restricciones
del Modelo Original, representan la solución óptima del problema
siguientes pasos:
1. Se grafican las restricciones originales así como la Función Objetivo. Si en la solución
óptima todas las variables son números Enteros, “Pare” ya se tiene la solución óptima
correcta. Si no es así, continúe al siguiente paso.
2. Analizar todos los puntos Enteros ubicados dentro de la región Factible y sustituir los
valores en cada restricción y en la Función Objetivo para asegurar que cumplan con cada
una de estas restricciones (se recomienda hacerlo en forma tabular).
3. El par de variables Enteras dentro de la Región Factible, que arroje las máximas utilidades
(caso Maximizar) o el menor costo (caso Minimizar), y que satisfaga todas las restricciones
del Modelo Original, representan la solución óptima del problema
3.4. Método de ramificación y acotación
Para resolver problemas de Programación Entera a través del Método de Branch & Bound
(Ramificar y Acotar), se recomienda seguir los siguientes pasos:
1. Resolver primeramente el problema por medio del Método Simplex o Método Gráfico de
PL (depende de la preferencia de quien lo resuelve y de la cantidad de variables). Si en la
solución, todas las variables son Enteras, “Pare”, ya que se ha conseguido la solución
óptima, en caso contrario pasar al siguiente paso.
2. Escójase arbitrariamente una de las variables encontradas en el paso anterior, cuyo
resultado no sea entero (valor fraccionario)
3. En base a la variable escogida en el paso 2, resuélvase un par de nuevos problemas, uno
con la Restricción Xi(ENTERA) ≤ [Xi(ESCOGIDA)], mientras que la otra tendría la restricción
Xi(ENTERA) ≥ [Xi(ESCOGIDA) + 1].
4. De los problemas lineales resueltos en el paso anterior, inclúyanse en el análisis a seguir,
solo aquellos problemas cuya solución entera o fraccional, sea mejor a cualquiera de las
soluciones enteras conocidas.
5. Al seleccionar la solución cuyas variables arrojen el máximo o mínimo valor (según la
función objetivo). Si las variables tienen un valor entero, se ha llegado a la solución del
problema, si no es así, regresar al paso 2 con la estructura del problema de programación
lineal resuelto hasta este paso
(Ramificar y Acotar), se recomienda seguir los siguientes pasos:
1. Resolver primeramente el problema por medio del Método Simplex o Método Gráfico de
PL (depende de la preferencia de quien lo resuelve y de la cantidad de variables). Si en la
solución, todas las variables son Enteras, “Pare”, ya que se ha conseguido la solución
óptima, en caso contrario pasar al siguiente paso.
2. Escójase arbitrariamente una de las variables encontradas en el paso anterior, cuyo
resultado no sea entero (valor fraccionario)
3. En base a la variable escogida en el paso 2, resuélvase un par de nuevos problemas, uno
con la Restricción Xi(ENTERA) ≤ [Xi(ESCOGIDA)], mientras que la otra tendría la restricción
Xi(ENTERA) ≥ [Xi(ESCOGIDA) + 1].
4. De los problemas lineales resueltos en el paso anterior, inclúyanse en el análisis a seguir,
solo aquellos problemas cuya solución entera o fraccional, sea mejor a cualquiera de las
soluciones enteras conocidas.
5. Al seleccionar la solución cuyas variables arrojen el máximo o mínimo valor (según la
función objetivo). Si las variables tienen un valor entero, se ha llegado a la solución del
problema, si no es así, regresar al paso 2 con la estructura del problema de programación
lineal resuelto hasta este paso
3.5. Método heurístico para problemas binarios
Reciben el nombre de algoritmos heurísticos, metaheurísticos o sencillamente heurísticos. Este término deriva de la palabra griega heuriskein que significa encontrar o descubrir y se usa en el ámbito de la optimización para describir una clase de algoritmos de resolución de problemas. En el lenguaje coloquial, optimizar significa poco más que mejorar; sin embargo, en el contexto científico la optimización es el proceso de tratar de encontrar la mejor solución posible para un determinado problema. En un problema de optimización existen diferentes soluciones, un criterio para discriminar entre ellas y el objetivo es encontrar la mejor. De forma más precisa, estos problemas se pueden expresar como encontrar el valor de unas variables de decisión para los que una determinada función objetivo alcanza su valor máximo o mínimo. El valor de las variables en ocasiones está sujeto a unas restricciones. Podemos encontrar una gran cantidad de problemas de optimización, tanto en la industria como en la ciencia