metodo simplex

FISEI I 402-A NOMBRE: Zurita Bayas Mauricio Alejandro FECHA: 22/12/2014

Investigacion #: 03 II TEMA: Mtodo Simplex PG. #: 1

Objetivo:

Obtener una definicin clara sobre el mtodo simplex y sus aplicaciones para aplicarlo a la

resolucin de ejercicios de maximizacin y minimizacin con ms de dos variables mediante la una

investigacin bibliogrfica.

BIBLIOGRAFA: [1] T. l. d. reservados, PHPSimplex, www.phpsimplex.com, 17 Febrero 2013. [En lnea]. Available: http://www.phpsimplex.com/teoria_metodo_simplex.htm. [ltimo acceso: 22 Diciembre 2014].

El mtodo Simplex se basa en la siguiente

propiedad: si la funcin objetivo Z no toma

su valor mximo en el vrtice A, entonces

existe una arista que parte de A y a lo largo

de la cual el valor de Z aumenta.

nicamente trabaja con restricciones del

problema cuyas inecuaciones sean del tipo

"" (menor o igual) y sus coeficientes

independientes sean mayores o iguales a 0.


Investigacin #: 03 II TEMA: Mtodo Simplex PG. #: 2

BIBLIOGRAFA:

[1] T. l. d. reservados, PHPSimplex, www.phpsimplex.com, 17 Febrero 2013. [En lnea].

Available: http://www.phpsimplex.com/teoria_metodo_simplex.htm. [ltimo acceso: 22 Diciembre 2014].



Desarrollando el mtodo Simplex

Una vez estandarizado el modelo puede ocurrir que sea necesario aplicar el mtodo Simplex o el mtodo de las Dos Fases. Vase en la figura la forma de actuacin para llegar a la solucin del problema modelado.

A continuacin se explican paso a paso los puntos de cada mtodo, concretando los aspectos a tener en cuenta.




Resolver mediante el mtodo simplex el siguiente problema:

Maximizar Z = f(x,y) = 3x + 2y sujeto a: 2x + y 18

2x + 3y 42 3x + y 24 x 0 , y 0

Se consideran las siguientes fases: Realizar un cambio de variables y normalizar el signo de los trminos independientes. Se realiza un cambio en la nomenclatura de las variables. Establecindose la correspondencia siguiente: x pasa a ser X1 y pasa a ser X2 Como los trminos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habra que multiplicar por "-1" en ambos lados de la inecuacin (teniendo en cuenta que esta operacin tambin afecta al tipo de restriccin). Normalizar las restricciones. Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales segn la tabla siguiente: Tipo de desigualdad Tipo de variable que aparece - exceso + artificial = + artificial + holgura En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del tipo , para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2X1 + X2 + X3 = 18 2X1 + 3X2 + X4 = 42 3X1 + X2 + X5 = 24 Igualar la funcin objetivo a cero. Z - 3X1 - X2 - 0X3 - 0X4 - 0X5 = 0




Escribir la tabla inicial del mtodo Simplex. La tabla inicial del mtodo Simplex est compuesta por todos los coeficientes de las variables de decisin del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas, siendo P0 el trmino independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se encuentran en la base. La primera fila est formada por los coeficientes de la funcin objetivo, mientras que la ltima fila contiene el valor la funcin objetivo y los costes reducidos Zj - Cj. La ltima fila se calcula como sigue: Zj = (CbiPj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del mtodo Simplex y ser todos los Cb nulos se puede simplificar el clculo, y por esta vez disponer Zj = -Cj.

Condicin de parada. Si el objetivo es la maximizacin, cuando en la ltima fila (fila indicadora) no existe ningn valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condicin de parada. En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la solucin ptima del problema. Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solucin siempre resultar mejorable. Ante esta situacin no es necesario continuar iterando indefinidamente y tambin se puede dar por finalizado el algoritmo. De no ser as, se ejecutan los siguientes pasos de forma iterativa. Eleccin de la variable entrante y saliente de la base. Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sera la variable X1 (P1) de coeficiente -3. Si existiesen dos o ms coeficientes iguales que cumplan la condicin anterior (caso de empate), entonces se optar por aquella variable que sea bsica. La columna de la variable que entra en la base se llama columna pivote (en color verde)..




Una vez obtenida la variable que entra en la base, se procede a determina cual ser la variable que sale de la misma. La decisin se toma en base a un sencillo clculo: dividir cada trmino independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya resultado mnimo. Si hubiera algn elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos los elementos de la columna pivote fueran de sta condicin se habra cumplido la condicin de parada y el problema tendra una solucin no acotada (ver teora del mtodo Simplex). En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] El trmino de la columna pivote que en la divisin anterior dio lugar al menor cociente positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser X5 (P5), de coeficiente 3. Esta fila se llama fila pivote (en color verde). Si al calcular los cocientes, dos o ms resultados cumplen la condicin para elegir el elemento saliente de la base (caso de empate), se escoge aquella que no sea variable bsica (siempre que sea es posible). La interseccin de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3. Actualizar la tabla. Los nuevos coeficientes de la tabla se calculan de la siguiente manera: En la fila del elemento pivote cada nuevo elemento se calcula como: Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote En el resto de las filas cada elemento se calcula: Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote) Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos de la columna pivote se anulan (anlogo al mtodo de Gauss-Jordan). Se muestran a continuacin los clculos para la fila P4: Anterior fila P4 42 2 3 0 1 0 - - - - - - Anterior Elemento Fila en Columna Pivote 2 2 2 2 2 2 x x x x x x Nueva fila pivote 8 1 1/3 0 0 1/3 = = = = = = Nueva fila P4 26 0 7/3 0 1 -2/3 La tabla correspondiente a esta segunda iteracin es:




Al comprobar la condicin de parada se observa que no se cumple ya que entre los elementos de la ltima fila hay uno negativo, -1. Se contina iterando nuevamente los pasos 6 y 7.

6.1. La variable que entra en la base es X2 (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.

6.2. Para calcular la variable que sale, se dividen los trminos de la columna P0 entre los trminos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6, la variable que sale de la base es X3 (P3).

6.3. El elemento pivote es 1/3.

7. Actualizando nuevamente los valores de la tabla se obtiene

Una nueva comprobacin de la condicin de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solucin ptima y hay que seguir iterando (pasos 6 y 7):

6.1. La variable que entra en la base es X5 (P5), por ser la variable que corresponde al coeficiente -1.

6.2. Se escoge la variable que sale calculando el cociente entre los trminos de la columna de trminos independientes y los trminos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta ocacin es X4 (P4).

6.3. El elemento pivote es 4.

7. Despus de actualizar todas las filas, se obtiene la tabla siguiente:




Fin del algoritmo.

Se observa que en la ltima fila todos los coeficientes son positivos cumplindose, por tanto la condicin de parada.

La solucin ptima viene dada por el valor de Z en la columna de los trminos independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las filas correspondientes a las variables de decisin que han entrado en la base: X1 = 3 y X2 = 12.

Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.

Anlisis

Las sucesivas tablas construidas durante el mtodo Simplex van proporcionando el valor de la funcin objetivo en los distintos vrtices de la regin factible, ajustndose, a la vez, los coeficientes de las variables iniciales y de holgura. En la tabla inicial se ha calculado el valor de la funcin objetivo en el vrtice O, cuyas coordenadas (0,0) se corresponden con el valor que tienen las variables bsicas, siendo el resultado 0. 43

Solucin ptima: cuando se cumple la condicin de parada y no hay variables artificiales en la base con valor positivo (los valores se indican en la columna P0), se ha conseguido la optimizacin. El valor Z0 actual es la solucin ptima del problema, cumplindose para las variables que se encuentran en la base. Si se trata de un problema de minimizacin, el valor ptimo obtenido se multiplicar por "-1".

Infinitas soluciones: cumplida la condicin de parada, si alguna variable de decisin no bsica tiene un valor 0 en la fila Z, significa que existe otra solucin que aporta el mismo valor ptimo para la funcin objetivo. Es este caso el problema admite infinitas soluciones, estando todas ellas comprendidas dentro del segmento (o porcin del plano, regin del espacio, etc. dependiendo del nmero de variables del problema) definido por AX1 + BX2 = Z0. Mediante una nueva iteracin y haciendo que la variable de decisin que tiene el 0 en la fila Z entre en la base se obtendr otra solucin diferente para el mismo valor ptimo.




Solucin ilimitada (no acotada): si toda la columna de la variable que entra a la base tiene todos sus elementos negativos o nulos se trata de problema no acotado, es decir, que tiene solucin ilimitada. No hay valor ptimo concreto para la funcin objetivo sino que a medida que se aumenta el valor de las variables tambin se incrementa el valor Z sin violar ninguna restriccin.

No existe solucin: cuando ningn punto satisface todas las restricciones del problema se produce la infactibilidad no existiendo ninguna solucin posible para l. En este caso, una vez terminadas todas las iteraciones del algoritmo, existen en la base variables artificiales cuyo valor es superior a cero.

Empate de variable entrante: cuando se produce un empate en la condicin de decisin de la variable entrante se puede optar por cualquiera de ellas sin que esto afecte a la solucin final. Por contra si influye en el nmero de iteraciones necesarias para obtener dicha solucin. Se aconseja optar a favor de las variables bsicas ya que ellas son las que formarn parte de la solucin ptima.

Empate de variable saliente: se puede nuevamente optar por cualquiera de ellas. Sin embargo, a fin de no alargar el problema y evitar la entrada en un bucle infinito (caso degenerado), se discrimina a favor de las variables de decisin haciendo que permanezcan en la base. En el caso de estar en la primera fase del mtodo de las Dos Fases, se optar por sacar de la base las variables artificiales.

Curiosidad en la Fase 1: al finalizar la fase 1, si el problema original tiene solucin, todas las variables artificiales en la fila indicadora deben tener el valor "1".

El elemento pivote puede ser nulo?: No, el elemento pivote siempre ser estrictamente positivo ya que nicamente se realizan los cocientes entre valores no negativos y mayores que cero (ante un problema de maximizacin).

Conclusin.

La importancia de este mtodo radica en que gracias a su existencia se pueden resolver problemas complejos. Este mtodo conforma la base de la programacin lineal y es debido a este procedimiento (simplex) que se facilita la toma de decisiones en casos complejos o de incertidumbre ya que ha resultado ser muy eficiente en la prctica.

Una gran parte de software para clculos estn estrictamente basados en el mtodo simplex, facilitndonos la interpretacin de datos en poco tiempo es decir que gracias a este mtodo y a los programas que se basan en elejercicios que se tardaran das en resolverse se llevan a cabo en tan solo horas y hasta minutos optimizando el trabajo de todo aquel que necesite realizar este tipo de clculo.


metodo simplex

Documents