Metodo Dual Simplex

INSTITUTO
POLITECNICO
NACIONAL
ESCUELA SUPERIOR
INGENIERIA Y
ARQUITECTURA
UNIDAD ZACATENCO
INGENIERIA EN SISTEMAS
METODO DUAL SIMPLEX
PROFESORA: ANGELICA MENDOZA EURASMO
ALUMNOS: AGUILAR GUITIERREZ EDGAR
MENDOZA CRUZ GUSTAVO
VENTURA CERRITEO
FRANCISCO
GRUPO: 6CV14
FECHA DE
ENTREGA: 21/ABRIL/2016
NDICE
Pg.
Mtodo Dual Simplex..

.................3
Relaciones Primal-Dual.
.....................3
Tabla de TUCKER.
............................5
Por qu se plantea el programa dual?
6
Qu significado tiene su solucin?.
.......7
La solucin del dual se puede obtener desde el
primal?....7
Teorema de
Existencia.
..7
Teorema de
Dualidad
..8
Teorema de Holgura
complementaria.8
2
Relaciones entre las soluciones del programa

primal y del programa
dual
..8
Interpretacin Econmica de las variables
Duales.8
Ejercicio paso a
paso
9
Aplicacin en la Ingeniera
Civil..13
Conclusin
.14
Bibliografa
.14
Mtodo Dual Simplex

Este mtodo se aplica a problemas ptimos pero infactibles.
En este caso, las restricciones se expresan en forma cannica
(restricciones).
La funcin objetivo puede estar en la forma de maximizacin
o de minimizacin. Despus de agregar las variables de
holgura y de poner el problema en la tabla, si algn elemento
de la parte derecha es negativo y si la condicin de optimidad
est satisfecha, el problema puede resolverse por el mtodo
dual simplex. Note que un elemento negativo en el lado
3
derecho significa que el problema comienza ptimo pero

infactible como se requiere en el mtodo dual simplex. En la
iteracin donde la solucin bsica llega a ser factible esta ser
la solucin ptima del problema.
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. Tome 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.
Relaciones Primal-Dual
Asociado a cada problema lineal existe otro problema
de programacin lineal denominado problema dual
(PD) , que posee importantes propiedades y relaciones
notables con respecto al problema lineal original,
problema que para diferencia del dual se denomina
entonces como problema primal (PP).
Las relaciones las podemos enumerar como siguen:
a) El problema dual tiene tantas variables como
restricciones tiene el programa primal.
4
b) El problema dual tiene tantas restricciones

como variables tiene el programa primal
c) Los coeficientes de la funcin objetivo del
problema dual son los trminos independientes
de las restricciones o RHS del programa primal.
d) Los trminos independientes de las
restricciones o RHS del dual son los coeficientes
de la funcin objetivo del problema primal.
e) La matriz de coeficientes tcnicos del problema
dual es la traspuesta de la matriz tcnica del
problema primal.
f) El sentido de las desigualdades de las
restricciones del problema dual y el signo de las
variables del mismo problema, dependen de la
forma de que tenga el signo de las variables del
problema primal y del sentido de las restricciones
del mismo problema. (tabla de TUCKER)
g) Si el programa primal es un problema de
maximizacin, el programa dual es un problema
de minimizacin.
h) El problema dual de un problema dual es el
programa primal original.
TABLA DE TUCKER
RESTRICCIONES
><
VARIABLES
VARIABLES
><
RESTRICCIONES
Los problemas duales simtricos son los que se

obtienen de un problema primal en forma cannica y
normalizada, es decir, cuando llevan asociadas
desigualdades de la forma mayor o igual en los
problemas de minimizacin, y desigualdades menores
o igual para los problemas de maximizacin. Es decir,
si el problema original es de la siguiente forma:
Mx Z(x) = ct x
s.a:
Axb
x0
El problema dual ( dual simtrico ) es :
Mn G() = b
s.a:
Ac
Los restantes tipos de combinaciones de

problemas, se conocen con el nombre de duales
asimtricos. Como por ejemplo:
Mx Z(x) = ct x
s.a:
6
Ax=b
x0
El problema dual ( dual asimtrico ) es :
Mn G() = b
s.a:
Ac
>< 0, es decir, variables libres.
Por qu se plantea el programa dual?

