jueves, 31 de julio de 2014

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.


miércoles, 30 de julio de 2014

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:

martes, 29 de julio de 2014

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.



lunes, 28 de julio de 2014

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)


domingo, 27 de julio de 2014

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.)

sábado, 26 de julio de 2014

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.

viernes, 25 de julio de 2014

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.


jueves, 24 de julio de 2014

Casos especiales importantes (II)

Tanto las restricciones de cota superior como las CSG ocurren debido a la naturaleza multidivisional del problema. Sin embargo, debe hacerse hincapié en que con frecuencia surgen también en muchos otros contextos. De hecho, ya  se han visto varios ejemplos que contienen restricciones de este tipo.

Nótese la tabla 7.6 que en realidad todas las restricciones del problema de transporte son restricciones CSG. ( La Tabla 7.6 se ajusta a la forma de la tabla 7.35 si se colocan las restricciones de recursos abajo de las restricciones de la demanda). A su vez, las restricciones de demanda se pueden interprestar como restricciones CSG pero sin manejar variables consecutivas.

Tanto las restricciones de terreno como las de cosecha en el problema de planeación regional de la confederación de Kibbutzim (veáse la sección 3.4) son restricciones CSG.

Las restricciones tecnológicas en el problema de contaminación del aire de la Nori &Leets Co. (Veáse la sección 3.4) son restricciones de cota superior al igual que dos de las tres restricciones funcionales en el problema de mezcla de productos de la Wyndor Glass Co. (Sec 31).

En vista de la frecuencia con que ocurren las restricciones CSG y de cota superior , se han desarrollado técnicas especiales para simplificar su manejo en el método símplex. (La técnica para las restricciones d ecota superior se describe en la sección 9.1 y la de las restricciones CSG es muy parecida.) Si se tienen muchas restricciones, estas técnicas pueden reducir en forma notable el tiempo de computación.

miércoles, 23 de julio de 2014

Casos especiales importantes (I)

Con frecuencia surgen formas todavía más simples de la estructura especial que se exhibe en la tabla 7.32. En la tabla 7.35 se muestran dos de ellas especialmente comunes.

La primera ocurre cuando algunas o todas las variables se pueden agrupar de manera que la suma de las variables en cada grupo no exceda una cota superior para ese grupo (o quizá deba ser igual a una constante especifica). Por lo general, las restricciones de esta forma.


martes, 22 de julio de 2014

Ejemplo Prototipo - Good Foods Corporation (II)

Nótese que la tabla correspondiente a los coeficientes de las restricciones, que se muestra en la tabla 7.34, tiene la estructura especial de los problemas multivisionales dada en la tabla 7.32. Sin duda, entonces, la Good Foods Co. puede resolver este problema ( o una versión más detallada) si emplea la versión simplificada del método símplex que proporciona el principio de descomposición.

lunes, 21 de julio de 2014

Ejemplo Prototipo - Good Foods Corporation (I)

La Good Foods Corporation es una empresa grande que produce y distribuye productos alimenticios. Tiene tres divisiones principales: la división de alimentos procesados, la división de alimentos enlatados y la división de alimentos congelados. Como los costos y precios de venta cambian con frecuencia en la industria alimenticia, la Good Foods usa periódicamente un modelo de programación lineal de la compañia para revisar las tasas de producción de sus productos, con el objeto de utilizar sus capacidades disponibles de la manera más redituable posible. Este modelo es parecido al de la Wyndor Glass Co. (veáse la sección 3.1), pero de mayor escala, con cientos de restricciones y variables. (Como el espacio en el libro es limitado, se describirá una versión simplificada del problema que combina los productos o recursos por tipos).

La corpración cultiva sus propias papas y maíz de alta calidad, y estas dos materias primas básicas son las únicas de bajo abastecimiento que en la actualidad usan todas las divisiones.

Excepto por estos recursos organizacionales, cada división utiliza sus propios recursos y, por lo tanto, puede determinar sus tasas de producción en forma autónoma. En la tabla 7.33 se dan los datos de cada división y el subproblema correspondiente que incluye sólo sus recursos y productos (en donde Z representa la ganancia mensual en millones de dólares), junto con los datos de los recursos de la organización.

