Investigacion de Operaciones 1

INVESTIGACION DE
OPERACIONES 1
Unidad III. Programación Entera

Arq. Jonathan Ramiro Grijalva Herrera
Contenido
3.1. Introducción y casos de
aplicación.
Introducción a la programación entera
Es frecuente al tener que resolver problemas en los cuales las soluciones
tienen que ser valores enteros como por ejemplo: números de unidades a
producir por máquina, número de máquinas necesarias, etc. Parte del problema
de la programación entera radica en la diferencia esencial que existe la
programación lineal y la entera, en la programación lineal se maximiza o
minimiza una función sobre una región de factibilidad convexa, mientras que al
usar los métodos de programación entera se maximiza una función sobre una
región de factibilidad que generalmente no es convexa.
De tal manera que la programación entera tiene más complicaciones que la

programación lineal. En este tema se presenta un tipo de problemas
formalmente similares a los problemas de Programación Lineal, ya que en su
descripción solo se establecen expresiones lineales. Sin embargo no
responden a problemas lineales ya que algunas (o todas) las variables del
problema toman valores que no están en un conjunto continuo.
Por ejemplo, pueden ser variables que toman valores 0 o 1(binarias), o
variables que toman valores enteros no negativos (0, 1,2,...), etc. Tras introducir
el tipo de problemas se dedica un importante apartado para presentar las
posibilidades de modelado que esta herramienta proporciona: problemas
binarios, problemas decarga, problemas con restricciones condicionales o con
dicotomías, etc. Trasdedicar una parte importante del tema a presentar estas
herramientas de modelado y a plantear numerosos problemas con ellas se
procede a mostrar dos métodos de resolución. Uno de ellos dedicado a
problemas en los que todas las variables son binarias y otro para problemas
generales. Ambos métodos tienen en común que desarrollan un proceso de e
numeración que permite comprobar explícita o implícitamente todas las
soluciones del problema hasta encontrar la óptima, y entran dentro del tipo de
métodos de ramificación y acotación.
En algunos casos se requiere que la solución óptima se componga de valores
enteros para algunas de las variables. La resolución de este problema se
obtiene analizando las posibles alternativas de valores enteros de esas
variables en un entorno al rededor de la solución obtenida considerando las
variables reales.Muchas veces la solución del programa lineal truncado está
lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo
para hallar esta solución de forma exacta.
Aplicaciones
Las aplicaciones de la programación entera son las siguientes:
 Todos los problemas de programación lineal, donde las actividades, por su

estructura deben ser no-divisibles, son programas enteros.
 Todos los problemas de transporte, asignación y redes de optimización. Este

tipo de problemas son enteros y dada la estructura tan especial de estos
problemas, tienen métodos de solución propios.
 Problemas de secuenciación. Este tipo de problemas aun que son fáciles de

formular, resultan bastantes difíciles de resolver, los cuales llevan una
secuencia.

 El problema del agente viajero. Este problema
concierne en un agente viajero que saliendo de una terminal de ciudad debe
visitar una sola vez n-1ciudades diferentes, y regresar al punto de partida.
 Problema tipo mochila. Este tipo de problemas de optimización de carácter

entero puede darse en dos versiones. En la primera se proporciona un
cierto espacio con determinado volumen o capacidad, y este debe ser
llenado con objetos de valor y volumen o capacidades especificados.
 Problemas de inversión. Estos problemas pueden ser de distintos tipos de

inversión, siempre y cuando se añada con el hecho de que la programación
sea entera.
 Problemas con costos fijos. Todos los problemas que en su función de costo
influyen un costo fijo del siguiente tipo pertenecen al grupo de problemas
enteros. Este tipo de costos aparecen frecuentemente en problemas de
transportes, inventarios, localización de plantas, distribución geográfica de
electores, etc.
 Problemas de cubrimiento y partición de un conjunto. Este tipo de modelos de

carácter entero se ha utilizado en problemas de acceso de
información,programación de entrega de paquetería por transporte terrestre,
distribución política electoral, problemas matemáticos de coloración y
programación de horarios de tripulación aéreos, ferrocarrileros, terrestres y
marítimos.
 Dicotomías y problemas de aproximación. Una dicotomía ocurre en un

programa matemático cuando se tienen condiciones de tipo esta restricción o la
otra restricción, pero no ambas. Este tipo de condiciones se pueden
representar por medio de una estructura entera.
 j) Balance de líneas de producción. Este tipo de problemas consisten en
