Funciones con N valores posibles (III)

Para ilustrar cómo puede surgir un caso de este tipo, reconsidérese el problema de la Wyndor Glass Co. que se presentó en la sección 3.1. En la actualidad, el 18% de la capacidad total de la planta no se usa y está disponible para los dos nuevos productos o para ciertos productos futuros que muy pronto estarán listos para producción. Con el fin de dejar cualquier capacidad restante en forma de bloques utilizables para estos productos futuros, la administración desea imponer la restricción de que la capacidad usada por los dos nuevos productos actuales sea el 6% o el 12% o el 18%. Entonces, la tercera restricción del modelo original (3x1 + 2x2 ≤ 18) debe cambiar a

El modelo completo para esta nueva versión del problema consiste, entonces, en el modelo original (véase la sección 3.1), más este nuevo conjunto de restricciones. Esta situación conduce a una formulación de programación entera muy clara.

Funciones con N valores posibles (II)

La formulación equivalente de programación entera para este requerimiento es la siguiente:

con lo que este nuevo conjunto de restricciones sustituye el requerimiento que se hizo al establecer el problema. Este conjunto de restricciones proporciona una formulación equivalente puesto que exactamente una de las yi debe ser igual a 1 y las otras deben ser iguales a cero, así que se está escogiendo justo una di como el valor de la función. En este caso existen N preguntas como con respuesta sí o no, a saber, debe ser di,el valor escogido (i = 1,2......,N). Como la yi respectiva representa estas decisiones si o no, la segunda restricción las hace alternativas mutuamente excluyentes.

Funciones con N valores posibles (I)

Considérese la situación en la que se requiere que una función dada tome cualquiera de N valores dados. Denótese este requisito por

Restricciones de una u otra (IV)

Después, con la misma lógica que para el caso anterior, se encuentra que una formulación equivalente del requerimiento de que K de estas restricciones se deben cumplir es:

en donde M es un número positivo muy grande, Como las restricciones sobre las yi garantizan que K de estas variables serán igual a cero y las restantes serán igual a 1, K de las restricciones originales no cambiarán y el resto, de hecho será eliminado. Con objeto de elegir cuáles K de estas restricciones deben retenerse, se aplica el algoritmo apropiado al problema completo para que encuentre una solución óptima para todas estas variables simultáneamente.

Deben cumplirse K de N restricciones (I)

Considérese la situación en la que el modelo completo incluye un conjunto de N restricciones posibles entre las que sólo  K de ellas se deben cumplir. (Supóngase que K < N). Parte del proceso de optimización es elegir qué combinación de K restricciones permite que la función objetivo adquiera el mejor valor posible. Las (N-K) restricciones que no se eligen, de hecho, quedan eliminadas del problema, aun cuando por coincidencia las soluciones factibles puedan satisfacer algunas de ellas.

Este caso es una generalización directa del anterior para el que K = 1 y N = 2 Denótese las N posibles restricciones por

Restricciones de una u otra (III)

Como sólo una de estas dos preguntas tendrá una respuesta afirmativa, los respectivos términos binarios, y y (1-y), representan las decisiones de sí o no, de manera que y + (1 -y) = 1 (un sí) automáticamente. Si en lugar de esto se usan las variables binarias separadas y1 y y2 para representar estas decisiones de sí o no, entonces se necesita una restricción adicional y1 + y2 = 1, para hacerlas mutuamente excluyentes.

A continuación se da una presentación formal de este enfoque para un caso más general.

Restricciones de una u otra (II)

Como la variable auxiliar y puede ser cero o 1, esta formulación garantiza que una de las restricciones originales se debe cumplir mientras que la otra queda, de hecho, eliminada. Este nuevo conjunto de restricciones se podría añadir a las otras restricciones del modelo completo para obtener un problema de programación entera pura o mixta (según si las xj son variables enteras o continuas).

Este enfoque se relaciona en forma directa con el análisis anterior sobre cómo expresar las relaciones combinatorias en términos de preguntas que se deben responder con sí o no. La relación combinatoria a la que se hace referencia concierne a la combinación de otras restricciones  del modelo con la primera de las dos restricciones alternativas y después con la segunda. Cuál de estas dos combinaciones de restricciones es mejor (en términos del valor de la función objetivo que se puede lograr?) Si esta pregunta se hace en términos de sí o no, en realidad deben hacerse dos preguntas complementarias: