Metodo Simplex

Investigaci´n Operativa o Algoritmo Primal del Simplex
1. A partir de la matriz A determinar una base B que proporcione una soluci´no b´sica factible xB = B −1 b. Sean: R = {columnas de A que no est´n en B}, I = a ¯ a {´ ındices de las columnas de la matriz A quepertenecen a la base B}, J = {resto de sub´ ındices o sub´ ındices de variables no b´sicas}. a 2. Calcular la matriz Y = B −1 R y lascantidades zj − cj = cT yj − cj , j ∈ J. B 3. Comprobar los valores zj − cj . a) Si ∀j ∈ J, zj − cj ≥ 0, (zj − cj ≤ 0 en problemas deminimizaci´n) ⇒ la o soluci´n b´sica factible en cuesti´n es maximal (minimal). o a o Si ∀j ∈ J, zj − cj > 0, (zj − cj < 0 en problemasde minimizaci´n) ⇒ la o soluci´n ´ptima es unica. o o ´ En caso de que exista una variable no b´sica con zj − cj = 0 ⇒ hay asoluciones ´ptimas alternativas. o b) En caso contrario sea J1 ⊆ J con J1 = {j ∈ J / zj − cj < 0}, (o J1 = {j ∈ J / zj − cj > 0} en caso deminimizar) e ir al paso 4. 4. Comprobar los valores de las columnas yj j ∈ J1 . a) Si existe j ∈ J1 tal que yj ≤ 0, el problema es noacotado. b) En caso contrario: 1) CRITERIO DE ENTRADA: Determinar k tal que: zk − ck = m´x |zj − cj | a
j∈J1

2) CRITERIO DE SALIDA:Determinar l tal que: xs ¯ xl ¯ = m´ ın ylk s/ysk >0 ysk 5. Considerar la nueva base B obtenida de sustituir al por ak . Ir a 2.