Toma Penali

LUIS CALDERÓN YARLEQUE
ERICKA EVANGELISTA MENDOZA

METODO DEPENALIZACIÓN

METODO DE PENALIZACIÓN
El método de la gran M consiste en
modificar el problema original para dar
lugar a un nuevo problema agregando una
variable Wllamada artificial y que se
penalizara mediante un costo “M” de
valores grandes y positivos, y esto permite
que la función objetivo tome valores muy
grandes.
Cuando W salga dela base en ese
momento W=0 y esto indica haber
regresado al problema original, pero si se
llega a W>0, entonces el problema no
tendrá solución.
MinZ= Cx + Mw
Sujeta a las restricciones y penalizando a
Zw1 - Cw

PRIMERA
REGLA
R1: Variable Artificial
S1 : Super Ábit
Entonces :
= : R1
≥ : -S1 + R1
≤ : S1

EJERCICIO :
Describimos este método por el sgte problema
Minimizar z = 4X1 + X2
Sujeto a :3X1+ X2 = 3
4X1+3X2 ≥6
X1+2X2 ≤0
X1.X2 ≥0
 La forma estandar de este modelo es entonces

Minimizar z= 4X1+X2
Sujeto a :
3X1+X2+
4X1 +3X2–X3
X1+2X2
+X4
X1.X2.X3.X4

=3
=6
=4
≥0

La primera y segunda ecuaciones no tienen variables que desempeñan la
función de una holgura . Por lo tanto, aumentamos las dos variables artificiales
R1 y R2 en estas dos ecuaciones de la manera siguiente:

3X1 + X 2
+ R1=3
4X1+3X2 – X3
+R2 =6
Podemos penalizar a R1 y R2 en la función objetivo asignándoles coeficientes positivos
muy grandes en la función objetivo . Sea M>0 una constante muy grande : entonces la
programación lineal con su variable artificial se transforma en
Minimizar Z = 4X1 + X2 + MR1+MR2
Sujeto a :

3X1+X2
+ R1 = 3
4X1+ 3X2 – X3 + R2 = 6
X1+ 2X2
+ X4 = 4
X1.X2.X3.R1.X4 ≥0

Obsérvese la razón deluso de las variables artificiales. Tenemos tres ecuaciones y seis
incógnitas. Por lo tanto, la solución básica inicial 6- 3 = 3 variables con valor cero. Si
colocamos X1, X2 Y X3 en el nivel cero, inmediamente obtenemos la solución R1= 3, R2= 6
y X4 = 4 , que es la solución factible inicial que se necesita
Variables Basica

Variables No Básica

R1 = 3

X1 =

0

R2 = 6

X2 =

0

X4 = 4

X3 =

0Ahora, obsérvese la forma como el “nuevo” modelo
hace que R1 y R2 sea cero , como realizamos un
proceso de minimización, asignando M a R1 y R2 en la
función objetivo, el proceso optimización que busca el
valor mínimo de Z asignará , por ultimo, valores de cero
a R1 y R2 en la solución optima

¿Cómo cambia la técnica M si maximizamos en vez de minimizar? Mediante el
uso de la misma lógica depenalizar la variable artificial, debemos asignarles el
coeficiente – M de la función objetivo (M > 0), con lo cual se vuelve poco
atractivo mantener la variable artificial en un nivel positivo en la solución
optima
4X1 + X2 + MR1 + MR2
R1 = 3 – 3X1 –X2
R2 = 6 – 4X2 -3X2 + X3
Por lo tanto, la función objetivo se convierte en :
Z= 4X1 + X2 + M (3 – 3X1 – X2 ) + M(6 – 4X1 – 3X2) + M (6 – 4X1 – 3X2 + X3)Z= (4 – 7M)X1 + (1- 4M)X2 + MX3 + 9M
Y la ecuación Z ahora figura en la tabla se convierte en
Z – (4- 7M)X1 – (1- 4M)X2 – MX3 = 9
Entonces X1= X2 = X3 = O , el valor de Z = 9 , como debe ser
R1= 3 Y R2= 6

Plasmamos lo obteniendo en la diapositiva anterior , en la tabla establecida con los datos
correspondiente.
BÁSICA

X1

X2

X3

R1

R2

X4

SOLUCIÓN

Z

-4+7M

-1+4M

-M

0

0

0

9M

R1

3

10

1

0

0

3/3= 1

R2

4

3

-1

0

1

0

6/4 = 1.5

X4

1

2

0

0

0

1

4/1 = 4

Primer paso : encontramos el mayor numero negativo ,
en la columna X1, en donde dividimos la solución con la
columna seleccionada ; para hallar la fila Pivot , como el
método simplex .

Z

0

1+ 5M

-M

4-7M

0

0

4M + 2M

X1

1

1/3

0

1/3

0

0

1

R2

0

5/3

-1

-4/3

1

0

2

X4

0

5/3

0

-1/3

0

1

3Columna Pivot principal
Piv.R1

Piv.Z

Piv.R2

Piv.X4

3

-(-4+7M)

4

1

 Para hallar la segunda tabla , aplicamos la sgte formula
Nvo Reglón : Renglón Anterior
Pivot
 Luego aplicamos la sgte formula para hallar :
el renglón Z, R2 , S4 = (- Pivot * Nvo Renglón)+ R.A
Ejemplo : -(-4+7M * 1) + (-4+7M) = 0

Aplicamos la misma formula en esta tabla para encontrar la solución

Z

0

0

1/5

8/5-M...