programación+entera+investigacion+operativa

PROGRAMACION ENTERA

PRESENTACIÓN MULTIMEDIAINDICE INTRODUCCION PONENTES

UNIVERSIDAD NACIONAL JOSE FAUSTINO SANCHEZ CARRION

INVESTIGACIÓN OPERATIVA I

EXPOSICION DECIMA SEMANAIngeniería de Sistemas

PRESENTACIÓN MULTIMEDIA

MÉTODO DE RAMIFICACIÓN Y ACOTAMIENTO.

MÉTODO DE PLANO CORTANTE

MÉTODO DE ENUMERACIÓN IMPLÍCITA CERO – UNO.

INDICE INTRODUCCION PONENTES

PROGRAMACION ENTERA

END






PROGRAMACION ENTERA

EJEMPLO DEL ALGORITMO DE GOMORY --SOLUCION GRAFICA --

EJEMPLO DEL ALGORITMO DE GOMORY --SOLUCION ANALITICA --

END






EJEMPLO DE ENUMERACION IMPLICITA CERO-UNO ADITIVO

EJEMPLO DEL ALGORITMO ADITIVO

PROGRAMACION ENTERA

END

Un enfoque primitivo de resolución consiste en evaluar cada una de las combinaciones de valores enteros para las variables del problema. Pero en este caso, analizar diez variables y diez valores en un problema tendríamos un número grande (diez mil millones) de posibles soluciones, lo que hace necesario planteamientos de solución inteligentes.

Estos se han dirigido por una parte hacia los "métodos exactos", es decir, aquellos que conducen a una solución óptima exacta para el problema combinatorio empleando técnicas que reduzcan la búsqueda de soluciones.



PROGRAMACION ENTERA

END

Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras solo toman valores en 0-1 ya que este tipo de variables permiten representar condiciones lógicas.

Este tipo de modelos permite representar modelos mucho mas complejos, aunque la resolución de los mismos se complica excesivamente. No se puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del óptimo. Siendo así que problemas con una sola decenas de variables pueden ser casi imposibles de resolver.



PROGRAMACION ENTERA

END

Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta.

En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital).

PROGRAMACION ENTERA

END



PROGRAMACION ENTERA

END



• En un problema de Programación Entera con frecuencia hay un número finito de soluciones factibles posibles. Entonces, es posible (teóricamente) enumerar y evaluar cada una de las soluciones enteras factibles con el fin de encontrar el óptimo.

• Lo más frecuente es el uso del Método De Ramificación y Acote en el que solamente es necesario una enumeración parcial, si se aplica sistemáticamente, en el hallazgo de una solución óptima entera. El método de Ramificación y Acote es una técnica para el logro de esto, ya que va eliminado conjuntos de soluciones bajo consideración

EL MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN

Ejemplo:

max Z = 5 X1 + 3 X2 + X3

s.a. : X1 + X2 + X3 ≤ 6

3 X1 + X2 + 4 X3 ≤ 9X1 ≤ 1X2 ≤ 1

X3 ≤ 4

X1 + X2 + X3 ≥ 0 y enteros

X1 = 0 X1 = 1

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

X3 = 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

Minimización• Considere el siguiente problema de minimización de costos:• Minimizar Z=X1+ 3X2+5X3

• Sujeto a: X1+X2+X3 6.5• 3X1+X2+4X3 9.5• X1 • X2• X3 • X1, X2, X3 0

1.- Resolver el problema como uno de programación lineal ignorando la restricción entera. Si la solución satisface la restricción entera, tenemos una solución optima para el problema de programación entera. La solución por programación lineal es:

x1 = 1, x2 = 2, x3 = 3.5

Z = 24.5 Como no es un solución entera necesitamos particionar el conjunto de soluciones

Seleccione una variable para Ramificar. Esta divide el conjunto de soluciones posibles en dos conjuntos. Seleccione una de las ramas (seleccionar Uno de los subconjuntos) para Nuevo análisis. resolver el problema Programación apropiado.

Determinar una solución entera Factible. Esta solución da una Cota superior inicial para el Costo mínimo

El costo de la solución obtenida en el paso Uno se convierte en la nueva cota inferior del costo Para todas las Soluciones de la rama que está siendo Investigada.

A

A

