Investigación de operaciones I

Programación lineal: método simplex

Programación lineal: método simplex
El método simplex es un conjunto iterativo de actividades utilizado ampliamente para resolver
problemas de programación lineal, propuesto por Dantzig George a finales de la década de
1940-1950. Se ha comprobado su eficiencia en un sin número de campos de la industria, y es
de uso común para resolver grandes problemas, incluso con equipos de cómputo de amplio
potencial de procesamiento.

1.Características

4. Otras formas Método 2.Procedimiento

de modelos simplex

3. Romper
empates
 Programación lineal: método simplex
El método simplex tiene bases conceptuales algebraicas. No obstante, muchos de sus
conceptos fundamentales son de carácter geométrico. La comprensión de dichos conceptos
genera un mejor entendimiento de este método y explica el por qué de su eficiencia. Se
retomará el ejemplo del fabricante de vidrios para iniciar la aproximación al tema.

Las cinco fronteras de restricción

corresponden a los puntos (0,0) (0,6) (2,6)
(4,3) y (4,0). Cada frontera de restricción
corresponde a una recta que marca el
límite de puntos factibles para el problema
propuesto. Los puntos que acotan la
región factible se conocen como
soluciones en los vértices. Para el caso
de este ejemplo, los puntos que se
encuentran en los vértices que acotan la
región factible se denominan como
“soluciones factibles en los vértices”
(FEV). En la gráfica podemos corroborar
que cada solución FEV se encuentra en la
intersección de dos (2) “fronteras de
restricción”.

● En el caso de un problema de programación lineal con n variables de decisión, cada una de las
soluciones en sus vértices se encuentra en la intersección de n fronteras de restricciones.
Programación lineal: método simplex
El método simplex es un método algebraico. Sin embargo, sus conceptos fundamentales son
geométricos. La comprensión de estos conceptos geométricos genera un mayor entendimiento
del método y explica el por qué de su eficiencia. Se retomará el ejemplo del fabricante de
vidrios para iniciar la aproximación al tema.

Para un problema de PL con n variables

de decisión, dos soluciones factibles en el
vértice son adyacentes entre sí, si
comparten n-1 “fronteras de restricción”.
Dos (2) soluciones factibles en el vértice
son adyacentes si están conectadas por
la sección de una recta que se encuentra
sobre estas mismas “fronteras de
restricción” que comparten. Esta sección
de recta se denomina “arista de la región
factible”.
Programación lineal: método simplex
El método simplex es un método algebraico. Sin embargo, sus conceptos fundamentales son
geométricos. La comprensión de estos conceptos geométricos genera un mayor entendimiento
del método y explica el por qué de su eficiencia. Se retomará el ejemplo del fabricante de
vidrios para iniciar la aproximación al tema.

Prueba de optimalidad. Para un

problema de PL que tenga una o más
soluciones óptimas. Cuando una solución
FEV no presenta soluciones FEV
adyacentes que mejoran el valor de la
función objetivo, entonces ese punto debe
corresponder a una solución óptima.
En el ejemplo de la ilustración el punto
(2,6) corresponde a una solución óptima
porque el valor de la función objetivo Z =
36 es más grande que Z = 30 para el
punto (0,6) y Z = 27 para el punto (4,3).

Esta “prueba de optimalidad” es

comúnmente aplicada en el método
simplex para evaluar si en una iteración
se ha llegado a una solución óptima.
 Programación lineal: método simplex
CONCEPTOS DE SOLUCIÓN

Cuando se evalúa El criterio para

una solución elegir la dirección
Como premisa factible en el del siguiente
En esta básica del método vértice cada punto solución
Solo se tienen en metodología se es deseable iteración del factible en el
cuenta las repite una establecer el método evalúa vértice es aquel
soluciones secuencia lógica punto de origen una nueva que represente
factibles en el de pasos hasta como solución solución factible una mejor tasa de
vértice dentro de alcanzar una inicial factible en en el vértice mejoramiento de
la metodología solución óptima el vértice o lo que ubicada en la la función objetivo
simplex. para el valor de la es lo mismo, que arista de un según los
función objetivo. las variables de segmento de recta coeficientes de las
decisión tomen el adyacente a la variables de
valor de cero (0). solución evaluada. decisión.
Programación lineal: método simplex
APROXIMACIÓN ALGEBRAICA AL MÉTODO SIMPLEX

El procedimiento algebraico se basa en la solución de sistemas de ecuaciones.

1 Convertir
Restricciones funcionales de Restricciones de igualdad
desigualdad equivalentes

Variable de Holgura
Programación lineal: método simplex
Continuando con el ejemplo del fabricante de vidrio, el modelo original se puede sustituir por
otro modelo equivalente (llamado forma aumentada del modelo).

Forma original del modelo Forma aumentada del modelo

