Solución de problemas de PL:
Método SIMPLEX algebraico
Maria Camila Arango | Optimización
Casos especiales
Recordemos.. • No hay región factible
Términos • Múltiples soluciones óptimas
• Región factible • No hay solución óptima →problema no
acotado
• Solución factible / solución no factible
Simplex gráfico
• Solución óptima
1. Hallar una solución inicial (FEV): Podría ser una solución
• Solución factible en vértice (FEV) –básica trivial; usualmente (0,0)
factible
2. Prueba de optimalidad: Es la solución óptima? Chequear
• Solución no factible en vértice –básica no las soluciones FEV adyacentes a la solución actual
factible
3. Iteraciones: Se mueve hacia otras soluciones FEV.
• Solución factible adyacente
Solución de problemas de PL:
Método SIMPLEX algebraico y
tabular
Maria Camila Arango | Optimización
Método Simplex
• La forma algebraica del método La forma tabular es la más
simplex puede ser la mejor para adecuada para realizar
entender la lógica fundamental de cálculos y análisis.
algoritmo. Sin embargo, no es la
más conveniente para realizar los En todas las ecuaciones,
cálculos necesarios. Cuando se las variables van al lado
tenga que resolver un problema a izquierdo y los términos
mano se recomienda la forma independientes al L.D,
tabular. incluida la F.O.
Método Simplex - Tabular
La forma tabular se registran:
• Coeficientes de costo (Cj)
• Coeficientes tecnológicos (aij)
• Términos independientes o lado derecho (bi)
• La variable básica que aparece en cada ecuación
Antes de empezar: tablero simplex
Forma original del modelo Forma aumentada del modelo
Ejercicio: proponga la forma aumentada del modelo
Antes de empezar: Con la forma aumentada del modelo creamos el
tablero simplex de la siguiente forma:
tablero simplex
Antes de empezar: tablero simplex
Coeficientes de
costos
Variables básicas (V.B) Coeficientes Las V.B forman Términos
tecnológicos una matriz independientes
identidad
Resumen del método simplex (tabular algebraico)
1. Paso inicial: 2. Prueba de optimalidad:
Se introducen las variables de holgura. La solución básica factible es óptima si y
sólo si todos los coeficientes del renglón (0)
son no negativos.
Se seleccionan las variables de decisión Si es así el proceso se detiene, sino, sigue
como las V.N.B (=0) una iteración para obtener la siguiente
solución B.F. que incluye cambiar una
variable V.N.B (=0) a básica V.B (diferente
de 0).
Resumen del método simplex (tabular algebraico)
3. Iteración: En el ejemplo:
Paso 1: Se determina la variable básica
entrante.
Para esto se selecciona la variable con el
coeficiente negativo que tiene el mayor
valor absoluto de la ecuación (0). Se pone
un recuadro alrededor de la columna
debajo de este coeficiente y se denomina
columna pivote.
Resumen del método simplex (tabular algebraico)
3. Iteración:
En el ejemplo:
Paso 2: Se determina la variable básica que sale.
Para esto se realiza la prueba de cociente mínimo.
Prueba de cociente mínimo:
1. Elija los coeficientes estrictamente positivos de
la columna pivote.
2. Divida la columna del L.D del mismo renglón
entre dicho coeficiente.
3. Identifique el renglón que tiene el menor
cociente de todos.
4. La variable básica de este renglón es la variable
que sale. Ponta un recuadro de ese renglón que
se llame renglón pivote.
Resumen del método simplex (tabular algebraico)
Variable que sale:
En el ejemplo:
Resumen del método simplex (tabular algebraico)
3. Iteración:
En el ejemplo:
Paso 3: se debe sustituir una nueva tabla
simplex mediante operaciones elementales con
renglones. Las operaciones elementales con
renglones que deben realizar son:
1. Divida el renglón pivote entre el número Este nuevo renglón es para sustituir el
pivote, use este nuevo renglón en los renglón de la variable que sale por la
siguientes pasos. nueva variable (la que entra).
2. Multiplique el nuevo renglón pivote por
Este paso es para encontrar el nuevo
menos el coeficiente de la variable que
entra y el resultado súmelo al renglón (0). Renglón (0) asociado a Z.
Resumen del método simplex (tabular algebraico)
3. Iteración:
3. En el caso de los renglones que tienen un coeficiente positivo mayor que
cero en la columna pivote, se les resta el producto (multiplicación) del valor
absoluto de este coeficiente por el nuevo renglón pivote
Finalmente: Se sustituye en la nueva tabla simplex, como iteración 1.
Primeras dos tablas simplex del problema prototípico
Resumen del método simplex (tabular algebraico)
4. Prueba de optimalidad:
En el ejemplo:
Aun tenemos coeficientes negativos en el renglón (0) por tanto debemos hacer otra iteración.
Este no es el valor optimo
Resumen del método simplex (tabular algebraico)
Aplicamos nuevamente los
pasos de iteración:
Resumen del método simplex (tabular algebraico)
Identificamos la variable que sale, la que entra, el renglón pivote, columna pivote:
En el ejemplo:
se debe sustituir una nueva tabla simplex mediante operaciones
elementales con renglones. Las operaciones elementales con
renglones que deben realizar son:
1. Divida el renglón pivote entre el número pivote, use este
nuevo renglón en los siguientes pasos.
2. Multiplique el nuevo renglón pivote por menos el coeficiente
de la variable que entra y el resultado súmelo al renglón (0).
Nueva solución básica factible
Prueba de optimalidad
Es la solución optima, no tenemos
coeficientes negativos en el renglón (0)