Compare la Cota inferior del Paso 2 con la actual cota superior del costo mínimo (el más bajo costo obtenido por una solución entera) para las ramas hasta aquí investigadas.

(a) Si la cota inferior excede a la actual superior, entonces elimine esta rama de las demás consideraciones.

(b) Si la cota inferior es menor que la cota superior actual y además es solución entera, entonces se convierte en la nueva o actual cota superior.

¿Todas las ramas han sido

investigadas?

La solución entera de costo mínimo es la solución entera factible asociada con la cota superior más actual.

Iteración 0

Paso 1:Ramificación

Paso 2: Acote

Paso 3:Comparación Y Eliminación

No

Si

Paso 4: Terminación

4X1 = 0.5, x2 = 2, X3 = 4

Costo Z = 26.5

Solución no entera: Rama

Cota Superior = 27

Solución no factible

5

X1

6

X1

X1 = 1, X2 = 2, X3 = 4

Costo Z = 27

Solución entera: también solución optima ya que no

hay mas ramas para investigar

Cota Superior = 27

Solución optima

Max: Z=X1+5X2+7X3+3X4

• Sujeto a • 7x1+3x2+2x3+4x4 <=15• 8x1+2x2+3x3+5x4 <=17• 1x1 <=4• 1x2 <=4• 1x3 <=1• 1x4 <=1

• x1, x2, x3, x4 Todos Enteros.

Maximización

Solucion por PL

X1 = 0, x2 = 4, X3 = 1

x4 = 0.25

Utilidad Z = 27.75

Solución no entera: Rama

Solucion PL

X1 = 1, X2 = 2, X3 = 1

X4 = 0

Utilidad Z = 18

Solución entera

Solucion PL

X1 = 0, x2 = 3, X3 = 1

x4 = 1

Utilidad Z = 25.00

Solución entera

Solucion PL

X1 = 0, X2 = 4, X3 = 1

X4 =0

Utilidad Z = 27.00

Solución entera

Solucion PL

X1 = 0.14, x2 = 4, X3 = 1

x4 = 0

Utilidad Z = 27.14

Solución entera

X1 =0 1<= x1 <=4

X4=0 X4=1

SoluciónEnteraOptima

VOLVER

EL MÉTODO DE PLANO CORTANTE O ALGORITMO DE GOMORY

Igual que en el algoritmo de Ramificación y Acotamiento, el algoritmo de plano cortante también empieza en la solución óptima de la Programación Lineal.

Sin embargo, en vez de utilizar la Ramificación y Acotamiento, modifica el espacio de la solución añadiendo sucesivamente restricciones especialmente construidas (llamadas cortes).

Ejemplo:Maximizar Z = 7x1 + 10x2Sujeto a: -x1 + 3x2 ≤ 6

7x1 + x2 ≤ 35x1, x2 ≥ 0 y entero

DESARROLLO ALGEBRAICO

Paso 1

Resolver el problema primal, si la solución es entera, corresponde a la óptima para el problema de Programación Lineal Entera.

Paso 2

Seleccionar decimales y escoger aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.

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.

Paso 3

Se separan la parte entera, es decir, quedarse solamente con la parte fraccionaria.

Nota:

VOLVER

Standarizando:Maximizar Z = 7x1 + 10x2 + 0x3 + 0x4Sujeto a: -x1 + 3x2 + x3 = 6 7x1 + x2 + x4 = 35 x1, x2, x3, x4 ≥ 0 y entero

Maximizar Z = 7x1 + 10x2Sujeto a: -x1 + 3x2 ≤ 6 7x1 + x2 ≤ 35 x1, x2 ≥ 0 y entero

EJEMPLO

Resolución:

Cj 7 10 0 0

Ck Xk bi X1 X2 X3 X4

00

X3X4

635

-17

31

10

01

Zj 0 0 0 0 0

Cj – Zj 7 10 0 0

Cj 7 10 0 0


100

X2X4

233

-1/322/3

10

1/3-1/3

01

Zj 20 -10/3 10 10/3 0

Cj - Zj 31/3 0 -10/3 0

PRIMERA TABLA SIMPLEX

SEGUNDA TABLA SIMPLEX

Elemento Pivote

Elemento Pivote

Cj 7 10 0 0


107

