Método simplex y análisis
de sensibilidad/Dualidad y análisis postóptimo
DEFINICIÓN DEL PROBLEMA DUAL
El problema dual se define sistemáticamente a partir del modelo de PL primal (u original).
Los dos problemas están estrechamente relacionados en el sentido de que la solución
óptima de uno proporciona automáticamente la solución óptima al otro.
En la mayoría de los tratamientos de PL, el dual se define para varias formas del primal
según el sentido de la optimización (maximización o minimización), los tipos de restricciones
(#, $ o =), y el signo de las variables (no negativas o irrestrictas).
RELACIONES PRIMAL-DUAL
Los cambios realizados en los datos de un modelo de PL pueden afectar la optimalidad
y/o factibilidad de la solución óptima actual. Esta sección presenta varias relaciones
primal-dual que pueden usarse para calcular de nuevo los elementos de la tabla simplex
óptima. Estas relaciones constituyen la base de la interpretación económica del
modelo de PL y del análisis postóptimo.
Repaso de operaciones con matrices simples
La tabla simplex puede generarse por medio de tres operaciones de matrices elementales:
(fila vector) 3 (matriz), (matriz) 3 (columna vector) y (escalar) 3 (matriz). Por
comodidad, estas operaciones se resumen.
Diseño de la tabla simplex
En la actualidad, es común el uso del paquete de hojas de cálculo líder, Microsoft Excel, para elaborar pequeños modelos de IO en este formato. Después, se utiliza el Excel Solver para resolver los modelos, en ocasiones, en una versión mejorada, como el Premium Solver for Education in-
cluido en el OR Courseware.
MODELO DE PL EN FORMA DE ECUACIÓN
El desarrollo de los cálculos con el método simplex se facilita si se imponen dos requerimientos
a las restricciones de programación lineal.
1. Todas las restricciones son ecuaciones con lado derecho no negativo.
2. Todas las variabzzles son no negativas
TRANSICIÓN DE LA SOLUCIÓN GRÁFICA A LA ALGEBRAICA
En el método gráfico el espacio de soluciones es la intersección de los semiplanos
que representan las restricciones, y en el método simplex, el espacio de soluciones está
representado por m ecuaciones lineales simultáneas y n variables no negativas.
MÉTODO SIMPLEX
En lugar de enumerar todas las soluciones básicas (puntos de esquina) del problema
de PL, el método simplex investiga sólo “algunas” de
estas soluciones
Naturaleza iterativa del método simplex
Un incremento de x1 o x2 (o ambas) sobre sus valores actuales de cero mejorará el
valor de z. El diseño del método simplex no permite el incremento simultáneo de
las variables. En cambio, incrementa una a la vez. La variable que va a aumentar es la
que tenga mayor grado de mejora en z.
Detalles de cálculo del algoritmo simplex
. De forma equivalente, en la tabla simplex donde la función objetivo
aparece como z 2 5x1 2 4x2 5 0, la variable seleccionada es la variable no básica con el coeficiente
más negativo en la ecuación objetivo. Esta regla define la llamada condición de optimalidad
simplex. En la terminología del algoritmo simplex, x1 se conoce como la variable de entrada
porque ingresa la solución básica