Clase #3

Clase #3

Método Simplex

Describiremos una técnica desarrollada por Neumann y Dantzig en matemáticas aplicadas que hace posible resolver problemas de P.L. en un tiempo relativamente breve, mediante simples cálculos.

El método simplex parte del 0 uso de la capacidad de las variables de decisión y el cálculo procede por una serie de pasos especificados, cada uno de los cuales se va acercando más y más hacia la última respuesta, es decir, comienza con una solución básica factible, (una solución básica factible para un problema con "n" variables y "m" restricciones, es una solución a las ecuaciones de variables con todas las variables > = 0 y no más de "m" variables son mayores que cero, el número de estas soluciones es finito y corresponden geométricamente a los puntos extremos de la región factible) y busca nuevas soluciones de tal manera que cada nueva solución permite mejorar el valor de la función objetivo. Mediante unas simples reglas se determina cuál es la variable básica que debe salir y cuál es la variable básica que debe entrar en cada interación, nos proporcionan, además, una manera de identificar que hemos llegado a la solución óptima.

El método puede ser sintetizado como un método algebraico sistemático que examina los vértices de una región solución de un problema de programación lineal en busca de una solución óptima. En particular , el algoritmo empieza por el examen de un vértice inicial para luego ir a un vértice adyacente. Cada vertice es una solución básica y cada movimiento, de un vértice al adyacente, se llama iteración. Las matemáticas de este recorrido o pivoteo son la esencia del algoritmo.

Caso Maximizar con Restricciones <= (Forma Canónica).

1.- Expresamos el problema en forma típica con ecuación (0) igual a Z-C1X1- ... -CnXn = 0. A fin de emplear el método hay que convertir las inecuaciones de restricciones en ecuaciones, mediante la adición de variables de "Holgura" (No Negativas) que no afecten a la ecuación objetivo (Una por cada restricción). Por consiguiente el coeficiente CJ de la variable de holgura XJ en la función objetivo es siempre cero (0). NOTA: Si el problema está en forma general primero debe ser puesto en forma canónica por medio de:

1) La minimización de la función objetivo Z puede expresarse como Maximizar -Z . Ejem:
MIN Z = 3X1 + 5X2 - 6X3
Es equivalente a Max (-Z) = -3X1 - 5X2 + 6X3

2) Una desigualdad de Tipo >= puede transformarse en una <= multiplicando por -1. Ejem:
3X1 + 8X2 - 6X3 >= 20
Es equivalente a: -3X1 - 8X2 + 6X3 <= - 20

3) Una Restricción de Tipo = Puede Ser Remplazada por dos Desigualdades de sentido contrario. Ejm: 8X1 + 6X2 = 40 Es equivalente a 8X1 + 6X2 <= 40 y 8X1 + 6X2 >= 40.

4) Una Variable que no este Restringida en signo puede ser remplzada por la diferencia de dos variables no negativas. Ejm:
Si XJ no está restringida en signo, se transforma en XJ = XJ' - XJ" con XJ' y XJ" >= 0.

5) Si la Restricción es de la forma IaX1 + bX2I <=C
Puede ser remplazada por:

aX1 + bX2 <= C y aX1 + bX2 >= -C.

Inicialización

Establece como se selecciona la S.B.F de partida:

2. Se toma como variables Básicas V.B. las variables de Holgura y Z (Hacemos las variables de decisión igual a cero y las llamamos variables no básicas). Construimos una tabla de columnas en la forma siguiente:

1 Columna : Las variables básicas V.B
2 Columna: (Columna de Z) Indicamos los coeficientes de las V.B en la función objetivo (Ecuación (0)).
3 Columna: Corresponde a los coeficientes de la Variable de la Decisión X1.
Por Cada variable de decisión se construye una columna.
N-i Columna: Se construyen columnas con los coeficientes de las variables de holgura.
N Columna: La última columna corresponde a los términos independientes en cada uno de las ecuaciones, todos los BI >= 0 (Porque son los valores de las variables en la solución factible dada.) con esta solución se observa que cada ecuación tiene una sola variable básica, cada variable básica tiene un coeficiente +1 en la tabla y NO aparece en ninguna otra ecuación.

