METODO SIMPLEX
El método gráfico, indica que la solución óptima de un programa lineal siempre está asociada con
un punto esquina del espacio de soluciones. Este resultado es la clave del método simplex
algebraico y general para resolver cualquier modelo de programación lineal.
La transición de la solución del punto esquina geométrico hasta el método simplex implica un
procedimiento de cómputo que determina en forma algebraica los puntos 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 simplex es que resuelve la programación lineal en iteraciones.
Cada iteración desplaza la solución a un nuevo punto 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 simplex 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 simplex se adaptan para facilitar el cálculo automático.
ESPACIO DE SOLUCIONES EN FORMA DE ECUACION
Para estandarizar, la representación algebraica del espacio de soluciones de programación lineal se
forma bajo dos condiciones:
1. Todas las restricciones (excepto las de no negatividad) son ecuaciones con lado derecho no negativo.
2. Todas las variables son no negativas.
Conversión de desigualdades a ecuaciones
En las restricciones (≤), el lado derecho se puede imaginar cómo representando el límite 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.
Para convertir una desigualdad (≤) en ecuación, se agrega una variable de holgura al lado izquierdo de
la restricción. Por ejemplo en el modelo de Reddy Mikks (Solución por el método gráfico) la restricción
asociada con el uso de la materia prima M1 está dada como:
6 X 1 +4 X 2 ≤ 24
Si se define S1 como la holgura, o cantidad no usada, de M1, la restricción se puede convertir en la
siguiente ecuación:
6 X 1 +4 X 2 + S1= 24, S1≥ 0
Continuando. 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 límite mínimo (lado derecho) representa un excedente.
Es importante observar que la variable de holgura S1 es siempre no negativa.
El único requisito que queda es que al lado derecho de la ecuación que resulte sea no negativo.
TABLA SIMPLEX
OPERACIONES NECESARIAS
La fila de la variable que sale es la ecuación pivote
Nueva ecuación pivote:
= ecuación pivote/ elemento pivote.
Las demás ecuaciones incluyendo Z:
(Ecuación anterior)-[coeficiente de la columna de la variable que entra]*(nueva ecuación
pivote)
CASOS ESPECIALES DEL METODO SIMPLEX
SOLUCION DEGENERADA:
Si se presenta un empate en la variable que sale de forma repetida, una variable básica tomará valor
cero, esto hace que la solución sea degenerada. Lo anterior es debido a la existencia de a lo menos
una restricción redundante.
MULTIPLES SOLUCIONES ÓPTIMAS:
Se presenta cuando la función objetivo es paralela a una restricción activa (se satisface como igualdad
en la solución óptima), en este caso hay infinitas soluciones.
Desde el punto de vista práctico permite escoger la solución que mejor se adapte a la situación.
SOLUCIONES NO ACOTADA:
Se presenta cuando el espacio de soluciones no está acotado en la dirección hacia donde aumenta o
disminuye la función objetivo, según el modelo sea de maximización o minimización. Si en cualquier
iteración los coeficientes de las restricciones de una variable no básica son no positivos, entonces el
modelo no está acotado en la dirección de esa variable. Si el coeficiente de la función objetivo es
negativo en maximización o positivo en minimización, entonces el valor de la función objetivo
tampoco está acotado.
SOLUCION INFACTIBLE:
Ocurre cuando las restricciones no se pueden satisfacer de forma simultánea. Este tipo de solución no
se presenta si todas las restricciones son del tipo ≤, en otro tipo de restricciones hace falta el uso de
variables artificiales, lo que puede dar lugar a soluciones no factibles. Un modelo con solución
infactible puede significar que ha sido mal planteado o que las restricciones no estén destinadas a
cumplirse simultáneamente, por lo que haría falta una estructura diferente del modelo.
