MÉTODO DUAL

MÉTODO DUAL

En el algoritmo dual símplex, el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacía la factibilidad, sin violar la optimalidad. En iteración, cuando se restaura la factibilidad, el algoritmo termina.

El método dual símplex contrasta con el método regular (primal simplex), en el sentido de que las iteraciones empiezan factibles y no optimas y no continúan siendo factibles hasta que se logra la factibilidad.

En el método dual símplex, el cuadro simplex inicial debe tener un renglón objetivo optimo por lo menos con una variable básica no factible (<>

Condición Dual de Factibilidad: La variable de salida, x, es la variable básica que tiene el valor más negativo, con empates que se rompen arbitrariamente. Si todas las variables básicas son no negativas, el algoritmo termina.

Condición Dual de Optimalidad : La variable de entrada esta determinada entre las variables no básicas como la correspondiente a

min {øzj - cj ø, rj <>

no básicas rj

Donde rj es el coeficiente de restricción de la tabla símplex asociada con el renglón de la variable de salida x, y la columna de la variable de entrada Xj. Los empates se rompen arbitrariamente.

Considerando el sig. Problema calcular su modelo

(DUAL) MINIMIZAR P=4Z1+6Z2+18Z3+10Z4 Z1+3Z3+Z4≥3 Z2+2Z3+4Z4≥5 Z1, Z2, Z3, Z4 ≥0

Sea Max Z=3X+5Y

RESTRICCIONES X ≤ 4

Y ≤ 6

3X+2Y≤18

X+4Y≤10

DONDE X, Y≥0

PONEMOS LOS COEFICIENTES DISPONIBILIDAD EN FORMA DE VECTOR COLUMNA (MATRIZ), PRIMAL.

	4 6 18 10

B= Y ESTOS SE CONVIERTEN EN VECTOR HORIZONTAL O

VERTICAL (MATRIZ FILA) TRASPUESTA ESTO ES:

B^T = 4,6,18,10

HACEMOS LAS RESTRICCIONES DEL PRIMAL EN FORMA DE MATRIZ

	1 0 0 1 3 2 1 4		1 0 0 1 3 2 1 4

A ; POR LO TANTO SU TRANSPUESTA A^T =

DUAL SERA

Y AL MAXIMIZAR

	3 5

C = 3,5 ; SU MATRIZ TRASPUESTA (DUAL) SERA C^T =