*** Cuando un problema es de maximización pero en las restricciones tenemos una desigualdad mayor o igual: >=, cambia un poco el uso de la variable de holgura (entra restando) y se agrega una Variable Artificial R.
QUE ES LA VARIABLE ARTIFICIAL
Se pudiera decir que se parece a una variable de holgura, la cual hemos venido usando para transformar una desigualdad <= a igualdad. Recuerda?: se agrega una variable de holgura por cada desigualdad <=, y en la función objetivo se agrega la variable de holgura con coeficiente cero. En el caso de que el problema de maximización, tenga restricciones de tipo <=, entonces es cuando se debe usar, además de la variable de holgura, una Variable Artificial que la mayoría de docentes la llaman R; pero ¿Cuándo se usa? ¿Cómo se usa? ¿Cómo afecta la función objetivo?. ¿Cuándo se usa?
¿Cuándo se usa la Variable Artificial?
La variable artificial se debe usar cuando un problema es de maximización pero en las restricciones tenemos una, o varias, desigualdades de tipo mayor o igual: >=
Por cada desigualdad de tipo mayor o igual se debe hacer esto: Restar una variable de holgura y sumar una variable artificial.
Tambièn se usa Variable Artificial si las restricciòn es una igualdad. aquì no se suma o resta variable de holgura; sino se suma una variable artificial por cada igualdad que tengamos.
Ejemplo,
Maximizar Z = - x + 2y
Sujeta a
............... x + y <= 5
.............. 2x + y >= 6
x>=0 y y>=0
Esto hace que el método Simplex debe usar una variable nueva R que se incorpora a la igualdad pero entra sumando.
¿Cómo se usa?
Para convertir a igualdad las restricciones, vea la segunda igualdad: seresta la VH y se suma la VA
............... x + y + t = 5
.............. 2x + y ....- u + v = 6
¿Cómo afecta la función objetivo?.
Ahora la función objetivo debe mostrar la variable de holgura con coeficiente cero y la nueva variable artificial con coeficiente M que se interpreta como un número muy grande Ej. 1 millón. La Va entra restando en la función objetivo para que n sea seleccionada como variable entrante al desarrollar el Simplex.
Z = - x + 2y + 0t + 0u - Mv
¿Cómo se hace la primera matriz para el Simplex?
Ordenamos las desigualdades, una debajo de otra pero cuidando que queden las variables en forma de columna: x debajo de las x; y debajo de las y, etc.
De último se escribe la función objetivo, pero la Z la colocamos a la derecha, para que quede debajo de los lados derecho de las igualdades
............... x + y + .. t...................= 5
.............. 2x + y ...........- u +. v... = 6
..............- x + 2y + 0t + 0u - Mv = Z
Para la primera matriz del Simplex, tomamos los coeficientes de las varaiables y tendremos una matriz de cinco columnas por tres filas.
Al lado izquierdo anotamos las variables donde tenemos columnas de 1 y ceros; pero OBSERVE la columna de v (variable artificial) no está completa porque en la fiila 3 no está el cero sino una - M.
CONSEJO: Entonces, siempre que se use la variable artificial, la primera matriz de datos no está lista como tabla Simplex porque la - M de la función objetivo hace que se tenga que convertir la - M a cero, usando la fila donde está el 1 de la variable artificial.
Ahora, luego de multiplicar la fila 2 por M y sumarla a la fila 3, esta sería la matriz:
Esta matriz sí representa una tabla Simplex, pues tenemos dos columnas de 1 y ceros; La columna de t y la columna de v.
La Solución Básica Factible (SBF) para esta Primera Tabla Simplex es: t = 5, v = 6 y las demás variables son cero: x=0, y=0 u=0
El valor de Z para esta tabla Simplex inicial es Z = - 6M
A partir de esta tabla comienza el juego del Simplex: buscar en la fila de la función objetivo el valor mas positivo (variable entrante) y luego en esa columna buscar donde hacer el 1 dividiendo con la última columna.
Seleccionamos la Variable Entrante:
Vemos en la fila 3, cual valor es mas positivo para escoger esa columna donde haremos el 1 y los ceros de la siguiente tabla Simplex.
Observe en la fila 3, que los valores de las columnas t , u, v, no entran en juego porque son cero o negativos.
Preguntamos. quién es mas positivo de estos valores que nos quedan
2M - 1
M+ 2
Como M es un número muy grande, usamos por ejemplo 1000, para determinar cuál es mas grande de las dos expresiones
2M - 1 = 2 * 1000 - 1
M + 2 = 1000 + 2
Se puede ver que 2M - 1 es el mas positivo; como está en la columna de x, esa será la variable entrante: x.
Por eso en la figura, verá una pequeña flecha debajo de la expresión 2M - 1
Seleccionamos la variable saliente
Ahora, en cual fila de la columna de x debo hacer el 1? Esa será la variable saliente.
Dividimos los elementos de la derecha de la igualdad entre el elemento de la columna de x.
Debemos escoger el "valor positivo menor" (atención, si la división da un número negativo, no se selecciona)
en la figura, se puede ver al lado derecho, la división de estos elementos: la columna de la derecha entre la columna de la variable entrante x.
Como el 3 resultante de dividir, es el menor positivo, seleccionamos esa fila que corresponde a una de la variables que están asignadas al lado izquierdo.
En este caso la variable saliente será: v
Entonces donde se cruza la columna de x con la fila de v, ahí se debe hacer el 1 para que posteriormente con operaciones fila columna, convertimos los demás números en cero.
Para hacer el 1, en la columna x con fila 2, multiplicamos la fila 2 por 1/2:
Ahora con operaciones fila - columna, convertimos a cero los elementos de la columna x así:
fila 1: Para llevar a cero el 1 de la columna x, multiplicamos la fila 2 por - 1 y la sumamos a la fila 1
Fila 3: Para convertir 2M - 1 a cero le debemos sumar lo opuesto: - 2M + 1. entonces, multiplicamos la fila 2 por (-2M+1) y lo sumamos a la fila 3
al terminar estas operaciones con cada fila, obtenemos una nueva tabla Simplex
En esta tabla simplex las varables asignadas son dos: aquellas donde tenemos columnas de 1 y ceros; estas columnas son:
La columna de x -------- entonces x, tiene su valor al lado derecho de la matriz: x = 3
La columna de t --------- entonces t, tiene su valor al lado derecho de la matriz: t = 2
Las demàs variables valen cero:
y = 0
u = 0
v = 0
el valor de Z serà: Z = - 3
tambièn lo puede calcular ysando la funciòn objetivo de arriba:
Z = - x + 2y + 0t + 0u - Mv
Z = - (3) + 2 (0) + 0 (0) + 0(0) - M(0) = - 3-------------- Z = - 3
Consejo: Para cada tabla Simplex, la SBF debe ser superior al de la tabla simplex anterior; veamos:
tabla simplex 1: Z = - 6M (recuerde M es un nùmero muy grande, por ejemplo 1000)
Tabla Simplex 2: Z = -3
Es decir, la Z pasò de - 6000 a - 3.
Identificada la SBF de la Tabla simplex, comienza de nuevo el juego para buscar la siguiente tabla Simplex, esta serà la Tabla Simplex 3
Comenzamos el proceso para la siguiente Tabla escogiendo de la ultima fila el valor positivo mas grande. Este valor es 5/2, el cual està en la columna y; la Variable Entrante es la y
ahora, dividimos la ultima columna entre la columna y para escoger el "menor positivo". Observe al lado derecho estas divisiones que son estas:
fila 1: se divide el 2 entre 1/2 ----------------resultado: 4
fila 2 se divide el 3 entre 1/2 -----------------resultado: 6
El valor positivo menor serà el 4, el cual està en la fila 1; entonces la variable saliente serà t; es decir, el nuevo 1 de la columna de y, se debe hacer donde se cruza columna y con la fila 1.
Al hacer las operaciones respectivas de Multiplicar la fila 1 por 2, para hacer el 1 de la columna y. Luego usar esa fila 1 para convertir a cero los otros elementos de la columna y, esta es la Tabla Simplex 3
Para esta Tabla Simplex 3, la SBF que le corresponde es esta: solo tienen valor y y x.
y = 4
x = 1
t = 0
u = 0
v = 0
Z = 7
Al revisar la fila 3 para escoger el mayor positivo y buscar otra Tabla Simplex, nos damos cuenta que todos los valores en esa ùltima fila son negativos o ceros; es decir, esa es la mejor soluciòn, por lo tanto, la SOluciòn òptima es la SBF que acabamos de describir, pero solo con las variables reales (sin t, u y v)
Soluciòn Optima:
y = 4
x = 1
Z = 7
No hay comentarios:
Publicar un comentario