Programación lineal: método simplex
TERMINOLOGÍA CORRESPONDIENTE A LA FORMA AUMENTADA DEL MODELO

Solución de las variables de

Solución decisión originales que se aumentó
aumentada con los valores correspondientes a
las variables de holgura.

Solución Solución en un vértice aumentada

básica

Solución
básica Solución FEV aumentada.
factible
Programación lineal: método simplex
TERMINOLOGÍA CORRESPONDIENTE A LA FORMA AUMENTADA DEL MODELO

5 variables

3
ecuaciones

2 grados
de libertad

# # grados
# variables ecuaciones de libertad
Programación lineal: método simplex
TERMINOLOGÍA CORRESPONDIENTE A LA FORMA AUMENTADA DEL MODELO

El método simplex asigna el valor de cero (0) (para el caso del ejemplo trabajado), a dos
(2) variables cualesquiera (que se denominan variables no básicas), y, entonces, la
solución simultánea de las tres (3) ecuaciones de las otras tres (3) variables (llamadas
variables básicas) es una solución básica.

PROPIEDADES DE UNA SOLUCIÓN BÁSICA

Cada variable es designada como variable básica o no

1 básica.

La cantidad de variables básicas es igual a la cantidad de

2 “restricciones funcionales”.

3 Las variables “no básicas” toman el valor cero (0).

Los valores para las “variables básicas” resultan de la solución

4 de las resolución de las ecuaciones simultáneas que derivan.

5 Toda solución básica factible satisface las restricciones de

“no negatividad”.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Incluir la función objetivo al sistema de ecuaciones

etiquetada como ecuación cero (0)
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Primer paso. Elija de la forma más conveniente, las variables no básicas e iguálelas
a cero (0).

Llegamos a la solución BF (0,0,4,12,18)

Segundo paso: Aplique prueba de optimalidad.

Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Tercer Paso. ITERAR

3.1 Sentido de la iteración

Elija la variable asociada a un mejor mejoramiento del valor de Z.

Para cada iteración de la metodología simplex, se debe elegir una “variable no básica”
que tome un mayor valor (se ajustan los valores de las demás variables básicas tal que
el sistema de ecuaciones sea válido). En el momento en que se aumenta el valor de la
variable no básica se convierte en variable básica en la siguiente iteración. Por lo
anterior, la variable básica elegida para mejorar su valor se convierte en variable básica
entrante de la nueva iteración dado que ingresa a la base.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Tercer Paso. ITERAR

3.2 Determinar el límite de aumento para la “variable básica entrante”

PRUEBA DEL COCIENTE MÍNIMO

Reescriba las igualdades en función de la sustitución de la variable no básica que se

mantiene igualada a cero (0)

Dada la restricción de no negatividad de las variables, evalúe el límite de crecimiento

de la variable básica entrante para cada igualdad, escogiendo el valor límite menor.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Tercer paso. ITERAR

3.2 Determinar el límite de aumento para la “variable básica entrante”

Para toda iteración de este método, utilizamos la prueba del cociente mínimo con el
ánimo de elegir cuál variable básica alcanza primero el valor de cero (0) cuando
aumentamos la “variable básica entrante”. Cuando disminuimos a cero (0) el valor
de esta variable básica, automáticamente pasa a ser “variable no básica” de la
nueva solución básica factible. Dado que esta variable deja la base en la actual
iteración, se denomina “variable básica saliente”.

Variable Básica Saliente

Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR

3.3 Nueva solución básica factible.

Para definir la ecuación cero (0) en esta iteración,

multiplicamos por cinco (5) la nueva ecuación dos (2) y
adicionamos la ecuación resultante con la ecuación cero
(0) anterior obteniendo lo siguiente.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR

3.3 Nueva solución básica factible.

Para definir la ecuación tres (3) en la iteración número 1,

multiplicamos por menos dos (-2) la ecuación (2) nueva y
adicionamos la ecuación resultante a la anterior ecuación tres
(3) de la siguiente forma.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR

3.3 Nueva solución básica factible

ELIMINACIÓN DE GAUSS-JORDAN
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR POR 2DA VEZ

Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

Para definir la ecuación uno (1) de la segunda iteración,

multiplicamos por menos uno (-1) la nueva ecuación (3) y
adicionamos la ecuación resultante a la ecuación (1)
anterior.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR POR 2DA VEZ

3.3 Nueva solución básica factible

Para definir la ecuación (0) de la segunda iteración,

multiplicamos por tres (3) la nueva ecuación (3) y
adicionamos la ecuación resultante a la ecuación (0)
anterior.
Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR POR 2DA VEZ

3.3 Nueva solución básica factible

Programación lineal: método simplex
FORMA ESTÁNDAR DEL MODELO (FORMA AUMENTADA) PARA APLICAR MÉTODO
SIMPLEX

PASO 3. ITERAR POR 3RA VEZ

3.3 Nueva solución básica factible

Lo que lleva a