El problema de programación lineal que se obtiene para esta corporación es


domingo, 20 de julio de 2014

Problemas multidivisionales (II)

Conceptualmente, esta versión simplificada del método símplex se puede interpretar como la posibilidad de dejar que cada división resuelva su subproblema  mande su solución como propuesta a la "coordinación general" (el problema maestro), en donde se negocian las propuestas de todas las divisiones  para encontrar una solución óptima para toda la organización. Si los subproblemas son de un tamaño razonable y el problema maestro no es demasiado grande (no más de 50 o 100 restricciones), este enfoque puede tener éxito al resolver algunos problemas multidivisionales extremadamente grandes. En particular, vale la pena aplicarlo cuando el número total de restricciones es bastante grande (por lo menos varios cientos ) y existen varios subproblemas, más que unos cuantos.


sábado, 19 de julio de 2014

Problemas multidivisionales (I)

Otra clase importante de problemas de programación lineal son una estructura especial que se puede explotar consiste en los problemas multivisionales. Su característica especial es que se refieren a la coordinación de las decisiones de divisiones independientes de una empresa grande. Como las divisiones operan con bastante autonomía , el problema casi se puede descomponer en problemas separados, en donde cada división se aboca sólo a optimizar su propia operación; sin embargo,  se requiere alguna coordinación general con el fin de dividir mejor ciertos recursos organizacionales entre las divisiones.

Como resultado de esta característica especial, la tabla de coeficientes de restricciónes en los problemas multidivisionales tiene la estructura angular de bloque que se muestra en la tabla 7.32 (recuérdese que las áreas sombreadas de la tabla representan las únicas porciones de la tabla que tiene cualquier coeficiente aij distinto de cero.) Entonces, cada pequeño bloque contiene los coeficientes de las restricciones de un subproblema, a saber, el problema de optimizar la operación de una división específica. El bloque grande de la parte superior contiene los coeficientes de las restricciones de enlace para el problema maestro, es decir, el problema  de coordinar las actividades de las divisiones y la repartición de los recursos de la organización  entre ellas, con el objeto de  obtener una solución óptima global para toda la organización.

Por su naturaleza, los problemas multidivisionales suelen ser muy grandes y contienen muchos cientos y hasta miles de restricciones y variables. Puede ser necesario explotar su estructura  especial con el fin de poder resolverlos con un gasto razonable de tiempo de computadora, y a veces para poder siguiera resolverlos. El principio de descomposición (descrito en las referencias selectas 2 y 3 del final de este capítulo) proporciona una manera eficiente de explotar esta estructura especial.

viernes, 18 de julio de 2014

Formulación de la opción 2 (III)

Como es usual, una manera de obtener esta solución óptima es convertir la tabla de costos de la tabla 7.31 a una tabla de costos y requerimientos equivalente para el problema de transporte (véase la tabla 7.28) y después aplicar el método símplex de transporte. Debido a que la tabla 7.31 contiene dosrenglones idénticos, este engoque se puede simplicadicar combinando los cinco asignados en tres orígenes con costos 2, 2 y 1, respecticamente. Esta simplificación también disminuirá el número de variables básicas degeneradas en todas las soluciones básicas factibles.
Ahora se debe comparar esta solución con la que se obtuvo para la opción 1, que incluye la separación del producto 4 entre las plantas 2 y 3. Las asignaciones son diferentes en las dos soluciones, pero el costo total es casi el mismo (Z=3270 para la opción 1 y Z=3290 para la opción 2.) Entonces, al tomar en cuenta los costos no evidentes asociados con la separación de productos, la gerencia decidió adoptar la solución de la opción 2.

jueves, 17 de julio de 2014

Formulación de la opción 2 (II)

El número de asignados (ahora cinco) debe ser igual al número de asignaciones (ahora cuatro), así que se introduce una asignación ficticia (producto) como 5(D) en la tabla 7.31. El papel de esta asignación ficticia es proporcionar un segundo producto ficticio a cualquiera de las plantas 1 o 2, que recibe sólo un producto real. No se incurre en ningún costo por producir un producto ficticio así que, como siempre, los costos de la asignación ficticia son cero. La excepción es el costo M en el último renglón de la tabla 7.31. La razón es que la planta 3 debe recibir un producto real y el método de la M evita que se le asigne el producto ficticio a esta planta.

