UNIVERSIDAD NACIONAL DE INGENIERÍA

Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Problemas de programación lineal entera

Un problema de optimización o programación lineal entera es aquel que tiene la

siguiente formulación

Optimizar f  x   c1 x1  c2 x2  ...  cn xn
sujeto a
ai1 x1  ai 2 x2  ...  ain xn       bi i  1,...,m  PLE 
x j  0, x j  Z 

En formato matricial este problema se escribe

Optimizar cT x
sujeto a Ax       b
x  Z n

La figura muestra la región factible de un problema de programación lineal entera con dos
variables de decisión.

Para obtener esta región se dibuja la región definida por

Ax     b

Página 1 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

pero sin tener en cuenta la condición integrabilidad de las variables una vez hecho esto en
dicha región consideramos los puntos donde ambas coordenadas son enteras no
negativas.

Nótese que los puntos de coordenadas enteras no tienen por qué ser finito, cuando la región
es no acotada tenemos un número infinito de puntos con coordenadas enteras.

Aquellos problemas de Optimizacion cuya región admisible está formada por un número
finito de puntos se les llaman Problemas de Optimizacion combinatorios

Los problemas de programación lineal entera se emplean para modelar situaciones, en

los que aparecen “indivisibilidades”.

Todo problema de programación lineal entera tiene asociado un problema de

programación lineal continuo el cual es llamado problema lineal relajado asociado que
se obtiene eliminado las condiciones de integrabilidad de las variables de decisión.

En este caso esta relajación seria:

Optimizar cT x
sujeto a Ax       b
x0
En una primera aproximación lo natural sería pensar que bastaría resolver el problema
relajado asociado y una vez obtenida la solución óptima de éste redondear hacia los
enteros más próximos. El inconveniente que se puede presentar es doble: por un lado que
esta solución no sea factible (no verifique una o varias restricciones) y caso lo sea nada
garantiza que el punto seleccionado, con todas las coordenadas enteras, sea mejor que
todos los puntos enteros factibles restantes.

maximizar z  700 x1  1000 x2

sujeto a 7 x1  13 x2  91
140 x1  80 x2  1190
x1 , x2  Z 

Se puede probar que la solución óptima para el problema relajado asociado es

x1  6,5, x2  3,5.

Página 2 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Obsérvese, como ya se dijo anteriormente, que si bien esta solución es óptima no es

admisible para el problema original ya que no es entera Si se redondea esta solución
hacia el entero más próximo, las cuatro posibles soluciones serían:

x1  6 x2  4
x1  7 x2  4
x1  6 x2  3
x1  7 x2  3

y según puede verificarse la única solución factible, de entre las cuatro anteriores, es

x1  6 x2  3

a la que corresponden un valor óptimo de 7,200

Sin embargo, cuando este problema es resuelto con técnicas propias para este tipo de
problemas se llega a que la solución óptima es:

x1  5 x2  4

A la que corresponde un valor óptimo de 7,500. Esto muestra que esta idea de redondear
puede no ser buena.

El problema de Optimizacion

Optimizar f  x   c1 x1  c2 x2  ...  cn xn
sujeto a
ai1 x1  ai 2 x2  ...  ain xn       bi i  1,...,m  PLEM 
x j  Z  j  J  1;2;...;n , xi  0, i  1;2;...;n  J

Cuando J es subconjunto propio de 1, 2,..., n , se denomina “programación lineal

entera mixta” En este caso se exige a algunas variables de decisión tomar valores
enteros.

Un hecho debe matizarse y es que en realidad los problemas de programación lineal

entera pura o mixta son problemas no lineales ya que tanto la función objetivo del
problema como las funciones que determinan las restricciones únicamente se encuentran
definidas para valores enteros de las variables de decisión.
Página 3 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Ahora bien, en términos generales y como posteriormente se precisará, se entiende por

problema de programación lineal entera pura o mixta a todo aquel problema de
Optimizacion en el que una vez suprimida la restricción correspondiente a que alguna o
todas las variables de decisión tengan que tomar valores enteros, el problema resultante
sea un problema de programación lineal continuo

Problemas de Optimizacion 0-1 o binarios

El problema

Optimizar f  x   c1 x1  c2 x2  ...  cn xn
sujeto a
ai1 x1  ai 2 x2  ...  ain xn       bi i  1,...,m  PB 
x j  0;1 , i  1; ;n
Es llamado problema de optimización con variables enteras binarias o simplemente
problemas binarios.

Ejemplo (Restricción sobre los valores de la solución)

Supongamos que una variable z j sólo puede tomar un valor de una lista de valores
dados, por ejemplo v1; v2 ;; vn . ¿Cómo se puede representar matemáticamente esta
situación?

