VARIABLES ARTIFICIALES

DR. LUIS REY DÍAZ BARRÓN

SOLUCIÓN ARTIFICIAL

 Los modelos que implican restricciones (=) o (≥) no ofrecen una conveniente solución factible básica
 Para solucionar el mal comportamiento de estas restricciones se utilizan variables artificiales
 Desempeñan el papel de variables de holgura en la primera iteración
 Se desechan en la iteración posterior
 Veremos dos métodos para atacar este tema
 Método M
 El Método de dos fases
MÉTODO 𝑀

 Vamos agregar la variable artificial 𝑅𝑖 , para formar una solución inicial parecida a la solución básica de total
holgura.
 Las variables artificiales no forman parte del problema original,.
 Se requiere un procedimiento para igualarlas a cero en el momento que se alcance la iteración óptima.
 Regla de penalización para variables artificiales
 Dado un 𝑀, un valor positivo suficientemente grande, matemáticamente (M → ∞), el coeficiente objetivo de una variable
artificial representa una penalización apropiada si:

−𝑴, 𝒆𝒏 𝒑𝒓𝒃𝒍𝒆𝒎𝒂𝒔 𝒅𝒆 𝒎𝒂𝒙𝒊𝒎𝒊𝒛𝒂𝒄𝒊ó𝒏

Coeficiente objetivo de la variable artificial =ቊ
𝑴, 𝒆𝒏 𝒑𝒓𝒐𝒃𝒍𝒆𝒎𝒂𝒔 𝒅𝒆 𝒎𝒊𝒏𝒊𝒎𝒊𝒛𝒂𝒄𝒊ó𝒏
EJEMPLO

 Minimizar 𝑧 = 4𝑥1 + 𝑥2

Sujeto a
3𝑥1 + 𝑥2 = 3
4𝑥1 + 3𝑥2 ≥ 6
𝑥1 + 2𝑥2 ≤ 4
𝑥1 , 𝑥2 ≥ 0
EJEMPLO
 Si utilizamos 𝑠1 como una variable de superávit en la segunda restricción y 𝑠2 como una variable de holgura en la
tercera restricción:

3𝑥1 + 𝑥2 = 3
4𝑥1 + 3𝑥2 − 𝑠1 = 6
𝑥1 + 2𝑥2 + 𝑠2 = 4
𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 ≥ 0
EJEMPLO

 La primera y segunda ecuación no tienen variables de holgura, por lo tanto , agregamos las variables artificiales 𝑅1
y 𝑅2 .
 Además de la penalización a la función objetivo con 𝑀𝑅1 + 𝑀𝑅2
Minimizar 𝑧 = 4𝑥1 + 𝑥2 + 𝑀𝑅1 + 𝑀𝑅2
Sujeto a
3𝑥1 + 𝑥2 + 𝑅1 = 3
4𝑥1 + 3𝑥2 − 𝑥3 + 𝑅2 = 6
𝑥1 + 2𝑥2 + 𝑥4 = 4
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑅1 , 𝑅2 ≥ 0
EJEMPLO

 La solución del problema requiere que se remplace 𝑀 con un valor numérico (suficientemente grande).
 El valor de 𝑀 depende de los datos de la programación original.
 La penalización 𝑀 debe ser lo bastante grande con respecto a los coeficientes objetivos originales.
 No es conveniente que 𝑀 sea innecesariamente grande ya que ello nos puede conducir a un grave error de
redondeo.
EJEMPLO

 Utilizando 𝑀 = 100

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑧 -4 -1 0 -100 -100 0 0
𝑅1 3 1 0 1 0 0 3
𝑅2 4 3 -1 0 1 0 6
𝑥4 1 2 0 0 0 1 4
EJEMPLO

 El lado derecho de la fila 𝑧 en la tabla muetra 𝑧 = 0.

 Sin embargo dad la solución no básica 𝑥1 = 𝑥2 = 𝑥3 = 0, la solución básica actual es 𝑅1 = 3, 𝑅2 = 6 y 𝑥4 = 4, la