El resto de los costos en la tabla 7.31 no son los costos unitarios que se muestran en la tabla 7.29 o 7.30. Para un problema de asignación, el costo cij es el costo total asociado al hecho de que el asignado i realice la asignación j. En la tabla 7.31, el costo total (por día) para que la planta i fabrique el producto j es el costo de producción multiplicado por el número de unidades producidas (por día), donde estas dos cantidades a multiplicar se dan por separado en la tabla 7.29)Igual que en la tabla 7.30, la M evita la asignación no factible del producto 3 a la planta 2).

La solución óptima para este problema de asignación es

La planta 1 fabrica los productos 2 y 3
La planta 2 fabrica el producto 1,
La planta 3 fabrica el producto 4,

donde la asignación ficticia se da en la planta 2. El costo total es Z = 3290

miércoles, 16 de julio de 2014

Formulación de la opción 2 (I)

Sin la separación de productos, cada producto debe asignarse a una sola planta. Entonces, los productos se pueden interpretar como las asignaciones en un probema de asignación y las plantas como los asignados.

La gerencia ha especificado que debe asignarse al menos uno de los productos a cada planta. Se tienen más productos (cuatro) que plantas (tres), por lo que tendrá que asignar dos productos a una de las plantas. La planta 3 tiene apenas la capacidad adicional para producir un producto (véase la tabla 7.29), así, la planta 1 o bien la 2 fabricará el otro producto.

Para hacer posible la asignación de este producto adicional dentro de la formulación de un problema de asignación, las plantas 1 y 2 se dividen en dos asignados cada una, como se muestran en la tabla 7.31.



martes, 15 de julio de 2014

Formulación de la opción 1

Al permitir la separación de productos, la tabla 7.29 se puede convertir directamente a una tabla de costos y requerimientos para un problema de transporte. Las plantas se convierten en orígenes  y los productos en destinos (o viceversa); así, los recursos se interpretan como las capacidades de producción y las demandas como las tasas de producción requeridas. Sólo se tienen que hacer dos cambios en la tabla 7.29. Primero, como la planta 2 no puede fabricar el producto 3, se evita esa asignación dando un costo unitario muy grande, M. Segundo, La capacidad total (75+75+45 = 195) excede la producción total requerida (20+30+30+40 = 120) así que se necesita un destino ficticio con una demanda de 75 para balancear estas dos cantidades. La tabla de costos y requerimientos que resulta se muestra en la tabla 7.30/

L solución óptima de este problema de transporte tiene variables básicas (asignaciones) x12 = 30, x13 = 30, x15 = 15, x24 = 15, x25 = 60, x31 = 20 y x34 = 25, de manera que

La planta 1 produce todos los productos 2 y 3,
La planta 2 produce la mitad del producto 4,
La planta 3 produce la mitad del producto 4 y todo el producto 1.

El costo total es Z = 3270

lunes, 14 de julio de 2014

Ejemplo - Asignación de productos a plantas (II)

La segunda opción impone una restricción que sólo puede aumentar el costo de una solución óptima según la tabla 7.29. Por otro lado, la ventaja clave de la opción 2 es que elimina algunos costos no evidentes asociados con la separación de productos que no se reflejan en la tabla 7.29, incluyendo costos adicionales de preparación, distribución y administración. Por todo esto, la gerencia quiere que se analicen ambas opciones antes de tomar la decisión final. Para la opción 2 se ha especificado además que debe asignarse al menos uno de los productos a cada planta.

Se formulará  y resolverá el modelo para cada opción, en donde la opción 1 lleva al problema de transporte y la opción 2 al problema de asignación.


domingo, 13 de julio de 2014

Ejemplo - Asignación de productos a plantas (I)

