Resumen del procedimiento de programación líneal paramétrica para cambios sistemáticos en los parámetros bi (I)

Paso 1:  se resuelve el problema con θ =0 mediante el método símplex.
Paso 2: se utiliza el procedimiento de análisis de sensiblidad (caso 1, sección 6.7) para introducir los cambios Δbi = αiθ en la columna del lado derecho.
Paso 3: se incrementa el valor de θ hasta que el valor de una de las variables básicas en la columna del lado derecho se vuelve negativo (o hasta que θ se ha incrementado todo lo que se desea.)
Paso 4: se usa esta variable como la variable básica que sale para llevar a cabo una nueva iteración del método símplex dual, para encontrar una nueva solución óptima. Se regresa al paso 3.

Cambios sistemáticos en los parámetros bi (III)

El siguiente resumen del procedimiento de solución es muy parecido al que se acaba de presentar para los cambios sistemáticos en los parámetros cj. Esto no se debe a que cambiar las bi es equivalente a cambiar los coeficientes de la función objetivo en el modelo dual. Entonces, el procedimiento para el problema primal es exactamente complementario a la aplicación simultánea del procedimiento para cambios sistemáticos en los parámetros cj del problema dual. En consecuencia, ahora se usará el método símplex dual (véase la sección 9.2) para obtener cada nueva solución óptima y el caso 1 del análisis de sensibilidad (véase la sección 6.7); estas diferencias son las únicas importantes.

Cambios sistemáticos en los parámetros bi (II)

Con esta formulación, el valor correspondiente de la función objetivo Z*(θ) siempre tiene la forma lineal por partes y cóncava que se muestra en la figura 9.2. (Véase el problema 25) El conjunto de variables básicas en la solución óptima cambia (al aumentar θ) sólo en el punto en que cambia la pendiente de Z*(θ), pero ahora los valores de estas variables cambian como una función (lineal) de θ entre los cambios pendientes. Esto se debe a que al aumentar θ, cambia el lado derecho en el conjunto inicial de ecuaciones, lo que a su vez causa cambios en los lados derechos del conjunto final de ecuaciones, es decir, en los valores de conjunto final que son óptimas para valores diferentes de θ, uno para 0 ≤ θ ≤ θ1, el segundo para θ1 ≤ θ ≤ θ2 y el tercero para θ ≥ θ2. Dentro de cada uno de estos intervalos para θ, el valor de Z*(θ) varía con θ a pesar de los coeficientes fijos cj, porque el valor de las xj cambia.

Cambios sistemáticos en los parámetros bi (I)

Para este caso, la única modificación que se hace al modelo de programación lineal es sustituir bi por (bi+αiθ), para i = 1,2,......,m, en donde las αi son constantes de entradas dadas. Así, el problema se convierte en:

El objetivo es identificar la solución óptima como una función de θ.

Resumen del procedimiento de programación lineal paramétrica para cambios sistemáticos en los parámetros cj

Paso 1: se resuelve el problema con θ = usando el método símplex.
Paso 2: se utiliza el procedimiento de análisis de sensibilidad (casos 2a y 3, Sec 6.7) para introducir los cambios Δcj = αjθ en la ecuación (0).
Paso 3: se incrementa θ hasta el coeficiente de una de las variables no básicas en la ecuación cero se vuelve negativo (o hasta que θ se ha incrementado todo lo que se desea)
Paso 4: se usa esta variable como variable básica entrante para llevar a cabo una nueva iteración del método símplex, para encontrar una nueva solución óptima. Se regresa al paso 3.

Cambios sistemáticos en los parámetros cj (IV)

Entonces, si se aumenta θ a un valor más alto que θ = 9/7, x4 se convierte en la variable básica entrante en la siguiente iteración del método símplex, para encontrar la nueva solución óptima. DEspués θ se aumenta más hasta encontrar otro coeficiente que se hace negativo, y así sucesivamente, hasta llegar al valor deseado de θ.

Ahora se resumirá el procedimiento completo y se terminará el ejemplo en la tabla 9.3.

Cambios sistemáticos en los parámetros cj (III)

A manera de ilustración, supóngase que α1= 2 y α2 = -1 para el problema de la Wyndor Glass Co. (véase la sección 3.1 y la tabla 4.8), de manera que

Cambios sistemáticos en los parámetros cj (II)

