INVESTIGACION DE OPERACIONES

INTRODUCCION

Cualquier modelo de una situacin es una simplificacin de la situacin real. Por lo tanto, existe cierta incertidumbre en la determinacin de los valores de todos los parmetros involucrados. Debido a ello, es importante estudiar la variabilidad de la solucin del problema planteado de acuerdo a eventuales medicaciones de los valores de los parmetros, o bien, debido a la incorporacin de nuevos elementos a la situacin. ANALISIS DE SENSIBILIDAD

Llamaremos Anlisis de Sensibilidad al estudio de la variacin del ptimo de un LP producto de modificaciones de ciertos parmetros como coeficientes de variables en la funcin objetivo, coeficientes del lado derecho de restricciones, etc. La idea general consiste en determinar rangos de variacin de los parmetros del LP de forma de mantener una cierta base ptima, teniendo en cuenta que una solucin bsica es factible solo si todas las variables basales tienen un valor no negativo. Debido a que el estudio de la variacin simultanea de varios parmetros puede ser difcil, nos centraremos en primer lugar en modificaciones de un parmetro a la vez manteniendo los restantes fijos. Estudiaremos las siguientes posibilidades:

Cambio 1 Cambio del coeficiente en la funcin objetivo de una variable no bsica.

Cambio 2 Cambio del coeficiente en la funcin objetivo de una variable bsica.

Cambio 3 Cambio del coeficiente del lado derecho de una restriccin.

Cambio 4 Incorporacin de una nueva variable.

Cambio 5 Incorporacin de una nueva restriccin.

Adems, se estudiara la variacin simultnea de coeficientes en la funcin objetivo y del lado derechoMediante la regla del 100 %.

Para desarrollar las distintas opciones consideraremos el siguiente ejemplo en su versin estndar:Max z = 60x1 + 30x2 + 20x3s.t.8x1 + 6x2 + x3 + s1 = 48 (a)4x1 + 2x2 + 1, 5x3 + s2 = 20 (b)2x1 + 1,5x2 + 0,5x3 + s3 = 8 (c)

Aplicando el mtodo Simplex obtenemos la tabla del Cuadro 1.1. Luego, la solucin ptima delProblema corresponde a z = 280, s1 = 24, x3 = 8, x1 = 2 y x2 = s2 = s3 = 0.

EL PROBLEMA DEL TRANSPORTE

Una cierta clase de problemas de programacin lineal, conocida como problema de transporte se da muy frecuentemente en aplicaciones prcticas. El problema general de transporte puede ser formulado como sigue: Un producto est disponible en ciertas cantidades conocidas en cada uno de los m orgenes. Es requerido que ciertas cantidades de un producto sean transportadas a cada uno de los n destinos. El mnimo costo de transportar una unidad de cualquier origen a cualquier destino es conocido. Se desea determinar el programa de los envos que minimiza el costo total de transporte.Sea ai la cantidad de producto disponible en el origen i y bj la cantidad de producto requerida en el destino j. El costo de transportar una unidad de origen i al destino j ser escrita como cij Se asumir que la cantidad disponible sea igual a la cantidad producida.

El nmero de celdas asignadas, ser igual a m + n + 1

Todas la celdas no asignadas son iguales a cero, por ejemplo si tenemos una matriz del tamao de 6x4 (m = 6 y n = 4), entonces el nmero de celdas asignadas (valores de xij diferentes de cero) ser m + n - 1 = 9, y las celdas no asignadas (con valores de xij = 0) sern 6(4)-9=15.Mtodos para obtener la primera Solucin Inicial Bsica Como el saso de mtodo Simples, el algoritmo de transporte consiste en empezar con una solucin inicial y moverse de una solucin bsica a otra en un numero de finito de iteraciones. En el mtodo de transporte, sin embargo, la solucin inicial no es solucin factible cero, (Z = 0, todas las variables reales son iguales a cero) si no una de las posibles soluciones.

Mtodo de la esquina Noroeste

La regla de la esquina noroeste muestra cmo obtener una rpida solucin inicial. Esta no toma en consideracin el costo de enviar una unidad de un centro de distribucin a un centro de consumo.

Paso 1.- Se obtiene realizando una asignacin que no considera costos o beneficios. Inicia en la celda superior izquierda (esquina noroeste) de la tabla. De no existir alguna ir al Paso 3, de otra forma ir al Paso 2.