Por una parte permite resolver problemas lineales
donde el nmero de restricciones es mayor que el
nmero de variables. Gracias a los teoremas que
expondremos a continuacin la solucin de unos de
los problemas (primal o dual) nos proporciona de
forma automtica la solucin del otro programa.
Qu significado tiene su solucin?

La
dualidad
permite
realizar
importantes
interpretaciones econmicas de los problemas de
programacin lineal.
La solucin del dual se puede obtener

desde el primal?
La dualidad permite generar mtodos como el mtodo
dual del simplex de gran importancia en el anlisis de
pos optimizacin y en la programacin lineal
paramtrica.
7
Teorema de existencia
La condicin necesaria y suficiente para que un
problema de programacin lineal tenga solucin es
que, tanto el conjunto de oportunidades del primal (S)
como en conjunto de oportunidades del dual (S) no
sean vacos, es decir, que ambos problemas sean
factibles.
( x* , * ) S S
Corolario del teorema de existencia
Una vez analizadas las condiciones que han de
cumplirse para que exista solucin ptima, vamos
a ver los diferentes casos posibles:
a) S S Ambos problemas tienen
solucin ptima finita.
b) S = S El programa primal es
infactible, y el programa dual es no acotado.
c) S S = El programa dual es infactible,
y el programa primal es no acotado.
d) S = S = Ambos problemas son
infactibles.
Teorema de la Dualidad
La condicin necesaria y suficiente para que exista
solucin ptima del primal ( x* ), es que exista una
solucin ptima para el dual ( * ) y que valor de la
funcin objetivo de ambos programas sea igual, es
decir Z(x* ) = G(* ).
x* * / Z(x* ) = G(* )
Teorema del Holgura complementaria

8
La condicin necesaria y suficiente para que (x* , * )

sean soluciones ptimas del programa primal y dual,
es que satisfagan las condiciones de holgura
complementaria:
( c - * A ) x* = 0
* ( b - A x* ) = 0
Relaciones entre las soluciones del

programa primal y del programa dual.
Tanto el programa primal como el programa dual son
dos formas de abordar el mismo problema, y por lo
tanto, si tienen solucin, tienen la misma solucin.
Entonces, cabe preguntarse cul es la relacin entre
las soluciones de ambos problemas.
Interpretacin econmica de las variables

duales
El significado de las variables duales es el mismo que
en el caso de los multiplicadores de Lagrange, es decir
miden la sensibilidad de la funcin objetivo respecto a
cambios
(infinitesimales)
de
los
trminos
independientes de cada restriccin.
Ejercicio Paso a Paso

F.O.
Min. Z = 4X1 + 12X2 + 18X3
S.A.
X1 + 3X3 3
2X2 + 2X3 5
X1, X2, X3 0
9
PASO 1: Convertir el problema de minimizacin en

uno de maximizacin.
La funcin objetivo se
multiplica por -1
F.O.
Max. Z = - 4X1 - 12X2 - 18X3
Las restricciones se multiplican por -1
S.A.
X1 - 3X3 -3
2X2 - 2X3 -5
X1, X2, X3 0
PASO 2: Se
ecuaciones.
convierten
las
inecuaciones
en
F.O.
Z + 4X1 + 12X2 + 18X3 = 0
S.A.
- X1- 3X3 + S1 = -3
2X2 - 2X3 + S2 = -5
PASO 3: Se determinan las variables bsicas y no
bsicas.
Bsicas: S1 y S2
No Bsicas: X1, X2 y X3
PASO 4: Elaborar la tabla inicial del simplex.
Variab
le
Variab
les
10
Soluci
n
Bsica X1
X2
X3
S1
S2
S1
-1
-3
-3
S2
-2
-2
-5
12
18
PASO 5: Determinar la variable que sale (fila pivote)

Es el nmero ms negativo de la solucin de las
restricciones = fila de S2
Varia
ble
Bsic
a
Variab
les
Soluci
n
X1
X2
X3
S1
S2
S1
-1
-3
-3
S2
-2
-2
-5
12
18
PASO 6: Determinar la variable que entra (columna

pivote).
Razn = Coeficiente de Z / coeficiente fila pivote.
Razn Mayor = Columna X2 (-12 / 2)
Varia
ble
Variab
les
11
Soluci
n
Bsic
a
X1
X2
X3
S1
S2
S1
-1
-3
-3
S2
-2
-2
-5
12
18
Razn -
-6
-9
PASO 7: Elaborar la nueva tabla del simplex.

