Programación Lineal Entera Binaria
Programación Lineal Entera Binaria
Programación Lineal Entera Binaria
Estudiamos el problema de Programación Lineal en números enteros en el que las variables solo puedan tomar los valores «0» y «1».
Programación Lineal Entera Binaria
Programación Lineal Entera Binaria
Estudiamos el problema de Programación Lineal en números enteros en el que las variables solo puedan tomar los valores «0» y «1».
Su resolución no se hará mediante algoritmos sino mediante las funciones Maximize[ ]/Minimize[ ] ó Nmaximize[ ]/Nminimize[ ].
Programación Lineal Entera Binaria
Programación Lineal Entera Binaria
Estudiamos el problema de Programación Lineal en números enteros en el que las variables solo puedan tomar los valores «0» y «1».
Su resolución no se hará mediante algoritmos sino mediante las funciones Maximize[ ]/Minimize[ ] ó Nmaximize[ ]/Nminimize[ ].
Como ejemplo damos el Problema de la Mochila de interesantes aplicaciones a la Economía.
Programación Lineal Entera Binaria
Introducción
Consideremos el problema:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
en el que todas o algunas variables tomen valores enteros.
Programación Lineal Entera Binaria
Introducción
Consideremos el problema:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
en el que todas o algunas variables tomen valores enteros.
Si las variables de decisión solo pueden tomar los valores 0 ó 1, entonces se llamarán binarias y el problema
será de P.L. Entera Binaria:
Programación Lineal Entera Binaria
Introducción
Consideremos el problema:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
en el que todas o algunas variables tomen valores enteros.
Si las variables de decisión solo pueden tomar los valores 0 ó 1, entonces se llamarán binarias y el problema
será de P.L. Entera Binaria:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
xj = 0 ó 1
Programación Lineal Entera Binaria
Ejemplo:
Una empresa está estudiando la posibilidad de expansión mediante la construcción de una nueva fábrica ya
sea en Ciudad 1 ó en Ciudad 2 ó en ambas ciudades. Si construye una fábrica en la Ciudad x, se puede
construir un almacén en dicha Ciudad, pero solo se construiría uno.
La siguiente tabla muestra el beneficio aportado por la inversión y los costes. El capital total disponible es de
10 um.
Se pide encontrar la solución que maximiza el beneficio total.
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1
9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
En este ejemplo, al ser sencillo, podemos estudiar exhaustivamente todas las combinaciones posibles (n=número de variables, en nuestro caso = 16 casos posibles) y elegir la que sea más conveniente:
Programación Lineal Entera Binaria
Casos Fábrica1
Fábrica 2
Almacén 1
Almacén 2
1 S S S S
2 S S S N
3 S S N S
4 S N S S
5 N S S S
6 S S N N
7 S N S N
8 N S S N
9 S N N S
10 N S N S
11 N N S S
12 S N N N
13 N S N N
14 N N S N
15 N N N S
16 N N N N
Programación Lineal Entera Binaria
Casos Fábrica1
Fábrica 2
Almacén 1
Almacén 2
Bene-ficio
Coste ¿Admisi-ble?
1 S S S S
2 S S S N 20 14 NO
3 S S N S 18 11 NO
4 S N S S
5 N S S S
6 S S N N 14 9 SI
7 S N S N 15 11 NO
8 N S S N
9 S N N S
10 N S N S 9 5 SI
11 N N S S
12 S N N N 9 6 SI
13 N S N N 5 3 SI
14 N N S N
15 N N N S
16 N N N N 0 0 SI
Programación Lineal Entera Binaria
Casos Fábrica1
Fábrica 2
Almacén 1
Almacén 2
Bene-ficio
Coste ¿Admisi-ble?
1 S S S S
2 S S S N 20 14 NO
3 S S N S 18 11 NO
4 S N S S
5 N S S S
6 S S N N 14 9 SI
7 S N S N 15 11 NO
8 N S S N
9 S N N S
10 N S N S 9 5 SI
11 N N S S
12 S N N N 9 6 SI
13 N S N N 5 3 SI
14 N N S N
15 N N N S
16 N N N N 0 0 SI
Programación Lineal Entera Binaria
Casos Fábrica1
Fábrica 2
Almacén 1
Almacén 2
Bene-ficio
Coste ¿Admisi-ble?
1 S S S S
2 S S S N 20 14 NO
3 S S N S 18 11 NO
4 S N S S
5 N S S S
6 S S N N 14 9 SI
7 S N S N 15 11 NO
8 N S S N
9 S N N S
10 N S N S 9 5 SI
11 N N S S
12 S N N N 9 6 SI
13 N S N N 5 3 SI
14 N N S N
15 N N N S
16 N N N N 0 0 SI
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1
9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
- Restricciones:
- Limitaciones de capital: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
- Restricciones:
- Limitaciones de capital: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1
9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
- Restricciones:
- Limitaciones de capital: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10
- Solo se construye un almacén: x3 + x4 ≤ 1
Programación Lineal Entera Binaria
Este problema puede ponerse en P.L. Entera:
- Variables de decisión: x1,x2,x3,x4:
x1=construir fábrica en ciudad 1, x2=construir fábrica en ciudad 2
x3=construir almacén en ciudad 1, x4=construir almacén en ciudad 2
Son variables binarias (0 ó 1) según que la decisión sea afirmativa (xi=1) ó negativa (xi=0)
- Función objetivo: Maximizar 9x1 + 5x2 + 6x3 + 4x4
- Restricciones:
- Limitaciones de capital: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10
- Solo se construye un almacén: x3 + x4 ≤ 1
- Se construye el almacén solo si se construye la fábrica :
x3 ≤ x1 , x4 ≤ x2
Programación Lineal Entera Binaria
Luego el modelo es:
Maximizar 9x1 + 5x2 + 6x3 + 4x4
Sujeta a: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 x3 + x4 ≤ 1
x3 ≤ x1 x4 ≤ x2
Programación Lineal Entera Binaria
Luego el modelo es:
Maximizar 9x1 + 5x2 + 6x3 + 4x4
Sujeta a: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 x3 + x4 ≤ 1
x3 ≤ x1 x4 ≤ x2
Hemos de añadir las siguientes restricciones:Las variables son enteras:
x1, x2, x3, x4 Z
Programación Lineal Entera Binaria
Luego el modelo es:
Maximizar 9x1 + 5x2 + 6x3 + 4x4
Sujeta a: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 x3 + x4 ≤ 1
x3 ≤ x1 x4 ≤ x2
Hemos de añadir las siguientes restricciones:Las variables son enteras:
x1, x2, x3, x4 ZLas variables solo pueden tomar loa valores 0 ó 1:
x1, x2, x3, x4 [0,1]
Programación Lineal Entera Binaria
Lo resolvemos con Mathematica:
Que nos indica que el beneficio se maximiza construyendo solo las fábricas 1 y 2 y ningún almacén.
Hemos obtenido el mismo resultado que por el método extensivo.
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1
9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
9 2
Cambiemos ahora algunos datos:
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1
9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
9 2
Cambiemos ahora algunos datos:
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 4 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 4 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 2
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2
5 3
3 Almacén Ciudad 1
6 2
4 Almacén Ciudad 2
4 2
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2 5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
El capital total disponible es de 10 um.
El capital total disponible es de 11 um
Programación Lineal Entera Binaria
Decisión ¿Si/No? Beneficio Coste
1 Fábrica Ciudad 1 9 6
2 Fábrica Ciudad 2 5 3
3 Almacén Ciudad 1
6 5
4 Almacén Ciudad 2
4 2
El capital total disponible es de 10 um.
El capital total disponible es de 11 um
Programación Lineal Entera Binaria
En el siguiente mini-video veremos El Problema de la Mochila
Mini-video 2 de 2
Programación Lineal Entera Binaria
Programación Lineal Entera Binaria
Introducción
Consideremos el problema:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
en el que todas o algunas variables tomen valores enteros.
Si las variables de decisión solo pueden tomar los valores 0 ó 1, entonces se llamarán binarias y el problema
será de P.L. Entera Binaria:
Maximizar F(x) = ct
x
Sujeta a: A x ≤ b
x ≥ 0, xi Z
xj = 0 ó 1
Programación Lineal Entera Binaria
El Problema de la Mochila
http://es.wikipedia.org/wiki/Problema_de_la_mochila
Programación Lineal Entera Binaria
Ejemplo 1
Sea una empresa que fabrica objetos de papelería, que en el ejercicio económico que se cierra ha obtenido un excedente de
10.000 €; se plantea invertir esta cantidad (o parte de ella) en algunos productos, teniendo en cuenta que los beneficios son:
Lápices de colores con un beneficio de 11.000 €
Gomas de borrar con un beneficio de 9.000 €
Carboncillos con un beneficio de 1.000 €
Por otra parte, los costes son:
Coste de las instalaciones para fabricar lápices de colores: 10.000 €
Coste de las instalaciones para fabricar gomas de borrar: 6.000 €
Coste de las instalaciones para fabricar carboncillos: 4.000 €
Programación Lineal Entera Binaria
Queremos elegir alguno (o varios) de los productos anteriores. Parece lógico tener en cuenta la relación bi/ci en el que
consideramos los beneficios y los costes a la vez (algoritmos voraces):
En nuestro ejemplo, si calculamos este ratio, obtenemos:
Lápices de colores: 11.000/10.000 = 1.1
Gomas de borrar: 9.000/6.000 = 1.5
Carboncillos: 1.000/4.000 = 0.25
De forma que elegiríamos primero “Gomas de borrar” pues su ratio es el mayor (con un coste de 6.000 €); el siguiente ratio
(1.1) sobrepasa el peso de la mochila máximo, por lo que elegimos “carboncillos” (con un coste de 4.000 €), no pudiendo
elegir más, ya que nuestro presupuesto era de 10.000 €.
Programación Lineal Entera Binaria
Con esta solución, el beneficio obtenido es de 9.000+ 1.000= 10.000 €.
Como veremos más adelante, si este problema se resuelve por técnicas de Programación Lineal, la solución obtenida no es la misma, resulta que elegimos “Lápices de colores”, el cual nos proporciona un beneficio mayor, 11.000 €.
En este ejemplo, al ser sencillo, podemos estudiar exhaustivamente todas las combinaciones posibles (n=número de variables, en nuestro caso = 8 casos posibles) y elegir la que sea más conveniente:
Programación Lineal Entera Binaria
Lápices Gomas Carboncillos Coste Beneficio Admisibles
1 Si Si Si 20.000 21.000 No
2 Si Si No 16.000 20.000 No
3 Si No Si 14.000 12.000 No
4 No Si Si 10.000 10.000 Si
5 Si No No 10.000 11.000 Si
6 No Si No 6.000 9.000 Si
7 No No Si 4.000 1.000 Si
8 No No No 0 0 Si
Programación Lineal Entera Binaria
Lápices Gomas Carboncillos Coste Beneficio Admisibles
1 Si Si Si 20.000 21.000 No
2 Si Si No 16.000 20.000 No
3 Si No Si 14.000 12.000 No
4 No Si Si 10.000 10.000 Si
5 Si No No 10.000 11.000 Si
6 No Si No 6.000 9.000 Si
7 No No Si 4.000 1.000 Si
8 No No No 0 0 Si
Programación Lineal Entera Binaria
Lápices Gomas Carboncillos Coste Beneficio Admisibles
1 Si Si Si 20.000 21.000 No
2 Si Si No 16.000 20.000 No
3 Si No Si 14.000 12.000 No
4 No Si Si 10.000 10.000 Si
5 Si No No 10.000 11.000 Si
6 No Si No 6.000 9.000 Si
7 No No Si 4.000 1.000 Si
8 No No No 0 0 Si
Programación Lineal Entera Binaria
Formulación mediante Programación Lineal
Llamaremos:
n : número de objetos entre los que se puede elegir.
ci : peso del objeto “i”; ci representa el coste de escoger un objeto, pues va a ocupar “espacio de la mochila” y dejará fuera
otros objetos.
bi: utilidad o beneficio que proporciona cada objeto.
P: capacidad de la mochila, lo que equivale al presupuesto máximo del que se dispone.
Las variables del problema, xi, son binarias, es decir, sólo pueden tomar dos valores:
• El valor “1” si el objeto se incluye en la mochila
• El valor “0” si el objeto se excluye de la mochila
Programación Lineal Entera Binaria
Hemos de maximizar el beneficio total: b1x1+…+bnxn
Pero estamos sujetos a la restricción de la capacidad de la mochila, es decir: c1x1+…+cnxn P
Luego el problema le formulamos como:
n,,1i],1,0[x
Pxc:aSujeta
xbMaximizar
i
n
1i
ii
n
1i
ii
Programación Lineal Entera Binaria
Ejemplo 1 mediante Programación Lineal:
x1: lápices de colores, x2: gomas de borrar, x3: carboncillos
Objetivo: Maximizar 11000 x1+9000 x2+1000 x3
Restricciones: 10000 x1+6000 x2 + 4000 x310000
x1,x2,x3 [0,1]
x1,x2,x3 Z
Programación Lineal Entera Binaria
Ejemplo 1 mediante Programación Lineal:
x1: lápices de colores, x2: gomas de borrar, x3: carboncillos
Objetivo: Maximizar 11000 x1+9000 x2+1000 x3
Restricciones: 10000 x1+6000 x2 + 4000 x310000
x1,x2,x3 [0,1]
x1,x2,x3 Z
Beneficio Coste
Lápices 11.000 € 10.000 €
Gomas 9.000 € 6.000 €
Carboncillos 1.000 € 4.000 €
10.000
Programación Lineal Entera Binaria
Ejemplo 1 mediante Programación Lineal:
x1: lápices de colores, x2: gomas de borrar, x3: carboncillos
Objetivo: Maximizar 11000 x1+9000 x2+1000 x3
Restricciones: 10000 x1+6000 x2 + 4000 x310000
x1,x2,x3 [0,1]
x1,x2,x3 Z
Programación Lineal Entera Binaria
Ejemplo 1 mediante Programación Lineal:
x1: lápices de colores, x2: gomas de borrar, x3: carboncillos
Objetivo: Maximizar 11000 x1+9000 x2+1000 x3
Restricciones: 10000 x1+6000 x2 + 4000 x310000
x1,x2,x3 [0,1]
x1,x2,x3 Z
En resumen:
Mediante “algoritmos voraces”, fabricar gomas de borrar y carboncillos con un beneficio de 10.000 €.
Solución mediante el “problema de la mochila”: fabricar solo lápices con un beneficio de 11.000 €.
Programación Lineal Entera Binaria
Ejemplo 2
Una empresa dispone de un millón de euros para invertir en nuevos proyectos. En concreto dispone de 3 nuevos proyectos
posibles. En la siguiente tabla aparece el coste que supone cada uno de ellos, así como el beneficio que se espera de su
realización. La empresa desea saber en cuál debe invertir si quiere maximizar su beneficio esperado sin superar su
presupuesto:
Coste inversión Beneficio esperado
Proyecto 1 500.000 1.750.000
Proyecto 2 600.000 2.000.000
Proyecto 3 400.000 1.500.000
Proyecto 4 550.000 1.900.000
Programación Lineal Entera Binaria
Si utilizamos para resolverlo el “razonamiento lógico” que consiste en elegir, en primer lugar, aquel que ofrezca un mayor
ratio:
Beneficio esperado / Coste de inversión
Programación Lineal Entera Binaria
Si utilizamos para resolverlo el “razonamiento lógico” que consiste en elegir, en primer lugar, aquel que ofrezca un mayor
ratio:
Beneficio esperado / Coste de inversión
Programación Lineal Entera Binaria
Si utilizamos para resolverlo el “razonamiento lógico” que consiste en elegir, en primer lugar, aquel que ofrezca un mayor
ratio:
Beneficio esperado / Coste de inversión
De tal forma que elegiríamos los Proyectos 3 y 1 (no podemos más ya que elegir el 4 supondría un coste mayor del millón de
euros), con un beneficio esperado de 1.500.000+1.750.000 = 3.250.000 €
Programación Lineal Entera Binaria
Para resolverlo mediante Programación Lineal, llamamos xi a una variable binaria que toma el valor 1 si se elige el proyecto i
( i = 1, 2, 3, 4) y cero en caso contrario.
La formularemos:
Maximizar 1.75 106
x1+2 106
x2+1.5 106
x3+1.9 106
x4
Sujeta: 0.5 106
x1+0.6 106
x2+0.4 106
x3+0.55 106
x4 ≤ 106
x1, x2, x3, x4 [0,1]
x1, x2, x3, x4 Z
Programación Lineal Entera Binaria
Para resolverlo mediante Programación Lineal, llamamos xi a una variable binaria que toma el valor 1 si se elige el proyecto i
( i = 1, 2, 3, 4) y cero en caso contrario.
La formularemos:
Maximizar 1.75 106
x1+2 106
x2+1.5 106
x3+1.9 106
x4
Sujeta: 0.5 106
x1+0.6 106
x2+0.4 106
x3+0.55 106
x4 ≤ 106
x1, x2, x3, x4 [0,1]
x1, x2, x3, x4 Z
Coste inversión Beneficio esperado
Proyecto 1 500.000 1.750.000
Proyecto 2 600.000 2.000.000
Proyecto 3 400.000 1.500.000
Proyecto 4 550.000 1.900.000
Programación Lineal Entera Binaria
Para resolverlo mediante Programación Lineal, llamamos xi a una variable binaria que toma el valor 1 si se elige el proyecto i
( i = 1, 2, 3, 4) y cero en caso contrario.
La formularemos:
Maximizar 1.75 106
x1+2 106
x2+1.5 106
x3+1.9 106
x4
Sujeta: 0.5 106
x1+0.6 106
x2+0.4 106
x3+0.55 106
x4 ≤ 106
x1, x2, x3, x4 [0,1]
x1, x2, x3, x4 Z
Programación Lineal Entera Binaria
Para resolverlo mediante Programación Lineal, llamamos xi a una variable binaria que toma el valor 1 si se elige el proyecto i
( i = 1, 2, 3, 4) y cero en caso contrario.
La formularemos:
Maximizar 1.75 106
x1+2 106
x2+1.5 106
x3+1.9 106
x4
Sujeta: 0.5 106
x1+0.6 106
x2+0.4 106
x3+0.55 106
x4 ≤ 106
x1, x2, x3, x4 [0,1]
x1, x2, x3, x4 Z
Programación Lineal Entera Binaria
Para resolverlo mediante Programación Lineal, llamamos xi a una variable binaria que toma el valor 1 si se elige el proyecto i
( i = 1, 2, 3, 4) y cero en caso contrario.
La formularemos:
Maximizar 1.75 106
x1+2 106
x2+1.5 106
x3+1.9 106
x4
Sujeta: 0.5 106
x1+0.6 106
x2+0.4 106
x3+0.55 106
x4 ≤ 106
x1, x2, x3, x4 [0,1]
x1, x2, x3, x4 Z
El beneficio esperado es de 3.500.000€, 250.000 € mas que por el método anterior.
Programación Lineal Entera Binaria
Ejemplo 3
El Club Baloncesto Unicaja de Málaga quiere contratar uno o varios jugadores nuevos; para ello, ha sondeado el mercado y
ha encontrado a 5 jugadores, sabiendo que el club dispone de un presupuesto máximo de 50.000 €/ mes. En la siguiente
tabla aparece una relación de los candidatos a ser fichados junto con su aportación esperada y el sueldo que percibirían:
Sueldo Aportación
Jugador 1 50.000 15
Jugador 2 25.200 8
Jugador 3 36.000 15
Jugador 4 47.000 17
Jugador 5 12.000 7
Programación Lineal Entera Binaria
Resolviendo mediante programación lineal:
Maximizar 15x1+8x2+15x3+17x4+7x5
Sujeta a: 50 103
x1 + 25.2 103
x2 + 36 103
x3 + 47 103
x4 + 12 103
x5 ≤ 50 103
x1, x2, x3, x4, x5 [0,1]
x1, x2, x3, x4, x5
O dividiendo la primera restricción por 1000:
Maximizar 15x1+8x2+15x3+17x4+7x5
Sujeta a: 50 x1 + 25.2 x2 + 36 x3 + 47 x4 + 12 x5 ≤ 103
x1, x2, x3, x4, x5 [0,1]
x1, x2, x3, x4, x5 Z
Programación Lineal Entera Binaria
Obtenemos entonces que sería rentable la contratación de los jugadores 3 y 5 con un coste de 36000+12000=48000€/mes,
cantidad menor que la permitida de 50000€/mes
Programación Lineal Entera Binaria
Obtenemos que sería rentable la contratación de los jugadores 3 y 5 con un coste de 36000+12000=48000€/mes, menor que
la permitida de 50000€/mes
Podríamos escoger como criterio el ratio "Aportación/Sueldo", ya que tenemos en cuenta ambos factores en la decisión:
cuanto más alto sea este ratio, preferible será contratar a este jugador. Reconsideraremos el sueldo, dividiéndolo por 1.000
para hacer el ratio más operativo:
Sueldo Aportación Aportación / Sueldo
Jugador 1 50 15 0,3000
Jugador 2 25,2 8 0,3175
Jugador 3 36 15 0,4167
Jugador 4 47 17 0,3617
Jugador 5 12 7 0,5833
Programación Lineal Entera Binaria
Como hemos dicho, escogeremos aquellos jugadores con mejor ratio hasta agotar el presupuesto:
Jugador 5: ratio =0,58333, sueldo = 12.000 €
Jugador 3: ratio =0,41666, sueldo = 36.000 €
Programación Lineal Entera Binaria
Como el total disponible era de 50.000 € y tenemos acumulado 48.000 €, no hay más jugadores cuyo sueldo pueda entrar en
presupuesto, así que éste es nuestro resultado definitivo por este método, resultado que coincide con el obtenido mediante
Programación Lineal.