Esto se puede representar como

 z j  v1 x1  v2 x2  ...  vn xn ,

 x1  x2  ...  xn  1,
 x  0; 1 , j  1,..., n.
 j  
La introducción de estas variables binarias también permite tratar restricciones de tipo
disyuntivo en las que debe satisfacerse al menos una de entre varias restricciones

Página 4 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Ejemplo (Problema de la mochila)

Una persona tiene a su disposición un número de objetos de n tipos, E1 ,..., En , con un
valor unitario c j y volumen unitario a j . Desea elegir el conjunto de objetos de forma que
no se sobrepase un determinado espacio que tiene a su disposición de volumen b.

Solución.
Sea xj la variable de decisión que indica el número de objetos de tipo E j que se
n
eligen. El objetivo será maximizar la función c x
j 1
j j

Las restricciones vendrán impuestas como consecuencia de la limitación del espacio

disponible. Es decir,
n

a x
j 1
j j b

Además las restricciones obvias,

x j  Z  j  1,..., n

El problema de Optimizacion es entonces,

n
maximizar z  cjxj
j 1
n
sujeto a a x
j 1
j j b

x j  Z  , j  1,..., n

Ciertos problemas de “asignación” donde por ejemplo, xij  1 si el trabajador i es asignado

al trabajo j y xij  0 en caso no lo sea, admiten una modelación como problemas binarios

Página 5 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Ejemplo (Problema de asignación)

Considere una empresa en la cual hay m grupos de trabajadores que pueden ser
asignados a n diferentes trabajos. Por alguna razón –quizás por diferentes niveles de
habilidad u otros factores- asignar un trabajador de un grupo determinado, para que
realice un determinado trabajo, tiene un costo para la empresa que depende de cuál es el
grupo al cual pertenece el trabajador

Se entiende que trabajadores de un mismo grupo tienen igual costos de asignación. Los
datos para el problema son:

a) ai cantidad de trabajadores en el grupo i , para i  1,...,m.

b) b j trabajadores requeridos en el trabajo tipo j , para j  1,...,n.
c) cij costo de asignar a un trabajador del grupo i para que realice el trabajo j , para
i  1,...,m, j  1,...,n.

Formule este problema de asignación como uno de optimización lineal de modo que se
minimice el costo de asignación de trabajadores a las distintas tareas.

Solución
Las variables de decisión son:

xij número de trabajadores del grupo i asignados al trabajo j , para

i  1,...,m, j  1,...,n.
m n
La función objetivo es igual a  c x
i 1 j 1
ij ij que representa el costo total en el que se

incurre al asignar a los trabajadores a los distintos trabajos

m n
minimizar z =  cij xij
i 1 j 1

 n
  xij  ai ,i  1,...,m
 j 1
m
sujeto a   xij  b j , j  1,...,n
 i 1
 xij  0 i  1,...,m, j  1,...,n



Página 6 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Las restricciones involucrando a ai nos dice que los trabajadores asignados de cada
grupo no puede ser más grande que el tamaño del grupo. Las restricciones involucrando a
b j nos dice que los trabajadores asignados a cada trabajo de ser por lo menos el número
necesario en ese trabajo.

Observación

a) La formulación del problema de asignación no contiene el requerimiento explícito

de que las variables xij deben ser enteras, es decir, porque no se tiene la siguiente
formulación
m n
minimizar z =  cij xij
i 1 j 1

 n
  xij  ai ,i  1,...,m
 j 1
m
sujeto a   xij  b j , j  1,...,n
 i 1
 xij  Z  , i  1,...,m, j  1,...,n



Podría ser el caso que niveles fraccionarios de trabajadores sean asignados a los
diversos tipos de trabajo. Sin embargo, si los valores ai y b j son todos enteros,
entonces, se puede probar (este es un resultado teórico) que existe una solución
óptima en la cual todas las variables xij son enteras. Esta es en realidad una
propiedad de los problemas de programación lineal que modelan problemas de
asignación.

b) Esta propiedad de integrabilidad hace posible algunas aplicaciones interesantes.

Supongamos que hay exactamente m personas a ser aginados a n  m trabajos,
exactamente una persona a cada trabajo.
En esta situación, cada «grupo» consiste de una persona, es decir, ai  1 para
todo i  1,...,m.

Página 7 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

También, solo una persona es requerida para cada tipo de trabajo, esto implica que
bj  1 para todo j  1,...,m.

Para tener una función objetivo, supongamos que cada persona especifica su
preferencia por cada tipo de trabajo
Sea

cij la preferencia de la persona i por el trabajo j , sobre una escala de 1(inferior) a

10 (alta) para i  1,...,m, j  1,...,n. .

Luego, el objetivo es encontrar la asignación que tiene la preferencia total más alta
entre todas las personas a ser asignadas.

