Método Simplex de Dos Fases 1
Método Simplex de Dos Fases 1
Método Simplex de Dos Fases 1
PROBLEMAS LINEALES
FREDY MARTINEZ
(DOCENTE)
UNIVERSIDAD DE CORDOBA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS Y TELECOMUNICACIONES
MONTERIA - CORDOBA
2015
INTRODUCCION
El presente trabajo tiene como objetivo, dar a conocer la aplicacin del Mtodo
Simplex de dos fases y formas Primal y Dual en los problemas lineales.
OBJETIVOS
Objetivo general:
1. Comparar la factibilidad de usar el mtodo simplex de dos fase y primal y
dual.
2. Definir que son los mtodos simplex de dos fases, primal y dual.
3. Formular problemas relacionados con cada uno de los mtodos.
Objetivo Especfico:
Analizar, a travs del Mtodo simplex de dos fase, dual y primal, problemas de
optimizacin restringida considerando la importancia de estos para la toma de
decisiones y manejos de recursos.
Este es otra variante del simplex que se aplica para resolver modelos de PL que
requieren una matriz unitaria de base artificial para poder iniciar el algoritmo.
El nombre indica que consiste de dos fases: En la 1, se reducen las artificiales
Wi a cero y en tal caso se optimiza en la 2, o bien, se concluye que no hay
solucin factible para el problema porque W i es diferente de cero en fase 1, y
por lo tanto no es necesaria la fase2.
Para la fase 1
Esta primera fase es muy similar al mtodo Simplex, con la excepcin de la
construccin de la primera tabla, adems de la necesidad de estudiar el
resultado obtenido para determinar si se desarrolla la segunda fase.
Construccin de la primera tabla:
Se elabora de manera anloga a la tabla inicial del mtodo Simplex, pero con
algunas diferencias.
En esta primera fase se resuelve un problema auxiliar (la minimizacin de la
suma de las variables artificiales) con una funcin objetivo auxiliar. Por lo tanto
en la primera fila de la tabla, donde se muestran los coeficientes de las
variables de la funcin objetivo, aparecern todos los trminos a cero excepto
los coeficientes de variables artificiales. El valor de cada uno de estos
coeficientes es "-1" debido a que se est minimizando la suma de dichas
variables (recuerde que minimizar Z' es igual que maximizar (-1) Z').
La otra diferencia para la primera tabla radica en que ahora s es necesario
calcular la fila Z (o fila indicadora).
Tabla
C0
C1
C2
...
Cn-k
...
Cn
Base
Cb
P0
P1
P2
...
Pn-k
...
Pn
P1
Cb1
b1
a11
a12
...
a1n-k
...
a1n
P2
Cb2
b2
a21
a22
...
a2n-k
...
a2n
...
...
...
...
...
...
...
...
...
Pm
Cbm
bm
am1
am2
...
amn-k
...
amn
Z0
Z1
Z2
...
Zn-k
...
Zn
FUNCION OBJETIVO A
OPTIMIZAR
Sujeto a:
X1 + 0.8X2 100
X1 + 2X2 200
X1, X2 0
Figura 1.
RESTRICCIONESDEL PROBLEMA
DE PROGRAMACION LINEAL (PPL).
XB
CB
Cj
b
0
X1
0
X2
0
H1
0
H2
1
A
1
A2
Ratio
A1
100
A2
200
Zj
Cj-Zj
0.
-1
0
8
1
2
0
-1
2
2.
-1
-1
8
-2
1
1
2.
8
Tabla del Simplex
0
1
1
1
100/0.
8
200/2
1.
Iteracin 1:
Una vez que hemos llenado el tabloide o tabla del simplex procedemos a
realizar el proceso de optimizacin (1ra. Fase) para lo cual se debe:
Ahora debemos hacer cero el valor 0.8 encima del valor pivote para ello
multiplicamos la fila 4 por -0.4 y el resultado se lo sumamos a la fila 3.
(VER TABLA SIMPLEX 2).
Ahora calculamos los Zj en cada columna de las variables del tabloide
(VER TABLA SIMPLEX 2).
Calculamos los Cj Zj y los resultados (VER TABLA SIMPLEX 2).
XB
CB
Cj
b
0
X1
0
X2
0
H1
0
H2
1
A
A1
20
0.
6
-1
0.4
X2
100
1
A2
Ratio
Zj
Cj-Zj
0.
1
0
-0.5
5
0.
0
-1
0.4
6
0
1
-0.4
0.
6
Tabla del Simplex
0
1
0
0.
4
0.
5
0.4
0.4
33.33
200
2.
Iteracin 2:
Observamos la sexta fila y buscamos los Cj Zj < 0 y podemos ver que
hay dos valores -0.6 y -0.4, seleccionando al ms negativo o sea -0.6
correspondiente a la variable X1, que ser la variable que entrar a ser
bsica.
Una vez seleccionada X1 procederemos obtener los cocientes de cada b
entre los coeficientes de X1. 200.6=33.33; 1000.5=200, el cociente
ms pequeo es 33.33, esto indica que la variable bsica que saldr es
A1.
Ahora debemos hacer cero el valor 0.5 debajo del valor pivote para ello
multiplicamos la fila 3 por -0.5 y a la fila 4 por 0.6. y sumamos dichas
filas (Ver Tabla del Simplex 3)
0
X1
0
X2
0
H1
0
H2
1
A1
1
A2
0.6
6
0.1
6
XB
CB
A1
33.3
3
1.66
0.6
6
1.6
6
X2
83.3
3
0.83
0.8
3
0
0.8
3
0
Zj
Cj-Zj
Rati
o
0
1
XB
X1
CB
80
X2
124
Cj
80
X1
1
12
4
X2
0
b
33.3
3
83.3
3
H1
-1.66
H2
0.66
Ratio
0.83
-0.83
83.33/0.8
3
80
Zj
Cj-Zj
12
4
0
29.88
29.88
50.12
50.12
CONDICION DE FACTIBILIDAD.
La variable que sale es la variable bsica que tiene el valor ms negativo (los
empates se rompen arbitrariamente si todas las variables bsicas son no
negativas, el proceso termina y esta ltima tabla es la solucin ptima
factible).
CONDICION DE OPTIMIDAD.
La variable que entra se elige entre las variables no bsicas como sigue. Se
toma los cocientes de los coeficientes de la funcin objetivo entre los
coeficientes correspondientes a la ecuacin asociada a la variable que sale.
Ignore los cocientes asociados a denominadores positivos o cero. La variable
que entra es aquella con el cociente ms pequeo si el problema es de
minimizar o el valor absoluto ms pequeo si el problema es de maximizacin
(rompa los empates arbitrariamente). Si los denominadores son ceros o
positivos el problema no tiene ninguna solucin factible.
EJEMPLO
Consideramos el siguiente modelo de Programacin Lineal:
Min 315A + 110B + 50C
s.a 15A + 2B + C 200
7,5A + 3B + C 150
5A + 2B + C 120
A, B, C0
Paso 1: Se lleva el modelo a su forma estndar. En nuestro ejemplo esto se
logra agregando variables de exceso en cada una de las restricciones (3
primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las
restricciones por -1 de modo de disponer una solucin bsica inicial (infactible)
en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente
tabla inicial.
A
-15
B
-2
C
-1
S1
1
S2
0
S3
0
-7,5
-3
-1
-5
-2
-1
315
11
0
50
200
150
120
0
B
2/1
5
C
1/1
5
0
0
-2
-4/3
-1/2
68
-2/3
29
S1
1/1
5
-1/2
-1/3
S2
0
S3
0
1
0
0
1
21
40/3
-50
160/3
4.200
B
0
C
0
0
0
0
1
0
0
0
1
0
S1
1/1
0
1/4
0
4
S2
0
S3
1/1
0
-1
2
10
3/4
-3
36
8
10
60
6.620
La solucin ptima es A=8, B=10, C=60 (marcado en azul) con valor ptimo V
(P)=6.620(marcado en rojo - se obtiene con signo cambiado). Tambin es
interesante notar que los costos reducidos de las variables artificiales S1, S2 y
S3 (marcado en amarillo).
CONCLUSION
Por consiguiente se puede concluir que:
El mtodo simplex de dos fases es una variante del algoritmo simple
que es usado como alternativa al Mtodo de la gran M.
El mtodo simplex de dos fases es considerado un problema auxiliar.
Si el mtodo simplex de dos fases tiene un valor ptimo de cero puede ir
a la fase II.
El mtodo simplex primales y duales se encuentran ligados por una
serie de relaciones que puede ser considerado de gran utilidad para la
resolucin de problemas que parecen no factibles o que no pueden ser
resueltos mediante un mtodo en particular.
Para toda restriccin del primal hay una variable dual.
Para toda variable del primal hay una restriccin dual.
Los coeficientes de las restricciones de una variable primal, forman los
coeficientes del primer miembro de la restriccin dual correspondiente.
BIBLIOGRAFIA
1. http://www.phpsimplex.com/teoria_metodo_simplex.htm
2. https://jrvargas.files.wordpress.com/2008/08/ejemplo-mc3a9todosimplex-de-las-dos-fases.pdf
3.
http://prof.usb.ve/nbaquero/metodo%20simplex.doc
4. http://fceioperativa.unse.edu.ar/asignaturas/Modelos_Matematicos_I/at/si
mplexDual.pdf
5. http://www.investigaciondeoperaciones.net/metodo_simplex_dual.html
6. http://oromeroio.blogcindario.com/ficheros/MetodoSimplexDual.pdf