Cuestionario 6

1. Un programa lineal está en forma estándar si todas las restricciones son de igualdad y todas las variables son no negativas.

Si alguna de las restricciones no es de igualdad, se convierte en una restricción de igualdad añadiendo una variable de holgura no negativa que indica lo que le falta a la restricción para saturarse:

i) Si la restricción es de la forma a_j₁x₁+ a_j₂x₂+ … + a_jnx_n≤ b_j, se suma una variable de holgura x_n₊₁≥ 0 de manera que la restricción queda a_j₁x₁+ a_j₂x₂+ … + a_jnx_n+ x_n₊₁ = b_j.

ii) Si la restricción es de la forma a_j₁x₁+ a_j₂x₂+ … + a_jnx_n≥ b_j, se resta una variable de holgura x_n₊₁≥ 0 de manera que la restricción queda a_j₁x₁+ a_j₂x₂+ … + a_jnx_n- x_n₊₁ = b_j.

2. Un programa lineal está en forma estándar si todas las restricciones son de igualdad y todas las variables son no negativas.

Si alguna de las variables x_ino está sujeta a restricción de no negatividad, se sustituye en el programa por la diferencia de dos variables no negativas, es decir, se considera el cambio x_i = u_i - v_i, con u_i≥ 0 y v_i ≥ 0.

3. La solución asociada a una tabla del Algoritmo del Simplex se obtiene dando el valor 0 a las variables no básicas y los valores bi de la tabla (columna b) a las variables básicas.

4. En el algoritmo del simplex para un problema de maximización, el criterio de optimalidad es zj - cj ≥ 0 para todo j, ya que -(zj - cj) es lo que aumenta la función objetivo por cada unidad de variable xj.

5. Al aplicar el algoritmo del simplex en un programa lineal, el criterio de óptimo y el criterio de entrada dependen de si el programa es de minimización o de maximización.

Si es de minimización: el criterio de óptimo es zj - cj ≤ 0 para todo j; y en caso de que esta condición no se verifique, el criterio de entrada establece que la variable no básica que entra en la base es la que tiene mayor zj – cj.
Si es de maximización: el criterio de óptimo es zj - cj ≥ 0 para todo j; y en caso de que esta condición no se verifique, el criterio de entrada establece que la variable no básica que entra en la base es la que tiene menor zj – cj.

6. Criterio de salida en el algoritmo del simplex

Este criterio es el mismo ya sea el programa lineal de minimización o de maximización. Suponiendo que entra como variable básica la variable xj, se considera la correspondiente columna Aj pudiendo ocurrir:

· si existen elementos aij (i = 1, … ,m) positivos entonces se calcula el mínimo de los cocientes de los valores entre las variables básicas en la tabla actual y estos aij. La variable que pasa a ser no básica es la correspondiente a dicho mínimo.

· si todos los elemento aij (i = 1, … ,m) son cero o negativos, entonces la función objetivo en el conjunto factible no está acotada inferiormente si el programa es de minimización y no está acotada superiormente si el programa es de maximización y, por tanto, el programa no tiene solución óptima finita.

Notar que si el criterio de salida se aplica mal, en la tabla siguiente aparecerá una variable básica con valor negativo, lo que no puede ser ya que no cumpliría las restricciones de no negatividad.

7. En el algoritmo del simplex para pasar de una tabla a la siguiente únicamente se pueden realizar ciertas operaciones elementales, que son:

· Multiplicar por un número no nulo la fila en la que está el elemento pivote.

· Sumar a cualquier otra fila, el resultado de multiplicar la fila en la que está el elemento pivote por un número.

8. Al aplicar el algoritmo del simplex en un programa lineal, si en la tabla correspondiente a una solución óptima algún zj - cj de una variable no básica es 0, entonces la solución óptima no es única, sino múltiple. Además:

· si en la correspondiente columna de esa variable no básica hay algún elemento positivo entonces hay existe un segmento de soluciones óptimas.

· si en la correspondiente columna de esa variable no básica todos los elementos son negativos o cero entonces existe una semirrecta de soluciones óptimas.

9. Al aplicar el algoritmo del simplex en un programa lineal, si en la tabla correspondiente a una solución óptima algún zj - cj de una variable no básica es 0, entonces la solución óptima no es única, sino múltiple. Además:

· si en la correspondiente columna de esa variable no básica hay algún elemento positivo entonces hay existe un segmento de soluciones óptimas.

· si en la correspondiente columna de esa variable no básica todos los elementos son negativos o cero entonces existe una semirrecta de soluciones óptimas.

10. Al aplicar el algoritmo del simplex en un problema de minimización (maximización), si en una tabla algún zj - cj > 0 (zj - cj < 0) y todos los elementos de la columna Aj son negativos o cero, entonces la función objetivo no está acotada inferiormente (superiormente) en el conjunto factible y, por tanto, el programa no tiene solución óptima finita.

11. Si al aplicar el algoritmo del simplex en un programa lineal, se añade alguna variable artificial para obtener una solución factible básica inicial asociada a la matriz identidad, esta variable se introduce en la función objetivo como sigue:

· Si el programa es de minimización con un coeficiente M, siendo M tan grande como se quiera.

· Si el programa es de maximización con un coeficiente -M, siendo M tan grande como se quiera.

De esta forma se penaliza que la variable artificial sea una variable básica, es decir, se le fuerza a que, si es posible, pase a ser una variable no básica.

12. Si al aplicar el algoritmo del simplex en un programa lineal, se añade alguna variable artificial para obtener una solución factible básica inicial asociada a la matriz identidad (método de las penalizaciones), y en la tabla correspondiente a una solución óptima, existe una variable básica artificial, entonces el programa inicial no tiene solución ya que el conjunto factible es vacío.

13. Dado una programa lineal en forma estándar cuyas restricciones de igualdad viene dadas por Ax = b, con A una matriz de orden mxn, se define:

· solución básica como una solución x = (x_Bl x_N) donde x_B son las variables básicas y viene dadas por x_B= B^-1b siendo B la submatriz regular de A formada por las m columnas de las variables básicas y x_N = 0 son las variables no básicas.

· solución básica factible como una solución básica que es factible, es decir, que sus variables básicas son no negativas, x_B ≥ 0.

Para construir la tabla asociada a esta solución factible básica se ha de tener en cuenta que:

· Las columnas asociadas a las variables básicas son las de la matriz identidad.

· Las columnas asociadas a las variables no básicas son B^-1A_j, donde A_j es la columna j de la matriz A inicial.