Formulacion Propiedad esencial de programación separable - Ejemplo (III)

Con esto se llega a la propiedad esencial de programación separable. Si bien este modelo no toma en cuenta este factor de manera explícita, lo hace en forma implícita! Aunque el modelo tenga un exceso de soluciones "factibles" que en realidad son inaceptable, se garantiza que cualquier solución óptima será legítima, es decir, que no sustituirá tiempo de trabajo normal disponible con horas extra. (El razonamiento en este caso es análogo al del método de la M que se presentó en la sección 4.6, en el que también se permiten más soluciones factibles, pero no óptimas, de las reales por conveniencia para trabajar.) En efecto, se puede aplicar con seguridad el método símplex a este modelo para encontrar la mezcla de productos más redituable. La razón es doble. Primero, las dos variables de decisión para cada producto siempre aparecen juntas como una suma, (x1R + x1O) o (x2R + x2O), en cada restricción funcional (un en este caso) distinta a las restricciones de cota superior sobre las variables indiviaduales. Por tanto, siempre es posible convertir una solución factible no aceptable en una aceptable que tenga las mismas tasas de producción totales, x1 = x1R + x1O  y x2 = x2R + x2O, con sólo reemplazar la producción en tiempo extra por producción normal lo más que se pueda. SEgundo, la producción en tiempo extra es menos redituable que la normal (es decir, la pendiente de cada curva de ganancia de la figura 15.13 es una función monótona decreciente de la tasa de producción), de modo que al convertir una solución factible no aceptable en una aceptable debe incrementarse la tasa total de la ganancia Z. En consecuencia, cualquier solución factible que usa tiempo extra de producción para un producto, cuando todavía se dispone de tiempo normal, no puede ser óptima respecto al modelo.

Formulacion Propiedad esencial de programación separable - Ejemplo (II)

Sin embargo, existe un factor importante que no se toma en cuenta en esta formulación y éste es que no existe nada en el modelo que requiera que se utilice todo el tiempo normal disponible, antes de emplear cualquier tiempo extra para ese producto. En otras palabras, puede ser factible tener x10 > 0 aun cuando x1R < 3 y tener x20 > 0  aun cuando x2R < 3. Tal solución sería inaceptable para la gerencia. ( La prohibición de esta solución lleva a la reestricción especial de la que se hablaba)

Formulacion Propiedad esencial de programación separable - Ejemplo (I)

A primera vista puede parecer sencillo modificar el modelo de programación lineal de la Wyndor Glass Co. para que se ajuste a esta nueva situación. En particular, sea x1 = x1R + x1O la tasa de producción para el producto 1, en donde x1R es la tasa de producción alcanzada con tiempos normales de trabajo y x1O es la tasa de producci;on incremental al usar tiempo extra. Sea x2 = x2R + x2O definida de la misma manera para el producto 2. Así,  n =2, n1 = 2 y n2 = 2 en el modelo general anterior. El nuevo problema de programación lineal trata de determinar  los valores de x1R, x1O, x2R, x2O para

Propiedad esencial de programación separable - Ejemplo (II)

La administración ha tomado la decisión de usar tiempo extra en lugar de contratar más trabajadores durante esta situación temporal. Sin embargo, insiste en que se aprovechen por completo las brigadas de trabajo de cada producto en tiempo normal antes de usar cualquier tiempo extra. Lo que es más, piensa que temporalmente se deben cambiar las tasas de producción actuales (x1 =2 para el producto 1 y x2 =  6 para el producto 2), si esto mejora el rendimiento total. Por todo esto, ha girado instrucciones al departamento de investigación de operaciones para revisar los productos 1 y 2 y determinar de nuevo la mezcla de productos más redituables para los próximos cuatro meses.

Propiedad esencial de programación separable - Ejemplo

La Wyndor Glass Co. (véase la sección 3.1) recibió un pedido especial deartículos de procesos manuales que se deben elaborar en las plantas 1 y 2 durante los próximos cuatro meses. PAra cumplir con este pedido será necesario asignar algunos empleados de las brigadas de trabajo de los productos normales, por lo que los trabajadores se queden tendrán que trabajar horas extra para utilizar toda la capacidad de producción de la maquinaria y equipo de la planta para estos productos. En particular, a fin de fabricar los dos nuevos productos normales que se analizaron en la sección 3.1, el tiempo extra tendrá que utilizar el último 25% de la capacidad disponible en la planta 1 para el producto 1 y el último 50% de la capacidad disponible en la planta 2 para el producto 2. El costo adicional del tiempo extra reducirá la ganancia de cada unidad de $3 a $2 para el producto 1 y de $5 a $1 para el producto 2, de lo que resultarán las curvas de ganancia de la figura  14.3, las cuales se ajustan a la forma del caso 1 de la figura 14.12.

Propiedad esencial de programación separable (III)

La manera más eficiente de resolver este modelo es usar la versión simplificada del método símplex para manejar restricciones de cota superior, que se mencionó al final de la sección 7.5 (y se describió en la sección 9.1). Después de obtener una solución óptima para este modelo, se calcula

Propiedad esencial de programación separable (II)

Para escribir el modelo completo de programación lineal con la notación anterior, sea nj el número de segmentos de recta en fj(xj) (o en la función lineal por prtes que la aproxima), de manera que

Propiedad esencial de programación separable (I)

Cuando f(x) y gi(x) satisfacen las suposiciones de programación separable y cuando las funciones lineales por partes que resulta se ponen en la forma de funciones lineales, al eliminar la restricción especial se obtiene un modelo de programación lineal cuya solución satisface de manera automática la restricción especial.

Más adelante, en esta sección, se profundizara un poco más en la lógica que sustenta esta propiedad esencial, en el contexto del ejemplo específico.

Reformulación como un problema de programación lineal (II)

La restricción especial sólo permite la primera posibilidad, que es la única que da el valor correcto para fj(1).

Desafortunadamente, la restricción especial no se ajusta al formato requerido para las restricciones de programación lineal, y así algunas funciones lineales por partes no se pueden reescribir en el formato de programación lineal. Sin embargo, se supone que nuestra fj(xj) es cóncava, por lo que sj1 > sj2 > ....., y así, un algortimo para maximizar f(x) automáticamente asigna la prioridad más alta al uso de xj1 cuando (de hecho) se aumenta el valor de xj desde cero, la siguiente prioridad al uso de xj2, etc., sin incluir siquiera la restricción especial en forma explícita en el modelo. Esta observación conduce a la siguiente propiedad esencial.

Reformulación como un problema de programación lineal (I)

La clave para dar una información lineal por partes la forma de una función lineal es usar variables separadas para cada segmento de recta. Para ilustrar esto, considérese la función lineal por partes fj(xj) que se muestra en la figura 14.12 caso 1 (o su aproximación en el caso 2), que tiene tres segmentos de recta en el intervalo de valores factibles de xj. Se introducen las tres nuevas variables, xj1, xj2, xj3, y se establece

Programación separable (V)

Este tipo de situaciones puede conducir a cualquiera de las curvas de ganancia que se muestar en la figura 14.12. En el caso 1, la pendiente decrece a intervalos, de manera que fj(xj) es una función lineal por partes (una sucesión de segmentos de recta conectados). Para el caso 2, la pendiente puede decrecer en forma continua al crecer xj, de manera que fj(xj) es una función cóncava general. Cualquier función de este tipo se puede aproximar tanto como  se quiera por una función lineal por aprtes y este tipo de aproximación se usa, según sea necesario, para problemas de programación separable. (La figura 14.12 muestra una función de aproximación que consiste en sólo tres segmentos de recta, pero la aproximación se puede mejorar si se introducen en intervalos.) Esta aproximación es muy conveniente, ya que una función lineal por partes de una sola variable se puede escribir como una función lineal de varias variables, con la restricción especial sobre estas variables que se describe a continuación.

Programación separable (IV)

De manera que cada fj(xj) tiene una forma como la que se muestra en la figura 14.12 (cualquier caso), en el rango de valores factibles de xj. Como f(x) representa la medida de desempeño (por ejemplo, ganancia) de todas las actividades juntas, fj(xj) representa la contribución de la ganancia por parte de la actividad j cuando se realiza al nivel xj. La condición de que f(x) sea separable simplemente implica aditividad (véase la sección 3.3); esto es, no existe interacción entre las actividades (no se tienen términos de productos cruzados) que afecten la ganancia total más allá de sus contribuciones independientes. La suposición de que cada fj(xj) es cóncava indica que la ganancia marginal (pendiente de la curva de ganancia), se mantiene igual o decrece (nunca aumenta) conforme xj crece.

Las curvas cóncavas para la ganancia  ocurren con mucha frecuencia. Por ejemplo, puede ser posible vender una cantidad limitada de algún producto a un cierto precio y después una cantidad adicional a un precio menor, y tal vez, otra cantidad adicional a un precio todavía menor. De igual manera, puede ser necesario comprar materias primas a fuentes cada vez más costosas. Otra situación común es aquélla en la que debe emplearse un proceso de producción más caro (como el uso de tiempo extra), para aumentar la tasa de producción sobre una cierta cantidad.

Programación separable (III)

Programación separable (II)

Bajo las suposiciones anteriores, la función objetivo se puede expresar como una suma de funciones cóncavas de variables individuales,