Representación binaria de variables enteras en general (II)

Por ejemplo, supóngase que un problema de PE tiene sólo dos variables enteras generales, x1 y x2 y muchas variables binarias, y que las restricciones funcionales incluyen

Representación binaria de variables enteras en general (I)

Supóngase que se tiene un problema de programación entera pura en el que la mayoría de las variables son binarias, pero la presencia de algunas variables enteras generales evita que se pueda usara el eficiente algoritmo de programación entera binaria que ahora se conoce. Una manera de salvar esta dificultad es usar la representación binaria para cada una de estas variables enteras generales,. En particular, si las cotas de una variable entera x son;

en donde las variables yi son variables binarias (auxiliares). Si se sustituye esta representación binaria por cada variable entera general (con un conjunto diferente de variables binarias auxiliares para cada una), el problema completo se reduce a un modelo de PE.

Problemas de costo fijo (V)

Si las xj también estuvieran restringidas a valores enteros, entonces éste sería un problema de programación entera pura.

Para ilustrar este enfoque, véase de nuevo en la sección 3.4 el problema de la contaminación ambiental que enfrenta la Nori & Leets Co. El primer método de abatimiento que se consideró (aumentar la altura de las chimeneas) en realidad significaría un enorme costo fijo para poder realizar cualquier aumento, además de un costo variable que en esencia sería proporcional al aumento. Después de una conversión al costo anual equivalente utilizado en la formulación, este cargo fijo sería de $2 000 000 por cada uno de los altos hornos y los hornos de hogar abierto, mientras que los costos variables son los mismos que se identificaron en la tabla 3.14. Así, en la notación anterior, k1 = 2, k2 = 2, c1 = 8 y c2 = 10. Como los otros métodos de abatimiento no implican cargos fijos, kj = 0 para j = 3, 4, 5, 6. Por lo tanto la nueva formulación de programación entera mixta de este problema es

Problemas de costo fijo (IV)

Para resumir, la formulación de programación entera mixta del problema de costo fijo es

Problemas de costo fijo (III)

Por tanto, se puede pensar que las yj son decisiones contingentes parecidas (pero no idénticas) a las que se consideraron en la sección 13.1. Sea M un número positivo muy grande que excede el máximo valor factible de cualquiera de las xj (j = 1,2.......,n). Entonces, las restricciones

Problemas de costo fijo (II)

Para formular el modelo completo, supóngase que existen n actividades, cada una con la estructura de costo anterior (con kj ≥ 0 en todos los casos y kj > 0 para alguna j = 1, 2,......n), y que el problema es

o no se representa por una variable binaria uj, de manera que

Problemas de costo fijo (I)

Es bastante común incurrir en un cargo de preparación o costo fijo cuando se emprende una actividad. Por ejemplo, un cargo así ocurre cuando se inicia una corrida de producción para fabricar un lote pequeño de un producto en particular y deben prepararse las instalaciones de producción que se requieren. En tales casos, el costo total de la actividad es la suma de un costo variable relacionado con el nivel de la actividad y el costo fijo en el que se incurre para iniciar la actividad. Con frecuencia, el costo variable será, por lo menos a grandes rasgos, proporcional al nivel de la actividad. Si lo es, el costo total de la actividad (por ejemplo, j) se puede representar por una función de la forma

en donde xj denota el nivel de actividad j (xj ≥ 0), kj denota el costo fijo y cj denota el costo de cada unidad incremental. Si no fuera por el costo fijo kj, esta estructura de costo sugeriría la posibilidad de una formulación de programación líneal para determinar los niveles óptimos de las actividades competitivas. Por fortuna, aun si se incluyen la k, se puede usar programación entera.