granulometria

EL MÉTODO
DUAL-SIMPLEX
OBJETIVO: PRESENTAR LA ESTRATEGIA
DEL MÉTODO DUAL-SIMPLEX PARA LA
SOLUCIÓN DE MODELOS DE
PROGRAMACIÓN LINEAL
TEMAS:
EL MÉTODO SIMPLEX
ADICIÓN DE UNA VARIABLE AL MODELO
ADICIÓN DE UNA RESTRICCIÓN AL MODELO
CONCLUSIONES
03/07/2007 05:48 p.m.

1

EL MÉTODO DUAL-SIMPLEX
De manera general se puede decir que la
estrategia del método Dual-Simplex consiste en lasolución de un modelo de Programación Lineal
desde el punto de vista Dual, pero trabajando
desde la tabla Primal del problema.
Se busca tener una solución Dual factible, hasta
alcanzar condiciones optimas en el Dual, aunque
desde el punto Primal se tienen soluciones con
condiciones óptimas que son no factibles.
03/07/2007 05:48 p.m.

2

EL MÉTODO DUAL-SIMPLEX
PRELIMINARES
El renglóncero de la tabla Primal tiene todos sus
coeficientes como positivos o ceros. (Dual factible).
Esta es una condición necesaria para la aplicación
directa del método.
En este método todas las restricciones se escriben
en la forma menor o igual que ( ≤ ) de tal forma
que se pueda tener el conjunto correcto de
variables básicas Duales, por la adición de
variables de holgura positivas.03/07/2007 05:48 p.m.

3

EL MÉTODO DUAL-SIMPLEX
PRELIMINARES
Se tiene una solución básica factible con respecto
al Dual, alguno o algunos coeficientes en el Lado
Derecho tendrán un coeficiente negativo por la
reexpresión de las restricciones.
Se siguen las condiciones del método y se
actualiza la tabla de manera habitual; nuevamente
manteniendo una solución Dual factible hasta que
seaóptima desde el punto de vista Dual,
trabajando en la tabla Primal.
03/07/2007 05:48 p.m.

4

EL MÉTODO DUAL-SIMPLEX
EL MÉTODO DUAL-SIMPLEX
INICIALIZACIÓN
Encontrar una solución Dual básica factible al problema
en la tabla Primal; todos los coeficientes en el renglón
cero son positivos o ceros.
PASO PRINCIPAL
1. Si todos los elementos en el Lado Derecho son
mayores o iguales a cerodetenerse, la solución actual
es óptima Dual (y también Primal). Si no, seleccione el
elemento más negativo del Lado Derecho de la tabla
simplex y defina dicha posición como el renglón pivote.
03/07/2007 05:48 p.m.

5

EL MÉTODO DUAL-SIMPLEX
EL MÉTODO DUAL-SIMPLEX
PASO PRINCIPAL (continuación)
2. Examine los elementos en el renglón pivote (excepto el
elemento en el Lado Derecho), si todosellos son mayores
o iguales a cero entonces la solución es no acotada en el
dual (e infactible Primal). En caso contrario y sólo con los
elementos negativos del renglón pivote, divida de forma
correspondiente cada elemento no básico en el
RENGLÓN CERO entre su respectivo elemento en el
renglón pivote y seleccione el cociente de menor valor
absoluto, defina dicha posición como la columnapivote.

03/07/2007 05:48 p.m.

6

EL MÉTODO DUAL-SIMPLEX
EL MÉTODO DUAL-SIMPLEX
PASO PRINCIPAL (continuación)
3. El renglón pivote indica la variable saliente y la columna
pivote indica la variable entrante. A partir de operaciones
básicas entre renglones, esto es, multiplicación por un
escalar y/o suma de renglones; con base en el pivote,
actualice la tabla hasta obtener el sistemaequivalente con
el nuevo conjunto de variables básicas. Repita el PASO
PRINCIPAL.

03/07/2007 05:48 p.m.

7

EL MÉTODO DUAL-SIMPLEX
7.1-3 Resolver por el método DualSimplex
min z =
sujeta a

03/07/2007 05:48 p.m.

7 x1 +
2 x1 +
8 x1 +
3 x1 +
x1 ,

2 x2 + 5 x3 + 4 x4
4 x2 + 7 x3 + x4
4 x2 + 6 x3 + 4 x4
8 x2 + x3 + 4 x4
x2 , x3 ,
x4

≥5
≥8
≥4
≥0

8

EL MÉTODODUAL-SIMPLEX
Expresando las restricciones como ≤, y en
forma para maximizar
max -z = -7 x1 sujeta a
-2 x1 -8 x1 -3 x1 x1 ,

03/07/2007 05:48 p.m.

2 x2 - 5 x3 - 4 x4
4 x2 - 7 x3 - x4
4 x2 - 6 x3 - 4 x4
8 x2 - x3 - 4 x4
x2 , x3 ,
x4

≤ -5
≤ -8
≤ -4
≥0

9

EL MÉTODO DUAL-SIMPLEX
Y trasladado a su tabla Dual-Simplex

VB

R

Coeficientes

LD

z

x1

x2

x3

x4...