A) Nueva fila pivote = Fila pivote / elemento
pivote
Fila Pivote
-2
-2
-5
-2
-2
-2
-2
-2
-2 Elemento Pivote
0 -0,5 2,5 Nueva Fila Pivote
B) Nuevas filas = fila anterior - coeficiente de la

columna pivote x nueva fila pivote
Nueva Fila (S1)

-1
0 -3
-3 Fila Anterior
0 Coeficiente
0 1
0 -0,5 2,5 Nueva Fila Pivote
0
X
-1
0 -3
-3 Nueva Fila
Nueva Fila (Z)

12
4 12
18 0
12 12
12 12 12 12
0 1
4 0
1
6
0
0
-0,5 2,5
6 -30
Nueva Tabla del Simplex

Variab
le
Bsica
Variab
les
Soluci
n
X1
X2
X3
S1
S2
S1
-1
-3
-3
X2
-1
2,5
-30
-2
Razn -4
Se realizan nuevamente los pasos

obteniendo como solucin final:
Variabl
e
Bsica
del
Variabl
es
al
Soluci
n
X1
X2
X3
S1
S2
X3
0,33
-0,33
X2
-0,33
0,33
-0,5
1,5
-36
13
NOTA: No hay ms iteraciones cuando no existan

soluciones con coeficientes negativos.
R\ El valor mnimo se alcanza para un X 2 = 3/2 y X3 =
1, para un Z = 36
Aplicacin en la Ingeniera Civil

En nuestro entorno muchas cosas se piensan sobre la
ingeniera en sistemas, como muchos o la mayora de
mtodos, tienen como fin el mismo, la aplicacin de
modelos de optimizacin, ya sea para empresas
productivas o para otro tipo de medios.
De esta forma la importancia de la ingeniera en
sistemas, programacin lineal y en nuestro caso, el
mtodo dual simplex, no solo radica en el
procedimiento matemtico, sino en la herramienta
financiera que sirve como soporte en la toma de
decisiones de cualquier organizacin.
Conclusin
Aunque es un mtodo muy fcil, se hace enredado
encontrar los resultados de las incgnitas ya que para
llegar a ellos se necesita de la realizacin de tablas o
matrices, y si no se tiene el cuidado y no se le presta
la atencin al proceso, se podra obtener un resultado
incorrecto. Pero si se tiene cuidado en su realizacin
no se tendr inconveniente en maximizar o minimizar
cualquier problema por el mtodo Dual Simplex.
Bibliografa
14
2012 Mtodo Dual Simplex

http://oromeroio.blogcindario.com/ficheros/MetodoSim
plexDual.pdf
2016 UV. Blasco Ibez Dualidad en Programacin
Lineal http://www.uv.es/~sala/Clase11.pdf
15

Metodo Dual Simplex

Cargado por

Copyright:

Formatos disponibles

Metodo Dual Simplex

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Metodo Dual Simplex

Cargado por

Copyright:

Formatos disponibles

INSTITUTO

Mtodo Dual Simplex..

Relaciones entre las soluciones del programa

Mtodo Dual Simplex

derecho significa que el problema comienza ptimo pero

b) El problema dual tiene tantas restricciones

Los problemas duales simtricos son los que se

El problema dual ( dual simtrico ) es :

Los restantes tipos de combinaciones de

>< 0, es decir, variables libres.

Por qu se plantea el programa dual?

Qu significado tiene su solucin?

La solucin del dual se puede obtener

Teorema del Holgura complementaria

La condicin necesaria y suficiente para que (x* , * )

Relaciones entre las soluciones del

Interpretacin econmica de las variables

Ejercicio Paso a Paso

PASO 1: Convertir el problema de minimizacin en

PASO 5: Determinar la variable que sale (fila pivote)

PASO 6: Determinar la variable que entra (columna

PASO 7: Elaborar la nueva tabla del simplex.

0 -0,5 2,5 Nueva Fila Pivote

B) Nuevas filas = fila anterior - coeficiente de la

Nueva Fila (S1)

0 -0,5 2,5 Nueva Fila Pivote

Nueva Fila (Z)

Nueva Tabla del Simplex

Se realizan nuevamente los pasos

NOTA: No hay ms iteraciones cuando no existan

Aplicacin en la Ingeniera Civil

2012 Mtodo Dual Simplex

También podría gustarte