Como resolver un SIMPLEX a mano.

El método SIMPLEX forma parte de la programación lineal y es una forma de encontrar máximos o mínimos de una función lineal objetivo considerando ciertas condiciones lineales también, en esta web describo el método. Esta resolución utiliza el denominado Algoritmo de Dantzig.

ADECUACIÓN DE LAS ECUACIONES

Este método busca hallar el máximo o mínimo de una función LINEAL dentro de unas restricciones LINEALES por lo tanto se trata de buscar entre los extremos o “cruce” de las restricciones, donde la función objetivo será máxima o mínima.

 Para aplicar el método simplex las ecuaciones a las que se aplica siempre han de tener un formato, antes y durante el método y el formato es:


 



Formato estandar:

Maximizar o minimizar: 

Z=C·x

sujeto a:

A·x=b

x>=0

donde:

A: es una matriz de coeficientes

C: es un vector de coeficientes

x: es un vector de variables

b: es un vector de terminos independientes


Donde TODAS LAS VARIABLES SOLO PUEDEN SER POSITIVAS, LAS RESTRICCIONES NO SON INECUACIONES Y LOS TERMINOS INDEPENDIENTES NO NEGATIVOS¿?.

 En caso de tener inecuaciones en las restricciones O las variables no sean necesariamente positivas ( HEMOS DE) hacer que sean mayores o iguales a cero. Para conseguir todo esto hemos de añadir variables con nombres específicos que indico en esta tabla:


Motivo

Tipo de variable que añado

Explicación

Consecuencias

Aparece un  (menor que)  en una restricción.

De holgura

 

Necesito una igualdad en la restricción.

Ninguna.

Aparece un (mayor que) en una restricción

(1)

De exceso

 

Necesito una igualdad en la restricción.

La nueva variable tiene un valor negativo, luego la añado con signo menos (no formara base factible)

Tendré que añadir una variable artificial y tendré que aplicar el método de las dos fases.

He añadido una variable de exceso.

Artificial

 

Necesito que las variables sean positivas.

Tengo que aplicar el método de las dos fases

La declaración de las variables no asegura que sean positivas.

Artificial

 

Necesito que las variables sean positivas.

Tengo que aplicar el método de las dos fases ¿?

(*) Si las variables que añado no forman base factible he de aplicar el método de las dos fases.

(*) Base factible es que formen una base unitaria con componentes positivos, si añado variables de exceso estas variables nos dan coeficientes negativos que hace que esta base no sea unitaria.

(1) Aparte de esta solución también podemos hacer un cambio de variable que nos dará variables que si forman base factible (todas positivas). Esto se aplica en restricciones sencillas.

ej:

x1>=100 ->y1=x1-100

 Si nuestras variables de holgura definen una solución básica factible inicial (esto ocurre siempre que solo se añadan variables de holgura) podemos aplicar SIMPLEX directamente.

 OPERANDO CON LA TABLA

Relleno la tabla del simplex con los coeficientes de las restricciones (todos deben estar con  términos independientes positivos si son negativos he de añadir variables artificiales), si estamos MAXIMIZANDO los coeficientes de la función objetivo son su signo y si estamos MINIMIZANDO cambiamos el signo de sus coeficientes y operamos como si estubiesemos maximizando.

Cuando estoy maximizando los coeficientes de la función objetivo son positivos y tengo que hacerlos negativos operando.

Cuando estoy minimizando he de cambiar el signo de los coeficientes de la función objetivo y mediante simplex hacerlos positivos. Es decir maximizar la función inversa TENGO QUE SACAR DE LA BASE LOS ELEMENTOS DE LA FUNCION OBJETIVO Y HACER NEGATIVOS LOS COEFICIENTES DE LA FO QUE ME QUEDAN.

 

Este algoritmo se repite hasta que hemos conseguido cambiar el signo a todos los elementos de la función objetivo.

 Nota: se opera por el método Gausiano, es decir solo se pueden sumar y restar filas, multiplicadas o no, cada uno de sus elementos por un coeficiente constante.

 Algoritmo:

Generalmente, si empezamos a operar la tabla, el primer paso es:

Hacemos ceros los coeficientes de la función objetivo de las variables que en ese momento forman la base. Sean positivos o negativos los coeficientes de la función objetivo.

 Buscamos la columna pivote (la del elemento pivote) que es la que tiene el termino de mayor valor absoluto de la fila de la función objetivo (si estamos minimizando tendrá signo positivo y viceversa)

 

En la columna pivote, buscamos el elemento con valor positivo y que su producto por su término independiente SEA MINIMO. Este es el ELEMENTO PIVOTE:

Si hay dos productos mínimos iguales elegimos uno.

Si no hay valores positivos el PROBLEMA ES NO ACOTADO es decir que con estas restricciones el valor máximo (o mínimo) es infinito.

 

Hacemos 1 el elemento pivote.

