Funciones lineales con componentes positivas y negativas (I)

La medida de desempeño también se puede comportar como se ilustra en la figura 8.1, cuando el valor de la abscisa se define por una función lineal y no por una variable. De hecho, como frecuencia el mismo ejemplo de nivel del inventario surge de manera natural en el modelo como una función lineal de las variables de decisión. Se vera cómo ocurre esto en el segundo ejemplo de la sección 8.4, en donde las variables de decisión de cada periodo j (o t en la sección 8.4) son el nivel de producción Pj y el nivel de mano de obra Wj pero es necesario incorporar al modelo el nivel de inventario con el fin de incluir sus costos en la función objetivo. Para preparar el terreno para esta incorporación se introduce una variable auxiliar xj (o Ij según la sección 8.4) para cada periodo j que representa el nivel de inventario al final del período despues se expresa esta variable como una función lineal de las variables de decisión apropiadas, etc, En este caso:

xj = xj-1 + Pj - Sj

en donde Sj es el nivel de ventas pronosticado (una constante dada) para el periodo J.

Variables o funciones lineales con componentes positiva y negativa (IV)

Cuando esta relación no se cumple, la reformulación anterior crea una Z no acotada en la dirección favorable, simplemente agregando el mismo valor positivos grande (sin cota en su tamaño) tanto a xj+ como a xj-. Si se agrega el mismo número a xj+ y a xj-. el valor de xj = xj+ - xj- no cambia.

Debido a que esto surge con alguna frecuencia, un caso especial importante de esta técnica es aquél en que cj+ = cj- (llémese a éste valor el valor común cj), de manera que Zj es sencillamente proporcional al valor absoluto de xj, |xj|. Para satisfacer la restricción anterior sobre cj+ y cj- supóngase que cj ≥ 0 cuando se minimiza Z o que cj ≤ 0 cuado se maximiza Z Nótese que:

Variables o funciones lineales con componentes positiva y negativa (III)

Dada esta diferencia entre el caso positivo y el negativo, el costo de xj no es proporcional a xj y queda violada la suposición de proporcionalidad de la programación líneal en este ejemplo. Esto se ilustra en la figura 8.1, en donde, en lugar de una sola línea recta que pasa por el origen (suposición de proporcionalidad), se tiene que el costo unitario de mantener un inventario (xj positivo) es $2 por unidad de tiempo, mientras que el costo unitario por faltantes (xj negativo) es $3 por unidad de tiempo (y no -$2)

Por fortuna, siempre que se cumpla la suposición de proporcionalidad para el caso positivo y el negativo considerados por separado, la función objetivo se puede reformular dentro del formato de programación lineal si se emplea xj+ y xj-. Sea.

Variables o funciones lineales con componentes positiva y negativa (II)

El  efecto de elegir el valor de xj puede ser muy diferente para valores positivos y negativos. Por ejemplo, supóngase que xj representa el nivel de inventario de un producto específico. Si zj > 0 (de manera que xj+ <0 y xj- = 0), los costos en que se incurre incluyen los gastos de almacenamiento y los cargos de interés sobre el capital comprometido en este inventario. Por otro lado, xj <0 (de forma que xj- >0 y Xj+ =) significa que ocurrió una faltante de xj- unidades. En este caso, los costos se deben a las ventas perdidas tanto en este momento (si el cliente no está dispuesto a esperar) como en el futuro (ya que los clientes decepcionados no regresaran)

Variables o funciones lineales con componentes positiva y negativa (I)

Variables con componentes positiva y negativa

Como ya se dijo al final de la sección 4.6, a veces es necesario manejar variables a las que se permite tomar valores positivos y negativos. Cuando no existe una cota sobre los valores negativos permisibles, cada variable (xj) se puede sustituir a través del modelo por la diferencia de dos nuevas variables no negativas (xj+ y xj-), de manera que

para todas las soluciones básicas factibles, ya que tales soluciones tienen necesariamente  la propiedad de que xj+ = 0 o bien, xj- = 0 (o ambos). Entonces, cuando se aplica el método símplex al modelo, después de sustituir xj por (xj+ y xj-), nunca tendrán a xj+ y a xj- como variables básicas al mismo tiempo. (Se seguirá empleando esta notación con los superíndices más o menos en este capítulo para representar las componentes positiva y negativa de cualquier cantidad, sin importar si se trata de, valor de una variable o de una función.)

