simplex

CAPÍTULO 4

PROGRAMACIÓN LINEAL - MÉTODO SÍMPLEX

4.1 Introducción
El método símplex es un procedimiento general para resolver problemas de programación lineal desarrollado por George Dantzig en 1947, está comprobado que es un método extraordinariamente eficiente que se usa en forma rutinaria para resolver problemas grandes en las computadoras de hoy en día. También se usan extensiones yvariaciones del método símplex para realizar análisis pos-óptimo (incluyendo el análisis de sensibilidad) sobre el modelo.
El algoritmo símplex es un método algebraico de programas lineales que aprovechan las propiedades de las soluciones básicas. Su estrategia consiste en explorar soluciones básicas hasta llegar a la óptima, de modo que la exploración se dirija siempre en la dirección queasegure una mayor aproximación a dicho óptimo.
El método gráfico del Capítulo 3 indica que la solución óptima de un programa lineal siempre esta asociada a un punto de esquina del espacio de soluciones. Este resultado es la clave del método símplex algebraico y general para resolver cualquier modelo de programación lineal.
La transición de la solución del punto de esquina geométrico hasta el métodosímplex implica un procedimiento de cómputo que determina en forma algebraica los puntos de esquina. Esto se logra convirtiendo primero a todas las restricciones de desigualdad en ecuaciones, para después manipular esas ecuaciones en una forma sistemática.
Una propiedad general del método símplex es que resuelve la programación lineal en iteraciones. Cada iteración desplaza la solución a un nuevopunto de esquina que tiene potencial de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden obtener mejoras.
El método símplex implica cálculos tediosos y voluminosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente, las reglas computacionales del método símplex se adaptan para facilitarel cálculo automático.
El método símplex, con la ayuda del computador, puede resolver problemas de programación lineal hasta con varios millares de variables y restricciones.
4.2 Espacio de soluciones en forma de ecuación
Para estandarizar, la representación algebraica del espacio de soluciones de programación lineal se forma bajo dos condiciones:
Todas las restricciones (excepto las de nonegatividad) son ecuaciones con lado derecho no negativo.
Todas las variables son no negativas.
4.2.1 Conversión de desigualdades a ecuaciones
El método símplex requiere que las restricciones sean ecuaciones (o restricción con relación de desigualdad). Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad no negativa en el lado de menor valor de la inecuación.
En lasrestricciones (≤), el lado derecho se puede imaginar como representando el limite de disponibilidad de un recurso, y en ese caso el lado izquierdo representaría el uso de ese recurso limitado por parte de las actividades (variables) del modelo. La diferencia entre el lado derecho y el lado izquierdo de la restricción (≤) representa por consiguiente, la cantidad no usada u holgura del recurso.
Paraconvertir una desigualdad (≤) en ecuación, se agrega una variable de holgura al lado izquierdo de la restricción. Por ejemplo, en el modelo de la constructora (ejemplo 3.1) la restricción asociada con la disponibilidad de camiones esta dada como:
x1 ≤ 6 [R2]
x2 ≤ 10 [R3]
Si se define h1 como la holgura, o cantidad no usada, las restricciones se pueden convertir en la siguienteecuación:
x1 + h1 = 6
x2 + h2 = 10
h1; h2 ≥ 0
Una restricción (≥) establece, normalmente, un límite inferior para las actividades del modelo de programación lineal. Como tal, la cantidad por la que el lado izquierdo es mayor que el limite mínimo (lado derecho) representa un excedente o superfluas.
La conversión de (≥) a ecuación se logra restando una variable de excedencia, del lado...