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= 1 si el proyecto j es seleccionado

0 si el proyecto j no es seleccionado j= 1, 2, 3, 4, 5.

X1, x2, x3, x4 y x5 son variables de decisión cero/1. Por lo tanto el problema de la Bestel es un problema de programación entera. Por ejemplo:

X1=1, x2=1, x3=0, x4=0, x5=1

Podría ser la decisión de seleccionar solamente los proyectos P1, P2 y P3.

Meta o función objetivo. La meta de la Bestel es seleccionar los proyectos que maximicen la utilidad total esperada.

Sea P= utilidad total esperada. Entonces la función objetivo es

P=100x1+80x2+70x3+60x4+90x5

Por ejemplo, si la decisión es seleccionar solamente los proyectos P1, P3 y P5, esto es:

X1=1, x2=1, x3=0, x4=0, x5=1,

Entonces la utilidad esperada es

P=100x1+80x2+70x3+60x4+90x5

=100(1)+80(1)+70(0)+60(0)+90(1)

=$270,000

Restricciones sobre las variables de decisión. Hay una restricción de caja de $150,000. La salida de caja total esperada es (en miles de dólares)

60x1+40x2+20x3+40x4+50x5

La cual no puede exceder de los fondos esperados disponibles.

60x1+40x2+20x3+40x4+50x5<150.

PREGUNTA. ¿Puede la Bestel escoger todos los cinco proyectos sin excederse en los fondos disponibles esperados?

Respuesta. NO. Si x1=1, x2=1, x3=1, x4=1 y x5=1, entonces el costo esperado es

60(1)+40(1)+20(1)+40(1)+50(1)=$210,

El cual está $60,000 por encima de la disponibilidad de fondos.

Definición y modelos de programación entera y binaria.

Un problema de Programación Entera es un problema de programación lineal en el cual algunas de las variables, o todas, tienen que ser números enteros no negativos. El objetivo de la Programación Lineal Entera es encontrar el valor de la función que

Max (Min) z = c1 x1 + c2 x2 + … + cn xn

Denominada función objetivo.

La función objetivo se encuentra sujeta a una serie de restricciones:

Cuando se nos presente la resolución de un Problema de Programación Entera, lo resolvemos como un problema de Programación Lineal. Si sus soluciones son enteras, ésta es la solución para el problema de programación lineal entera.

En cualquier problema se verifica que la solución óptima

Zop (PL) ≥ zop (PLE)

Ésta relación se cumple siempre porque cualquier solución factible para un problema de PLE es también una solución factible para la su relajación lineal (PL).

El problema de programación lineal que se obtiene al omitir todas las restricciones enteras o variables 0-1 se llama relajación de programación lineal para la programación entera. Criterio de optimalidad en un problema de PLE: Una solución entera factible xF es óptima para el problema de PLE si es solución óptima de una relajación lineal. En tal caso se cumple que

...