sadasdsa

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

IN34A: Clase Auxiliar

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

1

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 favorde denunciarlo a mgoic@cec.uchile.cl

IN34A: Optimizaci´n
o

1.

Pag. 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
continuascomo unica herramienta 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. Sinembargo, mas adelante se ver´ 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
oa
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.

2.1.

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

Consideremos la producci´n de un producto j (xj ), el cual puede producirse o no, pero que en
o
caso de producirse solopuede hacerse en un nivel comprendido entre Lj y 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
2

Si hay alguien muy inquieto puede comenzar a investigar acerca del algoritmo deramificaci´n y acoo
tamiento que se ver´ mas adelante en el curso.
a

IN34A: Optimizaci´n
o

2.2.

Pag. 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 porlo que aparte de la variable yj , inventamos
a
un nuevo parametro Mj que sirva como una cota superior:

1 Si se produce el producto j.
0 Si no se produce el producto j.

yj =

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 tienetanto una componente fija como una variable, es decir el costo de realizar 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 · xjNotar 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
3

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

IN34A: Optimizaci´n
o

Pag. 3
x j ≤ Mj · y j

con...