En la figura 9.1 se representa la forma en que el valor de la función objetivo Z*(θ), para la solución óptima, cambia al cambiar el valor de θ, Z*(θ) siempre tiene que esta forma lineal por partes y convexa (vease el problema 24). La solución óptima correspondiente cambia (al aumentar θ), justo en los valores de θ en donde cambia la pendiente de la función. Entonces, la figura 9.1 ilustra un problema en donde tres soluciones diferentes son óptimas para tres valores diferentes de θ, una para 0 ≤ θ ≤ θ1, la segunda para θ1 ≤ θ ≤ θ2 y la tercera para θ ≥ θ2. Como el valor de cada xj permanece igual dentro de cada uno de estos intervalos de θ, el valor de Z*(θ) varía sólo con θ porque los coeficientes de xj cambian como una función lineal.

Este procedimiento de solución se basa directamente en el procedimiento de análisis de sensibilidad para investigar los cambios en los parámetros cj (casos 2a y 3, Sec. 6.7). Como se describió en la última subsección de la sección 6.7, la única diferencia básica es que ahora los cambios se expresan en términos de θ y no de números específicos.

Cambios sistemáticos en los parámetros cj (I)

En este caso, la función objetivo del modelo de programación lineal normal,

en donde las αj son constantes de entrada dadas que representan las tasas relativas a las que se cambian los coeficientes. Al incrementar θ gradualmente desde cero, los coeficientes cambian según estas tasas relativas.

Los valores asignados a las αj pueden representar cambios simultáneos interesantes de las cj para realizar un análisis de sensibilidad sistemático del efecto que tiene el aumento en la magnitud de estos cambios. También pueden estar basados en la forma como cambiarían los coeficientes (por ejemplo, ganancia unitaria) respecto a algún factor medido por θ. Este factor puede ser incontrolable del tomador de decisiones, por ejemplo, la cantidad de personal y equipo que debe cambiarse de una actividad a otra.

Para cualquier valor dado de θ se puede obtener, mediante el método símplex, la solución óptima del problema de programación lineal correspondiente. Esta solución puede haberse obtenido ya para el problema original, en donde θ=0. Sin embargo, el objetivo es encontrar la solución óptima del problema modificado de programación lineal, [maximizar Z(θ) sujeta a las restricciones originales] como una función de θ. Así, es necesario que el procedimiento de solución sea capaz de determinar cómo y cuándo cambia la solución óptima (si lo hace) cuando el valor de θ aumenta de cero a cualquier número positivo específico.

Programación lineal paramétrica

Al final de la sección 6.7 se describió la programación lineal paramétrica y su utilización al llevar a cabo un análisis de sensibilidad sistemático que cambia gradual y simultáneamente varios parámetros del modelo. Se presentará ahora el procedimiento algorítimico, primero para el caso en el que se cambian los paramétros cj y después cuando se varián los parámetros bi.

Resumen del método símplex dual (V)

La solución básica inicial es y1 = 0, y2= 0, y3 = 0, y4 = -3, y5 = -5, con Z =0, que no es factible porque tiene valores negativos. La variable básica que sales es y5 (5>3), y la variable básica entrante es y2 (12/2< 18/2), lo que conduce al segundo conjunto de ecuaciones que se muestra en la iteración 1 de la tabla 9.2. La solución básica correspondiente y1 =0, y2 = 5/2, y3 = 0, y4 = -3, y5 =0, con Z =-30, que no es factible.

La siguiente variable básica que sale es y4 y la que entra es y3(6/3 < 4/1) lo que da lugar al conjunto final de ecuaciones que se presenta en la tabla 9.2. La solución básica correspondiente es y1 = 0 , y2 = 3/2, y3 = 1, y4 =0, con Z = -36, que es factible y por lo lo tanto óptima.

Obsérvese que la solución óptima para el dual de este problema es x1* = 2, x2* =6, x3* = 2, x4* =0, x5* =0, que es la misma que se obtuvo en la tabla 4.8 mediante el método símplex. Se sugiere al lector que siga con detalle al mismo tiempo lo que se obtuvo en las tablas 9.2y 4.8 y que compare los pasos complementarios de los dos métodos simétricos. 

Resumen del método símplex dual (IV)

Después de convertir las restricciones funcionales a la forma ≤ y de introducir las variables de holgura, el conjunto inicial de ecuaciones es el que se muestra en la iteración 0 en la tabla 9.2. Nótese que todos los coefecientes de la ecuación (0) son no negativos, con lo que la solución es óptima si es factible.

Resumen del método símplex dual (III)

