Si ya diste la I1 de Optimización (ICS1113) y saliste con la sensación de que por fin le tomaste el ritmo al Simplex, la I2 te va a mover el piso por una razón muy concreta: los problemas dejan de ser continuos. Cuando una variable solo puede valer 0 o 1, la geometría amable de la programación lineal —vértices, dirección de mejora, óptimo en una esquina— deja de servirte como brújula.

La tesis de esta guía es simple: la I2 se gana modelando, no calculando. En la I1 todavía podías compensar un modelo torcido con buena aritmética; acá no, porque si planteas mal las binarias todo lo que viene después se construye sobre ese error. Esta guía te sirve si ya rendiste la I1 y necesitas ordenar programación entera, branch and bound y modelos de redes antes de la segunda interrogación. No te sirve si todavía te enredas armando restricciones de PL básica: en ese caso parte por la guía de la I1 y vuelve acá después.

La I2 no es “más Simplex”: cambia el tipo de problema

El error de partida es asumir que la segunda interrogación es la primera pero con ejercicios más largos. No lo es. En la mayoría de las secciones, la I2 se concentra en tres bloques: programación entera y mixta, branch and bound y modelos de redes (transporte, asignación y flujo de costo mínimo). Todo lo de la I1 —modelar, dualidad, sensibilidad— sigue vivo, pero como herramienta de trabajo, no como pregunta central.

La diferencia práctica cabe en una frase: en programación lineal continua, la relajación te entrega el óptimo; en programación entera, la relajación te entrega una cota, y el trabajo recién empieza ahí. Si internalizas eso, la mitad de la I2 deja de parecer magia.

Confirma igual el temario con el programa de tu sección: hay semestres en que se agrega una pincelada de optimización no lineal o se le da más peso a los grafos. Pero el núcleo —entera y redes— no se mueve.

Programación entera: cuándo una binaria salva el modelo

Una variable binaria no es “una variable más chica”. Es una decisión de sí o no que te permite meter lógica dentro de un modelo lineal. Cada vez que el enunciado diga “solo si”, “a lo más uno de”, “hay un costo fijo por abrir” o “no se pueden elegir A y B juntos”, estás frente a una binaria.

Los tres casos que más aparecen en la I2:

• Costo fijo: producir cuesta un monto fijo más un costo variable. Necesitas una binaria que se prenda cuando la producción es positiva.
• Selección de proyectos: elegir a lo más k alternativas sujeto a un presupuesto. Es una suma de binarias acotada.
• Localización: abrir bodegas o plantas y asignarles clientes. Mezcla binarias de apertura con variables continuas de flujo.

Un consejo que vale puntos concretos: escribe siempre en palabras qué significa cada variable antes de escribir la primera restricción. Suena obvio, es lo primero que se salta todo el mundo cuando el reloj aprieta, y es exactamente donde el ayudante descuenta al corregir.

Los trucos de modelamiento que sí se preguntan

Hay un puñado de estructuras que se repiten interrogación tras interrogación. Conviene tenerlas memorizadas como plantillas, no deducirlas en el momento:

• Vínculo Big-M: x menor o igual a M por y obliga a que x sea cero cuando la binaria y vale cero. Elige la M más chica que puedas justificar; una M gigante no está mala, pero debilita la relajación y te alarga el branch and bound.
• Implicación: “si eliges A, debes elegir B” se escribe como y de A menor o igual a y de B. Escribirla al revés es un clásico.
• Exclusión mutua: la suma de las dos binarias es a lo más uno.
• Restricciones alternativas: cuando “se cumple una u otra”, necesitas una binaria auxiliar y dos Big-M.
• Producto de binarias: para z igual al producto de y1 por y2 se usan tres desigualdades: z acotada por cada binaria y z mayor o igual a la suma menos uno.

Si te preguntan por qué una formulación es “mejor” que otra teniendo exactamente el mismo conjunto de soluciones enteras, la respuesta casi siempre es la misma: la formulación más ajustada tiene una relajación lineal más cercana al óptimo entero y, por lo tanto, se resuelve explorando menos nodos.

Branch and bound: qué te van a pedir de verdad

Casi nunca te van a pedir resolver a mano un árbol completo de diez variables: no alcanza el tiempo y no mide nada. Lo que sí piden con mucha frecuencia es que completes un árbol parcial. Te dan nodos con el valor de su relajación y tienes que decidir si se podan, por qué, y cuál es la mejor solución conocida hasta ese punto.

Ten claras las tres razones de poda, porque la pregunta suele ser literalmente “¿por qué se poda este nodo?”:

• Por infactibilidad: la relajación del nodo no tiene solución.
• Por integralidad: la relajación entrega una solución que ya es entera, así que se actualiza la incumbente y no hay nada que ramificar.
• Por cota: el valor de la relajación es peor que la mejor solución entera que ya tienes.

Y mucho ojo con el sentido del problema: en maximización la relajación es una cota superior; en minimización, una cota inferior. Invertir eso es el error que más veces convierte un desarrollo correcto en cero puntos.

Redes: transporte, asignación y flujo de costo mínimo

El bloque de redes es, en el fondo, una buena noticia. Son modelos de programación lineal con una estructura tan especial que, si las ofertas y demandas son enteras, el óptimo continuo ya sale entero. Por eso no necesitan branch and bound, y por eso les gusta preguntarlos justo después de entera: quieren ver si notas la diferencia en vez de aplicar el martillo más grande que tengas.

Lo que sí tienes que dominar es reconocer el modelo desde el enunciado. Transporte tiene orígenes con oferta y destinos con demanda, y un costo por unidad enviada. Asignación es un transporte donde todas las ofertas y demandas valen uno, típicamente personas a tareas. Flujo de costo mínimo es el caso general, con nodos intermedios y capacidades en los arcos, y absorbe a los dos anteriores.

La restricción clave, siempre, es la conservación de flujo: en cada nodo, lo que entra menos lo que sale es igual a su oferta neta. Si la escribes bien nodo por nodo, el resto del ejercicio es contabilidad ordenada.

Si quieres practicar con ejercicios resueltos y guiados, en nuestros cursos de preparación de ARomperla trabajamos justamente el paso que más cuesta: pasar del enunciado al modelo.

Qué técnica usar según el enunciado

Esta tabla resume la decisión que tienes que tomar en los primeros treinta segundos de cada ejercicio, antes de escribir una sola variable:

Si además tienes otras interrogaciones encima este semestre, revisa las guías por ramo en el hub de la UC.

Preguntas frecuentes sobre la I2 de ICS1113

¿Necesito manejar el Simplex para rendir bien la I2?

Sí, pero como herramienta. No te van a pedir veinte iteraciones a mano, aunque sí resolver relajaciones y leer resultados. Si el Simplex te toma media hora por ejercicio, ese es tu cuello de botella real antes que la programación entera.

¿Puedo redondear la solución de la relajación y listo?

No, y es una de las preguntas conceptuales favoritas. Redondear puede dejarte en una solución infactible o, siendo factible, lejos del óptimo. Eso es precisamente lo que justifica que exista el branch and bound.

¿Cuántos ejercicios de árbol conviene hacer?

Con cuatro o cinco árboles parciales bien entendidos basta. Es más rentable hacer diez ejercicios de modelamiento que diez árboles: el árbol es mecánico, el modelo no.

¿Se puede usar software en la interrogación?

Depende de la sección y el semestre, así que confírmalo con tu profesor. Aunque lo permitan, la parte de justificar podas, interpretar cotas y explicar por qué una formulación es más ajustada se responde igual a mano.