Metodo simplex

I S

NGENIERIA

E

N

ISTEMAS

ING. YALEDDYS K. GAVIDIA R

I
S

E

ING. YALEDDYS K. GAVIDIA R.

HISTORIA La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. E llaposguerra, muchas iindustrias llo usaron en t t h t 1947 En h d ti su planificación diaria.

ING. YALEDDYS K. GAVIDIA R.

DEFINICION Es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo.

ING. YALEDDYS K. GAVIDIA R.

METODO SIMPLEX El método del simplex se utiliza, sobretodo, para resolver problemas de programación lineal en los que intervienen tres o más variables. Emplea un proceso iterativo que inicia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible t hasta f tibl a otro, h t que se ll llega por últi all punto ó ti último t óptimo.

ING. YALEDDYS K. GAVIDIA R.

METODO SIMPLEX
Grafica 01.Muestra la secuencia de soluciones.

ING. YALEDDYS K. GAVIDIA R.

METODO SIMPLEX
• • Determinar una solución básica factible inicial Prueba de optimidad: Determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos (>= 0). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva soluciónbásica factible inicial. • Condición de factibilidad: Para todos C di ió d f tibilid d P t d llos problemas d maximización y minimización, variable que bl de i i ió i i i ió i bl sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente. • • Seleccionar las variables de holgura como las variables básicas de inicio. Selecciona una variable que entrade entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.

ING. YALEDDYS K. GAVIDIA R.

METODO SIMPLEX
• • Realizar el paso iterativo Se determina la variable básica entrante mediante la elección de la variable con el coeficientenegativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote. • Se determina S d t i lla variable bá i que sale; para esta, se t i bl básica l t toma cada coeficiente positivo ( 0) d lla d fi i t iti (>0) de columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, seidentifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación. • Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces:

ING.YALEDDYS K. GAVIDIA R.

METODO SIMPLEX
renglón pivote nuevo = renglón pivote antiguo / número pivote para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xi en los otros renglones, para realizar este cambio se g utiliza la siguiente fórmula: renglón nuevo = renglón antiguo - ( coeficiente de la columnapivote x renglón pivote nuevo) cuando el coeficiente es negativo se utiliza la fórmula: renglón nuevo = renglón antiguo + (coeficiente de la columna pivote x renglón pivote nuevo) ING. YALEDDYS K. GAVIDIA R.

Ejemplo Nº 01 Ej l
La empresa Vidrios Venezolanos C.A. produce vidrios de una alta calidad, donde se incluye ventanas con marco de madera y ventanas con marco de aluminio. Posee tres...