La BETTER PRODUCTS COMPANY ha decidido iniciar la producción de cuatro nuevos productos utilizando tres plantas que por el momento tienen exceso de capacidad de producción. Los productos requieren un esfuerzo productivo comparable por unidad por lo que la capacidad de producción disponible en las plantas se mide por el número de unidades de cualquier producto que se pueden obtener por día, como se muestra en la última columna de la tabla 7.29. El último renglón da la producción diaria requerida para satisfacer las ventas proyectadas. Cada planta puede producir cualquiera de estos productos, excepto la planta 2 que no puede fabricar el producto 3. Sin embargo, el costo variable por unidad de cada producto difiere entre una planta y otra, como se muestra en el cuerpo de la tabla 7.29.

La gerencia necesita tomar la decisión de cómo dividir la producción entre las plantas. 

Tiene dos opciones:

Opción 1: permitir la separación de productos, de tal manera que el mismo producto se puede fabricar en más de una planta.

Opción 2: no autorizar la separación de productos.


sábado, 12 de julio de 2014

Modelo del problema de asignación y procedimientos de solución (V)

No es coincidencia que esta solución óptima que proporciona el método símplex de transporte tenga tantas variables básicas degeneradas. Para cualquier problema de asignación, la formulación del problema de transporte que se muestra en la tabla 7.28a tiene m = n. Los problemas de transporte tienen (m+n-1) variables basicas (asignaciones); así, toda la solución básica factible para este tipo de problema de transporte tiene (2n-1) variables básicas, pero sólo n de estas xij = 1. Por esto, siempre habrá (n-1) variables básicas degeneradas (xij = 0) Como se dijo al final de la sección 7.2, las variables básicas degeneradas no causan mayor complicación en la ejecución del algoritmo. No obstante, con frecuencia causan que se realicen iteraciones de balde, en las que nada cambia (asignaciones iguales) excepto la etiqueta de que asignaciones de cero corresponden a variables básicas degeneradas en lugar de a variables no básicas. Estas iteraciones de balde son un gran incoveniente para aplicar el método símplex de transporte a este tipo de situaciones en las que siempre hay tantas variables básicas degeneradas.

Otro incoveniente del método símplex de transporte es que se trata meramente de un algoritmo de propósitos generales para resolver todos los problemas de transporte. Así, no toma en cuenta la estructura especial adiciona en este tipo especial de problemas (m=n, toda si = 1 y toda dj = 1). Aunque no se describrían aquí, se han desarrollado algoritmos especiales para simplificar el procedimiento de solución exclusivo para los problemas de asignación. Estos algortimos operan directamente sobre la tabla de costos y no se preocupan por las variables básicas degeneradas. Si se dispone de un paquete de computadora para alguno de estos algoritmos, será preferible usarlo en lugar del método símplex de transporte.

viernes, 11 de julio de 2014

Modelo del problema de asignación y procedimientos de solución (IV)

Por lo general, los que aplican esta técnica a problemas de asignación específicos no se toman la molestia de escribir todo el modelo matemático. Es mucho más sencillo formularlo llenando la tabla de costos (por ejemplo, la tabla 7.27), con la identificación de los asignados y las asignaciones, a que esta tabla contiene todos los datos esenciales en una forma mucho más compacta.

Debido a que el problema de asignación es un tipo especial de problema de transporte, una forma conveniente de resolverlo es aplicar el método símplex de transporte que se describió en la sección 7.2. Este enfoque requiere que se convierta la tabla de costos a una tabla de costos y requerimientos para el problema de transporte equivalente, como se muestra en la tabla 7.28a.

Por ejemplo, la tabla 7.28b muestra la tabla de costos y requerimientos para la Job Shop Co. que se obtiene a partir de la tabla de costos en la tabla 7.27. Cuando se aplica el método símplex de transporte a esta formulación, la solución  óptima tiene variables básicas x13 = 0, x14 = 1, x23 = 1, x31 = 1, x41 = 0, x42 = 1, x43 =0. (En el problema 32 se le pide al lector que verifique esta solución). Las variables básicas degeneradas (xij = 0) y la asignación para la máquina ficticia no tienen significado para el problema original, de esta manera, las asignaciones reales son la máquina 1 al lugar 4, la máquina 2 al lugar 3 y la máquina 3 al lugar 1.

jueves, 10 de julio de 2014

Modelo del problema de asignación y procedimientos de solución (III)

