APLICACIÓN DE LAS VARIABLES BINARIAS

Las variables binarias, o 0 – 1, desempeñan un papel especialmente importante en las aplicaciones de la PLE. Estas variables permiten incluir decisiones “si o no”, conocidas a veces como decisiones de dicotomía, en un formato de optimización. Dos ejemplos rápidos ilustraran esta idea:

1. En un modelo para decidir la ubicación de una planta, sea Xj =1 la opción de construir la planta en la localidad j,y,x_j=0 la opción de no hacerlo.


2. En un modelo de rutas, sea x_ijk=1 el resultado que corresponde a la opción de que el camión k vaya de la ciudad i a la cuidad j,y sea x_ijk=0 el correspondiente a la opción de que no recorra esa ruta.

En estos ejemplos podrá observar que el empleo de variables 0-1 nos proporciona una nueva herramienta de formulación. En esta sección veremos algunos ejemplos de la forma en que se usan variables 0-1 para tomar decisiones de dicotomía en diferentes aplicaciones. Veremos también la forma de manipular las variables de esa índole para representar condiciones lógicas de diversos tipos.

CONDICIONES LOGICAS
Una aplicación importante de las variables 0-1 consiste en imponer restricciones que surgen de condiciones lógicas. Mencionamos a continuación varios ejemplos:

• No más de k de n alternativas supongamos que x_i=0 o 1, para i=1,….,n. La restricción x_1+x_(2 )+ …+ x_n ≤k implica que podemos seleccionar como máximo k alternativas entre n posibilidades. Es decir, como cada x_i sol puede ser 0 o 1, la restricción anterior implica que no más de k de ellas puede ser igual a 1. Considerando los datos presentados en la tabla anterior, suponga que PROTRAC ha estimado que no le será posible aceptar más de un proyecto en el extranjero. Por este motivo, la junta directiva quiere suprimir la alternativa que incluye tanto la expansión en Bélgica como la nueva planta en Chile. Añadir la restricción x_1+ x_3 ≤1 al modelo de PLE implica que la solución puede contener como máximo una de las opciones en el extranjero.

DECISIONES DEPENDIENTES
Podemos usar variables 0-1 para hacer que una relación dependa de dos o más decisiones. Supongamos, que la gerencia de PROTRAC no quiere seleccionar la alternativa k, a menos que haya elegido primero la alternativa m. La restricción x_k≤x_m asegura el cumplimiento de esta condición. Observe que si no se ha seleccionad previamente m, entonces x_m=0.
En consecuencia, la condición x_k≤x_m hace obligatorio que x_k sea 0 (es decir, que no se selecciona la alternativa k). En forma alternativa, si se selecciona m,x_m=1, entonces x_k≤x_m se convierte en x_k≤1. Con esto, el programa queda en libertad para seleccionar x_k=1 o bien x_k=0.

RESTRICCIONES AL TAMAÑO DEL LOTE
Considere al administrador de una cartera de inversiones que debe trabajar bajo las siguientes restricciones:

1. Si compra valores j, se debe adquirir por lo menos 200 acciones


2. No puede comprar más de 1000 de los valores j.

Sea x_j el número de acciones compradas del valor j. La restricción de que si se compra j, tendrán que ser compradas por lo menos 200 acciones, si se conoce como una restricción al “tamaño mínimo del lote” o al “tamaño de la partida”. Observe que ese tipo de restricción no puede introducirse en un modelo de PL. Las restricciones 200≤ x_j≤1000no producen ese efecto por que se exigen que x_j siempre sea 200 por lo menos. Deseamos que la condición sea o bien x_j=0 o 200 ≤x_j≤1000. Para lograrlo usaremos una variable 0-1, digamos y_j para el valor j. La variable y_jtiene la siguiente interpretación:

• Si y_j=1, entonces compre el valor j.


• Si y_j=0, no compre el valor j.

Consideramos ahora las dos restricciones x_j≤1000 y_j ; x_j ≥200 y_j
Veremos que si y_j=1, entonces x_j≤1000 y_j y x_j ≥200 y_j implica que 200 ≤x_j≤1000.
Por otra parte, si y_j=0, entonces x_j≤1000 y_j implica que x_j≥0.

En forma similar, x_j ≥200 y_j implica que〖 x〗_j ≥0. Estas dos desigualdades, tomadas en conjunto, implica que x_j=0. Así, si y_j=1 cuando compramos j, y 0 cuando no lo hacemos, ya hemos impuesto las condiciones apropiadas sobre 〖 x〗_j.

¿Cómo podemos estar seguros de que y_j=1 si compramos el valor j?

La desigualdad x_j≤1000 y_j lo garantiza.
Observamos que en esta desigualdad no es posible tener el mismo tiempo x_j>0 y y_j=0. Por consiguiente, si x_j>0, y_j debe ser igual a 1. De esta manera, vemos que las desigualdades〖 x〗_j≤1000 y_j y x_j ≥200 y_j juntas garantizan la restricción sobre el “tamaño mínimo del lote”.

k de m RESTRICCIONES
Mischa Gaas, un estudiante de intercambio que viene del Oriente Medio, llego a la universidad para realizar estudios de posgrado. Su asesor le informo que todas las personas que desean obtener un doctorado en historia deben satisfacer por lo menos dos de los siguientes criterios: “Tendrás que ser soltero, rico o loco”. Por desgracia, Mischa era pobre y estaba casado. De hecho, antes de casarse dedico largos años a buscar una novia que fuera alta, morena, bella y rica. Finalmente, lleno de frustración, dijo en su fuero interno: “Tres virtudes de cuatro no es un mal resultado”; y la mujer que eligió (o la que lo eligió a el) no era rica. Estos son algunos ejemplos de modelos en los cuales es necesario satisfacer k de m restricciones. En notación general, representemos en la siguiente forma el “superconjunto” de m restricciones
g_i (x_1,…,x_n )≤b_i, i=1,…,m
Introduzcamos ahora m nuevas variables del tipo 0-1 y_i y escojamos un número muy grande como valor de U, tan grande que para i,g_i (x_(i,…,) x_n )≤U para toda x que satisfaga cualquier conjunto de k desigualdades tomadas de entre las m anteriormente mencionadas. En ese caso, las siguientes m+1 restricciones expresan la condición deseada:
∑_(i=1)^m▒〖y_1=〗 k
g_i (x_1,…,x_n )≤b_i y_i+ (1-y_i )U, i=1,…,m
Observe que ∑_(i=1)^m▒〖y_i=k〗 obliga a k de las y_1 variables a tener el valor 1. Esto significa que exactamente k de las desigualdades anteriores son equivalentes a g_i (x_1,…,x_n )≤ b_i
Las demás desigualdades son equivalentes a g_i (x_1,…,x_n )≤ U y por la suposición de que se ha elegido un número muy grande para U, cada una de esas restricciones es redundante.