Metodo m

Cómo resolver el Método Simplex, con penalizaciones, o gran M
Material de apoyo realizado por Sebastián Fellenberg C. Estudiante de Ingeniería Industrial. Universidad de las Américas. Chile

Introducción.
Antes de comenzar, debo aclarar que esto NO es el manual de un programa para la calculadora, en particular. Aquí les explicaré cómo utilizar la TI (cualquiera sea el modelo: 89, voyage 200,92, 92plus, etc.) para resolver el método simplex, con penalización (o la gran M).

Desarrollo.
Tomemos el siguiente ejemplo:

MinZ = 4 x1 + x 2 s.a 3x1 + x 2 = 3 4 x1 + 3x 2 ≥ 6 x1 + 2 x 2 ≤ 2 xi ≥ 0
Siendo MinZ la función objetivo, y el resto de las igualdades y desigualdades, las restricciones del problema. Para resolver este problema, debemos estandarizar las restricciones, las cualesquedarán de la siguiente forma: R1: R2: R3: 3 x1 + x2 + x3 = 3 4 x1 + 3 x2 − x4 + x5 = 6 x1 + 2 x2 + x6 = 4 x1 , x2 , x3 , x 4 , x5 , x6 ≥ 0

Observación: nótese que x 4 , NO conforma parte de la base de las variables básicas, por ser variable negativa. La variable básica será x 6 y las variables artificiales serán x3 y x5 . Una vez realizado este paso, debemos cambiar la función objetivo, esdecir, debemos cambiar dicha función a un problema de maximización, además de penalizar por cada variable artificial que tenga nuestro problema. Si no entendieron esto, a continuación les quedará un poco más claro: MinZ = 4 x1 + x 2 + Mx3 + Mx5 ⇒ Max(− Z ) = −4 x1 − x 2 − Mx3 − Mx5 Observación: recordar que SIEMPRE que tengamos un problema de programación lineal de minimización, debemos agregar un Mbastante grande (+M), por lo tanto, lo debemos adicionar a la función objetivo. En cambio, si tenemos un problema de maximización, debemos agregar un valor de M bastante pequeño (–M). Recordar también que MinZ = Max(–Z).

Ordenando las ecuaciones, tendremos lo siguiente: −Z + 4 x1 3x1 4 x1 x1 + x2 + x2 + 3x2 + 2 x2 + Mx3 + + x3 − x4 + Mx5 + x5 x6 =0 =3 =6 =4

Ahora viene lo interesante…Formamos el Tableau, con los valores que tenemos en las ecuaciones ordenadas. x1 4 3 4 1 x2 1 1 3 2 x3 M 1 0 0 x 4 x5 0 M 0 0 −1 1 0 0 x6 0 0 0 1 L.D R 0 3 6 4

−Z x3 x5 x6

Observación: L.D es lo que hay a la derecha del signo igual, y R es la razón (este es el criterio que se utiliza para saber qué variable entra y qué variable sale) Al ver este tableau, podemos ver que éste no está correcto,pues los costos reducidos de las variables básicas no son igual a cero, por lo tanto, este tableau se debe canonizar (es decir, eliminar las M que hay en el reglón cero) Para canonizar nuestro tableau, utilizamos la calculadora (usen la calculadora en inglés). Nos vamos al “Home”, y utilizamos la función mRowAdd, esta función la puedes hallar si buscas la tecla “math”, seleccionas matrix, Row ops,mRowAdd(. El comando mRowAdd lo utilizamos para poder eliminar el M de la primera fila. El comando mRowAdd, se utiliza de la siguiente manera: mRowAdd( – el número o letra a eliminar, matriz, fila que estás multiplicando por el número o letra, fila a la que vas a eliminar) Si te pareció muy enredado esto, con lo siguiente te va a quedar muy claro.

Escribiré la matriz en la calculadora, y laasignaré a la variable “new” (esto es algo opcional, no es necesario que lo hagan, pero yo les recomiendo que sí lo hagan, por si se equivocan, no deben volver a escribir todo otra vez)

Una vez escrita la matriz, y que la tienes en la pila de la calculadora, escribes lo siguiente: mrowadd(-ans(1)[1,3],ans(1),2,1) Observación: el comando ans(n) sirve para llamar a la barra de texto, el n – ésimoobjeto que está en la pila. Al escribir ans(1)[1,3], le estamos diciendo a la calculadora: “en el lugar 1 de la pila, hay una matriz, y quiero el elemento que está en la posición [1,3], entendiendo que los elementos se distribuyen [fila,columna]. El segundo argumento, es la matriz; el tercero es la fila “que ataca”, y el cuarto argumento es la fila “a la cual ataco”.

Esto queda así, como en la...