Paso 2.- Asignar a esta celda la cantidad menor entre lo requerido y lo disponible (menor cantidad entre restricciones de esa fila y esa columna). Reste la cantidad asignada de lo disponible en la capacidad y lo requerido (restriccin de la fila y la columna respectivamente), y elimine la fila o la columna que quede a nivel cero en su restriccin, ir a Paso 1. Paso 3.- La solucin inicial factible ha sido obtenida.

MTODO MODIFICADO DE LA ESQUINA NOROESTEEste mtodo requiere una reorientacin de la esquina inicial con la ms ptima asignacin de tal forma que las cantidades disponibles y requeridas se encuentren satisfechas.

1) Empieza analizando las celdas no asignadas 2) Identifica la celda no asignada que tenga el menor costo Cij en la matriz y asigne en ella tanto como sea posible debido a las restricciones con la fila y columna. 3) Reduzca lo asignado del correspondiente requerimiento y disponibilidad, eliminando la columna o fila correspondiente a estas que se haya reducido a cero. 4) Contine con la fila o columna no eliminada y asigne en la celda que tenga menor costo. Si se ha terminado de asignar, ir al paso 2. 5) Repita el paso 2 hasta que lo requerido y lo disponible sea asignado.

MTODO DE APROXIMACIN DE VOGEL Este mtodo es razonablemente bueno para obtener una solucin inicial bsica factible, la cual puede ser ptima o requerir un nmero mnimo de interacciones para obtener la solucin ptima. El mtodo es el siguiente:

1. Inicio con las celdas no asignadas. 2. Clculo en cada fila y en cada columna la diferencia entre los dos costos ms pequeos de las celdas.

3. De entre estas filas y columnas seleccione aquella que tenga la mxima diferencia. 4. Asigne tanto como sea posible en aquella celda que corresponda a la mxima diferencia y que tenga en su fila o columna el menor costo. (La mxima asignacin posible es la cantidad menor entre lo disponible y lo requerido). 5. Reduzca la correspondiente cantidad asignada de la cantidad disponible y de la requerida, y elimine la fila o columna que se haya reducido a cero. Detngase si no existen filas y comuna restantes. De forma contraria regresar al paso 1.

LOCALIZACIONES ARTIFICIALES (CELDAS ARTIFICIALES)

El Mtodo de Transporte requiere que la suma de las capacidades iguales a la de los requerimientos. Si la suma de las capacidades no iguala a la suma de los requerimientos (produccin no iguala a la demanda) una localizacin (celda) artificial puede ser creada para lograr la igualdad. La localizacin artificial tendr asignacin de cero en los valores de la funcin objetivo y ser eliminada si la solucin final indica alguna asignacin en la localizacin artificial. Si lo requerido excede a la capacidad una localizacin artificial puede representar una planta imaginaria. Si la capacidad excede a lo requerido una localizacin artificial puede representar un mercado imaginario. La localizacin artificial es similar a la variable de holgura en el Mtodo Simples.

DEGENERACIN

Si ms de m + n 1 celdas son asignadas, habr ms de un ciclo (camino cerrado) para el anlisis de las celdas en busca de la optimizacin. Todos los posibles caminos deben ser evaluados para determinar la optimalidad de las asignadas realizadas. Si menos de m + n 1 celdas son asignadas, el problema se denomina Degenerado y no todas las celdas vacas (no asignadas) tendr un camino cerrado (ciclo). La condicin de degeneracin puede ocurrir en la solucin inicial o puede iniciarse cuando dos celdas con igual asignacin salen la solucin (es decir una de las dos celdas queda a nivel cero), cuando una transferencia de unidades se realiza a una celda de menor costo. Existen varias formas de manejar la degeneracin. Esta dificultad puede ser eliminada utilizando la letra E, que representa una asignacin infinitesimal asignndola en aquella o aquellas celdas que causaron la degeneracin (celda o celdas que pasan a nivel cero) y con ello se completan las m + n 1 celdas asignadas. Una regla sencilla es la siguiente:

Si una celda asignada dada que pasa a nivel cero no tiene otras asignaciones en la fila o columna a las cuales pertenece, asigne la pequea cantidad E en cualquier celda no asignada en esa fila o en esa columna. Si la condicin anterior no existe, asigne una pequea cantidad E, en cualquier celda no asignada que permita completar la evaluacin de las celdas. Problema de maximizacin Cuando se trate de maximizar utilidad, ganancias, produccin, efectividad, etc. los cij ser negativos (multiplicarlos por -1) y el problema se tratara como uno de minimizacin utilizando de forma normal los mtodos cubiertos. La nica consideracin es la que cuando se haya obtenido la asignacin ptima los cij deben ser nuevamente positivos (tomar sus valores originales). Otra alternativa ser la de determinar el mayor cij y obtener la diferencia entre este valor y cada uno de los cij en la tabla. El problema se resuelve de la forma normal utilizando los mtodos cubiertos y una vez obtenida la asignacin ptima los cij debern tomar sus valores originales.

METODO DE ASIGNACION El mtodo de asignacin es una forma de Programacin Lineal, que asigna eficientemente personas a tareas. Es un mtodo iterativo que garantiza encontrar un programa ptimo de asignacin sin tener que considerar todas las posibles alternativas. Esta tcnica ha estado siendo usada para asignar rdenes a mquinas, personas a proyectos, vendedores a territorios, vehculos a sectores, etc.

El mtodo de asignacin conocido como EL METODO DE HUNGARO requiere una asignacin de uno a uno entre personas y tareas, resultando una matriz cuadrada donde el nmero de personas (filas) es igual al nmero de tareas (columnas). El procedimiento de solucin no permite la posibilidad de asignar una de las personas a ms de una tarea. Si el nmero de las personas no es igual al nmero de las tareas, un agente o tarea de holgura deber ser creada con valor cero, para obtener una matriz cuadrada y esas variables (ficticias) de holgura asignadas son ignoradas en la solucin ptima. Los nmeros en la matriz sern los valores asociados con cada asignacin. Esencialmente est tcnica minimiza los costos de oportunidad de perdida en una manera similar como el mximo arrepentimiento es de minimizado en toma de decisiones bajo incertidumbre.

Todos los problemas de asignacin pueden ser formulados y resueltos como problemas de programacin lineal por el mtodo simples. Sin embargo el mtodo de asignacin es computacionalmente ms eficiente.

Ejemplo: Una compaa de limpieza desea determinar cmo asignar a sus empleados a diferentes centros de trabajo para realizar actividades de limpieza, de tal forma que la efectividad total del desempeo de sus actividades en el centro de trabajo sean mximos. A continuacin se proporciona la matriz de efectividad del desempeo de cada uno de los empleados si fueran asignados a los diferentes centros de trabajo.

Cuatro empleados sern asignados a 5 centros de trabajo. El nivel mximo posible de desempeo es de 40. Debido a que la matriz no es cuadrada, un empleado artificial ser aadido.

El objetivo es el que de maximizar el desempeo total en los centros de trabajo, debido a que es un problema de maximizacin, reste de todas las entradas de las celdas en la matriz la mxima entrada de celda (esta operacin convierte la matriz de ganancias en una matriz de costos.) La mxima entrada de celda es 40, la matriz modificada se muestra a continuacin:

Los costos de oportunidad para cada columna son obtenidos restando la entrada de costo ms baja en cada columna de los otros costos en la misma columna. El resultado se muestra a continuacin:

Los costos de oportunidad para cada fila son obtenidos restando la entrada de costo ms baja en cada fila de los otros costos en la misma fila. Todo esto es con el fin de generar a menos un cero por cada fila y por cada columna. El resultado se muestra a continuacin:

Debido a que existen 5 filas y estas pueden cubrir todas las celdas con entradas cero (con el menor nmero de lneas), una asignacin ptima se ha logrado). El paso final requiere que las filas y columnas con nicamente un cero son exploradas para determinar las asignaciones. Las filas 2 y 5 tiene celda nica con entrada cero, y las columnas 2, 4 y 5 tienen celda nica con entrada cero, por lo que la persona 2 ser asignada al centro de trabajo 3, la persona 5 ficticia ser asignada al centro de trabajo 1 (lo que indica que ninguna persona es asignada al centro de trabajo 1), la persona 4 ser asignada al centro de trabajo 2, la persona 3 ser asignada al centro de trabajo 4 y la persona 1 ser asignada al centro de trabajo 1. La asignacin ptima es la siguiente: