programaciÓn entera

UNIVERSIDAD

NACIONAL

E.A.P. INGENIERÍA DE SISTEMAS

INVESTIGACIÓN OPERATIVA I

PROGRAMACIÓN ENTERA

PROGRAMACIÓN ENTERA

Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros.

Existen 3 tipos de modelos de programación entera:

PROGRAMACIÓN ENTERA PURA: Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros.

Sin las restricciones adicionales de que X1, X2, X3 sean enteros (o sea las condiciones de integralidad) seria un problema de programación lineal.

Ejemplo:

MAX Z= 21X1 + 11X2

S. a: 7X1 + 4X2<= 13X1, X2 >= 0; X1, X2 son enteros

Solución:

Dando valores tenemos:

S= {(0,0); (0,1); (0,2); (0,3); (1,0); (1,1)}

Remplazando:

Z= 21X1 + 11X2

1: Z= 21(0) + 11(0)

= 0

2: Z= 21(0) + 11(3)

= 33

3: Z= 21(1) + 11(0)

= 21

Solución óptima: Z=33, X1= 0, X2= 3

Resolución como P. E (WinQSB):

Resolución como P. L (WinQSB):

PROGRAMACIÓN ENTERA MIXTA: Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad.

Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier número no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM).

Cuando se redondea esta solución, se llega a X1=2, X2=0 como una posible solución óptima.

Pero X1=2, X2=0 no es factible

Aun cuando se redondee hacia abajo X1=1, X2=0 no se llegaría a una solución óptima

PROGRAMACIÓN ENTERA BINARIA: Utiliza variables binarias.En algunos problemas se restringe el valor de las variables 0 o 1. Son de particular interés debido a que se pueden usar variables 0-1 para representar decisiones dicotómicas (si o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación entera 0-1Sólo tiene 2 alternativas posibles.

Ejemplos:

1) Un excursionista planea salir de campamento. Hay cinco artículos que desea llevar consigo, pero entre todos sobrepasan las 60 libras que considera puede cargar. Para ayudarse en la selección ha asignado un valor a cada artículo en orden ascendente de importancia:

Articulo 1 2 3 4 5Peso 42 23 21 15 7Valor 100 60 70 15 15

¿Qué artículos deberá llevar maximizando el valor total sin sobrepasar la restricción de peso? No se puede llevar más de un artículo del mismo tipo?

Sol:*Planteamiento del modelo:Se define la variable como el artículo que se debe o no llevar, por lo tanto en variable binaria.Variables:

“0” no llevar el articulo i

“1” llevar el articulo ixi

La función objetivo es maximizada debido a que se desea llevar la mayor cantidad de artículos maximizando su valor pero sujeto a las restricciones.

MAX: Z=100x1+60x2+70x3+15x4+15x5

s.a:

42x1+23x2+21+x3+15x4+7x6<=60

Esta restricción la definimos como la sumas de los artículos que no beben excederse de las 60 libras (capacidad de la mochila).

*Solución del Modelo:

Se puede resolver el modelo con el Método de ramificación y acotamiento para el problema tipo mochila, obteniéndose la siguiente solución:

Z óptimo=145

X1=0

X2=1

X3=1

X4=1

X5=0

*Interpretación de Resultados:

Se obtiene un nivel máximo de importancia de 145 si se lleva un artículo del tipo 2,3

Y 4 y ninguno del tipo 1y 5, llevando un peso máximo de 59 libras.

2) Hay 6 ciudades (ciudades 1 a 6) en el condado de Kilroy. El condado debe decidir dónde construir la estación de bomberos. Asimismo, el condado quiere construir la cantidad mínima de estaciones de bomberos necesarias para tener la certeza de que por lo menos una está dentro de 15 minutos (tiempo de manejo) de cada ciudad. Los tiempos (en minutos) necesarios para ir en automóvil de una ciudad a otra del condado se indican en la tabla 1. Plantee un PE mediante el cual Kilroy sepa cuántas estaciones de bomberos debe construir y donde ubicarlas.

Tabla 1:

ADesde Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad 6

Ciudad 1 0 10 20 30 30 20Ciudad 2 10 0 25 35 20 10Ciudad 3 20 25 0 15 30 20Ciudad 4 30 35 15 0 15 25Ciudad 5 30 20 30 15 0 14Ciudad 6 20 10 20 25 14 0

Solución:

*Planteamiento del modelo:

