martes, 31 de diciembre de 2013
Procedimiento global
Existen dos implicaciones importantes en la forma matricial del conjunto de ecuaciones actual. La primera es que sólo es necesario obtener B^-1 para poder calcular todos los números de la tabla símplex a partir de los parámetros originales (A, b, cB) del problema. (Esta implicación es la esencia de la idea fundamental que se describe en la siguiente sección.) La segunda es que cualquiera de estos números (excepto Z = cBB^-1b) se puede obtener al efectuar nadamás una parte de la multiplicación de matrices. Por tanto, se pueden calcular los números requeridos para llevar a cabo una iteración conforme se necesiten sin dedicar todo el esfuerzo computacional que toma obtener todos los números.
lunes, 30 de diciembre de 2013
Ejemplo para ilustrar la forma matricial
Para ilustrar esta forma matricial para el conjunto de ecuaciones actual, considerese el último conjunto de ecuaciones que se obtiene en la iteración 2 para el problema de la Wyndor Glass Co. Si se emplea la B^-1 que se da en la iteración 2.
domingo, 29 de diciembre de 2013
Forma matricial del conjunto de ecuaciones actual (III)
DEbido a que se realiza la misma serie de operaciones algebraicas en ambos lados del conjunto original de ecuaciones, se usa esta misma matriz que premultiplica el lado derecho original para premultiplicar el lado izquierdo original. En consecuencia, como
sábado, 28 de diciembre de 2013
Forma matricial del conjunto de ecuaciones actual (II)
Las operaciones algebraicas realizadas por el método simplex (multiplicar una ecuación por una constante y sumar un múltiplo de una ecuación a otra) se expresan en forma matricial premultiplicando ambos lados del conjunto original de ecuaciones por la matriz apropiada. Esta matriz tiene el mismo número de elementos que la matriz idéntica, excepto que cada múltiplo de una operación algebraica se debe colocar en el lugar que se necesita para que la multiplicación de matrices realice esta operación. Aún después de una serie de operaciones algebraicas a través de varias iteraciones se puede deducir cuál debe ser esta matriz (simbólicamente) en cada paso usando lo que ya se sabe sobre el lado derecho del nuevo conjunto de ecuaciones. En particular, después de cualquier iteración, xB = B^-1b y Z = cBB^-1b, por lo que el lado derecho de las ecuaciones se ha convertido en
viernes, 27 de diciembre de 2013
Forma matricial del conjunto de ecuaciones actual (I)
El último preliminar antes de resumir el método símplex revisado es mostrar la forma matricial del conjunto de ecuaciones que aparece en la tabla símplex en cualquier iteración del método original.
Para el conjunto original de ecuaciones, la forma matricial es
Este conjunto de ecuaciones se exhibe también en la primera tabla símplex de la tabla 5.7
Para el conjunto original de ecuaciones, la forma matricial es
Este conjunto de ecuaciones se exhibe también en la primera tabla símplex de la tabla 5.7
jueves, 26 de diciembre de 2013
Ejemplo Obtención de una solución básica factible
Para ilustrar este método para obtener una solución básica factible, considérese otra vez el problema de la Wyndor Glass Co., presentado en la sección 3.1 que se resolvió empleando el método símplex original en la tabla 4.8. En este caso,
miércoles, 25 de diciembre de 2013
Obtención de una solución básica factible (II)
El método símplex introduce sólo variables básicas tales que B sea no singular, de manera que B^-1 siempre existe. Así, para resolver BxB =b, ambos lados se premultiplicarán por B^-1
martes, 24 de diciembre de 2013
Obtención de una solución básica factible
Recuérdese que el objetivo general del método símplex es obtener una sucesión de soluciones básicas factibles mejoradas hasta alcanzar la solución óptima. Una de las caracteristicas clave del método símplex revisado tiene que ver con la forma en que obtiene cada nueva solución básica factible después de identificar sus variables básicas y no básicas. Dadas estas variables, la solución básica que resulta es la solución de las m ecuaciones.
se obtiene al eliminar las columnas correspondientes a los coeficientes de las variables no básicas de [A, I]. (Aún más los elementos de xb y, por lo tanto, las columnas de B pueden quedar colocadas en diferente orden al ejecutar el método símplex.)
se obtiene al eliminar las columnas correspondientes a los coeficientes de las variables no básicas de [A, I]. (Aún más los elementos de xb y, por lo tanto, las columnas de B pueden quedar colocadas en diferente orden al ejecutar el método símplex.)
lunes, 23 de diciembre de 2013
El método símplex revisado (II)
El método símplex revisado usa explicitamente operaciones con matrices, por lo que se vuelve importante describir el problema en notación matricial. Para ayudar al lector a distinguir entre mátrices, vectores y escalares, usarán siempre letras MAYUSCULAS en negritas para representar matrices, letra minúsculas en negritas para representar vectores y letras cursivas normales en el caso de los escalares. También se usará el cero en negritas (0) para denotar el vector nulo (un vector cuyos elementos son todos cero) ya sea en forma de columna o de renglón (lo que debe ser claro por la forma del problema), mientras que el cero normal (0) seguirá representado el número cero.
So se emplean matrices, nuestra forma estándar del modelo general de programación lineal establecido en la sección 3.2 se convierte en:
So se emplean matrices, nuestra forma estándar del modelo general de programación lineal establecido en la sección 3.2 se convierte en:
domingo, 22 de diciembre de 2013
El método símplex revisado (I)
El método símplex, tal como se describió en el capitulo 4 (y que en adelante se llamará método símplex original) es un procedimiento algebraico directo. Sin embargo, esta forma de ejecutar el algoritmo (ya sea en su forma algebraica o tabular) no es el procedimiento de cálculo más eficiente cuando se trata de emplear una computadora digital, pues calcula y almacena muchos números que no se necesitan para la iteración actual y muchos que ni siquiera son pertinentes para la toma de decisiones en iteraciones subsecuentes. Las únicas cifras importantes en cada iteración son los coeficientes de las variables no básicas en la ecuación (0), los coeficientesde la variable básica entrante en las restricciones y el lado derecho de las ecuaciones. Sería muy útil contar con un procedimiento que obtuviera esta información de manera eficiente sin tener que calcular y almacenar los demás coeficientes.
Como se mencionó en la sección 4.8 estas ideas motivaron el desarrollo del método símplex revisado. Este método se ideó para que lograra exactamente las mismas cosas que el método símplex original, pero que, al llevarlo a la computadora, las hiciera en una forma más eficiente. Así, se trata de una versión simplificada del procedimiento original. Calcula y almacena sólo la información que se necesita en el momento y guarda los datos esenciales de manera más compacta.
Como se mencionó en la sección 4.8 estas ideas motivaron el desarrollo del método símplex revisado. Este método se ideó para que lograra exactamente las mismas cosas que el método símplex original, pero que, al llevarlo a la computadora, las hiciera en una forma más eficiente. Así, se trata de una versión simplificada del procedimiento original. Calcula y almacena sólo la información que se necesita en el momento y guarda los datos esenciales de manera más compacta.
El método símplex comienza con una solución básica factible
El método símplex comienza con una solución básica factible y se mueve en forma iterativa a una solución básica adyacente mejor, hasta que logra una solución óptima. Cómo se alcanza la solución básica factible adyacente en cada iteración?
Recuérdese que para el problema original se obtiene una solución en un vértice adyacente a partir de la solución actual cuando: 1) se elimina una ecuación de frontera (ecuación de definición) del conjunto n restricciones que definen la solución actual, 2) se hace un movimiento alejándose de la solución actual, enla dirección factible a lo largo de las (n-1) restricciones de frontera (una arista de la región factible) restantes y 3) el movimiento se detiene al encontrar la primera restricción (ecuación de definición) nueva.
De manera equivalente, en la terminología nueva el método simplex llega a una solución básica factible adyacente a partir de la solución actual cuando: 1) se elimina una variable (la variable básica entrante) del conjunto de n variables no básicas que definen la solución actual, 2) se aleja de la solución actual incrementando el valor de esta variable (y ajustando las otras variables básicas para que sigan satisfaciendo el sistema de ecuaciones) y manteniendo las (n-1) variables restantes a nivel cero y 3) se detiene cuando el valor de la primera variable básica (la variable básica que sale) llega a cero (a su ecuación de frontera). Con cualquiera de estas dos interpretaciones, la elección entre las n alternativas en el paso 1 se hace escogiendo aquella que da la tasa más alta para mejorar el valor de Z (por cada unidad de incremento de la variable básica entrante) durante el paso 2.
Recuérdese que para el problema original se obtiene una solución en un vértice adyacente a partir de la solución actual cuando: 1) se elimina una ecuación de frontera (ecuación de definición) del conjunto n restricciones que definen la solución actual, 2) se hace un movimiento alejándose de la solución actual, enla dirección factible a lo largo de las (n-1) restricciones de frontera (una arista de la región factible) restantes y 3) el movimiento se detiene al encontrar la primera restricción (ecuación de definición) nueva.
De manera equivalente, en la terminología nueva el método simplex llega a una solución básica factible adyacente a partir de la solución actual cuando: 1) se elimina una variable (la variable básica entrante) del conjunto de n variables no básicas que definen la solución actual, 2) se aleja de la solución actual incrementando el valor de esta variable (y ajustando las otras variables básicas para que sigan satisfaciendo el sistema de ecuaciones) y manteniendo las (n-1) variables restantes a nivel cero y 3) se detiene cuando el valor de la primera variable básica (la variable básica que sale) llega a cero (a su ecuación de frontera). Con cualquiera de estas dos interpretaciones, la elección entre las n alternativas en el paso 1 se hace escogiendo aquella que da la tasa más alta para mejorar el valor de Z (por cada unidad de incremento de la variable básica entrante) durante el paso 2.
viernes, 20 de diciembre de 2013
Extensiones a la forma de igualdades del problema (V)
De igual manera, las otras tres soluciones en los vértices llevan a las otras soluciones básicas que se muestran en la tabla 5.6.
Los otros dos conjuntos de variables de definición -1) x1 y x3 y 2) x2 y x4 - no conducen a una solución básica para el sistema de ecuaciones 1) -3) que se da en la tabla 5.4 Esta conclusión se equipara a la observación que se hizo antes respecto a que los conjuntos correspondientes de ecuaciones de definición no conducen a una solución.
Los otros dos conjuntos de variables de definición -1) x1 y x3 y 2) x2 y x4 - no conducen a una solución básica para el sistema de ecuaciones 1) -3) que se da en la tabla 5.4 Esta conclusión se equipara a la observación que se hizo antes respecto a que los conjuntos correspondientes de ecuaciones de definición no conducen a una solución.
jueves, 19 de diciembre de 2013
Extensiones a la forma de igualdades del problema (IV)
Ya se hizo notar que no todo conjunto de n ecuaciones de frontera conduce a una solución en un vértice, ya sea porque el sistema no tiene soluciones o porque tiene soluciones múltiples. Por razones análogas, no todo conjunto de n variables no básicas conduce a una solución básica. Sin embargo, el método símplex evita los casos.
Para ejemplificar estas definiciones, considérese una vez más el ejemplo de la Wyndor Glass Co. Sus ecuaciones de frontera y las variables indicativa se muestran en la tabla 5.4.
Al aumentar las soluciones factibles en los vértices (véase la tabla 5.1) se obtienen las soluciones básicas factibles enumeradas en la tabla 5.5. En esta tabla se han colocado junta las soluciones básicas factibles adyacentes, excepto el par formado por la primera y la última. Nótese que en todos los casos, las variables no básicas son necesariamente las variables indicativas de las ecuaciones de definición. Entonces, las soluciones básicas factibles adyacentes difieren en que tienen sólo una variable no básica distinta. También nótese que cada solución básica factible es necesariamente la solución simultánea del sistema de ecuaciones para el problema en forma aumentada (véase la tabla 5.4) cuando las variables no básicas se igualan a cero.
Para ejemplificar estas definiciones, considérese una vez más el ejemplo de la Wyndor Glass Co. Sus ecuaciones de frontera y las variables indicativa se muestran en la tabla 5.4.
Al aumentar las soluciones factibles en los vértices (véase la tabla 5.1) se obtienen las soluciones básicas factibles enumeradas en la tabla 5.5. En esta tabla se han colocado junta las soluciones básicas factibles adyacentes, excepto el par formado por la primera y la última. Nótese que en todos los casos, las variables no básicas son necesariamente las variables indicativas de las ecuaciones de definición. Entonces, las soluciones básicas factibles adyacentes difieren en que tienen sólo una variable no básica distinta. También nótese que cada solución básica factible es necesariamente la solución simultánea del sistema de ecuaciones para el problema en forma aumentada (véase la tabla 5.4) cuando las variables no básicas se igualan a cero.
miércoles, 18 de diciembre de 2013
Extensiones a la forma de igualdades del problema (III)
Ahora considérense las soluciones básicas factibles. Se puede observar que los únicos requisitos para que una solución sea factible en la forma aumentada del problema son que satisfaga el sistema de ecuaciones y que todas las variables sean no negativas.
Una solución factible es aquella en la que la m variables básicas son no negativas (≥0). Se dice que una solución básica factible es degenerada si cualquiera de estas m variables es igual a cero.
Una solución factible es aquella en la que la m variables básicas son no negativas (≥0). Se dice que una solución básica factible es degenerada si cualquiera de estas m variables es igual a cero.
martes, 17 de diciembre de 2013
Extensiones a la forma de igualdades del problema (II)
En este punto deben aclararse las relaciones algebraicas entre las soluciones básicas y las soluciones en vértices. Recuérdese que cada solución en un vértice es la solución simultánea de un sistema de n ecuaciones de frontera, a las que se dio el nombre de ecuaciones de definición. La pregunta clave es: "cómo puede distinguirse cuando una ecuación de frontera en particular es una de las ecuaciones de definción si el problema se encuentra en forma aumentada?" Por fortuna, la respuesta es sencilla. Como ahora se cuenta con (n+m) variables, una para cada una de las (n+m) restricciones, cada restricción tiene exactamente una variable indicativa que marca por completo (según si su valor es cero o no) cuando la solución actual satisface la ecuación de frontera de esa restricción.
Así pues, siempre que la ecuación de frontera de una restricción sea una de las ecuaciones de definición, la variable indicativa tiene valor cero en la forma aumentada del problema. Cada una de estas variables indicativas se llama variable no básica para la solución básica correspondiente. En seguida se resumen las conclusiones y la terminología (que ya se introdujo en la sección 4.2).
Cada solución básica tiene n variables no básicas iguales a cero. Los valores de las m variables restantes (llamadas variables básicas) constituyen la solución simultánea del sistema de m ecuaciones del problema en la forma aumentada ( después de igualar a cero las variables no básicas). Esta solución básica es la solución en el vértice aumentada cuyas n ecuaciones de definición son las indicadas por las variables no básicas.
Así pues, siempre que la ecuación de frontera de una restricción sea una de las ecuaciones de definición, la variable indicativa tiene valor cero en la forma aumentada del problema. Cada una de estas variables indicativas se llama variable no básica para la solución básica correspondiente. En seguida se resumen las conclusiones y la terminología (que ya se introdujo en la sección 4.2).
Cada solución básica tiene n variables no básicas iguales a cero. Los valores de las m variables restantes (llamadas variables básicas) constituyen la solución simultánea del sistema de m ecuaciones del problema en la forma aumentada ( después de igualar a cero las variables no básicas). Esta solución básica es la solución en el vértice aumentada cuyas n ecuaciones de definición son las indicadas por las variables no básicas.
lunes, 16 de diciembre de 2013
Extensiones a la forma de igualdades del problema (I)
En cualquier problema de programación lineal en nuestra forma estandar la apariencia de las restricciones funcionales después de introducir variables de holgura.
en donde x(n+1), x(n+2),.......,x(n+m) son variables de holgura. En la sección 4.6 se describió cómo puede obtenerse esta misma forma (la forma apropiada de eliminación Gaussiana) para otros problemas de programación líneal, introduciendo variables artificiales, etc. Entonces las soluciones originales (x1, x2,......,xn) quedan aumentadas con los valores correspondientes de las variables de holgura o artificiales (xn+1, xn+2,........., xn+m). A partir de este aumento, en la seccion 4.2 se definieron las soluciones básicas como soluciones aumentadas en un vértice y las soluciones básicas factibles como soluciones factibles aumentadas en un vértice. En consecuencia, las tres propiedades anteriores de las soluciones factibles en un vértice también se cumplen para las soluciones básicas factibles.
en donde x(n+1), x(n+2),.......,x(n+m) son variables de holgura. En la sección 4.6 se describió cómo puede obtenerse esta misma forma (la forma apropiada de eliminación Gaussiana) para otros problemas de programación líneal, introduciendo variables artificiales, etc. Entonces las soluciones originales (x1, x2,......,xn) quedan aumentadas con los valores correspondientes de las variables de holgura o artificiales (xn+1, xn+2,........., xn+m). A partir de este aumento, en la seccion 4.2 se definieron las soluciones básicas como soluciones aumentadas en un vértice y las soluciones básicas factibles como soluciones factibles aumentadas en un vértice. En consecuencia, las tres propiedades anteriores de las soluciones factibles en un vértice también se cumplen para las soluciones básicas factibles.
domingo, 15 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (VI)
Por el contrario, la figura 5.3 muestra una región factible que nunca puede ocurrir en un problema de programación líneal, pero que viola la propiedad 3. El problema que se muestra es idéntico al de la Wyndor Glass Co. (incluso con la misma función objetivo) excepto que se aumentó la región factible hacia la derecha de (8/3, 5). Así, las soluciones factibles en un vértice adyacentes a (2,6) son ahora (0,6) y (8/3, 5). y de nuevo ninguna delas dos es mejor que (2,6). Sin embargo, ahora otra solución factible en un vértice, (4,5), es mejor que (2,6), lo que viola la propiedad 3. La razón es que la frontera de la región factible va de (2,6) a (8/3,5) y después "dobla hacia afuera" hasta (4,5), más allá de la línea de la función objetivo que pasa pr (2,6).
El punto clave es que el tipo de situación que se ilustra en la figura 5.3 no puede ocurrir en programación líneal. La región factible en esta figura implica que las restricciones 2x2 ≤ 12 y 3x1 + 2x2 ≤ 18 se cumplen para 0 ≤ x1 ≤ (8/3). Sin embargo, bajo la condición de que 8/3 ≤ x1 ≤4, la restricción 2x1 + 2x2 ≤ 18 se elimina y la reemplaza x2 ≤5. Este tipo de "restricciones condicionales" simplemente no están permitidos en la programación líneal.
El punto clave es que el tipo de situación que se ilustra en la figura 5.3 no puede ocurrir en programación líneal. La región factible en esta figura implica que las restricciones 2x2 ≤ 12 y 3x1 + 2x2 ≤ 18 se cumplen para 0 ≤ x1 ≤ (8/3). Sin embargo, bajo la condición de que 8/3 ≤ x1 ≤4, la restricción 2x1 + 2x2 ≤ 18 se elimina y la reemplaza x2 ≤5. Este tipo de "restricciones condicionales" simplemente no están permitidos en la programación líneal.
sábado, 14 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (V)
La propiedad 2 sugiere que puede obtenerse una solución óptima mediante la enumeración exhaustiva, esto es, se pueden encontrar y comparar todas las soluciones factibles en los vértices, pues son un número finito. Desafortunadamente existen números finitos que (para propósitos prácticos) bien podráin ser infinitos. Por ejemplo, un problema de programación líneal bastante pequeño que consta de sólo m = 50 restricciones y n =50 variables, tendría (100!)/(50!) ≈ 10^29 sistemas de ecuaciones que resolver. En contraste, el método símplex necesitaría examinar nada más alrededor de 100 soluciones factibles en los vértices para un problema de este tamaño. este ahorro tan grande se puede obtener gracias a la prueba de optimalidad que proporciona la propiedad 3:
Propiedad 3. Si una solución factible en un vértice no tiene soluciones factibles en vértices adyacentes que sean mejores (en cuanto al valor de Z), entonces no existen soluciones factibles en un vértice que sean mejores, es decir, la solución es óptima.
A manera de ilustración de la propiedad 3 considérese la figura 5.1 (o la figura 3.3) para el ejemplo de la Wyndor Glass Co. Las soluciones facrtibles en los vértices (0,6) y (4,3) son adyacentes a la solución factible en el vértice (2,6) y ninguna te las dos tiene un valor mejor de Z. Esto implica que ninguna de las otras soluciones factibles en un vértice (0,0) y (0,4), pueden ser mejores que (2,6) y por lo tanto (2,6) debe ser óptima.
viernes, 13 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (IV)
El significado real de la propiedad 1 es que simplifica la búsqueda de la solución óptima, ya que sólo tienen que tomarse en cuenta las soluciones factibles en los vértices. La propiedad 2 pone de relieve la magnitud de esta simplificación.
Propiedad 2. Existe sólo un número finito de soluciones factibles en los vértices.
Esta propiedad sin duda se cumple en las figuras 5.1 y 5.2 donde nada más se tienen cinco y diez soluciones factibles en un vértice, respectivamente. Para ver por qué en general este número es finito, recuérdese que cada solución factible en un vértice es la solución simultánea de un sistema de n entre (m +n) ecuaciones de frontera de restricción. El número de combinaciones diferentes de las (m+n) ecuaciones tomadas n a la vez es:
(m+n)!/m!n!
Que es un número finito. Este número a su vez, es una cota superior para el número de soluciones factibles en los vertices. En la figura 5.1 m=3 y n=2, de manera que existen 10 sistemas diferentes de dos ecuaciones, pero sólo la mitad de ellos son soluciones factibles en un vértice. En la figura 5.2., m=4 y n =2, de manera que hay 35 sistemas diferentes de tres ecuaciones, pero sólo 10 conducen a soluciones factibles en un vértice.
Propiedad 2. Existe sólo un número finito de soluciones factibles en los vértices.
Esta propiedad sin duda se cumple en las figuras 5.1 y 5.2 donde nada más se tienen cinco y diez soluciones factibles en un vértice, respectivamente. Para ver por qué en general este número es finito, recuérdese que cada solución factible en un vértice es la solución simultánea de un sistema de n entre (m +n) ecuaciones de frontera de restricción. El número de combinaciones diferentes de las (m+n) ecuaciones tomadas n a la vez es:
(m+n)!/m!n!
Que es un número finito. Este número a su vez, es una cota superior para el número de soluciones factibles en los vertices. En la figura 5.1 m=3 y n=2, de manera que existen 10 sistemas diferentes de dos ecuaciones, pero sólo la mitad de ellos son soluciones factibles en un vértice. En la figura 5.2., m=4 y n =2, de manera que hay 35 sistemas diferentes de tres ecuaciones, pero sólo 10 conducen a soluciones factibles en un vértice.
jueves, 12 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (III)
Como las ponderaciones α y (1-α) suman 1, las únicas posibilidades que se tienen al conparar Z*, Z1 y Z2 son: 1) Z* = Z1 = Z2, 2)Z1 < Z* Z* > Z2. La primera posibilidad implica que x' y x'' también son óptimas, lo que contradice la suposición de que se cumple el caso del inciso a. Las otras posibilidades contradicen la suposición inicial de que x* es óptima. En conclusión, es imposible tener siquiera una solución óptima que no sea una solución factible en un vértice.
Ahora considérese el caso del inciso b que se demostró en la sección 3.2 bajo la definición de solución óptima cambiando la función objetivo del ejemplo a Z = 3x1 + 2x2. Lo que ocurre en el procedimiento gráfico es que la recta que representa la función objetivo se mueve hacia arriba hasta que contiene el segmento que conecta la dos soluciones factibles en los vértices (2,6) y (4,3). Lo mismo pasa en dimensiones más altas, excepto que en este caso la función objetivo es un hiperplano que se mueve hasta que contiene el o los segmentos que conectan dos (o más) soluciones factibles en los vértices. Como consecuencia, es posible obtener todas las soluciones óptimas como promedios ponderados de soluciones óptimas factibles en los vértices.
Ahora considérese el caso del inciso b que se demostró en la sección 3.2 bajo la definición de solución óptima cambiando la función objetivo del ejemplo a Z = 3x1 + 2x2. Lo que ocurre en el procedimiento gráfico es que la recta que representa la función objetivo se mueve hacia arriba hasta que contiene el segmento que conecta la dos soluciones factibles en los vértices (2,6) y (4,3). Lo mismo pasa en dimensiones más altas, excepto que en este caso la función objetivo es un hiperplano que se mueve hasta que contiene el o los segmentos que conectan dos (o más) soluciones factibles en los vértices. Como consecuencia, es posible obtener todas las soluciones óptimas como promedios ponderados de soluciones óptimas factibles en los vértices.
miércoles, 11 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (II)
El punto de vista algebraico siguiente también aclara por qué en el caso del inciso a la propiedad debe cumplirse. Se desarrollará una demostración por contradicción suponiendo que esa solución óptima no es una solución factible en un vértice y demostrando que esta suposición lleva a una contradicción y por lo tanto no puede ser cierta. El paso más importante es observar, a partir de la definición de solución factible en un vértice que esta suposición implica que deben existir otras dos soluciones factibles tales que el segmento de línea que las une contiene la solución óptima. Sean x*, x', x'''los vectores que denotan la solución óptima y estas otras dos soluciones óptimas respectivamente, y sean Z*, Z1, Z2 los valores respectivos de la función objetivo. Igual que para cualquier otro punto sobre el segmento de línea que conecta x' y x''
x* = αx'' + (1+α )x'
para algún valor de α tal que 0 < α < 1. Entonces
Z* = αZ2 + (1-α )Z1
martes, 10 de diciembre de 2013
Propiedades de las soluciones factibles en un vértice (I)
En la sección 4.1 se habló de propiedades clave de las soluciones factibles en los vértices que constituyen los principios fundamentales del método símplex. En este momento se tiene la posibilidad de explicar por qué estas propiedades (que se acaban de restablecer) de hecho se cumplen para cualquier problema de programación lineal que tiene soluciones factibles y una región factible acotada.
Propiedad 1. a) Si el problema tiene exactamente una solución óptima, entonces ésta debe ser una solución factible en un vértice; b) si el problema tiene soluciones múltiples, entonces al menos dos deben ser soluciones factibles en vértices adyacentes.
La propiedad 1 es un concepto bastante intuitivo desde el punto de vista geométrico. Primero, considérese el caso del inciso a que se ilustra con el problema de la Wyndor Glass Co., el que la única solución óptima (2,6) es sin duda una solución factible en un vértice. Nótese que nada especial hay en el ejemplo que lleve a este resultado. Para cualquier problema que tiene sólo una solución óptima, siempre es posible seguir elevando la línea (hiperplano) de la función objetivo hasta que nada más toque en un punto (la solución óptima), esquina o vértice, de la región factible.
Propiedad 1. a) Si el problema tiene exactamente una solución óptima, entonces ésta debe ser una solución factible en un vértice; b) si el problema tiene soluciones múltiples, entonces al menos dos deben ser soluciones factibles en vértices adyacentes.
La propiedad 1 es un concepto bastante intuitivo desde el punto de vista geométrico. Primero, considérese el caso del inciso a que se ilustra con el problema de la Wyndor Glass Co., el que la única solución óptima (2,6) es sin duda una solución factible en un vértice. Nótese que nada especial hay en el ejemplo que lleve a este resultado. Para cualquier problema que tiene sólo una solución óptima, siempre es posible seguir elevando la línea (hiperplano) de la función objetivo hasta que nada más toque en un punto (la solución óptima), esquina o vértice, de la región factible.
Propiedades de las soluciones factibles en un vértice (VII)
La razón básica para que la propiedad 3 se cumpla es que en cualquier problema de programación lineal la región factible siempre tiene la propiedad de ser un conjunto convexo, como se define en el apéndice 1 se ilustra en varias figuras ahí mismo. Para un problema de dos variables, esta propiedad de convexo que significa que el ángulo dentro de la región factible en todas las solucione factibles en un vértice es menor a 180°. Esto se ilustra en la figura 5.1 en donde los ángulos en (0,0), (0,6) y (4,0) son de 90° y aquellos en (2,6) y (4,3) tienen entre 90° y 180°. Por el contrario, la región factible de la figura 5.3 no es un conjunto convexo debido a que el ángulo en (8/3, 5) es mayor a 180°. Éste es el tipo de "doblez hacia afuera" en un angulo mayor a 180° que no puede ocurrir en programación líneal. En problemas de n dimensiones se sigue aplicando este concepto intuitivo de "nunca doblar hacia afuera".
Para aclarar el significado de región factible convexa, considérese el hiperplano de la función objetivo que pasa por una solución factible en un vértice, y que es igual o mejor que todas las soluciones factibles en vértices adyacentes. [En el ejemplo original de la Wyndor Glass Co. este hiperplano es la recta que pasa por (2,6) en la figura 3.3] Todas estas soluciones adyacentes [(0,6) y (4,3) en el ejemplo] deben estar ya sea en el hiperplano o en el lado no favorable (según lo mide el valor de Z) del hiperplano. El que la región factible sea convexa significa que su frontera no se puede "doblar hacia afuera" más allá de una solución factible en un vértice adyacente para dar una solución que se encuentre en el lado favorable del hiperplano de manera que la propiedad 3 se cumple.
Para aclarar el significado de región factible convexa, considérese el hiperplano de la función objetivo que pasa por una solución factible en un vértice, y que es igual o mejor que todas las soluciones factibles en vértices adyacentes. [En el ejemplo original de la Wyndor Glass Co. este hiperplano es la recta que pasa por (2,6) en la figura 3.3] Todas estas soluciones adyacentes [(0,6) y (4,3) en el ejemplo] deben estar ya sea en el hiperplano o en el lado no favorable (según lo mide el valor de Z) del hiperplano. El que la región factible sea convexa significa que su frontera no se puede "doblar hacia afuera" más allá de una solución factible en un vértice adyacente para dar una solución que se encuentre en el lado favorable del hiperplano de manera que la propiedad 3 se cumple.
lunes, 9 de diciembre de 2013
Soluciones factibles en vértices adyacentes (VI)
En seguida se analizarán algunas propiedades importantes de las soluciones factibles en un vértice y se describirán las implicaciones de todos estos conceptos al interpretar el método símplex. Sin embargo, ahora que se tiene fresco el resumen anterior, se expondrá un panorama general de estas implicaciones. Cuando el método símplex elige una variable básica entrante, la interpretación geométrica es que está eligiendo una de las aristas que emanan de la solución factible en un vértice actual para trasladarse sobre ella. El aumento en el valor de esta variable (y al mismo tiempo el cambio en los valores de las otras variables básicas según sea necesario) corresponde a moverse a lo largo de esta arista. El que la primera variable básica llegue a cero (la variable básica que sale) corresponde a llegar a la primera frontera de restricción nueva en la otra punta de esta arista de la región factible.
domingo, 8 de diciembre de 2013
Soluciones factibles en vértices adyacentes (V)
Cuando n>3, estos mismos conceptos se generalizan a mayores dimensiones, sólo que las fronteras de restricción son ahora hiperplanos en lugar de planos. Para resumir:
Una solución factible en un vértice se encuentra en la intersección de n fronteras de restricción (y satisface también las otras restricciones). Una arista de la región factible es un segmento de línea factible que se encuentra en la intersección de (n-1) fronteras de restricción, en el que cada punto terminal se encuentra en una frontera de restricción adicional (por lo que estos puntos terminales son soluciones factibles en un vértice). Dos soluciones factibles en un vértice son adyacentes si el segmento de línea que las conecta es una arista de la región factible. De cada solución factible en un vértice emanan n aristas, cada una lleva a una de las n soluciones factibles en un vértice adyacentes. Cada iteración del método símplex se mueve de la solución factible en un vértice actual a una adyacente a lo largo de una de estas n aristas.
Al cambiar del punto de vista geométrico al algebraico, la intersección de fronteras de restricción cambia a la solución simultánea de las ecuaciones de frontera de restricción. Las n ecuaciones de frontera que llevan a (definen) una solución factible en un vértice son las ecuaciones de definición, y al eliminar una de estas ecuaciones se obtiene una línea cuyo segmento factible es una arista de la región factible.
Una solución factible en un vértice se encuentra en la intersección de n fronteras de restricción (y satisface también las otras restricciones). Una arista de la región factible es un segmento de línea factible que se encuentra en la intersección de (n-1) fronteras de restricción, en el que cada punto terminal se encuentra en una frontera de restricción adicional (por lo que estos puntos terminales son soluciones factibles en un vértice). Dos soluciones factibles en un vértice son adyacentes si el segmento de línea que las conecta es una arista de la región factible. De cada solución factible en un vértice emanan n aristas, cada una lleva a una de las n soluciones factibles en un vértice adyacentes. Cada iteración del método símplex se mueve de la solución factible en un vértice actual a una adyacente a lo largo de una de estas n aristas.
Al cambiar del punto de vista geométrico al algebraico, la intersección de fronteras de restricción cambia a la solución simultánea de las ecuaciones de frontera de restricción. Las n ecuaciones de frontera que llevan a (definen) una solución factible en un vértice son las ecuaciones de definición, y al eliminar una de estas ecuaciones se obtiene una línea cuyo segmento factible es una arista de la región factible.
sábado, 7 de diciembre de 2013
Soluciones factibles en vértices adyacentes (IV)
Para n=3, todas las aristas de la región factible se forman de esta manera, como el segmento factible de la línea que está en la intersección de dos fronteras de restricción y los dos puntos terminales de una arista son soluciones factibles en un vértice adyacentes. En la figura 5.2 hay 15 aristas de la región factible y tanto hay 15 pares de soluciones factibles en un vértice adyacente. Para la solución factible en un vértice actual (2,4,3) hay tres formas de eliminar una de sus tres ecuaciones de definición para obtener la intersección de las otras dos fronteras de restricción, así hay tres aristas que emanan de (2,4,3). Estas aristas llevan a (4,2,4), (0,4,2) y (2,4,0) y éstas son las soluciones factibles en un vértice adyacentes a (2,4,3).
En la siguiente iteración, el método símplex elige una de estas tres aristas, digamos el segmento de línea más oscuro y se mueve a lo largo de él alejándose de (2,4,3) hasta que llega a la primera frontera de restricción nueva x1 = 4 en la otra punta. [No se puede continuar por esta línea hasta la siguiente frontera de restricción, x1 = 0, porque se llegaría a una solución no factible en un vértice, (6,0,5)]. la intersección de esta primera frontera de restricción nueva con las dos fronteras de restricción que forman la arista conduce a la nueva solución factible en un vértice, (4,2,4).
En la siguiente iteración, el método símplex elige una de estas tres aristas, digamos el segmento de línea más oscuro y se mueve a lo largo de él alejándose de (2,4,3) hasta que llega a la primera frontera de restricción nueva x1 = 4 en la otra punta. [No se puede continuar por esta línea hasta la siguiente frontera de restricción, x1 = 0, porque se llegaría a una solución no factible en un vértice, (6,0,5)]. la intersección de esta primera frontera de restricción nueva con las dos fronteras de restricción que forman la arista conduce a la nueva solución factible en un vértice, (4,2,4).
viernes, 6 de diciembre de 2013
Soluciones factibles en vértices adyacentes (III)
Cuando n=3, las respuestas son un poco más complejas. Para ayudar y visualizar lo que ocurre, la figura 5.2 muestra un dibujo en tres dimensiones de una región factible representativas para este caso, en la que los puntos son las soluciones en los vértices. Esta región factible es un poliedro en lugar del polígono que se tenía para n = 2 (figura 5.1), ya que las fronteras de restricción son ahora planos y no líneas. Las caras del poliedro forman la frontera de la región factible, donde cada cara es la porción de la frontera de restricción que también satisface a las otras restricciones. Nótese que cada solución factible en un vértice se encuentra en la intersección de tres fronteras de restricción (quizá incluyendo para de las frontera de restricción x1 = 0, x2 = 0 y x3 = 0 para las restricciones de no negatividad) y que la solución también satisface las otras restricciones. Las intersecciones que no satisfacen una o más de las otras restricciones llevan a soluciones no factible en un vértice.
El segmento de línea más oscuro en la figura 5.2 traza la trayectoría que sigue el método símplex en una iteración normal. El punto (2.4.3) es la solución factible en un vértice actual que se usa para iniciar una iteración y el punto (4,2,4) será la nueva solución factible en un vértice al término de la iteración. El punto (2,4,3) se encuentra en la intersección de la frontera de restricción x2 = 4, x1 + x2 =6 y -x1 + 2x3 =4, por lo que estas tres ecuaciones son las ecuaciones de definición para esta solución factible en un vértice. Si se eliminara la ecuación de definición x2 = 4, la intersección de las otras dos fronteras de restricción (planos) formarían una línea. Un segmento de esta línea, que se muestra en la figura5.2 como el segmento más oscuro que va de (2,4,3) a (4,2,4), está sobre la frontera de la región factible, mientras que el resto de la línea es no factible. Este segmento de línea se llama arista de al región factible y sus puntos terminales (2,4,3) y (4,2,4) son soluciones factibles en un vértice adyacentes.
El segmento de línea más oscuro en la figura 5.2 traza la trayectoría que sigue el método símplex en una iteración normal. El punto (2.4.3) es la solución factible en un vértice actual que se usa para iniciar una iteración y el punto (4,2,4) será la nueva solución factible en un vértice al término de la iteración. El punto (2,4,3) se encuentra en la intersección de la frontera de restricción x2 = 4, x1 + x2 =6 y -x1 + 2x3 =4, por lo que estas tres ecuaciones son las ecuaciones de definición para esta solución factible en un vértice. Si se eliminara la ecuación de definición x2 = 4, la intersección de las otras dos fronteras de restricción (planos) formarían una línea. Un segmento de esta línea, que se muestra en la figura5.2 como el segmento más oscuro que va de (2,4,3) a (4,2,4), está sobre la frontera de la región factible, mientras que el resto de la línea es no factible. Este segmento de línea se llama arista de al región factible y sus puntos terminales (2,4,3) y (4,2,4) son soluciones factibles en un vértice adyacentes.
jueves, 5 de diciembre de 2013
Soluciones factibles en vértices adyacentes (II)
La respuesta a estas preguntas es sencilla cuando n=2. En este caso la frontera de la región factible consiste de varios segmentos de línea conectados que forman un polígono, como se muestra en la figura 5.1 con los cinco segmentos más oscuros. Estos segmentos de líneas se conocen como aristas de la región factible. De cada solución factible en un vértice emanan dos de estas aristas que llevan a una solución factible en un vértice adyacente en la otra punta (Nótese en la figura 5.1 que cada solución factible en un vértice tiene dos soluciones adyacentes) Cada iteración sigue una trayectoria a lo largo de estas aristas moviéndose de una punta a otra. En la figura 5.1 la primera iteración se mueve a lo largo de la arista que va de (0,0) a (0,6), y en el siguiente se mueve por la arista que va de (0,6) a (2,6). Como se puede ver en la tabla 5.1, cada uno de estos movimientos a una solución factible en un vértice significa sólo un cambio en el conjunto de ecuaciones de definición (fronteras de restricción sobre las que se encuentra la solución)
miércoles, 4 de diciembre de 2013
Soluciones factibles en vértices adyacentes (I)
Ahora se analizaran las soluciones factibles en vértices adyacentes y el papel que juegan en la solución de problemas de programación lineal. Recuérdese que en el capitulo 4 al ignorar las variables de holgura y artificiales, cada iteración del método símplex se mueve de la solución factible en el vértice actual a uno adyacente. Cuál es la trayectoria que sigue este proceso? Qué significa en realidad una solución factible en un vértice adyacente? Primero se contestará a estas preguntas desde el punto de vista geométrico y después se dará la interpretación algebraica.
martes, 3 de diciembre de 2013
Fundamentos del método símplex - Terminología (IV)
No obstante, esto no quiere decir que todo conjunto de n ecuaciones frontera que se elija entre las (n+m) restricciones (n restricciones de no negatividad y m funcionales) conduzca a una solución factible en un vértice. En particular, la solución simultánea de algún sistema puede violar una o más de las otras m restricciones no seleccionadas, en cuyo caso se trata de una solución no factible en un vértice. El ejemplo tiene tres soluciones de este tipo, y en la tabla 5.2 se resume esta situación.
Más aún, un sistema de n ecuaciones de frontera puede no tener solución. Esto ocurre dos veces en el ejemplo con los pares de ecuaciones 1) x1=0 y x1 = 4, y 2) x2 = 0 y 2x2 = 12. Tales sistemas no son de interés en el contexto de este blog.
La última posibilidad (que nunca ocurre en el ejemplo) es que un sistema de n ecuaciones de frontera tenga soluciones múltiples ocasionadas por una ecuación redundante. Tampoco es necesario preocuparse por este caso, ya que el método símplex salva estas dificultades.
Para resumir, en el ejemplo con cinco restricciones y dos variables existen 10 pares de ecuaciones frontera. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles en los vértices, tres se vuelven ecuaciones de definición para soluciones no factibles en un vértice y cada uno de los otros dos pares no tiene solución.
Más aún, un sistema de n ecuaciones de frontera puede no tener solución. Esto ocurre dos veces en el ejemplo con los pares de ecuaciones 1) x1=0 y x1 = 4, y 2) x2 = 0 y 2x2 = 12. Tales sistemas no son de interés en el contexto de este blog.
La última posibilidad (que nunca ocurre en el ejemplo) es que un sistema de n ecuaciones de frontera tenga soluciones múltiples ocasionadas por una ecuación redundante. Tampoco es necesario preocuparse por este caso, ya que el método símplex salva estas dificultades.
Para resumir, en el ejemplo con cinco restricciones y dos variables existen 10 pares de ecuaciones frontera. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles en los vértices, tres se vuelven ecuaciones de definición para soluciones no factibles en un vértice y cada uno de los otros dos pares no tiene solución.
lunes, 2 de diciembre de 2013
Fundamentos del método símplex - Terminología (III)
Según esta definición, una solución factible está sobre un segmento de línea que conecta otras dos soluciones factibles no es una solución factible en un vértice. Para dar un ejemplo cuando n=2, considérese la figura 5.1. El punto (2,3) no es una solución factible en un vértice puesto que se encuentra en varios de estos segmentos, por ejemplo, en el segmento de línea que conecta los puntos (0,3) y (4,3). De igual manera, (0,3) no es una solución factible en un vértice ya que se encuentra sobre el segmento de línea que conecta (0,0) con (0,6). Sin embargo, (0,0) es una solución factible en un vértice porque es imposible encontrar otras dos soluciones factibles que se encuentren en lados completamente opuestos de (0,0).
Cuando el número de variables de decisión es mayor que 2 o 3, esta definición no es muy conveniente para identificar soluciones factibles en los vértices. Por tanto, una interpretación algebraica de estas soluciones resultará muy útil. En el ejemplo de la Wyndor Glass Co. cada solución factible en un vértice en la figura 5.1 está en la intersección de dos (n=2) líneas de restricción; es decir, es una solución simultánea de un sistema de dos ecuaciones frontera.
Esta situación se resume en la tabla 5.1, en las que las ecuaciones de definición se refieren a las ecuaciones de la frontera de las restricciones que definen o conducen hacia las soluciones factibles en un vértice indicadas. De manera similar, en cualquier problema de programación lineal, cada solución factible en un vértice se encuentra en la intersección de n fronteras de restricción; esto es, se trata de una solución simultánea de un sistema de n ecuaciones frontera.
Cuando el número de variables de decisión es mayor que 2 o 3, esta definición no es muy conveniente para identificar soluciones factibles en los vértices. Por tanto, una interpretación algebraica de estas soluciones resultará muy útil. En el ejemplo de la Wyndor Glass Co. cada solución factible en un vértice en la figura 5.1 está en la intersección de dos (n=2) líneas de restricción; es decir, es una solución simultánea de un sistema de dos ecuaciones frontera.
Esta situación se resume en la tabla 5.1, en las que las ecuaciones de definición se refieren a las ecuaciones de la frontera de las restricciones que definen o conducen hacia las soluciones factibles en un vértice indicadas. De manera similar, en cualquier problema de programación lineal, cada solución factible en un vértice se encuentra en la intersección de n fronteras de restricción; esto es, se trata de una solución simultánea de un sistema de n ecuaciones frontera.
domingo, 1 de diciembre de 2013
Fundamentos del método símplex - Terminología (II)
Por ejemplo,el problema de la Wyndor Glass Co. tiene cinco restricciones (tres funcionales y dos de no negatividad), de manera que tiene cinco ecuaciones de frontera que se muestra en la figura 5.1. Como n=2, los hiperplanos definidos por estas ecuaciones de frontera son sólo rectas. Por lo tanto, las fronteras de restricción para las cinco restricciones son las cinco líneas que se muestran en la figura 5.1
La frontera de la región factible consiste en aquellas soluciones factibles que satisfacen una o más de las ecuaciones de frontera de las restricciones.
Geométricamente, cualquier punto sobre la frontera de la región factible se encuentra sobre uno o más de los hiperplanos definidos por las ecuaciones de frontera de restricciones respectivas. En la figura 5.1 la frontera consiste en los cinco segmentos de recta oscuros.
En seguida se da una definición general de solución factible en un vértice en el espacio de n dimensiones.
Una solución factible en un vértice es aquélla que no está sobre ningún segmento de linea que conecta a otras dos soluciones factibles.
La frontera de la región factible consiste en aquellas soluciones factibles que satisfacen una o más de las ecuaciones de frontera de las restricciones.
Geométricamente, cualquier punto sobre la frontera de la región factible se encuentra sobre uno o más de los hiperplanos definidos por las ecuaciones de frontera de restricciones respectivas. En la figura 5.1 la frontera consiste en los cinco segmentos de recta oscuros.
En seguida se da una definición general de solución factible en un vértice en el espacio de n dimensiones.
Una solución factible en un vértice es aquélla que no está sobre ningún segmento de linea que conecta a otras dos soluciones factibles.
Suscribirse a:
Entradas (Atom)