Definamos las siguientes variables de decisión, para todo i  1,...,m, j  1,...,n.

.
xij  1 Si persona i es asignada al trabajo j
xij  0 persona i no es asignada al trabajo j

Desde que una persona es asignada a solo un trabajo, la solución tendrá xiq  1
para un trabajo particular q , y tendrá xij  0 para todo j  q .
m
Entonces, c x
j 1
ij ij será simplemente igual a ciq el cual es la preferencia de la

persona i por el trabajo al cual él es asignado.

La preferencia total, se obtiene sumando

m m

 c x
i 1 j 1
ij ij

igual que en el problema de asignación anterior e igual que en el problema del

transporte.
Desde que valores altos en esta suma representan preferencias más altas por un
tipo de trabajo.

La función objetivo será

m m
maximizar  cij xij
i 1 j 1

Página 8 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Si por alguna razón se desea minimizar solo hay que decirles a las personas que
la preferencia más alta es 1 y la más baja 10.
El análisis hecho sugiere un problema de optimización lineal del tipo
m m
maximizar  cij xij
i 1 j 1

m
  xij  1, i  1,...,m
 j 1
m
sujeto a   xij  1, j  1,...,m
 i 1
 xij  0;1 , i  1,...,m; j  1,...,m



Nuevamente nos formulamos la pregunta:¿Por qué la formulación no es solamente

la siguiente?

m m
maximizar  cij xij
i 1 j 1

 m

  xij  1, i  1,...,m
 j 1
m
sujeto a   xij  1, j  1,...,m
 i 1
 xij  Z  , i  1,...,m; j  1,...,m



Esto es posible ya que desde que todo ai  1 y b j  1, la solución óptima debe ser
entera. Porque para una persona particular p ¿Cómo pueden los valores enteros no
negativos de x pj , j  1,...,m sumar uno como es requerido por las restricciones?

Página 9 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Ejemplo (Problema del coste fijo)

Un determinado producto se puede fabricar en n máquinas. Cada máquina M j  j  1,..., n 

tiene un coste fijo K j siempre que esa máquina se utilice en la fabricación de una
cantidad x j > 0 del producto dado. Además, cada máquina tiene un coste variable de c j
unidades monetarias por cada unidad producida. La producción de la máquina j-ésima, en
el período de tiempo considerado, está limitada por b j . Se trata de determinar la cantidad
x j producida por cada máquina para satisfacer la demanda D de dicho producto en el
período de tiempo considerado, con coste mínimo.

Solución.
La función de coste asociada a la máquina j-ésima, será

0 si x j  0
cxj   
 K j  c j x j si x j > 0

donde x j es la cantidad producida por la máquina j-ésima. La función a minimizar será

cx 
n

j y esta función no es lineal en x j debido a la discontinuidad que presenta en el

j 1

origen.

Con el objeto de plantear el problema anterior en términos de un problema de PLE. se

introducen las variables y1 ,, yn , con

0 si x j  0
yj  
1 si x j > 0

y el problema se puede formular en los siguientes términos

n n
minimizar cjxj   K j y j
j 1 j 1
n
sujeto a x
j 1
j D

0  x j  bj y j j  1,..., n
x j  Z , y j  0,1

Página 10 de 11
 UNIVERSIDAD NACIONAL DE INGENIERÍA
Facultad de Ingeniería Económica, Estadística y CC.SS

Escuela Profesional de Ingeniería Estadística

Optimizacion
Profesor Carlos Vargas [email protected]

Obsérvese que si x j > 0, entonces y j  1 y el costo fijo K j se añade a la función objetivo.

Por otro lado, si x j  0, y j  0 y no se añade tal coste a la función objetivo

Ejemplo (Problema de localización de plantas con capacidades)

En el Problema de Localización de Plantas con Capacidades, se pueden instalar

plantas de servicio en m puntos posibles con costes fi , i  1,..., m, respectivamente, para
satisfacer las demandas de n clientes. Cada planta tiene una capacidad de producción
máxima de qi unidades y cada cliente necesita que le sean servidas d j unidades,
j  1,..., n. Además, el coste de servir una unidad de producto desde la planta i al cliente j
es de cij unidades monetarias.
Solución.
Definiendo las variables de decisión
xij  número de unidades que se envían de la planta i al cliente j

1 si la planta i se instala,
yi  
0 en caso contrario,

el problema puede ser formulado de la siguiente forma:

 minimizar  f i yi   j 1 cij xij

m n

 i 1

sujeto a

m
xij  d j, j  1,..., n,
 i 1


n
 j 1
xij  qi yi , i  1,..., m,

 yi  0,1 , i  1,..., m,
 
 xij  Z , i  1,..., m, j  1,..., n.


Página 11 de 11