dual simplex

Ejemplo Simplex Dual
Considere el siguiente modelo de Programación Lineal:

Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra agregando variables de exceso en cadauna de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de modo de disponer una solución básica inicial (infactible) en lasvariables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.






Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las actuales variablesbásicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar cual de las actuales variables no básicas (A, B, C)entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es el costoreducido de la respectiva variable no básica. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al hacer el primer cuociente, por tanto Aentra a la base.
Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en el Método Simplex. En el ejemplo se debe dejar a la variable A como básica y S1 como nobásica. La tabla que resulta es la siguiente:

Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta disponer de una solución básica factible. Luego de unas iteraciones se obtiene lasiguiente tabla final:







La solución óptima es A=8, B=10, C=60 (marcado en verde) con valor óptimo V(P)=6.620 (marcado en rojo - se obtiene con signo cambiado). También es interesantenotar que los costos reducidos de las variables artificiales S1, S2 y S3 (marcado en amarillo), corresponde a la solución óptima del modelo presentado en el tutorial de solver, esto dado que dicho...