Ahora se hará una comparación de este modelo (sin la restricción binaria) con el modelo del problema de transporte que se presentó en la segunda subsección de la sección 7.1 (incluyendo la tabla 7.6). Obsérvese que sus estructuras son similares. De hecho el problema de asignación es sólo un caso especial de los problemas de transporte en donde los orígenes son ahora los asignados y los destinos son las asignaciones, y donde

número de orígenes (m) = número de destinos (n)
cada recurso si = 1,
cada demanda dj =1

Ahora se centrará la atención en la propiedad de soluciones enteras de la subsección del modelo de transporte. Como ahora toda si y dj son enteros (=1), esta propiedad significa que toda solución básica factible (incluso la óptima) es entera para un problema de asignación.

Las restricciones funcionales del modelo de asginación evitan que las variables sean mayores que uno y las restricciones de no negatividad evitan valores menores que cero. Por lo tanto, al eleminar la restricción binaria para poder resolver el problema de asignacion como un problema de programación líneal, la solución básica factible que se obtiene (incluyendo la solución óptima final) automáticamente satisfará la restricción binaria.

miércoles, 9 de julio de 2014

Modelo del problema de asignación y procedimientos de solución (II)

Las variables binarias son importantes en investigación de operaciones para representar las decisiones de si o no, como se verá en detalle en el capítulo de programación entera (cap 13). En este caso, las decisiones de si o no son: debe el asignado i realizar la actividad j?

Sea Z el costo total, el modelo de asignación es


