PROGRAMACION LINEAL

PROGRAMACION LINEAL

PROGRAMACIN LINEAL.

DEFINICIN, DESARROLLO Y TIPOS DE MODELOS DE INVESTIGACIN DE OPERACIONES. La Investigacin de Operaciones aspira a determinar el mejor curso de accin, o curso ptimo, de un problema de decisin con la restriccin de recursos limitados. Como tcnica para la resolucin de problemas, investigacin de operaciones debe visualizarse como una ciencia y como un arte. Como Ciencia radica en ofrecer tcnicas y algoritmos matemticos para resolver problemas de decisin adecuada.Como Arte debido al xito que se alcanza en todas las fases anteriores y posteriores a la solucin de un modelo matemtico, depende de la forma apreciable de la creatividad y la habilidad personal de los analistas encargados de tomar las decisiones.En un equipo de Investigacin de Operaciones es importante la habilidad adecuada en los aspectos cientficos y artsticos de Investigacin de Operaciones. Si se destaca un aspecto y no el otro probablemente se impedir la utilizacin efectiva de la Investigacin de Operaciones en la prctica.La Investigacin de Operaciones en la Ingeniera de Sistemas se emplea principalmente en los aspectos de coordinacin de operaciones y actividades de la organizacin o sistema que se analice, mediante el empleo de modelos que describan las interacciones entre los componentes del sistema y de ste con este con su medio ambiente.En la Investigacin de Operaciones la parte de Investigacin se refiere a que aqu se usa un enfoque similar a la manera en la que se lleva a cabo la investigacin en los campos cientficos establecidos.La parte de Operaciones es porque en ella se resuelven problemas que se refieren a la conduccin de operaciones dentro de una organizacinLa investigacin de operaciones es la aplicacin, por grupos interdisciplinarios, del mtodo cientfico a problemas relacionados con el control de las organizaciones o sistemas (hombre-mquina) a fin de que se produzca soluciones que mejor sirvan a los objetivos de toda organizacin. Churchman, Ackoff y Arnoff.

Definicin de Modelos.Un modelo de decisin debe considerarse como un vehculo para resumir un problema de decisin en forma tal que haga posible la identificacin y evaluacin sistemtica de todas las alternativas de decisin del problema. Despus se llega a una decisin seleccionando la alternativa que se juzgue sea la mejor entre todas las opciones disponibles.

Un modelo es una abstraccin selectiva de la realidad.El modelo se define como una funcin objetivo y restricciones que se expresan en trminos de las variables (alternativas) de decisin del problema. Una solucin a un modelo, no obstante, de ser exacta, no ser til a menos que el modelo mismo ofrezca una representacin adecuada de la situacin de decisin verdadera. El modelo de decisin debe contener tres elementos: Alternativas de decisin, de las cuales se hace una seleccin. Restricciones, para excluir alternativas infactibles. Criterios para evaluar y clasificar alternativas factibles.

Tipos de Modelos de Investigacin de Operaciones.Modelo Matemtico: Se emplea cuando la funcin objetivo y las restricciones del modelo se pueden expresar en forma cuantitativa o matemtica como funciones de las variables de decisin.Modelo de Simulacin: Los modelos de simulacin difieren de los matemticos en que las relaciones entre la entrada y la salida no se indican en forma explcita. En cambio, un modelo de simulacin divide el sistema representado en mdulos bsicos o elementales que despus se enlazan entre si va relaciones lgicas bien definidas. Por lo tanto, las operaciones de clculos pasaran de un mdulo a otro hasta que se obtenga un resultado de salida.Los modelos de simulacin cuando se comparan con modelos matemticos; ofrecen mayor flexibilidad al representar sistemas complejos, pero esta flexibilidad no est libre de inconvenientes. La elaboracin de este modelo suele ser costoso en tiempo y recursos. Por otra parte, los modelos matemticos ptimos suelen poder manejarse en trminos de clculos.Modelos de Investigacin de Operaciones de la ciencia de la administracin: Los cientficos de la administracin trabajan con modelos cuantitativos de decisiones.Modelos Formales: Se usan para resolver problemas cuantitativos de decisin en el mundo real. Algunos modelos en la ciencia de la administracin son llamados modelos determinsticos. Esto significa que todos los datos relevantes (es decir, los datos que los modelos utilizarn o evaluarn) se dan por conocidos. En los modelos probabilsticos (o estocsticos), alguno de los datos importantes se consideran inciertos, aunque debe especificarse la probabilidad de tales datos

Modelo de Hoja de Clculo Electrnica: La hoja de clculo electrnica facilita hacer y contestar preguntas de que si en un problema real. Hasta ese grado la hoja de clculo electrnica tiene una representacin selectiva del problema y desde este punto de vista la hoja de clculo electrnica es un modelo.

