Programación Lineal Entera
Páginas: 6 (1283 palabras)
Publicado: 18 de julio de 2011
INVESTIGACION DE OPERACIONES
Programación Lineal Entera
Hasta ahora hemos visto los problemas de programación lineal en el dominio de los números reales (incluyendo enteros y decimales).
Sin embargo, en muchos modelos algunas o todas las variables de decisión deben ser enteras. Estos modelos son conocidos como modelos de programación lineal entera (PLE).
A primera vista podría parecermás fácil resolver problemas con restricción de enteros, ya que transforman un problema continuo en un problema discreto. Sin embargo, los algoritmos que permiten resolver los problemas PLE son más complejos y requieren muchas más iteraciones para arrojar una solución.
Los modelos de programación lineal entera se pueden clasificar en:
|Modelos de programación entera |Tipos de variablesde decisión |
|Entera |Todas son enteras |
|Mixto |Algunas, pero no todas son enteras |
|Binaria |Todas son binarias (1 ó 0) |
PROBLEMA 1
Boxcar es una nueva cadena de restaurantes decomida rápida (fast-food) que está planificando expandirse en Washington DC.
La compañía dispone de $ 2.7 millones para su expansión. Cada restaurante en los suburbios requiere $ 200.000 en inversión, y cada local en el centro requiere de $ 600.000.
Se proyecta que luego de los gastos, la ganancia neta semanal en los locales de los suburbios (que estarán abiertos las 24 horas) será en promedio $1200. Los restaurantes del centro abrirán sólo 12 horas al día, pero debido a una gran cantidad de clientes durante las horas de trabajo las proyecciones indican que la ganancia neta semanal será de $ 2000. La compañía desea abrir al menos 2 restaurantes en el centro. Boxcar actualmente tiene 19 administradores. Cada local en los suburbios requerirá tres administradores para su funcionamiento las24 horas, y se cree que con sólo un administrador en el centro por restaurante sería suficiente.
Boxcar desea saber cuántos restaurantes podría abrir para maximizar su ganancia neta semanal.
Solución
Resumiendo el problema, se tiene
▪ Boxcar debe decidir cuántos restaurantes debe abrir en los suburbios
▪ y en el centro de Washington DC
▪ Desean maximizar suganancia total semanal promedio
▪ La inversión total no puede exceder $ 2.7 millones
▪ Se deben abrir al menos 2 restaurantes en el centro
▪ Sólo se cuenta con 19 administradores.
Un Modelo Matemático sería:
Máx 1200 A + 2000 B
s.a.
2 A + 6 B ≤ 27
B ≥ 2
3 A + B ≤ 19
A, B ≥ 0, enteros
Siendo:
A: cantidad derestaurantes a habilitar en los suburbios
B: cantidad de restaurantes a habilitar en el centro
La solución real del problema es:
A = 5,4375 B = 2,6875 Z = $ 11.900
Surgen naturalmente algunas interrogantes:
¿Por qué no redondear simplemente los valores la solución real?
Posibles resultados del redondeo:
▪ Los puntos pueden ser no-factibles
▪ Los puntos pueden serfactibles pero no-óptimos
▪ Los puntos pueden ser factibles y óptimos
La solución entera del problema es: A = 4, B = 3, Z = US$ 10.800
IMPORTANTE: Imponer restricción de enteros agrega dos restricciones al problema: A entero y B entero. Así es que el valor de la función objetivo NO puede mejorar. En un problema de maximización, por ejemplo, esto significa que el valor de la funciónobjetivo disminuirá o en el mejor de los casos será el mismo que el valor óptimo del problema de programación lineal en el dominio de los reales.
PROBLEMA 2
Después de muchos años con bajos intereses en los bancos, la Sra. Mendoza ha decidido incursionar en la bolsa. Sin embargo, ella desea hacer una inversión cautelosa. Ella escuchó que las acciones de una compañía de telefonía celular se...
Programación Lineal Entera
Hasta ahora hemos visto los problemas de programación lineal en el dominio de los números reales (incluyendo enteros y decimales).
Sin embargo, en muchos modelos algunas o todas las variables de decisión deben ser enteras. Estos modelos son conocidos como modelos de programación lineal entera (PLE).
A primera vista podría parecermás fácil resolver problemas con restricción de enteros, ya que transforman un problema continuo en un problema discreto. Sin embargo, los algoritmos que permiten resolver los problemas PLE son más complejos y requieren muchas más iteraciones para arrojar una solución.
Los modelos de programación lineal entera se pueden clasificar en:
|Modelos de programación entera |Tipos de variablesde decisión |
|Entera |Todas son enteras |
|Mixto |Algunas, pero no todas son enteras |
|Binaria |Todas son binarias (1 ó 0) |
PROBLEMA 1
Boxcar es una nueva cadena de restaurantes decomida rápida (fast-food) que está planificando expandirse en Washington DC.
La compañía dispone de $ 2.7 millones para su expansión. Cada restaurante en los suburbios requiere $ 200.000 en inversión, y cada local en el centro requiere de $ 600.000.
Se proyecta que luego de los gastos, la ganancia neta semanal en los locales de los suburbios (que estarán abiertos las 24 horas) será en promedio $1200. Los restaurantes del centro abrirán sólo 12 horas al día, pero debido a una gran cantidad de clientes durante las horas de trabajo las proyecciones indican que la ganancia neta semanal será de $ 2000. La compañía desea abrir al menos 2 restaurantes en el centro. Boxcar actualmente tiene 19 administradores. Cada local en los suburbios requerirá tres administradores para su funcionamiento las24 horas, y se cree que con sólo un administrador en el centro por restaurante sería suficiente.
Boxcar desea saber cuántos restaurantes podría abrir para maximizar su ganancia neta semanal.
Solución
Resumiendo el problema, se tiene
▪ Boxcar debe decidir cuántos restaurantes debe abrir en los suburbios
▪ y en el centro de Washington DC
▪ Desean maximizar suganancia total semanal promedio
▪ La inversión total no puede exceder $ 2.7 millones
▪ Se deben abrir al menos 2 restaurantes en el centro
▪ Sólo se cuenta con 19 administradores.
Un Modelo Matemático sería:
Máx 1200 A + 2000 B
s.a.
2 A + 6 B ≤ 27
B ≥ 2
3 A + B ≤ 19
A, B ≥ 0, enteros
Siendo:
A: cantidad derestaurantes a habilitar en los suburbios
B: cantidad de restaurantes a habilitar en el centro
La solución real del problema es:
A = 5,4375 B = 2,6875 Z = $ 11.900
Surgen naturalmente algunas interrogantes:
¿Por qué no redondear simplemente los valores la solución real?
Posibles resultados del redondeo:
▪ Los puntos pueden ser no-factibles
▪ Los puntos pueden serfactibles pero no-óptimos
▪ Los puntos pueden ser factibles y óptimos
La solución entera del problema es: A = 4, B = 3, Z = US$ 10.800
IMPORTANTE: Imponer restricción de enteros agrega dos restricciones al problema: A entero y B entero. Así es que el valor de la función objetivo NO puede mejorar. En un problema de maximización, por ejemplo, esto significa que el valor de la funciónobjetivo disminuirá o en el mejor de los casos será el mismo que el valor óptimo del problema de programación lineal en el dominio de los reales.
PROBLEMA 2
Después de muchos años con bajos intereses en los bancos, la Sra. Mendoza ha decidido incursionar en la bolsa. Sin embargo, ella desea hacer una inversión cautelosa. Ella escuchó que las acciones de una compañía de telefonía celular se...
Leer documento completo
Regístrate para leer el documento completo.