X2X1

7/29/2

01

10

7/22-1/22

1/223/22

Zj 133/2 7 10 63/22 31/22

Cj - Zj 0 0 -63/22 -31/22

La solución óptima es: X1 = 9 / 2 X2 = 7 / 2

X3 = 0 X4 = 0

Z = 133 / 2

TERCERA TABLA SIMPLEX

Desarrollaremos cortes a partir del reglón de la fuente X1; y del renglón de la fuente x2.

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

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

X1 + ( -1 + 21/22) X3 + (0 + 3/22) X4 = (4 + 1/2)

Luego:

X1 – X3 - 4 = -21/22 X3 – 3/22 X4 + ½

Información de la tabla simplex óptima:

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

Se obtiene:

Se selecciona arbritariamente el corte generado del renglón X2:

-7/22 X3 – 1/22 X4 ≤ - ½

-7/22 X3 – 1/22 X4 + S1 = - ½ (Corte I)

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

Debido a que X3 Y X4 son no negativos entonces el lado izquierdo debe satisfacer:

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

A partir del renglón fuente 2:

-21/22 X3 – 3/22 X4 + ½ ≤ 0

-7/22 X3 – 1/22 X4 + ½ ≤ 0

Cj 7 10 0 0 0

Ck Xk bi X1 X2 X3 X4 S1

1070

X2X1S1

7/29/2-1/2

010

100

7/22-1/22-7/22

1/223/22-1/22

001

Zj 133/2 7 10 63/22 31/22 0

Cj - Zj 0 0 -63/22 -31/22 0

-7/22 X3 – 1/22 X4 + S1 = - ½Añadiendo el corte:

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

Cj 7 10 0 0 0

Ck Xk Bi X1 X2 X3 X4 S1

1070

X2X1X3

332/711/7

010

100

001

01/71/7

1-1/7-22/7

Zj 62 7 10 0 1 9

Cj – Zj 0 0 0 -1 -9

X1 X2 X3 X4 S1

Zj 7 10 63/22 31/22 0

S1 0 0 -7/22 -1/22 1

COCIENTE - - -9 -31 -

Elemento pivote

TABLA SIMPLEX DUAL

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/7X1 + (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 , S2 ≥ 0 (Corte II)

X2 =X1 = X3 =Z =

332/711/762

Solución obtenida:

Cj 7 10 0 0 0 0

Ck Xk Bi X1 X2 X3 X4 S1 S2

10700

X2X1X3S2

332/711/7-4/7

0100

1000

0010

01/71/7-1/7

1-1/7-22/7-6/7

0001

Zj 62 7 10 0 1 9 0

Cj - Zj 0 0 0 -1 -9 0

Añadiendo el Corte II:-1/7 X4 – 6/7 S1 + S2 ≤ -4/7 , S2 ≥ 0

Aplicando el método dual simplex:

X1 X2 X3 X4 S1 S2

Zj 7 10 0 1 9 0

S2 0 0 0 -1/7 -6/7 1

COCIENTE - - - -7 -63/7 -

Elemento pivote

Cj 7 10 0 0 0 0

Ck Xk bi X1 X2 X3 X4 S1 S2

10700

X2X1X3X4

3414

0100

1000

0010

0001

1-1-46

011-7

Zj 58 7 10 0 0 3 7

Cj - Zj 0 0 0 0 -3 -7

TABLA SIMPLEX DUAL

La solución óptima (X1 = 4, X2 = 4, Z = 58) es toda entera.

VOLVER

MÉTODO DE LOS PLANOS CORTANTES DE GOMORY

I).METODO GRÁFICO

Ejemplo: Max: Z = X1 + 5 X2 S.AX1 + 10X2 < 20 X1 < 2 Xj > 0 y entero; j=1, 2

METÓDO GRÁFICO

Solución Óptima Continua (No Entera): X1=2; X2=9/5; X3=0; X4=0

Z=11

2

1

2 5 10 20

X2

X1

Óptimo(2,9/5)

Región Factible

Óptimo de la Solución Continua En el punto (2,9/5)

Óptimo de la Solución Entera o Real En el punto (2,0)

X1

con Z = 10

Éste método sirve para solucionar problemas

de más de dos (2) variables. Algoritmo

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

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

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.

