Programación lineal

Solo sabemos hacer Max f(x) sujeto a R, luego si nos sale min f(x) sujeto a R
lo ponemos como Max -f(x) sujeto a las mismas restricciones.Las soluciones
de las variables son las mismas ( por ejemplo x_1=5, x_2=3) para ambos casos y lo único que varía es el valor de la función objetivo que si en el caso de minimizar valía z al sustituir ahora los mismos valores en -f(x) lógicamente nos da -z.Simplemente cambia de signo.
¿Como tratamos las restricciones?
<=)Añadimos una variable de holgura h_1 simplemente x+2y<=5 pasa a ser x+2y+h=5 y aparece un 1 directamente en la matriz unitaria
>=)x+2y>=5 restamos una variable de holgura x+2y-h+a_1=5 y añadimos una artificial a con idea de que aparezca el 1 de la matriz unitaria del problema general
Max f(x) -M(a_1+a_2)
=)x+y=5 para que aparezca el 1 en la matriz unitaria añadimos una nueva variable artificial x+y+a_2=5
Tanto para el método de la gran M como para el de las dos fases vemos que el número de variables artificiales es igual a la suma de los signos >=, y signos = que haya en las restricciones y nos va a definir el número de M's a emplear o de W's en el caso de las dos fases.Los signos <= son los únicos que no generan variables artificiales.
Ponemos un ejemplo:
min x-y sujeto a x+2y>=6,2x+y<=6,4x+y=4 que pasaria a Max -x+y sujeto a las mismas restricciones que bien puestas en forma estandar son: x+2y-h_1+ a_1=6,2x+y+h_2=6,4x+y+a_2=4 y la tabla inicial seria: 1 2 -1 0 0 1 6 2 1 0 1 0 0 6 Max -x+y-M(a_1+a_2) [1] 4 1 0 0 1 0 4 ----------------------------------- 1 -1 0 0 M M 0 Entran con signo cambiado al de [1] ----------------------------------- 1-M,-1-2M,M,0, M, 0 -6M -------------------------------------- 1-5M,-1-3M,M,0, 0 0 -10M Ya tengo las variables basicas a costo 0, y a partir de aqui seguimos el algoritmo del simplex:Entra la que tenga el menor valor de la fila de abajo,la mas negativa es decir 1-5M(entra x) y para ver quien sale min(6/1,6/2,4/4) es decir sale a_2 ... La columna de la variable artificial correspondiente a la igualdad-es las pondremos antes que las que corresponden a >= con idea de que al hacer la fase l solo eliminamos las columnas de las variables artificiales que corresponden a >=.
¿Por qué no podemos eliminar las columnas de las variables artificiales que proceden de igualdades? Porque a lo largo de la fase II pueden llegar a entrar de nuevo como variables básicas es decir que a_i tenga un valor no nulo y si esto ocurre no tiene solución el problema porque la igualdad que corresponde a esa a_1 no es tal igualdad al no ser nula la a_i.
Decíamos que entra en la base la que tiene mayor valor negativo(la mas negativa) y de esa columna pivote hacemos el mínimo de los{b_i/a_i} no pudiendo tomarse los valores de a_i que sean nulos 0 negativos.Si todos los a_i de la columna pivote fueran negativos o nulos estaríamos ante un
problema no acotado.
Si cuando llegamos al óptimo (todos los valores de la fila de abajo son positivos o nulos) ocurre que alguno de esos costes de alguna o varias variables no básicas sean nulos y si hacemos una nueva iteración(entra esta variable de costo nulo y sale como siempre la de su columna con menor b_i/a_i) la función objetivo no varía (puesto que ha entrado una variable de costo nulo) pero estoy en otro punto óptimo.Tendremos en este caso infinitas soluciones,todas las que están en la "recta" que unen esos dos puntos óptimos.

León-Sotelo