INSTITUTO TECNOLOGICO DE

CIUDAD GUZMAN

Ingeniería Industrial

Investigación de Operaciones

“Programación Entera”

Alumno: Eduardo Vargas Mata

Maestra: Erika Citlali Rodríguez

López
 Introducción

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel

cuya solución óptima tiene sentido solamente si una parte o todas las variables de
decisión toman valores restringidos a números enteros, permitiendo incorporar en
el modelamiento matemático algunos aspectos que quedan fuera del alcance de
los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación

Entera difieren a los utilizados en los modelos de Programación Lineal,
destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch &
Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas:

Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).
Índice

Portada ------------------ 1

Introducción ----------------- 2

Índice ------------------------------- 3

Definición y Modelos de Programación Entera-------------------- 4

Casos de aplicación----------------------------------------------- 7 a 20
La programación entera es el método empleado para resolver problemas que
tienen
variables de decisión enteras. Estos modelos se han considerado submodelos de
la
programación lineal con la característica de enteridad. Uno de los primeros
enfoques de solución al tipo de problemas que plantea la programación entera, fue
el de evaluación de cada posible solución, es decir, cada una de las
combinaciones
de valores enteros para las variables del problema, conduciendo a una solución
óptima exacta.
Un modelo de programación entera es aquel cuya solución óptima tiene
sentido
solamente si una parte o todas las variables de decisión toman valores
restringidos
a números enteros, permitiendo incorporar en el modelamiento matemático
algunos
aspectos que quedan fuera del alcance de los modelos de programación línea.
En este sentido los algoritmos de resolución de los modelos de programación
entera
difieren a los utilizados en los modelos de programación lineal, destacándose
entre
ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch &
Cut,
Planos cortantes, Relajación Lagrangeana, entre otros.
Los modelos de programación entera se pueden clasificar en: programación
entera
mixta (PEM), programación entera pura (PEP) y programación entera binaria
(PEB).

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 forma un problema de PEM puede considerarse como un
híbrido entre distintas categorías de 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).

Por ejemplo:
 Incorporacion de costos fijos
 Problemas de localización y transporte
 Problemas de generación eléctrica
Programación Entera Pura (PEP). En esta categoría encontramos aquellos
modelos
de programación entera que consideran exclusivamente variables de decisión que
adoptan valores enteros o binarios.
Por ejemplo:
 Problemas de asignación
 Problemas de corte de rollos
 Selección de invitados a una boda
Programación entera binaria (PEB). Es un método perteneciente a la
programación
 lineal, por lo que su base es un algoritmo matemático que tiene
como finalidad
 resolver un problema indeterminado formulado a través de ecuaciones
lineales,
 optimizando así una función objetivo también lineal que generalmente se
refiere a
 costo o a tiempo.
 Se utiliza en problemas de asignación o de toma de decisiones enfocadas a
hacer
 o no una tarea, entre sus campos de aplicación más comunes se
encuentran

• Problemas de asignación
• Problemas de corte de
rollos
• Selección de invitados a
una boda
• Programación de la
explotación forestal
• Problema de la mochila
METODO DE RAMIFICACION Y ACOTACION

El método de Branch and Bound (o Ramificación y Acotamiento) es un algoritmo

diseñado para la resolución de modelos de Programación Entera. ... El algoritmo
genera en forma recursiva cotas (o restricciones adicionales) que favorecen la
obtención de valores enteros para las variables de decisión.

De esta forma, ¿qué es el algoritmo de ramificacion y acotamiento?

El método de Branch and Bound (o Ramificación y Acotamiento) es

un algoritmo diseñado para la resolución de modelos de Programación Entera. ...
El algoritmo genera en forma recursiva cotas (o restricciones
adicionales) que favorecen la obtención de valores enteros para las variables de
decisión.
En consecuencia, ¿qué es el metodo grafico de programación entera?

La programación entera es el método empleado para resolver

