PROBLEMAS RESUELTOS DE MATEMÁTICAS
ejercicios resueltos de optimización

Ver enunciado del ejercicio en:

Problemas de optimización

Estás en : Matemáticas y Poesía > Problemas resueltos

 

Ejercicios de programación matemática

Respuesta del ejercicio 2
En primer lugar, añadimos a todas las inecuaciones una variable de holgura:
    \( \begin{array}{cccccccc} x_1 & + x_2 &  & + x_4 &  &  & = & 6 \\  & x_2 & + x_3 &  & + x_5 &  & = & 6 \\ x_1 &  & + x_3 &  &  & + x_6 & = & 2 \end{array} \)
De este sistema podemos tomar como solución básica :
    \( x_1 = x_2 = x_3 = 0 \; ; \; x_4 = x_5 = 6 \; ; \; x_6 = 2 \rightarrow 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 Cq - Fq obtenidos de restar al elemento m-ésimo de la primera fila el producto ai.vmi.
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.

  c -10 -20 -3 0 0 0
ab cb 0 a1 a2 a3 a4 a5 a6
a4 0 6 1 1 0 1 0 0
a5 0 6 0 1 1 0 1 0
a6 0 2 1 0 1 0 0 1
Cq - Fq     -10 -20 -3 0 0 0


Observamos que el valor C2 - F2 es el valor mas pequeño de todos los Cq - Fq y además negativo, por lo que no estamos en el punto óptimo y el vector a introducir en la base es el a2.
En este caso no podemos aplicar los criterios de salida para sacar un vector de la base pero elegimos el a4. De ese modo, el pivote es v12 = 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 vij tomamos :
    \( \displaystyle v'_{ij} = v_{ij}- \left(\frac{v_{lj}}{v_{lk}}\right)·v_{ik},\;\textrm{con } i\neq 1\Rightarrow v'_{ij} = v_{ij}- \left(\frac{v_{1j}}{v_{12}}\right)·v_{i2} \)
Para facilitar estas transformaciones se puede proceder por filas ya que en este caso se tendría, por ejemplo para la segunda:
    \( \displaystyle v'_{2j} = v_{2j}- \left(\frac{v_{1j}}{v_{12}}\right)·v_{22} \)
En este caso v22 = 1 y no se anula el factor correspondiente (salvo que sea nulo v1j) pero podría ocurrir que v22 fuera nulo y ello simplificaría las operaciones.
Para los elementos de la tercera columna que deban transformarse tomamos:
    \( \displaystyle x'_i = x_i- \left(\frac{x_l}{v_{lk}}\right)·v_{ik} \)
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 Cq - Fq se toman como en el caso de la primera tabla.

  c -10 -20 -3 0 0 0
ab cb -120 a1 a2 a3 a4 a5 a6
a2 -20 6 1 1 0 1 0 0
a5 0 0 -1 0 1 -1 1 0
a6 0 2 1 0 1 0 0 1
Cq - Fq     10 0 -3 20 0 0

Vemos que el valor C3 - F3 es negativo por lo que estamos en el punto óptimo y el vector a introducir en la base es el a3. Para determinar el vector que debe salir consideramos el criterio:
    \( \displaystyle \min \frac{u_b^b}{e_{b,q-m}} = \min \left(\frac{0}{1}, \frac{2}{1}\right)= \frac{0}{1}\Rightarrow \textrm{ sale } a_5 \)
De ese modo el pivote para la nueva tabla es v32 = 1 y con los pasos ya explicados se tendrá:

  c -10 -20 -3 0 0 0
ab cb -120 a1 a2 a3 a4 a5 a6
a2 -20 6 1 1 0 1 0 0
a3 -3 0 -1 0 1 -1 1 0
a6 0 2 2 0 0 1 -1 1
Cq - Fq     7 0 0 17 3 0

Tenemos que todos los Cq - Fq son positivos por lo que hemos llegado a la solución óptima para la que se tiene:
    \( a_1 = 0 \textrm{ (*) }; a_3 = 0\; ;\; a_2 = 6 \rightarrow F_\min (x_1, x_2, x_3)= - 120 \)
(*) No está en la base
EJERCICIOS RESUELTOS DE OPTIMIZACIÓN MATEMÁTICA PARA INGENIERÍA Y CIENCIAS
primero ~ : ~ anterior ~ : ~ siguiente


tema escrito por: José Antonio Hervás