Programación lineal

FORMULACIÓN

1. IDENTIFICAR LAS VARIABLES DE DECISIÓN (X1, X2, X3….. Xn)
2. ESTABLECER EL  OBJETIVO (FUNCIÓN OBJETIVO):   MAX Z  (GANANCIAS)  O   MIN Z (COSTOS)
3. IDENTIFICAR LAS RESTRICCIONES (PUEDEN SER > =, =, < =)
4. COLOCAR  LA RESTRICCIÓN DE NO NEGATIVIDAD (Xi >=0)

MÉTODO GRÁFICO

1. CONDICIÓN PARA APLICAR EL MÉTODO: QUE EL MODELO SOLO TENGA 2 VARIABLES
2. GRAFICAR TODAS LAS RESTRICCIONES
3. IDENTIFICAR LA REGIÓN FACTIBLE
4. EVALUAR LOS PUNTOS DE CORTE DE LA REGIÓN FACTIBLE EN LA FUNCIÓN OBJETIVO
5. TOMAR LA DECISIÓN DE ACUERDO A LOS VALORES DE Z (SI SE ESTÁ MAX SE ESCOGE ELPUNTO  QUE DE MAYOR RESULTADO, SI SE ESTÁ MIN SE ESCOGE EL PUNTO QUE  DE MENOR RESULTADO)
6. CONCLUIR

MÉTODO SIMPLEX

1. VERIFICAR CONDICIONES:

• QUE TODAS LAS RESTRICCIONES SEAN DEL TIPO < =
• QUE LOS VALORES DEL LADO DERECHO DE LAS RESTRICCIONES SEAN NO NEGATIVOS ( REVISAR SI SE PUEDEN ARREGLAR LAS RESTRICCIONES)

1. ESTANDARIZAR EL MODELO (AGREGANDO VARIABLES DE HOLGURA,+S,  A CADA RESTRICCIÓN)
2. HACER LA TABLA DE INICIO:

• INICIAR CON TODAS LAS VARIABLES DE HOLGURA COMO VARIABLES BÁSICAS
• EL RENGLON Z INICIA CON TODOS LOS SIGNOS CONTRARIOS A LA FUNCIÓN OBJETIVO ORIGINAL

1. SE BUSCA PRIMERO QUIEN ENTRA A LA SOLUCIÓN:

• SI EL PROBLEMA ES DE MAX ENTRA LA VARIABLE NO BÁSICA CUYO VALOR DE Z SEA EL MÁS NEGATIVO DE LOS NEGATIVOS
• SI EL PROBLEMA ES DE MIN ENTRA LA VARIABLE NO BÁSICA CUYO VALOR DE Z SEA EL MÁS POSITIVO  DE LOS POSITIVOS.
• DESPUES DE IDENTIFICAR QUIEN ENTRA A LA SOLUCIÓN, SE BUSCA QUIEN SALE, HALLANDO LA RAZÓN: PARA HALLAR LA RAZÓN, SE DIVIDEN LOS ELEMENTOS DE LA SOLUCIÓN ENTRE LOS ELEMENTOS DE LA COLUMNA PIVOTE (VARIABLE QUE ENTRA)…TOMANDO EN CUENTA QUE LOS ELEMENTOS DE LA COLUMNA PIVOTE DEBEN SER POSITIVOS, NO PUEDEN SER CERO NI NEGATIVOS. SEA DE MAX O MIN, SALE DE LA SOLUCIÓN LA VARIABLE BÁSICA CUYA RAZÓN SEA EL VALOR NO NEGATIVO MÁS PEQUEÑO.

1. EN ESTE PUNTO YA SABEMOS QUIEN ES LA COLUMNA PIVOTE (VARIABLE DE ENTRADA), RENGLON PIVOTE (VARIABLE DE SALIDA) Y ELEMENTO PIVOTE (ELEMENTO DE LA INTERSECCIÓN ENTRE LA COLUMNA PIVOTE Y RENGLON PIVOTE)
2. INICIAMOS LAS ITERACIONES:

• PRIMERO SE CALCULA EL NUEVO RENGLÓN PIVOTE(N.R.P)-DONDE OCURRE EL INTERCAMBIO ENTRE LA VARIABLE QUE ENTRA Y LA QUE SALE- CON LA SIGUIENTE FÓRMULA:

N.R.P= VIEJO RENGLÓN / ELEMENTO PIVOTE

• LUEGO SE CALCULAN LOS DEMÁS RENGLONES (INCLUYENDO Z), CON LA SIGUIENTE FÓRMULA:

DEMÁS RENGLONES= VIEJO RENGLÓN – ELEMNTO QUE TIENE LA VARIABLE EN LA COLUMNA PIVOTE*N.R.P

1. SE SIGUE ITERANDO HASTA QUE NO EXISTA VARIABLE DE ENTRADA.
2. CONCLUIR

MÉTODO DE LA M

1. VERIFICAR CONDICIONES:

• QUE AL MENOS UNA DE LAS RESTRICCIONES SEA DIFERENTE DE < =
• QUE EL LADO DERECHO DE LAS RESTRICCIONES SEAN NO NEGATIVOS ( REVISAR SI SE PUEDEN ARREGLAR LAS RESTRICCIONES)

1. ESTANDARIZAR EL MODELO (HOLGURA(+Si) PARA LAS RESTRICCIONES <= Y SUPERÁVIT(-Si) PARA LAS RESTRICCIONES >=
2. AGREGAR UNA VARIABLE ARTIFICIAL (+Ri) EN CADA RESTRICCIÓN DONDE NO HAY VARIABLE DE HOLGURA
3. PENALIZAR LA FUNCIÓN OBJETIVO: CADA VARIABLE ARTIFICIAL QUE SE AGREGÓ A LAS RESTRICCIONES SE COLOCAN EN LA FUNCIÓN OBJETIVO CON UN COEFICIENTE M…. SI EL PROBLEMA ES DE MAX SE LE AÑADE –MRi…. SI EL PROBLEMA ES DE MIN SE LE AÑADE +MRi
4. HACER LA TABLA DE INICIO:

• INICIAR CON TODAS LAS VARIABLES DE HOLGURA Y ARTIFICIALES COMO VARIABLES BÁSICAS.
• EL RENGLON Z INICIA CON TODOS LOS SIGNOS CONTRARIOS A LA FUNCIÓN OBJETIVO  (YA PENALIZADA)

1. SE CALCULA EL NUEVO Z CON LA SIGUIENTE FÓRMULA:

NUEVO Z= VIEJO Z ± MRi   (SI ES DE MIN ES +MRi, SI ES DE MAX ES –MRi)                        

1. SE HACE OTRA TABLA CON EL NUEVO Z (LO DEMÁS QUEDA IGUAL)
2. SE EMPIEZA A ITERAR APLICANDO NORMALMENTE EL MÉTODO SIMPLEX:

• SE BUSCA PRIMERO QUIEN ENTRA A LA SOLUCIÓN:

• SI EL PROBLEMA ES DE MAX ENTRA LA VARIABLE NO BÁSICA CUYO VALOR DE Z SEA EL MÁS NEGATIVO DE LOS NEGATIVOS
• SI EL PROBLEMA ES DE MIN ENTRA LA VARIABLE NO BÁSICA CUYO VALOR DE Z SEA EL MÁS POSITIVO  DE LOS POSITIVOS.
• DESPUES DE IDENTIFICAR QUIEN ENTRA A LA SOLUCIÓN, SE BUSCA QUIEN SALE, HALLANDO LA RAZÓN: PARA HALLAR LA RAZÓN, SE DIVIDEN LOS ELEMENTOS DE LA SOLUCIÓN ENTRE LOS ELEMENTOS DE LA COLUMNA PIVOTE (VARIABLE QUE ENTRA)…TOMANDO EN CUENTA QUE LOS ELEMENTOS DE LA COLUMNA PIVOTE DEBEN SER POSITIVOS. SEA DE MAX O MIN, SALE DE LA SOLUCIÓN LA VARIABLE BÁSICA CUYA RAZÓN SEA EL VALOR NO NEGATIVO MÁS PEQUEÑO.

• EN ESTE PUNTO YA SABEMOS QUIEN ES LA COLUMNA PIVOTE (VARIABLE DE ENTRADA), RENGLON PIVOTE (VARIABLE DE SALIDA) Y ELEMENTO PIVOTE (ELEMENTO DE LA INTERSECCIÓN ENTRE LA COLUMNA PIVOTE Y RENGLON PIVOTE)
• SE EMPIEZA A ITERAR:

• PRIMERO SE CALCULA EL NUEVO RENGLÓN PIVOTE(N.R.P)-DONDE OCURRE EL INTERCAMBIO ENTRE LA VARIABLE QUE ENTRA Y LA QUE SALE- CON LA SIGUIENTE FÓRMULA:

N.R.P= VIEJO RENGLÓN / ELEMENTO PIVOTE

• LUEGO SE CALCULAN LOS DEMÁS RENGLONES (INCLUYENDO Z), CON LA SIGUIENTE FÓRMULA:

DEMÁS RENGLONES= VIEJO RENGLÓN – ELEMNTO QUE TIENE LA VARIABLE*N.R.P

1. SE SIGUE ITERANDO HASTA QUE NO EXISTA VARIABLE DE ENTRADA.
2. CONCLUIR

MÉTODO DUAL SIMPLEX

1. VERIFICAR CONDICIONES:

• QUE AL MENOS UNA DE LAS RESTRICCIONES SEA DIFERENTE DE < =
• SI EXISTE UN = SE CONVIERTE LA RESTRICCIÓN EN DOS RESTRICCIONES (UNA >= Y LA OTRA <=)

1. ESTANDARIZAR EL MODELO (HOLGURA(+Si) PARA LAS RESTRICCIONES <= Y SUPERÁVIT(-Si) PARA LAS RESTRICCIONES >=
2. SE MULTIPLICAN TODAS LAS RESTRICCIONES DONDE HAY SUPERÁVIT (-Si) POR -1 …. DE TAL MANERA QUE TODO QUEDE +Si
3. HACER LA TABLA DE INICIO:

• INICIAR COMO VARIABLES BÁSICAS CON TODAS LAS VARIABLES DE HOLGURA Y LAS SUPERÁVIT CONVERTIDAS EN +S.

1. SE EMPIEZA A ITERAR:

• SE BUSCA PRIMERO QUIEN SALE DE LA SOLUCIÓN:

• SEA DE MAX O MIN SALE LA VARIABLE BÁSICA CUYO VALOR SEA EL MÁS NEGATIVO DE LOS NEGATIVOS (EN LA COLUMNA DE SOLUCIÓN).
• LUEGO SE BUSCA QUIEN ENTRA: PARA ESTO SE DEBE HALLAR LA PROPORCIÓN, DIVIDIENDO LOS ELEMENTOS DEL RENGLON Z (SOLO DE LAS VARIABLES NO BÁSICAS) ENTRE LOS ELEMENTOS DEL RENGLON PIVOTE (VARIABLE DE SALIDA), TOMANDO EN CUENTA QUE LOS ELEMENTOS A DIVIDIR (DEL RENGLON PIVOTE) DEBEN SER NEGATIVOS.

SI EL PROBLEMA ES DE MINIMIZAR SE COLOCA VALOR ABSOLUTO  A LA PROPORCIÓN, SI ES DE MAXIMIZAR NO SE COLOCA VALOR ABSOLUTO… LUEGO SE ELIGE EL MAS PEQUEÑO DE LA PROPORCIÓN.  

...