cual da 𝑧 = 900.
 Esta inconsistencia se deriva del hecho de que los coeficientes de 𝑅1 y 𝑅2 no son cero.
 Para eliminar la inconsistencia, tenemos que sustituir 𝑅1 y 𝑅2 en la fila 𝑧

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑧 696 399 -100 0 0 0 0
𝑅1 3 1 0 1 0 0 3
𝑅2 4 3 -1 0 1 0 6
𝑥4 1 2 0 0 0 1 4
EJEMPLO

 El resultado es que 𝑅1 y 𝑅2 ahora se sustituyen en la fila 𝑧 con 𝑧 = 900, como se deseaba.

 Aplicamos las condiciones de optimalidad y factibilidad de simplex.

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑧 696 399 -100 0 0 0 0
𝑅1 3 1 0 1 0 0 3
𝑅2 4 3 -1 0 1 0 6
𝑥4 1 2 0 0 0 1 4
EJEMPLO

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑧 0 167 -100 -232 0 0 204
𝑥1 1 1/3 0 1/3 0 0 1
𝑅2 0 5/3 -1 -4/3 1 0 2
𝑥4 0 5/3 0 1/3 0 1 3

2
 Continuando con los cálculos simplex, se requiere dos iteraciones más para alcanzar el óptimo 𝑥1 = , 𝑥2 =
5
9 17
,𝑧 = .
5 5
MÉTODO DE DOS FASES

 El método de dos fases elimina el uso de la constante 𝑀.

 Como su nombre lo indica el método se divide en dos fases:
 Fase I:
 Poner el problema en ecuaciones.
 Agregar las variables artificiales necesarias.
 Determinar una solución básica de la ecuación resultante que siempre minimice la suma de las variables artificiales,
independientemente de si la PL es de maximización o minimización.
 Si el valor mínimo es cero, prosiga con la fase dos.
 Fase II:
 Use la solución factible de la fase I como una solución básica inicial para el problema original.
EJEMPLO

 Utilizamos el mismo problema del ejemplo anterior

 Fase I
Minimizar 𝑟 = 𝑅1 + 𝑅2
Sujeto a
3𝑥1 + 𝑥2 + 𝑅1 = 3
4𝑥1 + 3𝑥2 − 𝑥3 + 𝑅2 = 6
𝑥1 + 2𝑥2 + 𝑥4 = 4
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑅1 , 𝑅2 , ≥ 0
EJEMPLO

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑟 0 0 0 -1 -1 0 0
𝑅1 3 1 0 1 0 0 3
𝑅2 4 3 -1 0 1 0 6
𝑥4 1 2 0 0 0 1 4

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝟏 𝑹𝟐 𝒙𝟒 Solución
𝑟 0 0 0 -1 -1 0 0
𝑥1 1 0 1/5 3/5 -1/5 0 3
𝑥2 0 1 -3/5 -4/5 3/5 0 6/5
𝑥4 0 0 1 1 -1 1 1
EJEMPLO

3 6
 Como el mínimo 𝑟 = 0 la fase I produce la solución básica 𝑥1 = , 𝑥2 = y 𝑥4 = 1.
5 5

 En este punto las variables artificiales ya cumplieron su misión, y podemos eliminar sus columnas de la tabla y
continuar con la fase II
 Fase II
 Después de eliminar las columnas artificiales, escribimos el problema original como:
Minimizar 𝑧 = 4𝑥1 + 𝑥2
Sujeto a
1 3
𝑥1 + 𝑥3 =
5 5
3 6
𝑥2 − 5 𝑥3 = 5
𝑥3 + 𝑥4 = 1
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
EJEMPLO

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 Solución
𝑧 -4 -1 0 0 0
𝑥1 1 0 1/5 0 3/5
𝑥2 0 1 -3/5 0 6/5
𝑥4 0 0 1 1 1

Básica 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 Solución
𝑧 0 0 1/5 0 18/5
𝑥1 1 0 1/5 0 3/5
𝑥2 0 1 -3/5 0 6/5
𝑥4 0 0 1 1 1
EJEMPLO

 Como estamos minimizando, 𝑥3 debe entrar en la solución . La aplicación del método simplex producirá el
óptimo en una iteración.
 La eliminación de las variables artificiales y sus columnas al final de la fase I sólo puede ocurrir cuando todas son
no básicas.
 Si una o más variables son básicas, entonces su eliminación requiere:
 Seleccione una variable artificial cero que salga de la solución básica y designe su fila como pivote. La variable de entrada
puede ser cualquier variable no básica (y no artificial) con un coeficiente diferente de cero. Realice la iteración simplex.
 Elimine la columna de la variable artificial de la table.
 Si se eliminaron todas las variables artificiales, continúe con la fase II.
 De lo contrario, regrese al paso anterior.