jueves, 31 de octubre de 2013

Cuando no hay variable básica que sale - Z no acotada

Existe otra posibilidad, en la parte 2 del paso iterativo, dela que no se ha hablado, aquella en la que ninguna variable califica como variable básica que sale. Esta situación puede ocurrir si la variable básica entrante puede crecer indefinidamente sin que ninguna de las variables básicas actuales adquiera valores negativos. En la forma tabular, esto significa que todos los coeficientes en la columna pivote (se excluye el renglón 0) son negativos a cero. Esta situación se ilustra en la tabla 4.9 al eliminar las dos ultimás restricciones funcionales en el problema de la Wyndor Glass Co.


La interpretación de una tabla símplex como la que se muestra en la tabla 4.9 es que las restricciones no impiden el crecimiento indefinido de la función objetivo (Z); en este caso, el método símplex se detiene con el mensaje de que Z es no acotada. Debido a que ni siquiera la programación lineal,. ha descubierto la manera de lograr ganancias infinitas, el mensaje real en problemas prácticos es: ise ha cometido un error! Tal vez el modelo está mal formulado, ya sea por haber omitido una restricción relevante o por haberla establecido incorrectamente. De otra manera, pudo haber ocurrido un error en los cálculos.

Empate para la variable básica que sale - degeneración

Ahora supóngase que el empate ocurre entre dos o más variables básicas al elegir la variable que sale en la parte 2 del paso iterativo. Importa cúal se escoge? En teoría, sí, y en una forma crítica debido a que puede ocurrir las siguientes sucesión de eventos. Primero, todas las variables empatadas se hacen cero al mismo tiempo cuando aumenta el valor de la variable entrante. Por tanto aquellos que no se eligieron como variable básica que sale también tendrán un valor de tanto, aquellas que no se eligieron como variable básica que sale también tendrán un valor de cero en la nueva solución básica factible. Segundo si una de estas variables básicas degeneradas sigue con valor de cero hasta que se selecciona como variable básica que sale en una iteración posterior, la variable básica entrante deberá también quedar con valor de cero (ya que no puede crecer sin que la variable básica que sale se vuelva negativa), entonces el valor de Z permanecerá sin cambio. Tercero, si Z permanece igual en lugar de mejorar cada iteración, el método símplex puede caer en un ciclo que repite la misma secuencia de soluciones periódicamente, en lugar de aumentar en algún momento para llegar a la solución óptima. De hecho, se han construido ejemplos artificiales que se quedan atrapados en un ciclo perpetuo de este tipo.

Por fortuna, aunque en teoría es posible que haya ciclos perpetuos, ha sido en extremo raro que tengan lugar en problemas prácticos. Si ocurriera un ciclo siempre se puede salir de el cambiando la elección de la variable básica que sale. Aún más, se han dado reglas especiales para romper empates que siempre evitan los ciclos. Sin embargo, estas reglas prácticamente se han ignorado en las aplicaciones reales, y no se repetirán en este texto. Para los propósitos del lector, se recomienda romper los empates arbitrariamente y seguir el proceso sin preocuparse de las variables degeneradas que pueden resultar.

miércoles, 30 de octubre de 2013

Empate para la variable básica entrante

La parte 1 del paso iterativo elige la variable no básica que tiene el coeficiente negativo con el mayor valor absoluto en la ecuación (0) actual como la variable básica entrante. Ahora supóngase que dos o más variables no básicas tiene el coeficiente negativo más grande (en valor absoluto), es decir, que hay un empate entre ellas. Por ejemplo, esto ocurriría en la primera iteración del problema de la Wyndor Glass Co. si se cambiara la función objetiva a Z = 3x1 + 3x2, con lo que la ecuación incial (0) sería Z - 3x1 - 3x2 = 0. Cómo debe romperse este empate?

La respuesta es que la elección entre estos dos contendientes se puede hacer de manera arbitraria. Tarde o temprano se llegará a la solución óptima, sin importar cuál de las variables empatadas se haya escogido, y no existe un método conveniente para predecir cuál lleva ahí más rápidamente. En este ejemplo, ocurre que si se escoge x1 como variable entrante, el método símplex alcanza la solución óptima (2,6) en tres iteraciones y si se elige x2 llega en dos.

Rompimiento de empates en el método símplex

Con seguridad el lector observó que en las dos secciones anteriores no se dijo qué hacer cuando las reglas de selección del método símplex no llevan a una decisión clara, ya sea porque existen empates (valores iguales) u otras ambiguedades parecidas. En esta sección se presenta ese tipo de detalles.

martes, 29 de octubre de 2013

El método símplex en forma tabular - Paso iterativo -Parte 6

En la tabla 4.8 se tiene ahora el conjunto completo de la tabla símplex completa. La nueva solución básica factible es (2,6,2,0,0), con Z = 36. Al hacer la prueba de optimalidad se encuentra que la solución es óptima por que no hay coeficientes negativos en el renglón 0, de manera que el algoritmo ha terminado. En consecuencia, la solución óptima para el problema de la Wyndor Glass Co. (antes de introducir variables de holgura) es x1 = ,x2 = 6.

Ahora compárese la tabla 4.8 con el trabajo que se hizo en la sección 4.3 para verificar que, en realidad, estas dos formas del método símplex son equivalentes. Después obsérvese que la forma tabular organiza, el trabajo de una manera mucho más conveniente y compacta. En adelante se usará principalmente esta forma.

El método símplex en forma tabular - Paso iterativo -Parte 5

La segunda iteración comienza de nuevo en la segunda tabla símplex de la tabla 4.6 para encontrar la siguiente solución básica factible. Si se siguen las instrucciones de las partes 1 y 2,se encuentra que x1 es la variable básica entrante y x5 la variable básica que sale, como se muestra en la tabla 4.7.

Utilizando el número pivote 3, los cálculos para obtener la nueva tabla símplex son:


lunes, 28 de octubre de 2013

El método símplex en forma tabular - Paso iterativo -Parte 4

Como las variables básicas siempre son iguales al lado derecho de la ecuación que les corresponde, la nueva solución básica factible es (0,6,4,0,6) con  Z = 30.

Este trabajo completa el paso iterativo, así que debe proseguirse a la prueba de optimalidad para verificar si la nueva solución básica es óptima. Como el nuevo renglón (0) todavía tiene coeficientes negativos (-3 para x1), la solución no es óptima, por lo que se necesita por lo menos una iteración más.


El método símplex en forma tabular - Paso iterativo -Parte 3

Se determina la nueva solución básica factible construyendo una nueva tabla símplex en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. (Las primeras tres columnas no cambian, excepto que la variable básica entrante sustituye a la variable básica que sale en la columna de variable básica.) Para cambiar el coeficiente de la nueva variable básica en el renglón privote 1, se divide todo el renglón entre el número pivote, entonces:

Renglón pivote nuevo = renglón pivote antiguo/número pivote

En el ejemplo, como el renglón pivote antiguo es el renglón 2 enmarcado en la primera tabla símplex de la tabla 4.5, y el número privote es 2, al aplicar esta fórmula se obtiene el nuevo renglón pivote, como se muestra en la segunda tabla símplex de la tabla 4.5

Para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica  x2 en los otros renglones (incluso el renglón 0) de esta segunda tabla símplex. Como el renglón 1 ya tiene coeficiente de 0 para x2 en la primera tabla símplex, este renglón se puede copiar a al segunda sin cambios. No así  los renglones 0 y 3 que tienen coeficientes en la columna pivote  de -5 y 2, respectivamente, así que cada uno de ellos necesita cambiarse usando la siguiente fórmula:

Renglón nuevo =  Renglón antiguo - (coeficiente de la columna pivote x renglón pivote nuevo)

De otra forma, cuando el coeficiente de la columna pivote es negativo (como  en el renglón 0), una expresión más conveniente para esta fórmula es:

Renglón nuevo =  Renglón antiguo + [(-coeficiente de la columna pivote) x renglón pivote nuevo].

A manera de ilustración, los renglones que faltan en la segunda tabla símplex de la tabla 4.5 se obtienen como sigue:




domingo, 27 de octubre de 2013

El método símplex en forma tabular - Paso iterativo -Parte 2

Se determina la variable básica que sale; para esto, a) se toma cada coeficiente estrictamente positivo (>0) de la columna enmarcada, b) se divide al lado derecho de cada renglón entre estos coeficientes, c) se identifica la ecuación con el menor cociente y d) se selecciona la variable básica para esta ecuación. Se enmarca el renglón de esta ecuación en la tabla símplex sin incluir la columna Z y se le da el nombre de renglón pivote. El número que está en la intersección de ambos recuadros se llama número pivote.

En la tabla 4.4 se muestran los resultados de las partes 1 y 2 para el ejemplo, la prueba del cociente mínimo para determinar la variable básica que sale se muestra a la derecha de la tabla. En el renglón 1, el coeficiente en la columna pivote es 0, así que los únicos dos coeficientes estrictamente positivos se encuentra en los renglones 2 y 3. Las razones para estos renglones son 6 y 9, respectivamente por lo que la razón mínima de 6 identifica al renglón 2 como el renglón pivote (con 2 como número pivote. En consecuencia la variable, básica que sale es x1 es decir, la variable básica del renglón 2 que aparece en la primera columna.

El método símplex en forma tabular - Paso iterativo -Parte 1

Parte 1: se determina la variable básica entrante mediante la elección de la variable (automáticamente se refiere a una variable no básica) con el coeficiente negativo que tiene el mayor valor absoluto en la ecuación (0). Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.

En el ejemplo, el coeficiente negativo más grande (en términos de valor absoluto) es -5 para x2(5>3,), por lo que x2 debe convertirse en variable básica.

sábado, 26 de octubre de 2013

El método símplex en forma tabular - Prueba de optimalidad

La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación (0) son no negativos (≥ 0). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por un pbásica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3).

En este ejemplo hay dos coeficientes negativos en la ecuación (0), -3 par x1 y -5 para x2, con esta información debe irse al paso iterativo.

El método símplex en forma tabular - Paso Inicial

Se introducen variables de holgura. Si el modelo no se encuentra en la forma en esta sección, véase la sección 4.6 para hacer los ajustes necesarios. De otra manera, se seleccionan las variables originales como variables no básicas  iniciales (se igualara a cero) y las variables de holgura como las variables básicas iniciales.

Esta selección lleva a la tabla símplex inicial que se mostró en la tabla de 4.3 para el ejemplo, de donde la solución básica factible inicial es (0, 0, 4, 12, 18). Ahora debe realizarse la prueba de optimalidad para determinar si la solución es óptima.


viernes, 25 de octubre de 2013

El método símplex en forma tabular (III)

Según las suposiciones actuales sobre la forma original del modelo, la tabla símplex inicial queda automáticamente  en la forma apropiada de eliminación gaussiana. Cuando el método símplex se traslada a la solución básica factible actual a la siguiente, la parte 3 del paso iterativo utiliza la eliminación de Gauss para restablecer esta forma para la nueva solución.

El método símplex construye una tabla símplex para cada solución básica factible que se obtiene, hasta alcanzar la solución óptima. A continuación se describe el procedimiento , que es sólo una representación tabular del procedimiento algébraico presentado en la sección 4.3. Se continuara empleando el ejemplo de la Wyndor Glass Co. como ejemplo.


El método símplex en forma tabular (II)

Para introducir la forma tabular, considérese la forma aumentada del problema de la Wyndor Glass Co. que se presentó al final de la sección 4.2. Este sistema de ecuaciones  [de la (0) a la (3)] puede expresarse como se muestra en la tabla 4.3. Esta tabla contiene la distribución de cualquier tabla símplex, donde la columna de la izquierda indica la variable básica que aparece en cada ecuación de la solución básica factible actual. [Aunque sólo las variables xj son básicas  o no básicas, Z hace las veces de la variable básica para la ecuación (0).] Por ejemplo, la columna de Variable Básica  en la tabla 4.3 indica que la solución básica factible inicial tiene las variables x3, x4, y x5,es decir, las variables no básicas son las que no están en la lista, x1 y x2. Después de establecer x1 = 0, x2 = 0, la columna denominada Lado derecho proporciona la solución para las variables básicas, de manera que la solución básica factible inicial es (x1, x2, x3, x4, x5) = (0, 0, 4, 12, 18) con Z = 0.

La razón por al que la columna Lado derecho siempre da los valores de las variables básicas en la solución básica factible actual es que el método símplex requiere que la tabla símplex al iniciar (o terminar) cara iteración esté en la forma apropiada de eliminación de Gauss. Esta forma es aquella en la que la columna de cada variable básica contiene sólo un coeficiente distinto de cero y este coeficiente es 1 en el renglón de esta variable básica. (Las columnas de las variables no básicas pueden tener cualquier elemento). Obsérvese en la tabla 4.3 que las columnas de x3, x4 y x5 (lo mismo que la de Z) se ajustan a este patrón especial. En consecuencia, cada ecuación contiene exactamente una variable básica con coeficiente distinto de cero, en donde este coeficiente es 1, por lo que esta variable básica con coeficiente distinto de cero, en donde este coeficiente es 1, por lo que esta variable básica con coeficiente distinto de cero, en donde este coeficiente es 1, por lo que esta variable básica es igual a la constante en el lado derecho de esta ecuación.


jueves, 24 de octubre de 2013

El método símplex en forma tabular (I)

La forma algebraica del método símplex presentada en la sección 4.3 puede ser la mejor para entender la lógica que fundamente el algoritmo. Sin embargo, no es la más conveniente para realizar los cálculos necesarios. Cuando se tenga que resolver un problema a mano (o en computadora), se recomienda la forma tabular descrita en esta sección.

La forma tabular del método símplex es matemáticamente equivalente a la forma algebraica, nada más que en lugar de escribir cada conjunto de ecuaciones con todo detalle, se usa una tabla símplex para registrar sólo la información esencial, a saber:

  1. los coeficientes de las variables
  2. las constantes del lado derecho de las ecuaciones
  3. las variables básicas que aparecen en cada ecuación. 
Esto ahorra la escritura de los símbolos de las variables, pero es más importante en cada ecuación. Esto ahorra la escritura de las simbolos de las variables, pero es más importante el hecho de que permite hacer que sobresalgan los números que se usan en los cálculos aritméticos y registrarlos en forma muy compacta.

Reforzamiento del proceso de aprendizaje con el OR COURSEWARE

Este es el primero de muchos puntos en el libro en el que puede ser una gran ayuda usar el OR COURSEWARE. Este paquete contiene un ejemplo completo de demostración del método símplex en la forma algebraica que se acaba de presentar. Esta demostración vivida despliega en forma simultánea el álgebra y la geométria según el desarrollo dinámico del método símplex, paso por paso. Al igual que muchos otros ejemplos de demostración que acompañan otras secciones del libro (incluso la siguiente), esta demostración en computadora hace resaltar los conceptos difíciles de asimilar en la página impresa.

Otra característica del OR COURSEWARE es una colección de rutinas que permite la ejecución interactiva de varios algoritmos que se presentan. Una de estas rutinas está diseñada par ala forma algebraica del método símplex. Como las otras, esta rutina realiza casi todos los cálculos mientras el usuario toma decisiones en cada paso, lo que le permite dedicar su atención en conceptos sin que tenga que sumergirse en una mar de operaciones númericas/

miércoles, 23 de octubre de 2013

Prueba de optimalidad del ejemplo

La nueva forma de la función objetivo es Z = 36 - (3/2)x4 - x5. Ningún coeficiente de las variables no básicas es positivo, por lo que la solución básica factible actual es óptima. Entonces, la solución deseada para la forma original del problema es x1 = 2, x2 = 6, lo que significa un valor de Z = 36.


Iteración 2 del ejemplo

Parte 1: como la ecuación (0) actual da Z = 30 + 3x1 - (5/2)x4, la función Z crece sólo si se aumenta el valor de x1, esto es x1 tiene el mayor coeficiente positivo (y el único). Por tanto, se elige x1 como la variable básica entrante.

Parte 2: los límites superiores sobre x1 antes de que las variables básicas de las ecuaciones respectivas se vuelven negativas, se muestran en la tabla 4.2 En este caso, x5 tiene la menor cota superior sobre x1, por lo que x5 debe seleccionarse como la variable básica que sale.

Parte 3: después de eliminar x1 de todas las ecuaciones del conjunto actual excepto de la ecuación (3), en la que x1 sustituye a x5 como variable básica, el nuevo conjunto de ecuaciones en la forma apropiada de eliminación de Gauss es:




martes, 22 de octubre de 2013

Prueba de optimalidad

