Investigación Operativa . Método Simplex

Método Simplex

Problema Original

|Minimizar Z = |[pic] |
|s.a. | |
| |[pic] |
| |[pic] || |[pic] |

El primer paso consiste en escribir el modelo original en la forma estándar. Notar que este problema ya se encuentra en la forma estándar.

Sistema ampliado es el mismo sistema de ecuaciones de la forma estándar más la función objetivo escrita de la manera siguiente: [pic] [pic] [pic]

[pic]Consideremos a [pic] y [pic] como variables básicas. Escribamos el sistema de tal manera que cada variable básica tenga coeficiente uno en una ecuación y coeficiente cero en todas las otras. Esto se realiza mediante cálculos elementales de filas y columnas. Tal sistema se dice que está en la forma canónica.

Forma Canónica

[pic]

Ahora, si hacemos cero a las variables no básicas [pic],[pic] y [pic] obtenemos la siguiente solución básica factible:
[pic], [pic], [pic], [pic], [pic] y [pic]

¿ es óptima esta sbf ?

Despejando Z de la primera ecuación, se tiene:

[pic]

Como estamos minimizando, vemos que si le asignamos a la variable no básica [pic] valores positivos se reduce aún más el valor de Z. Esto implica que podemos mejorar el valor de Z y por tanto esta soluciónbásica factible no sería la solución óptima.

Notar que mientras más grande es el valor que le asignemos a [pic] menor será el valor de Z. Sin embargo, con los valores asignados a [pic] las variables básicas [pic] y [pic] también cambian de valor y, eventualmente, podrían llegar a tomar valores negativos, haciendo que la nueva solución sea infactible. Luego, el mayor valor que le asignemos a lavariable no básica [pic] será aquel valor que haga que una de las variables básicas tome el valor cero.

Despejando Z y las variables básicas [pic] y [pic] en función de la variable no básica [pic], manteniendo las otras variables no básicas en cero, esto es, [pic] y [pic], se tiene:

[pic]

Queremos que, cuando le asignemos valores a la variable no básica [pic], cada variable básica continúesiendo no negativa. Es decir, que [pic] y [pic]. Entonces:

[pic]
[pic]

Notar que, cualquier valor de [pic] mayor que [pic]hace que [pic] sea negativo. De igual manera, cualquier valor de [pic] mayor que [pic]hace que [pic] sea negativo. Luego, el mayor valor que podemos asignarle a [pic] es [pic], pues cualquier otro valor mayor hará que [pic] sea negativo y la solución infactible.Observemos que [pic].

Ahora bien, si [pic] se obtiene la siguiente solución básica factible:

[pic], [pic], [pic], [pic], [pic] y [pic]

¿es óptima esta nueva sbf?

La única forma de responder esta pregunta es teniendo el sistema de ecuaciones en la forma canónica, con [pic] y [pic] como variables básicas. Puesto que la variable [pic] sigue siendo una variable básica, los coeficientes de sucolumna ya están en la forma canónica. Sólo falta poner a la variable [pic] en la forma canónica. Como [pic] reemplaza a la variable [pic], en la misma ecuación donde [pic] tiene coeficiente 1 la variable [pic] deberá tener coeficiente 1 y cero en las otras filas.

[pic]

Ahora, nuevamente, si hacemos cero a las variables no básicas [pic], [pic] y [pic] obtenemos la misma solución básicafactible:
[pic], [pic], [pic], [pic], [pic] y [pic]
Sin embargo, como el sistema de ecuaciones ampliado está en la forma canónica, podemos despejar Z de la primera ecuación y obtener:

[pic]

Dado que el coeficiente de la variable no básica [pic] es negativo se concluye que la solución actual tampoco es la óptima. Es claro que si todos estos coeficientes fueran positivos entonces no se podría...