datos

Para formular el modelo completo, suponga 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 5 1, 2, . . . , n—,
y que elproblema es
Minimizar Z
f1(x1)  f2(x2)  . . .  fn(xn),
sujeta a
las restricciones de programación lineal dadas.
Para convertir este problema al formato de programación entera mixta, secomienza por proponer
las preguntas que deban responderse con sí o no; por ejemplo, para cada j 5 1, 2, . . . , n, ¿debe
emprenderse la actividad j (xj . 0)? Después, cada una de estas decisiones sí o nose representa por
una variable binaria yj, de manera que
Z
n
j
1
(cjxj  kjyj),
donde
yj

si xj  0
si xj
0.
1
0
Por tanto, se puede pensar que las yj son decisiones contingentesparecidas (pero no idénticas) a
las que se consideran en la sección 11.1. Si M es un número positivo muy grande que excede el
máximo valor factible de cualquiera de las xj (j 5 1, 2, . . . , n), lasrestricciones
xj  Myj para j
1, 2, . . . , n
asegurarán que yj 5 1 y no cero, siempre que xj . 0. La única difi cultad que queda por salvar es
que estas restricciones dejan a las yj en libertad detomar el valor 0 o 1 cuando xj 5 0. Por fortuna,
esto también se resuelve en forma automática por la naturaleza de la función objetivo. El caso en
el que kj 5 0 se puede ignorar puesto que yj sepuede eliminar de la formulación. Entonces, sólo
se toma en cuenta el otro caso, es decir, cuando kj . 0. Si xj 5 0, de manera que las restricciones
permiten elegir entre yj 5 0 y yj 5 1, yj 5 0 debeconducir a un valor menor de Z que yj 5 1. De
esta forma, como el objetivo es minimizar Z, un algoritmo que conduzca a una solución óptima
siempre elegirá yj 5 0 si xj 5 0.
Para resumir, laformulación de PEM del problema de costo fi jo es
Minimizar Z
n
j
1
(cjxj  kjyj),
sujeta
las restricciones originales, más
xj 2 Myj # 0
y
yj es binaria, para j 5 1, 2, . . . , n.
Si las xj...