Se determina si la solución es óptima: se verifica si el valor de Z puede aumentar al hacer que una de las variables no básicas crezca. Esto se puede realizar al reescribir la función objetivo en términos de las variables no básicas y pasar estas variables al lado derecho de la ecuación (0) y al observar el signo de los coeficientes de cada una. Si todos los coeficientes son negativos o cero, entonces la solución es óptima, y el proceso termina. De otra manera, se regresa al paso iterativo.

A manera de aclaración se aplicará este resumen a la siguiente iteración del ejemplo.

Resumen del método símplex - Paso Iterativo

Parte 1: se determina la variable básica entrante: para esto se selecciona la variable no básica que, al aumentar su valor, aumente el valor de Z más rápidamente. Esta elección se puede hacer usando la ecuación (0) para expresar Z sólo en términos de las variables no básicas y eligiendo aquella cuyo coeficiente positivo sea el mayor.

Parte 2: se determina la variable básica que sale; se elige la variable básica que primero alcanza el valor cero cuando se incrementa  la variable básica entrante. Cada variable básica aparece sólo en su ecuación, de manera que esta ecuación se usa para determinar cuándo llega a cero esta variable básica si se aumenta el valor de lo que entra. Un procedimiento  algebraico formal para hacer esto es el siguiente: sea e el subíndice  de la variable básica entrante, sea a'ie su coeficiente actual en la ecuación (i) y sea b'i el lado derecho actual de esta ecuación (i= 1,2,.....,m) Entonces, la cota superior para xe en la ecuación (i) es


en donde la variable básica de esta ecuación se hace cero en esta cota superior. Entonces se determina la ecuación con la cota superior más pequeña y se elige la variable básica actual en esa ecuación como la variable básica que sale.

Parte 3: se determina la nueva solución básica factible: comenzando con el conjunto actual de ecuaciones, se despejan las variables básicas y Z en términos de las variables no básicas por el método de eliminación de Gauss-Jordan. Las variables no básicas  se igual a cero; cada variable básica (y Z) es igual al nuevo lado derecho de la ecuación en que aparece (con coeficiente +1).

lunes, 21 de octubre de 2013

Resumen del método símplex - Paso Inicial

Se introducen las variables de holgura. Si el modelo no se encuentra en la forma supuesta en esta sección 4.6 para hacer los ajustes necesarios. De otra manera, para obtener la solución básica factible inicial, se seleccionan las variables originales como las variables no básicas (es decir, iguales a cero) y las variables de holgura como las variables básicas ( y por tanto, iguales al lado derecho de las ecuaciones). Se realiza la prueba de optimalidad. 

Prueba de optimalidad (II)

La razón para usar la forma actual de la función objetivo en lugar de la original es que la forma acutal contiene todas las variables no básicas y ninguna variable básica. Se necesitan todas las variables no básicas para poder comparar todas las soluciones básicas factibles adyacentes con la solución actual. Las variables básicas no deben aparecer, pues sus valores pueden cambiar cuando se incrementan alguna variable no básica., en cuyo caso el coeficiente de la variable no básica ya no indica  la tasa de cambio de Z. A causa de las ecuaciones de las restricciones, las dos formas de la función objetivo son equivalentes, por lo que se usa la que contiene toda la información necesaria.

La ecuación (0) se incluye desde el principio en el sistema de ecuaciones de restricción y después en el proceso de eliminación de Gauss precisamente para poder obtener esta nueva forma, más conveniente, de la función objetivo.

Antes de proceder con la siguiente iteración, es posible ahora, y resulta imortante, hacer un resumen del método símplex.

domingo, 20 de octubre de 2013

Prueba de optimalidad (I)

Para determinar si la solución básica actual es óptima, se usa la ecuación (0) para reescribir la función objetivo en términos nada más de las variables no básicas actuales.

Z = 30 + 3x1 - 5x4/2

Aumentar el valor de cualquiera de estas variables no básicas (con el ajuste de los valores de las variables básicas para que cumplan todavía con el sistema de ecuaciones) significa trasladarse a una de las dos soluciones básicas factibles adyacentes. Como x1 tiene coeficiente positivo, hacerla crecer lleva a una solución básica factible adyacente que es mejor que la solución actual, por lo que ésta no es óptima.

En términos generales, la solución básica factible actual es óptima si y sólo si todas las variables no básicas tienen coeficientes no positivos (≤ 0) en la forma actual de la función objetivo. Esta forma actual se obtiene cambiando las variables xj al lado derecho de la ecuación (0) actual después de haber convertido todas las ecuaciones a la forma apropiada de eliminación de Gauss [que elimina las variables básicas de esta ecuación]. En forma equivalente, las variables se pueden dejar en el lado izquierdo y entonces la prueba de optimalidad consiste en que todas las variables no básicas tengan coeficientes no negativos (≥ 0) en la ecuación (0) actual.

Operaciones algebraicas para resolver un sistema de ecuaciones lineales (II)

Asi x2 ha sustituido a X4 como variable básica en la ecuación 2 del anterior post. Es necesario resolver este sistema de ecuaciones para encontrar los valores de Z, x2, x3 y x5. Como x2 tiene coeficiente 2 en la ecuación 2, esta ecuación se dividirá por 2 pará que la nueva variable básica tenga un coeficiente de 1. (Este es un ejemplo de la operación algebraica 1.)

x2 + 1x4/2 = 6

Ahora debe eliminarse x2 de las otras ecuaciones en que aparece. Usando la operación algebraica (2), esta eliminación se hace de la siguiente manera:

Ecuación (0) nueva = ecuación (0) antigua + [5x ecuación(2) nueva], de manera que:





sábado, 19 de octubre de 2013

Operaciones algebraicas para resolver un sistema de ecuaciones lineales


  1. Multiplicar (o dividir) una ecuación por una constante diferente de cero.
  2. Sumar (o restar) un múltiplo de una ecuación a otra.
Estas operaciones son legítimas por que implican sólo:
  1. Multiplicar cosas iguales (ambos lados de una ecuación) por la misma constante 
  2. Sumar cosas iguales a cosas iguales. Por tanto, una solución satisfará un sistema de ecuaciones después de estas operaciones si y sólo si lo hacía antes de realizarlas.
Para ilustrar esto, considérese el sistema de ecuaciones original, en donde las nuevas variables básicas se muestran en negritas ( y donde Z tiene el papel de variable básica en la ecuación de la función obejtivo):

Cómo puede identificarse la nueva solución básica factible en una forma conveniente?

Después de identificar las variables básicas entrante y saliente (incluyendo el nuevo valor de la variable básica entrante), todo lo que se necesita hacer para identificar la nueva solución básica factible es encontrar los nuevos valores de las variables básicas restantes. Estos valores podrían obtenerse directamente de la tabla 4.1. Sin embargo, con el fin de dejar todo listo para la siguiente iteración, el método símplex establece el sistema de ecuaciones a a la misma forma apropiada de eliminación de Gauss que se tenían en el paso inicial (aquella en la que cada ecuación tiene sólo una variable básica con coeficiente +1, y esta variable básica no aparece en ninguna otra ecuación). esta conversión se realiza con dos tipos de operaciones algebraicas.


viernes, 18 de octubre de 2013

Cómo se identifica la variable básica que sale? (II)

En el ejemplo, las posibilidades par ala variable básica que sale son las variables básicas actuales x3,x4 y x5. Los cálculos para identificar cuál debe ser la variable básica que sale se resumen en la tabla 4.1. Como x1 es una variable no básica, x1 = 0 en la segunda columna de la tabla 4.1. La tercera columna indica que:


  1. x3 sigue siendo no negativa (=4) sin importar cuánto aumente x2, 
  2.  x4 =0 si x2 = 6 (mientras que x4>0 si x2 < 6 y x4 <0 cuando x2  > 6);  
  3. x5 = 0 si x2 = 9 (mientras que x5 >0 si x2 <9 y x5 <0 cuando x2 >9).
Asi los números calculados en la tercera columna son las cotas superiores para x2 antes de que la variable básica correspondiente en la primera columna se vuelva negativa. Como x4 (la variable de holgura para restricción 2x2 ≤12) impone la menor cota superior sobre x2, la variable básica que sale es x4, de manera que x4 = 0 (no básica) y x2 = 6 (básica) en la nueva solución factible.

Cómo se identifica la variable básica que sale? (I)

Ignorando las variables de holgura, aumentar el valor de x2 mientras que el de x1 se mantiene en cero significa un movimiento hacia arriba por el eje x2 en la figura 4.1. La solución factible en el vértice adyacente, (0,6) se alcanza al detener el movimiento en la primera línea de restricción que se encuentra (2x2 = 12). Ahí se debe detener aunque existe otra solución en un vértice en (0,9) ya que seguir más arriba significa obtener una solución no factible que viola la restricción 2x2 ≤12

Para el problema en forma aumentada, las soluciones factibles deben satisfacer tanto el sistema de ecuaciones de restricciones funcionales como las restricciones de no negatividad sobre todas las variables (variables originales y de holgura). Al aumentar el valor de x2 mientras se mantiene el de x1 igual a cero (no básica), una o todas las variables básicas actuales (x3,x4,x5) deben cambiar sus valores para mantener satisfecho el sistema de ecuaciones. Algunas de estas variables decrecerán al crecer x2. La solución básica  factible adyacente se alcanza cuando la primera variable básica (variable básica que sale) llega a cero. Ahí se debe detener para evitar la no factibilidad. Entonces, una vez elegida la variable básica entrante, la variable básica que sale no es cuestión de elección. Debe ser la variable básica actual cuya restricción de no negatividad se impone la otra cota superior más pequeña, sobre cuánto puede aumentar el valor de la variable básica entrante, como se ilustra en seguida.

jueves, 17 de octubre de 2013

Cuál es el criterio para seleccionar la variable básica entrante?

Los candidatos para la variable básica entrante son las n variables no básicas acutales. La que se elija, cambiará su estado de no básica a básica, por lo que su valor aumentará de cero a algún valor positivo y las otras se mantendrán en nivel cero. Como se requiere que la nueva solución básica factible sea mejor (un valor más grande de Z) que la actual, es necesario que la tasa de cambio en Z al aumentar el valor de la variable básica entrante sea positivo. Usando la ecuación (0) para expresar Z sólo en términos de las variables no básicas, el coeficiente de cada una es la tasa a la que Z cambiaría si se incrementara el alor de esa variable. Se elige como variable básica entrante la que tiene el coeficiente positivo mayor, ya que es la que hace que Z se incremente a la tasa más rápida.

Como aclaración, los dos candidatos para variable básica entrante en el ejemplo son las variables no básicas actuales x1 y x2. Como la función objetivo ya está escrita sólo en términos de estas variables, puede analizarse tal como está:

Z = 3x1 + 5x2

 Ambas variables tienen coeficientes positivos, así que al aumentar cualquiera de ellas, el valor de Z aumenta pero con tasas distintas de tres y cinco por cada unidad de aumento en la variable. Como 3 < 5, la elección para la variable básica entrante es x2. Así se incrementará el valor de x2 y el de x1 se dejará en cero.

Álgebra del método símplex - Paso Iterativo

En cada iteración el método símplex se mueve de la solución factible básica actual a una solución factible básica adyacente mejor. Este movimiento consiste en convertir una variable no básica (llamada variable básica entrante) en variable básica, y al mismo tiempo convertir una variable básica (llamada variable básica que sale) en variable no básica, y en identificar la nueva solución básica factible.

miércoles, 16 de octubre de 2013

Álgebra del método símplex - Paso inicial

El método símplex puede comenzar en cualquier solución factible en un vértice (solución básica factible), de manera que se escoge una que sea conveniente. Antes de tomar en cuenta las variables de holgura, esta elección es el origen (con todas las variables originales iguales a cero) o (x1,x2) = (0,0) para el ejemplo. En consecuencia, después de introducir las variables de holgura, las variables originales son variables no básicas y las variables de holgura son las variables básicas de la solución básica factible inicial. Esta elección se muestra en el siguiente sistema de ecuaciones en el que las variables básicas se escribieron en negritas:

1) x1 + x3 = 4
2) 2x2 + x4 = 12
3) 3x1 + 2x2 + x5 =18

Como las variables no básicas son iguales acero, el resto de la solución se lee como si no existieran: entonces, x3 = 4, x4 =12y x5 = 18, de ahí que la solución básica factible inicial resulta igual a (0,0,4,12,18).

Nótese que la razón por la que esta solución se puede leer de inmediato es por que cada ecuación tiene sólo una variable básica, que tiene coeficiente +1, y que esta variable básica no aparece en ninguna otra ecuación. Pronto se verá que cuando el conjunto de variables básicas cambia, el método símplex utiliza un procedimiento algebraico (el de eliminación de Gauss) para poner las ecuaciones en esta forma tan convincente para leer igual todas las soluciones factibles básicas subsecuentes. Esta forma se llama la forma apropiada de eliminación gaussiana.

Álgebra del método símplex

La presentación de la esencia del método símplex que se hizo en los anteriores posts, no entró en detalles sobre la forma de realizar cada uno de los pasos. En particular, no se han contestado por completo las siguientes preguntas (las frases entre paréntesis reestablecen las pregunta en la terminología algebraica de la sección 4.2)


  1. Paso inicial: Cómo se selecciona la solución factible en un vértice (la solución básica factible) inicial?
  2. Paso iterativo: al buscar un traslado a una solución factible en un vértice adyacente (una solución básica factible adyacente)
       a) como se selecciona la dirección del traslado? 
       b) a que lugar se hizo el traslado?
       c) como se identifica la nueva solución?

3. Prueba de optimalidad: cómo se determina que la solución factible en un vértice acutal (solución básica factible) no tiene soluciones factibles en un vértice adyacentes (soluciones básicas factibles adyacentes) que sean mejores?


martes, 15 de octubre de 2013

Operaciones algebraicas para resolver un sistema de ecuaciones lineales (III)

Ahora, si se compara este último conjunto de ecuaciones con el conjunto inicial que se obtuvo en el paso inicial, se puede observar que se encuentra en la misma forma apropiada de eliminación de Gauss que permite leer de inmediato la solución básica factible actual después de ver que las variables no básicas (x1 y x4) son iguales a cero. Se cuenta ahora con la nueva solución básica factible, (x1, x2, x3, x4, x5) = (0,6,4,0,6), lo que significa un valor de Z = 30.

Para dar una perspectiva más amplia a este procedimiento algebraico, se acaba de resolver el conjunto original de ecuaciones para obtener la solución general para Z, x2,x3 y x5 en términos de x1 y x4 (Esta solución general se puede expresar en forma explícita cambiando x1 y x4 al lado derecho del nuevo conjunto de ecuaciones, pero no se hará aquí.) Después se obtuvo una solución específica (la solución básica factible) haciendo x1 y x4 (las variables no básicas) iguales a cero. Este procedimiento para obtener la solución simultánea de un sistema de ecuaciones líneales se llama método de eliminación de Gauss-Jordan, o en forma corta eliminación gaussiana. El concepto clave de este método es usar dos tipos de operaciones algebraicas para reducir el sistema de ecuaciones original a la forma apropiada de eliminación de Gauss, en donde cada variable básica se elimina de todas las ecuaciones menos una (su ecuación) y en esa ecuación tiene coeficiente +1. Una vez obtenida la forma apropiada de eliminación de Gauss, la solución para las variables básicas se puede leer directamente en el lado derecho de las ecuaciones.


La única diferencia entre las soluciones básicas y las soluciones en un vértice (III)

En términos generales, el número de variables no básicas de una solución básica siempre es igual a los grados de libertad del sistema de ecuaciones y el número de variables básicas siempre es igual al número de restricciones funcionales.

Al trabajar con el problema en forma de igualdades conviene tomar en cuenta y manipular la ecuación de la función objetivo al mismo tiempo que las nuevas ecuaciones de las restricciones. Antes de comenzar con el método simplex es necesario escribir el problema una vez más en una forma equivalente.


Es justo como si la ecuación (0) fuera una de las restricciones originales que, como ya se encuentra  en forma de igualdad, no necesita variable de holgura. Con esta interpretación, las soluciones básicas no cambian, excepto que Z puede verse como una variable básica adicional.

Por casualidad, el modelo para el problema de la Windor Glass Co. se ajusta a nuestra forma estándar, y todas sus restricciones funcionales tienen valores positivos en el lado derecho (bi). Si el caso fuera diferente sería necesario hacer ajustes adicionales en este punto, antes de aplicar el método símplex. .


La única diferencia entre las soluciones básicas y las soluciones en un vértice (II)

Con el fin de ilustrar estas definiciones se considerará de nuevo la solución básica factible (0,6, 4, 0,6). Esta solución se obtuvo aumentando la solución factible en un vértice (0,6). Sin embargo, otra manera de obtenerla es elegir x1 y x4 como variables no básicas, es decir, como  las dos variables que se han de igualar a cero. Las tres ecuaciones llevan, entonces, a a X3 = 4, X2 = 6 y X5 = 6, respectivamente,como la solución para las tres variables básicas. como estas tres variables básicas son no negativas, esta solución básica (0,6,4,0,6) es sin duda una solución básica factible.

Dos soluciones básicas factibles son adyacentes si todas menos una de sus variables no básicas son las mismas (de manera que la misma aseveración se cumple para sus variables básicas). Entonces, trasladarse de una solución básica factible a una adyacente significa cambiar el estado de una variable de no básica a básica y viceversa para otra variable.

Para dar un ejemplo de soluciones básicas factibles adyacentes, considérese un par de soluciones factibles  en vértices adyacentes en la figura 4.1, (0,0) y (0,6). Sus soluciones aumentadas (0,0,4,12,18) y (0,6,4,0,6) son, de manera automática, soluciones básicas factibles adyacentes. Sin embargo, no es necesario ver la figura 4.1 para llegar a esta conclusión. Otra forma de verlo es observar que sus variables no básicas (x1,x2) y (x1,x4) son las mismas excepto que x4 sustituye a x2. En consecuencia, trasladarse de (0,04,12,18) a (0,6,4,0,6) implica cambiar x2 de variable no básica a básica y lo contrario para x4.


lunes, 14 de octubre de 2013

La única diferencia entre las soluciones básicas y las soluciones en un vértice (I)

O entre  soluciones básicas factibles y soluciones factibles en un vértice, es el que estén incluidos los valores de las variables de holgura. Dada cualquier solución básica, la solución en el vértice correspondiente se obtiene con sólo quitar las variables de holgura. Entonces, las relaciones geométricas y algebraicas entre estas dos soluciones son muy estrechas.

Como los términos solución básica y solución básica factible constituyen partes muy importantes del vocabulario normal de programación lineal, es necesario aclarar sus propiedades algebraicas. Nótese que para la forma aumentada del ejemplo, el sistema de restricciones funcionales tiene dos variables más (cinco) que ecuaciones (tres). Este hecho proporciona dos grados de libertad al resolver el sistema y aque se pueden elegir dos variables cualesquiera y hacerlas iguales a cualquier valor arbitrario para resolver las tres ecuaciones en términos de las tres variables restantes (con esto se excluyen redundancias). El método símplex usa cero para este valor arbitrario. Las variables que por el momento se hacen igual a cero se llaman variables no básicas, todas las demás se llaman variables básicas. La solución que resulta es una solución básica. Si todas las variables básicas son no negativas, entonces se tiene una solución básica factible.

Una solución básica es una solución en un vértice aumentada

Para ilustrar esto, considérese la solución no factible en el vértice 94,6) del ejemplo. Al aumentarla con los valores obtenidos para las variables de holgura x3 = 0, x4 = 0 y x5 = -6, se llega ala solución básica correspondiente (4, 6, 0, 0,-6).

El hecho de que las soluciones en los vértices (y por ende las soluciones básicas) puedan ser o no factibles implica la siguiente definición:

Una solución básica factible es una solución factible en un vértice aumentada.

Así la solución factible en el vértice (0,6) del ejemplo es equivalente a la solución básica factible (0, 6, 4, 0, 6) para el problema en la forma aumentada.

domingo, 13 de octubre de 2013

Preparación para el método símplex (II)

Aún cuando este problema es idéntico al anterior, esta forma es mucho más conveniente para la manipulación algebraica y la identificación de las soluciones factibles en un  vértice. Ésa se llama forma aumentada del problema, ya que la forma original se ha aumentado con algunas variables adicionales necesarias para aplicar el método símplex.

La terminología usada en la sección anterior (soluciones en los vértices, etc.) se aplica a la forma original del problema. Ahora se introducirá la terminología correspondiente a la forma aumentada.

Una solución aumentada es una solución para la variables originales que se ha aumentado con los valores correspondientes de las variables de holgura

Por ejemplo, al aumentar la solución (3,2) en el ejemplo, se obtiene la solución aumentada (3,2,1,8,5) puesto que los valores correspondientes de las variables de holgura son x3 = 1, x4 = 8, x5 = 5.


Preparación para el método símplex (I)

La sección anterior subrayó los conceptos geométricos fundamentales del método símplex. Sin embargo, este algoritmo normalmente se trabaja en una computadora que solo puede seguir instrucciones algebraicas. Por tanto, es necesario traducir el procedimiento geométrico conceptual que se acaba de describir a un procedimiento algebraico utilizable. En esta sección se introducirá el lenguaje algebraico del método símplex y se relacionará con los conceptos de la sección anterior.

En el procedimiento algebraico es mucho más conveniente manejar ecuaciones que desigualdades. Así, el primer paso para preparar el método símplex es convertir las restricciones funcionales de desigualdad en restricciones de igualdad equivalentes. (Las restricciones de no negatividad se pueden dejar como desigualdades por que el algoritmo las usa sólo indirectamente.) Esta conversión se hace mediante la introducción de variables de holgura. Con el fin de ejemplificar, considérese la primera restricción funcional en el ejemplo de la Wyndor Glass Co. de la sección 3.1



sábado, 12 de octubre de 2013

Esencia del método símplex (V)

Este bosquejo muestra la esencia del método símplex, aunque la descripción completa dada en las dos secciones siguientes específica una forma conveniente de elegir la nueva solución, tanto en el paso iterativo como en el inicial. En el caso del ejemplo, al utilizar estas reglas de selección, el método símplex procede como sigue:

1. Paso inicial: comienza en (0,0)
2a. Iteración 1: se mueve de (0,0) a (0,6)
2b. Iteración 2: se mueve de (0,6) a (2,6)
3. Prueba de optimalidad: ni (0,6) ni (4,3) son mejores que (2,6), entonces se detiene (2,6) es óptima.

Esencia del método símplex (IV)

El método símplex explota estas tres propiedades al examinar nada más unas cuentas y prometedoras soluciones factibles en un vértice y al detenerse en cuanto una de ellas pasa la prueba de optimalidad. En particular, se traslada repetidamente (en forma iterativa) de una solución factible en un vértice a otra, adyacente y mejor (lo que se puede realizar en forma muy eficiente) hasta que la solución actual no tiene soluciones factibles en vértices adyacentes que sean mejores. ESte procedimiento se resume como sigue

Búsqueda del método simplex

1. Paso inicial: Inicio en una solución factible en un vértice
2. Paso iterativo: traslado a una mejor solución factible en un vértice adyacente. (Repitase este apso las veces que sea necesario)
3. Prueba de optimalidad: la solución factible en un vértice es óptima cuando ninguna de las soluciones en vértices adyacentes a ellas sean mejores.

viernes, 11 de octubre de 2013

Esencia del método símplex (III)

En la sección 5.1se estudian con detalle las propiedades generales de las soluciones factibles en un vértice  para problemas de programación lineal de cualquier tamaño, al igual que las relaciones entre estas propiedades y el álgebra del método símplex que se presenta en las dos secciones siguientes. Las tres propiedades clave que forman el fundamento del método símplex se resume como sigue:

Propiedades de las soluciones factibles en un vértice.

1a. Si existe exactamente una solución óptima, entonces debe ser una solución factible en un vértice.
1b. Si existen soluciones óptimas múltiples, entonces al menos dos de ellas deben ser soluciones factibles en vértices adyacentes.

2. Existe sólo un número finito de soluciones factibles en los vértices.
3. Si una solución en un vértice es igual o mejor (según el valor de Z) que todas las soluciones factibles en los vértices adyacentes a ella, entonces es igual o mejor que todas las demás soluciones en los vértices; es decir, es óptima.

La propiedad 1 significa que la búsqueda de la solución óptima se puede reducir a la consideración de sólo las soluciones factibles en los vértices, de manera que sólo existe un número finito de soluciones que es necesario tomar en cuenta. La propiedad 3 proporciona una prueba de optimalidad muy conveniente.

Esencia del método símplex (II)

