Introducción y casos de aplicación

Introducción y casos de aplicación.

En muchos de los problemas propios de la administración las variables de decisión tienen sentido solamente si tienen valores enteros. Por ejemplo, muchos problemas propios de la administración requieren de la asignación o localización de hombres, máquinas y materiales para actividades de producción en cantidades enteras. La restricción de que las variables de decisión tienen que tener valores enteros encausó el desarrollo de algoritmos especiales de programación. Sin embargo, es común en la práctica que un problema de programación lineal entera primero sea resuelto por el método simplex (ignorando así las restricciones enteras) y redondeando luego los valores no enteros a soluciones resultantes enteras. Esto a menudo es un enfoque inadecuado, ya que hemos llegado a una solución entera que es sustancialmente diferente de una solución optima entera.

Los primeros intentos para resolver un problema de programación entera surgieron de la metodología utilizada en la resolución de problemas de programación lineal. El primer algoritmo finito fue dado por R. Gomory y se denominó Método de los planos de corte.

Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de modelos lineales enteros y sus métodos de solución es en la actualidad bastante extenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad.

Los avances teóricos en la resolución de programación entera han sido importantes, si bien no se ha visto correspondido en la eficacia del cómputo. Esto es debido a los errores de redondeo cometidos en las sucesivas iteraciones y acumulados en el cómputo que realizan los ordenadores.

Considere el problema de programación lineal (PPL) formulado a continuación. El conjunto de soluciones factibles del problema se muestra gráficamente.

PROBLEMA DE PROGRAMACIÓN LINEAL

Maximizar Z= 6x1+7x2

Sujeto a x1+2x2 ≤ 8

X1-x2 ≤ 4

X1 ≥ 0 x2 ≥ 0

La solución óptima tiene lugar en el vértice C determinado por la intersección de las ecuaciones

X1+2x2=8 y x1-x2=4

Las coordenadas del vértice C son:

X1=16/3 y x2=4/3

Esto es, observe que los valores óptimos de las variables de decisión son

X1=16/3 y x2=4/3

Suponga que estamos interesados en la solución óptima entera del (PPL). Entonces nuestro conjunto de soluciones factibles no es el área sombreada que se muestra en la figura, pero los puntos repintados mostrados en la otra figura son los valores de las soluciones factibles enteras.

Para determinar la solución óptima entera del (PPL) necesitamos resolver el siguiente modelo de programación entera:

PROBLEMA DE PROGRAMACIÓN LINEAL

Maximizar Z= 6x1+7x2

Sujeto a x1+2x2 ≤ 8

X1-x2 ≤ 4

X1 ≥ 0 x2 ≥ 0

X1 , x2 enteros

El conjunto de soluciones factibles enteras del (PPE) son listadas en la primera tabla, además con su contribución o utilidad.

Observamos en ambas tablas que hay 20 valores de soluciones enteras factibles para el PPE. Por inspección en la segunda columna de la primer tabla vemos que la solución óptima entera es

X1=4, x2=2 con utilidad Z=$38.

X1 X2 Utilidad= Z=6x1+7x2

0 0 $0

0 1 7

0 2 14

0 3 21

0 4 28

1 0 6

1 1 13

1 2 20

1 3 27

2 0 12

2 1 19

2 2 26

2 3 33

3 0 18

3 1 25

3 2 32

4 0 24

4 1 31

4 2 38 solución óptima (PPE)

5 1 37 solución redondeo (PPL)

Tabla de soluciones enteras

Comparando la solución óptima del PPL y del PPE se obtiene la siguiente tabla:

Modelo Solución óptima Utilidad máxima

PPL X1=16/3 , x2=4/3 $41.33

PPE X1=4 , x2=2 $38.00

Observe que la restricción entera hace decrecer la utilidad de $41.33 a $38.

PREGUNTA. Suponga que resolvemos el PPL por el método simple y redondeamos la solución resultante. Obtendremos la solución entera óptima del PPE???

Respuesta. No. El valor óptimo de x1 en el (PPL) es 16/3=5 1/3, el cual si redondeamos da un valor de x=5. Pero 4 es el valor óptimo de x1 en el (PPE).

Similarmente, el valor óptimo de x2 en el (PPL) es 4/3=1 1/3, el cual redondeado da un valor de x2=1. Pero 2 es el valor óptimo para x2 en el PPE.

La tabla de soluciones enteras nos muestra que redondeando una solución por el método simplex no tiene que aportar la solución entera óptima.

Ejemplo—Problema de presupuesto de capital

La Bestel Construction Company el año próximo tiene la oportunidad de invertir en cinco proyectos diferentes, P1, P2, P3, P4 y P5, cada uno con un beneficio neto estimado como se muestra en la siguiente tabla.

TABLA 1 Beneficio neto esperado para los proyectos

Proyecto número Beneficio neto esperado (000s)

1 $100

2 80

3 70

4 60

5 90

Ya que los diferentes requerimientos de cada proyecto (mano de obra, equipo, etc.), los costos varían de proyecto a proyecto. Además las obligaciones de requerimientos de flujo de caja, hace que la Bestel no pueda invertir en todos los cinco proyectos.

En la siguiente tabla se listan los costos totales o salidas de cada requeridos para invertir en cada proyecto.

Proyecto número Costo esperado (000s)

1 $60

2 40

3 20

4 40

5 50

TABLA 2—Costo esperado para los proyectos del ejemplo.

La Bestel estima que tendrá una disponibilidad de caja en la cantidad de $150,000 para el próximo año. ¿En cuales proyectos podría invertir la Bestel el próximo año?

El problema mostrado por la Bestel Construction Inc. Puede ser formulado como un modelo de programación entera con valores enteros en las variables de decisión.

Variables de decisión

Xj=

...