Para comprender bien el método símplex dual se debe entender que hace lo mismo que haría el método símplex si se aplicara a las soluciones básicas complementarias en el problema dual. (De hecho, esta fua la motivación para construirlo así) La parte I, que determina la variable básica que sale, es equivalente a determinar la variable básica entrante en el problema dual. La variable con el valor negativo más grande corresponde al coeficiente negativo mayor en la ecuación (0) del problema dual (véase la tabla 6.3). La parte 2, que determina la variable básica entrante, es equivalente a determinar la variable básica que sale en el problema dual. El coeficiente de la ecuación (0) que llega primero a cero corresponde a la primera variable que se hace cero en el problema dual. También los dos criterios para detener el algoritmo son complementarios.

Se ilustrará el método símplex dual aplicándolo al problema dual de la Wyndor Glass Co. (véase la tabla 6.1). Por lo general, este método se aplica directamente al problema  en cuestión (un problema primal) En este caso se escogió este problema porque ya se conoce la aplicación del método símplex a su problema dual (a saber, el problema primal) que se hizo en la tabla 4.8; de esta forma se pueden comparar los dos. Para facilitar la comparación, se continuará denotando a las variables de decisión en el problema que se va a resolver, como yi en lugar de xj.

En forma de maximización, el problema es:

Resumen del método símplex dual (II)

Prueba de factibilidad: se determina si la solución es factible (y por tanto óptima) al verificar que todas las variables básicas sean no negativas. Si es así, entonces esta solución es factible y el algoritmo se detiene. De otra manera, se siguen las instrucciones del paso iterativo.

Resumen del método símplex dual (I)

1. Paso inicial: se introducen las variables de holgura necesitaras para construir un conjunto de ecuaciones que describan el problema. Se encuentra la solución básica tal que los coeficientes de la ecuación (0) sean ceros para las variables básicas y no negativos para las variables no básicas. Se lleva a cabo la prueba de optimalidad.
2. Paso Iterativo:

Parte 1: Se determina la variable básica que sale seleccionando aquélla que tenga el valor negativo más grande.

Parte 2: se determina la variable básica entrante; se elige aquellá cuyo coeficiente en la ecuación (0) llegue primero a cero al agregar a la ecuación (0) un múltiplo creciente de la ecuación que contiene la variable básica que sale. Esta elección se hace examinado las variables no básicas con coeficientes negativos en esta sección (la que contiene la variable básica que sale) y escogiendo la que tiene el cociente más pequeño, dado por el coeficiente de la ecuación (0) entre el valor absoluto del coeficiente en esa ecuación.

Parte 3: se determina la nueva solución básica: se comienza con el conjunto actual de ecuaciones y se despejan las variables básicas en términos de las no básicas, mediante el método de eliminación de Gauss (veáse el apéndice 4). Cuando las variables no básicas se hacen cero, cada variable básica (y Z) es igual al nuevo valor del lado derecho de la ecuación en la que aparece (con coeficiente +1)

Método símplex dual (II)

Como se mencionó varias veces en el capítulo 6 al igual que en la sección 4.7, otra aplicación de primordial importancia del método símplex dual es su asociación con el análisis de sensibilidad. Supóngase que se ha obtenido una solución óptima por el método símplex pero que es necesario (o de interés para el análisis de sensibilidad) hacer cambios menores al modelo.

Si la solución básica óptima que se tenía ya no es factible (pero todavía satisface la prueba de optimalidad), se puede aplicar de inmediato el método símplex dual a partir de esta solución básica superóptima. Con la aplicación del método símplex dual por lo general se llega a la nueva solución óptima mucho más rápidamente que si se resuelve el nuevo problema desde el principio con el método símplex.

Las reglas para el método símplex dual son muy parecidas a las del método símplex. De hecho, una vez que se inician, la única diferencia entre ellos es el criterio para elegir las variables básicas que entran y salen y la regla para detener el algoritmo.

Para dar inicio al método símplex dual todos los coeficientes en la ecuación (0) deben ser no negativos (de manera que la solución básica sea superóptima). Las soluciones básicas serán no factibles (excepto la última) sólo porque algunas variables son negativas. El método continúa haciendo que el valor de la función objetivo disminuya, y conserva siempre coeficientes no negativos en la ecuación (0), hasta que todas las variables sean no negativas. En este momento la solución básica es factible (satisface todas las ecuaciones) y, por tanto, es óptima según el criterio del método símplex de coeficientes no negativos en la ecuación (0). A continuación se resumirán los detalles del método símplex dual.

Método símplex dual (I)

Se puede considerar que el método símplex dual es la imagen en un espejo del método símplex.