Formulación de Modelos de programación lineal, incluyendo programación por objetivos

En el capitulo 3 se introdujo la naturaleza general de los problemas de programación lineal; en los capítulos 4,5 y 6 se describió la manera de resolverlos y analizarlos. Después, en el capítulo 7 se presentó una clase especial de problemas de programación lineal que tienen una gran importancia. Sin embargo, estos capítulos han incluido sólo una parte de la historia. Los usuarios de programación lineal que han tenido sólo una parte de la historia. Los usuarios de programación lineal que han tenido un mayor éxito informan que una de las áreas cruciales en su trabajo es la construcción del modelo. Muchas de las aplicaciones más notorias abarcan problemas cuya naturaleza ni siquiera se parece a un modelo de programación lineal. Es sólo a través de técnicas de formulación sutiles como se puede reformular el problema para ajustarlo a la programación lineal y a sus poderosos procedimientos de solución. Este capítulo se dedica a la descripción e ilustración de las técnicas más útiles de formulación, para proporcionar al lector una perspectiva más completa de las aplicaciones de programación linea..

La primera sección describe el manejo de variables de funciones lineales que pueden tomar valores positivos o negativos, pero con costos unitarios distintos. Esta descripción lleva al tema central de programación por objetivos (véase la sección 8.2) en el que el objetivo único característico de programación lineal se sustituye por varios objetivos que tratarán de alcanzarse simultáneamente. La técnica de formulación de la sección 8.1 permite adaptar un problema como esté al formato de programación lineal. La sección 8.3 trata un problema bastante parecido en el qeu se tienen varias funciones objetivo y se maximiza aquélla que tiene el valor más pequeño. Otra técnica de formulación muestra cómo se puede recuperar el formato de programación lineal en este caso.

Estas tres secciones también se ilustran una técnica de formulación adicional muy útil, a saber, la introducción de variables auxiliares. Al contrario de las variables de decisión, las auxiliares no representan las decisiones originales del problema, son simplemente variables adicionales que resultan útiles para la formulación del modelo. Esta técnica surge de nuevo en la sección 8.4 que presenta algunos ejemplos de formulaciones más o menos complicadas. Por último, la sección 8.5 está dedicada al estudio de un caso que integra algunas de las ideas básicas de este capítulo y anteriores.

Conclusiones Problemas especiales de programación lineal

El problema de programación líneal abarca una gran variedad de tipos específicos de problemas. El método símplex general es un algoritmo poderoso que puede resolver versiones sorprendentemente grandes de cualquiera de estos problemas. Algunos de estos problemas tienen formulaciones tan sencillas que se pueden resolver de manera mucho más eficiente mediante versiones simplificadas del método símplex, que aprovechan su estructura especial. Estas versiones simplificadas pueden reducir mucho el tiempo de computadora que requieren los problemas grandes y algunas veces, de hecho, permiten que los problemas grandes se puedan resolver en una computadora. Esto es cierto en particular para problemas de transporte y trasbordo, para problemas de asignación y para problemas con muchas restricciones CSG y de cota superior. Para problemas multidivisionales en general, el tiempo de preparación es tan grande para el procedimiento simplificado que se recomienda usarlo en forma selectiva sólo en problemas grandes.

En la sección 10.6 se examinará la estructura especial de los problemas de transporte, trasbordo y asignación. Ahí se verá que estos problemas son casos especiales de una clase importante de problemas de programación líneal conocidos como el problema de flujo máximo. Este problema se interpreta como minimizar el costo del flujo de bienes a través de una red. La interpretación de red agregará una visión más amplia de la estructura de estos tres problemas.

Una gran parte de la investigación continúa dedicada al desarrollo de procedimientos de solución simplificados para los problemas de programación líneal de tipo especial, entre los que se cuentan algunos que no se presentaron aquí. Al mismo tiempo, existe un amplio interés en las aplicaciones de programación líneal para optimizar la operación de sistemas complicados de gran escala, incluso los sistemas sociales. Las formulaciones que resultan casi siempre tienen estructuras especiales que se pueden aprovechar. Reconocer y explotar estas estructuras especiales se ha convertido en un factor muy importante en la aplicación exitosa de la programación líneal.