Inicio > Sin categoría > METODO SIMPLEX

METODO SIMPLEX

El método simplex  y su utilización en la programación de programación lineal

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 del 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.

Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:

Maximizar Z= f(x,y)= 3x + 2y
sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x0 , y 0

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL

Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por:

  • Min          c1x1  + c2x2  + … + cnxn
  • sa            a11x1 + a12x2 + … + a1nxn = b1
  • a21x1 + a22x2 + … + a2nxn = b2
  • …          …                  …
  • am1x1 + am2x2 + … + amnxn = bm
  • xi >=  0,   i = 1, 2, …, n    y    m <= n

Matricialmente escrito como:

Min cTx
s.a      Ax = b
x >=  0

No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:

  • EJEMPLO
  • P)            Max        9u + 2v + 5z
  • sa            4u + 3v + 6z <=  50
  • u + 2v – 3z >=  8
  • 2u – 4v + z = 5
  • u,v >=  0
  • z e IR
  1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= – f(x), para todo x factible. En consecuencia:  x* es también mínimo de  -f(x)
  2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
  3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
  4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

Considerando la siguiente notación: u = x1, v = x2, z = x3 – x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:

  • Min         – 9×1 – 2×2 – 5×3 + 5×4 + 0x5 + 0x6
  • sa:              4×1 + 3×2 + 6×3 – 6×4 +    x5          = 50
  • x1 + 2×2 – 3×3 + 3×4             – x6  =  8
  • 2×1 – 4×2 +  x3   –   x4                     =  5
  • xi >=  0,    i=1,2,3,4,5,6.
Categorías:Sin categoría
  1. Aún no hay comentarios.
  1. No trackbacks yet.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: