Scribd
Cargar
139 vistas3 páginas

Programacion Entera

La programación entera busca obtener la solución óptima para una función objetivo dadas sus restricciones, pero a diferencia de la programación lineal, las variables solo pueden tomar valores enteros. Existen tres tipos de programación entera: pura, mixta y binaria. Los algoritmos más comunes para resolver problemas de programación entera son la relajación lineal, la ramificación y acotamiento, y el método de los planos de corte. La programación entera se aplica comúnmente para la toma de decisiones en proyectos, contrataciones y diseño

Cargado por

Luis Angel
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
139 vistas3 páginas

Programacion Entera

La programación entera busca obtener la solución óptima para una función objetivo dadas sus restricciones, pero a diferencia de la programación lineal, las variables solo pueden tomar valores enteros. Existen tres tipos de programación entera: pura, mixta y binaria. Los algoritmos más comunes para resolver problemas de programación entera son la relajación lineal, la ramificación y acotamiento, y el método de los planos de corte. La programación entera se aplica comúnmente para la toma de decisiones en proyectos, contrataciones y diseño

Cargado por

Luis Angel
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
Está en la página 1/ 3

PROGRAMACION ENTERA

Como se ha visto ya en Programación Lineal, el cual busca obtener la solución óptima


para una función objetivo dado sus respectivas restricciones, ahora la Programación
Entera tendrá un ligero cambio, y es que ahora las variables del problema pueden tomar
valores enteros. Esto hace que el método de solución sea distinto al de Programación
Lineal ya que las variables se restringen a que solo tomen valores enteros.

Generalmente la estructura de la Programación Entera es la misma que la de


Programación Lineal, salvo algunos detalles:

Max / Min Z  cT x
s.a.
Ax , ,  b
x0
xi  Z para i  I  1, 2,..., n

Como se ve en la última línea, se encuentra la condición de que las variables deben


tomas valores enteros para un conjunto de valores, y de estos valores se pueden hacer
tres clasificaciones de la Programación Entera:

 Programación Entera Pura: cuando todas las variables del problema solo pueden
tomar valores enteros.
I  1, 2,3,..., n
 Programación Entera Mixta: se da cuando solo algunas de las variables
requieren que sea valores enteros.
I  1, 2,3,..., n
 Programación Entera Binaria: este es un caso específico ya que solo se dan dos
resultados, 1 si la variable se escoge y 0 si la variable no es tomada en cuenta.
Esto se ve más seguido en problemas de asignación, transportes, etc. Así:
1 si la decisión i es sí
xi   (i  1, 2,3,...)
0 si la decisión i es no

En este tipo de programación hace que aparezcan diferentes tipos de restricciones que
permitan cumplir la condición de que la variable sea entera, algunas de estas
restricciones son:

 Restricciones de tipo una u otra. En este tipo de restricciones, nos dan a elegir
que restricciones se cumplen bajo determinadas condiciones. En este caso solo
debemos de elegir UNA de las restricciones dadas en la condición (aunque
exista el caso que puedan cumplirse algunas restricciones, no necesariamente
una). Para la solución de estos casos se usa el método de la gran M.
 Restricciones del tipo “se deben cumplir K restricciones”. Aquí el problema ya
es más complejo, debido a que nos condicionan previamente que deben si o si
cumplirse K restricciones de un total de N. Para estos casos debemos aplicar la
misma lógica del caso anterior, salvo que debemos agregar una última
restricción:
N

y
i 1
i  N K

yi es binaria, para i  1, 2,3,..., N

Para la Programación Entera existen distintos algoritmos de solución, los más conocidos
son los siguientes:

 Enumeración Exhaustiva. Este tipo de solución no es recomendable ya que hace


que las soluciones crezcan de forma exponencial.
 Relajación Lineal. Consiste en resolver el problema como si fuese un problema
de Programación Lineal cualquiera. Si el óptimo satisface las condiciones de las
variables enteras, entonces se dice que esa es la solución al problema dado
 Ramificación y acotamiento. Divide el problema en problemas menores y se
descartan algunos de ellos. Se toma este método si la relajación lineal no
satisface las condiciones de las variables enteras. El algoritmo consta de 4 pasos
1. Crear dos subproblemas ramificando una variable.
2. Para cada subproblema determinar una cota (ya sea superior o inferior)
para la función objetivo.
3. Se deja de desarrollar una rama si:
a. La solución es entera
b. La función objetivo es peor que la cota
c. La solución no es factible
4. Si se ha recorrido todas las ramas, escoger como óptima aquella que
tenga mejor función objetivo.
 Método de los planos de corte. Son planos de corte a todas las restricciones
validas deducidas de las restricciones lineales: En este caso las soluciones
enteras van a verificar dichos planos de corte, hasta llegar a un óptimo.

APLICACIONES DE LA PROGRAMACION ENTERA

Las aplicaciones de la programación entera son muy diversas. Por ejemplo, la


Programación Entera Binaria es muy usada en casos de toma de decisiones de proyectos
(para comprobar cuan viable y optimo es el proyecto), contratación de personas o
servicios, análisis de inversión o diseño de redes de producción y distribución. En todas
ellas entra la toma de decisiones en la que es útil la PEB.
Un ejemplo aplicativo es el de la empresa de aerotransporte AIR New Zealand, la cual
usa la PEB para resolver problemas de planeación de viajes ocupados y problemas de
lista de turnos. Dicha empresa ahorra 6.7 millones de dólares al año por usar este
método de optimización, lo cual genera una increíble ganancia de 11% más de lo
normal.

Otra aplicación ilustrativa es de la empresa Taco Bell Corporation que cuenta con más
de 6500 establecimientos de comida rápida en Estados Unidos. Para ello usa la
Programación Entera Mixta (PEM) para resolver problemas de asignación de personal y
recursos en cada uno de sus establecimientos, esto le ha llevado ahorros en más de 13
millones de dólares al año en costos laborales.

También podría gustarte