problemas que tienen variables de decisión enteras. Estos modelos se han
considerado submodelos de la programación lineal con la característica de
enteridad.
De la siguiente manera, ¿dónde se aplica la programación entera?

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.

El método heurístico es una técnica utilizada para resolver problemas de optimización,

especialmente en situaciones donde no se conoce una solución algorítmica precisa o cuando
encontrar la solución exacta requeriría demasiado tiempo de cómputo. A continuación, te
proporciono información relevante sobre este método:
1. Definición y Concepto:
o Los métodos heurísticos, también conocidos como algoritmos heurísticos o
metaheurísticas, se basan en la búsqueda de soluciones aproximadas a
problemas de optimización.
o La palabra “heurístico” proviene del griego “heuriskein”, que significa
“encontrar” o “descubrir”. En el contexto de la optimización, se refiere a una
clase de algoritmos que buscan resolver problemas de manera eficiente sin
garantizar la solución óptima.
o En un problema de optimización, existen diferentes soluciones posibles, un
criterio para evaluarlas y el objetivo es encontrar la mejor solución dentro de
ciertas restricciones.
2. Dificultad de los Problemas de Optimización:
o Algunos problemas de optimización son relativamente fáciles de resolver,
como los problemas lineales. Sin embargo, muchos otros son muy difíciles y
caen en la categoría de “NP-hard”.
o Un problema “difícil de resolver” en términos científicos es aquel para el
cual no podemos garantizar encontrar la mejor solución en un tiempo
razonable.
3. Programación Binaria:
o La programación entera binaria es un método perteneciente a la
programación lineal. Se basa en algoritmos matemáticos para resolver
problemas formulados mediante ecuaciones lineales.
o En la programación binaria, las variables de decisión toman valores 0 o 1
(binarios), y se optimiza una función objetivo lineal (por ejemplo, costo o
tiempo).
4. Método IDEAL:
o El método heurístico “IDEAL”, formulado por Bransford y Stein, consta de
cinco pasos: Identificar el problema, definirlo, explorar estrategias viables,
avanzar en las estrategias y lograr una solución (evaluando los efectos).

En resumen, los métodos heurísticos nos permiten encontrar soluciones rápidas y buenas
(aunque no necesariamente óptimas) para problemas de optimización. Si tienes alguna
pregunta específica o necesitas más detalles, no dudes en preguntar
Ejercicios Resueltos
Ejercicio 1

1: Resolver gráficamente el siguiente sistema de ecuaciones:

SOLUCIÓN:

Lo primero que hacemos es despejar la y𝑦 en ambas ecuaciones para

que sea más fácil calcular los puntos.

Primera ecuación:

Segunda ecuación:

Ahora vamos a calcular unos cuantos puntos de las dos funciones

para representarlas (con 2 es suficiente).
Utilizaremos x=0𝑥=0 y x=2𝑥=2.

Para la primera función tenemos la tabla

Ahora representamos los puntos de cada tabla y los unimos para
obtener las rectas:

La solución del sistema es el punto donde las gráficas se cortan

(intersección de la recta), es decir:

Para la segunda función tenemos la tabla

Ahora representamos los puntos de cada tabla y los unimos para
obtener las rectas:

La solución del sistema es el punto donde las gráficas se cortan

(intersección de la recta), es decir:

Ejerer

Ejercicio 2 anterior
 Ejercicio 3
3:Un burro puede transportar como máximo 300 zanahorias y, además,
necesita comer una zanahoria por cada kilómetro que recorre. Si no lleva
zanahorias para comer se detiene y no sigue caminando.
¿Cuál el el mayor número de zanahorias que conseguiremos transportar
hasta el mercado?»
Analicemos el problema para intentar comprenderlo.
Tenemos unas zanahorias en el punto de partida…

… bueno, alguna más…

 … ¡Tampoco tantas! Vamos a dejarlo en 900 zanahorias.