2.) METODO ALGEBRAICO

Nueva restricción a partir de la restricción actual que tenga la variable cuyo valor en su parte fraccional sea mayor.

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.

Ejemplo: Max: Z = X1 + 5 X2 S.AX1 + 10X2 < 20 X1 < 2

Xj > 0 Y ENTERO; j=1, 2

Max: Z = X1 + 5X2C.S.R. X1 + 10X2 + X3 = 20 X1 + X4 = 2Xj > 0 Y Entero; j=1, 2, 3,4

A continuación solucionamos el problema por el método simplex, tal como se haría si el problema fuese de programación lineal continua.

Cj 1 5 0 0 b/a


0 X3 20 1 10 1 0 2

0 X4 2 1 0 0 1 No

Zj 0 0 0 0 0

Cj - Zj 1 5 0 0

A.1) PRIMERA TABLA SIMPLEX

VARIABLE QUE ENTRA: X2VARIABLE QUE SALE: X3

Cj 1 5 0 0 b/a


5 X22 1/10 1 1/10 0 20

0 X42 1 0 0 1 2

Zj10 -5/10 0 5/10 0

Cj - Zj5/10 0 -5/10 0

VARIABLE QUE ENTRA: X1VARIABLE QUE SALE: X4

A.2)SEGUNDA TABLA SIMPLEX

Cj 1 5 0 0 b/a


5 X2 9/5 0 0 1/10 -1/10 20

1 X1 2 1 1 0 1 2

Zj 11 1 5 1/2 1/2

Cj - Zj 0 0 -1/2 -1/2

A.3) ULTIMA TABLA SIMPLEX

Solución Óptima Continua (No Entera): X1=2; X2=9/5; X3=0; X4=0Z=11ECUACION 1 (Fila 1) .-Para construir la nueva restricción; ya que tiene la Variable (X2), cuyo valor de su parte fraccional es Mayor.

Ecuacion(1)

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

X2 + 1/10X3 – 1/10X4 = 9/5

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

(1+0)X2 + (0+1/10)X3 + (-1+9/10)X4 = (1+4/5) Simplificando

X2 + 1/10X3 – X4 + 9/10X4 = 4/5 + 1 ; positivo

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

1/10X3 + 9/10X4 = 4/5 + 1 – X2 + X4 positivo entero

Fíjese que el lado izquierdo subrayado debe ser positivo y el lado derecho subrayado, debe ser entero, luego podemos asegurar que:

1/10X3 + 9/10X4 > 4/5 ; Multiplicando por (-1) ;

-1/10X3 – 9/10X4 < -4/5 ;

Adicionando una variable de holgura (S1)

-1/10X3 – 9/10X4 + S1 = -4/5

Esta restricción se añade como una restricción secundaria a la tabla simplex Óptima de la PL, como sigue a Continuación

Cj 1 5 0 0 0

b/aCk Xk bi X1 X2 X3 X4 S1

5 X2 9/5 0 0 1/10 -1/10 0 -18

1 X1 2 1 1 0 1 0 2

0 S1 -4/5 0 0 -1/10 -9/10 1 8/9

Zj 11 1 5 1/2 1/2 0

Cj - Zj 0 0 -1/2 -1/2 0

(Cj - Zj)/arj no no 5 5/9 no

B.1) PRIMERA TABLA SIMPLEX DUAL

NOTA: Para hallar el elemento pivote en esta tabla Simplex Dual se toma en cuenta El valor fraccional de la fila [(Cj - Zj)/arj]. Por ello tomamos la columna de 5/9

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

Cj 1 5 0 0 0

Ck Xk bi X1 X2 X3 X4 S1

5 X2 17/9 0 1 1/9 0 -1/9

1 X1 10/9 1 0 -1/9 0 10/9

0 X4 8/9 0 0 1/9 1 -10/9

Zj 95/9 1 5 4/9 0 5/9

Cj - Zj 0 0 -4/9 0 -5/9

B.2) ULTIMA TABLA SIMPLEX DUAL

X1 = 10/9 = 1 + 1/9 ; X2 = 17/9 = 1 + 8/9 ; X3 = 0 ; X4 = 8/9 ; S1 = 0 ; Z = 95/9 = 10,5555555

