imagen: slidesharecdn.com
El método Simplex de Programación Lineal tiene como base de trabajo usar los datos en forma de matrices. ¿Recuerda la tabla de datos inicial en la forma 2: Los productos encabezan las columnas? Pues esta manera de organizar los datos del ejercicio ayuda a comenzar más rápido con el proceso del Método Simplex.
Veamos el ejemplo trabajado antes:
FORMA 2: Los productos encabezan las columnas
.........................Prod. A.........Prod. B....... disponibilidad
cantidad............... X................. Y
Ensamble.............. 4................. 3..................... 200 hr.
Pintura...................5.................. 6..................... 350 hr.
utilidad ................. 3................ 4
Al plantear el problema de programación lineal sería esto:
Función Objetivo:........ Zmax= 3x + 4y
sujeto a:
..................................................4x+3y <= 200
...................................................5x + 6y<= 350
Variables de no negatividad:
...................................................x>=0 y y>=0
Debemos construir una matriz ampliada donde tendremos la columna de x, la columna de y y la columna del lado derecho de las desigualdades; pero antes, debemos trasformarlas desigualdades a igualdad; para transformarlas, vamos a agrear nuevas variables con nombres s, t, u, w, (las últimas letras del alfabeto) Estas se van a llamar variables de holgura.
Qué hace la varable de holgura
Te lo voy a explicar pero esto no lo vas a necesitar para nada mas adelante; solo te muestro la función teórica que hace en el ejercicio para poder transformar una desigualdad en igualdad.
Advertencia: Este ejemplo solo funciona para cuando la desigualdad es menor o igual. Si la igualdad fuera mayor o igual, el proceso es algo mas largo para poder usar el método Simplex, lo puedes ver en Arya.
Veamos la desigualdad 4x+3y <= 200. Si agregamos la variable de holgura S, ahora será una igualdad así:
4x+3y+s = 200
Mira cómo funcionará s:
Si tuvieramos el valor de x y de y, el resultado debe ser menor de 200, entonces la nueva variable de holgura, tendrá el valor de la cantidad que falta para llegar a 200.
Imaginemos que x= 20 y y=15, entonces: 4*(20)+3*(15)=125 esto quiere decir que la variable de holgura (para que sea una igualdad) debería valer lo que falta para llegar a 200 que es 75. Entonces: s=75 si x=20 y y=15
¿Cuántas variables de holgura se usan?
En cada ejercicio, las variables de holgura a agregar, dependen de cuántas restricciones tengas. en este ejemplo, como hay dos restricciones, debemos agregar dos variables de holgura así:
Una variable s para la primera (ya lo hicimos): 4x+3y+s = 200
Una variable w para la segunda restricción: .....5x + 6y+w = 350
¿Cómo afectan las variables de holgura a la función objetivo?
Al agregar mas variables al problema, ahora tenemos estas: x, y, s, w. Estas variables se incorporan a la función objetivo Zmax o Zmin. en este caso, como es Zmax las variables de holgura no dan ninguna utilidad a la empresa es decir: cero (0), entonces se agregan a la función objetivo así:
Zmax= 3x + 4y + 0s + 0w
¿Cómo se construye la primera matriz para empezar el método simplex?
Ahora reescribimos el planteamiento del ejercicio que teníamos con desigualdades, pero ahora con las variables de holgura en la función objetivo y en las restricciones que ahora son igualdades.
Observa que en la primera restricción ahora también va w pero con coeficiente cero (0) y lo mismo con la segunda igualdad: lleva la variable s pero con coeficiente cero (0)
CONDICIÓN: Debes escribir el ejercicio ordenado para que queden las x formando una columna; igual para las y, y también para s y w.
Entonces lo verás así:
Función Objetivo:........ Zmax= 3x + 4y + 0s + 0w
sujeto a:
...................................................4x+ 3y +.. s + 0w = 200
...................................................5x + 6y + 0s +.. w = 350
La matriz a construir es una matriz ampliada: Las restricciones son las filas y la función objetivo es la ultima fila, pero cambiamos de posición Zmax al lado derecho y solo usamos Z.
Las columnas son: las cuatro variables x y s w mas la columna del lado derecho de las igualdades
Las filas son así:
Fila 1: Uso los coeficientes de la primera igualdad:....4....3...1...0....200
Fila 2: Uso los coeficientes de la segunda igualdad:...5....6...0...1....350
Fila 3: Uso los coeficientes de la función objetivo:.....3....4...0...0.....Z
Entonces la primera matriz para comenzar con el método simplex quedaría así:
Identifico cada columna para no olvidar a quién representa: La columna 1 representa a x; la columna 2: representa a y y así seguimos...
Identifico las filas para recordar a que recurso representan:
La fila 1: representa al recurso Ensamble
La fila 2: representa al recurso Pintura
La fila 3: representa la utilidad
..........................x.....y...s...w....
ensamble...........4....3...1...0....200
pintura...............5....6...0...1....350
Utilidad.............3....4...0...0.....Z
El método Simplex explicado de forma resumida
Para hacerlo sencillo, solo vamos a referirnos a problemas de maximización. En este caso, el signo de la desigualdad de las restricciones deben estar todas iguales a menor o igual: <=. Si hay alguna desigualdad con el signo mayor o igual >= se debe transformar esa desigualdad a <=. (luego lo veremos)
La ventaja del método Simplex es que se pueden resolver problemas para más de dos variables. Por ejemplo un problema de maximizar utilidad para una empresa con 3 o 4 productos.
Sin embargo, por lo extenso de resolver un ejercicio con 3 o 4 variables, casi siempre se usan problemas con solo dos variables.
El método Simplex nos va llevando de una tabla Simplex a la siguiente hasta finalizar mostrando la solución óptima. En cada avance de la Tabla Simplex la Z debe ir aumentando pues va maximizando ese valor.
La ventaja para quien domine el método gráfico
Como la mayoría de los problemas de Simplex, son con dos variables, esta situación le da ventaja a quien domine el método gráfico; pues un ejercicio de Simplex, primero lo resuelve por método geométrico, con la finalidad única de saber cuál es la solución y saber los puntos del polígono de soluciones factibles. Estos puntos, van apareciendo en el método Simplex como SBF en cada Tabla Simplex, hasta llegar a la solución óptima.
De este modo, si conoces de antemano los valores de las posibles SBF, puedes darte cuenta que vas por buen camino cuando haces cada tabla Simplex y el resultado o solución óptima ya lo conoces.
Mira cómo funciona el Simplex
En pocas palabras, se puede decir que el método Simplex es como jugar con una matriz inicial donde tenemos columnas de 1 y ceros. Debemos cambiar convenientemente una columna existente que ya tiene 1 y ceros, para que aparezcan estos números en otra columna. Para esto usamos las operaciones fila columna de hacer un 1 en la columna y luego hacer ceros los demás elementos de esa columna, usando la fila donde está hecho el 1.
El problema al empezar el juego con la matriz inicial son dos:
1 - ¿Cuál columna debo seleccionar para hacerle el uno (1)?
2 - ¿En cuál fila, de esa columna, debo hacer el uno (1)?
Para escoger la columna donde vamos a hacer el 1, observamos con detalle la última fila (fila de utilidad o maximización) el número positivo más grande me indica que esa columna es la que conviene seleccionar.
Para seleccionar la fila donde debemos hacer el 1 de la columna seleccionada antes, hacemos varias divisiones. Usando el número de la última columna de la matriz, lo dividimos entre el número correspondiente de esa fila. El resultado positivo mas pequeño, me indica que en esa fila es que debo hacer el 1 de la columna seleccionada.
Una vez que hallas hecho todas las operaciones fila columna para que en la columna seleccionada aparezca 1 y ceros, entonces tendrás dos columnas de 1 y ceros: La columna de una de las variables anteriores y la nueva columna que seleccionaste. Esa será la segunda tabla Simplex y le corresponde definir la SBF que arroja esa matriz.
Ahora, con esta nueva Matriz o Tabla Simplex, repites de nuevo el proceso de seleccionar una columna para hacer 1 y ceros, usando operaciones fila columna, y así llegarás a otra tabla Simplex.
El juego termina cuando en la última fila, ya no quedan números positivos sino valores cero y negativos. Entonces la SBF que corresponde a esa matriz, ya no es SBF, esa es la Solución Optima que maximiza la función objetivo.
¿Cómo se obtiene la tabla Simplez inicial y la SBF?
..........................x.....y...s...w....
ensamble...........4....3...1...0....200
pintura...............5....6...0...1....350
Utilidad.............3....4...0...0.....Z
De la primera matriz, puede observar que existen dos columnas con 1 y ceros (las ve?) Son s y w
Como el 1 de la columna s está en la fila 1 de ensamble, decimos que s=200
Como el 1 de la columna w esta en la fila 2 de pintura, decimos que w=350
El método simplex consiste en que esa matriz inicial, solo nos da el valor de dos variables (las que tienen columna de 1 y ceros) y las demás variables tendrán valor cero. Entonces el valor de todas las variables según la matriz inicial será: s=200....w=350.....x=0....y=0
Si usamos estos valores en la función objetivo Z podemos sabr cuánto valdrá Z en este caso.
Calculemos Z usando la función objetivo
Zmax= 3x + 4y + 0s + 0w
Recuerde los valores a usar aquí: s=200....w=350.....x=0....y=0
Z= 3*(0) + 4*(0) + 0*(200) + 0*(350) = 0
es decir z=0 para cuando s=200....w=350.....x=0....y=0. a esto se le llama solución básica factible (SBF) inicial.
Esta matriz inicial la llamamos Tabla Simplex inicial o 1 y le corresponde la
SBF s=200....w=350.....x=0....y=0...z=0
Mira cómo empieza el juego del Simplex
A partir de la tabla Simplex inicial, ahora debemos seleccionar una columna para hacerle el uno y los ceros; recuerda resolver dos preguntas: ¿Cuál será esa columna? ¿En cuál fila hago el 1?
Veamos la tabla Simplex inicial (debe haber dos columnas con 1 y ceros)
..........................x.....y...s...w....
ensamble...........4....3...1...0....200
pintura...............5....6...0...1....350
Utilidad.............3....4...0...0.....Z
Al observar con detalle la última fila, (resaltada en negritas) veamos cuál es el número positivo más grande...Ya lo viste? Es el 4, que está en la columna de y. También se le llama Variable Entrante, pues para la siguiente Tabla Simplez, en esa columna habrá un uno y ceros por lo cual toma valor y en la siguiente solución factitble.
Entonces esa columna será la seleccionada y es donde debo hacer el 1 y los ceros, usando operaciones fila columna.
Se recomienda entonces, encerrar la columna y para saber que esa es la que vamos a transformar a 1 y ceros. aquí lo verás en negritas
TABLA SIMPLEX INICIAL CON LA COLUMNA Y RESALTADA
..........................x.....y...s...w....
ensamble...........4....3...1...0....200
pintura...............5....6...0...1....350
Utilidad.............3....4...0...0.....Z
Ahora, en ¿Cuál fila hago el 1? Hago dos divisiones usando la ultima columna.
En la fila 1, vemos que hay un 3 en la columna y; entonces divido el 200 al final de esa fila entre el 3, dividimos asi: 200/3 = 66,66
En la fila 2, vemos que hay un 6 en la columna y; entonces divido el 350 al final de esa fila entre el 6, dividimos asi: 350/6 = 58,33
SELECCONO LA FILA PARA HACER EL 1 EN LA COLUMNA Y
ensamble...........4....3...1...0....200.......... divido 200/3 = 66,66
pintura...............5....6...0...1....350.......... divido 350/6 = 58,33
Utilidad.............3....4...0...0.....Z
De estas dos divisiones escojo el menor positivo que sería 58,33 para identificar la fila donde debe hacerse el 1 de la "columna y"; como este resultado: 58,3 lo saqué de la fila 2, entonces será en la fila 2 donde debo hacer el 1 para la columna y.
Quiere decir que donde está el 6, deberá ahora hacerse un 1 (usando operaciones filia columna multiplico toda la fila 2 por 1/6)
La nueva fila 2 será: ......5/6.....1....0....1/6.....350/6
Me queda la matriz con la fila 2 nueva así:
..........................x..........y....s.....w....
ensamble...........4.........3....1......0.......200
pintura...............5/6.....1....0....1/6.....350/6
Utilidad..............3........4.....0......0.........Z
El siguiente paso es convertir a cero, los otros elementos de la columna y, usando operaciones fila columna. Recuerde: Usaré la fila 2 como referente para multiplicar esa fila por el número conveniente, de tal modo que al sumar la fila 2 con la otra, me da cero en el elemento que deseo transformar.
A partir de este momento, empezamos a calcular la nueva matriz convirtiendo a cero los otros elementos de la "columna y" la fila 2 es la que quedará como está ahora y las otras dos filas: 1 y 3, van a cambiar quedando cero en la columna y.
Para convertir el 3 de fila 1 a cero:
Multiplico la fila 2 por -3 y se lo sumo a la fila 1: Lo señalo al lado derecho de la fila 1
Para convertir el 4 de fila 3 a cero:
Multiplico la fila 2 por -4 y se lo sumo a la fila 3: Lo señalo al lado derecho de la fila 3
..........................x..........y....s.....w....
ensamble...........4.........3....1......0.......200............... F2*(-3) + F1
pintura...............5/6.....1....0....1/6.....350/6
Utilidad..............3........4.....0......0.........Z ...............F2*(-4) + F3
Entonces la nueva matriz donde ya aparece la "columna y", con 1 y ceros es una tabla simplex, (ya tiene dos columna de 1 y ceros):
TABLA SIMPLEX 2
............................x...........y.......s.......w....
ensamble...........13/2.........0......1......1/2.......375
pintura................5/6..........1......0......1/6.......350/6
Utilidad..............19/3........0......0......-2/3.........Z -700/3
¿Cómo hallar la SBF para esta Tabla Simplex 2?
Recuerde: solo tienen valor dos variables, aquellas donde la columna es de 1 y ceros;
En la columna y: vemos donde está el 1 y luego la última columna de esa fila: y= 350/6
En la columna de s, vemos donde está el 1 y luego la última columna de esa fila: s= 375
Entonces la nueva SBF (Solución Básica Factible) es con los valores de "y" y "s" mientras las otras variables: "x" y "w" son cero:
y= 350/6
s= 375
x= 0
w= 0
Con estos valores calculamos Z de la función objetivo:
Zmax= 3x + 4y + 0s + 0w
Z= 3*(0) + 4*(350/6) + 0*(375) + 0*(0) = 700/3
TRUCO: Si observa la tabla simplex, en la fila 3 y la última columna, el valor es Z-700/3
Para ahorrarnos hacer el cálculo de Z, se toma el valor negativo -700/3 y se lleva a positivo, para asignarlo como valor de Z. Entonces, esto quiere decir que Z= 700/3.
¿Cómo saber si ya terminó el Método Simplex?
En cada Tabla Simplex, se debe revisar los valores de la última fila, si existe un valor positivo, entonces aún debemos seguir buscando la nueva Tabla Simplex, seleccionando la columna donde aparece el número positivo mas grande y repetir el proceso de hacer el uno en la fila adecuada.
Continuando con el ejemplo, se puede dar cuenta que en la fila 3 existe un valor positivo: 19/3 lo cual implica que debemos seleccionar esa columna y repetir el proceso de hacer el 1 y los ceros....
Por favor...siga usted con esta nueva vuelta del juego del Simplex; a lo mejor en la siguiente tabla ya no quedarán números positivos en la fila 3 y esa SBF ya pasará a ser la Solución Optima del problema de maximización. Solo en la última Tabla Simplex es cuando la SBF cambia de nombre para llamarse Solución Optima.
Suerte...
El método Simplex en el libro de Arya
En la pag. 433 Se muestran los pasos para aplicar el método Simplex
Libro de Arya
Método Simplex
Pag. 418 - 425
Ejercicios del libro de Arya
Resolver por método Simplex
pag 416: solo los ejercicios 4, 5, 6, 17, 18, 19
pag 436: solo los ejercicios 18 y 19
No hay comentarios:
Publicar un comentario