Tenemos también un burro que como máximo puede transportar de
una vez 300 zanahorias (tan solo hay que verle la cara al pobre)…
y un mercado al que tenemos que conseguir que llegue el mayor número
posible de ellas, y que está a una distancia del punto de partida de 300
km.
Nuestro burro necesita comerse una zanahoria por cada kilómetro que
recorre (esto es claramente una condición del problema), con lo
cuál nos conviene que no haga más kilómetros de la cuenta, porque se
comerá más zanahorias y nos quedarán menos para intentar llevarlas al
mercado.
Esto es lo que comentaba anteriormente, a la vez que analizamos el
problema (datos, condiciones…) nos ha surgido una idea clara que debe
formar parte de nuestro plan o estrategia de resolución.
¿Cómo podemos evitar que haga kilómetros innecesarios? Pues haciendo
los viajes, siempre que sea posible, con la mayor carga de zanahorias, es
decir, con 300 zanahorias… en definitiva, aprovechando los viajes que
hagamos al máximo.

Ya tenemos un plan o estrategia a seguir: que el burro realice siempre

que se pueda los viajes cargado inicialmente con 300 zanahorias.
Lo primero que se nos puede ocurrir es recorrer los 300 km de una vez
cargados con 300 zanahorias. Pero al llegar al mercado el burro se habrá
comido las 300 zanahorias (300 km recorridos = 300 zanahorias que se
come el burro) y no le quedará ninguna para poder emprender el viaje de
vuelta para ir a por el resto, quedándose 600 en el punto de partida, y no
habremos conseguido llevar ninguna zanahoria al mercado.

Eso sí, los amigos de lo ajeno nos lo agradecerán…

Habéis observado que lo he representado gráficamente. Sin duda alguna

la representación gráfica como estrategia de resolución de
un problema es de gran ayuda, tanto para comprender mejor las partes
constituyentes del problema como para la propia resolución. Yo siempre
doy este consejo a mis alumnos: «si puedes dibuja«.
Seguimos…

De este primer intento nos queda clara una cosa: no podemos recorrer
los 300 km de una sola vez, así que tendremos que dividir el trayecto
en etapas y acopiar zanahorias en el camino para después volver a por
ellas. Eso sí, escondiéndolas para que los «amigos de lo ajeno» no se las
lleven en lo que tardamos en volver.
¿Y cómo de largas hacemos esas etapas?

Si no queremos volver a quedarnos parados sin poder seguir por falta de

zanahorias, como máximo la etapa podrá ser de 150 km, pues cargado
con 300 zanahorias, tendrá zanahorias suficientes para el viaje de vuelta.
Aunque ya os podéis imaginar lo que va a ocurrir, vamos a ver qué
pasaría con una primera etapa de 150 km…

Realizando los viajes cargado con 300 zanahorias, el burro necesitará dos
viajes de ida y vuelta y uno más de ida (ya no tiene que volver al punto de
partida a por más zanahorias). Es decir, realiza 5 viajes de 150 km,
recorriendo en total 750 km, con lo que se come 750 zanahorias y
consigue llevar al kilómetro 150 una cantidad de 150 zanahorias (las 900
iniciales menos las 750 que se come).
 Ahora, con las 150 zanahorias que nos han quedado, en una segunda y
última etapa de 150 km, llegamos al mercado… ¡sin zanahorias! (150 km
recorridos = 150 zanahorias que se come el burro) … Al menos antes se
aprovechaban de la situación nuestros amigos de lo ajeno, y el burro nos
diría algo así como: «si hay que ir se va, pero ir pá ná es tontería«.

Bueno. Está bastante claro que las etapas en las que tengamos que hacer
algún viaje de ida y vuelta deben ser de menos de 150 km, porque de lo
contrario no estamos consiguiendo nada.
Ya tenemos bastante más acotado nuestro problema.

Pues bien, no se trata de ir probando así sin más con distintas distancias,
se nos puede hacer eterno y además no sabríamos bien cuando acabar.
 Vamos a pensar un poco, que para eso tenemos la cabeza (a parte de
para llevar gorras y sombreros).