Escogemos la variable básica con mayor parte fraccionaria, en caso de empate, escoja al azar. Escojo X4

1/9X3 + X4 – 10/9S1 = 8/9

Entonces: (0+1/9)X3 + (1+0)X4 + (-2+8/9)S1 = 8/9

1/9X3 + X4 –2S1 + 8/9S1 = 8/9 8/9 – X4 + 2S1 Positivo Entero Se sabe que:

1/9X3 + 8/9S1 > 8/9; ahora multiplicamos por (-1)-1/9X3 – 8/9S1 < -8/9;

ADICIONANDO UNA VARIABLE DE HOLGURA (S1)

-1/9X3 – 8/9S1 + S2 = -8/9

Cj 1 5 0 0 0 0 b/a


5 X2 17/9 0 1 1/9 0 -1/9 0 17

1 X1 10/9 1 0 -1/9 0 10/9 0 -10

0 X4 8/9 0 0 1/9 1 -10/9 0 8

0 S2 -8/9 0 0 -1/9 0 -8/9 1 8

Zj 95/9 1 5 4/9 0 5/9 0

Cj - Zj 0 0 -4/9 0 -5/9 0

(Cj - Zj)/arj no no 4 no 5/8 no

C.1) PRIMERA TABLA SIMPLEX DUAL

Cj 1 5 0 0 0 0


5 X2 2 0 1 1/8 0 0 -1/8

1 X1 0 1 0 -1/4 0 0 5/4

0 X4 2 0 0 1/4 1 0 -5/4

0 S1 1 0 0 3/8 0 1 -9/8

Zj 10 1 5 3/8 0 0 5/8

Cj - Zj 0 0 -3/8 0 0 -5/8

C.2) ULTIMA TABLA SIMPLEX DUAL

La Solución Optima Entera es Cuando:X1 = 0X2 = 2X3 = 0 X4 = 2S1 = 1S2 = 0

Max: Z = X1 + 5 X2Remplazando:

Z = 0*(X1) + 5*(2) Z = 10

VOLVER

PROGRAMACION LINEAL ENTERA BINARIA

Las situaciones en las que las decisiones aparecen como alternativas son las más frecuentes con las que nos enfrentamos.

La noción de tipo binario la utilizamos en nuestros razonamientos y en nuestras acciones: todo o nada, blanco o negro, abierto o cerrado, existe o no existe, 0 o 1, verdadero o falso, prendido o apagado, muerto o vivo, entre otros.

Los dos métodos más usuales para solucionar problemas de Programación Lineal Entera Binaria son

Enumeración Implícita Cero – Uno Método Aditivo de Egon Balas.

Algoritmo de Enumeración Implícita Cero_Uno

El primer algoritmo especial 0_1,llamado el algoritmo aditivo fue desarrollado en 1965,unos años después del desarrollo del de R y A.

El diseño del método heurística de sondeo en el algoritmo aditivo requiere la presentación del problema [0_1] en una forma conveniente que satisfaga las siguientes requerimientos:

1. La función objetivo es de tipo de minimización, con todos los coeficientes no negativos.

2. todas las restricciones deben ser del tipo (<=), con todas los lados derechos negativos , de ser necesario. Después, estas ecuaciones se convierten en inecuaciones, utilizando variables de holgura .

Ejemplo 1Convertir el problema 0_1 para satisfacer los

requerimientos iniciales del algoritmo aditivo.Maximice z = 3X1-5X2Sujeto A:

X1+ X2 = 5

4X1 + 6X2 >=4 X1,X2 >=0 Primero convertimos el problema a uno de minimización con todas las

restricciones (<=)como sigue.(a) Multiplique Z por -1 para obtener la minimización de W = -3X1+ 5X2(b) Convierte las ecuaciones de restricciones del tipo (<=)para obtener X1+ X2<=5 y –X1-X2<=-5.(c) Multiplique la segunda restricción por -1 para obtener -4X1-6X2<=-4

• Utilizando las holguras S1,S2,S3para las tres restricciones, el el problema se escribe como.

Minimice W = - 3X1 + 5X2

X1+ X2 +S1 = 5

- X1 - X2 + S2 = - 5 - 4X1 - 6X2 + S3 = - 4 X1,X2 =(0 ,1) S1 ,S2 ,S3 >=0

