Método Simplex

Universidad Autónoma de Chiapas

Facultad de Ingeniería

Ingeniería Civil

Ingeniería de Sistemas

Asignatura

Ing. José Alejandro Jiménez Gordillo

Catedrático

Problemas de programación lineal por el método “soluciones básicas” e Investigación del Método Simplex con 2 ejemplos

Trabajo

Ricardo Rodríguez Alvarez

Alumno

6º “C”

Tuxtla Gutiérrez, Chiapas, Lunes 4 de Marzo del 2013

Método Simplex

En el año 1947 el doctor George Dantzig presentó el algoritmo que desarrolló y que denominó simplex. A partir de este logro se pudieron resolver problemas que por más de un siglo permanecieron en calidad de estudio e investigación con modelos formulados pero no resueltos. El desarrollo paralelo de la computación digital, hizo posible su rápido desarrollo y aplicación empresarial a todo tipo de problemas.

El método simplex disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles. El algoritmo simplex utiliza el conocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordan y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro de un conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices factibles. También se consigue con eficiencia, debido a que se dirige la búsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica; seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo.

El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono, o de las aristas del poliedro, si el número de variables es mayor. Cómo el número de vértices y de aristas es finito, siempre se podrá encontrar la solución.

El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.

PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

Esta es la forma estándar del modelo:

Función objetivo: c1•x1 + c2•x2 + ... + cn•xn

Sujeto a: a11•x1 + a12•x2 + ... + a1n•xn = b1

a21•x1 + a22•x2 + ... + a2n•xn = b2

...

am1•x1 + am2•x2 + ... + amn•xn = bm

x1,..., xn ≥ 0

Para ello se deben cumplir las siguientes condiciones:

El objetivo es de la forma de maximización o de minimización.

Todas las restricciones son de igualdad.

Todas las variables son no negativas.

Las constantes a la derecha de las restricciones son no negativas.

Cambio del tipo de optimización.

Si en nuestro modelo, deseamos minimizar, podemos dejarlo tal y como está, pero deberemos tener en cuenta nuevos criterios para la condición de parada (deberemos parar de realizar iteraciones cuando en la fila del valor de la función objetivo sean todos menores o iguales a 0), así como para la condición de salida de la fila. Con objeto de no cambiar criterios, se puede convertir el objetivo de minimizar la función F por el de maximizar F•(-1).

Ventajas: No deberemos preocuparnos por los criterios de parada, o condición de salida de filas, ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todas sus variables básicas positivas, y además las restricciones sean de desigualdad "≤", al hacer el cambio se quedan negativas y en la fila del valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por defecto el valor óptimo que se obtendría es 0.

Solución: En la realidad no existen este tipo de problemas, ya que para que la solución quedara por encima de 0, alguna restricción debería tener la condición "≥", y entonces entraríamos en un modelo para el método de las Dos Fases.

Conversión de signo de los términos independientes (las constantes a la derecha de las restricciones)

Deberemos preparar nuestro modelo de forma que los términos independientes de las restricciones sean mayores o iguales a 0, sino no se puede emplear el método Simplex. Lo único que habría que hacer es multiplicar por "-1" las restricciones donde los términos independientes sean menores que 0.

Ventaja: Con ésta simple modificación de los signos en la restricción podemos aplicar el método Simplex a nuestro modelo.

Inconvenientes: Puede resultar que en las restricciones donde tengamos que modificar los signos de las constantes, los signos de las desigualdades fueran ("=", "≤"), quedando ("=","≥") por lo que en cualquier caso deberemos desarrollar el método de las Dos Fases. Este inconveniente no es controlable, aunque nos podría beneficiar si sólo existen términos de desigualdad ("≤","≥"), y los "≥" coincidieran con restricciones donde el término independiente es negativo.

Si en nuestro modelo aparece una inecuación con una desigualdad del tipo "≥", deberemos añadir una nueva variable, llamada variable de exceso si, con la restricción si ≥ 0. La nueva variable aparece con coeficiente cero en la función objetivo, y restando en las inecuaciones.

Surge ahora un problema, veamos cómo queda una de nuestras inecuaciones que contenga una desigualdad "≥”:

a11•x1 + a12•x2 ≥ b1 a11•x1 + a12•x2 - 1•xs = b1

Como todo nuestro modelo, está basado en que todas sus variables sean mayores o iguales que cero, cuando hagamos la primera iteración con el método Simplex, las variables básicas no estarán en la base y tomarán valor cero, y el resto el valor

...