EL MÉTODO SIMPLEX

INDICE.


EL METODO SIMPLEX
1. ESPACIO DE SOLUCIONES EN FORMA DE ECUACIÓN.
1.1 Conversión de desigualdades a ecuaciones.
1.2 Manejo de variables no restringidas.
2. TRANSICIÓN DE SOLUCIÓN GRÁFICA A SOLUCIÓN ALGEBRAICA.
3. EL MÉTODO SÍMPLEX.
3.1 Naturaleza iterativa del método simplex.
3.2 Detalles de cálculo del algoritmo simplex.
4. SOLUCIÓN ARTIFICIALDE INICIO
4.1 Método M.
4.2 Método de dos fases.
5. CASOS ESPECIALES DE LA APLICACIÓN DEL MÉTODO SÍMPLEX.
5.1 Degeneración.
5.2 Óptimos alternativos.
5.3 Solución no acotada.
5.4 Solución no factible.

NOMBRE: LLINER HERNAN VARGAS ZAGACETA
CURSO: INVESTIGACION DE OPERACIONES
CICLO: III
CARRERA: INGENIERIA MECANICA






EL MÉTODO SIMPLEX
El método gráfico indica que la solución óptima de unprograma 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. Es- to se lograconvirtiendo 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 puedenobtener 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.
1. ESPACIO DE SOLUCIONES EN FORMA DE ECUACIÓN
Para estandarizar, la representaciónalgebraica del espacio de soluciones de programación lineal se forma bajo dos condiciones:
a. Todas las restricciones (excepto las de no negatividad) son ecuaciones con lado derecho no negativo.
b. Todas las variables son no negativas.
1.1 Conversión de desigualdades a ecuaciones.
En las restricciones (Š), el lado derecho se puede imaginar cómo representando el límite de disponibilidad de unrecurso, 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 larestricción. Por ejemplo, en el modelo de Reddy Mikks, la restricción asociada con el uso de la materia prima M1 está dada como
6x1 + 4x2…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:
6x1 + 4x2 + s1 = 24, s1 Ú 0
Prosigamos. Una restricción (Š) establece, normalmente, un límite inferior para las actividades del modelo deprogramació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.
La conversión de (Š) a (=) se logra restando una variable de excedencia, del lado izquierdo de la desigualdad. Por ejemplo, en el modelo de la dieta (Ejemplo 2.2-2), la restricción que representa los requisitos mínimos de alimento está dada como
x1 + x2 Ú800
Si se define a S1 como una variable de excedencia se puede convertir la restricción en la ecuación siguiente:
x1 + x2 - S1 = 800, S1 Ú 0
Es importante observar que las variables de holgura y de excedencia, s1 y S1, siempre son no negativas.
El único requisito que queda es que el lado derecho de la ecuación que resulte sea no negativo. Esta condición se puede satisfacer siempre, si es...