Variables de Decisión
|
Variables de Holgura
|
||||||||
Básicas ↓
|
Solución ↓
|
||||||||
Función Objetivo →
|
martes, 26 de febrero de 2013
2.2 Forma tabular del método simplex
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.
Suscribirse a:
Entradas (Atom)