FORMULACIN DE UN MODELO.Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste en reformularlo de manera conveniente para su anlisis. La forma convencional en que la investigacin de operaciones realiza esto es construyendo un modelo matemtico que represente la esencia del problema. El modelo matemtico puede expresarse entonces como el problema de elegir los valores de las variables de decisin de manera que se maximice la funcin objetivo, sujeta a las restricciones dadas. Un modelo de este tipo, y algunas variaciones menores sobre l, tipifican los modelos analizados en investigacin de operaciones.Un paso crucial en la formulacin de un modelo de Investigacin de Operaciones es la construccin de la funcin objetivo. Esto requiere desarrollar una medida cuantitativa de la efectividad relativa a cada objetivo del tomador de decisiones identificado cuando se estaba definiendo el problema. Si en el estudio se contemplan ms de un objetivo, es necesario transformar y combinar las medidas respectivas en una medida compuesta de efectividad llamada medida global de efectividad. A veces esta medida compuesta puede ser algo tangible (por ejemplo, ganancias) y corresponder a una meta ms alta de la organizacin, o puede ser abstracta (como utilidad). En este ltimo caso la tarea para desarrollar esta medida puede ser compleja y requerir una comparacin cuidadosa de los objetivos y su importancia relativa.

MTODO DE SOLUCIN GRFICO La PL es una tcnica mediante la cual se toman decisiones, reduciendo el problema bajo estudio a un modelo matemtico general, el cual debe ser resuelto por mtodos cuantitativos.En desarrollo de este captulo se aplicarn la solucin de dichos modelos aplicando diversas tcnicas como: el mtodo grfico, mtodo simplex, mtodo matricial, tcnica de la gran M.Adems se desarrollara la aplicacin de variables artificiales y obtencin de soluciones para identificar a qu tipo de clasificacin pertenecen. Por medio de dichos modelos de solucin se podr obtener la solucin adecuada para cada problema y facilitar la toma de decisiones. MTODO GRFICO. El mtodo grfico se utiliza para la solucin de problemas de PL, representando geomtricamente a las restricciones, condiciones tcnicas y el objetivo.El modelo se puede resolver en forma grfica si slo tiene dos variables. Para modelos con tres o ms variables, el mtodo grfico es imprctico o imposible.Cuando los ejes son relacionados con las variables del problema, el mtodo es llamado mtodo grfico en actividad. Cuando se relacionan las restricciones tecnolgicas se denomina mtodo grfico en recursos.Los pasos necesarios para realizar el mtodo son nueve: 1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultnea. 2. Las restricciones de no negatividad Xi>= 0 confan todos los valores posibles. 3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer trmino = 0). Si es as, el proceso termina; de otra manera se lleva a cabo otra interaccin para obtener la nueva solucin bsica factible inicial. 3. Condicin de factibilidad.- Para todos los problemas de maximizacin y minimizacin, variable que sale es la variable bsica que tiene la razn ms pequea (positiva). Una coincidencia se anula arbitrariamente. 4. Seleccionar las variables de holgura como las variables bsicas de inicio. 5. Selecciona una variable que entra de entre las variables no bsicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la funcin objetivo. Si no existe la solucin bsica es la ptima, si existe pasar al paso siguiente. 6. Realizar el paso iterativo. a) Se determina la variable bsica entrante mediante la eleccin de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuacin. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote. b) Se determina la variable bsica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada rengln entre estos coeficientes, se identifica la ecuacin con el menor cociente y se selecciona la variable bsica para esta ecuacin. c) Se determina la nueva solucin bsica factible construyendo una nueva tabla en la forma apropiada de eliminacin de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable bsica en el rengln pivote a 1, se divide todo el rengln entre el nmero pivote, entonces rengln pivote nuevo = rengln pivote antiguo nmero pivote para completar la primera iteracin es necesario seguir usando la eliminacin de Gauss para obtener coeficientes de 0 para la nueva variable bsica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente frmula: rengln nuevo = rengln antiguo - ( coeficiente de la columna pivote X rengln pivote nuevo) cuando el coeficiente es negativo se utiliza la frmula: rengln nuevo = rengln antiguo + (coeficiente de la columna pivote X rengln pivote nuevo)

FORMA CANONICA Y FORMA ESTANDAR Un problema de programacin lineal puede ser establecido en diferentes formas equivalentes a travs de manipulaciones apropiadas. Dos formas en particular sern de bastante utilidad. Estas son las formas Estndar y Cannica. Un problema lineal se dice que est en la forma estndar s ; a) Todas las restricciones son igualdades b) Todas las variables son no-negativas c) Las limitaciones (lado derecho de la restriccin) son positivas. El Mtodo Simplex, est diseado para ser aplicado nicamente hasta que el problema se encuentre en la forma Estndar. La forma Cannica es tambin de bastante utilidad, especialmente en explorar la relacin de Dualidad. Un problema de P.L. est en la forma cannica si para un problema de: Maximizacin, las variables son no-negativas y las restricciones son del tipo Minimizacin, las variables son no-negativas y las restricciones son del tipo