Esta interpretación se explica mejor si se consultan las tablas 6.10 y 6.11  y la figura 6.1. El método símplex trata directamente con soluciones básicas subóptimo y se mueve hacia la solución óptima al tratar de satisfacer la prueba de optimalidad. Por el contrario, el método símplex dual maneja en forma directa soluciones básicas superóptimas y se mueve hacia la solución óptima tratando de alcanzar la factibilidad. Aún más, el método dual símplex trata un problema como si se aplicara el método símplex a su problema dual de manera simultanea. Si se hacen complementarias sus soluciones  básicas iniciales, los dos méetos se mueven en una secuencia completa y obtienen soluciones básicas complementarias en cada iteración.

El método símplex dual es muy útil en algunas situaciones especiales. Lo normal es que sea más fácil encontrar una solución inicial básica factible que una solución inicial básicas superóptima, aunque en ocasiones es necesario introducir muchas variables artificiales para construir, en una forma simulada, una solución inicial básica factible. En estos casos puede ser más sencillo comenzar con una solución básica superóptima y aplicar el método símplex dual. Incluso, puede ser que se requieran menos iteraciones cuando no se tienen que hacer cero tantas variables artificiales.

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.

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

El siguiente paso es determinar cuándo esta solución es también óptima para el modelo original, incluyendo las restricciones de balance racial. Para ellos se verifica que tan grande puede ser L antes de que la solución viole alguna de estas restricciones; este valor es L ≤ 0.285. Colo la solución es factible para este intervalo de valores de L, debe ser también óptima para estos valores.

