martes, 26 de febrero de 2013

2.2 Forma tabular del método simplex




Variables de Decisión
Variables de Holgura

Básicas ↓








Solución ↓






























Función Objetivo →










2.1 Teoría del método simplex


Para poder aplicar el método simplex a un modelo de programación lineal es necesario que este se encuentre en su forma estándar.

La forma estándar.

Las características de la forma estándar son:
1.-Todas las restricciones son ecuaciones excepto para las restricciones de no negatividad que permanecen como desigualdades.
2.-Los elementos del lado derecho de cada ecuación son no negativos.
3.-Todas las variables son no negativas.
4.-la función objetivo es del tipo de Maximización o minimización.

Transformaciones elementales.
1.-Las restricciones de desigualdad pueden cambiarse por ecuaciones introduciendo en el lado izquierdo de cada una de tales restricciones una variable no negativa.(estas nuevas variables se conocen como variables de holgura o superavit las cuales se sumaran si la desigualdad es £ (Holgura) y se restaran si la desigualdad es ³ (Superávit o exceso).
2.-El signo del lado derecho (-) puede eliminarse multiplicando la ecuación por  (-1) en caso de que sea necesario.
3.-Una restricción de desigualdad con su lado izquierdo en forma de valor absoluto puede cambiarse a dos desigualdades, la desigualdad contraria a la original se le antepone el signo negativo a su lado derecho.
4.-Una variable que es irrestricta en signo ( esto es positiva, negativa o cero) es equivalente a la  diferencia entre dos variables no negativas por consiguiente si X es irrestricta en signo puede remplazarse por (X+-X-) donde X+  y X-  son  ³ 0.
5.-Una desigualdad en una dirección (£ o ³) puede cambiarse a una desigualdad opuesta (³ o £) multiplicando ambos lados por (-1).
6.-Una ecuación puede ser remplazada por dos desigualdades en direcciones opuestas.
7.-La minimización de una función f(x), es matemáticamente equivalente a la maximización de la expresión negativa de esta función –f(x), y viceversa.

El método simplex.

Podemos decir que es la determinación algebraica de los puntos extremos del espacio de soluciones factibles (método gráfico), partiendo de la forma estándar. En la cual tenemos un sistema con m ecuaciones y n incógnitas.
La diferencia entre el número de ecuaciones y las incógnitas nos dan el número de variables que son iguales a cero en un punto extremo, las cuales son llamadas variables no básicas, y las variables restantes son llamadas básicas.



El método simplex inicia con un punto extremo o solución factible básica.


1.-La función objetivo se presenta como una ecuación y al pasarla a la tabla simplex cambian de signo los coeficientes de la función objetivo.
2.-Se coloca toda la información en una tabla.
3.-El siguiente paso es determinar una solución básica factible ( punto extremo). El método simplex hace esto eligiendo una variable no básica a la cual se le conoce como la variable que entra (se convertirá en básica) y una variable básica que se le conoce como la variable que sale ( se convertirá en no básica). La que entra está determinada por la condición de optimidad y la que sale por la condición de factibilidad.
4.-Condición de optimidad.- Dada la ecuación X0 (función objetivo) expresada en función de las variables no básicas solamente, se elige la variable que entra en maximización como la variable no básica que tiene el mayor coeficiente negativo y en minimización como la variable no  básica que tiene el mayor coeficiente positivo, en la ecuación X0. Un empate entre dos variable no básicas o más se rompe arbitrariamente. Cuando los coeficientes del lado izquierdo de la ecuación X0 (Función objetivo)son no negativos (maximización) o no positivos (minimización) se ha llegado al punto optimo.
5.-Condición de factibilidad.-La variable que sale es la variable básica correspondiente al cociente más pequeño de los valores actuales de las variables básicas entre los coeficientes positivos de las restricciones de la variable que entra. Un empate puede romperse arbitrariamente.