Recordad que había dicho que nos interesa hacer los viajes con la carga
máxima de 300 zanahorias, para evitar hacer kilómetros innecesarios, de
hecho esa era nuestra estrategia a seguir. Pues vamos a ver cómo
podemos conseguir esto.
Como ya hemos visto antes, al tener 900 zanahorias en el punto de
partida y poder llevar 300 en cada viaje, sea cual sea la longitud de la
primera etapa, el burro tiene que hacer 5 viajes en total en dicha etapa (3
de ida y 2 de vuelta).

Así que nos interesa que, después de los 5 viajes de la primera

etapa, queden o bien 300 o bien 600 zanahorias, porque así en la
segunda etapa podremos realizar los correspondientes viajes con la carga
máxima.
Para que después de la primera etapa nos queden 300 zanahorias, es
decir, el burro se coma 600 zanahorias, tiene que haber recorrido 600 km
entre los 5 viajes, con lo que la longitud de la primera etapa será de 120
km (resultado de dividir 600 km entre 5 viajes).

Análogamente, para que después de la primera etapa nos queden 600

zanahorias, es decir, el burro se coma 300 zanahorias, tiene que haber
recorrido 300 km entre los 5 viajes, siendo en este caso la longitud de la
primera etapa de 60 km (resultado de dividir 300 km entre 5 viajes).

Se puede intuir ya, viendo lo que nos ha pasado antes, cuál de las dos
opciones es mejor, no obstante, como me gusta hacer siempre, vamos a
verlas las dos.

Si la primera etapa es de 120 km…

 El burro realiza 5 viajes de 120 km, recorriendo en total 600 km, con lo
que se come 600 zanahorias y consigue llevar al kilómetro 120 una
cantidad de 300 zanahorias (las 900 iniciales menos las 600 que se come)
…

… y en una segunda etapa de 180 km, cargado con las 300 zanahorias,
llega al mercado con 120 zanahorias (las 300 que tenía después de la
primera etapa menos las 180 zanahorias que se ha comido en esos 180
km).
No está mal, pero vamos a ver la otra opción que decíamos (ya os podéis
imaginar que ésta es mejor que la anterior).

Si la primera etapa es de 60 km…

Nuestro burro hace 5 viajes de 60 km, recorriendo en total 300 km,

comiéndose por tanto 300 zanahorias y consiguiendo llevar al kilómetro
60 un total de 600 zanahorias (las 900 iniciales menos las 300 que se
come)…
 Después de esta primera etapa, se encuentra como hemos visto en el
kilómetro 60 con 600 zanahorias, y aun hay una distancia de 240 km hasta
el mercado.

Como son 600 zanahorias, va a necesitar más de un viaje para

transportarlas y, además, al haber una distancia al mercado mayor de 150
metros, son necesarias al menos dos etapas más (esto ya lo habíamos
deducido antes).

¿De qué longitud hacemos la segunda etapa?

Pues según lo que ya hemos visto, nos interesa que al terminar dicha
etapa queden 300 zanahorias, para así en una última etapa hacer el viaje
con la carga máxima posible.

En este caso, ya no hay que hacer 5 viajes (3 de ida y 2 de vuelta) como

ocurría en la primera etapa donde teníamos 900 zanahorias, sino que al
tener 600 zanahorias que transportar nos es suficiente con 3 viajes (2 de
ida y 1 de vuelta).
Por tanto, para que después de la segunda etapa nos queden 300
zanahorias, es decir, el burro se coma 300 zanahorias, tiene que haber
recorrido 300 km entre los 3 viajes, con lo que la longitud de la segunda
etapa será de 100 km (resultado de dividir 300 km entre 3 viajes).
Se llega así al kilómetro 160 con 300 zanahorias, que sí podemos cargar
en un solo viaje en una última etapa de 140 km. Como en esos 140 km
el burro se come 140 zanahorias, consigue llegar al mercado con… 160
zanahorias (las 300 del final de la segunda etapa menos las 140 que se
come ahora).