Hacemos 0 los elementos de la columna pivote (incluida la fila de la función objetivo).

Después hemos de comprobar que en la columna de elementos independientes de las restricciones los elementos son no negativos (multiplicándola por -1 la fila si es necesario), así CONSERVAMOS EL FORMATO ESTANDAR, necesario para aplicar el simplex.

 

Nota: cada elemento pivote nuevo, define la nueva VARIABLE DE ENTRADA y la base que tenía su componente uno en el pivote, SALE DE LA BASE. El simplex va siguiendo las “intersecciones” de las restricciones buscando la”interseccion” máxima, hasta que la encuentra.

 

Si a cada base que encontramos sacamos el vector asociado veremos cómo este algoritmo va buscando el máximo o mínimo.

 

4º Resultado:

Cuando no quedan en la fila de la función objetivo elementos positivos*, hemos conseguido encontrar el máximo o mínimo de la función.

*Si en la tabla en algun momento tenemos que todos los coeficientes de las retricciones son cero o menor que cero el problema es NO ACOTADO. (es decir, el máximo o el mínimo de la función objetivo es infinito)


La solución será:

El valor que toma la función: es el del término independiente de la fila de la función objetivo.(si la función la hemos cambiado de signo para minimizar en vez de maximizar el valor también)

Para las variables que forman la base: su valor será el que aparece en la fila de la función objetivo.

Para las variables que no forman la base: su valor es cero. Y su coeficiente en la función objetivo es NO NULO,

Si alguna variable NO BASICA tiene en su correspondiente coeficiente de la función objetivo un cero el simplex tiene INFINITAS SOLUCIONES y hemos encontrado una, para encontrar otra hemos de hacer entrar en la base esa misma variable no básica, entonces las infinitas soluciones estaran contenidas en la recta que une esos dos puntos.


CAMBIOS DE VARIABLES

Se hacen para no tener que añadir tantas variables adicionales y se pueden hacer de diferentes formas:

-. Si las variables no están restringidas a únicamente sus valores positivos:

p.e.:

x pertenece a R (cuando debería ser x mayor q 0 )

podemos hacer el cambio x=x1-x2, así x1 y x2 son variables positivas y x puede ser positiva y negativa.

-. Las variables que no cubren todo el rango de los positivos (cuando deberian ser x mayor igual que cero):

x >=100 -> x1=x-100>=0


METODO DE LAS DOS FASES

Este método se hace cuando al estandarizar el sistema hemos tenido que añadir variables auxiliares. El objetivo es eliminarlas.

Dicho de forma mas matematica, las variables añadidas no forman una base.

 

FASE 1

En la primera fase, la función objetivo solo tiene coeficientes en los lugares correspondientes a las variables auxiliares. ¿como se forma la funcion objetivo?

 Operamos la tabla por el método gausiano pero ahora el objetivo es SACAR LA BASE DE LAS VARIABLES AUXILIARES y hacer negativos los coeficientes de la función objetivo.

 Una vez sacada la base hemos eliminar las columnas de las VARIABLES AUXILIARES y sustituir la función objetivo por la del problema con las variables de exceso y de holgura.

Si el valor optimo del problema es distinto de cero, es decir el maximo o minimo en esta fase es distinto de cero EL PROBLEMA ES INFACTIBLE. ¿se puede encontrar solucion?

 

FASE 2

Una vez eliminadas las variables artificiales, colocada la función objetivo y comprobado que el máximo de la función anterior era cero aplicamos simplex;

Es igual que la del método simplex: sacamos de la base y hacemos los coeficientes negativos.


RESUMEN CASOS PARTICULARES

-. Problema in factible:

Cuando en la Fase 1 el resultado de la función objetivo es distinto de cero,

-. Problema no acotado:

Cuando al determinar la columna pivote, ningún coeficiente de las restricciones es positivo. por tanto el máximo o mínimo de la función objetivo es infinito.

-. Infinitas soluciones:

 Si tenemos que la funcion objetivo da cero en alguno de sus coeficientes QUE NO FORMAN PARTE DE LA BASE tenemos que el problema tiene infinitas soluciones.Podemos determinar un conjunto que incluya todas las soluciones haciendo entrar en la base esa variable

nota:

Añado un programa que obtiene la base de una tabla simplex (Dantzig) partiendo de la tabla y indicando el elemento pivote. (este programa tiene un error que le hace calcular mal la fila de la función objetivo, en el caso que el coeficiente "pivote" de la función objetivo sea diferente de 0 o 1) lo depurare en breve. 

El programa toma como tabla de simplex la MATRIZ DE LISTAS asignada a la variable S, y da el resultado en la variable Sc.

Podemos crear una matriz de listas como si creasemos una matriz de vectores levantado el FLAG 91.



ċ
SIMPLEX
(4k)
Bjorn Adams,
25 jun. 2010 8:18
Comments