METODO SIMPLEX

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 ano 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 estandar, 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.

EJEMPLO:

Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

* Max 40*X1 + 60*X2
* s.a. 2*X1 + 1*X2 <= 70
* 1*X1 + 1*X2 <= 40
* 1*X1 + 3*X2 <= 90
* X1 >= 0 X2 >= 0

Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:

9102lf

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido “más negativo”. En este caso, X2.

Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos “Pivote” (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:

2n7jcjt

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

16k1fsh

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con “infinitas soluciones”.

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.

Table2_13

simplex-1

Visitas mas recursos:

DIAPOSITIVA METODO SIMPLEX

PDF METODO SIMPLEX

VIDEO DE PROGRAMACION LINEAL POR EL METODO SIMPLEX

EJERCICIOS RESUELTOS DE PROGRAMACION LINEAL POR EL METODO SIMPLEX

Esta entrada fue publicada en Sin categoría. Guarda el enlace permanente.

Una respuesta a METODO SIMPLEX

  1. wi7max dijo:

    Excelente aporte, haber si poseto algo asi en mi web, sobre IO

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