Kilroy tiene que determinar, para cada ciudad, si construye una estación de bomberos allí.Definimos las variables 0-1 (binarias) x1, x2, x3, x4, x5 y x6 mediante:

1 si se construye una estación de bomberos en la ciudad i

X1

0 si no sucede así.

Donde:

Z= x1+x2+x3+x4+x5+x6

¿Cuáles son las restricciones de Kilroy? Se muestra en la tabla 2 según el enunciado:

Tabla 2:

Ciudad A 15 minutos1 1,22 1,2,63 3,44 3,4,55 4,5,66 2,5,6

Por lo tanto:

X1+x2>=1 (restricción de la ciudad 1)

X1+x2 + x6>=1 (restricción de la ciudad 2)

X3+x4>=1 (restricción de la ciudad 3)

X3+x4+x5 >=1 (restricción de la ciudad 4)

X4+x5+x6>=1 (restricción de la ciudad 5)

X2 +x5+x6>=1 (restricción de la ciudad 6)

*Solución del Modelo:

Una solución óptima para este PE es:

Z=2

X2=x4=1

X1=x3=x5=x6=0

*Interpretación de Resultados:

El condado kilroy puede construir dos estaciones de bomberos: una en la ciudad 2 y otra el la ciudad 4.

PROGRAMACIÓN ENTERA MIXTA:

Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier número no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM).

EJEMPLO:

Compañía Gandhi fabrica 3 tipos de prendas de vestir: camisetas, shorts y pantalones. La elaboración de cada tipo de prenda requiere que Gandhi tenga disponible el tipo de maquinaria apropiada. La maquinaria necesaria para manufacturar cada tipo de prenda se tiene que rentar a las tarifas siguientes: maquinaria para camisetas, 200 dólares por semana; maquinaria para shorts, 150 dólares por semana; maquinaria para pantalones, 100 dólares por semana. La confección de cada tipo de prenda también requiere las cantidades de tela y mano de obra que se indican en la tabla:

Tipo de Prenda Mano de Obra(H)

Tela(Yardas cuadradas)

Camiseta 3 4

Shorts 2 3

Pantalones 6 4

Están disponibles cada semana 150 horas de mano de obra y 160 yardas cuadradas de tela. El costo unitario variable y el precio de venta para cada tipo de prenda, se proporcionan en la siguiente tabla:

Tipo de PrendaPrecio de Venta

(Dólares)Costo Variable

(Dólares)

Camiseta 12 6

Shorts 8 4

Pantalones 15 8

En el problema actual, se pueden elaborar cuando mucho 40 camisetas, 53 Shorts y 25 Pantalones

En el problema actual, se pueden elaborar cuando mucho 40 camisetas, 53 Shorts y 25 Pantalones

Formule una P.E cuya solución maximice la utilidad semanal de Gandhi.

SOLUCIÓN:Al igual que en los planteamientos de PL, se define una variable de decisión por cada decisión que Gandhi debe tomar. Evidentemente, Gandhi tiene que decidir cuántas prendas de cada tipo debe fabricar a la semana:

Xj= Cantidad de tipo de prenda j fabricada a la semana

El costo de rentar la maquinaria depende sólo de los tipos de prenda que se elaboran, y no de la cantidad de cada tipo de prenda. Esta situación nos permite expresar el costo de rentar maquinaria utilizando las variables siguientes:

1 Si se fabrican tipo de prenda j

En pocas palabras, si Xj>0, entonces yj=1, y si Xj=0, entonces yj=0.

Por consiguiente:La utilidad semanal de Gandhi= (ingresos por las ventas semanales) – (costos variables semanales) – (costos semanales de la renta de maquinaria)

También:Costo a la semana de la renta de maquinaria= 200Y1 + 150Y2 + 100Y3

Ahora ya se puede expresar las utilidades de la semana como:

Utilidades de la semana= (12X1 + 8X2 +15X3) - (6X1 + 4X2 + 8X3) - (200Y1 + 150Y2 + 100Y3)

= 6X1 + 4X2 +7X3 - 200Y1 - 150Y2 - 100Y3

Por lo tanto, Gandhi desea maximizar:

Z= 6X1 + 4X2 +7X3 - 200Y1 - 150Y2 - 100Y3

Ya que el suministro de mano de obra y tela es limitado, Gandhi afronta las dos restricciones siguientes:

Restricción de la mano de Obra: 3X1 + 2X2 +6X3 <= 150

Restricción de tela : 4X1 + 3X2 +4X3 <= 160

La función objetivo será:

MAX Z= 6X1 + 4X2 +7X3 - 200Y1 - 150Y2 - 100Y3

S. a: 3X1 + 2X2 +6X3 <= 1504X1 + 3X2 +4X3 <= 160 X1 <= 40Y1

X2 <= 53Y2

X3 <= 25Y3

X1, X2 , X3 >= 0 ; X1, X2 , X3 son enteros Y1 , Y2 , Y3= 0 ó 1

Solución óptima con P.L:

Yj=0 Si no sucede así

Solución óptima con P.E:

RAMIFICACIÓN Y ACOTACIÓN

El primer algoritmo B&B fue desarrollado por A. Land y G. Doig en 1960, para el problema general de programación lineal entera, mixta y pura. Después en 1965 E. Balas desarrollo el algoritmo aditivo para resolver problemas de programas lineal entero con variables binarias (cero o uno) puras. Los cálculos del algoritmo aditivo eran tan sencillos (principalmente suma y resta) que se le llamó como un gran avance en la solución del programa lineal entero.

El método de diseño de algoritmos Ramificación y Acotación es una variante del Backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización.

La técnica de Ramificación y Acotación se suele interpretar como un árbol de soluciones, donde cada rama nos lleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima.

Estructura:

Un criterio para dividir los subconjuntos candidatos a contener la solución óptima encontrados en cada fase.

http://es.wikipedia.org/wiki/Backtracking

El cálculo de una cota (inferior o superior) para los valores de la función en cada subconjunto candidato.

Un criterio para seleccionar un subconjunto para una partición posterior.

Pasos:

Ramificación: Variables Acotación: Valor de la función objetivo

A partir de la solución del PLA:

La ramificación consiste en dividir cada problema en dos nuevos subproblemas, obtenidos mediante la imposición de restricciones excluyentes que dividen el conjunto de oportunidades del problema original en dos partes, pero eliminando en ambas partes la solución no entera del problema original. Si xbi no entero, entonces se genera a partir de dicho valor, dos restricciones x i≤ [xbi] y xi≤ [xbi]+1 (siendo [xbi] la parte entera por defecto de x i), que añadidas cada uno por separado al problema original, da lugar a dos nuevos subproblemas.

Por ejemplo la x1 tiene que ser entera, pero en l solución anterior (PLA u otro), la variable vale: x1=6.8. Esta solución no es válida, ya que no es admisible un valor fraccional, por tanto se introducirán las siguientes restricciones: x1≤6 y x1≥7, de forma que se ha eliminado una porción del conjunto donde no hay soluciones enteras, pero se mantienen las enteras. Así se prosigue con todas las variables hasta que sean enteras.

Si al proceso de ramificación no se mejora de alguna forma, llegaríamos a analizar TODAS las soluciones enteras (Enumeración Total). Por eso, se añade la fase de Acotación, esta tiene que ver con el valor de la función objetivo.

A medida que se va ramificando se obtienen soluciones enteras y otras que no lo son.

No podemos asegurar que la primera solución entera obtenida sea la solución óptima, sino que es necesario comprobar si existen otras soluciones enteras o no.

El análisis del PLA: Ramificación se realiza siempre a partir de aquel problema que tiene el mejor valor de la función objetivo, y siempre que exista alguna solución (no entera) con un valor de la función objetivo.

Aplicación del método “Ramifica y acota” a un problema de programación lineal entera.

1º) Resolvemos el problema P0 relajando la condición que exige que x e y sean enteros

MaxZ= x1+1.2x 2

sujetoa :

x1+5 y ≤25

9 x1+6 y≤49.5

x1≥0

x2≥0

x1 , x2enteros

2º) Se ramifica el problema P0 en dos direcciones según que x2 ≤ 4 o X2 ≥ 5 , ya que no puede haber ninguna solución entera con 4 ≤ x2 ≤ 5

Finalizado el proceso de ramificación y poda, la solución óptima entera corresponde al subprograma P3:

MÉTODO DEL PLANO CORTANTE O ALGORITMO DE GOMORY

El algoritmo de corte o de gomory es otro procedimiento para hallar la solución de los problemas de programación entera.

Este algoritmo elimina en la región factible porciones donde esta la solución del problema relajado, pero no puede estar la solución entera optima.

De esta manera modifica el espacio de la solución añadiendo sucesivamente restricciones especialmente construidas (llamadas cortes).

