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.
El método simplex comienza con una solución factible y prueba si es o no óptima. Si no lo es, el método sigue a una mejor solución. Se dice mejor en el sentido de nueva solución no es óptima, entonces se repite el procedimiento. En algún momento el método simplex conduce a una solución óptima, si es que existe.
Además de ser eficiente, dicho método tiene otras ventajas. Es completamente mecánico (se utilizan matrices, operaciones elementales sobre renglones y aritmética básica). Asimismo, no implica el uso de geometría. Esto permite resolver problemas de programación lineal que tiene cualquier número de restricciones y variables.
El problema normal de programación lineal es de la forma.
Maximizar Z = C 1 X 1 + C 2 X 2 + ...................+ C n X n
Sujeto a: a 11x 1 + a 12 x 2 + ............................ a 1 n x n
b 1
a 12x 1 + a 22 x 2 + ............................ a 2 n x n
b 2
a m1x 1 + a m2 x 2 + ............................ a m n x n
b m
En donde x1 , x 2,..........x n y b 1 , b 2 , ................b m son no negativas.
Para aplicar el método simplex tenemos un ejemplo.
Maximizar Z = 3 x 1 + x 2
s.a. 2 x 1 + x 2
8
2 x 1 + 3x 2
12
x 1 , x 2
0
Se comienza expresar las restricciones en forma de ecuaciones. En la restricción 1 tenemos
2 x 1 + x 2
8 será igualdad si se añade algún número no negativo s 1 quedando.
2 x 1 + x 2 + s 1 = 8
a s 1 se le denomina variable de holgura puesto que absorbe la holgura o falta de consistencia que existe en el lado izquierdo de modo similar, la otra restricción puede escribirse:
2 x 1 + 3x 2 + s 2 = 12 a las variables x 1 , x 2 se les denomina variables estructurales. Ahora puede replantearse el problema en términos de ecuaciones:
maximizar Z = 3 x 1 + x 2
s.a. 2 x 1 + x 2 + s 1 = 8
2 x 1 + 3x 2 + s 2 = 12
La solución gráfica para este problema es:
(0,4)
(3,2)
(0,0) (4,0)
En el vértice (0,0) las dos variables valen cero. Por lo tanto, Z = 0
En cualquier vértice hay una solución factible. Básica (S.F.B.) de las cuatro variables al menos dos de ellas serán cero. Este 2 resulta de hacer una resta de m - n donde m es el número de restricciones y n él numero de variables del problema. m = 2 y n = 4 ; 4 - 2 = 2 . Para cualquier S:F.B. las dos variables que son iguales a cero sé denominar variables no básicas, en tanto que a las otras variables se denominan variables básicas para SFG.
La mejor forma de hacer este proceso es a través de técnicas matriciales que se basan en los métodos desarrollados en él capitulo inicial.
La ecuación o función objetivo se iguala a cero quedando:
Z - 3 x 1 - x 2 = 0
Resumiendo el problema queda:
Z - 3 x 1 - x 2 = 0
2 x 1 + x 2 + s 1 = 8
2 x 1 + 3 x 2 + s 2 = 12
estos datos se incorporan a una tabla que tendrá las siguientes columnas:
variable número coeficientes lado
básica de ecuación Z X 1 X 2 S 1 S 2 D
Bibliografía:
http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/simplex.html
