Puede entenderse de manera intuitiva que las soluciones óptimas de cualquier problema de programación líneal deben estar sobre la frontera de la región factible, y de hecho, ésta es una propiedad general. Como la frontera es un concepto geométrico, las dos primeras definiciones se pueden identificar algebraicamente.
La ecuacion de la frontera para cualquier restricción se obtiene sustituyendo su signo ≤, = o ≥ por un signo =.
En consecuencia, la forma de una ecuación de la frontera de restricción es ai1x1 + ai2x2+ ..... + ainxn = bi para las restricciones funcionales y xj = 0 para las de no negatividad. Estas ecuaciones definen una figura geométrica "plana" (llamada hiperplano) en un espacio n-dimensional, análoga a la línea en el espacio de dos dimensiones y al plano en el de tres dimensiones. Este hiperplano forma una frontera de restricción para la restricción correspondiente ya que cualquier punto que se encuentre a un lado de esta frontera viola esa restricción, mientras que cualquier punto sobre ella, satisface la restricción. (Los puntos en el otro lado también la satisfacen si se trata de una desigualdad.)
sábado, 30 de noviembre de 2013
viernes, 29 de noviembre de 2013
Fundamentos del método símplex
En la sección 4.1 se introdujo el concepto de soluciones factibles en un vértice y el papel clave que desempeñan en el método símplex. Estos conceptos geométricos se relacionaron con el álgebra del método símplex en la sección 4.2. Sin embargo, todo esto se hizo en el contexto del problema de la compañia Wyndor Glass, que tiene sólo dos variables y por ende tiene una interpretación geométrica directa. Cómo puede generalizarse estos conceptos a dimensiones mayores cuando se manejan problemas más grandes?. La respuesta se dará en esta sección.
Para comenzar, se introducirá parte de la terminología básica para cualquier problema de programación lineal con n variables (antes de introducir variables de holgura y artificiales para iniciar el método símplex). Mientras se lee esto, puede ser útil que el lector consulte la figura 5.1 para interpretar estas definiciones en dos dimensiones (n = 2)
jueves, 28 de noviembre de 2013
Teoría del método Símplex
En el anterior capítulo se presentó la mécanica básica del método símplex. Ahora se profundizara un poco en este algoritmo al examinar parte de la teoría en que se apoya. En esta primera sección se estudian las propiedades algebraicas y geométricas generales que constituyen el fundamento del método símplex. Después se describe la forma matricial del método símplex (llamada método símplex revisado) que simplifica mucho el procedimiento y facilita su introducción a una computadora. En seguida se presenta la idea fundamental sobre la propiedad del método símplex que permite deducir de qué manera los cambios que se hacen al modelo original repercuten en al tabla del símplex final. Esta idea proporcionará la clave para los importantes temas de más adelante
miércoles, 27 de noviembre de 2013
Conclusiones del Método Símplex
El método símplex es un algoritmo eficiente y confiable para resolver problemas de programación líneal. También proporciona la base para llevar a cabo, en forma muy eficiente, las distintas etapas del análisis posóptimo.
Aunque tiene una interpretación geométrica útil, el método símplex es un procedimiento algebraico. En cada iteración se mueve de la solución básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea mejor, la solución actual es óptima y el algoritmo se detiene.
Se presentó la forma algebraica completa del método símplex para establecer su lógica y se llevó el método a una forma tabular más conveniente. Para preparar el inicio del método símplex, algunas veces es necesario obtener una solución básica factible inicial para un problema revisado. En este caso se puede usar el método de la M, o bien, el método de las dos fases, para asegurar que el método símplex obtenga una solución óptima para el problema original.
Los paquetes de software para computadoras personales basados en el método símplex están ampliamente difundidos y al alcance, para manejar problemas de tamaño modesto. Los programas para computadoras grandes se usan por rutina para resolver y analizar problemas con muchos cientos y aun miles de funciones de restricción y variables.
El algoritmo de puntos interiores de Karmarkar proporciona una nueva herramienta poderosa para resolver problemas muy grandes.
Aunque tiene una interpretación geométrica útil, el método símplex es un procedimiento algebraico. En cada iteración se mueve de la solución básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea mejor, la solución actual es óptima y el algoritmo se detiene.
Se presentó la forma algebraica completa del método símplex para establecer su lógica y se llevó el método a una forma tabular más conveniente. Para preparar el inicio del método símplex, algunas veces es necesario obtener una solución básica factible inicial para un problema revisado. En este caso se puede usar el método de la M, o bien, el método de las dos fases, para asegurar que el método símplex obtenga una solución óptima para el problema original.
Los paquetes de software para computadoras personales basados en el método símplex están ampliamente difundidos y al alcance, para manejar problemas de tamaño modesto. Los programas para computadoras grandes se usan por rutina para resolver y analizar problemas con muchos cientos y aun miles de funciones de restricción y variables.
El algoritmo de puntos interiores de Karmarkar proporciona una nueva herramienta poderosa para resolver problemas muy grandes.
martes, 26 de noviembre de 2013
Programación lineal paramétrica
El análisis de sensibilidad requiere el cambio de un parámetro a la vez en el modelo original para examinar su efecto sobre la solución óptima. Por el contrario, la programación líneal paramétrica (o programación paramétrica en forma más corta) se refiere al estudio sistemático de los cambios en la solución óptima cuando cambia el valor de muchos parámetros al mismo tiempo dentro de un intervalo. Este estudio proporciona una extensión muy útil al análisis de sensibilidad, por ejemplo, se puede verificar el efecto de cambios simultaneos en parámetros "correlacionados", causados por factores exógenos tales como el estado de la economía. Sin embargo, una aplicación más importante es la investigación de los trueques entre los valores de los parámetros. Por ejemplo, si la cj representa la ganancia unitaria de la actividad resprectiva es posible aumentar el valor de alguna xj a costa de disminuir el de otra mediante un intercambio apropiado de personal y equipo entre las actividades. De manera parecida, si las bi representan las cantidades disponibles de los respectivos recursos, puede ser posible aumentar alguna bi si se está de acuerdo en aceptar disminuciones en algunas otras.
En algunos casos, el propósito del estudio es determinar el trueque más apropiado entre dos factorse básicos como costos y beneficios. La forma usual de hacerlo es expresar uno de estos factores en la función objetivo (como minimizar el costo total) e incorporar el otro a las restricciones (por ejemplo, beneficio ≥ nivel mínimo aceptable) como se hizo para el problema de contaminación de la Nori&Leets Co. en la sección 3.4. La programación lineal paramétrica permite entonces la investigación sistemática de lo que ocurre cuando se cambia una decisión inicial tentativa para mejorar un factor a costa de otro. Este enfoque se ejemplifica en la sección 8.5 con el estudio de un caso en el que los dos factores básicos son la distancia recorrida por los estudiantes y el grado de balance racial que se logra en sus escuelas.
La técnica algorítmica para programación líneal paramétrica es una extensión natural del análisis de sensibilidad, por lo que también está basada en el método símplex.
En algunos casos, el propósito del estudio es determinar el trueque más apropiado entre dos factorse básicos como costos y beneficios. La forma usual de hacerlo es expresar uno de estos factores en la función objetivo (como minimizar el costo total) e incorporar el otro a las restricciones (por ejemplo, beneficio ≥ nivel mínimo aceptable) como se hizo para el problema de contaminación de la Nori&Leets Co. en la sección 3.4. La programación lineal paramétrica permite entonces la investigación sistemática de lo que ocurre cuando se cambia una decisión inicial tentativa para mejorar un factor a costa de otro. Este enfoque se ejemplifica en la sección 8.5 con el estudio de un caso en el que los dos factores básicos son la distancia recorrida por los estudiantes y el grado de balance racial que se logra en sus escuelas.
La técnica algorítmica para programación líneal paramétrica es una extensión natural del análisis de sensibilidad, por lo que también está basada en el método símplex.
lunes, 25 de noviembre de 2013
Como se identifican los parámetros sensibles? (II)
La manera más fácil de analizar la sensibilidad de cada uno de los parámetros aij es verificar si su restricción correspondiente es de atadura sobre la solución óptima. Como x1 ≤ 4 no es una restricción de atadura, cualquier cambio suficientemente pequeño en sus coeficientes (a11 = 1, a12 = 0) no cambiará la solución óptima, así que éstos no son parámetros sensibles. Poro otro lado, tanto 2x2 ≤ 12 como 3x1 + 2x2 ≤ 18, son restricciones de atadura, por lo que al cambiar cualquiera de sus coeficientes (a21 = 0, a22 = 2, a31 = 3, a32 = 2) tendrá que cambiar la solución óptima, y así, éstos son parámetros sensibles.
Es común que se preste más atención al análisis de sensibilidad sobre los parámetros bi y cj que sobre los aij. En los problemas reales con cientos o miles de restricciones y variables, el efecto al cambiar una aij por lo general es despreciable, mientras que el cambio en una bi o en una cj puede tener un impacto real. Aún más, en muchos casos, los valores de las aij se quedan determinados por la tecnología que se está usando (a veces se les da el nombre de coeficientes tecnológicos) por lo que puede que haya muy poca ( o ninguna) incertidumbre respecto de sus valores finales. Esto resulta ventajoso ya que existen muchos más parámetros aij que bi y cj en problemas grandes.
En problemas con más de dos variables, no se puede analizar la sensibilidad de los parámetros en una gráfica como se hizo con el problema de la Windor Glass Co. Sin embargo, se puede extraer el mismo tipo de información del método símplex. Para obtenerla es preciso usar la idea fundamental que se describe en la sección 5.3 para deducir los cambios que se generan en la tabla símplex final como resultado de cambiar el valor de un parámetro en el modelo original.
domingo, 24 de noviembre de 2013
Como se identifican los parámetros sensibles?
En el caso de las bi, acaba de verse que esta información está dada por los precios sombra que proporciona el método símplex. En particular si yi* > 0, entonces la solución óptima cambia si bi lo hace, por que bi es un parámetro sensible. Sin embargo; yi* = 0 indica que la solución óptima no es sensible al menos a cambios pequeños en bi. En consecuencia, si el valor que se usa para bi es una estimación de la cantidad de recursos que se tendrán disponibles (y no una decisión de la gerencia), las bi que se deben que se deben estimar con más cuidado son aquellas con precio sombra positivos, en especial las que tienen precios sombra grandes.
Cuando el problema es de dos variables, la sensibilidad de los distintos parámetros se puede analizar con una gráfica. Por ejemplo, en la figura 4.3 ( o en la figura 3.3) se puede observar que c1 = 3 se puede cambiar a cualquier otro valor dentro del intervalo de 0 a 7(1/2) sin que la solución óptima (2, 6) cambie. (La razón es que cualquier valor de c1 dentro de este intervalo mantiene la pendiente de Z = c1x1 + 5x2 entre las pendientes de las líneas 2x2 = 12 y 3x1 + 2x2 = 18). De igual manera, si c2 =5 es el único parámetro que se cambia, puede tomar cualquier valor mayor que 2 sin que afecte la solución óptima. Asi, ni c1 ni c2 son parámetros sensibles.
Cuando el problema es de dos variables, la sensibilidad de los distintos parámetros se puede analizar con una gráfica. Por ejemplo, en la figura 4.3 ( o en la figura 3.3) se puede observar que c1 = 3 se puede cambiar a cualquier otro valor dentro del intervalo de 0 a 7(1/2) sin que la solución óptima (2, 6) cambie. (La razón es que cualquier valor de c1 dentro de este intervalo mantiene la pendiente de Z = c1x1 + 5x2 entre las pendientes de las líneas 2x2 = 12 y 3x1 + 2x2 = 18). De igual manera, si c2 =5 es el único parámetro que se cambia, puede tomar cualquier valor mayor que 2 sin que afecte la solución óptima. Asi, ni c1 ni c2 son parámetros sensibles.
sábado, 23 de noviembre de 2013
Análisis de sensibilidad
Cuando se examinó la suposición de certidumbre para la programación lineal al final de la sección 3.3, se hizo notar que los valores usados para los parámetros del modelo (las aij, bi y cj que se identifican en la tabla 3.3) casi siempre son estimaciones de las cantidades cuyos verdaderos valores no se conocerán hasta que el estudio de programación lineal se lleve a la práctica en el futuro. El propósito general del análisis de sensibilidad es identificar los parámetros sensibles (esto es, aquellos que no pueden cambiar mucho sin cambiar la solución óptima) para tratar de dar mejores estimaciones que no pueden cambiar mucho sin cambiar la solución óptima) para tratar de dar mejores estimaciones para estos parámetros, y después seleccionar una solución que sea buena para toda la escala de valores posibles de esos parámetros sensibles.
viernes, 22 de noviembre de 2013
Precios Sombra (III)
Ahora obsérvese en la misma figura por qué y1* = 0. La restricción sobre el recurso 1, x1 ≤ 4, no tiene ingerencia en la solución óptima (2,6), ya que existe un superávit de este recurso. Por tanto, si b1 adquiere un valor mayor que 4, no se obtendrá una nueva solución óptima con un valor mayor para Z.
Por el contrario, las restricciones sobre los recursos 2 y 3, 2x2 ≤ 12 y 3x1 + 2x2 `≤ 18 son restricciones de atadura (en las que se cumple la igualdad para la solución óptima). Debido a que la disponibilidad limitada de estos recursos (b2 = 12, b3 = 18) ata a Z para que no pueda incrementarse, tienen precios sombra positivos. Los economistas se refieren a estos recursos como bienes escasos, mientras que los recursos disponibles con superávit (como el recurso 1) son bienes libres (con precios sombra de cero).
El tipo de información que proporcionan los precios sombra es valiosa para la gerencia cuando examina la posibilidad de reasignar recursos dentro de la organización. También resulta muy útil cuando un aumento en bi se puede lograr con sólo salir a comprar un poco más del recurso. Por ejemplo, supóngase que Z representa ganancias y que las ganancias unitarias de las actividades (las cj) incluyen costos (a precios normales) de todos los recursos que se consumen; entonces, un precio sombra positivo y*i, para el recurso i significa que la ganancia total Z se puede aumentar en la cantidad yi* al comprar una unidad más de este recurso a su precio normal. Así mismo, si se tiene que pagar un precio mayor al nominal por la cantidad adicional del recurso, yi* representará el mayor precio (cantidad adicional sobre el precio normal) que vale la pena pagar.
En el problema de la Wyndor Glass Co., la gerencia ha descartado por el momento cualquier posibilidad de expansión en la capacidad de producción de las tres plantas. No obstante, las capacidades asginadas a los dos productos nuevos se pueden aumentar si se disminuye un poco más la producción de la línea actual. El departamento de investigación de operaciones estudia esta posibilidad como parte del análisis de sensibilidad.
La teoria de dualidad proporciona el fundamento teórico de los precios sombra y se describe posteriormente.
Por el contrario, las restricciones sobre los recursos 2 y 3, 2x2 ≤ 12 y 3x1 + 2x2 `≤ 18 son restricciones de atadura (en las que se cumple la igualdad para la solución óptima). Debido a que la disponibilidad limitada de estos recursos (b2 = 12, b3 = 18) ata a Z para que no pueda incrementarse, tienen precios sombra positivos. Los economistas se refieren a estos recursos como bienes escasos, mientras que los recursos disponibles con superávit (como el recurso 1) son bienes libres (con precios sombra de cero).
El tipo de información que proporcionan los precios sombra es valiosa para la gerencia cuando examina la posibilidad de reasignar recursos dentro de la organización. También resulta muy útil cuando un aumento en bi se puede lograr con sólo salir a comprar un poco más del recurso. Por ejemplo, supóngase que Z representa ganancias y que las ganancias unitarias de las actividades (las cj) incluyen costos (a precios normales) de todos los recursos que se consumen; entonces, un precio sombra positivo y*i, para el recurso i significa que la ganancia total Z se puede aumentar en la cantidad yi* al comprar una unidad más de este recurso a su precio normal. Así mismo, si se tiene que pagar un precio mayor al nominal por la cantidad adicional del recurso, yi* representará el mayor precio (cantidad adicional sobre el precio normal) que vale la pena pagar.
En el problema de la Wyndor Glass Co., la gerencia ha descartado por el momento cualquier posibilidad de expansión en la capacidad de producción de las tres plantas. No obstante, las capacidades asginadas a los dos productos nuevos se pueden aumentar si se disminuye un poco más la producción de la línea actual. El departamento de investigación de operaciones estudia esta posibilidad como parte del análisis de sensibilidad.
La teoria de dualidad proporciona el fundamento teórico de los precios sombra y se describe posteriormente.
jueves, 21 de noviembre de 2013
Precios Sombra (II)
Se puede verificar que estos números son correctos al observar en las figuras 3.2 y 3.3 que, sí se incrementa por separado cada bi en una unidad, el valor óptimo de Z aumentará y*i. Por ejemplo, en la figura 4.3 se muestra un aumento así para el recurso 2 al reaplicar el procedimiento gráfico que se presentó en la sección 3.2. La solucion óptima (2,6) con Z = 36, cambia a (5/3, 13/2) con Z = 37(1/2) cuando se incrementa en uno el valor de b2 (de 12 a 13), de manera que:
y2* = ΔZ = 37(1/2) - 36 = 3/2
La figura 4.3 demuestra que y2* = 3/2 es la tasa a la que aumentaría Z si se incrementara un poco b2, pero también demuestra el fenómeno general de que esta interpretación es válida nada más para aumentar pequeños. Si b2 se aumenta a más de 18 unidades, la solución óptima se queda en el punto (0,9) sin que la Z siga aumentando.
miércoles, 20 de noviembre de 2013
Precios Sombra (I)
Recuérdese que los problemas más comunes de programación líneal (véanse las tablas 3.2 y 3.3) pueden interpretarse como la asignación de recursos a las actividades, donde bi representa la cantidad de los respectivos recursos disponibles para las actividades bajo estudio. En muchos casos, pueden haber dudas respecto a las cantidades que estarán disponibles. Si así es, la cantidad bi que se usa en el modelo inicial (validado), en realidad puede representar una decisión inicial tentativa del gerente sobre la cantidad de recursos de la organización que se asignarán a las actividades consideradas en el modelo y no a otras actividades que el gerente considere importantes. Desde esta amplia perspectiva, algunos valores de bi se pueden incrementar en un modelo revisado sólo cuando se presenten razones poderosas en cuanto a que esta revisión será bénefica.
En consecuencia, la información sobre la contribución económica de los recursos a la medida de desempeño (Z) para el estudio en curso casi siempre será en extremo útil. El método símplex proporciona esta información en forma de "precios sombra" para los recursos respectivos.
Los precios sombra para el recurso i (denotados por yi*) miden el valor marginal de este recurso, es decir, la tasa a la que Z puede aumentar si se incrementa (un poco) la cantidad que se proporciona de este recurso bi. El método símplex identifica este precio sombra como yi* = coeficiente de la i-esima variable de holgura en el renglón (0) de la tabla símplex final.
En el problema de la Wyndor Glass Co., la tabla símplex final en la tabla 4.8 da
y1* = 0 = precio sombra del recurso 1,
y2* = 3/2 = precio sombra del recurso 2,
y3* = 1 = precio sombra del recurso 3.
en donde estos recursos son las capacidades de producción disponibles en las plantas 1, 2 y 3, respectivamente (b1 = 4, b2 =12 y b3 = 18).
martes, 19 de noviembre de 2013
Reoptimización (II)
La gran ventaja de la técnica de reoptimización sobre el hecho de resolver el problema desde el principio, es que quizá la solución óptima para el problema revisado esté mucho más cerca de la solución óptima anterior que de una solución básica factible inicial construida como siempre. Así , si se supone que las revisiones del modelo fueran moderadas, se requerirán sólo unas cuantas iteraciones para reoptimizar en lugar de cientos o tal vez miles que pueden llevarse a cabo cuando se comienza desde el principio en problemas grandes. De hecho, las soluciones del modelo anterior y del revisado con frecuencia son las mismas, en cuyo caso, la técnica de reoptimización requiere sólo una aplicación de la prueba de optimalidad y ninguna iteración.
lunes, 18 de noviembre de 2013
Reoptimización (I)
Con frecuencia, después de encontrar una solución óptima para una versión de un modelo de programación líneal, el problema debe resolverse de nuevo para un modelo ligeramente diferente. Casi siempre se tiene que resolver varias veces durante la etapa de verificación de modelo, y por lo general se hace lo mismo un gran número de veces durante las etapas de análisis posóptimo.
Una manera de hacerlo es sencillamente aplicar el método símplex desde el principio a cada nueva versión del modelo, aunque cada corrida pueda requerir, en problemas grandes cientos o miles de operaciones. Sin embargo, una forma mucho más eficiente es la de reoptimizar. La reoptimización deduce los cambios que deben introducirse a la tabla símplex final como consecuencia de los cambios en el modelo y después usa la solución óptima del modelo anterior como solución básica inicial para resolver el nuevo modelo. Si esta solución es factible para el nuevo modelo, se puede aplicar el método símplex en la forma usual, a partir de esta solución básica factible inicial. Si la solución no es factible, tal vez se pueda aplicar un algoritmo similar llamado método símplex dual para encontrar la nueva solución óptima, tras comenzar con esta solución básica inicial.
Una manera de hacerlo es sencillamente aplicar el método símplex desde el principio a cada nueva versión del modelo, aunque cada corrida pueda requerir, en problemas grandes cientos o miles de operaciones. Sin embargo, una forma mucho más eficiente es la de reoptimizar. La reoptimización deduce los cambios que deben introducirse a la tabla símplex final como consecuencia de los cambios en el modelo y después usa la solución óptima del modelo anterior como solución básica inicial para resolver el nuevo modelo. Si esta solución es factible para el nuevo modelo, se puede aplicar el método símplex en la forma usual, a partir de esta solución básica factible inicial. Si la solución no es factible, tal vez se pueda aplicar un algoritmo similar llamado método símplex dual para encontrar la nueva solución óptima, tras comenzar con esta solución básica inicial.
Análisis posóptimo
En los anteriores articulos se hizo hincapié en que el análisis posóptimo, el análisis que se hace después de obtener una solución óptima para la versión inicial del modelo, constituye una parte muy importante de casi todos los estudios de investigación de operaciones. Este hecho es particularmente cierto para las aplicaciones comunes de programación líneal. Esta sección está dedicada a presentar el papel que juega el método símplex al realizar este análisis.
La tabla del siguiente post resumen los pasos que se deben seguir en un análisis posóptimo en estudios de programación líneal. La última columna de esta tabla identifica algunas técnicas que emplean el método símplex. Aquí se dará una introducción breve a estas técnicas y los detalles se dejan para capítulos posteriores.
La tabla del siguiente post resumen los pasos que se deben seguir en un análisis posóptimo en estudios de programación líneal. La última columna de esta tabla identifica algunas técnicas que emplean el método símplex. Aquí se dará una introducción breve a estas técnicas y los detalles se dejan para capítulos posteriores.
domingo, 17 de noviembre de 2013
Variables sin cotas sobre los valores negativos permitidos (III)
Desde un punto de vista computacional, este enfoque tiene la desventaja de que el nuevo modelo equivalente tiene más variables que el modelo original. De hecho, si ninguna variable tuviera restricción de cota inferior, el nuevo modelo tendria el doble de variables. Por fortuna esto se puede modificar un poco para que el número de variables aumente sólo en uno, sin importar cuántas variables orginales tengan que sustituirse. Esta modificación se hace al reemplazar cada variable de este tipo, xj por
xj = x'j - x'', donde x'j ≥ 0, x'' ≥ 0
donde x'' es la misma variable para toda j relevante. En este caso, la interpretación de x'' es que -x'' es el valor actual de la variable original negativa más grande (en términos de valor absoluto), entonces, x'j es la cantidad por la que xj excede este valor. Con esto, el método símplex puede hacer que algunas x'j adquieran valores mayores a cero aun cuando x'' >0.
xj = x'j - x'', donde x'j ≥ 0, x'' ≥ 0
donde x'' es la misma variable para toda j relevante. En este caso, la interpretación de x'' es que -x'' es el valor actual de la variable original negativa más grande (en términos de valor absoluto), entonces, x'j es la cantidad por la que xj excede este valor. Con esto, el método símplex puede hacer que algunas x'j adquieran valores mayores a cero aun cuando x'' >0.
Variables sin cotas sobre los valores negativos permitidos (II)
PAra ilustrar esto se usará el mismo ejemplo que el caso de la variable acotada, pero ahora supóngase que la restricción x1 ≥ -10 no está incluida en el modelo original, ya que es claro que no influye en la solución óptima. (En algunos problemas, ciertas variables no necesitan tener cotas inferiores explícitas cuando las restricciones funcionales impiden valores menores.) Entonces, antes de aplicar el métod símplex, x1 se reemplaza por la diferencia,
sábado, 16 de noviembre de 2013
Variables sin cotas sobre los valores negativos permitidos (I)
En caso de que xj no tenga una cota inferior en el modelo formulado, se requiere un cambio distinto: xj se sustituye en todo el modelo por la diferencia de dos nuevas variables no negativas
Como xj(+) y xj(-) pueden tomar cualquier valor no negativo, esta diferencia (xj+ - xj-) puede ser cualquier valor (positivo o negativo), por lo que es una sustitución legítima para xj, después de estas sustituciones, el método símplex puede proceder con variables que son no negativas.
Las nuevas variables xj+ y xj- tienen una interpretación sencilla. Por la definición geométrica de solución factible en un vértice, cada solución básica factible para la nueva forma del modelo necesariamente tiene la propiedad de que o bien xj* = 0 o xj- (o ambas); por tanto, en la solución óptima obtenida por el método símplex, de manera que xj+ representa la parte positiva de xj y xj- su parte negativa (como lo sugieren los superíndices).
Como xj(+) y xj(-) pueden tomar cualquier valor no negativo, esta diferencia (xj+ - xj-) puede ser cualquier valor (positivo o negativo), por lo que es una sustitución legítima para xj, después de estas sustituciones, el método símplex puede proceder con variables que son no negativas.
Las nuevas variables xj+ y xj- tienen una interpretación sencilla. Por la definición geométrica de solución factible en un vértice, cada solución básica factible para la nueva forma del modelo necesariamente tiene la propiedad de que o bien xj* = 0 o xj- (o ambas); por tanto, en la solución óptima obtenida por el método símplex, de manera que xj+ representa la parte positiva de xj y xj- su parte negativa (como lo sugieren los superíndices).
Variables con una cota sobre los valores permitidos (II)
Para ejemplificar, supóngase que la tasa de producción actual para el producto 1 en el problema de la Wyndor Glass Co. es 10. Con la definición que se acaba de dar para x1, el modelo completo en este punto es el mismo que el dado en la sección 3.1, salvo que la restricción de no negatividad x1 ≥ 0 se reemplaza por
x1 ≥ -10
Para obtener el modelo equivalente que se necesita para el método símplex, la variable de decisión se redefinirá como la tasa de producción total del producto 1
x1 = x1 + 10
lo que lleva a los siguientes cambios en la función objetivo y las restricciones:
x1 ≥ -10
Para obtener el modelo equivalente que se necesita para el método símplex, la variable de decisión se redefinirá como la tasa de producción total del producto 1
x1 = x1 + 10
lo que lleva a los siguientes cambios en la función objetivo y las restricciones:
viernes, 15 de noviembre de 2013
Variables con una cota sobre los valores permitidos (I)
Considérese cualquier variable de decisión xj que puede tener varios negativos, pero nada más aquellos que satisfacen una restricción de forma
xj ≥ Lj
donde Lj es una constante negativa. Esta restricción se puede convertir en una de no negatividad haciendo el cambio de variables.
xí = xj - Lj de manera que xj ≥ 0.
Entonces (xj + Lj) sustituye a xj en el modelo y al nueva variable de decisión xj no puede ser negativa.
xj ≥ Lj
donde Lj es una constante negativa. Esta restricción se puede convertir en una de no negatividad haciendo el cambio de variables.
xí = xj - Lj de manera que xj ≥ 0.
Entonces (xj + Lj) sustituye a xj en el modelo y al nueva variable de decisión xj no puede ser negativa.
Variables que pueden ser negativas
En la mayor parte de los problemas prácticos, los valores negativos para las variables de decisión no tienen significado físico, por lo que es necesario incluir las restricciones de no negatividad en la formulación del módelo de programación líneal. Sin embargo, esto no ocurre siempre.
Como ejemplo, supóngase que en el problema de la Wyndor Glass Co. El producto 1 ya está en producción y que la primera variable de decisión x1 representa el incremento en la tasa de producción. Entonces, un valor negativo de x1 indicaría que debe disminuirse la producción más alta del nuevo producto 2, con lo que se permitirían valores negativos de x1 en el modelo.
Como el procedimiento para determinar la variable básica que sale requiere que todas las variables tengan restricción de no negatividad, cualquier problema que contanga variables que puedan adquirir valores negativos debe convertirse en un problema equivalente que emplee sólo variables no negativas. Por fortuna, se puede hacer esta conversión. La modificación que requiere cada variable depende de si tiene o no una cota inferior (negativa) sobre los valores permitidos. Se presentará cada caso.
jueves, 14 de noviembre de 2013
Sin soluciones factibles (II)
Por fortuna, la técnica de las variables artificiales proporciona algunas señales que indican que esto ha ocurrido:
Si el problema original no tiene soluciones factibles, entonces cualquier solución óptima obtenida con el método de la M o en la fase 1 del método de las dos fases lleva a una solución final que contiene al menos una variable artificial mayor que cero. De otra manera,todas son iguales a cero.
con fines didácticos, cámbiese la primera restricción del ejemplo de terapia de radiación como sigue:
0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 ≤ 1.8
con lo que el problema ya no tiene soluciones factibles. Si se aplica el método de la M como antes (vease la tabla 4.12) se obtiene la tabla símplex que se muestra en la tabla 4.15 (La fase 1 del método de las dos faces conduce a la misma tabla símplex, excepto que cada expresión con M se reemplaza solo con el factor multiplicativo) En un caso normal el método de la M indicaría que la solución óptima es (3, 9, 0, 0, 0, 0.6). Sin embargo, como una variable artificial x6 = 0.6 > 0, el mensaje real aquí es que el problema no tiene soluciones factibles.
Si el problema original no tiene soluciones factibles, entonces cualquier solución óptima obtenida con el método de la M o en la fase 1 del método de las dos fases lleva a una solución final que contiene al menos una variable artificial mayor que cero. De otra manera,todas son iguales a cero.
con fines didácticos, cámbiese la primera restricción del ejemplo de terapia de radiación como sigue:
0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 ≤ 1.8
con lo que el problema ya no tiene soluciones factibles. Si se aplica el método de la M como antes (vease la tabla 4.12) se obtiene la tabla símplex que se muestra en la tabla 4.15 (La fase 1 del método de las dos faces conduce a la misma tabla símplex, excepto que cada expresión con M se reemplaza solo con el factor multiplicativo) En un caso normal el método de la M indicaría que la solución óptima es (3, 9, 0, 0, 0, 0.6). Sin embargo, como una variable artificial x6 = 0.6 > 0, el mensaje real aquí es que el problema no tiene soluciones factibles.
Sin soluciones factibles (I)
Hasta aquí, esta sección se ha ocupado más que nada del problema elemental de identificar la solución básica factible inicial cuando no se dispone de una obvia. Se ha visto que la técnica de la variable artificial construye un problema artificial y obtiene una solución básica factible inicial para este problema revisado. El método de la M o el de las dos fases permiten al método símplex comenzar su recorrido hacia las soluciones básicas factibles y por último hacia la solución óptima del problema original.
No obstante, se debe estar consciente d un obstáculo que se puede presentar. Puede no existir una elección obvia para la solución básica factible inicial por la poderosa razón de que no exista soluciones factibles!. Al construir una solución factible artificial, no hay nada que impida al método símplex proceder como siempre e incluso informar que encontró una supuesta solución óptima.
No obstante, se debe estar consciente d un obstáculo que se puede presentar. Puede no existir una elección obvia para la solución básica factible inicial por la poderosa razón de que no exista soluciones factibles!. Al construir una solución factible artificial, no hay nada que impida al método símplex proceder como siempre e incluso informar que encontró una supuesta solución óptima.
miércoles, 13 de noviembre de 2013
Resumen del método de las dos fases (VI)
DAdo que los términos Mx4 + Mx6, dominan a los términos 0.4x1 y 0.5x2 en la función objetivo para el método de la M, esta función objetivo es esencialmente equivalente a la de la fase 1 mientras x4 y/o x6 sean mayores que cero. Entonces, cuando tanto x4 = 0 como x6 = 0, la función objetivo del método de la M se vuelve completamente equivalente a la función objetivo de la fase 2.
Debido a estas equivalencias virtuales en la función objetivo, el método de la M y el de las dos fases tienen casi siempre la misma secuencia de soluciones básicas factibles. La única excepción posible ocurre cuando existe un empate para la variable básica entrante en la fase 1 del método de las dos fases, como sucedió en la tercera tabla símplex de la tabla 4.13 son casi idénticas con la única diferencia de que los factores multiplicativos de M en la tabla 4.12 se convierten en cantidades solas en los puntos correspondientes de la tabla 4.13. En consecuencia, no se contaba con los factores aditivos que rompieron el empate para la variable básica entrante en la tercera tabla símplex de la tabla 4.12 para romper este mismo empate de la tabla 4.13. El resultado en este ejemplo fue una iteración adicional en el método de las dos fases, aunque en general, la ventaja de contar con los factores aditivos es mínima.
El método de las dos fases sigue los pasos del método de la M usando sólo los factores multiplicativos en la fase 1 y eliminando las variables artificiales en al fase 2. (El método de la M puede combinar los factores multiplicativos y aditivos asignando un valor muy grande a M,pero esto podría crear problemas con inestabilidad númerica) Por estas razones es común que cuando se trate de paquetes de computadora se use el método de las dos fases.
Resumen del método de las dos fases (V)
Si el empate para la variable básica entrante que surgió en la penúltima tabla de la tabla 4.13 se hubiera roto de otra manera, entonces la fase 1 habría ido directamente de (8,3) a (7.5, 4.5). Después de utilizar (7.5, 4.5) para establecer la tabla símplex inicial para la fase 2, la prueba de optimalidad habría revelado que esta solución es óptima y no se habría realizado ninguna interacción.
Resulta interesante comparar los métodos de la M y de las dos fases. Se comenzará por sus funciones objetivo
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Método de dos fases:
Fase 1: Minimizar Z = x4 + x6
Fase 2: Minimizar Z = 0.4x1 + 0.5x2
Resulta interesante comparar los métodos de la M y de las dos fases. Se comenzará por sus funciones objetivo
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Método de dos fases:
Fase 1: Minimizar Z = x4 + x6
Fase 2: Minimizar Z = 0.4x1 + 0.5x2
martes, 12 de noviembre de 2013
Resumen del método de las dos fases (IV)
Al principio de la tabla 4.14 se muestra la tabla símplex inicial que resulta para la fase 2. Al aplicar el método símplex se llega en una iteración a la solución óptima que se muestra en la segunda tabla símplex, (x1,x2,x3,x5) = (7.5, 4.5, 0 , 0.3).
Ahora obsérvese lo que el método de las dos fases ha hecho en la gráfica de la figura 4.2. Usando nada más (x1,x2), la secuencia de soluciones en un vértice que se obtuvieron en las tablas 4.13 y 4.14 es
Fase 1: (0,0) → (9,0) → (8,3) → (6,6)
Fase 2: (6,6) → (7.5, 4.5)
Notese que todas estas soluciones en la fase 1 son no factibles (excepto para el problema revisado) hasta la última. La fase 2 maneja entonces sólo soluciones factibles en un vértice.
Ahora obsérvese lo que el método de las dos fases ha hecho en la gráfica de la figura 4.2. Usando nada más (x1,x2), la secuencia de soluciones en un vértice que se obtuvieron en las tablas 4.13 y 4.14 es
Fase 1: (0,0) → (9,0) → (8,3) → (6,6)
Fase 2: (6,6) → (7.5, 4.5)
Notese que todas estas soluciones en la fase 1 son no factibles (excepto para el problema revisado) hasta la última. La fase 2 maneja entonces sólo soluciones factibles en un vértice.
Resumen del método de las dos fases (III)
Para la fase 2, se eliminan x4 y x6. Para comenzar con el método símplex a partir de la solución básica factible (x1,x2,x3,x5) = (6,6,0.3,0), los renglones 1-3 de la última tabla símplex en la tabla 4.13 están listos y en la forma apropiada de eliminación de Gauss. Sin embargo, ahora es necesario insertar en el renglón 0 la función objetivo del problema original en esta misma forma apropiada. La serie de pasos para obtener este nuevo renglón 0 (incluyendo el uso de los renglones 1 a 3 para eliminar x1 y x2 del renglón 0) se muestran a continuación.
lunes, 11 de noviembre de 2013
Resumen del método de las dos fases (II)
La tabla 4.13 muestra el resultado de aplicar la fase 1 al ejemplo de terapia de radiación [El renglón 0 en la tabla símplex inicial se obtiene al convertir minimizar Z = x4 + x6 a maximizar (-Z) = -x4 -x6, y después usar la eliminación gaussiana para eliminar x4 y x6 de -Z + x4 + x6 =0] En la penúltma tabla símplex existe un empate para la variable básica entrante entre x3 y x5 que se rompe arbitrariamente en favor de x3. La solución obtenida al final de al fase 1 es, entonces, (x1, x2, x3, x4, x5, x6) = (6, 6, 0.3, 0, 0, o) o despues de eliminar x4 y x6 (x1, x2,x3,x5) = (6,6,0.3,0)
Según se afirmó en el resumen, esta solución de la fase 1 es sin duda una solución básica factible para el problema original puesto que es la solución (después de hacer x5 = 0) a las restricciones originales en la formula aumentada.
(1) 0.3x1 + 0.1x2 + x3 =2.7
(2) 0.5x1 + 0.5x2 =6
(3) 0.6x1 + 0.4x2 -x5 = 6
Según se afirmó en el resumen, esta solución de la fase 1 es sin duda una solución básica factible para el problema original puesto que es la solución (después de hacer x5 = 0) a las restricciones originales en la formula aumentada.
(1) 0.3x1 + 0.1x2 + x3 =2.7
(2) 0.5x1 + 0.5x2 =6
(3) 0.6x1 + 0.4x2 -x5 = 6
Resumen del método de las dos fases (I)
Paso incial:
revisión de la restricción del problema original introduciendo variables artificiales según se necesite para obtener una solución básica factible inicial obvia para el problema revisado.Fase 1: uso del método símplex para resolver el problema de programación lineal:
Minimizar = Z = suma de las variables artificiales, sujeta a las restricciones revisadas.
La solución óptima que se obtiene para este problema (con Z = 0) será una solución básica factible para el problema original.
Fase 2: eliminaciónde las variables artificiales ( de todas formas ahora todas valen cero) Comenzando con la solución básica factible que se obtuvo al final de la fase 1, usar el método símplex para resolver el problema original.
domingo, 10 de noviembre de 2013
Método de las dos fases
Para el ejemplo de terapia de radiación que se acaba de resolver en la tabla 4.12, el método de la M utiliza la siguiente función objetivo ( o su equivalente en forma de minimización) a través de todo el procedimiento.
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
En contraste, el método de las dos fases puede eliminar la M usando dos funciones objetivo distintas.
Método de dos fases:
Fase 1: Minimizar Z = x4+ x6 (hasta que x4 = 0, x6 = 0)
Fase 2: Minimizar Z = 0.4x1 + 05x2 (con x4 = 0, x6 = 0)
Antes de resolver el ejemplo de esta manera se hará un resumen de las caracteristicas generales.
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
En contraste, el método de las dos fases puede eliminar la M usando dos funciones objetivo distintas.
Método de dos fases:
Fase 1: Minimizar Z = x4+ x6 (hasta que x4 = 0, x6 = 0)
Fase 2: Minimizar Z = 0.4x1 + 05x2 (con x4 = 0, x6 = 0)
Antes de resolver el ejemplo de esta manera se hará un resumen de las caracteristicas generales.
Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (III)
En las primeras dos soluciones en un vértice, tanto x4 como x6 son mayores que cero, lo que indica que se violan tanto 0.5x1 + 0.5x2 = 6 como 0.6x1 + 0.4x2 ≥ 6. El método de la M tiene éxito en llevar x6 a nivel cero en (8,3) de manera que 0.6x1 + 0.4x2 ≥ 6 se satisface. Después, x4 también adquiere valor de cero en (7.5, 4.5), con lo que 0.5x1 + 0.5x2 =6 también se satisface y se obtiene la primera solución factible para el problema original. Por casualidad, esta primera solución factible es también óptima por lo que no es necesario realizar más iteraciones.
En otros problemas con variables artificiales, puede ser que haya que realizar iteraciones adicionales para llegar a una solución óptima después de obtener la primera solución factible para el problema original. Así, puede pensarse que el método de la M tiene dos fases. En la primera, todas las variables artificiales se hacen cero (debido a la penalización de M por unidad al ser mayores que cero) con el fin de obtener una solución básica factible inicial para el problema original. En la segunda fase todas las variables artificiales se mantienen en cero (por la misma razón) mientras que el método símplex genera una secuencia de soluciones básicas factibles que llevan a la solución óptima.
El método de las dos fases se describe a continuación es un procedimiento directo para realizar estas dos fases sin siquiera introducir M de una mera explicita.
sábado, 9 de noviembre de 2013
Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (II)
La tabla símplex inicial que resulta, lista para comenzar el método símplex se muestra en la tabla 4.12 Al aplicar el método símplex en la forma acostrumbrada se obtiene la secuencia de tablas símplex que se muestran en el resto de la tabla 4.12. En cuanto a la prueba de optimalidad y la elección de la variable básica entrante en cada iteración, las cantidades que incluyen M se trataron justo como se explicó para la tabla 4.11 En particular, siempre que M está presente, sólo se usa su factor multiplicativo a menos que haya un empate, en cuyo caso el empate se rompe usando los factores aditivos correspondientes. Un empate de este tipo ocurre en la última selección de la variable básica entrante en donde los coeficientes de x3 y x5 en el renglón 0 tienen el mismo factor multiplicativo, -(5/3) al comprar los factores aditivos, (11/6)<(7/3) se selecciona x5 como la variable básica entrante.
Ahora se puede observar lo que el método de la M ha hecho que la gráfica de la figura 4.2.
Al usar nada más las variables de decisión originales (x1, x2) la secuencia de soluciones en un vértice que se obtiene en la tabla 4.12 es:
(0,0) → (9,0) → (8,3) → (7.5, 4.5)
Ahora se puede observar lo que el método de la M ha hecho que la gráfica de la figura 4.2.
Al usar nada más las variables de decisión originales (x1, x2) la secuencia de soluciones en un vértice que se obtiene en la tabla 4.12 es:
(0,0) → (9,0) → (8,3) → (7.5, 4.5)
Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (I)
Puede aplicarse a esta ecuación (0) la prueba de optimalidad y el procedimiento para elegir una variabla básica entrante? No! Ocurre que el sistema de ecuaciones todavia no está en la forma apropiada de eliminación de Gauss (en la que cada variable básica se elimina de todas las ecuaciones excepto de su propia ecuación en la que debe tener coeficiente +1). Las ecuaciones (1) a (3) están bien, pero todavía es necesario eliminar las variables básicas x4 y x6 de la ecuación (0) con la eliminación gaussiana. Como tanto x4 como x6 tienen coeficiente M, se tiene que restar de la ecuación (0) M veces la ecuación (2) y M veces la ecuación (3). Por ejemplo, el coeficiente de x1 en la ecuación (0) se convierte en 0.4 - 0.5M - 0.6M = -1.1M + 0.4M, de manera que M se maneja como un número real (muy grande) cuyo valor es fijo pero no especificado. A continuación se resumen los cálculos de todos los coeficientes (y el lado derecho), en donde los vectores son los renglones relevantes de la tabla símplex correspondiente al sistema de ecuaciones anterior
viernes, 8 de noviembre de 2013
Solución del ejemplo de terapia de radiación
El ejemplo está casi listo para aplicarle el método símplex. Si se usa la forma de maximización que se acaba de obtener, el sistema de ecuaciones completo es:
(0) -Z + 0.4x1 + 0.5x2 + Mx4 +Mx6 = 0
(1) 0.3x1 + 0.1x2 + x3 = 2.7
(2) 0.5x1 + 0.5x2 + x4 = 6
(3) 0.6x1 + 0.4x2 -x5 +x6 = 6
Las variables básicas (x3,x4,x6) en la solución inicial básica factible (para este problema revisado) se muestran en negritas
(0) -Z + 0.4x1 + 0.5x2 + Mx4 +Mx6 = 0
(1) 0.3x1 + 0.1x2 + x3 = 2.7
(2) 0.5x1 + 0.5x2 + x4 = 6
(3) 0.6x1 + 0.4x2 -x5 +x6 = 6
Las variables básicas (x3,x4,x6) en la solución inicial básica factible (para este problema revisado) se muestran en negritas
Minimizacion (II)
Entonces, en el ejemplo de terapia de radiación se debe hacer el siguiente cambio en la formulación:
Minimizar Z = 0.4x1 + 0.5x2
→ Minimizar (-Z) = -0.4x1 - 0.5x2
Después de introducir las variables artificiales (x4,x6) y de aplicar el método de la M la conversión correspondiente es:
Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
→ Minimizar (-Z) = -0.4x1 - 0.5x2 - Mx4 - Mx6
Minimizar Z = 0.4x1 + 0.5x2
→ Minimizar (-Z) = -0.4x1 - 0.5x2
Después de introducir las variables artificiales (x4,x6) y de aplicar el método de la M la conversión correspondiente es:
Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
→ Minimizar (-Z) = -0.4x1 - 0.5x2 - Mx4 - Mx6
jueves, 7 de noviembre de 2013
Minimizacion (I)
Una manera directa de Minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón 0, tanto para la prueba de optimalidad como para la parte 1 del paso iterativo. Sin embargo, en lugar de cambiar las instrucciones del método símplex se presentará una manera sencilla de convertir cualquier problema de minimización en un problema equivalente de maximización:
es decir, las dos formulaciones llevan a la (s) misma (s) solución(es) óptima(6)
La razón por la que las dos formulaciones son equivalentes es que entre más pequeña es Z, más grande es (-Z), así que la solución que da el menor valor de Z dentro de la región factible, también debe dar el mayor valor para (-Z) en esta región.
es decir, las dos formulaciones llevan a la (s) misma (s) solución(es) óptima(6)
La razón por la que las dos formulaciones son equivalentes es que entre más pequeña es Z, más grande es (-Z), así que la solución que da el menor valor de Z dentro de la región factible, también debe dar el mayor valor para (-Z) en esta región.
Lado derecho negativo (II)
Como siempre, al introducir variables artificiales, la región factible se amplia. La restricción original permitía sólo soluciones que estuvieran arriba de o sobre la frontera de restricción. 0.6x1 + 0.4x2 = 6. Ahora permite también soluciones que estén por debajo de la frontera de restricción, ya que tanto x5 como x6 tienen sólo la restricción de no negatividad, por lo que su diferencia (x6-x5) puede ser cualquier número positivo. Ninguna solución queda fuera, asi, el efecto temporal de introducir x6 es eliminar la restricción en el problema revisado. (La restricción se mantiene en el sistema de ecuaciones por que volverá a ser relevante más tarde, una vez que el método de la M haga que x6 sea cero).
Se ha revisado dos veces el problema original, ampliando su región factible, primero con la introducción de la variable artificial x4 en la restricción de igualdad (0.5x1 + 0.5x2 + x4 = 6), y ahora al introducir x6. En consecuencia, la región factible para el problema revisado es el poliedro completo de la figura 4.2 cuyos vértices son (0.0), (9,0) (7.5,4.5) y (0,12).
Quizá el lector observó que se tomó un camino con rodeos al convertir la tercera restricción de su forma original, 0,6x1 + 0.4x2 ≥6, a su version final 0.x1 + 0.4x2 - x5 + x6 = 6. De hecho, se multiplicó toda la ecuación por (-1) dos veces! Ahora que se ha visto la motivación que llevó a la forma final se puede establecer un camino corto:
0.6x1 + 0.4x2 ≥ 6
→ 0.6x1 + 0.4x2 -x5 = 6 (x5 ≥ 0)
→ 0.6x1 + 0.4x2 -x5 + x6 = 6 (x5 ≥ 0, x6 ≥ 0)
En esta forma, x5 se llama variable de superávit, puesto que resta lo que le sobra al lado izquierdo para convertir la desigualdad en una ecuación equivalente.
Se ha revisado dos veces el problema original, ampliando su región factible, primero con la introducción de la variable artificial x4 en la restricción de igualdad (0.5x1 + 0.5x2 + x4 = 6), y ahora al introducir x6. En consecuencia, la región factible para el problema revisado es el poliedro completo de la figura 4.2 cuyos vértices son (0.0), (9,0) (7.5,4.5) y (0,12).
Quizá el lector observó que se tomó un camino con rodeos al convertir la tercera restricción de su forma original, 0,6x1 + 0.4x2 ≥6, a su version final 0.x1 + 0.4x2 - x5 + x6 = 6. De hecho, se multiplicó toda la ecuación por (-1) dos veces! Ahora que se ha visto la motivación que llevó a la forma final se puede establecer un camino corto:
0.6x1 + 0.4x2 ≥ 6
→ 0.6x1 + 0.4x2 -x5 = 6 (x5 ≥ 0)
→ 0.6x1 + 0.4x2 -x5 + x6 = 6 (x5 ≥ 0, x6 ≥ 0)
En esta forma, x5 se llama variable de superávit, puesto que resta lo que le sobra al lado izquierdo para convertir la desigualdad en una ecuación equivalente.
miércoles, 6 de noviembre de 2013
Lado derecho negativo
Se recordará que el método símplex se presentó bajo la suposición de que bi > 0 para toda i = 1,2,.....m. Esta suposición permitió elegir las variables de holgura como las variables básicas iniciales (iguales al lado derecho) y obtener una solución básica factible no degenerada.
Partiendo de esto, se hizo incapié en la sección 4.5 en que no es necesario evitar la degeneración (variables básicas igual a cero). Sin embargo, un lado derecho negativo como el de la tercera restricción.
- 0.6x1 - 0.4x2 + x5 = -6
daria un valor negativo para la variable de holgura (x5 = -6) en la solución inicial (donde x1 = 0, x2 = 0), lo que violaría la restricción de no negatividad para esta variable. Al multiplicar toda la ecuación (-1) el lado derecho se vuelve positivo:
-0.6x1 + 0.4x2 - x5 = 6,
pero también cambia el coeficiente de la variable de holgura -1, por lo que de todas formas la variable sería negativa. Sin embargo, en esta forma la restricción se puede considerar una restricción de igualdad con un lado derecho no negativo y se puede aplicar la técnica de la variable artificial justo como se describio. Sea x6 la variable artificial no negativa para esta restricción, su forma final es
0.6x1 + 0.4x2 - x5 +x6 = 6
en donde x6 se usa como la variable básica inicial (x6 = 6) para esta ecuación y x5 comienza como variable no básica. El método de la M se aplicará también en la misma forma que antes, como se verá más adelante.
Partiendo de esto, se hizo incapié en la sección 4.5 en que no es necesario evitar la degeneración (variables básicas igual a cero). Sin embargo, un lado derecho negativo como el de la tercera restricción.
- 0.6x1 - 0.4x2 + x5 = -6
daria un valor negativo para la variable de holgura (x5 = -6) en la solución inicial (donde x1 = 0, x2 = 0), lo que violaría la restricción de no negatividad para esta variable. Al multiplicar toda la ecuación (-1) el lado derecho se vuelve positivo:
-0.6x1 + 0.4x2 - x5 = 6,
pero también cambia el coeficiente de la variable de holgura -1, por lo que de todas formas la variable sería negativa. Sin embargo, en esta forma la restricción se puede considerar una restricción de igualdad con un lado derecho no negativo y se puede aplicar la técnica de la variable artificial justo como se describio. Sea x6 la variable artificial no negativa para esta restricción, su forma final es
0.6x1 + 0.4x2 - x5 +x6 = 6
en donde x6 se usa como la variable básica inicial (x6 = 6) para esta ecuación y x5 comienza como variable no básica. El método de la M se aplicará también en la misma forma que antes, como se verá más adelante.
Restricciones en forma de igualdad (VIII)
Muy pronto se mostrará la solución completa este problema con el método símplex incluida la secuencia de soluciones en los vértices que se obtienen, pero primero ha de convertirse el modelo en la forma apropiada para poder aplicarlo. Dos ajustes consisten en introducir una variable de holgura (x3 ≥0) en la primera restriccion.
0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 + x3 = 2.7,
y una variable artificial (x4 ≥ 0) enla restriccion de igualdad.
0.5x1 + 0.5x2 = 6 → 0.5x1 + 0.5x2 + x4 = 6
El efecto temporal al introducir x4 en esta restricción (antes de que el método de la M la obligue a tener valor de cero) es permitir las soluciones como 0.5x1 + 0.5x2 ≤6. Si también se toman en cuenta las otras restricciones, la región factible para el problema revisando se expande hasta incluir todo el triángulo cuyos vértices son (6,6), (7.5, 4.5) y (8,3).
Los ajustes que quedan para las otras formas no estándar en el modelo se describen a continuación.
0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 + x3 = 2.7,
y una variable artificial (x4 ≥ 0) enla restriccion de igualdad.
0.5x1 + 0.5x2 = 6 → 0.5x1 + 0.5x2 + x4 = 6
El efecto temporal al introducir x4 en esta restricción (antes de que el método de la M la obligue a tener valor de cero) es permitir las soluciones como 0.5x1 + 0.5x2 ≤6. Si también se toman en cuenta las otras restricciones, la región factible para el problema revisando se expande hasta incluir todo el triángulo cuyos vértices son (6,6), (7.5, 4.5) y (8,3).
Los ajustes que quedan para las otras formas no estándar en el modelo se describen a continuación.
martes, 5 de noviembre de 2013
Restricciones en forma de igualdad (VII)
En la figura 4.2 se repite también la solución gráfica de este ejemplo (presentada en la figura 3.7) en una forma un poco distinta. Las tres líneas en la figura, junto con los dos ejes constituyen las cinco restricciones del problema. los puntos dibujados en las intersecciones de cada par de líneas son las soluciones en los vértices. Las únicas dos soluciones factibles en un vértice son (6,6) y (7.5, 4.5) y la región factible es el segmento de línea que conecta a estos dos puntos. La solución óptima es (x1,x2) = 97.5,4.5) con Z = 5.25.
Restricciones en forma de igualdad (VI)
En la tabla 4.11 se muestra la tabla símplex que resulta al aplicar esta técnica al ejemplo. La solución óptima (x1 = 2, x2 =6) es la misma que en la primera versión del problema de la Wyndor Glass Co. En cualquier caso, debe observarse que se obtuvo una secuencia distinta de soluciones básicas factibles,porque la comparación de los factores multiplicativos (3>2) condujo a la elección de x1 en lugar de x2 como la variable básica entrante inicial. Si la restricción de igualdad hubiera sido 3x1 + 3x2 = 18, los dos factores multiplicativos hubiera sido -3 y entonces la comparación de los factores aditivos (5>3) hubiera llevado a la elección de x2 como antes.
Este ejemplo incluyó solo una restriccion de igualdad. Si un modelo de programación lineal tiene más, cada una debe manejarse de la misma manera. [Si el lado derecho es negativo, primero se multiplican ambos lados por (-1).] Entonces, cada restricción de éstas tendrá una variable artificial que se usa como variable básica inicial; a cada una de estas variables se le asigna un coeficiente de -M [o por +M cuando se cambia la variable al lado izquierdo de la ecuación (0)] en la función objetivo, y al renglón 0 que resulta se le resta cada renglón que corresponde a las restricciones de igualdad multiplicado por M.
La forma de manejar otros tipos de restricciones que requieren variables artificiales es totalmente análoga. Para ilustrar los ajustes que se hacen para las distintas formas, se usará el modelo para diseñar la terapia de la radiación de Mary según se presento antes. Por conveniencia repetimos el modelo aca.
Este ejemplo incluyó solo una restriccion de igualdad. Si un modelo de programación lineal tiene más, cada una debe manejarse de la misma manera. [Si el lado derecho es negativo, primero se multiplican ambos lados por (-1).] Entonces, cada restricción de éstas tendrá una variable artificial que se usa como variable básica inicial; a cada una de estas variables se le asigna un coeficiente de -M [o por +M cuando se cambia la variable al lado izquierdo de la ecuación (0)] en la función objetivo, y al renglón 0 que resulta se le resta cada renglón que corresponde a las restricciones de igualdad multiplicado por M.
La forma de manejar otros tipos de restricciones que requieren variables artificiales es totalmente análoga. Para ilustrar los ajustes que se hacen para las distintas formas, se usará el modelo para diseñar la terapia de la radiación de Mary según se presento antes. Por conveniencia repetimos el modelo aca.
lunes, 4 de noviembre de 2013
Restricciones en forma de igualdad (V)
Esto completa el trabajo adicional que se requiere en el paso inicial para problemas de este tipo y el resto del método símplex se trabaja igual que antes. Las cantidades que incluyen el valor M nunca aparecen en otro renglón que no sea el 0, así que sólo tienen que tomarse en cuenta en la prueba de optimalidad y al determinar la variable básica entrante. Una manera de manejar estas cantidades es asignar a M algún valor numérico (muy grande) y trabajar con las cantidades que resulten en el renglon 0 en la forma acostumbrada. Sin embargo, este enfoque puede acarrear errores de redondeo significativos que a su vez pueden invalidar la prueba de optimalidad. Por tanto, es mejor hacer lo que acaba de mostrarse, esto es, expresar cada coeficiente del renglón 0 como una funcion lineal aM +b de la cantidad simbólica M al registrar y actualizar por separado el valor numérico de:1) el factor multiplicativo a y 2) el factor aditivo b. Como se supone que M es tan grande que b es despreciable comparado con aM cuando a ≠ 0, las decisiones en la prueba de optimalidad y la elección de la variable básica entrante se hacen sólo con los valores de los factores multiplicativos en la forma usual.
La única excepción ocurre cuando esto lleva a un empate [donde un empate para la prueba de optimalidad quiere decir que el facto (o factores) multiplicativo más pequeño es igual a cero] en cuyo caso el empate se rompe si se usan los factores aditivos correspondientes.
Restricciones en forma de igualdad (IV)
Pero esta Ro no se puede usar en la tabla símplex inicial para aplicar el método símplex, ya que no se encuentra en la forma apropiada de eliminación de Gauss. Esta forma requiere, en parte, que toda variable básica (sin contar Z, que sólo hace las veces de una variable básica) se elimine de la ecuación (0) y, en caso , x5 es una variable básica con coeficiente M. Es esencial recuperar esta forma apropiada tanto para la prueba de optimalidad com la determinar la variable básica entrante. Por lo general, esta forma se obtiene automáticamente en la parte de eliminación de Gauss del paso iterativo y se usará este método para recuperarla. Procediendo como si la columna de la variable (x5) fuera la columna pivote y la ecuación que contiene esta variable (renglón 3) fuera del renglón pivote, los cálculos son los siguientes.
domingo, 3 de noviembre de 2013
Restricciones en forma de igualdad (III)
El efecto de introducir una variable artificial es agrandar la región factible. En este caso la dicha región se expande del segmento de línea que une (2,6) y (4,3) a toda la región sombreada que se muestra en la figura 3.2. Una solución factible para el problema revisado (con 3x1 + 2x2 + x5 = 18 y x5 ≥ 0) también es factible para el problema original ( con 3x1 + 2x2 =18) si la variable artificial es igual a cero (x5 = 0).
Ahora supóngase que se permite que el método simplex obtenga una solución óptima para el problema revisado y que, por coincidencia, esta solución es factible para el problema original. Se puede concluir entonces que la solución también es óptima para el problema original, de manera que el proceso ha terminado. (La razón es que esta solución es óptima en la región factible completa para el problema revisado, que incluye la región factible del problema original).
Por desgracia, no existe una garantía de que la solución óptima para el problema revisado sea siempre factible para el problema original; es decir, no existe garantía hasta que se haga otra revisión. Si se emplea el método de la M, esta revisión significa asignar una penalización tan grande al hecho de quedar fuera de la región factible del problema original, que obligue a la solución óptima del problema revisado a quedar dentro de esta región factible. Recuérdese que el problema revisado coincide con el problema original cuando x5 = 0. Por ello, si se cambia la función objetivo, Z = 3x1 + 5x2, a
Z = 3x1 + 5x2 - Mx5
donde M representa algún número positivo enorme, entonces el valor máximo de Z debe ocurrir cuando x5 (el valor de x5 no puede ser negativo). Después de algunos pequeños arreglos más (que se presentan en seguida), la aplicación del método símplex a este problema revisado llevará automáticamente a la solución buscada.
Al usar la función objetivo revisada, la ecuación (0) queda
Z - 3x1 - 5x2 + Mx5 = 0
o, en forma tabular, el renglon 0 preliminar (llamese Ro) se convierte en
Ro = [-3 -5 0 0 M, 0]
Restricciones en forma de igualdad (II)
Por ello, la región factible para este problema, consiste ahora nada más en el segmento que conecta los puntos (2,6) y (4,3).
Después de introducir las variables de holgura necesitarias todavía para las restricciones de desigualdad, la forma aumentada del problema es
(0) Z - 3x1 + 5x2 = 0
(1) x1 + x3 = 4
(2) 2x2 +x4 = 12
(3) 3x1 + 2x2 = 18
Desafortunadamente, estas ecuaciones no tiene una solución básica factible inicial obvia por que en la ecuación (3) ya no se tiene una variable de holgura para usar como variable básica inicial. La técnica de variables artificiales salva este obstáculo al introducir una variable artificial (llámese x5) en esta ecuación, como si fuera una variable de holgura! Entonces esta sección revisa el problema cambiando la ecuación (3) a
(3) 3x1 + 2x2 + x5 = 18,
junto con la restricción de no negatividad.
x5 ≥ 0,
igual que lo que se tenía en la versión del problema de la Wyndor Glass Co. presentada en la sección 3.1. Si se procede como antes, ahora se tiene una solución inicial básica factible (para el problema revisado) (x1, x2, x3, x4, x5) = (0,0,4,12,18).
Después de introducir las variables de holgura necesitarias todavía para las restricciones de desigualdad, la forma aumentada del problema es
(0) Z - 3x1 + 5x2 = 0
(1) x1 + x3 = 4
(2) 2x2 +x4 = 12
(3) 3x1 + 2x2 = 18
Desafortunadamente, estas ecuaciones no tiene una solución básica factible inicial obvia por que en la ecuación (3) ya no se tiene una variable de holgura para usar como variable básica inicial. La técnica de variables artificiales salva este obstáculo al introducir una variable artificial (llámese x5) en esta ecuación, como si fuera una variable de holgura! Entonces esta sección revisa el problema cambiando la ecuación (3) a
(3) 3x1 + 2x2 + x5 = 18,
junto con la restricción de no negatividad.
x5 ≥ 0,
igual que lo que se tenía en la versión del problema de la Wyndor Glass Co. presentada en la sección 3.1. Si se procede como antes, ahora se tiene una solución inicial básica factible (para el problema revisado) (x1, x2, x3, x4, x5) = (0,0,4,12,18).
sábado, 2 de noviembre de 2013
Restricciones en forma de igualdad (I)
En realidad, cualquier restricción en forma de igualdad,
es equivalente a dos restricciones de desigualdad
Sin embargo, en lugar de hacer estas sustitución e incrementar con ello el número de restricciones, es más conveniente usar la técnica de la variable artificial que se describe en seguida.
Supóngase que se modifica el problema de la Wyndor Glass Co. de la ecuación 3.1, de manera que la planta 3 deba utilizarse en toda su capacidad. El único cambio que sufre el modelo de programación líneal es que la tercera restricción, 3x1 + 2x2 ≤ 18, se convierte en una restricción de igualdad,
ai1x1 + ai2x2 +......+ainxn = bi
es equivalente a dos restricciones de desigualdad
ai1x1 + ai2x2 +......+ainxn ≤ bi
ai1x1 + ai2x2 +......+ainxn ≥ bi
Sin embargo, en lugar de hacer estas sustitución e incrementar con ello el número de restricciones, es más conveniente usar la técnica de la variable artificial que se describe en seguida.
Supóngase que se modifica el problema de la Wyndor Glass Co. de la ecuación 3.1, de manera que la planta 3 deba utilizarse en toda su capacidad. El único cambio que sufre el modelo de programación líneal es que la tercera restricción, 3x1 + 2x2 ≤ 18, se convierte en una restricción de igualdad,
3x1 + 2x2 = 18
Adaptación a otras formas de modelo
Hasta ahora se han presentado los detalles del método símplex con la suposición de que el problema se encuentra en nuestra forma estandar (maximizar Z sujeta a restricciones funcionales de la forma ≤ y restricciones de no negatividad sobre todas las variables), bi > 0 para toda i = 1,2,.....,m. En esta sección se establecerá como hacer los ajustes requeridos a otrsa formas legítimas de modelos de programación lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de manera que el resto del método símplex aplica justo como se aprendió.
El único problema real que introducen las otras formas de restricciones funcionales (=,≥ o bi ≤0) es identificar una solución inicial básica factible. Antes, la primera solución se encontraba en forma muy convincente al hacer que las variables de holgura fueran las variables básicas iniciales, donde cada una era igual a la constate positiva del lado derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar que se utiliza en estos casos es la técnica de variables artificiales. Esta construye un problema revisado más conveniente introduciendo una variable fícticia (llamada variable artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no negatividad también se aplican sobre estas variables y la función objetivo se modifica para que imponga una penalización exorbitante en el caso de que adquieran valores mayores que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la solución; después de esto se resuelve el problema real.
Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en que la única forma no estándar en el problema es la presencia de una o más restricciones en forma de igualdad.
viernes, 1 de noviembre de 2013
Restricciones de desigualdad ≥
El sentido de una desigualdad siempre se invierte cuando se multiplican ambos lados por (-1). En consecuencia, cualquier restricción funcional de la forma ≥ se puede convertir en una restricción equivalente con nuestra forma estándar ≤ cambiando los signos de todos los números en ambos lados.
Al usar este enfoque para la tercera restricción del ejemplo de terapia de radiación se obtiene:
0.6x1 + 0.4x2 ≥ 6
→ - 0.6x1 - 0.4x2 ≤ -6
→ - 0.6x1 - 0.4x2 +x5 ≤ -6
donde x5 es la variable de holgura para esta restricción. Aún así, todavía se necesita un cambio más, como se verá enseguida.
Al usar este enfoque para la tercera restricción del ejemplo de terapia de radiación se obtiene:
0.6x1 + 0.4x2 ≥ 6
→ - 0.6x1 - 0.4x2 ≤ -6
→ - 0.6x1 - 0.4x2 +x5 ≤ -6
donde x5 es la variable de holgura para esta restricción. Aún así, todavía se necesita un cambio más, como se verá enseguida.
Soluciones óptimas múltiples (II)
A manera de ilustración, considérese el caso anterior del problema de la Wyndor Glass Co. donde la función objetivo es Z = 3x1 + 2x2. En la tabla del anterior post se muestran las primeras tres tablas que obtiene el método símplex antes de detenerse con una solución básica factible óptima. No obstante, como una variable no básica (x3) en esta iteración tiene coeficiente cero en el renglón 0, se realiza una iteración más en esa misma tabla para identificar la otra solución básica factible óptima. Entonces las dos soluciones básicas factibles óptimas son (4,3,0,6,0) y (2,6,2,0,0), y ambas dan un valor de Z = 18. Nótese que la última tabla símplex también tiene una variable no básica (x4) con coeficientes cero en la ecuación (0). Esta situación es inevitable porque las iteraciones adicionales no cambian el renglón 0, con lo que cada una de las variables básicas que salen conserva su coeficiente cero. Si ahora se eligiera x4 como variable básica entrante, sólo se regresaría a la tercera tabla símplex. (Verifiquese esto). Por ello, estas dos son las únicas soluciones básicas factibles que son óptimas, y todas las demás son un promedio ponderado de ellas. En particular, sean α y (1-α) las ponderaciones de estas dos soluciones, en donde α debe debe ser un número entre 0 y 1. Entonces toda solución óptima está dada por la fórmula vector α (4,3,0,6,0) + (1-α)(2,6,2,0,0) para 0 ≤ α ≤ 1.
Soluciones óptimas múltiples (I)
En la sección 3.2 se mencionó que un problema puede tener más de una solución óptima. Este hecho se ejemplificó al cambiar la función objetivo del problema de la Wyndor Glass Co. z Z = 3x1 + 2x2, de lo que resultó que todos los puntos sobre el segmento de recta entre (2,6) y (4,3) eran óptimos. También se hizo notar en la sección 4.1 que todos los problemas de este tipo tienen al menos dos soluciones factibles en un vértice (soluciones básicas factibles) que son óptimas. Estas soluciones se pueden usar para identificar el resto de las soluciones óptimas.
El método símplex se detiene automáticamente al encontrar una solución óptima. Sin embargo, en muchas aplicaciones de programación lineal existen factores intangibles que no se incorporan al modelo y que pueden ser útiles para tomar decisiones significativas respeto a cuál de las soluciones óptimas alternativas que proporciona el modelo es lo mejor. En esos casos, también deben identificarse las otras soluciones óptimas. Una vez que el método símplex encuentra una solución básica factible óptima, Cómo reconoce que existen otras y cómo se encuentran? La respuesta se resume como sigue:
Siempre que un problema tiene más de una solución básicas factible óptima, al menos una variable no básica tiene coeficiente de cero en la ecuación (0) final, de manera que si aumenta su valor, el valor de la función Z no cambia. Por lo tanto estas otras soluciones, básicas factibles óptimas se pueden identificar (si se desea) realizando iteraciones adicionales del método símplex, en las que cada vez se elige una variable no básica con coeficiente cero como variable básica entrante.
Suscribirse a:
Entradas (Atom)