Evolucion De La Computadora

Método Simplex.

El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal.

El algorítmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con elconocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.

Las definiciones siguientes fundamentadas en 3 importantes teoremas, ayudan a entender la filosofía de este eficiente algorítmo.

Teoremas de la Programación Lineal.

1. El conjunto desoluciones factibles para un problema de P.L. es un conjunto convexo.

2. La solución óptima del problema de programación lineal , si existe, es un punto extremo (vértice) del conjunto de soluciones factibles. Si dicha solución óptima se tiene para más de un punto extremo, entonces también optimiza en cualquier punto que sea combinación convexa lineal entre los dos vértices que optimiza.

...ysuponiendo que la función objetivo fuera:

 Max zC = 6x1 + 4x2  6(2) + (6) = 36
Max zH = 6(4) + 4(3) = 36
Max zA = 6(0) + 4(6) = 24

Calcular P como CCL entre C y H con = ¼
P =  C + (1 - ) H
P = ¼ (2 , 6) + ( 1 – ¼) (4 , 3)
P = ( ½ , 3/2) + (3 , 9/4) = (7/2 , 15/4)

... y retomando el gráfico anterior:

ZP = 6 (7/2) + 4 (15/4) = 36

3.El número máximo de puntos extremos (vértices) por revisar en la búsqueda de la solución óptima del problema es finito y coincide con el número máximo de soluciones básicas únicas que se pueden determinar mediante el binomio...

m + n = m + n = (m+n) !
m n m! n!

Método Simplex Penal o de La ‘M’ Grande.

Como su nombre lo indica, consiste enpenalizar la inclusión de las variables artificiales en la función objetivo con un coeficiente ‘M’ muy grande que para el caso de maximizar es ‘¬- M’ y para el caso de minimizar es ‘+ M’.

La primera solución básica del simplex en tal caso, debe de incluir a todas las variables artificiales que fueron necesarias en el arreglo del modelo de programación lineal por resolver esto último porque lasvariables artificiales se utilizan precisamente para tomar la primera solución básica. A medida que se cumplen las etapas de cálculo en el simplex, las variables artificiales deberán de ir saliendo de la misma, en consecuencia del coeficiente ‘M’ muy grande.
Si se presenta el caso de que las variables artificiales no se logren sacar de la base y por lo tanto se anulen, ello significará que tal problemano tiene solución factible.

Ejemplo:

Max z = 4x1 + 3x2
Sujeta a:
x1 + x2  6 ..... (1)
2x1 - x2  0 ..... (2)
x1 = 2 ..... (3)
x2  0

Forma estándar.
Max z = 4x1 + 3x2
Sujeta a:
x1 + x2 - x3  6 ..... (1)
2x1 - x2 - x4  0 ..... (2)
x1 = 2 ..... (3)
x2 , x3 , x4  0...consiguiendo una base artificial....

x1 + x2 - x3 + 5  6 ..... (1)
2x1 - x2 - x4 + 6  0 ..... (2)
x1 + 7 = 2 ..... (3)

Var. Artificiales
x2 , x3 , x4 , 5 , 6 , 7  0

Penalizar la función objetivo.
Min z = 4x1 + 3x2 + M5 + M6 + M7

...debemos pasar al arreglo de tener el términoindependiente cero al lado derecho.
z - 4x1 - 3x2 - M5 - M6 - M7 = 0

Paso a la forma tabular del Método Símplex Penal.

BASE z x1 x2 x3 x4 5 6 7 SOLUCION
(Aquí i deberían tener coeficiente 0,  sigue z abajo) 1 -4 -3 0 0 -M -M -M 0
M(5)+Rz  z’ 1 M-4 M-3 -M 0 0 -M -M 6M
M(6)+Rz’ z’’ 1 3M-4 -3 -M -M 0 0 -M 6M
M(7)+Rz’’ z’’’ 1 4M-4 -3 -M -M...