Programación separable (I)

La sección anterior presentó la forma en que se puede resolver una clas de problemas de programación no lineal mediante una extensión del méetodo símplex. Ahora se estudiará otra clase llamada programación separable, para la que de hecho se puede encontrar una aproximación tan cercana como se quiera, con un problema de programación lineal que tiene un número mayor de variables.

Como se indicó en la sección 14.3, la programación separable supone que la función objetivo f(x) es cóncava, que cada una de las funciones de restricción gi(x) es convexa y que todas estas funciones son funciones separables (funciones en las que cada término incluye una sola variable). Sin embargo, con el fin de simplificar la presentación, la atención de esta sección se centra en el caso especial en el que las funciones gi(x) convexas y separables de hecho son funciones lineales, como las de programación lineal. Así, solo la función objetivo requerirá un tratamiento especial.

Método Símplex Modificado - Ejemplo (IV)

La solución óptima que resulta para esta fase 1 del problema es x1 = 12, x2 = 9, u1 =3, con el resto de las variables iguales a cero. [El problema 43x pide que se verifique que esta solución es óptima demostrando que x1 = 12, x2 = 9, u1 = 3 satisfacen las condiciones KKT para el problema original, cuando se escriben en la forma dada en la sección 14.6] Entonces, la solución óptima para el problema de programación cuadrática (que sólo incluye la variable x1 y x2) es (x1,x2) = (12, 9)

Método Símplex Modificado - Ejemplo (III)

La tabla 14.4 muestra los resultados de la aplicación del método símplex modificado a este problema. La primera tabla símplex exhibe el sistema de ecuaciones inicial después de convertir de minimización de Z a maximización de (-Z) y de eliminar algebraicamente las variables básicas iniciales de la ecuación (0), lo mismo que se hizo para el ejemplo de terapia de radiación en la sección 4.6. Las tres iteraciones procedenigual que en el método simplex normal, excepto por la eliminación de ciertos candidatos para la variable básica entrante, según la regla de entrada restringida. En la primera tabla se elimina u1 como candidato porque su variable complementaria (v1) es ya una variable básica (de todas maneras, habría entrado x2 puesto que -4 < - 3). En la segunda tabla se elimina tanto u1 como y2 (puesto que v1 y x2 son variables básicas) y de manera automática se elige x1 como único candidato con coeficientes negativos en el renglón 0 (mientras que el método símplex normal habría permitido la entrada o bien de x1 o de u1, porque están empatadas con el coeficiente más negativo). En la tercera tabla se eliminan y1 y y2 (porque x1 y x2 son variables básicas). Esta vez u1 no se elimina, pues v1 ya no es una variable básica, así que se elige u1 como variable entrante.

Método Símplex Modificado - Ejemplo (II)

La restricción de complementariedad adicional

x1y1 + x2y2 + u1v1 = 0, 

no se incluye explícitamente, porque el algoritmo refuerza esta restricción de manera automática con la regla de entrada restringida. En particular, para cadauno de los tres pares de variables complementarias [(x1, y1), (x2, y2), (u1, v1)], siempre que una de las dos variables sea ya una variable básica, la otra se excluye de los candidatos como variable básica entrante. Como el conjunto inicial de variables básicas para el problema de programación lineal [z1, z2, v1] da una solución básica factible inicial que satisface la restricción de complementariedad, no hay manera de violar esta restricción con ninguna de las restricciones básicas factibles subsecuentes.

Método Símplex Modificado - Ejemplo (I)

Se ilustrará este enfoque con el problema que se dio al principio de la sección. Como se puede verificar con los resultados del apéndice 1 [véase el problema 43a], f(x1, x2) es estrictamente cóncava; es decir

Método Símplex Modificado - Regla de entrada restringida

Cuando se elige la variable básica entrante, se excluye de las posibilidades cualquier variable no básica cuya variable complementaria sea básica; la elección debe hacerse entre las otras variables no básicas, según el criterio normal del método símplex.

Esta regla conserva satisfecha la restricción de complementariedad en todo el curso del algoritmo. Cuando se obtiene una solución óptima.

x*, u*, y*, v* z1 = 0,............................, zn = 0

para la fase I de este problema, x* es la solución óptima deseada para el problema original de programación cuadrática. La fase 2 del método de do fases no se necesita.

Método Símplex Modificado (III)

Después se utiliza la fase 1 del método de dos fases para encontrar una solución factible básica para el problema real; es decir, se aplica el método símplex (con una modificación) al siguiente problema de programación lineal.

sujeta a las restricciones anteriores de programación lineal, obtenidas de las condiciones KKT, pero con estas variables artificiales incluidas.

La modificación al método símplex es el siguiente cambio en el procedimiento para elegir una variable básica entrante.