MTODO DE LAS VARIABLES ARTIFICIALES. Mtodo de la gran M o mtodo penal. El mtodo de la gran M es empleado para resolver modelos de programacin lineal; cuando en sus r estricciones al menos una de ellas el signo de la desigualdad es diferente ; es decir, las restricciones son del tipo o =; el algoritmo matemtico para resolver este tipo de modelos obedece a los siguientes pasos:1.- Se expresa en problema en la forma estndar.2.- Se aaden las Variables no negativas en cada una de las ecuaciones, cuyas restricciones originales tengan () o (=). Esas variables artificiales y su presencia es una violacin a las leyes del lgebra. Esta dificultad se supera asegurando que esas variables artificiales sean ceros (0) en la solucin final.3.- Utilizar las variables artificiales para la solucin bsica inicial, para ello la funcin objetivo deber ser ajustada adecuadamente.Proceda con los pasos regulares del Mtodo Simplex.Nota: Las variables artificiales proporcionan un artificio matemtico para obtener la solucin inicial. Son variables ficticias y no tienen ningn significado fsico directo en trminos del problema original.

Las variables artificiales se reconocern por la variable Wn.Ejemplo 1:

PASO1: Pasar a formato estndar y aadir variables artificiales en las restricciones y que estas sean Formato estndar.

PASO 2: Se aade en la funcin objetivo el coeficiente M contrario a su espritu de dicha funcin por cada variable artificial contenida en las restricciones y se iguala a cero la funcin objetivo.

PASO 3: Armar el Tabln en la base siempre que la desigualdad sea de signo ( o =), la variable a contemplar ser la artificial y en las desigualdades ser siempre en la base de las variables de holgura.

NOTA 1: Se forma la Matriz identidad con las variables artificiales acompaadas con las de holgura, intercambiando las columnas o filas en el siguiente orden X1, X2, S1, W1, S2, W.

PASO 4: Hacer el ajuste. Eliminar las M de la zona , para ello cada variable artificial se multiplica por el mismo coeficiente con signo opuesto y se suman las variables artifciales y la cantidad ser adicionada en la funcin objetivo zona , esto es par a Maximizar y Minimizar. El ajuste solo se lleva a cabo en la funcin objetivo.

PASO 5: Se sigue o aplica el mtodo simplex y los criterios de factibilidad, segn sea el caso para maximizar o minimizar el coeficiente M no tiene valor

7M 4M por lo tanto 7M es la variable ms positiva y entra X1. Toda la fila del rengln W1 se multiplica por 1/3 para obtener 1 y tiene que ser el eje pivote.

En caso de la Funcin Objetivo se sigue toda la fila, se multiplica por 4-7M; checar operaciones

NOTA: Arriba y abajo del eje pivote ceros, hay que multiplicarlo por cada uno de los nmeros que se encuentran en la columna con signo opuesto al eje pivote y sumarlo en la respectiva fila.

MTODO DE LA DOBLE FASE.El procedimiento de la doble fase es similar al Mtodo de la M en sus pasos 1 y 2, solo que en su paso 4 se sustituye la funcin (F.O), por una funcin que ser la de objetivo de estudio, la cual se obtiene a partir de la suma de tantas variables artificiales como sean necesarias agregar en la forma estndar.

Paso 1: Formato Estndar.

Paso 2: Despejar las variables artificiales de cada r estriccin: siempre se tomara en cuenta los signos o = y se suman todas las variables artificiales, tomando una nueva funcin objetivo.

Se iguala la funcin objetivo a la constante obtenida de la suma de cada una de ellas, en este caso a 12.

Fase 2: Lleva de la funcin objetivo a a la funcin objetivo inicial Z

Despejar cada una de las ecuaciones de la base obtenidas en la Fase I con la variable respectiva.

Sustituimos los valores X1, X2 en la funcin objetivo Z, la funcin original.

Se iguala a 12/5

Armar nuevamente el tabln sin las variables artificiales.

La tabla es ptima porque se tienen 0 y negativos en la zona

BIBLIOGRAFIA

*TECNOLGICO DE ESTUDIOS SUPERIORES DEL ORIENTE DEL ESTADO DE MXICOING. OSCAR EDUARDO PREZ GAON*Juan Prawda WitenbergMtodos y modelos de investigacin de operaciones LIMUSA*Investigacin de operaciones: aplicaciones y algoritmos Wayne L. WinstonMC. GRAW-HILLINVESTIGACION DE OPERACIONES.CARLOS ADRIEL ALVARO TOSCA