Dada esta información, los consultores aplicaron programación paramétrica para determinar los cambios que sufre la solución óptima al aumentar L en forma continua hasta 1/2, comenzando con la solución anterior y con L = 0.285. El resultado es una solución óptima que cambia en forma continua, donde cada variable se expresa en función de L. (Se puede decir que ésta es una aplicación del procedimiento de análisis de sensiblidad descrito en la sección 6.6, con una variación continua para determinar el efecto de introducir las restricciones de balance racial conforme sea necesario y del cambio en los coeficientes de estas variables en esas restricciones.

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

Puede usarse esta misma forma para desarrollar las restricciones correspondientes de limite superior que representan los requerimientos de cada fracción ≤ 1/2 + θ. Sin embargo como

fracción de estudiantes blancos = 1 - fracción de estudiantes negros.

las restricciones anteriores de limite inferior impuestas a los dos tipos de fracciones garantiza que los requerimientos de límite superior se satisfaga y así no se necesitan otras restricciones para el modelo.

Puede decirse que este modelo tiene un defecto que consiste en que permite que las xij (al igual que el número correspondiente de estudiantes blancos y negros que se asignan de la sección i a la escuela j) tomen valores no enteros (por la suposición de divisibilidad de programación lineal). De todas maneras, si se considera el gran número de estudiantes que hay que tomar en cuenta, se piensa que no será difícil ajustar una solución óptima a valores enteros durante el análisis posterior. Los consultores saben, por experiencia, que un modelo de programación lineal tiene ventajas computacionales importantes sobre los modelos de programación entera, por lo que aparentemente vale la pena hacer las aproximaciones.

En este momento se puede pasar la etapa de cálculos de este estudio. Cuando L es lo suficientemente pequeño (esto es, θ está lo suficientemente cerca de 1/2), las restricciones de balance racial no tienen defecto y se pueden suprimir. También se puede observar que el problema sin estas restricciones se puede formular como un problema de transporte (el tipo especial de problema de programación lineal descrito en la sección 7.1). como se muestra en la tabla 8.8. Así, en lugar de aplicar el método símplex, los consultores comenzaron por aplicar el método símplex de transporte (véase sección 7.2) que es mucho más eficiente en el caso de esta fomulación. La solución óptima que se obtuvo tiene como variables básicas

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

En donde cada coeficiente del numerador es el número de estudiantes blancos en esa sección dividio entre el número total de estudiantes también de esa sección (véase la tabla 8.7). Así, la restricción de límite inferior para esta fracción es

Como las restricciones de esta forma requieren algoritmos de programación no lineal menos eficientes, los consultores decidieron convertir estas restricciones a una forma equivalente que se ajuste al formato de programación lineal. Esta conversión se hace multiplicando ambos lados de la desigualdad por el denominador del lado derecho, para obtener

Planeación y control de proyectos con PERT-CPM (I)

La buena administración de proyectos a gran escala requiere planeación, programación y coordinación cuidadosas de muchas actividades interrelacionadas. Al principiar la década de 1950 e desarrollaron procedimientos formales basados en el uso de redes y de las técnicas de redes para ayudar en estas tareas. Entre los procedimientos más sobresalientes se encuentran el PERT (técnica de evaluación y revisión de programas) y el CPM (método de la ruta crítica), aunque existen muchas variantes con diferentes nombres. Como se verá más adelante, existen diferencias importantes entre estos dos procedimientos. Sin embargo, a últimas fechas, existen diferencias importantes entre estos dos procedimientos. Sin embargo, a últimas fechas, existe una cierta tendencia a unir los dos enfoques en lo que se conoce como sistemas tipo PERT.

Aunque originalmente los sistemas tipo PERT se aplicaron para evaluar la programación de un proyecto de investigación y desarrollo, también se usan para controlar el avance de otros tipos de proyectos especiales. Como ejemplos se puede citar los programas de construcción, la programación de computadoras, la preparación de propuestas y presupuestos, la planeación del mantenimiento y la instalación de sistemas de cómputo. Este tipo de técnica se ha venido aplicando aún a la producción de película, a las campañas políticas y a operaciones quirúrgicas complejas.

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

Balance racial

Las restricciones de balance racial deben especificar que la fracción de estudiantes de una raza dada en una escuela dada tiene que caer dentro de ciertos límites. Después de analizar el asunto con el consejo directivo escolar y de observar que la población estudiantil completa se divide en partes iguales  entre blancos y negros, se decidió que se tomarían los mismos límites para todas las escuelas  y que estos límites debían ser simétricos respecto a las razas. Así, para cada escuela y ambas razas, la fracción de estudiantes deben estar dentro de los limites.

1/2 - 

θ ≤ fracción ≤ 1/2 + θ,

de forma que θ representa la desviación máxima permitida de una distribución equitativa de razas en una escuela.

En cualquier otro caso, por ahora los miembros del consejo directivo no quieren especificar un valor para θ, hasta que puedan tener una idea de las consecuencias de su decisión en términos de las distancias que los estudiantes deben recorrer. (Recuérdese que intentan lograr un trueque razonable entre estos dos puntos.) Por otro todo lo anterior, los consultores llegaron a la conclusión de que deben usar programación paramétrica (véanse las secciones 4.7, 6.7 y 9.3) para determinar qué cambios sufre la solución óptima en el intervalo completo de valores de θ (0 ≤ θ ≤ 1/2).

AOra expresar matemáticamente las restricciones de balance racial primero debe expresarse la fracción de estudiantes de cada raza en cada escuela en términos de las variables de decisión. Por ejemplo.

Fracción de estudiantes blancos en la escuela 1 =

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

En lugar de esperar estas variables en el número de estudiantes blancos y el número de estudiantes negros que se han de asignar, los consultores establecieron una suposición de simplificación consistente en que la mezcla racial de cada sección se conservaría en las asignaciones a las respectivas escuelas.

La formulación obtenida usando los datos de la tabla 8.7 es la siguiente:

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

Sin embargo, es necesario establecer con más precisión el objetivo de "optimizar la distancia recorrida". Una posibilidad es minimizar la distancia máxima que cualquier estudiante debe recorrer, mediante la técnica de la formulación correspondiente que se presentó en la sección debe recorrer, mediante la técnica de formulación correspondiente que se presentó en la sección 8.3, pero este objetivo puede conducir a que muchos estudisantes tengan que recorrer la distancia máxima. Otro objetivo más conveniente que puede llevar a un mejor resultado global es miminizar la suma de las distancias recorridas para todos los estudiantes. Si esto se conduce a unas cuantas injusticias inaceptables, se podrán eliminar durante la etapa de análisis de sensibilidad introduciendo restricciones sobre las distancias recorridas por grupos de estudiantes cuyo recorrido sea excesivo en la solución óptima original. Por tanto, la estructura elegida para el modelo fue minimizar la distancia recorrida total sujeta a las restricciones sobre balance racial y cualquier otra restricción que se necesite.

En última instancia, se tendrán que tomar decisiones sobre la asignación individual de lo estudiantes a las respectivas escuelas. Pero estas decisiones detalladas sobre cómo marcar las fronteras de las zonas de asignación se pueden tomar después de decidir cuántos estudiantes de cada sección deben asignarse a cada escuela. Así, las variables de decisión que se escogieron para el modelo son:

xij = número de estudiantes en la sección i que se asigna a la escuela j (i = 1,2,.........,10; j=1,2,3)