método simplex ii - · pdf fileel metodo simplex de las dos fases ejemplo: el modelo se...
Post on 06-Feb-2018
240 Views
Preview:
TRANSCRIPT
1
MÉTODO SIMPLEX
PROFESORA: LILIANA DELGADO HIDALGO
Liliana.delgado@correounivalle.edu.co
Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3
4x1 + 3x2 – S2 = 6
x1 + 2x2 + S3 = 4
x1 , x2,S2, S3 ≥ 0
Estandarización Tradicional
Como n=4 y m=3, el Simplex hace n-m variables “cero” (en este caso una) para crearun sistema de ecuaciones consistente que arroje una Solución Inicial Inmediata yFactible .
Qué pasa si x1 se hace igual a cero? Qué pasa si x2 se hace igual a cero?
x1 = 0
x2 = 3
S2 = 3
S3 = -2
x2 = 0
x1 = 1
S2 = -2
S3 = 3
2
El método SIMPLEX necesita que la base inicial sea la matriz idéntica para poder arrancar. El problema general de PL es:
0X
b),,(AX
:a sujeto
CX )(
≥≥≥≥
≥≥≥≥====≤≤≤≤
====ZMINMAX
Si todas las restricciones son de ≤ , el método SIMPLEX inicia con la base igual a la matriz idéntica, formada por las columnas de las variables de holgura. Pero si existe por lo menos una restricción de = ó de ≥ , la matriz idéntica no aparece en forma automática y por lo tanto debe crearse mediante la adición de variables artificiales.
En general, las restricciones de “=“ y de “≥” generanproblemas al Simplex al momento de construir la tablainicial que arranca el procedimiento. En cambiocuando las restricciones son de “≤” no existen estosinconvenientes y el método puede iniciar sinproblemas con las variables de holgura.
El Simplex soluciona estos inconvenientes de arranquecreando Variables Artificiales.
3
Min Z = 4x1 + x2
Sujeto a:
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Min Z = 4x1 + x2
Sujeto a:
3x1 + x2 = 3
4x1 + 3x2 – S2 = 6
x1 + 2x2 + S3 = 4
x1 , x2,S2, S3 ≥ 0
Min Z = 4x1 + x2 + MR1+ MR2
Sujeto a:
3x1 + x2 + R1 = 3
4x1 + 3x2 – S2 + R2 = 6
x1 + 2x2 + S3 = 4
x1 , x2, S2, S3, R1, R2 ≥ 0
Aquí n = 6 y m = 3, siendo (n-m) = 3. Es decir, al hacer 3 variables iguales a “cero” saleuna Solución Inicial Inmediata Factible. [Puede observar que estas 3 variables no básicasiniciales deben ser x1, x2, s2]. La Tabla Simplex Inicial se construye teniendo en cuenta queen el renglón (Zj – Cj) las variables básicas tienen necesariamente valores de “cero”.
Tenga en cuenta que en la Tabla 1:
- Variables No Básicas: x1, x2, s2
- Variables Básicas: R1, R2, S3
El MÉTODO DE LA GRAN M
Min Z = 4x1 + x2 + MR1+ MR2
Min Z = 4x1 + x2 + MR1+ MR2
Sujeto a:
3x1 + x2 + R1 = 3
4x1 + 3x2 – S2 + R2 = 6
x1 + 2x2 + S3 = 4
x1 , x2, S2, S3, R1, R2 ≥ 0
De la primera y segunda restricción:
R1 = 3 - 3x1 - x2
R2 = 6 - 4x1 - 3x2 + S2
Transformación necesaria en la Función Objetivo:
Min Z = 4x1 + x2 + M(3 - 3x1 - x2) + M(6 - 4x1 - 3x2 + S2)
Min Z = (4 - 7M) x1 - (4M - 1)x2 + MS2 + 9M
Variables Básicas
Coeficientes en la Función Objetivo
(Cj)
x1 x2 S2 S3 R1 R2 Solución (R.H.S.)
R1 M 3 1 0 0 1 0 3
R2 M 4 3 -1 0 0 1 6
S3 0 1 2 0 1 0 0 4
Zj - Cj - (4-7M) (4M -1) -M 0 0 0 9M
4
Tabla 1
Variables Básicas
Coeficientes en la Función
Objetivo (Cj)
x1 x2 S2 S3 R1 R2 Solución (R.H.S.)
R1 M 3 1 0 0 1 0 3
R2 M 4 3 -1 0 0 1 6
S3 0 1 2 0 1 0 0 4
Zj - Cj - (4-7M) (4M -1) -M 0 0 0 9M
Tabla 4
Variables Básicas
Coeficientes en la Función
Objetivo (Cj)
X1 x2 S2 S3 R1 R2 Solución (R.H.S.)
X1 4 1 0 0 -1/5 2/5 0 2/5
X2 1 0 1 0 3/5 -1/5 0 9/5
S2 0 0 0 1 1 1 -1 1
Zj - Cj 0 0 0 -1/5 7/5-M -M 17/5
Tabla OPTIMA
NOTA: Las variables artificiales siempre deben ser al final No Básicas, o tener valor de “cero”, ya que solo fueron creadas para arrancar el procedimiento.
Maximice Z = (5/2)X1 + X2
Sujeto a: 3X1 + 5X2 ≤ 155X1 + 2X2 ≤ 10Xj > 0 ; j = 1, 2
Tabla Final OPTIMA
Variables
Básicas
Coeficientes en la Función Objetivo
(Cj)
x1 X2 S1 S2 Solución
(R.H.S.)Razón θ
S1 0 0 3.8 1 -0.6 9 9/3,8 = 2,36
X1 5/2 1 0.4 0 0.2 2 2/0.4 = 5
Zj - Cj 0 0 0 0.5 5 -
Entonces aquí la variable que entra es la variable no-básica que tenga el valor (Zj - Cj) másnegativo. Observe la variable No Básica x2 con un valor de “0”. Si esta variable entra, lafunción objetivo permanece inmodificable.
Puede encontrarse otra solución con el mismo valor de Z
Observe que una Tabla Optima deMAXIMIZACION tiene todos los valoresdel renglón (Zj – Cj) ≥ 0. Es decir, elcriterio funciona a la inversa de laMinimizacion.
Múltiples Soluciones
5
Minimice Z = - X1 + X2 Sujeto a: - X1 + X2 ≤ 0
- 0,5X1 + X2 ≤ 1 Xj > 0 ; j = 1, 2
Problema sin solución Cuando en la Tabla Final existe como solución una Variable Artificial con valor mayor que cero.
Tabla Inicial
Variables Básicas
Coeficientes en la Función Objetivo
(Cj)
x1 X2 S1 S2 Solución (R.H.S.) Razón θ
S1 0 -1 1 1 0 0 0/-1 = 0
S2 5/2 -0.5 1 0 1 1 1/-0,5 = -2
Zj - Cj 1 -1 0 0 0
Entra x1 pero: ¿Cuál variable sale?
Problema de solución infinita (ó No Acotada)
Condiciones De Parada Del Método Simplex
1. Si todos los valores (Zj – Cj) son positivos (MAX), o negativos (MIN), el SIMPLEX concluye y se tiene entonces una solución ÓPTIMA.
2. Si el valor (Zj – Cj) de, por lo menos, una cualquiera de las variables NO básicas (iniciales) en el tablero SIMPLEX óptimo es cero (0), el SIMPLEX ha detectado un conjunto infinito de soluciones que puede escribirse como una combinación líneal convexa de cualesquiera dos ó más de ellas.
3. Si el tablero SIMPLEX actual tiene una variable candidata a entrar a la base, pero no hay una candidata a salir de ella, esto es, falla la regla del cociente, relacionada con la factibilidad de la siguiente solución básica, entones se concluye que se está trabajando con una función objetivo no acotada.
4. Si el tablero SIMPLEX cumple con la condición de parada enunciada en 1 pero aparece una variable artificial con un valor positivo en la solución óptima, entonces el SIMPLEX ha detectado que el problema NO tiene solución factible alguna.
6
3.3 EL METODO SIMPLEX DE LAS DOS FASES
Este método elimina el problema de trabajar con la “Gran M” y los
errores de redondeo asociados.
FASE I: trata de encontrar una solución básica factible inicial.
Aquí se minimiza la suma de las variables artificiales, sujeto a las restricciones del problema original. Hay dos posibilidades:
a) La suma de las variables artificiales es igual a cero, entonces se continua con la fase II.
b) Si el valor óptimo de la función objetivo es mayor que cero, entonces el problema original no tiene ninguna solución factible.
FASE II: Se cambia la función objetivo a la función objetivo original y se utiliza la solución básica factible encontrada en la fase I.
EL METODO SIMPLEX DE LAS DOS FASES
Ejemplo:
El modelo se transforma como sigue para iniciar el método de las dos fases:
0)X,X(
4X2X
6XX4
3XX3 :
X4X Z
21
21
21
21
21
≥≤+≥+
=++=
Sujeto a
Minimizar
esArtificial Var. , ;0),,,(
4 2
6 34
3 3 :a sujeto
Minimizar
212121
2 21
2121
121
21'
AASSXX
SXX
ASXX
AXX
AAZ
≥=++=+−+=++
+=
7
EL METODO SIMPLEX DE LAS DOS FASES
Variables Básicas
Coeficientes en la FO
(Cb)
X1 X2 S1 S2 A1 A2 Solución (R.H.S.)
A1 1 3 1 0 0 1 0 3
A2 1 4 3 -1 0 0 1 6
S2 0 1 2 0 1 0 0 4
Zj - Cj 7 4 -1 0 0 0 9
esArtificial Var. , ;0),,,(
4 2
6 34
3 3 :a sujeto
Minimizar
212121
2 21
2121
121
21'
AASSXX
SXX
ASXX
AXX
AAZ
≥=++=+−+=++
+=
biC ijP
bC
Coeficientes de lasvariables en lafunción objetivo
Columnas
ijP
�� − �� = �� � × �� ���
= 1� − ��
EL METODO SIMPLEX DE LAS DOS FASES
Variables
Básicas
Coeficientes en la FO (Cb)
X1 X2 S1 S2 A1 A2 Solución (R.H.S.)
Razón Mínima
(θ)
A1 1 3 1 0 0 1 0 3 3/3 = 1
A2 1 4 3 -1 0 0 1 6 6/4 = 1.5
S2 0 1 2 0 1 0 0 4 4/1 = 4
Zj - Cj 7 4 -1 0 0 0 9
esArtificial Var. , ;0),,,(
4 2
6 34
3 3 :a sujeto
Minimizar
212121
2 21
2121
121
21'
AASSXX
SXX
ASXX
AXX
AAZ
≥=++=+−+=++
+=
Qué variable entra a la base? Qué variable sale a la base?
8
Variables
Básicas
Coeficientes en la FO (Cb)
X1 X2 S1 S2 A1 A2 Solución (R.H.S.)
Razón Mínima ( θ)
X1 0 1 1/3 0 0 1/3 0 1 1 / (1/3) = 3
A2 1 0 5/3 -1 0 -4/3 1 2 2 / (5/3) = 1,2
S2 0 0 5/3 0 1 -1/3 0 3 3/(5/3) = 1,8
Zj - Cj 0 5/3 -1 0 -7/3 0 2
Variables Básicas
Coeficientes en la FO (Cb)
X1 X2 S1 S2 A1 A2 Solución (R.H.S.)
Razón Mínima ( θ)
X1 0 1 0 1/5 0 3/5 - 1/5 3/5X2 0 0 1 - 3/5 0 - 4/5 3/5 6/5S2 0 0 0 1 1 1 -1 1
0 0 0 0 -1 -1 0 Zj - Cj
Se debe pasar a la fase dos, con la anterior solución inicial
EL METODO SIMPLEX DE LAS DOS FASES
Gauss…
EL METODO SIMPLEX DE LAS DOS FASES
En la FO original: Cb 4 1 0 0
Variables Básicas
Coeficientes en la FO (Cb)
X1 X2 S1 S2 Solución (R.H.S.)
Razón Mínima ( θ)
X1 4 1 0 1/5 0 3/5 (3/5)/(1/5) = 3X2 1 0 1 - 3/5 0 6/5 -S2 0 0 0 1 1 1 1/1 = 1
0 0 1/5 0 18/5Zj - Cj
Variables Básicas
Coeficientes en la FO (Cb)
X1 X2 S1 S2 Solución (R.H.S.)
X1 4 1 0 0 - 1/5 2/5X2 1 0 1 0 3/5 9/5S1 0 0 0 1 1 1
0 0 0 - 1/5 17/5Zj - Cj
FASE 2 �� − �� = �� � × �� ���
= 1� − ��
21 X4X Z +=Minimizar
9
3. MÉTODO SIMPLEX Cualquier problema de Programación Lineal, en su forma estándar puede escribirse así:
0X
bAX
CX
≥=
=
:a sujeto
Z(MIN) MAX
donde
Z = Valor de la función objetivo C = Vector fila de los coeficientes de todas las variables en la función
objetivo X = Vector columna de todas las variables del problema (incluyendo las de
holgura) A = Matriz de coeficientes del sistema b = Vector del lado derecho
3. MÉTODO SIMPLEX En su forma general, un modelo estándar tendrá n variables (incluyendo las de holgura) y m restricciones. Así, en general, las dimensiones de cada matriz y vector son las siguientes:
[ ] nnCCCC ×= 1 321 ······· C
1
2
1
.
.
.
×
=
nnX
X
X
X (incluye variables de holgura Sk)
nmmnm
n
n
aa
aaa
aaa
×
=
. . . .
. . . . . .
. . . . . .
. . . . . .
· · ·
· · ·
1
22221
11211
A
1
2
1
.
.
.
×
=
mmb
b
b
b
10
3.1 Soluciones Básicas En Forma Matricial
[ ] [ ] ; ; T2 1210 0 3 5 S S X X== XC
=
=
10
15 ;
1025
0153bA
0)X,(X
10X25X
15X53X
:a sujeto
X3X5ZMaximizar
Original Modelo
21
21
21
21
≥≤+≤+
+=
•
0),,X,(X
10 X25X
15 X53X
:a sujeto
X3X5ZMaximizar
Estándar Modelo
2121
221
121
21
≥=++=++
+=
SS
S
S
•
3.1 Soluciones Básicas En Forma Matricial
Solución Básica Nº X1
X2
S1
S2
Factible
Valor de Z
1 0 0 15 10 Si 0
2 0 3 0 4 Si 9
3 0 5 -10 0 No –
4 5 0 0 -15 No –
5 2 0 9 0 Si 10
6 20/19 45/19 0 0 Si 235/19 = 12.4
•
0),,X,(X
10 X25X
15 X53X
:a sujeto
X3X5ZMaximizar
Estándar Modelo
2121
221
121
21
≥=++=++
+=
SS
S
S
•
Variables no básicas
Variables básicas
11
3.1 Soluciones Básicas En Forma Matricial
=
=
=
−
10
15
10
15
10
01
10
15
10
01
1
2
1
2
1
S
S
S
S
Solución básica Nº 1
0),,X,(X
10 X25X
15 X53X
:a sujeto
S0S0X3X5ZMaximizar
2121
221
121
2121
≥=++=++
+++=
SS
S
S
0),,X,(X
10)(1)(0(0)25(0)
15 )0( )(1(0)53(0)
:a sujeto
)(0)(0(0)3)0(5ZMaximizar
2121
21
21
21
≥=+++=+++
+++=
SS
SS
SS
SS
X1 = 0 X2 = 0 S1 = 15 S2 = 10
•3.1 Soluciones Básicas En Forma Matricial
3.1 Soluciones Básicas En Forma Matricial
Solución Básica Nº X1
X2
S1
S2
Factible
Valor de Z
1 0 0 15 10 Si 0
2 0 3 0 4 Si 9
3 0 5 -10 0 No –
4 5 0 0 -15 No –
5 2 0 9 0 Si 10
6 20/19 45/19 0 0 Si 235/19 = 12.4
•
0),,X,(X
10 X25X
15 X53X
:a sujeto
X3X5ZMaximizar
Estándar Modelo
2121
221
121
21
≥=++=++
+=
SS
S
S
•
Variables no básicas
Variables básicas
12
−=
−=
=
=
−
15
5
10
15
13/5
03/1
10
15
15
03
10
15
15
03
1
2
1
2
1
S
X
S
X
Solución básica Nº 4
0),,X,(X
10 X25X
15 X53X
:a sujeto
S0S0X3X5ZMaximizar
2121
221
121
2121
≥=++=++
+++=
SS
S
S
S1 = 0 X2 = 0S2 = -15 X1 = 5No factible!
0),,X,(X
10)(1 )0(0)0(25X
15 )(0)0(1(0)53X
:a sujeto
)0() 0(0(0)3X5ZMaximizar
2121
21
21
21
≥=+++
=+++
+++=
SS
S
S
S
3.1 Soluciones Básicas En Forma Matricial
Obsérvese que, en cada caso, lasolución básica se obtieneinvirtiendo la base ypremultiplicándola por el vectorb, o sea que una solución básicaes de la forma ,
donde B es la matriz baseasociada a la solucióncorrespondiente.
bB 1−
3.1 Método SIMPLEX en Forma Matricial El problema general de P.L. dado en su forma estándar por el conjunto de ecuaciones, puede tomarse de la siguiente manera:
[ ] [ ]RCCC
X
X
XRBA MLM B
R
B
=
==
Bm×m = Matriz base de orden m (se forma escogiendo m columnas de la matriz A, correspondientes a
las variables básicas)
Rm×(n-m) = Matriz restante, formada por las (n-m) columnas de la matriz A, asociadas a las variables no
básicas.
1mBX×
= Vector de las variables básicas.
1X
×m)-(nR = Vector de las variables no básicas.
m×1BC = Vector de los coeficientes de las variables básicas en la función objetivo.
)(1R mn−×C = Vector de los coeficientes de las variables no básicas en la función objetivo.
13
Por la tanto el modelo de P.L. quedaría expresado así:
0X
bRXBX
XCXC
≥=+
+=
:a sujeto
Z(MIN) MAX
RB
RRBB
Una solución básica es aquella en la que 0=RX , y, por lo tanto, bBX 1−=B . Una solución básica factible es aquella solución básica bBX 1−=B , tal que.
0X ≥B
3.1 Método SIMPLEX en Matricial
MÉTODO SIMPLEX MATRICIAL
Inicie con una solución básica factible inmediata
¿Se cumple el CRITERIO DE PARADA?
Escoger la variable que va a entrar a la base (CRITERIO DE ENTRADA )
Determinar la variable que va a salir de la base (CRITERIO DE SALIDA )
Realizar las operaciones fila elementales para cambiar de base y obtener una nueva
solución básica factible
No
La solución básica factible actual es una SOLUCIÓN
ÓPTIMA
FIN
Si
14
1. Llevar el modelo a la forma estándar.
2. Determinar los parámetros de punto de partida:
Bm×m Matriz base de orden m (se forma escogiendo m columnas de
la matriz A, correspondientes a las variables básicas)
Rm×(n-m) Matriz restante, formada por las (n-m) columnas de la matriz A,
asociadas a las variables no básicas.
1mBX×
Vector de las variables básicas.
1X
×m)-(nR Vector de las variables no básicas.
m×1BC Vector de los coeficientes de las variables básicas en la función
objetivo.
)(1R mn−×C
Vector de los coeficientes de las variables no básicas en la
función objetivo.
MÉTODO SIMPLEX MATRICIAL
3. Calcule la solución básica inicial, donde:
bBX 1−=B BBZ XC=
4. Calcule el valor de jZ - jC para las variables no básicas
jBjZ YC= y jj aBY 1−=
RBY 1−=
donde ja son las columnas de A que forman la matriz R.
MÉTODO SIMPLEX MATRICIAL
15
MÉTODO SIMPLEX MATRICIAL
5. Revise el Criterio de Optimalidad:
Caso Maximización: si todos los jj CZ − calculados en el literal
anterior son mayores o iguales que cero, dicha solución es la solución óptima: Caso Minimización: si todos los jj CZ − calculados en el literal
anterior son menores o iguales que cero, dicha solución es la solución óptima: Si se cumple el criterio finalice, de lo contrario continúe el
paso 6.
0≥− jj CZ
0≤− jj CZ
6. Realice el proceso de primer cambio de base
a) Criterio de entrada:
Caso Maximización: sea el “más negativo”.
Caso de Minimización: sea el “más positivo”.
)( jj CZ −
)( jj CZ −
b) Criterio de salida
Sale de la base aquella variable cuyo cociente θ sea el minimo, donde:
0 ; >= sksk
s yy
xθ
MÉTODO SIMPLEX MATRICIAL
16
MÉTODO SIMPLEX MATRICIAL 6. Realice el proceso de primer cambio de base
b) Criterio de salida:
Recuérdese que RBB YXXX −= , en este caso:
−
=
= i
B
x
d
c
b
aX
Columna asociada a iX , variable a entrar a la base.
Luego: { }b/d , /c, amínd
b
c
amín =
=θ
Por lo tanto sale de la base asociada al θ mínimo
7. Actualizar la información con la nueva solución y repita todo el proceso, hasta llegar a la solución óptima.
Ejemplo:
0)X,(X
10X25X
15X53X
:a sujeto
X3X5ZMaximizar
Original Modelo
21
21
21
21
≥≤+≤+
+=
MÉTODO SIMPLEX MATRICIAL
17
Aplicación Del Método Simplex En Forma Matricial
1. Llevar el modelo a la forma estándar.
0)X,(X
10X25X
15X53X
:a sujeto
X3X5ZMaximizar
Original Modelo
21
21
21
21
≥≤+≤+
+=
0),,X,(X
10 X25X
15 X53X
:a sujeto
X3X5ZMaximizar
Estándar Modelo
2121
221
121
21
≥=++=++
+=
SS
S
S
Aplicación Del Método Simplex En Forma Matricial
2. Determinar los parámetros de punto de partida:
Bm×m Matriz base de orden m (se forma escogiendo m columnas de
la matriz A, correspondientes a las variables básicas)
Rm×(n-m) Matriz restante, formada por las (n-m) columnas de la matriz A,
asociadas a las variables no básicas.
1mBX×
Vector de las variables básicas.
1X
×m)-(nR Vector de las variables no básicas.
m×1BC Vector de los coeficientes de las variables básicas en la función
objetivo.
)(1R mn−×C
Vector de los coeficientes de las variables no básicas en la
función objetivo.
[ ] [ ]
=
=
=
===
=
2
1
2
1 ; ;25
53 ;
10
15 ;35 ;00 ;
10
01
X
X
S
SRBRB XXRbCCB
S1 S2 X1 X2
18
Aplicación Del Método Simplex En Forma Matricial
3. Calculo de la solución básica inicial bBX 1−=B
0),,X,(X
10 X25X
15 X53X
:a sujeto
X3X5ZMaximizar
2121
221
121
21
≥=++=++
+=
SS
S
S ;10
15 ;
10
01
=
= bB
Entonces:
=
==
−−
10
15
10
15
10
011
1bBX B
0== BBZ XC
BX es la solución básica factible inicial.
Aplicación Del Método Simplex En Forma Matricial
4. Calculo de )( jj CZ − para las variables no básicas.
jBjBjZ aBCYC 1−== , donde ja son las columnas de A que forman
la matriz R.
=
== −
25
53
25
53
10
011RBY (columnas de la matriz Y)
[ ][ ][ ][ ] 02500
05300
22
11
===
===T
B
TB
Z
Z
YC
YC
330
550
22
11
−=−=−⇒
−=−=−⇒
CZ
CZ
19
Aplicación Del Método Simplex En Forma Matricial
5. Revisión del criterio de optimalidad
Caso Maximización: si todos los jj CZ − calculados en el literal
anterior son mayores o iguales que cero, dicha solución es la solución óptima:
Como
330
550
22
11
−=−=−⇒
−=−=−⇒
CZ
CZ
Entonces ésta no es la solución óptima y se debe continuar con el paso 6
0≤− jj CZ
Aplicación Del Método Simplex En Forma Matricial
6. Primer Cambio de Base:
a) Criterio de entrada: )( jj CZ − sea el “más negativo”.
=
== −
25
53
25
53
10
011RBY (columnas de la matriz Y)
[ ][ ][ ][ ] 02500
05300
22
11
===
===T
B
TB
Z
Z
YC
YC
330
550
22
11
−=−=−⇒
−=−=−⇒
CZ
CZENTRA A LA BASE LA VARIABLE x1
20
Aplicación Del Método Simplex En Forma Matricial
6. Primer Cambio de base
b. Criterio de salida:
Recuérdese que RBB YXXX −= , en este caso:
−
=
=
2
1
2
1
25
53
10
15
x
x
s
sBX
Columna asociada a 1X , variable a entrar a la base.
Luego: { } 22 , 5mín5
10,
315
mín ==
=θ
Por lo tanto sale de la base la variable S2.
Aplicación Del Método Simplex En Forma Matricial 7. Actualización de la información con la solución básica
factible actual:
Actualmente, las nuevas condiciones son:
[ ] [ ]
=
=
=
===
=
2
2
1
1 ; ;21
50 ;
10
15 ;30 ;50 ;
50
31
X
S
X
SRBRB XXRbCCB
s1 x1 s2 x2
Entonces, la solución actual es:
=
−=
==
−−
2
9
10
15
510
531
10
15
50
311
bBX 1B
10== BBZ XC
21
Aplicación Del Método Simplex En Forma Matricial
Segundo Cambio de Base: (si se necesita) Criterio de entrada: )( jj CZ − sea el “más negativo”.
jBjBjZ aBCYC 1−== , donde ja son las columnas de A que forman la
matriz R.
−=
−== −
5/25/1
5/195/3
21
50
5/10
5/311RBY (Columnas de Y)
S2 X2
[ ][ ][ ][ ] 25/25/1950
15/15/350
22
11
===
=−==T
B
TB
Z
Z
YC
YC
10111 =−=−⇒ CZ
13222 −=−=−⇒ CZ , ENTRA A LA BASE LA VARIABLE X2 (la única cuyo Zj – Cj es negativo)
Aplicación Del Método Simplex En Forma Matricial
Criterio de salida:
Recuérdese que RBB YXXX −= , en este caso:
−−
=
=
2
2
1
1
5/25/1
5/195/3
2
9
x
s
x
sBX
Columna asociada a 2X , variable a entrar a la base.
Luego: 1945
5 ,1945
mín =
=θ
Por lo tanto sale de la base la variable S1.
22
Aplicación Del Método Simplex En Forma Matricial � Solución básica factible actual:
Actualmente, las nuevas condiciones son:
[ ] [ ]
=
=
===
=
1
2 ; ;01
10 ;
10
15 ;00 ;53 ;
52
35
X
XRBRB XXRbCCB
x2 x1 s2 s1
Entonces, la solución actual es:
=
−−
=
==
−−
19/20
19/45
10
15
19/519/2
19/319/5
10
15
52
351
1bBXB
37.1219/235Z ≅== BB XC
Aplicación Del Método Simplex En Forma Matricial
Tercer Cambio de Base: (si se necesita)
Criterio de entrada: )( jj CZ − sea el “más negativo”.
jBjBjZ aBCYC 1−== , donde ja son las columnas de A que forman la
matriz R.
−−
=
−−
== −
19/219/5
19/519/3
01
10
19/519/2
19/319/51RBY (columnas de Y)
[ ][ ][ ][ ] 19/519/219/553
19/1619/519/353
22
11
=−==
=−==T
B
TB
Z
Z
YC
YC
019/5 019/5
19/16019/16
22
11 ≥
=−=−⇒
=−=−⇒
CZ
CZ, SE CUMPLE EL CRITERIO DE PARADA Y
OPTIMALIDAD.
23
FUENTES:
1. Vidal, Carlos Julio (2005). Introducción A LaModelación Matemática Y Optimización.
2. Bravo, Juan José. Notas de Clase: MétodoSimplex.
3. Ramírez, Luis Felipe (2009). Notas de Clase:Método Simplex.
4. Toro, Héctor Hernán. Notas de Clase. MétodoSimplex
top related