Proceso Iterativo

Establece el Criterio para seleccionar la variable no básica que debe entrar al conjunto de variables básicas y como puede identificarse la variable que debe salir:

3.- Determinamos la variable que entra a formar parte de la solución básica la cual es la que corresponde al coeficiente más negativo en la ecuación de Z (ecuación 0) según aparece en la tabla. La variable básica V.B entrante debe escogerse de manera tal que incremente el valor de la función objetivo a la tasa más rápida.
Los coeficientes de la columna debajo de la variable que entra (excepto el coeficiente de la función objetivo) forman la columna pivote.

4.- Determinamos la variable que sale procediendo a identificar la variable básica que corresponde al menor de los cocientes que resultan de dividir los términos independientes entre los correspondientes coeficientes estrictamente positivos de la columna pivote, la variable correspondiente es la que primero llega a cero cuando la variable que entra aumenta. La fila formada por los coeficientes de la ecuación que corresponde a la variable que sale, es la llamada fila pivote.

5.- La intersección de la columna pivote con la fila pivote es el elemento pivote.

6.- Una vez identificadas las variables entrante y saliente se deben determinar los nuevos valores de las V.B por lo cual, es necesario transformar el nuevo sistema de ecuaciones a la misma forma que se tenía en la etapa inicial: Cada educación debe tener una sola V.B con coeficiente +1 en esa ecuación y no aparecer en ninguna otra ecuación . Para lo cual :

6.1) Dividimos los elementos de la fila pivote entre el elemento pivote para convertir el elemento pivote a 1.
6.2) Debemos reducir a cero todos los elementos restantes de la columna pivote por medio de procedimiento algebraicos utilizando operaciones entre filas (Procedimientos de Gauss - Jordan).

Regla de Parada

Se establece el criterio para conocer si una solución presente es o no óptima.

7.- Repítance los pasos 3,4,5 y 6 hasta que no queden número negativos en la ecuación de Z.

8.- Se habrá llegado a la solución óptima cuando todos los coeficientes de la función objetivo en la tabla correspondiente son no negativos. (mayores que cero para las variables no básicas e iguales a cero para las básicas) La solución óptima se obtiene asignado a cada variable de la primera columna, aquel valor en el región correspondiente en la última columna. A todas las otras variables se les asigna el valor cero.

Consideraciones.

1.- Las variables no básicas en la tabla final debe tener coeficientes mayores de cero en la función objetivo.
En el caso de que tuviesemos una variable no básica con coeficiente cero, el problema tendria multiple soluciones óptimas. Si la tomamos como variable que entra podemos obtener soluciones óptimas adicionales.

2.- Si hay 2 o más variables que son candidatas a entrar como variables básicas (empate en el coeficiente más negativo) se elije arbitrariamente cualquiera. La solución óptima se obtendrá eventualmente, más tarde o más temprano.

3.- Si hay un empate entre 2 o más variables candidatas a salir esto es, si los cocientes entre los términos independientes y los correspondientes de la columna pivote, tienen el mismo valor, se selecciona arbitrariamente la variable que sale.

4.- Si después de alguna iteración se observa que una de las variables básicas es cero. La solución se dice que es degenerada: no hay seguridad de que la función objetivo mejore (es posible que las iteraciones entren en un ciclo sin llegar a la solución óptima).

5.- Si ninguna variable es candidata a ser variable básica saliente (si todos los elementos de la columna pivote son cero o negativo) Se tiene que el valor óptimo de Z es ilimitado, infinito.

6.- La existencia de una o más variables artificiales (Ai) en la solución final con valores positivos, nos indicará que estamos en presencia de una solución no factible.

7.- Si en cualquier iteración, cualquiera de las variables candidatas a variable entrante tiene coeficientes menores o iguales a cero (<= 0) en todas las restricciones, entonces podemos afirmar que estamos en presencia de una solución no acotada.