El primer conjunto de restricciones funcionales especifica que cada asignado realiza exactamente una asignación, mientras que el segundo conjunto requiere que cada asignación sea realizada exactamente por un asignado. Si se elimina la restricción entre paréntesis de que xij sean binarias, resulta claro que el modelo es un problema especial de programación linea, por lo que se puede resolver de inmediato. Por fortuna, debido a las razones que se expondrán en seguida, se puede eliminar esta restricción. (Precisamente, el que se pueda eliminar es la razón por la que el problema de asignación se incluye en este capítulo y no en el de programación entera.

martes, 8 de julio de 2014

Modelo del problema de asignación y procedimientos de solución (I)

El modelo matemático para el problema de asignación utiliza las siguientes variables de decisión:



para i = 1,2, ..........., n y j = 1,2,........., n. Entonces, cada xij es una variable binaria (0 o 1).

lunes, 7 de julio de 2014

Ejemplo Prototipo

La JOB SHOP COMPANY ha comprado tres máquinas nuevas de diferentes tipos. Existen cuatro sitios disponibles dentro del taller en donde se podría instalar una máquina. Algunos de ellos  son más adecuados que otros para una máquina en particular por su cercanía a los centros de trabajo que tendrían un flujo intenso de trabajo hacia estas máquinas y desde ellas. Por tanto, el objetivo es asignar las nuevas máquinas a los lugares disponibles de manera que se minimice el costo total del manejo de materiales. En la tabla 7.26 se proporciona el costo estimado por unidad de tiempo del manejo de los materiales en cuestión con cada una de las máquinas en los sitios respectivos. El lugar 2 no se considera adecuado para la máquina 2. No habrá flujo de trabajo entre las nuevas máquinas.

Para formular este problema como un problema de asignación debe introducirse una máquina ficticia para el lugar adicional. Además debe asignarse un costo muy grande M a la asignación de la máquina 2 en el lugar 2 para evitarla en la solución óptima. En la tabla 7.27 se muestra la tabla de costos del problema de asignación que resulta. Esta tabla de costos contiene todos los datos necesarios para resolver el problema. La solución óptima es asignar la máquina 1 al lugar 4, la máquina 2 al lugar 3 y la máquina 3 al lugar 1 con un costo total de 29. La máquina ficticia se asigna al lugar 2, con lo que esta localidad queda disponible para alguna asignación real futura. 

Se formulará el modelo matemático para el problema general de asignación y después se analizará cómo se obtiene esta solución.

domingo, 6 de julio de 2014

Problema de asignación

El problema de asignación consiste en un tipo especial de problema de programación lineal en el que los recursos se asignan a las actividades sobre una base de uno-a-uno. Entonces, cada recurso o asignado (por ejemplo, un empleado, máquina o intervalo de tiempo) debe asignarse a una actividad en particular asignación (por ejemplo, una tarea, lugar o evento. Existe un costo cij asociado con el asignado i (i= 1,2,......,n) que realiza la asignación j (j = 1,2, ...., n), de manera que el objetivo es determinar cómo deben hacerse las asignaciones con el fin de minimizar los costos totales.

sábado, 5 de julio de 2014

Características generales

Este ejemplo prototipo ilustra todas las características generales del problema del trasbordo y sus relaciones con el problema del transporte. El problema del trasbordo se puede describir en términos generales  como aquél que se ocupa de asignar y encontrar la ruda para las unidades (cargas de chícharos enlatados en el ejemplo) desde los centros de suministro (enlatadores) hacia  los centros de recepción (almacenes) pasando por los puntos de trasbordo (conexiones, otros centros de suministro y otros centros de recepción). Además de las unidades que se mandan (trasbordan) cada centro de suministro genera un superávit neto dado de unidades que deben distribuirse, y cada centro de recepción absorbe un déficit neto dado, mientas que las conexiones ni generan ni absorben unidades. (El problema tiene soluciones factibles sólo si el superávit neto total generado en los centros de suministro es igual al déficit neto total absorbido por los centros de recepción.)

Un embarque directo puede ser imposible (cij = M) para algunos pares de localidades. Además, puede ser que algunos centros de suministro y algunos de recepción no puedan actuar como putos de trasbordo. En la reformulación del problema de trasbordo como un problema de transporte, la forma más sencilla de manejar este tipo de centros es quitar su columna (si es un centro de suministro) o su renglón (si se trata de un centro de recepción) en la tabla de costos  y requerimientos, y no agregar nada a sus cantidades originales de demanda o de recursos.

Se incurre en un costo positivo cij por cada unidad que se manda directamente de una localidad i (centro de suministro, conexión o centro de recepción) a otra localidad j. El objetivo es determinar  el plan de asignación y encontrar las rutas que  minimizan el costo total.

El modelo matemático que resulta para el problema del trasbordo (véase el problema 27) tiene una estructura especial un poco distinta a la del problema del transporte. Igual que en este caso, se ha encontrado que algunas aplicaciones que no tienen nada que ver con transporte se pueden ajustar a esta estructura especial. De cualquier manera, independientemente  del contexto de la aplicación, este modelo siempre se puede reformular como uno equivalente al problema del transporte en la forma en que se ilustró con el ejemplo prototipo.


viernes, 4 de julio de 2014

Ejemplo Prototipo (III)

Para completar la reformulación de este problema de trasbordo es necesario explicar cómo obtener las cantidades de demanda y de recursos de la tabla 7.25. El número de cargas trasferidas en cualquier localidad se debe incluir tanto en su demanda cuando actúa como destino, como en los recursos con que cuenta si es un origen. Como este número no se conoce de antemanno, se puede simplemente agregar una cota superior segura en ambos, demanda y recursos de esa localidad y después introducir la misma variable de holgura en sus restricciones de recursos y demandas, para que se le asigne el exceso. ( De esta manera, la variable de holgura juega los dos papeles, el de un origen ficticio y el de un destino ficticio.) Como nunca sería conveniente regresar una carga para hacer un trasbordo, más de una vez en la misma localidad, la cota superior segura para este número en cualquier localidad es el número total de cargas (300), por lo que se usará 300 como cota superior. La variable de holgura para las dos restricciones de la localidad i sería xii número (ficticio) de cargas que se mandan de la localidad i a sí misma. Entonces, (300 -xii) es el número real de cargas que hicieron un trasbordo en la localidad i.

Sumando 300 a cada cantidad de asignación y demanda en la tabla 7.24 (en donde los espacios en blanco son ceros) se obtiene la tabla completa de costos y requerimientos que se muestran en la tabla 7.25 para la formulación del problema de trasbordo. Entonces, al aplicar el método símplex de transporte para obtener una solución óptima para este problema se obtiene el plan de embarque óptimo (xii se ignoran) para la P & T Co.

jueves, 3 de julio de 2014

Ejemplo Prototipo (II)

Esta posibilidad es sólo una de muchas formas indirectas en que puede mandarse una carga de la enlatadora 1 al almacén  4 y que deben tomarse en cuenta sien realidad esta enlatadora debe mandar algo a este almacén. El problema global es determinar cómo debe mandarse la producción de todas las enlatadoras para cumplir con las demandas de todos los almacenes y minimizar el costo total de embarque.

Se verá ahora cómo se puede reformular este problema de trasbordo como un problema  de transporte. La idea básica consiste  en interpretar los viajes individuales (en lugar de las jornadas  completas de los embarques) como si se tratara del transporte de un origen a un destino, y así, pensar en que todas las localidades (enlatadoras, conexiones y almacenes) son ejemplo anterior en donde un camión con chícharos se manda la enlatadora 1 al almacén  4  transbordando en la conexión  2 y después en el almacén 2. El primer viaje  de este embarque tiene la enlatadora 1 como origen  y la conexión 2 como destino,  pero después  la conexión 2 se convierte en origen para el segundo viaje, con el almacén 2 como su destino. Por último, el almacén 2 se convierte en el origen del tercer viaje de este mismo embarque y el almacén 4 es cualquiera de las 12 localidades se pueden convertir en origen, destino o ambas, para los viajes de los camiones.



miércoles, 2 de julio de 2014

Ejemplo Prototipo (III)

Entonces, para la reformulación como un problema de transporte, se cuenta con 12 orígenes y 12 destinos. Los costos unitarios cij para la tabla cij para la tabla de costos y requerimientos  que resulta se dan en la tabla  7.25 y son justo  los costos de transporte por camión que se dieron en la tabla 7.24. A los embarques imposibles marcados con un guión en la tabla 7.24 se les asignará un costo muy grande  M. Como cada localidad es tanto un origen como un destino, los elementos de la diagonal en la tabla de costos y requerimientos representan el costo unitario de un embarque  de una localidad dada hacia sí misma. El costo de estos embarques ficticios que no van a ningún lado son cero.


martes, 1 de julio de 2014

Ejemplo Prototipo (I)

Después de una mayor investigación, la P & T COMPANY (Sec. 7.1) encontró  que puede disminuir los costos de transporte de sus chícharos enlatados si elimina su propia operación de distribución y usa servicios comerciales de distribución. Como ninguna compañia da servicio a toda el área  completa de las enlatadoras y los almacenes, será necesario transferir muchos de los embarques a otro camión, por lo menos una vez en el camino. Estas transferencias se pueden llevar a cabo en alguna de las enlatadoras o almacenes  intermedios, o en otras cinco localidades. (Butte, Montana; Boise, Idaho; Cheyene, Wyoming; Denver, Colorado y Omaha, Nebraska) conocidas como conexiones. En la figura 7.2 se muestran los orígenes, los destinos y las conexiones. En la tabla 7.24 se dan los costos de transporte de carga entre cada uno de estos puntos; los guiones indican que el transporte directo no es posible.

Por ejemplo, se puede mandar una carga de chícharos de la enlatadora 1 directamente al almacén 4 a un costo de $871. Otra posibilidad es mandar la carga de la enlatadora 1 a la conexión 2 y después transferirla para que llegue al almacén 4, a un costo de sólo ($286 + $207 + $341) = $834



Problema de trasbordo (II)

Por supuesto, se pueden investigar estas posibilidades de antemano para determinar la ruta más barata de cada origen a cada destino. Sin embargo, si existen muchos puntos de transfarencia intermedios, esta puede resultar una tarea en extremo compolicado tardada. Entonces puede ser mucho mejor dejar que un algoritmo de computadoras obtenga al mismo tiempo las cantidades que han de mandarse de cada origen  a cada destino y la ruta a seguir con cada embarque, con el objeto de minimizar los costos totales de transporte.
Esta extensión al problema de transporte incluye las decisiones sobre las rutas y se conoce como el problema de trasbordo.

Por fortuna existe una manera muy sencilla de reformular el problema de trasbordo para que se ajuste al formato del problema de transporte. TAmbién se puede usar el método simplex de transporte para resolver el problema de trasbordo.

Para aclarar la estructura del problema de trasbordo y la naturaleza de la reformulación se extenderá el ejemplo prototipo del problema de transporte para incluir trasbordos.