VARIABLE BINARIA

Situaciones frecuentes que pueden modelarse con

variables binarias

 Produccion acotada

Consideremos la produccion de un producto j (

caso de producirse solo puede hacerse en un nivel comprendido entre

esta restricci´on, aparte del nivel de producci´on

xj), el cual puede producirse o no, pero que enLj y Uj . Para modelarxj , definimos la siguiente variable binaria:

y

j = 

       1 Si se produce el producto j.

       0 Si no se produce el producto j.

Produccion acotada inferiormente

Consideremos la produccion de un producto j (

en caso de producirse solo puede hacerse en un nivel de al menos

superior explicita. La tactica anterior no sirve por lo que aparte de la variable

un nuevo parametro

xj), el cual puede producirse o no, pero queLj sin que exista una cotayj , inventamosMj que sirva como una cota superior:

y

j =

      1 Si se produce el producto j.

      0 Si no se produce el producto j.

M

j = Un n´umero muy grande.

 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 de realizar la actividad al

nivel

xj viene dado por:

C

(xj) =

0 Si

xj = 0.

f

En este caso, nuevamente nos es de gran utilidad definir una variable binaria:

j + vjxj Si xj > 0.

y

           0 Si no se realiza la actividad j.

Ası, la funcion de costo queda como:

j =     1 Si se realiza la actividad j.

C

(xj) = fj · yj + vj · xj

Notar sin embargo que hasta ahora nada impide al modelo adoptar soluciones del tipo

y

yj = 0xj = k 6= 0, situacion que evitamos imponiendo la siguiente restricci´on:

Observaci´on:

Existen otras formulaciones alternativas como por ejemplo C(xj) = fj · yj +

v

j · xj · yj , pero no son lineales.

Variables que toman un conjunto de valores

Consideremos ahora la situaci´on en que una variable

definidos:

xj solo puede tomar ciertos valores bienxj 2 {a1, a2, ..., an}. En este caso, debemos definir:

y

ij =  1 Si xj = ai

        0 Si

xj 6= ai

x

j solo puede tomar un valor en el conjunto, entonces tenemos la siguiente restricci´on:

X

i

n=1

y

ij = 1 8j

Ademas,

xj vendra dado por:

x

j =

X

i

n=1

a

i · yij

Restricciones excluyentes (una u otra)

Examinaremos esta situacion a traves de un ejemplo: Consideremos que existen 2 restricciones

de las cuales se requiere que solo una de ellas sea satisfecha:

(1) 3

´o

(2) 5

Esta restriccion no esta en formato de programaci´on matem´atica pues en el se asume que deben cumplirse TODAS las restricciones. Sean:

x1 + 2x2 =18x1 + 4x2 =16

y

     0 Si la restricci´on (2) es la que se cumple

=1 Si la restricci´on (1) es la que se cumple

Entonces:

(¯1) 3

(¯2) 5

x1 + 2x2 =18 +M · (1 − y)x1 + 4x2 = 16 +M · y

2.6. Max-Max

Se desea plantear algo del tipo

max

t = max{x1, x2, . . . , xn}

s.a

(x1, x2, . . . , xn) 2 S

La funcion objetivo anterior es intrınsicamente no lineal. Queremos plantear un modelo

lineal:

max

s.a t

t xi 8i.

(

x1, x2, ..., xn) 2 S

Sin embargo, esto no impide que t crezca indefinidamente. Queremos que

t = x1 ´o t = x2

´o ... ´o

t = xn. Esto se implementa con variables binarias:

y

i =

1 Si

t xi

0

Luego, considerando

m´ax

s.a t

M 　 1 el modelo queda:t xi 8i.

P

i

(

t xi +M(1 − yi) 8i. n=1 y1 = 1x1, x2, . . . , xn) 2 S

Quedan propuestos los casos de varias situaciones excluyentes, criterio de min-max y min

|x1−x2|.

Observaci´on:

resolver problemas en los que estan ivolucrados. Es por esto que se deben usar con precauci´on

y discrecion.

Las variables binarias son muy poderosas para modelar, pero no es f´acil

 Problemas

 Problema 1

Una empresa europea piensa instalar plantas de produccion en Chile para lanzar sus productos

al mercado chileno por lo que necesita decidir su plan de producci´on para el proximo

a˜no. La empresa puede fabricar N productos distintos y la elaboraci´on de cada uno de ellos

implica la compra de una m´aquina especializada para su elaboraci´on a un costo de $

Adem´as, el costo variable de producir una unidad del producto n es de $

elaborar el producto n se deber´a necesariamente incurrir en un costo de $

variables por elaboraci´on del producto y si se decide no fabricarlo no se incurrir´a en ning´un

tipo de gasto.

Si la demanda pronosticada para el producto n es de

dicho producto a un precio de $

encontrar el conjunto de productos que la empresa debe fabricar.

fn.cn. As´ı, si se decidefn mas los costosDn unidades (n=1...N) pudiendo vendersepn, formule un PPL mixto que resuelva el problema de

Soluci´on

1. Variables de Decisi´on.

x

n = Unidades de producto n a producir.

y

n =

1 Si se decide producir el producto n.

0

2. Restricciones

a

) Demanda acotada

x

n Dn

b

) Producir solo si se compra la m´aquina

x

3. Funci´on Objetivo

m´ax

n yn ·M M 　 1z =

X

n

N=1

(

pn · xn − fn · yn − cn · xn)

Observaci´on:

necesitamos un

como:

Las 2 restricciones escritas pueden resumirse en una sola notando que noM tan grande y basta con poner M = Dn. As´ı la restricci´on puede escribirse

x

n yn · D

Problema 2

Un estudiante debe rendir examenes en los cursos de Econom´ıa, Estadistica, Electromagnetismo

y Optimizaci´on. Para estudiar estos 4 examenes dispone solamente de 20 horas.

Con el proposito de asignar el tiempo de estudio, a cada curso el estudiante ha fraccionado

su tiempo disponible en bloques de 4 horas cada uno.

La nota que obtendra en un examen determinado dependera de los bloques de tiempo que

asigne al estudio de ese curso. Sea

de tiempo (i=1,2,3,4; j=0,1,2,3,4,5).

Para aprobar Electromagnetismo debe obtener al menos un 4 en el examen y para aprobar

optimizaci´on debe obtener al menos un 3. Los 2 cursos restantes los aprueba con cualquier

nota en el examen.

El problema consiste en encontrar una asignacion de tiempo tal que respetando su disponibilidad

horaria permita aprobar los 4 cursos obteniendo la m´axima suma de nota en los

examenes. Plantee un modelo lineal que represente el problema.

Cij la nota que obtendr´a en el curso i al asignarle j bloques

Soluci´on

1. Variables de Decisi´on.

x

ij =

1 Si dedico j bloques a estudiar el ramo i

0

2. Restricciones

i = 1, ..., 4 j = 0, ..., 5

a

) Obtener al menos un 4 en electromagnetismo.

X

5

j

=0

x

ij · Cij 4 i=Electromagnetismo

b

) Obtener al menos un 3 en optimizaci´on.

X

5

j

=0

x

ij · Cij 3 i=Optimizaci´on

c

) Para cada ramo solo decidir 1 vez cuantos bloques dedicar

X

5

j

=0

x

ij = 1 8i

IN34A: Optimizaci´on Pag.

7

d

) No ocupar mas de 5 bloques en total

X

5

j

=0

X

4

i

=1

j

3. Funcion Objetivo

max

· xij 5z =

X

4

i

=1

X

5

j

=0

x

ij · Cij

Problema 3

Un artista tiene 7 d´ıas para completar 4 obras de arte. Quiere asignar el tiempo disponible

de la forma mas eficiente posible. Necesita por lo menos un d´ıa para cada obra y quiere

dedicar a una sola obra cada d´ıa, puediendo asignar 1, 2, 3 o 4 d´ıas a cada una de ellas.

Como sabe de optimizaci´on, ha decidido realizar estas asignaciones maximizando el total de

sus ingresos. El artista estima que las distintas alternativas en d´ıa de trabajo asignado le

reportar´an ingresos de acuerdo al tiempo dedicado a cada obra. Sea

i si trabaja en ella j d´ıas. Formule un modelo lineal que permita al artista asignar su tiempo.

Cij el ingreso de la obra

Soluci´on

1. Variables de decisi´on.

x

ik =

1 Si el artista trabaja en la obra i en el dia k

0

i = 1, ..., 4 k = 1, ..., 7

y

ij =

1 Si el artista dedica j dias en la obra i

0

2. Restricciones.

i = 1, ..., 4 j = 1, ..., 4

a

) Cada obra necesita de al menos 1 d´ıa de trabajo

X

7

k

=1

x

´O

alternativamente

ik 1 i = 1, ..., 4

X

4

j

=1

y

ij = 1 i = 1, ..., 4

IN34A: Optimizaci´on Pag.

8

b

) Cada d´ıa debe pintarse a lo mas 1 obra

X

4

i

=1

x

ik 1 k = 1, ..., 7

c

) Agregamos una restricci´on que una logicamente xik con yij

X

7

k

=1

x

ik =

X

4

j

=1

j

3. Funci´on Objetivo.

m´ax

· yij i = 1, ..., 4F =

X

4

i

=1

X

4

j

=1

C

ij · yij

 Problema 4

Una determinada empresa forestal puede produce L productos distintos y tiene I plantas

productoras ubicadas en diferentes zonas, siendo

la planta i (i=1,...,I) en el periodo t (t=1,...,5) sin importar de que tipo de producto se trate.

El tipo de producto l tiene un costo de producci´on de

fabrique ni el periodo en cuesti´on. Los productos son demandados por J ciudades diferentes,

siendo

t. Las demandas deben ser satisfechas per´ıodo a per´ıodo.

Como no existe la posibilidad de almacenar producto en las plantas, la empresa esta estudiando

la posibilidad de arrendar bodegas ubicadas en diferentes puntos geogr´aficos. El arriendo

de las bodegas se hace per´ıodo a per´ıodo, esto quiere decir que si se arrienda la bodega k

en el per´ıodo t, no necesariamente la bodega k debe haber estado arrendada en el per´ıodo

t-1 o seguir arrendada para el per´ıodo t+1. Hay K posibles bodegas para arrendar. De esta

manera, la producci´on de las plantas se llevar´a a las bodegas y desde all´ı se abastecer´a a las

ciudades. No existe inventario de productos, las bodegas solo se utilizan para etiquetar los

distintos art´ıculos. Si se arrienda la bodega k (k=1,...,K) se incurre en un gasto fijo de

Sit la capacidad de total de producci´on dePl sin importar la planta en que seDljt la demanda de la ciudad j (j=1,...,n), por el producto l (l=1,..., L), en el periodoFkt

pesos por el pago de arriendo en el periodo t. Ahora bien, si se arrienda una bodega por 3

per´ıodos consecutivos se recibir´a un reembolso de

consecutivos. Por cada unidad del art´ıculo l que ingrese a la bodega k se gasta

concepto de etiquetaci´on. La capacidad de la bodega k es de

importar su tipo.

Adem´as se sabe que cada ciudad debe ser abastecida desde una ´unica bodega en cada per´ıodo

y tambien se sabe que la bodega k puede despachar como m´ınimo al total de ciudades que

abastezca la cantidad de

total de art´ıculos que despacha). Si la bodega despacha mas de

W pesos por cada secuencia de 3 periodosElk pesos porQk unidades de producto sinLk y como m´aximo la cantidad de Uk unidades de art´ıculos (delUk unidades de producto, se le

IN34A: Optimizaci´on Pag.

debe pagar un bono extra a los empleados de esa bodega igual a

de la magnitud del exceso.

El costo de transporte del producto l desde la planta i a la bodega k en el periodo t es de

9Bk pesos, fijo independiente

M

per´ıodo t es de

Plantee un modelo de programaci´on lineal mixto que permita determinar que bodegas deben

arrendarse para que el costo de producci´on, transporte, arriendo y almacenamiento sea m´ınimo.

likt pesos y el costo de transporte desde la bodega k a la ciudad j del producto l en elNlkjt pesos.

Soluci´on

1. Variables de decisi´on.

x

kt =

1 Si se arrienda la bodega k en el periodo t

0

kt =

1 Si arrienda bodega k en periodos t, t+1 y t+2

0

kt =

1 Si se excede el m´aximo

0

Uk en el per´ıodo t

kjt

=

1 Si bodega k abastece a ciudad j en periodo t

0

w

lit = Unidades de producto del tipo l producido en planta i en periodo t

y

likt = Unidades de producto l enviado desde planta i a bodega k en periodo t

z

2. Restricciones.

lkjt = Unidades de producto l enviado desde bodega k a ciudad j en periodo t

a

) Capacidad de Producci´on

X

l

L=1

w

lit Sit

b

) Satisfacci´on de demanda

X

k

K=1

z

lkjt Dljt

IN34A: Optimizaci´on Pag.

10

c

planta

) Conservacin de flujowlit =

X

k

K=1

y

likt

bodega

X

i

I=1

y

likt =

X

j

J=1

z

lkjt

d

) Abastecerse de una sola bodega

z

lkjt Mkjt M 　 1

X

k

K=1

kit

= 1

e

recibir

enviar

) No ocupar bodegas cerradasylikt Mxkt M 　 1zlkjt Mxkt M 　 1

f

) capacidad de bodegas

X

l

L=1

X

i

I=1

y

likt Qk ´o

X

l

L=1

X

j

J=1

z

lkjt Qk

g

) Envio mınimo

X

l

L=1

X

i

I=1

y

likt Lk ´o

X

l

L=1

