Docente: Rosario Mamani Investigación Operativa Capitulo Nro.
Método de las variables artificiales
Sabemos que el método simplex inicia cuando se tiene una solución factible y las
restricciones son de la forma ≤ (menor igual que). Además, una solución factible
ocurre en el origen de coordenadas. ¿Qué sucede cuando el origen no es solución
factible? Cuando las restricciones son de la forma (mayor igual que) ≥ o son
restricciones de igualdad (=), el origen no es una solución factible. El problema ahora
radica en encontrar una solución básica inicial. Para ello estudiaremos dos métodos:
El Método de la M o método penalizado y el método de Dos Fases.
Variable artificial
Una variable artificial es aquella que define una dirección auxiliar que se utiliza para
llegar hacia la región de factibilidad de un problema de PL.
Se utiliza una variable artificial cuando las restricciones son de la forma: ≥ (mayor
igual que) o = (igualdad)
El procedimiento para iniciar un problema de PL con restricciones “≥” e “=” es
utilizar variables artificiales que desempeñan el papel de holguras en la primera
iteración, y que luego se desechan en una iteración posterior.
Método de la gran M
Consiste en modificar nuestra función objetivo restando de ella las variables
artificiales afectadas del coeficiente M, el cual se supone positivo y tan grande como
se quiera.
En esta forma no hay duda que Z alcanzará su valor máximo cuando todas las
variables artificiales sean cero.
Sí al final de una iteración todos los coeficientes de la F.O. Son no negativos y el valor
de Z depende de M el problema es incompatible.
Regla de penalización para variables artificiales
Dado que M, un valor positivo suficientemente grande (matemáticamente M→ꝏ), el
coeficiente objetivo de una variable artificial representa una penalización apropiada
si:
–M en PPL Maximización
Coeficiente en la F.O. de la Var. Artificial = +M en PPL Minimización
Procedimiento de resolución del PPL
1. Expresar el problema en forma estándar.
2. Sumar variables no negativas ai aquellas restricciones de la forma: ≥ ó =,
estas variables se llaman variables artificiales.
3. Los coeficientes de las variables artificiales en la F.O. serán –M para
problemas de maximización y +M para problemas de minimización.
4. Se usa las variables artificiales para la solución básica inicial y se procede a
aplicar el simplex hasta obtener la solución óptima
17
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
Ejemplo 4.
Estandarizando el PL
Max Z 3x 1 5x 2 Max Z 3x 1 5x 2 0h1 0h2 Ma1
Sujeto a: Despejando
x1 4 Z 3x 1 5x 2 0h1 0h2 Ma1 0
2x 2 12 x1 h1 4
3x 1 2x 2 18 2x 2 h2 12
x 1, x 2 0 3x 1 2x 2 a1 18
V. B. Z x1 x2 h1 h2 a1 L. D.
Z 1 -3 -5 0 0 M 0
h1 0 1 0 1 0 0 4
h2 0 0 2 0 1 0 12
a1 0 3 2 0 0 1 18
Recuerde que todos sus coeficientes de las variables básicas deben ser nulos (cero) en
la F.O. en nuestro ejemplo el coeficiente de la variable artificial es M entonces
anulemos este coeficiente con la siguiente operación
f1 Mf4 f1
V. B. Z x1 x2 h1 h2 h3 L. D.
Z 1 -3-3M -5-2M 0 0 0 -18M
h1 0 1 0 1 0 0 4
h2 0 0 2 0 1 0 12
a1 0 3 2 0 0 1 18
Cuando la variable artificial salga de la base en ese momento a 0 y esto nos indica
que hemos regresado al problema original, pero si se llega a que, a 0 , entonces el
problema no tiene solución. Estamos en condiciones de aplicar el método simplex
hasta llegar a una solución óptima.
Primera iteración
V. B. Z x1 x2 h1 h2 h3 L. D.
18
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
Segunda iteración
V. B. Z x1 x2 h1 h2 h3 L. D.
Tercera iteración
V. B. Z x1 x2 h1 h2 h3 L. D.
Para transformar un PPL a su forma estándar usaremos la siguiente tabla de TUGER
Tipos de Adición en la restricción Coeficiente de la F.O.
restricción
≤ + Variable holgura 0
= + Var. Artificial +M (Min) -M (Max)
≥ + Var artificial -Var holgura +M (Min) -M (Max
Ejemplo 5. Resolver
Min Z 0.4x 1 0.5x 2 Max Z 0.4x 1 0.5x 2
Sujeto a: Sujeto a:
0.3x 1 0.1x 2 2.7 0.3x 1 0.1x 2 2.7
0.5x 1 0.5x 2 6 0.5x 1 0.5x 2 6
0.6x 1 0.4x 2 6 0.6x 1 0.4x 2 6
x 1, x 2 0 x 1, x 2 0
Solución Estandarizando y penalizando el modelo
19
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
Max Z 0.4x 1 0.5x 2 0h1 Ma1 Ma2 0h2
Z 0.4x 1 0.5x 2 0h1 Ma1 Ma2 0h2 0
0.3x 1 0.1x 2 h1 2.7
0.5x 1 0.5x 2 a1 6
0.6x 1 0.4x 2 a2 h2 6
x 1, x 2 , a1, a2 , h1, h2 0
V. B. Z x1 x2 h1 a1 a2 h2 L. D.
Z -1 0.4 0.5 0 M M 0 0
h1 0 0.3 0.1 1 0 0 0 2.7
a1 0 0.5 0.5 0 1 0 0 6
a2 0 0.6 0.4 0 0 1 -1 6
Recuerde que todos sus coeficientes de las variables básicas deben ser nulos (cero) en
la Función Objetivo por lo tanto realizamos operaciones elementales de fila, para
volver cero a los coeficientes de las variables artificiales a1 y a2.
f1 Mf3 Mf4 f1
-Mf3 -0.5M -0.5M 0 -M 0 0 -6M
-Mf4 -0.6M -0.4M 0 0 -M M -6M
f1 0.4 0.5 0 M M 0 0
-M f3-Mf4+f1 0.4-1.1M 0.5-0.9M 0 0 0 M -12M
Sustituyendo en la primera fila Z estamos en condiciones de aplicar el simplex.
V. B. Z x1 x2 h1 a1 a2 h2 L. D.
Z -1 0.4-1.1M 0.5-0.9M 0 0 0 M -12M
h1 0 0.3 0.1 1 0 0 0 2.7
a1 0 0.5 0.5 0 1 0 0 6
a2 0 0.6 0.4 0 0 1 -1 6
Primera iteración
V. B. Z x1 x2 h1 a1 a2 h2 L. D.
Segunda iteración
V. B. Z x1 x2 h1 a1 a2 h2 L. D.
20
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
Método de las dos faces
El método de las dos fases elimina el uso de la constante y se resuelve en dos fases:
Primera Fase.
Se trata de encontrar una solución básica factible donde la F.O. debe ser minimizar
ya sea un problema de maximización o minimización
1ºPaso. Estandarizar las restricciones agregando variables de holgura y artificiales
según sea el caso de cada desigualdad.
2ºPaso. Analicemos la F.O.
Sustituimos los coeficientes de las variables de decisión cx por ceros.
Las variables artificiales tienen coeficiente 1 en la F.O.
Las variables de holgura tienen coeficiente 0 en la F.O.
3ºPaso. Construir la tabla inicial como el método de la gran M. Esta fase termina
cuando la F.O. (artificial) es nula, es decir: Z 0 y todas las variables artificiales
salen de la base.
Segunda Fase
Consideramos la F.O. original y resolvemos utilizando como base inicial la obtenida
en la 1era fase sin considerar las columnas de las variables artificiales. La solución
óptima de la 2da fase es la solución óptima del problema original.
Ejemplo 4. Resolver
Min Z 0x 1 0x 2 0x 3 0h1 1a1
Max Z 3x 1 2x 2 4x 3
Z 0x 1 0x 2 0x 3 0h1 1a1 0
S .A 3x 1 3x 2 5x 3 120
S .A 3x 1 3x 2 5x 3 h1 120
2x 1 x 2 3x 3 60
2x 1 x 2 3x 3 a1 60
x 1, x 2 , x 3 0
x 1, x 2 , x 3 , h1, a1 0
Solución 1º Fase
V. B. Z x1 x2 x3 h1 a1 L. D.
1 0 0 0 0 -1 0
h1 0 3 3 5 1 0 120
a1 0 2 1 3 0 1 60
Para que a1 sea variable básica su coeficiente debe ser nulo, entonces realicemos
operaciones elementales de fila f1 f3 f1
21
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
V. B. Z x1 x2 x3 h1 a1 L. D.
1 2 1 3 0 0 60
+ Positivo
h1 0 3 3 5 1 0 120
a1 0 2 1 3 0 1 60 Fila Pivote
1º V. B. Z x1 x2 x3 h1 a1 L. D.
Itera. 1 0 0 0 0 -1 0
h1 0 -1/3 4/3 0 1 -5/3 20
x3 0 2/3 1/3 1 0 1/3 20
2º Fase. Formulamos el problema y preparemos la tabla para la segunda fase
Max Z 3x 1 2x 2 4x 3 0h1
Z 3x 1 2x 2 4x 3 0h1 0
V. B. Z x1 x2 x3 h1 L. D.
1 -3 -2 -4 0 0
h1 0 -1/3 4/3 0 1 20
x3 0 2/3 1/3 1 0 20
1º V. B. Z x1 x2 x3 h1 L. D.
Itera. 1 -1/3 -2/3 0 0 80
h1 0 -1/3 4/3 0 1 20
Fila Pivote x3 0 2/3 1/3 1 0 20
V. B. Z x1 x2 x3 h1 L. D.
1 -1/3 -2/3 0 0 80
x2 0 -1/4 1 0 3/4 15
x3 0 2/3 1/3 1 0 20
2º V. B. Z x1 x2 x3 h1 L. D.
Itera. 1 -1/2 0 0 1/2 90
x2 0 -1/4 1 0 3/4 15
Fila x3 0 3/4 0 1 -1/4 15
Pivote
V. B. Z x1 x2 x3 h1 L. D.
1 -1/2 0 0 1/2 90
x2 0 -1/4 1 0 3/4 15
x1 0 1 0 4/3 -1/3 20
3º V. B. Z x1 x2 x3 h1 L. D.
Itera. 1 0 0 2/3 1/3 100
x2 0 0 1 -1/3 5/6 20
x1 0 1 0 4/3 -1/3 20
Ejemplo 5. Resolver por el método de las dos faces
22
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
PRIMERA FASE
Max Z 5 x1 7 x 2 3 x3 Z a1 0
Sujeto a: Min Z 0 x1 0 x 2 0 x3 0h1 0h 2 0h3 a1
4 x1 3 x 2 2 x3 75 4 x1 3 x 2 2 x3 h1 75
x1 2 x 2 3 x3 100 x1 2 x 2 3 x3 h2 100
x1 x 2 x3 20 x1 x 2 x3 h3 a1 20
x1, x 2, x3 0 x1, x 2, x3, h1, h 2, h3, a1 0
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z 0 0 0 0 0 0 -1 0
h1 4 3 2 1 0 0 0 75
h2 1 2 3 0 1 0 0 100
a1 1 1 1 0 0 -1 1 20
Para que a1 sea variable básica su coeficiente debe ser nulo, entonces realicemos
operaciones elementales de filas Z=a1+Z
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z 1 1 1 0 0 -1 0 20
h1 4 3 2 1 0 0 0 75
h2 1 2 3 0 1 0 0 100
a1 1 1 1 0 0 -1 1 20
Como estamos minimizando elegimos el valor más positivo en la fila Z
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z 0 0 0 0 0 0 -1 0
h1 2 1 0 1 0 2 -2 35
h2 -2 -1 0 0 1 3 -3 40
x3 1 1 1 0 0 -1 1 20
SEGUNDA FASE
Min Z 5 x1 7 x 2 3x3 0h1 0h2 0h3
Z 5 x1 7 x 2 3x3 0h1 0h2 0h3 0
V.B. x1 x2 x3 h1 h2 h3 L.D.
Z 5 7 3 0 0 0 0
h1 2 1 0 1 0 2 35
h2 -2 -1 0 0 1 3 40
x3 1 1 1 0 0 -1 20
V.B. x1 x2 x3 h1 h2 h3 L.D.
Z -2 0 -4 0 0 7 -140
23
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
h1 1 0 -1 1 0 3 15
h2 -1 0 1 0 1 2 60
x2 1 1 1 0 0 -1 20
V.B. x1 x2 x3 h1 h2 h3 L.D.
Z -2 0 -4 0 0 7 -140
h3 1/3 0 -1/3 1/3 0 1 5
h2 -1 0 1 0 1 2 60
x2 1 1 1 0 0 -1 20
V.B. x1 x2 x3 h1 h2 h3 L.D.
Z -13/3 0 -5/3 -7/3 0 0 -175
h3 1/3 0 -1/3 1/3 0 1 5
h2 -5/3 0 5/3 -2/3 1 0 50
x2 4/3 1 2/3 1/3 0 0 25
Como no existen valores positivos en la F.O. el problema termina con: x2=25 y un
óptimo de Min (-Z) = -175 el modelo es equivalente a Max Z=175
Ejemplo 5. Resolver por el método penalizado
Max Z 5 x1 7 x 2 3 x3 Max Z 5 x1 7 x 2 3 x3 0h1 0h 2 0h3 Ma1
Sujeto a: Z 5 x1 7 x 2 3 x3 0h1 0h 2 0h3 Ma1 0
4 x1 3 x 2 2 x3 75 4 x1 3 x 2 2 x3 h1 75
x1 2 x 2 3 x3 100 x1 2 x 2 3 x3 h2 100
x1 x 2 x3 20 x1 x 2 x3 h3 a1 20
x1, x 2, x3 0 x1, x 2, x3, h1, h 2, h3, a1 0
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z -5 -7 -3 0 0 0 M 0
h1 4 3 2 1 0 0 0 75
h2 1 2 3 0 1 0 0 100
a1 1 1 1 0 0 -1 1 20
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z -5-M -7-M -3-M 0 0 M 0 -20M
h1 4 3 2 1 0 0 0 75
h2 1 2 3 0 1 0 0 100
a1 1 1 1 0 0 -1 1 20
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z -5-M -7-M -3-M 0 0 M 0 -20M
h1 4 3 2 1 0 0 0 75
h2 1 2 3 0 1 0 0 100
a1 1 1 1 0 0 -1 1 20
24
Docente: Rosario Mamani Investigación Operativa Capitulo Nro.2
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z 2 0 4 0 0 -7 7+M 140
h1 1 0 -1 1 0 3 -3 15
h2 -1 0 1 0 1 2 -2 60
x2 1 1 1 0 0 -1 1 20
V.B. x1 x2 x3 h1 h2 h3 a1 L.D.
Z 2 0 4 0 0 -7 7+M 140
h3 1/3 0 -1/3 1/3 0 1 -1 5
h2 -1 0 1 0 1 2 -2 60
x2 1 1 1 0 0 -1 1 20
Z 13/3 0 5/3 7/3 0 0 M 175
h3 1/3 0 -1/3 1/3 0 1 -1 5
h2 -5/3 0 5/3 -2/3 1 0 0 50
x2 4/3 1 2/3 1/3 0 0 0 25
25
