Ppl de variables binarias

Universidad de Chile Facultad de Ciencias F´ ısicas y Matem´ticas a Departamento de Ingenier´ Industrial ıa

Modelamiento de Problemas de Programaci´n Lineal o con Variables Binarias.
Marcel Goic F.1

IN34A: Clase Auxiliar

Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortograf´ y o ıa errores no forzados. Si encuentran alguno favor de denunciarloa mgoic@cec.uchile.cl

1

IN34A: Optimizaci´n o

Pag. 1

1.

Introducci´n o

En optimizaci´n, frecuentemente aspiraremos a modelar problemas de modo lineal ya que son o emp´ ıricamente mas f´ciles de resolver. Sin embargo, muchos problemas presentan situaciones a en que la linealidad del modelo se hace muy dif´ de sostener con un conjunto de variables ıcil continuas como unicaherramienta de modelaci´n. Es as´ como surgen las variables binarias ´ o ı (aquellas que solo pueden tomar los valores 0 y 1) como un artificio que nos permite expresar situaciones no lineales como lineales. A primera vista puede pensarse que el artificio no sirve de nada porque el definir una variable como binaria ya hace que el modelo se deslinealice y en efecto tienen raz´n. Sin embargo, mas adelante sever´ que esta definici´n de variables es o a o bastante conveniente pues existen algoritmos para resolver este tipo de problemas basandose en las t´cnicas de programaci´n lineal 2 . e o De este modo queda claro que es necesario tener un buen manejo de las variables binarias como una potente herramienta de modelaci´n matem´tica. Si bien es cierto que no se puede o a dar un algoritmo de modelaci´n,al menos podemos exhibir una serie de situaciones frecuentes o en que se ejemplifica su uso. Ese es el objetivo de esta clase.

2.

Situaciones frecuentes que pueden modelarse con variables binarias
Producci´n acotada o

2.1.

Consideremos la producci´n de un producto j (xj ), el cual puede producirse o no, pero que en o caso de producirse solo puede hacerse en un nivel comprendido entre Ljy Uj . Para modelar esta restricci´n, aparte del nivel de producci´n xj , definimos la siguiente variable binaria: o o yj = 1 Si se produce el producto j. 0 Si no se produce el producto j.

Asi, la restricci´n vendr´ dada por o ıa L j · y j ≤ x j ≤ Uj · y j
Si hay alguien muy inquieto puede comenzar a investigar acerca del algoritmo de ramificaci´n y acoo tamiento que se ver´ mas adelante en elcurso. a
2

IN34A: Optimizaci´n o

Pag. 2

2.2.

Producci´n acotada inferiormente o

Consideremos la producci´n de un producto j (xj ), el cual puede producirse o no, pero que o en caso de producirse solo puede hacerse en un nivel de al menos Lj sin que exista una cota superior explicita. La t´ctica anterior no sirve por lo que aparte de la variable yj , inventamos a un nuevo parametroMj que sirva como una cota superior:

yj =

1 Si se produce el producto j. 0 Si no se produce el producto j. Mj = Un n´mero muy grande.3 u

Asi, la restriccion vendr´ dada por ıa Lj · y j ≤ x j ≤ M j · y j

2.3.

Costo Fijo

Consideremos el caso en que debemos decidir si realizar o no una actividad cuyo costo tiene tanto una componente fija como una variable, es decir el costo derealizar la actividad al nivel xj viene dado por: C(xj ) = 0 Si xj = 0. fj + vj xj Si xj > 0.

En este caso, nuevamente nos es de gran utilidad definir una variable binaria: yj = 1 Si se realiza la actividad j. 0 Si no se realiza la actividad j.

As´ la funci´n de costo queda como: ı, o C(xj ) = fj · yj + vj · xj Notar sin embargo que hasta ahora nada impide al modelo adoptar soluciones del tipo yj= 0 y xj = k = 0, situaci´n que evitamos imponiendo la siguiente restricci´n: o o
Que sea una cota emp´ ırica para xj . En la pr´ctica siempre podremos encontrar un n´mero que sea a u razonable pensar que no se sobrepasar´ esa cota. a
3

IN34A: Optimizaci´n o x j ≤ Mj · y j con Mj muy grande

Pag. 3

Observaci´n: Existen otras formulaciones alternativas como por ejemplo C(xj ) = fj · yj...