Otros algoritmos para programación lineal (VI)

Para comenzar con la primera iteración, esta ecuación (0) inicial indica que la variable básica entrante inicial es x1. Como las restricciones de cota superior no están incluidas, el conjunto inicial completo de ecuaciones y los cálculos correspondientes para seleccionar la variable básica que sale se muestra en la tabla 9.1. La segunda columna muestra cuánto puede aumentar la variable básica entrante x1 antes de que alguna variable básica (inclusive x1) se vuelva no factible. Ahora, el valor máximo que se da a la ecuación (0) es sencillamente la cota superior para x1. Para la ecuación (1), como el coeficiente de x1 es positivo, al aumentar a 3 su valor, la variable básica (x2) en esta ecuación disminuye de 12 a su cota inferior de cero. En la ecuación (2), el coeficiente de x1 es negativo, por lo que si se aumenta su valor a 1 la variable básica (x3) en esta ecuación aumenta de 4 a su cota superior de 6.

Este último valor máximo de x1 es el más pequeño, lo que determina que x3 sea la variable básica que sale. Ahora bien, como x3 alcanzó su cota superior, x3 sustituyendo por (6-y3) y y3=0 se convierte en la nueva variable no básica en la siguiente solución básica factible y x1 se convierte en la nueva variable básica en la ecuación (2). Este reemplazo lleva a los siguientes cambios en esa ecuación:

Otros algoritmos para programación lineal (V)

Las tres variables tienen pues, restricciones de cota superior (u1 =4, u2 = 15, u3 = 6). Las dos restricciones de igualdad se encuentran ya en la forma apropiada de eliminación de Gauss para identificar la solución básica factible inicial (x1 =0, x2 = 12, x3 =4) y ninguna de las variables de esta solución excede su conta superior; así, x2 y x3 se pueden usar como variables básicas iniciales sin introducir variables artificiales. Como quiera que sea, es necesario eliminar algebraicamente estas variables de la función objetivo para obtener la ecuación (0) inicial,

Otros algoritmos para programación lineal (IV)

Así pues, siempre que una variable básica llega a su cota superior se debe cambiar de opción y usar su variable de decisión complementaria como la nueva variable no básica (la variable que sale) para identificar la nueva solución básica factible. Entonces, la única modificación sustantiva que se hizo al método símplex está en la regla para elegir la variable básica que sale.

Recuérdese que el método símplex elige como variable básica que sale a aquélla que sería la primera en convertirse en no factible al tomar valores negativos cuando se incrementa el valor de la variable básica entrante. En cambio, con la modificación que se acaba de hacer, se selcciona la variable que sería la primera en volverse no factible en cualquier dirección, a sea por volverse negativa o por sobrepasar la cota superior cuando se incrementa la variable básica entrante. (Nótese que una posibilidad es que la variable básica entrante se vuelva no factible si adquiere un valor mayor que su cota superior, en este caso su variable complementaria se convierte en la variable básica que sale.) Si la variable básica que sale adquiere el valor cero, se procede con el método símplex en forma normal, pero si por el contrario alcanza su  cota superior, entonces se cambia de opción y su variable de decisión complementaria será la variable básica que sale.
Para ilustrar este procedimiento, considérese el problema.

Otros algoritmos para programación lineal (III)

Para poner en práctica esta idea, nótese que una variable de decisión xj con una restricción de cota superior (xj ≤ uj) siempre puede sustituir por

Otros algoritmos para programación lineal

La razón por que la programación lineal se usa tan ampliamente es la disponibilidad de un algoritmo excepcionalmente eficiente, el método símplex, que en forma rutinaria resuelve problemas grandes que surgen con frecuencia en la práctica. Sin embargo, el método símplex es sólo una parte del arsenal de algoritmos que se usan con regularidad en la aplicación de la programación lineal. El capítulo 7 describió varias clases especiales de programación lineal para las que existen versiones simplificadas del método símplex (como se pudo observar en el método símplex de transporte en la sección 7.2). En la sección 4.8 se mencionó que los paquetes de computadora adaptan el método símplex a una forma matricial más conveniente. En las secciones 4.7  6.6 se hizo notar la utilidad de ciertas modificaciones o extensiones del método  símplex, en particular para el análisis de sensibilidad. Así, todos estos algoritmos son variantes del método símplex que se presentó en el capítulo 4. En consecuencia, también son excepcionalmente eficientes.

Este capitulo esta dedicado a tres algoritmos de gran importancia, basados en el método símplex. Las tres secciones siguientes presentan la técnica de ramificación y acotamiento (versión simplificada del método símplex para manejar variables que tienen una cota superior), el método dual símplex (modificación muy útil para el análisis de sensibilidad) y programación paramétrica (extensión para el análisis de sensiblidad sistemático).

En la sección 4.9 se introdujo un nuevo desarrollo en programación lineal que causa gran  emoción, un nuevo y poderoso tipo de algoritmo que se mueve por el interior de la región factible. En la sección 9.4 se describirá con detalle este enfoque de punto interior.

Conclusiones formulación de modelos de programación lineal, incluyendo programación por objetivos

En este capítulo se describieron e ilustraron algunas técnicas de formulación particularmente útiles para la construcción de modelos de programación líneal. Este material proporciona un buen antecedente, pero el mejor de esta área es la experiencia. La meta de los autores fue proporcionar al lector fundamentos sólidos para manejar problemas reales y para continuar el aprendizaje en el arte de la programación lineal.

Estudio de caso - Reubicación de zonas escolares para lograr un balance racial (VII)

No obstante, los consultores piensan que los resultados obtenidos de esta manera serán muy complicados para que sean útiles para el consejo directivo escolar. Así, después de examinar con todo cuidado los resultados, seleccionaron un pequeño número de alternativas interesantes (L = 0.285, 0.30, 0.35, 0.40) que representan una sección transversal de los distintos trueques o combinaciones entre el balance racial y la distancia recorrida. Analizaron estas alternativas con detalle e hicieron los refinamientos apropiados a la "solución óptima" que obtuvieron un modelo. Una vez concluida esta etapa presentaron los datos básicos y sus conclusiones al consejo directivo.

Después de una larga deliberación, el consejo eligió la alternativa con θ = 0.15, pero la modificaron ligeramente para evitar asignar dos vecs una pequeña parte de una de las secciones a una escuela nueva. El plan maestro obtenido asigna las secciones 2,3 y 7 a la escuela 1, las secciones 1,4,5 y 6 a la escuela 2 y la 8 y la 9 a la escuela 3; la sección 10 se dividió como sigue: x10,2 = 50, x10,3 = 400. Como este plan da como resultado θ = 0.155, el consejo directivo escolar anunció oficialmente la nueva política: cualquiera de las dos razas debe constituir por lo menos un tercio del total de estudiantes en cualquiera de las escuelas . Acto seguido, giraron sus instrucciones a la superintendente para que su personal pusiera en práctica esta política utilizando el plan maestro como base para la planeación detallada.