Alumno:
DENISSE ANAHI ARANDA HERNANDEZ
Matricula:
L-8876
Grupo:
6to
Materia:
INVERSION OPERATIVA
Profesor:
SERGIO GUAJARDO
Trabajo:
EL METODO SIMPLEX
GUADALUPE,
N. L. A 9 DE JULIO DEL 2012
EL METODO SIMPLEX PARA SOLUCIÓN
DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Es un
procedimiento iterativo que permite ir mejorando la solución a cada paso. El
proceso concluye cuando no es posible seguir mejorando más dicha solución.
El método del simplex fue creado
en 1947 por el matemático George Dantzig .
Partiendo del valor de la función
objetivo en un vértice El método del simplex se cualquiera, el método consiste
en buscar sucesivamente utiliza, sobre todo, para otro vértice que mejore al
anterior. La búsqueda se hace resolver problemas de programación lineal en los
siempre a través de los lados del polígono (o de las que intervienen tres o más
aristas del poliedro, si el número de variables es mayor). variables. Cómo el
número de vértices (y de aristas) es finito, siempre se podrá encontrar la
solución. El álgebra matricial y el El método del simplex se basa en la
siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el
vértice A, entonces hay una arista que parte de A, a lo largo de la cual f
aumenta.
proceso de eliminación de
Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la
base del método simplex.
Encontrar la variable de decisión
que entra en la base y la variable de holgura que sale de la base A. Para
escoger la variable de decisión que entra en la base, nos fijamos en la última
fila, la de los coeficientes de la función objetivo y escogemos la variable con
el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable
x de coeficiente - 3. Si existiesen dos o más coeficientes iguales que cumplan
la condición anterior, entonces se elige uno cualquiera de ellos. Si en la
última fila no existiese ningún coeficiente negativo, significa que se ha
alcanzado la solución óptima. Por tanto, lo que va a determinar el final del
proceso de aplicación del método del simplex, es que en la última fila no haya
elementos negativos. La columna de la variable que entra en la base se llama
columna pivote (En color azulado).
Para encontrar la variable de
holgura que tiene que salir de la base, se divide cada término de la última
columna (valores solución) por el término correspondiente de la columna pivote,
siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] ,
42/2 [=21] y 24/3 [=8] Si hubiese algún elemento menor o igual que cero no se
hace dicho cociente. En el caso de que todos los elementos fuesen menores o
iguales a cero, entonces tendríamos una solución no acotada y no se puede
seguir. El término de la columna pivote que en la división anterior dé lugar al
menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable
de holgura que sale de la base, d. Esta fila se llama fila pivote (En color
azulado).
Si al calcular los cocientes, dos o más son
iguales, indica que cualquiera de las variables correspondientes puede salir de
la base. En la intersección de la fila pivote y columna pivote tenemos el
elemento pivote operacional, 3. 5. Encontrar los coeficientes de la nueva
tabla. Los nuevos coeficientes de x se obtienen dividiendo todos los
coeficientes de la fila d por el pivote operacional, 3, que es el que hay que
convertir en 1. A continuación mediante la reducción gaussiana hacemos ceros
los restantes términos de su columna, con lo que obtenemos los nuevos
coeficientes de las otras filas incluyendo los de la función objetivo Z. También
se puede hacer utilizando el siguiente esquema: Fila del pivote: Nueva fila del
pivote= (Vieja fila del pivote) : (Pivote) Resto de las filas: Nueva fila=
(Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable
entrante) X (Nueva fila del pivote) Veámoslo con un ejemplo una vez calculada
la fila del pivote (fila de x en la Tabla II): Vieja fila de s 2 3 -
Coeficiente 2 2 x x 0 1 0 - - 2 2 2 x x x 42 2 x
Como en los elementos de la
última fila hay uno negativo, -1, significa que no hemos llegado todavía a la
solución óptima. Hay que repetir el proceso: A. La variable que entra en la
base es y, por ser la variable que corresponde al coeficiente -1 B. Para
calcular la variable que sale, dividimos los términos de la última columna
entre los términos correspondientes de la nueva columna pivote: 2:1/3 [=6] ,
26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que
la variable de holgura que sale es h. C. El elemento pivote, que ahora hay que
hacer 1, es 1/3. Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3 Base Variable de decisión Variable de holgura
Valores solución x y s x Z 0 0 1 0 y 1 0 0 0 h 3 -7 -1 3 s 0 0 0 0 d -2 4 1 -1
6 12 6 30
Como en los elementos de la
última fila hay uno negativo, -1, significa que no hemos llegado todavía a la
solución óptima. Hay que repetir el proceso: A. La variable que entra en la
base es d, por ser la variable que corresponde al coeficiente -1 B. Para
calcular la variable que sale, dividimos los términos de la última columna
entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] ,
12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la
variable de holgura que sale es s. C. El elemento pivote, que ahora hay que
hacer 1, es 4. Obtenemos la tabla:
Tabla IV . Final del proceso Base
Variable de decisión Variable de holgura Valores solución x y d x Z 0 0 1 0 y 1
0 0 0 h -1/2 -7/4 -3/4 5/4 s 0 0 0 0 d 0 1 0 0 12 3 3 33
Como todos los coeficientes de la
fila de la función objetivo son positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de los valores
solución, en nuestro caso: 33. En la misma columna se puede observar el vértice
donde se alcanza, observando las filas correspondientes a las variables de
decisión que han entrado en la base: D(3,12) * Si en el problema de maximizar
apareciesen como restricciones inecuaciones de la forma: ax + by c;
multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax - by -
c y estamos en el caso anterior * Si en lugar de maximizar se trata de un
problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del
criterio, es decir, para entrar en la base se elige la variable cuyo valor, en
la fila de la función objetivo, sea el mayor de los positivos y se finalizan
las iteraciones cuando todos los coeficientes de la fila de la función objetivo
son negativos
Interpretación geométrica del
método del simplex Las sucesivas tablas que hemos construido van proporcionando
el valor de la función objetivo en los distintos vértices, ajustándose, a la
vez, los coeficientes de las variables iniciales y de holgura. En la primera
iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha
calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.
A continuación se desplaza por la arista AB, calculando el valor de f , hasta
llegar a B. Este paso aporta la Tabla II. En esta segunda iteración se ha
calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24 Sigue por
la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla
III.
No hay comentarios:
Publicar un comentario