PGDES

II.9 MÉTODO DE PENALIZACIÓN.
 
 
 
Si se tiene un problema de Programación Lineal, que no se encuentra expresado en forma canónica, es recomendable utilizar el Método de Penalización.
Las restricciones e inclusive las variables de holgura son presentadas como una igualdad o no-negativas, deberán introducirse variables artificiales (), que harán posible resolver el problema.
Existen variasmaneras de darle solución al problema planteado, dos de ellas son estos dos métodos de solución alternativa :
a. El Método de Penalización
b. El Método de Doble Fase.
 
Para lo cual debe seguirse un método que permita convertir en cero a la variable artificial para obtener una solución factible. A este método se le conoce como Método de la M Grande, o la Gran M,("Big M Method" en la literaturainglesa).
Este método radica en la introducción de la variable artificial que modifica a la función objetivo, que será a su vez multiplicada por una cantidad M, que describe un valor muy grande con signo negativo cuando se quiera maximizar y en caso de minimizar el valor arbitrario será positivo y muy elevado, que amplía el espacio de soluciones factibles.
Se tiene que:
Opt Z = Cx
Sujeto a :Ax  b y/o Ax = b
tal que Ax = b puede decirse como [ b.]
tenemos que para minimizar la función objetivo:
Mín Z= C x + M
S.a.
A x – Y + M = b
x0, Y0, M0.
 
 
 
Si se busca maximizar Z:
Max Z = C x – M 
S.a.
A x + Y – M = b
 
Se obtiene la solución óptima del problema sí y solo sí el vector M es igual con cero.
El Método Simplex trata en cada iteración mejorar la función objetivo.Si el problema original no tiene restricciones inconsistentes, el vector M, saldrá de la base por completo, o sea M = 0, se habrá retornado al problema original y se obtendrá por el Método Simplex la solución óptima.
En caso de haber utilizado el Método de la M, y haber llegado a la solución óptima; pero el vector M > 0, entonces el problema original no tiene solución, por las restriccionesinconsistentes del problema .
 
 
Método de la M Grande o de Penalización.
Los pasos a seguir son:
1. Expresar el problema en forma estándar, teniendo en cuenta que:
Todas las restricciones son ecuaciones, con excepción de la restricción de no-negatividad,
El valor de , o los valores de la extrema derecha de la tabla deben ser también no negativos.
Las variables x estarán expresadas en formano-negativa
La optimización de la función objetivo, puede ser de maximización o minimización.
Recordar que:
Mín Z = max H  max H = min (-Z)
1. Reescribir el problema
I. Haciendo igualdades las desigualdades, tomando en cuenta las variables de holgura y de exceso donde sean requeridas. De tal forma que:
 
 
 

 
II. Introducir las variables artificiales () en las restricciones que tengan lacaracterística ( b, = b ).
III. Asignar la penalización para cada unidad de las variables en la función objetivo designada como (–M) para problemas de maximización y (+M) para minimización , con M>0.
1. Elaborar la primera tabla con todo lo anterior señalado.
2. Mediante el uso de las operaciones de renglón elementales, a fin de expresar el coeficiente ( –M) en caso de maximizar, ó (+M) en elde minimizar , haciendo cero el valor de la variable artificial 
.
5. Continuar con el algoritmo del Método Simplex descrito anteriormente.
 
 
 
A continuación se presenta un problema de programación lineal1, que será resuelto por el Método de Penalización y que posteriormente, éste mismo se resolverá con el Método de las Dos Fases.
Min Z = 
Sujeto a las siguientes restricciones:
  4  6
 18
con  0, siendo j = 1, 2
0, 0, 0, 0, 0, 0.
 
 
 
Asignar la penalización a la función objetivo , que radica en colocar (+M) para problemas de maximización, e introducir la variable artificial (  ), quedando:

Min Z = + M 
Hacer la función objetivo igual a cero, y las restricciones expresadas en forma de igualdad, considerando las variables de exceso y superfluas.
De manera que:...