Variables Artificiales

Variables artificiales
El procedimiento para iniciar programas lineales de “mal comportamiento” con restricciones (=) y (≥) es permitir que variables artificiales desempeñen el trabajo de holguras en la primera iteración, para después, en alguna iteración posterior, desecharlas en forma legítima.
Se desarrolla para este tipo dos métodos:
1.- “Técnica M o Método de penalización”
2.- “Técnicade las dos fases”
Técnica M
Los pasos de la técnica M son los siguientes:
1. Expresa el problema en la forma estándar
2. Agregue variables no negativas al lado izquierdo de cada una de las ecuaciones correspondientes a las restricciones de los tipos (≥) y (=), estas variables se denominan variables artificiales y su adición hace que se infrinjan las restricciones correspondientes. Estadificultad se elimina haciendo que las variables artificiales sean igual a cero (siempre que exista la solución del problema). Esto se logra asignando una penalización muy grande por unidad a estas variables de la función objetiva. Tal penalización se designara como –M para problemas de Maximización y +M para problemas de minimización y m>0.
3. Utilice las variables artificiales de lasolución básica inicial.
4. Proceden con los pasos regulares del método simplex.
Ejemplo 1
Considere el problema:
Minimizar
x0=4x1+x2
Sujeto a:
3x1+x2=3
4x1+3x2≥6
x1+2x2≤4

x1,x2≥0

La forma estándar está dada como:
Minimizar:
x0=4x1+x2
Sujeto a:
3x1+x2=3
4x1+3x2-S1=6
x1+2x2+S2=4
x1,x2,S1,S2,≥0
La primera y segunda ecuaciones no tienen variables que desempeñen la función de unaholgura. Por lo tanto, aumentamos las dos variables artificiales R1 y R2 en estas dos ecuaciones de la manera siguiente:
3x1+x2+R1=3
4x1+3x2-S1+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:x0=4x1+x2+MR1+MR2
Sujeto a:
3x1+x2+R1=3
4x1+3x2-S1+R2=6
x1+2x2+S2=4
x1,x2,S1,S2,R1,R2≥0
Solución de inicio:
Básica | x0 | x1 | x2 | S1 | R1 | R2 | S2 | Solución |
x0 | 1 | -4 | -1 | 0 | -M | -M | 0 | 0 |
R1 | 0 | 3 | 1 | 0 | 1 | 0 | 0 | 3 |
R2 | 0 | 4 | 3 | -1 | 0 | 1 | 0 | 6 |
S2 | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 4 |

Habiendo construido una solución factible inicial, debemos condicionar elproblema de modo que cuando lo pongamos en forma tabular, la columna del lado derecho producirá la solución inicial en forma directa. Esto se hace mediante el uso de las ecuaciones de restricciones para sustituir R1 y R2 en la función objetivo. De manera que:
R1=3-3x1-x2
R2=6-4x1-3x2+S1
Nueva ecuacion x0= Ec. x0 anterior+MEcR1+MEcR2
Por lo tanto la función objetivo se convierte en:x0=4x1+x2+M3-3x1-x2+M6-4x1-3x2+S1
=(4-7M)x1+1-4Mx2+MS1+9M
De tal manera la tabla queda de la siguiente forma:
Básica | x0 | x1 | x2 | S1 | R1 | R2 | S2 | Solución |
x0 | 1 | -4+7M | -1+4M | -M | 0 | 0 | 0 | 9M |
R1 | 0 | 3 | 1 | 0 | 1 | 0 | 0 | 3 |
R2 | 0 | 4 | 3 | -1 | 0 | 1 | 0 | 6 |
S2 | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 4 |

La variable que entra es la que tiene mayor coeficiente positivo.
R133=1
R2 64=1.5 Min 1,1.5, 3
S2 31=3

Entra x1 y sale R1

Nuevo x0= Ec. x0 anterior+(4-7M)x1actual
R2actual=R2anterior+-4x1actual

1 | -4+7M | -1+4M | -M | 0 | 0 | 0 | 9M |
0 | 4-7M | (4-7M/3) | 0 | 4-7M/3 | 0 | 0 | 4-7M |
1 | 0 | 1/3+5/3M | -M | 4/3-M | 0 | 0 | 4+2M |
| | | | | | ||

Básica | x0 | x1 | x2 | S1 | R1 | R2 | S2 | Solución |
x0 | 1 | 0 | 1/3+5/3M | -M | 4/3-7/3M | 0 | 0 | 4+2M |
x1 | 0 | 1 | 1/3 | 0 | 1/3 | 0 | 0 | 1 |
R2 | 0 | 0 | 5/3 | -1 | -4/3 | 1 | 0 | 2 |
S2 | 0 | 0 | 5/3 | 0 | -1/3 | 0 | 1 | 3 |

La variable que entra es la que tiene mayor coeficiente positivo.
x1 11/3=3
R2...