Ejemplo:

Maximizar Z = 7x1 + 10x2

Sujeto a: -x1 + 3x2 ≤ 6

7x1 + x2 ≤ 35

X1, X2 ≥ 0 y entero

Se pretende mostrar una de las versiones de Gomory (Fraccional), existen otros, como son el entero y el mixto.

Éste método sirve para solucionar problemas de más de dos (2) variables.

Algoritmo

3. Si no es entera, introducir una restricción nueva para la variable no entera, que tenga la mayor parte fraccional (Quebrar empates arbitrariamente) y resolver el nuevo problema mediante el método dual simplex.

1. Encontrar la solución, empleando el método simplex.

2. Si la solución es entera, entonces estamos en el óptimo.

(1)

(3)

(2)

a) Escriba cada constante como la suma de: Un número entero de cualquier signo y una fracción no negativa, menor que uno (1).

b) Cambiar la ecuación trasladando los coeficientes enteros al lado derecho.

Nota: Luego de encontrar una solución óptima para el primal, por Simplex y después de agregarle la primera nueva ecuación al sistema se pasa a Dual – Simplex, para quitarle la infactibilidad al sistema.

Al relajar la condición de que las variables sean enteras y resolver el problema de P.L. continua asociado, vamos a suponer que en la solución final las variables básicas son las m primeras. Esto supone que la matriz de restricciones adopta la forma

Todo número real puede descomponerse en la suma de su parte entera y su parte decimal, que es siempre positiva:

1,122,111,11 ............................. Bxaxaxax nmnmmmmm

2,222,211,22 ...................... Bxaxaxax nmnmmmmm

mnmnmmmmmmmmm Bxaxaxax ,22,11, ......

27

4221

3227

2 xxx

29

4223

3221

1 xxx

X1X2

R = E + D. Y recordemos que

E + D ≥ 0⇒ E ≥ 0

Cada coeficiente del conjunto de restricciones puede ser expresado como suma de su parte entera y su parte decimal, de forma que el conjunto de restricciones puede expresarse como

Desigualdades que han de cumplir todas las soluciones del problema, incluidas las enteras.

Consideremos, por ejemplo, la primera restricción. La podemos expresar como

El lado derecho de la desigualdad es siempre positivo. Para una solución entera el paréntesis del segundo miembro es una cantidad entera y también lo será entonces

Por tanto, para una solución entera habrá de cumplirse que

11,1,111,11,11 ................ DExdexdex nmnmnmmmm

22,2,211,21,22 .......... DExdexdex nmnmnmmmm

mmnmnmmnmmmmmmmm DExdexdex ,,11,1, ....

21

4223

32221