X

j

J=1

z

lkjt Lk

h

Relaci´on

) L´ogicasxkt con
kt

3

kt

X

t+2

=t

x

Relaci´on

k 2 +
kt t = 1, 2, 3zlkjt con kt

(

uk −

X

l

L=1

X

j

J=1

z

3. Funci´on Objetivo.

m´ın

lkjt) (1 − 2 kt)M M 　 1F =

X

lit

P

lwlit+

X

likt

y

liktElkt+

X

likt

y

liktMlikt+

X

lkjt

z

lkjtNlkjt+

X

kt

x

ktFkt+

X

kt

ktBk−

X

kt

ktW

Problema 5

Douglas Pompkins es un prominente empresario que esta analizando su plan de inversiones

para el pr´oximo ao, para determinar en que proyecto invertir y que ejecutivos contratar

para que administren cada uno de dichos proyectos. Para eso cuenta M posibles proyectos

para desarrollar y con N posibles ejecutivos para administrarlos, debiendo asignar al menos

un ejecutivo por cada proyecto. Sin embargo, no todos los ejecutivos tienen las habilidades

t´ecnicas para administrar todos los proyectos. En efecto, se conocen los par´ametros

toma el valor 1 si el ejecutivo

lo est´a.

Los proyectos a elegir tienen una serie de condiciones t´ecnicas que deben ser cumplidas:

Para cada proyecto

si el proyecto

realizarse ningun proyecto en

el proyecto

Para cada proyecto

el proyecto

todos los proyectos en

aij quei esta capacitado para hacerse cargo del proyecto j y 0 si noj existe un conjunto Ej de proyectos que no pueden ser realizadosj es realizado y viceversa, es decir si se realiza el proyecto j no puedeEj y si se realiza alg´un proyecto en Ej no puede realizarsej.j existe un conjunto Ij de proyectos que deben ser realizados sij es realizado, es decir si se realiza el proyecto j deben realizarse tambienIj y si existe alg´un proyecto en Ij que no se realiza, el proyecto

j

Para cada proyecto

realizaci´on del proyecto

que todos los proyectos en

Para cada proyecto

para la realizaci´on del proyecto

necesario que al menos uno proyecto en

Por ´ultimo existen restricciones de ´ındole financiera. Se sabe que un proyecto

inversi´on de

de inversi´on tal que la rentabilidad esperada sea mayor que

Con los datos anteriores y suponiendo que para cada ejecutivo

´on

inversi´on de modo de minimizar el costo total de contrataci´on de los ejecutivos.

no puede realizarse.j existe un conjunto Rj de proyectos que son requisitos para laj, es decir, para que el proyecto j sea realizado es necesarioRj sean realizados.j existe un conjunto Sj de proyectos que son requisitos alternativosj, es decir, para que el proyecto j sea realizado esSj sean realizados.i requiere unapj y tiene una rentabilidad esperada de uj . Con esto se debe elegir una carteraU y no se invierta mas de P.i existe un sueldo de contratacici, formule un modelo de programaci´on binaria que permita determinar la cartera de

Soluci´on

1. Variables de decisi´on.

y

i =

1 Si contrato al ejecutivo i

0

IN34A: Optimizaci´on Pag.

12

z

j =

1 Si realizo el proyecto j

0

x

ij =

1 Si asigno al ejecutivo i al proyecto j

0

2. Restricciones.

a

) Proyectos que no pueden ser realizados si el proyecto j es realizado.

z

k 1 − zj 8k 2 Ej j = 1...M

b

) Proyectos que deben realizarse si el proyecto j es realizado.

z

k zj 8k 2 Ij j = 1...M

c

) Proyectos que deben realizarse todos para poder realizar el proyecto j .

X

k

2Rk

z

k zj · |Rj | j = 1...M

d

) Proyectos que alguno debe realizarse para poder realizar el proyecto j.

X

k

2Sj

z

k zj j = 1...M

e

) Cota inferior a la utilidad esperada de la cartera de inversi´on.

X

j

M=1

u

j · zj U

f

) Cota superior al dinero invertido en los proyectos.

X

j

M=1

p

j · zj P

g

) Asignar al menos a un ejecutivo competente a los proyectos realizados.

X

i

N=1

a

ij · xij zj j = 1...M

h

) No asignar a un ejecutivo que no he contratado.

x

ij yi i = 1...N, j = 1...M

IN34A: Optimizaci´on Pag.

13

i

) Naturaleza de las variables.

y

i, zj , xij 2 {0, 1} i = 1...N, j = 1...M

3. Funci´on Objetivo.

m´ın

CTC =

X

i

N=1

c

i · yi