• Para asegurarse de que los coeficientes de la funcion objetivo son no negativo, sustituya Xj = 1 – Xj* para cualquier Xj con coeficiente negativo en la funcion objetivo. Por consiguiente , sustituimos X1= 1-X1*y ajustamos el lado derecho de las restriccionesconforme a ello . Ahora el algoritmo aditivo trata con X1* y X2.

VOLVER

problema binario(0_1) resuelto a través del del algoritmo aditivo

• Maximice W =3Y1+ 2Y2-5Y3 -2Y4+3Y5• Sujeto a Y1 + Y2 + Y3 + Y4 + Y5 <=4 7Y1 + 3Y3 - 4Y4 + 3Y5 <=8 11Y1 - 6Y2 + 3Y4 - 3Y5 >=3 Y1,Y3,Y2,Y4,Y5 = (0,1)1.- Multiplique la función objetivo por -12.- Multiplique la tercera restriccion por -13.- añade las variables de holgura S1,S2,S3 para convertir las

tres en ecuaciones 4.- Sustituya Y1=1-X1, Y2= 1- X2 , Y5= 1- X5, Y3= X3, Y4= X4

para obtener todos los coeficientes objetivos en positivos.

• Ahora tenemos:Minimice Z*= 3X1+ 2X2+ 5X3+ 2X4+ 3X5- 8Ignoremos la constante -8 y remplazemos Z*+8 con Z, de

manera que :Minimice Z= 3X1+ 2X2+ 5X3+ 2X4+ 3X5Sujeto a

-X1-X2+X3+2X4-X5+S1=1-7X1+3X3-4X4-3X5+S2=-211X1-6X2-3X4-3X5+S3=-1X1, X2, X3, X4, X5=(0,1)

Resumen de la ecuación Solución Básica factible X1 X2 X3 X4 X5 S1

S2 S3 Solución S1 -1 -1 1 2 -1 1

0 0 1 S2 -7 0 3 -4 -3 0

1 0 -2 S3 11 -6 0 -3 -3 0

0 1 -1

Coeficientes Objetivos 3 2 5 2 3

• Dada la solucion binaria inicial toda cero, la solucion de la holgura es:

(S1,S2,S3) =(1,-2,-1),Z=0

Si todas las variables fuesen no negativas concluiriamos que la solución binaria toda cero es optima.

• La variable de ramificación debe tener el potencial de reducir la no factibilidad de las holguras.

• Se excluye X3 y consideramos a X1,X2,X4,X5 como las variables de ramificación

• La selección de la variable de ramificacion entre las candidatas X1,X2,X4,X5,se basa en la medida de no factibildad de la holgura ; esta medida se basa.

• por ejemplo cuando determinamos X1=1 obtenemos S1= 1-(-1)= 2 ,S2= -2-(-7)=5,y

S3= -1-11= -12 Asi I1=-12,I2=-2 I4=-1,y I5=0Como I5 produce la medida mas pequeña de no factibilidad se

sellecciona X5 como variable de ramificacion: X5=1,X5=0; se crea los nodos 1y 2el nodo 1 produce los valores de holgura (S1,S2,S3)=

(2,1,2)y Z=3

Z=0

X5=0 X5=1

Z = 3(Sondeada)

0

2 1

• Para las variables X2 y X4 calculamos las medidas de factibilidad como:

I2=-2, I4=-1

Por consiguienteX4 es la variable de ramificacion del nodo 2

Z =0

X5=0 X5=1

Z =0

X4=0 X4=1

Z =0 Z =2 (sondeado)

(S1,S2,S3)=(-1,2,-1), Z =2

0

21

43

Z=0

X5=0 X5=1 Z=0

X4=0 X4=1 Z=3(sondeada)

Z=0 Z=2(sondeada) X2=0 X2=1

Z=0(sondeada) Z=2(sondeado)

0

1

4

2

6 5

3

• Ahora se han sondeado todos lo nodos pendientes . la solución optima esta asociada con el nodo 1, X5=1,z = 3,Y TODAS LAS DEMAS VARIABLES CERO. en términos de las variables originales , la solución es Y1= Y2 =1 y Y3= Y4 = Y5=0 con W = 5

VOLVER

Documents

programación+entera+investigacion+operativa