Metodo M o Penalizacion

Método M o Penalizacion:

El Método M se inicia con la P.l en forma de ecuación.Si la ecuacion no tiene una holgura (o una variable que pueda desempeñar el papel de una), se agrega una VARIABLE ARTIFICIAL , Ri , para formar una solucion inicial procede a la solucion basica de total holgura.

Sin embargo, las VARIABLES ARTIFICIALES en formar parte del problema original, y se requiere un "Artificio" de modelado para IGUALARLAS A CERO en el momento que se alcance la iteracion OPTIMA (suponiendo que el problema tenga una solucion factible )

La meta deseada se logra PENALIZANDO estas variables en la funcion objetivo utilizando la siguiente regla: 

Regla de penalizacion para variables Artificiales:

Dado M, un valor positivo suficientemente grande ( matemáticamente (M       00), el coeficiente objetivo de una variable artificial representa una penalizacion apropiada si : 

Los Pasos Básicos del Método M o Penalizacion son los siguientes: 

1.-Exprese el problema en forma Estándar transformando las inecuaciones inecuaciones introduciendo variables de Holgura. (X1;X2;X3 o Cualquier variable) 

2.-Agrega VARIABLES NO NEGATIVAS al lado izquierdo de cada de las ecuaciones correspondientes a las restricciones de tipo (>=  o  <= ).Estas variables se denominan VARIABLES ARTIFICIALES y su adición hace que las restricciones sean correspondientes.

3.-Utiliza las VARIABLES ARTIFICIALES en la solucion basica inicial., sin embargo la funcion objetivo de la tabla inicial se prepara adecuadamente para expresarse en términos de las variables no básicas únicamente. 

4.-Proceda con los pasos regulares del metido simplex.

EJEMPLOS:
1.-Realizar en siguiente ejercicio por el Método M :

                                                          Maximizar  Z= 4x1 + x2 

                                         sujeto a : 

3x1 + x2      = 3

4x1 + 3x2 >= 6

x1 + 2x2   <= 4

SOLUCIÓN:

1º Iniciamos analizando las restricciones y agregando variables a cada uno de ello :

Mazimizar Z = 4X2 + X2 + MR1 + MR2 

Z= 4X1 + X2 + 0X3 +  MR1 + MR2 + 0X4

Z - 4X1 - X2 - 0X3 -  MR1 - MR2 - 0X4 = 0 

                        Sujeto a : 

3X1 + X2  = 3

4X1 + 3X2 -X3 = 6 

X1 + 2X2 + X4 +X4 = 4 

X1,X2,X3,X4 >= 0

Se le agrega la VARIABLE ARTIFICIAL  donde no hay variable de HOLGURA:

3X1 + X2 + R1 = 3

4X1 + 3X2 -X3 + R2 = 6

X1 + 2X2 +X4 = 4 

X1,X2,X3,X4 >=0

R1,R2 >= 0

Solución Básica :  (R1,R2,X4)

                                       (3,6,4)

2ºColocamos los datos en las Tablas:

Nueva Fila Z = anterior fila +100 (fila X1 + filaX2) 

           

Escogemos el valor mínimo:

                                                     

                

                                              

 

Z = 3.4 

X1 = 0.4

X2 = 1.8 

X3 = 1

3ºIngresamos los Valores en Tora:

Read More

Examen Parcial de Programacion Lineal

1.- Demuestre algebraicamente que todas las soluciones básicas de la siguiente P.L son no factibles.

Maximizar Z = x1 + 3x2 

Sujeto a : 

   x1 + x2 <= 2 

- x1 + x2 <= 4

x1 , x2 >=  0

Solución

1°Igualamos las Variables y colocamos la Variable de Holgura:

Maximizar Z =  x1 + 3x2 + 0S1 + 0S2 

x1 + x2 + S1 = 2 

- x1 + x2  + S2 = 4

x1 , x2 >=  0

S1 , S2 >= 0

2°Colocamos los Valores en la tabla:

3°Colocamos los valores en el Programa Tora:

5°Observamos los Valores en la Gráfica;

6°Nos dan los siguientes Valores : 

2.- Considere el problema :

Minimizar Z = 4x1 - 8x2 + 3x3

Sujeto a :

x1 + x2 + x3 = 7                          (1) 

2x1 - 5x2 + x3 >= 10                      (2)       

x1 , x2 ,x3 >= 0

Solución

1°Igualamos las Variables :

z - 4x1 + 8x2 - 3x3 = 0

Sujeto a : 

   X1 + X2 + X3 = 7 

                                                                   

2X1 - 5X2 + X3 - S2 = 10

X1 ; X2 ; X3 >= 0

2° Colocamos los Valores en las Tablas:

             

3.- Considere el problema :

Maximizar  Z = 16x1 + 15x2

Sujeto a :

40x1 + 31x2 <= 124

- x1 + x2 <= 1

x1           <=3

       x1 , x2  > = 0  

Solución

Read More

Ejercicios de Modelo de P.L en forma de una Ecuacion

Ejercicios de un Modelo de Programación Lineal en Forma de una Ecuación:

Demuestra algebraicamente que todas las soluciones básicas de la siguiente Programación Lineal son no factibles:

Maximizar Z = X1 + X2 

Sujeto a :

                    X1 + 2X2 <= 6                                        (1)

                    2X1 + X2 <= 16                                      (2)

                     X1;X2      >=0

Solución:

Utilizaremos los siguientes Pasos;

1ª Hallamos los valores de X1 ; X2 :

• X1  = 0               X2  =  3
• X2 = 0                X1  =  8

 

• X1  = 0                 X2  =  16
• X2 = 0                  X1  =  8

2ªLos reemplazamos en la Tabla:

3ªUbicamos los puntos en la Gráfica; Unimos los puntos mas cercanos 

4ªIngresamos los datos al Programa Tora;

5ªObseramos la Grafica :

6ªNos dan los siguientes valores:

• Z   = 6.00
• X1 = 6.00
• X2 = 0.00

Read More

Método Simplex

Resumen del Método Simple:

En problemas  de Minimizacion , la CONDICIÓN ES OPTIMALIDAD   requiere seleccionar la VARIABLE DE ENTRADA como la VARIABLE NO BÁSICA con el coeficiente mas positivo en la ecuación objetiva, la regla exacta opuesta del caso de maximizacion. Esto obedece a que:

Max Z = min(-z)

En cuanto a la Condición de factibilidad para seleccionar la variable de salida . la regla no cambia.

Condición de Optimilidad:

La Variable de entrada en un problema la Maximizacion es la variable no Básica con el coeficiente mas negativo (positivo) en la Fila Z .

Condición de Factibilidad:

Tanto en Problemas  de Maximizacion como de Minimizacion, la variable de salida es la variable básica asociada con la relación mínima no negativa.  

Operaciones de Filas de GAUSS-JORDAN:

1.-Fila Pivote:

• Reemplace  la variable de salida en la columna básica por la variable de entrada.

• Nueva Fila Pivote. = Fila Pivote Actual / Elemento Pivote.

• Nueva Fila = ( Fila Actual ) - (Coeficiente en la columna pivote ) X (Nueva fila pivote} 
• Todas las Demas filas, incluida la Z

          Nueva Fila = ( Fila Actual ) - (Coeficiente en la columna pivote ) X (Nueva fila pivote} 

Los Pasos de Método Simplex son :

1. Determine la solución factible básica inicial 
2. Selecciona una variable de entrada Utilizando la condición de optimalidad. Deténgase si no hay Variable de Entrada; la ultima condición es Optima. De otro modo, prosiga con el siguiente paso.
3. Selecciona una variable de salida utilizando la condición de factibilidad .
4. Aplique en los cálculos de Gauss - Jordan para determinar la nueva solución básica.
5. Vaya al paso.

Ejemplos del Método Simplex:

1.-Considere la siguiente P.L:

Maximizar Z= 16x1 + 15x2

                   Sujeto a:

       

   40x1 + 31x2 <= 124

-x1 + x2       <= 1

   x1             <= 3

x1;x2           >= 0

Solución:

 1ª.-Igualamos:

Z = 16x1 + 15x2 + 0s1 + 0s2 + 0s3

 Z - 16x1 - 15x2 - 0s1 - 0s2 - 0s3 = 0

40x1 + 31x2 + s1 = 124

-x1 + x2  + s2 = 1

x1  + s3 = 3

x1;x2 = 0

1ª Iteracion:

2ªIteracion:

3ªIteracion:

2ªIngresamos los datos en el Programa Tora:

3ªNos dan los siguientes Valores:

Z = 55.61

x2 =2.31

s3 = 1.69

x1 = 1.31

Read More