1 4)1( xxx

d1 ,m+1 xm+1+. .. .+d1 ,m+n xm+1≤E1−(x1+e1 ,m+1xm+1+.. . .+e1 ,m+n xm+1 )+D1

R=E1−(x1+e1,m+1 xm+1+.. . .+e1 ,m+n xm+1 )

R=E1−(x1+e1,m+1 xm+1+.. . .+e1 ,m+n xm+1 )≥0

x1+e1 ,m+1xm+1+.. . .+e1,m+n xm+1≤E1

Se añade esta última restricción a la tabla final del simplex

Y se resuelve el nuevo modelo. El proceso se reitera hasta que todas las soluciones sean enteras.

A partir del siguiente ejemplo, vamos a mostrar la manera de aplicar el algoritmo de Gomory para solucionar un problema de Programación Lineal Entera:

Ejemplo:

Max 5x1 + 2x2

s.a 2x1 + 2x2 ≤ 9

3x1 + x2 ≤ 11

x1, x2 ≥ 0

x1, x2 ∈ Z

Solución:

Resolviendo el problema por el algoritmo del simplex, sin tener en cuenta que las dos variables deben ser enteras, obtenemos la siguiente tabla final:

1,122,111,11 ......................... Bxaxaxax nmnmmmmm

2,222,211,22 ................... Bxaxaxax nmnmmmmm

mnmnmmmmmmmmm Bxaxaxax ,22,11, .....

11,111,11 .... Exexex mnmmm

ULTIMA TABLA SIMPLEX

La solución optima es: x1 =3.25 , x2=1.25 , x3=x4=0

Hemos de construir, por tanto, un plano de corte de Gomory. Para ello se determina la parte entera y fraccionaria de la solución:

x1=3+1/4 , x2=1+1/4 , por tanto f1=f2=1/4

Puesto que f1=f2 , podemos elegir cualquiera de las dos variables para construir el plano de corte, elegimos X2 y la restricción a añadir en la tabla es:

Se divide en factores enteros y fraccionales, siempre y cuando el componente fraccional sea estrictamente positivo.

Dejamos al lado izquierdo los coeficientes fraccionales y al lado derecho los coeficientes enteros

Imponiendo la condición de que el primer miembro de esta igualdad sea no positivo, se obtiene un corte en la región factible:

Tabla Dual Simplex

41

421

343 xx

Nueva Restricción

Cj 5 2 0 0

Ck Xk bi X1 X2 X3 X4

2 X2 1.25 0 1 0.75 -0.5

5 X1 3.25 1 0 -0.25 0.5

Zj 18.75 5 2 0.25 1.5

Zj – Cj 0 0 0.25 1.5

x2+34x3−

12x4=1+ 1

4

x2+34x3+(−1+ 1

2) x4=1+ 1

4

34x3+

12x4−

14=1−x2+ x4

Con su correspondiente variable de holgura x5

La solución encontrada no es factible pues la nueva variable de holgura es negativa.

Utilizamos el simplex dual para encontrar, si la hay, una solución factible. Entra la variable X3 en substitución de X5.

Cj 5 2 0 0 0

Ck Xk bi X1 X2 X3 X4 X5

Cocientes 333.00.75-0.25 30.5-

1.5

entra

− 34x3 −1

2x4+x5=− 1

4

2 X2 1 0 1 0 -1 1

5 X1 3.33333333 1 0 0 0.66666667 -0.3333

0 X3 0.33333333 0 0 1 0.66666667 -1.3333

Zj 18.6666667 5 2 0 1.33333333 0.33333

Zj – Cj 0 0 0 1.33333333 0.33333

Puesto que la solución no es entera, hemos de introducir un nuevo plano de corte, considerando nuevamente la división de cada una de las variables en su parte entera y su parte fraccionaria:

x1=3+1/3 , x3=1/3 , por tanto f1=f3=1/3

Eligiendo la variable x1 la restricción a añadir en la tabla final es:




31

532

432 xx

Nueva Restricción

con variable de holgura x6. entra

sale

31

6532

432 xxx

x1+23x 4−

13x5=3+ 1

3

x1+23x 4+(−1+ 2

3) x5=3+ 1

3

23x4+

23x5−

13=3+x5−x1


Utilizamos el simplex dual para encontrar, si la hay, una solución factible. Entra la variable X 5 en substitución de X6.

Cj 5 2 0 0 0 0

Ck Xk bi X1 X2 X3 X4 X5 X6

2 X2 0.5 0 1 0 -2 0 1.5

5 X1 3.5 1 0 0 1 0 -0.5

0 X3 1 0 0 1 2 0 -2

0 X5 0.5 0 0 0 1 1 -1.5

Zj 18.5 5 2 0 1 0 0.5

Zj – Cj 0 0 0 1 0 0.5

Como obtenemos de nuevo una solución no entera, hemos de construir, de nuevo, un plano de corte de Gomory, que en este caso es:



x2−2x4+32x6=

12

x6+12x6=

12(1+ 1

2 ) x6=12

12x6−

12=x6


Aplicando el método dual del símplex, sale de la base X7 y entra X6.

21

621 x

Nueva Restricción

21

7621 xx

con su correspondiente variable de holgura x7.

Cocientes-10.5-

0.5

entra

sale

Cj 5 2 0 0 0 0 0

Ck Xk bi X1 X2 X3 X4 X5 X6 X7

2 X2 -1 0 1 0 -2 0 0 3

5 X1 4 1 0 0 1 0 0 -1

0 X3 3 0 0 1 2 0 0 4

0 X5 2 0 0 0 1 1 0 -4.5

0 X6 1 0 0 0 0 0 1 -2

Zj 18 5 2 0 1 0 0 1

Zj – Cj 0 0 0 1 0 0 1

Como obtenemos una solución no admisible, aplicamos de nuevo el dual del símplex. Sale de la base X2 y entra X4.

Cj 5 2 0 0 0 0 0

Ck Xk bi X1 X2 X3 X4 X5 X6 X7

0 X4 0.5 0 -0.5 0 1 0 0 -1.5

5 X1 3.5 1 0.5 0 0 0 0 0.5

0 X3 2 0 1 1 0 0 0 -1.5

0 X5 1.5 0 0.5 0 0 1 0 -3

0 X6 1 0 0 0 0 0 1 -2

Zj 17.5 5 2.5 0 0 0 0 2.5

Zj – Cj 0 0.5 0 0 0 0 2.5

La solución obtenida todavía no es entera, hemos de introducir, por tanto, un nuevo plano de corte de Gomory, que en este caso es:


con variable de holgura X8.


Utilizamos el simplex dual para encontrar, si la hay, una solución factible. Entra la variable X2 en substitución de X8.

Cocientes -50.5-2.5 -50.5-

2.5

entra

21

721

221 xx

sale

Nueva Restricción

21

721

221 xx

x 1 +12x2+

12x7=3+ 1

2

12x2+

12x7−

12=3−x1

− 12x2−

12x7+x8=− 1

2

Cj 5 2 0 0 0 0 0 0

Ck Xk bi X1 X2 X3 X4 X5 X6 X7 X8

0 X4 1 0 0 0 1 0 0 -1 -1

5 X1 3 1 0 0 0 0 0 0 1

0 X3 1 0 0 1 0 0 0 -2 2

0 X5 1 0 0 0 0 1 0 -2 1

0 X6 1 0 0 0 0 0 1 -2 0

2 X2 1 0 1 0 0 0 0 1 -2

Zj 15 5 2 0 0 0 0 2 1

Zj – Cj 0 0 0 0 0 0 2 1

En esta tabla la solución asociada es x* = (3, 1, 1, 1, 1, 1, 1, 0, 0), la cual ya es entera y habríamos terminado nuestro problema

COMPROBACION POR SOFTWARE

Ejemplo:

Maximizar Z = 7x1 + 10x2

S. a:

-x1 + 3x2 ≤ 6

7x1 + x2 ≤ 35

x1, x2 ≥ 0 y entero

Estandarizando:

Maximizar Z = 7x1 + 10x2 + 0x3 + 0x4

Sujeto a:

-x1 + 3x2 + x3 = 6

7x1 + x2 + x4 = 35

x1, x2, x3, x4 ≥ 0 y entero

SEGUNDA TABLA

SIMPLEX

ELEMENTO PIVOTE

PRIMERA TABLA SIMPLEX

Información de la tabla simplex optima

Ecuación 1 : X2 + 7/22 X3 + 1/22 X4 = 7/2

LA SOLUCIÓN ÓPTIMA ES: X1 = 9 / 2

X2 = 7 / 2 X3 = 0 X4 = 0

Z = 133 / 2

TERCERA TABLA SIMPLEX

Ecuación 2 : X1 – 1/22 X3 + 3/22 X4 = 9/2

En la primera iteración del algoritmo del plano de corte se puede usar cualquiera de los cortes.

Cálculo de la nueva restricción, a partir de la Ecuación 1

X2 + 7/22 X3 + 1/22 X4 = 7/2

Remplazamos cada coeficiente de la ecuación, por la suma de un número entero de cualquier signo y una fracción no negativa menor que uno (1).

(0+1)X2 + (0+7/22)X3 + (0+1/22)X4 = (3+1/2)

Trasladamos los términos con coeficiente entero, al lado izquierdo.

X2 - 3 = 1/2 - 7/22X3 - 1/22X4

Entera fraccionaria

Tomamos la parte fraccional, en la cual tiene q ser (<=0)

1/2 - 7/22X3 - 1/22X4 <= 0

-7/22X3 - 1/22X4 <= -1/2

Adicionando una variable de holgura (s1)

-7/22X3 - 1/22X4 + s1= -1/2 ………………………CORTE I

Esta restricción se añade como una restricción secundaria a la tabla simplex óptima.

Nueva Restricción Agregada

La tabla simplex es óptima, pero no factible. Aplicamos el método simplex dual para recuperar la factibilidad, lo que nos da:

arj = son los coeficientes de las variables de la nueva restricción insertada.

Solución obtenida

X1: 32/7

X2: 3

X3: 11/7

Z: 62

Elemento pivote

El menos Negativo

TABLA SIMPLEX

La última solución todavía es de no enteros en X1 Y X3.

Entonces seleccionamos X1 como el renglón fuente

X1 + 1/7 X4 – 1/7 S1 = 32/7

X1 + (0 + 1/7) X4 – (-1 + 6/7) S1 = (4 + 4/7)

El corte asociado es:

-1/7 X4 – 6/7 S1 + 4/7 ≤ 0

-1/7 X4 – 6/7 S1 ≤ -4/7

-1/7 X4 – 6/7 S1 + S2 = -4/7, .............(CORTE II)

Ahora agregamos la nueva restricción a nuestra última tabla simplex dual.

Primera tabla simplex dual

Elemento pivote

El menos negativo

Nueva Restriccion

ARJ

La solución optima entera es cuando:

X1: 4

X2: 3 s1:0

X3: 1 s2:0

X4: 4

Z: 58

Solución factible, óptima y entera

MÉTODO DE ENUMERACIÓN IMPLÍCITA

Método de Dankin(1966)

Se usa frecuentemente para resolver P.P.E. con variables de decisión igual a 0 o a 1.

Toda variable de decisión de un P.P.E., donde Xi Z se puede representar así:

i:=0…n

• Consiste en enumerar todas las soluciones posibles Xj que sean enteras, para ir encontrando soluciones factibles enteras e ir guardando la mejor. Cada solución encontrada es comparada con la siguiente generada.

• Cada rama del árbol especifica, para alguna variable Xj, que Xj=1.

Ejm: Problema( X1, X2, X3, X4, X5, X6 )

Modo de determinar si un nodo tiene una terminación que satisfaga una restricción dada

Pasos

1° Se comprueba si la terminación de un nodo i es factible

2° Se verifica si el nodo i no tiene terminación factible

Límite: Si no son factibles los 2 pasos anteriores se elimina el nodo.

Alternativa: La terminación de un nodo que es factible y cumplimiento del criterio de factibilidad indica una posible solución del problema.

X2=1 X2=1 X1=0X2=0

5 6

X1=0X1=1

3

3

4

2

1

Enunciado: Con el fin de promover la seguridad de los estudiantes, el departamento de seguridad de una Universidad, se encuentra en proceso de instalar teléfonos de emergencia en ubicaciones selectas dentro de sus instalaciones.

El departamento quiere instalar un número mínimo de teléfonos, siempre y cuando cada una de las principales calles del campus cuente por lo menos con un teléfono.

El siguiente mapa muestra las calles principales.

1 3

2

4

5

6

8

7

Se colocarán los teléfonos de la siguiente manera:

Otro ejemplo:

MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5

Con sus restricciones:

Para nuestro caso el número de combinaciones es 25 =32, que corresponde a la cantidad de soluciones posibles:

En el tablero anterior algunas soluciones son válidas, mientras que otras no porque en algunos casos violan una, unas o todas las restricciones. Solución Óptima: Y*1 = 1; Y*2 = 1; Y*3 = 0; Y*4 = 0; Y*5 = 0; Z* = 5

Método Aditivo de Egon Balas para problemas binarios (0,1)

No confundir éste método para solucionar problemas de asignaciones, aquí el problema de programación lineal tiene la forma general y lo diferente es que las variables solo pueden tomar valores binarios (0,1).

La filosofía del método se basa en pensar que si se tiene una función objetiva minimizando y todos sus términos son positivos, entonces, entre menos variables tomen el valor de uno (1), la función objetiva será mínima.

Algoritmo1. La función objetivo se minimiza, en caso de maximización, use la regla de equivalencia:

Maximizar (Z) = Minimizar (-Z).2. Se requiere que Cj > 0 , para todo j. En caso de que Cj < 0 , entonces Xj se sustituye

por: 1 - X’J , es decir: Xj = 1 - X’J

Ejemplo: Min Z = 3X1 - 2X2 => X2 = 1 - X’2Remplazando Z = 3X1 - 2(1 - X’2) = 3X1 - 2 + 2X’2Min Z = 3X1 + 2X’2 - 2, que para el caso queda: Min Z = 3X1 + 2 X’2Nota: El cambio de variable, también se debe aplicar a todas las restricciones.

Ejemplo 1Para apreciar la utilidad del método, resolveremos el siguiente ejemplo, primero, contemplando todas las posibles soluciones y a continuación aplicando el método aditivo de Egon Balas, que reduce el número de soluciones posibles a contemplar.

Minimice Z = 8X1 + 7X2 + 6X3 + 5X4 + X5 -6X1 – 3X2 + 2X3 – 4X4 – X5 < -3 -4X1 – 5X2 – 4X3 – 3X4 + 3X5 < -7

Xj = 0,1 ; j = 1,2,3,4,5

El número posible de soluciones es de 2n, en donde n es el número de variables. En el ejemplo, el número posible de soluciones es 25 = 32

En el siguiente diagrama se muestran todas las 32 posibles soluciones:

Algunas de éstas soluciones no son factibles, ya que no satisfacen las restricciones. Aquellas que satisfagan las restricciones, deberán ser remplazadas en la función objetivo y la que la haga más pequeña, será la solución óptima. Éste procedimiento es dispendioso, tanto en la consecución de todas las soluciones como en su evaluación para todas las restricciones y en su evaluación final sobre la función objetiva.

Aplicación del Método de Egon BalasEvaluamos cada restricción, primeramente suponiendo que todas las variables valgan cero, y después, alternativamente a cada variable le asignamos el valor de uno (1) y al resto de variables el valor de cero (0). Cada vez que una solución no satisfaga una restricción, el que tan lejos está de satisfacerla, lo llamamos infactibilidad.

Ejemplo: Si

X1 = 1 y X2 = X3 = X4 = X5 = 0Remplazando en la restricción uno (1), establecemos que: -3 < 0 , luego aquí la infactibilidad es cero (0), ya que la solución evaluada, satisface la restricción, convirtiéndola en una afirmación verdadera.

Remplazando en la restricción dos (2), establecemos que: 3 < 0 , luego aquí la infactibilidad es tres (3), ya que la solución evaluada, no satisface la restricción, convirtiéndola en una afirmación falsa. El que tan lejos está de ser una verdad, es lo que llamamos infactibilidad.

En total, la solución evaluada tiene una infactibilidad de 0 + 3 = 3

Si en ésta primera iteración, encontramos una solución cuya infactibilidad sea cero (0), hemos encontrado la solución factible y óptima. Si encontramos que varias soluciones tienen la infactibilidad igual a cero (0), remplazamos todas éstas soluciones en la función objetivo y la solución óptima será aquella que haga que Z sea mínima.

Si no hay ninguna solución con su infactibilidad igual a cero (0), Escogemos la solución que menor infactibilidad tenga y de ella la variable que esté valiendo uno (1). Remplazamos en las restricciones dicha variabley sobre dichas restricciones iniciamos la segunda iteración. Éste procedimiento se repite hasta encontrar la solución óptima factible.

Primera Iteración-6X1 – 3X2 + 2X3 – 4X4 – X5 + 3 < 0-4X1 – 5X2 – 4X3 – 3X4 + 3X5 + 7 < 0X1 = X2 = X3 = X4 = X5 = 03 < 07 < 0 Infactibilidad = 10X1 = 1 ; X2 = X3 = X4 = X5 = 0-3 < 03 < 0 Infactibilidad = 3X2 = 1 ; X1 = X3 = X4 = X5 = 00 < 02 < 0 Infactibilidad = 2 ; La menorX3 = 1 ; X1 = X2 = X4 = X5 = 05 < 03 < 0 Infactibilidad = 8X4 = 1 ; X1 = X2 = X3 = X5 = 0-1 < 0

Segunda Iteración (X2 = 1)-6X1 + 2X3 – 4X4 – X5 < 0-4X1 – 4X3 – 3X4 + 3X5 + 2 < 0X1 = 1 ; X3 = X4 = X5 = 0-6 < 0-2 < 0 Infactibilidad = 0 ;X3 = 1 ; X1 = X4 = X5 = 02 < 0-2 < 0 Infactibilidad = 2X4 = 1 ; X1 = X3 = X5 = 0-4 < 0-1 < 0 Infactibilidad = 0X5 = 1 ; X1 = X3 = X4 = 0-1 < 05 < 0 Infactibilidad = 5

4 < 0 Infactibilidad = 4X5 = 1 ; X1 = X2 = X3 = X4 = 02 < 010 < 0 Infactibilidad = 12

Aquí concluimos, que lo menos malo esfijar la primera variable con valor deuno (1) a X2 ya que presenta la menorinfactibilidad, remplazamos a X2 = 1 enlas dos restricciones e iniciamos la 2ºiteracion

En ésta iteración hay dos solucionescon infactibilidad igual a cero (0), evaluadola función objetivo con ambassoluciones, encontramos la soluciónóptima con Z = 12Solución: X1* = 0 ; X2* = 1 ; X3* = 0 ;X4* = 1X5* = 0 ; Z* = 12Solamente se hizo necesario escudriñar10 de las 32 soluciones posibles.

programaciÓn entera

Documents