Metodo Simplez

Curso: Investigación de
Operaciones
Profesor: Ing. Emanuel Aguilar Oviedo

Clase 3 Modelos matemáticos de investigación de operaciones.
SIMPLEX

Método simplex


El método simplex resuelve los problemas de programación lineal en
iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina que
tiene potencial de mejorar el valor de la función objetivo. El proceso terminacuando ya no se pueden obtener mejoras.
Para visualizar mejor la situación imaginemos a la función Z si
la evaluamos la función en cada uno de los puntos Si aumenta
(X1, X2), entonces:
como se ve en la figura el valor relativo a Z aumenta, por
ejemplo si aumentamos X1 desde (0,0), a (0,4) su valor debe
aumentar para llegar al punto esquina B (recuerde que no se
acepta detenerse antes dellegar a B, porque un candidato para
el óptimo debe ser un punto esquina).
Una vez en B, el método simplex aumentará el valor de (X1,
X2), para llegar al punto esquina mejorado C.
El punto D es óptimo y se termina el proceso. La trayectoria
asociada al algoritmo simplex es: A----B----C----D
𝑍 = 3𝑋1 + 5𝑋2

Si aumenta X2, el siguiente punto esquina será E, y a partir de E
la solución semueve hacia el punto óptimo D. El trayecto
asociado con el algoritmo simplex es A----E----D

Método simplex
Examinemos el método gráfico, tómese los
siguientes puntos como referencia



A: (X1, X2) = (0, 0)

Z=0



B: (X1, X2) = (4, 0)

Z = 15



C: (X1, X2) = (4, 3)

Z = 27



D: (X1, X2) = (2, 6)

Z = 36



E: (X1, X2) = (0, 6)

Z = 30

Esto se conoce comola Prueba de optimalidad:
𝑍 = 3𝑋1 + 5𝑋2

Método simplex


Terminología para la forma aumentada:


Solución Básica (BF): es una solución en un vértice aumentada.



Solución básica factible: es una solución a la ecuación Z aumentada. Una solución básica tiene
las siguientes propiedades:
1.

Cada variable se designa ya sea como variable básica o variable no básica.

2.

Elnumero de variables básicas es igual al número de restricciones funcionales. Por lo tanto, el número de
variables no básicas es igual al número total de variables menos el número de restricciones funcionales.



Las variables no básicas se igualan a cero.



Los valores de las variables básicas se obtienen como la solución simultanea del sistema de
ecuaciones.



Si las variablesbásicas satisfacen las restricciones de no negatividad, la solución básica es una
solución BF.

Método simplex


Paso inicial: Se eligen como variables no básicas a X1 y X2, por lo tanto se
igualan a cero. El sistema de ecuaciones es:

Prueba de optimalidad:
la función objetivo es Z = 3x1+5x2, de manera que Z = 0 para la BF inicial.
No es optima porque al aumentar el valor de cualquiervariable no básica (X1 y X2), el
valor de Z aumenta.

Método simplex
Iteración 1:
Determinación de la dirección de movimiento (paso 1 de una iteración): Se debe
elegir entre las variables no básicas, cual debe aumentar su valor. Como la función
objetivo es Z = 3x1+5x2, la tasa de mejoramiento de x2, es mayor, por lo que se elige
a esta para aumentar su valor. Se la denomina variablebásica entrante.

Iteración 1:
Determinación de donde detenerse (paso 2): esto nos dice cuanto aumentar la
variable básica entrante x2 antes de detenerse

Entonces x2 puede crecer justo hasta 6, en este punto x4 ha llegado a cero. Si se aumenta mas x2, causaría
que x4 se vuelva negativa, lo que violaría la factibilidad. Este cálculo recibe el nombre de prueba del
cociente mínimo. De esta manerax4 es la variable básica que sale para la iteración 1.

Método simplex
Iteración 1: Solución (paso3)
El propósito de este paso es convertir el sistema de ecuaciones a una forma más
conveniente para llevar a cabo la prueba de optimalidad. El sistema de ecuaciones que
tenemos es:

Para despejar Z, x2, x3 y x5, de este sistema de ecuaciones es necesario realizar algunas
operaciones...