Ejercicios resueltos de programación matemática - Respuesta 2

En primer lugar, añadimos a todas las inecuaciones una variable de holgura:



De este sistema podemos tomar como solución básica :

x₁ = x₂ = x₃ ; x₄ = 6 ; x₅ = 6 ; x₆ = 2 → F_b = 0

En estas condiciones podemos construir la tabla del algoritmo simples, teniendo en cuenta las siguientes consideraciones:

1ª) Se construye una primera fila con una celda menos que las restantes y se coloca en ella, a partir de la tercera celda, los coeficientes de las variables de la función a minimizar, en orden creciente de los subíndices y haciendo nulos los coeficientes de las variables de holgura.

2ª) Se construye una segunda fila colocando debajo de cada uno de los números anteriores la variable correspondiente y a continuación tantas filas como condiciones restrictivas se tengan, anotando sus coeficientes en la columna correspondiente a cada variable.

3ª) Si hay n condiciones restrictivas, en las dos segundas columnas de la tabla y desde la tercera hasta la n+1 fila se colocan los coeficientes de las variables no nulas en la solución básica y los valores de dichas variables.

4ª) En la fila n+1 y a partir de la tercera columna, se colocan los valores C_q - F_q obtenidos de restar al elemento m-ésimo de la primera fila el producto a_i.v_mi.

5ª) En la celda correspondiente a la segunda fila, tercera columna, se coloca la suma de todos los productos de todos los pares de la tercera consideración (este valor corresponde al que toma la función a minimizar en la situación presente). Mas detalles a lo largo del texto.

A partir de las consideraciones anteriores podemos construir la tabla que viene a continuación. En ella buscaremos el llamado elemento pivote, que estará en la intersección de la columna cuya última fila sea más negativa y la fila que haga mínimo al cociente del elemento de la tercera columna con el de la considerada. Si hay varios elementos que cumplen dicha condición, se escoge uno.



Observamos que el valor C₂ - F₂ es el valor mas pequeño de todos los C_q - F_q y además negativo, por lo que no estamos en el punto óptimo y el vector a introducir en la base es el a₂.
En este caso no podemos aplicar los criterios de salida para sacar un vector de la base pero elegimos el a₄. De ese modo, el pivote es v₁₂ = 1. Todos los elementos de la fila del pivote quedan divididos por él y todos los de su columna se anulan excepto él. Para los demás elementos v_ij tomamos :



Para facilitar estas transformaciones se puede proceder por filas ya que en este caso se tendría, por ejemplo para la segunda:



En este caso v₂₂ = 1 y no se anula el factor correspondiente (salvo que sea nulo v_1j) pero podría ocurrir que v₂₂ fuera nulo y ello simplificaría las operaciones.
Para los elementos de la tercera columna que deban transformarse tomamos:



Esto salvo para el elemento que nos da el valor de la función (el primero de la columna) en la situación presente, que se calcula del mismo modo que para la tabla anterior. Para ello se cambian antes los elementos de la segunda columna escribiendo en su lugar el coeficiente según la función a minimizar, de cada una de las variables de la base. Finalmente, los elementos C_q - F_q se toman como en el caso de la primera tabla.



Vemos que el valor C₃ - F₃ es negativo por lo que estamos en el punto óptimo y el vector a introducir en la base es el a₃. Para determinar el vector que debe salir consideramos el criterio:



De ese modo el pivote para la nueva tabla es v₃₂ = 1 y con los pasos ya explicados se tendrá:



Tenemos que todos los C_q - F_q son positivos por lo que hemos llegado a la solución óptima para la que se tiene:

a₁ = 0 (no está en la base) ; a₃ = 0 ; a₂ = 6 → F_min(x ₁, x ₂, x ₃) = - 120