Embed Size (px)
DESCRIPTION
Ejemplo 01
Citation preview
ALGORITMO DEL TABLERO SIMPLEXProcedimiento de computo:Paso 01.Expresar de forma estándar el programa lineal de acuerdo al tablero simplex.Paso 02.Elija la solución básica factible inicial.
Caso 01. si todas las restricciones del problema original son (≤) las variables de holgura se utilizaran para una solución de inicio.Caso 02. Si las restricciones del problema original incluyen (≥) o (=) una técnica conocida como “la técnica de variables artificiales” se utiliza para dar una base de principio.
Paso 03.Generar nuevas soluciones básicas factibles utilizando la condición de optimidad y factibilidad hasta que se obtenga la solución optima (si esta existe y es acotada)
RESOLVER EL PROBLEMA CON EL MÉTODO SIMPLEX:
MAX (Z) = 2X1 +X2 -3X3 +5X4
SUJETO A :
X1 +7X2 +3X3 +7X4 ≤ 463X1 –X2 +X3 +2X4 ≤ 8 FORMA CANONÍCA2X1 + 3X2 -X3 +X4 ≤ 10X1,X2,X3,X4 ≥ 0
SOLUCIÓN:PASO 01. ESCRIBIR EN FORMA STANDARD EL PROBLEMA DE PL.
MAX (Z) = 2X1 +X2 -3X3 +5X4 + 0S1 +0S2 + 0S3. Sa.1X1 +7X2 +3X3 +7X4 + 1S1 =463X1 –1X2 +1X3 +2X4 + 1S2 =082X1 + 3X2 -1X3 +1X4 + 1S3 =10X1,X2,X3,X4 ≥ 0
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN
Z 1 -2 -1 3 -5 0 0 0 0
S1
S2
S3
0
0
0
1 7 3 7 3 -1 1 2
2 3 -1 1
1 0 0 0 1 0
0 0 1
46
08
10
LUEGO EL TABLERO SIMPLEX SERA:
COMO TODAS LAS RESTRICCIONES SON (≤) LA 1ra SOLUCIÓN BÁSICA FACTIBLE SERA
VARIABLES BÁSICASS1 = 46S2 = 08S3 = 10
VARIABLES NO BÁSICASX1 = 0X2 = 0X3 = 0X4 = 0Z = 0 FUNCIÓN OBJETIVO
NOTA: LA BASE DEL SISTEMA ESTA CONFORMADA POR UNA MATRIZ IDENTIDAD.
S1 S2 S31 0
00 1
00 0
1
LAS COLUMNAS CORRESPONDIENTES DE LAS VARIABLES NO BÁSICAS X1,X2,X3,X4, PUEDEN SER EXPRESADAS EN TÉRMINOS DE COMBINACIÓN LINEAL DE S1,S2,S3.
LA FUNCIÓN OBJETIVO PUEDE MEJORAR ¿COMO? INTRODUCIENDO UNA DE LA VARIABLES NO BÁSICAS X1,X2,X3,X4, A LA BASE DEL SISTEMA.
EN REEMPLAZO DE UNO DE LOS VECTORES CORRESPONDIENTES A LA BASE ANTERIOR (S1,S2,S3).
LA NUEVA SOLUCIÓN BÁSICA FACTIBLE CORRESPONDE A LAS VARIABLES QUE CONFORMAN ESTA NUEVA BASE DEL SISTEMA.
¿Qué VARIABLES NO BÁSICAS ENTRA A LA BASE DEL SISTEMA?¿Qué VARIABLE BÁSICA SALE DE LA BASE DEL SISTEMA?CONDICIONES DE OPTIMIDADLA CONDICIÓN DE OPTIMIDAD ESTABLECE QUE:1.- CUANDO SE ESTA MAXIMIZANDO LA VARIABLE NO BÁSICA QUE ENTRA A LA BASE PARA SER SOLUCIÓN ES AQUELLA QUE EN EL TABLERO SIMPLEX, EN LA FILA CORRESPONDIENTE Z TIENE EL MAYOR COEFICIENTE NEGATIVO.(EL MAS NEGATIVO)2.- CUANDO SE ESTA MINIMIZANDO, LA VARIABLE QUE ENTRA ES AQUELLA VARIABLE NO BÁSICA QUE EN LA FILA DE Z TIENE EL MAYOR COEFICIENTE POSITIVO (EL MAS POSITIVO).
CONDICIÓN DE FACTIBILIDAD.LA CONDICIÓN DE FACTIBILIDAD DETERMINA LA VARIABLE QUE SALE, COMO CON LA CONDICIÓN DE OPTIMIDAD SE DETERMINA QUE VARIABLE ENTRA O QUE VECTOR COLUMNA FORMA PARTE DE LA NUEVA BASE, A ESTA COLUMNA SE LE LLAMA COLUMNA PIVOTE.LA VARIABLE BÁSICA QUE SALE SERA AQUELLA CUYO COEFICIENTE bi/aij SEA EL MENOR POSITIVO
LA VARIABLE QUE ENTRA A LA SOLUCIÓN SERA X4 CUYO COEFICIENTE DE BENEFICIO EN LA TABLA ES IGUAL A -5 (CRITERIO DE OPTIMIDAD) LA VARIABLE DE SALE SE ELIGE A S2.
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN RAZÓN
Z 1 -2 -1 3 -5 0 0 0 0 ∆
S1
S2
S3
0
0
0
1 7 3 7 3 -1 1 2
2 3 -1 1
1 0 0 0 1 0
0 0 1
46
08
10
6.57
4
10
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN
Z 1 11/2 -7/2 11/2 0 0 5/2 0 20
S1
X4
S3
0
0
0
-19/2 21/2 -1/2 0 3/2 -1/2 1/2 1
1/2 7/2 -3/2 0
1 7/2 0 0 1/2 0
0 -1/2 1
18
04 6
S1 = 46/7 = 6.57, S2 = 8/2 = 4, S3 = 10/1 = 10
ENTRA -5, SALE S2 PIVOTE = 2
ITERACIÓN 01.Ec Z anterior. ( 1 -2 -1 3 -5 0 0
0 0) + Ec. Pivote x 5( 0 15/2 -5/2 5/2 5 0 5/2
0 20)
Ec Z nuevo 1 11/2 -7/2 11/2 0 0 5/20 20
Ec Z anterior. ( 0 1 7 3 7 1 00 46)
+ Ec. Pivote x -7( 0 -21/2 7/2 -7/2 7 0 -7/2
0 28)
Ec Z nuevo 0 -19/2 21/2 -1/2 0 1 -7/20 18
Ec Z anterior. ( 0 2 3 -1 1 0 01 10)
+ Ec. Pivote x -1( 0 3/2 ½ -1/2 -1 0 -1/2
0 -4)
Ec Z nuevo 0 ½ 7/2 -3/2 0 0 -1/21 6
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN RAZÓN
Z 1 11/2 -7/2 11/2 0 0 5/2 0 20 ∆
S1
X4
S3
0
0
0
-19/2 21/2 -1/2 0 3/2 -1/2 1/2 1
1/2 7/2 -3/2 0
1 7/2 0 0 1/2 0
0 -1/2 1
18
04
06
1.714
------
1.714
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN
Z 1 11/2 -7/2 11/2 0 0 5/2 0 20
S1
X4
X2
0
0
0
-19/2 21/2 -1/2 0 3/2 -1/2 1/2 1
1/2 7/2 -3/2 0
1 7/2 0 0 1/2 0
0 -1/2 1
18
04 6
S1 = 18/(21/2) = 1.714, X4 = 4/(-1/2) = ----- S3 = 6/(7/2) = 1.714
ENTRA -7/2, SALE S3 PIVOTE =7/2
Ambos coeficientes son iguales 1.714 solución degenerada temporal se elige cualquiera de ellos en este caso escogemos S3
ITERACIÓN 02
ITERACIÓN 02.Ec Z anterior. ( 1 -2 -1 3 -5 0 0
0 0) + Ec. Pivote x 5( 0 15/2 -5/2 5/2 5 0 5/2
0 20)
Ec Z nuevo 1 11/2 -7/2 11/2 0 0 5/20 20
Ec Z anterior. ( 0 1 7 3 7 1 00 46)
+ Ec. Pivote x -7( 0 -21/2 7/2 -7/2 7 0 -7/2
0 28)
Ec Z nuevo 0 -19/2 21/2 -1/2 0 1 -7/20 18
Ec Z anterior. ( 0 2 3 -1 1 0 01 10)
+ Ec. Pivote x -1( 0 3/2 ½ -1/2 -1 0 -1/2
0 -4)
Ec Z nuevo 0 ½ 7/2 -3/2 0 0 -1/21 6
BÁSICAS Z X1 X2 X3 X4 S1 S2 S3 SOLUCIÓN
Z 1
S1
X4
X2
0
0
0