decidir qué actividades deben ser desempeñadas por cada trabajador, a
medida que un producto se desplaza por una línea de producción. El
objetivo consiste en 0, si = 0, 0 ≤ ≤, j=1,2,… n +,si > 0 minimizar el número
de trabajadores (o estaciones de trabajo o actividades) en función de una
tasa de producción.
 k) Asignación cuadrática. Estos aparecieron en problemas

de localización,existe un conjunto de n posibles lugares en donde se piensa
construir n plantas industriales m<n sea el costo unitario de transporte de
lugar i al lugar j y sea el volumen que se debe transferir de la planta
industrial k a la planta industrial p.
3.2. Definición y modelos de
programación entera.
Definición
Los modelos de Programación Entera son aquellos donde la totalidad o un
subconjunto de las variables de decisión toman valores enteros. En este
sentido laforma estándar de un modelo de Programación Entera queda definido
de la siguiente forma:
Existen múltiples aplicaciones de modelos de Programación Entera como

apoyo a la toma de decisiones. Algunas aplicaciones típicas son problemas de
localización de instalaciones, inclusión de costos fijos, problemas de
asignación, problemas de ruteo vehicular, etc.
Modelos de Programación Entera
Los modelos de Programación Entera se pueden clasificar en 3 grandes
áreas:Programación Entera Mixta (PEM), Programación Entera Pura (PEP)
yProgramación Binaria.
Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas
de optimización que consideran variables de decisión enteras o binarias pero
no de forma exclusiva. De esta formaun problema de PEM puede considerarse
como un híbrido entre distintas categoríasde modelamiento, siendo un caso
típico aquel que considera la mezcla de variables enteras y variables continuas
(estas últimas características de los modelos de Programación Lineal). A modo
de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta
de modelos de Programación Entera Mixta:
Programación Entera Pura (PEP)
En esta categoría en contramos aquellos modelos de Programación Entera que
consideran exclusivamente variables de decisión que adoptan valores enteros
obinarios. Un ejemplo de ello son las siguientes aplicaciones:
Notar que en los problemas anteriores (PEP) el conjunto de las soluciones

factibles(o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente
con los problemas de Programación Entera (puros).
Programación Binaria.
En Matemática Aplicada la programación binaría hace referencia a aquella cuyo
conjunto de soluciones sólo puede tomar uno de dos posibles valores: 1 ó 0. Es
un caso especial de la Programación Entera. Esta herramienta matemática es
especialmente útil para enfrentar problemas de tipo de toma de decisiones Si o
No. El Problema de la asignación, es un caso particular de esta metodología,
dónde se debe asignar unos recursos limitados a unas tareas específicas de
manera óptima.
3.3. Método gráfico de
programación entera.
El método gráfico se emplea para resolver problemas que presentan sólo 2
variables de decisión. El procedimiento consiste en trazar las ecuaciones de las
restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área
de solucionesfactibles (soluciones que cumplen con todas las restricciones).
La solución óptima del problema se encuentra en uno de los vértices de esta

área de soluciones creada, por lo que se buscará en estos datos el valor
mínimo o máximo del problema.
EJEMPLO:
Una compañía de auditores se especializa en preparar liquidaciones y
auditorías de empresas pequeñas. Tienen interés en saber cuántas auditorías y
liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se
dispone de 800horas de trabajo directo y 320 horas para revisión. Una auditoría
en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, a
demás aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8
horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100
dls. El máximo de liquidaciones mensuales disponibles es de 60.
La solución óptima siempre se encuentra en uno de los vértices del conjunto de
soluciones factibles. Se analizan estos valores en la función objetivo. El vértice
que representa el mejor valor de la función objetivo será la solución óptima.

Investigacion de Operaciones 1

Cargado por

Copyright:

Formatos disponibles

Investigacion de Operaciones 1

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Investigacion de Operaciones 1

Cargado por

Copyright:

Formatos disponibles

INVESTIGACION DE

Unidad III. Programación Entera

De tal manera que la programación entera tiene más complicaciones que la

 Todos los problemas de programación lineal, donde las actividades, por su

 Todos los problemas de transporte, asignación y redes de optimización. Este

 Problemas de secuenciación. Este tipo de problemas aun que son fáciles de

 Problema tipo mochila. Este tipo de problemas de optimización de carácter

 Problemas de inversión. Estos problemas pueden ser de distintos tipos de

 Problemas de cubrimiento y partición de un conjunto. Este tipo de modelos de

 Dicotomías y problemas de aproximación. Una dicotomía ocurre en un

 k) Asignación cuadrática. Estos aparecieron en problemas

Existen múltiples aplicaciones de modelos de Programación Entera como

Programación Entera Mixta (PEM)

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones

La solución óptima del problema se encuentra en uno de los vértices de esta

También podría gustarte