El método símplex es un procedimiento algebraico en el que cada iteración contiene la solución de un sistema de ecuaciones para obtener una nueva solución a la que se le aplica la prueba de optimalidad. No obstante, también tiene una interpretación geométrica muy útil. Para ilustrar los conceptos geométricos generales se empleará la solución gráfica del ejemplo de la Wyndor Glass Co.

Para refrescar la memoria, la gráfica se repitió acá abajo. Se marcaron las cinco líneas de las retristricciones y sus puntos de intersección ya que son punto clave para el análisis. En particular, estos puntos de intersección son las soluciones en los vértices del problema. Los cinco puntos que se encuentran en los vértices de la región factible, (0,0), (0,6), (2,6), (4,3), (4,0) son las soluciones factibles en los vértices. [Los otros tres -(0,9), (4,6), (6,0) -se llaman soluciones no factibles en un  vertice]. Algunas de estas soluciones factibles en un vertice son adyacentes en el sentido de que están conectadas por una sola orilla (segmento de línea) de la frontera de la región factible, esto es, tan (0,6) como (4,3) son adyacentes a (2,6).


jueves, 10 de octubre de 2013

Esencia del método símplex (I)

En realidad, el método símplex es un algoritmo, el primero de muchos que se verán en este libro. Aun cuando el lector no hay oído este nombre, sin duda se ha encontrado con muchos algoritmos. Por ejemplo, el procedimiento familiar para hacer una división larga es un algoritmo.  Por ejemplo, el procedimiento familiar para hacer una división larga es un algoritmo. También lo es el procedimiento para calcular la raíz cuadrada. De hecho cualquier procedimiento iterativo de solución es un algoritmo. Entonces un algoritmo es simplemente un proceso en el que se repite (se itera) un procedimiento sistemático una y otra vez hasta obtener el resultado deseado. Cada vez que se lleva a cabo el procedimiento sistemático se realiza una iteración.  En consecuencia, un algoritmo sustituye un problema útil por una serie de problemas fáciles.

Además de las iteraciones, los algoritmos incluyen un procedimiento para iniciar y un criterio para determinar cuándo detenerse, como se resume en seguida.



En la mayor parte de los algoritmos de investigación de operaciones, el método simplex imclusive, el resultado deseado del que se habla en la regla de detención es que la solución acutal sea óptima. En este caso, la regla de detención de hecho es una prueba de optimalidad, como se muestra aquí:


Solución de problemas de programación lineal: el método símplex

El lector esta listo para comenzar a estudiar el método simplex, es decir, el procedimiento general para resolver problemas de programación lineal. Desarrollado por George Dantzing en 1947, ha probado ser un método extraordinariamente eficiente que se usa en forma rutinaria para resolver problemas grandes en las computadoras de hoy en dia. Excepto en el caso de problemas muy pequeños, su ejecución se hace siempre en una computadora y existe una amplia variedad de complejos paquetes  de software para ello. De cualquier manera, es importante aprender algo de su funcionamiento para poder entender cómo realizar un análisis posóptimo (incluso análisis de sensibilidad) sobre el modelo. Este capítulo describe y ejemplifica las características principales del método símplex.


miércoles, 9 de octubre de 2013

Conclusiones de la Programación Lineal

La programación lineal es una técnica poderosa para tratar problemas de asignación de recursos escasos entre actividades que compiten, al igual que otros problemas cuya formulación matemática es parecida. Se ha convertido en una herramienta estándar de gran importancia para muchas organizaciones industriales  y de negocios. Aún más, casi cualquier organización social tiene el problema de asignar recursos en algún contexto y cada vez mayor el reconocimiento de la aplicabilidad tan amplia de esta técnica.

Sin embargo, no todos los problemas de asignación de recursos limitados se pueden formular de manera que se ajusten a un modelo de programación lineal, ni siquiera como una aproximación razonable. Cuando no se cumplen una o más de las suposiciones de programación lineal, tal vez sea posible aplicar otro tipo de modelos matemáticos, por ejemplo, los modelos de programación entera o de programación no lineal.

Otros ejemplos de programación lineal

Los cuatro ejemplos de programación lineal que se han presentado hasta aquí son sólo una pequeña muestra de las aplicaciones de esta técnica. En los siguientes posts se darán muchas otras ilustraciones que, en su mayor parte,  se refieren a aplicaciones en la industria y los negocios, pero otras surgen en contextos diferentes. Mas adelante verán como se centra en cierto tipo de problemas de programación lineal que proporcionan muchas aplicaciones importantes. El capitulo 8 considera algunos ejemplos que son más difíciles de formular, e incluye el estudio de un caso sobre el diseño de las zonas escolares para alcanzar un mejor balance racial. Pero  antes de entrar a estos temas, se expondrá el método para resolver problemas de programación lineal.


martes, 8 de octubre de 2013

Problema Control de la Contaminación - Formulación como un problema de programación lineal

Este problema tiene seis variables de decisión, xj (j = 1,2,.....6), que representan el uso de cada uno de los tres métodos de abatimiento en cada tipo de horno, expresado como una fracción de la capacidad. En la tabla 3.15 se muestra el orden asignado a las variables. Tomando en cuenta el objetivo es minimizar el costo total sin violar los requerimientos de reducción en la emisión, el modelo es:

El equipo de investigación de operaciones usó este modelo para encontrar el plan de costo mínimo (x1,x2,x3,x4,x5,x6) = (1, 0.623, 0.343, 1, 0.048, 1). Después se llevó a cabo un análisis de sensibilidad seguido de una planeación detallada y la aprobación de la gerencia. Muy poco tiempo después se puso en práctica y los habitantes de Steeltown respiraron con alivio.


Problema Control de la Contaminación (IV)

En este momento, todo ésta listo para desarrollar el marco general del plan de la compañia para disminuir la contaminación. Este plan consistirá en especificar qué tipo de métodos de abatimiento deben emplearse y a qué fracciones de su capacidad para:

  1. Los altos hornos
  2. Los hornos de hogar abierto.
Debido a la naturaleza combinatoria del problema de encontrar un plan que satisfaga los requisitos  con el menor costo posible, se formó un equipo de investigación de operaciones para resolverlo. El equipo decidió enforcar el problema desde un punto de vista de programación lineal, formulando el modelo que se resumen a continuación.


lunes, 7 de octubre de 2013

Problema Control de la Contaminación (III)

Después de obtener estos datos, quedó claro que ningún método por sí solo podía lograr las reducciones requeridas. Por otro lado, la combinación de los tres métodos a toda su capacidad (lo que sería demasiado caro si se quiere que los productos sigan siendo competitivos en precio) resulta mucho mayor de lo que se pide. Por todo esto, la conclusión de los ingenieros fue que tendrían que usar alguna combinación de métodos, tal vez con capacidades fraccionarias, con base en sus costos relativos. Lo que es más, debido a las diferencias entre los altos hornos y los hornos del hogar abierto, es probable que la combinación sea diferente para cada tipo de horno.

Se llevó a cabo un análisis para estimar el costo total anual de cada método de abatimiento. Además del aumento en los costos de operación y mantenimiento, se tomaron en cuenta los costos iniciales o fijos (convertidos a su equivalente anual) de los métodos, al igual que las pérdidas de eficiencia que puedan resultar de los procesos de producción. El análisis proporciono estimaciones de los costos totales, que se dan en la tabla 3.14 (en millones de dolares) en que se incurre al usar los métodos a toda su capacidad de abatimiento. También se determinó que el costo de un método que se utiliza a un nivel menor es esencialmente proporcional a la capacidad fraccional. Entonces, para cualquier fracción utilizada, el costo total anual sería la fracción de la cantidad correspondiente en la tabla 3.14.


Problema Control de la Contaminación (II)

La fabricación de acero tiene dos fuentes principales de contaminación, los altos hornos para fabricar el arrabio y los hornos de hogar abierto para transformar el hierro en acero. En ambos casos, los ingenieros determinaron que los  métodos de abatimiento más efectivos son:

  1. Aumentar la altura de las chimeneas
  2. Usar filtros (incluyendo trampas de gas) en las chimeneas
  3. Incluir limpiadores de alto grado en los combustibles de los hornos. Todos estos métodos tienen limitaciones tecnológicas en cuanto a la cantidad de emisión que pueden eliminar; en la tabla 3.13 se dan los datos (en millones de libras por año).
Los métodos se pueden utilizar en cualquier nivel fraccionario de las capacidades de abatimiento (incluyendo cero) que se muestran en esta tabla y las fracciones pueden ser diferentes para los altos hornos y los de hogar abierto. Para cualquiera de os hornos, el uso simultáneo de otro método no afecta de manera significativa la reducción de emisiones que alcanza cada uno de ellos.



domingo, 6 de octubre de 2013

Problema Control de la Contaminación (I)

La NORI & LETTS CO., una de las mayores productoras de acero del mundo occidental está localizada en la ciudad de Steeltown y es la única empresa grande de la localidad. Steeltown ha crecido y prosperado junto con la compañia, que de momento emplea a cerca de 50000 residentes. La actitud de los habitantes ha sido siempre "lo que es bueno para Nor&Letts es bueno para nostros". Sin embargo, esta actitud está cambiando; la contaminación no controlada del aire debida a los altos hornos de la plata está arruinando la apariencia de la ciudad y poniendo en peligro la salud de sus habitantes.

Como resultado, después de una revuelta entre los accionistas se eligió un nuevo consejo directivo mas responsable. Los nuevos directores han decidido seguir políticas de responsabilidad social y están en pláticas con las autoridades de la ciudad y con grupos de ciudadanos para tomar medidas respecto a la contaminación ambiental. Juntos han establecido estándares rigurosos de calidad del aire para la ciudad de Steeltown

Los tres tipos principales de contaminantes son particulas de materia,  óxidos de azufre e hidrocarburos. Los nuevos estándares requieren que la compañia reduzca su emisión anual de estos contaminantes en las cantidades que se presentan en la tabla del siguiente post. El consejo directivo ha dado instrucciones a la gerencia para que el personal de ingeniería determine como lograr estas reducciones en la forma más económica.

Planeación regional - Formulación como un problema de programación lineal

Las cantidades sobre las que se tomará la decisión son el número de acres que se dedicaran a cada cosecha en cada kibbutz. Las variables de decisión, xj (j= 1,2,....9), representan estas nueve cantidades, como se muestra en la tabla 3.10. Como la medida de efectividad Z es el rendmientoneto total, el modelo de programación lineal que resulta para este problema es:







sábado, 5 de octubre de 2013

Planeación regional

Un experimento social interesante en la región del Mediterráneo es el sistema de kibbutzim, o comunidades agrícolas comunales, en Israel. Es usual que algunos grupos de kibbutzim se unan para compartir los servicios técnicos comunes y coordinar su producción. El primer ejemplo se refiere a un grupo de tres kibbutzim, al que se llamará la CONFEDERACION SUR DE KIBBUTZIM.

La planeación global de la Confederación Sur de Kibbutzim se hace en su oficina de coordinación técnica. En la actualidad están planeando la producción agrícola para el próximo año.

La producción agrícola está limitado tanto por la extensión de terreno disponible para irrigación como por la cantidad de agua que la Comisión de Aguas (una oficina del gobierno nacional) asigna para irrigarlo. En la tabla estan estos datos.

El tipo de cosecha apropiada par ala región incluye remolacha, algodón y sorgo, y éstas precisamente las tres que se estan estudiando para la estación venidera. Las cosechas difieren primordialmente en su rendimiento neto por acre esperado y en su consumo de agua. Además, el Ministerio de Agricultura ha establecido una cantidad máxima de acres que la Confederación puede dedicar a estas cosechas. La tabla de abajo muestra estas cantidades.

Los tres kibbutzim que pertenecen a la Confederación Sur están de acuerdo en que cada kibbutz sembrará la misma proporción de sus tierras irrigables disponibles. Cualquier combinación de estas cosechas se puede sembrar en cualquiera delos kibbutzim. El trabajo al que se enfrenta la oficina de coordinación técnica consiste en planear cuántos acres deben asignarse a cada tipo de cosecha en cada kibbutz, cumpliendo con las restricciones dadas. El objetivo es maximizar el rendimiento neto total para la Confederación Sur

Problema de Radiación, formulación como un problema de programación lineal (II)

Sin embargo, ambos modelos tienen sólo dos variables, de manera que este nuevo problema también se puede resolver por el procedimiento gráfico que se presentó en la sección 3.1. La figura 3.5 muestra la solución gráfica. La región factible consiste solamente en el segmento de recta oscuro entre los puntos (6,6) y (7.5, 4.5) ya que los puntos sobre este segmento son los únicos que satisfacen simultáneamente todas las restricciones (verifiquese esto.). La línea punteada es la correspondiente a la función objetivo que pasa por la solución optima (x1,x2) = (7.5,4.5) con Z = 5.25. Ésta es la solución óptima y no el punto (6,6) puesto que decrecer Z (para valores positivos de Z) hace que la línea de la función objetivo se acerque al origen (en donde Z = 0). Z = 5.25 para (7.5, 4.5) es menor que Z = 5.4 para (6,6).

Pero, que ocurrió con MAry? A lo largo de un penoso periodo de tratamiento de seis semanas, el equipo médico puso en práctica este diseño óptimo del uso de una dosis total en el punto de entrada de 7.5 kilorads para el rayo 1 y 4.5 kilorads para el 2. El espíritu de lucha de la paciente hizo el resto. 


viernes, 4 de octubre de 2013

Problema de Radiación, formulación como un problema de programación lineal (I)

Las dos variables de decisión x1 y x2 representan la dosis en (kilorads) en el punto de entrada de los rayos 1 y 2, respectivamente. Como debe minimizarse la dosis total que llega a la anatomía sana, denótese esta cantidad por Z. En este punto se pueden usar los datos de la tabla del anterior post, para formular el siguiente modelo de programación lineal.


Obsérvense las diferencias entre este modelo y el de la sección 3.1 para el problema de la Wyndor Glass Co. El anterior involucra maximizar Z, y todas las restricciones funcionales estaban en la forma <=. Este nuevo modelo no se ajusta a la misma forma estándar pero si incorpora otras tres formas legitímas descritas en la sección 3.2, a saber, minimizar Z, restricciones de la forma = y restricciones de la forma >=.

Diseño de terapia de radiación (III)

Después de un análisis exhaustivo de este tipo, el equipo médico ha estimado con detalle los datos necesarios para el diseño del tratamiento de Mary; el resumen se presenta en la tabla de abajo. La primera columna da una lista de las áreas del cuerpo que deben considerarse y las dos siguientes proporcionan la fracción de la dosis de radiación de cada rayo en el punto de entrada que se absorbe en promedio en las áreas respectivas. Por ejemplo , si el nivel de la dosis en el punto de entrada del rayo 1 es  1 kilorad, entonces se absorberan 0,4 kilorad en toda la anatomía sana en el plano de dos dimensiones, un promedio de 0.3 kilorad en los tejidos críticos cercanos, un promedio de 0.5 kilorad en las distintas partes del tumor y 0.6 kilorad se absorberán en el centro del tumor. La última columna da las restricciones sobre la dosis total de ambos rayos que se absorben en promedio en las diferentes partes del cuerpo. En particular, la absorción promedio de la dosis para la anatomía sana que debe ser tan pequeña como sea posible, los tejidos críticos no deben exceder 2.7 kilorads, el promedio sobre todo el tumor debe ser igual a 6 kilorads y  en el centro del tumor debe ser por lo menos 6 kilorads.

La satisfacción simultánea de todos estos requisitos puede ser muy complicada. El equipo médico ha dicho a la familia de Mary que la enfermedad ha alcanzado una etapa de gravedad en la que sólo queda una pequeña posibilidad de éxito en el tratamiento. La única oportunidad de salvar su vida estriba en el desarrollo del mejor diseño de tratamiento posible usando los procedimiento más avanzados de optimización disponibles, a saber (qué otra cosa podía ser). Programación lineal..


jueves, 3 de octubre de 2013

Diseño de terapia de radiación (II)

DEbido a la necesidad de balancear cuidadosamente todos estos factores, el diseño de la terapia de radiación es un proceso muy delicado. La meta principal de este diseño es elegir la combinación de rayos que debe utilizarse y la intensidad de cada uno para generar la mejor distribución de la dosis posible.(La fuerza de la dosis en cualquier punto del cuerpo se mide en unidades llamadas kilorads) Una vez desarrollado el diseño de tratamiento, se administra en muchas sesiones a lo largo de varias semanas.

En el caso de Mary, el tamaño y la localización del tumor hace que el diseño de su tratamiento sea más delicado que lo usual. La figura 3.4 muestra un diagrama de un corte transversal del tumor visto desde arriba, al igual que los tejidos cercanos críticos que deben evitarse. Estos tejidos incluyen órganos vitales (por ejemplo, el recto) al igual que estructura ósea (como, el fémur y la pelvis) que atenuarán la radiación. Además se muestra el punto de entrada y la dirección de los únicos dos rayos que se pueden usar con un grado módico de seguridad para este caso. (De hecho, el ejemplo se ha simplificado en este punto, ya que en realidad deben considerarse docenas de rayos posibles)

Para cualquier rayo propuesto de una intensidad dada, el análisis de cuál sería la absorción de radiación resultante en distintas partes del cuerpo requiere un proceso complicado. En resumen, con base en un análisis anatómico cuidadoso, la distribución de energía dentro de un corte transversal de dos dimensiones se puede graficar en un mapa de isodosis en el que las curvas representan la fuerza de la dosis como un porcentaje de la fuerza de la dosis en el punto de entrada. Después se coloca una red fina sobre el mapa de isodosis. Si se suma la radiación absorbida en los cuadros que contienen en cada tipo de tejido, se puede calcular la dosis promedio que absorben el tumor, los tejidos sanos y los tejidos críticos. La absorción de la radiación es aditiva cuando se administra mas de un rayo (en forma secuencial.)

Diseño de terapia de radiación (I)

Mary es una historia moderna sobre el éxito. Ella realmente tiene todo, una carrera exitosa, un papel de liderazgo en su comunidad, muchos amigos y admiradores al igual que un amante esposo y dos preciosos hijos. Pero la tragedia llegó a su vida. Acaban de diagnosticarle cáncer en una etapa bastante avanzada. Específicamente, tiene un tumor grande en el área de la vejiga (una lesión completa en la vejiga).

Su familia ha hecho arreglos para que Mary reciba los cuidados médicos más avanzados disponibles en el país, con el fin de proporcionarle la mejor posibilidad de supervivencia. La única esperanza es una terapia de radiación extensa (en combinación con quimioterapia y cirugia).

La terapia de radiación incluye el uso de una máquina de rayos externos que pasa radiación inonizante a través del cuerpo del paciente dañando tanto los tejidos cancerosos como los sanos. Lo normal es que se administren los rayos con precisión desde diferentes ángulos en un plano de dos dimensiones. Debido a la atenuación, cada rayo descarga más radiación sobre el tejido cercano al punto de entrada que sobre el cercano al punto de salida. La dispersión también causa que parte de la radiación se descargue sobre tejidos que están fuera de la trayectoria directa del rayo. Como las células del tumor casi siempre se encuentran diseminadas de manera microscópica entre células sanas, la dosis de radiación a través de la región del tumor debe ser suficiente para matar las células malignas que son un poco más sensibles a ésta, pero lo suficientemente pequeña  como para no matar las celulas sanas. Al mismo tiempo, la dosis agregada que reciben los tejidos criticos no debe exceder los niveles de tolerancia establecidos con el objeto de prevenir complicaciones que pueden resultar más serias que la enfermedad misma. Por la misma razón, la dosis completa que recibe la anatomía sana debe minimizarse. 


miércoles, 2 de octubre de 2013

Ejemplos adicionales de programación lineal

El problema de la Wyndor Glass Co. es un ejemplo de prototipo de programación lineal en varios aspectos: comprende la asignación de recursos limitados entre actividades que compiten por ellos, su modelo se ajusta a nuestra forma estándar y su contexto es el tradicional de la planeación de la administración para mejorarla. Sin embargo, la aplicación de la programación lineal es mucho más amplia. Esta sección comienza por ampliar el horizonte. Al estudiar los siguientes ejemplos, nótese que lo que los caracteriza como problemas de programación lineal es el modelo matemático, más que su contexto. Para esto, piénsese que el mismo modelo matemático surge en muchos otros contextos con sólo cambiar los nombres de las actividades.

Estos ejemplos se han mantenido de tamaño muy pequeño (según los estándares de programación lineal) para facilitar su lectura. Sin embargo, se pueden resolver rápidamente versiones más grandes de cientos de restricciones y variables. 

Perspectiva de las suposiciones

En la sección 2.2 se hizo hincapié  en que el modelo matemático intenta ser sólo una representación idealizada del problema real. Por lo general se requieren aproximaciones y las suposiciones de simplificación para que el problema se puede manejar. El agregar demasiados detallados y precisión puede hacer que el modelo sea demasiado amplio para llevar a cabo un análisis útil del problema. En realidad, todo lo que se necesita es que exista una correlación relativamente alta entre la predicción del modelo y lo que de hecho pasaría en el problema real.

Este consejo sin duda es aplicable a programación lineal. Es muy frecuente en las aplicaciones reales de esta técnica que casi ninguna de las suposiciones se cumpla. Excepto quizá en lo que se refiere a la suposición de divisibilidad, deben esperarse pequeñas disparidades. Esto es cierto en especial para la suposicion de certidumbre, de manera que es normal que deba aplicarse el análisis de sensibilidad para compensar la violación de esta uposición.

Sin embargo, es importen que el equipo que se está estudiando y analice qué tan grandes son las cuatro suposiciones para el problema que se está estudiando y analice qué tan grandes son las disparidades. Si cualquiera de las suposiciones queda violada de manera importante, entonces se dispone de varios modelos alternativos, como se verá en las siguientes partes de este sitio. Una desventaja de estos modelos es que los algoritmos disponibles para resolverlos no son ni lejanamente tan poderosos como el de programación lineal, pero en algunos casos esto se ha ido solucionando. En algunas aplicaciones se utiliza el poderoso enfoque de programación lineal para el análisis inicial y después se usa un modelo más complicado para refinar este análisis.

Al trabajar con los ejemplos de la siguiente sección, se encontrará que una buen práctica es analizar hasta qué grado se cumplen las suposiciones de programación lineal en estos problemas.


martes, 1 de octubre de 2013

Certidumbre

La suposición de certidumbre dice que todos los parámetros del modelo (los valores aij,bi y cj) son constantes conocidas. En los problemas reales, muy pocas veces se satisface por completo esta suposición. Casi siempre se formula una modelo de programación lineal para elegir un curso de acción futuro. Entonces, los parámetros que se emplean están basados en una predicción de las condiciones futuras, lo que inevitablemente introduce un cierto grado de incertidumbre.

Por esta razón siempre es importante realizar un análisis de sensibilidad después de encontrar una solución óptima para los valores supuestos de los parámetros. Como se presenta en la sección 2.3, el propósito general es identificar los parámetros sensibles (es decir, aquellos que no pueden cambiar mucho sin cambiar la solución óptima), para tratar de estimarlos con mayor exactitud, y después elegir una solución que sea buena en toda la gama de valores posibles para estos parámetros sensibles. Esto es lo que hará el departamento de investigación de operaciones para el problema de la Wyndor Glass Co.

En algunos casos, el grado de incertidumbre en los parámetros es demasiado grande para que el análisis de sensibilidad lo pueda manejar. Entonces es necesario establecer, en forma éxplicita, estos parámetros como variables aleatorias..

Divisibilidad

Algunas variables de decisión sólo tienen significado físico cuando adquieren valores enteros. La solución óptima que se obtiene en programación lineal con mucha frecuencia no es entera. Por esto, la suposición de divisibilidad se refiera a que las unidades de cada actividad se puedan dividir en cualquier nivel fraccional, para que se permitan valores no enteros de las variables de decisión.

En el problema de la Wyndor Glass Co. las variables de decisión representan tasas de producción que pueden tener valores fraccionarios. Algunos de estos valores son más convenientes que otros debido a que corresponden a número de personas y máquinas trabajando tiempo completo en el producto. Sin embargo, el departamento de investigación de operaciones concluyó que se pueden hacer ajustes menores después de utilizar el modelo para analizar el panorama general y para identificar en forma aproximada qué combinacion de tasas de produccion debe adoptarse.

Aun cuando se requiera una solución entera, es frecuente que se aplique programación lineal. Si la solución obtenida no es entera, entonces las variables no enteras simplemente se redondean. Esto puede ser satisfactorio, en particular si las variables de decisión adquieren valores grandes, pero llegan a surgir algunos obstáculos. Si no se puede usar este enfoque, entonces el problema se encuentra en el ámbito de la programación entera.