5. EVIDENCIAS DE ACTIVIDADES DE APRENDIZAJE

5.1. Actividades de aprendizaje asistido por el profesor

PROGRAMACIN LINEAL.Es una parte de la investigacin operativa que la podremos aplicar cuando el problema que tratamos se puede traducir a expresiones matemticas de tipo lineal y que las limitaciones o restricciones que tenga el sistema productivo se pueda tambin traducir en expresiones matemticas de tipo lineal. Su empleo es frecuente en aplicaciones de la industria, la economa, la estrategia militar, etc. Un problema de programacin lineal tendr la siguiente forma:Funcin Objetivo: Es una expresin matemtica lineal que representa el objetivo del problema. Es la expresin que tendremos que maximizar o minimizar.Funcin Objetivo:(Max. Min.) Z = c1x1 + c2x2 + + cnxnEcuaciones o Inecuaciones de Restriccin: Expresiones matemticas, ecuaciones o inecuaciones de tipo lineal que representan las limitaciones del problema.a11x1 + a12x2 + + a1nxn b1a21x1 + a22x2 + + a2nxn >= b2a31x1 + a32x2 + + a3nxn b3am1x1 + am2x2 + + amnxn = bmAunque el problema no lo diga llevara las restricciones:x1; x2; xn >= 0Las variables no tomaran valores negativos.Conceptos propios de la programacin Lineal:Solucin Posible: Es cualquier conjunto de valores de la variable que satisface el sistema de ecuaciones de la restriccin.Solucin Posible Bsica: Es aquella solucin posible en la que ninguna variable toma valores negativos.Solucin Bsica Posible Degenerada: Solucin bsica posible en la que al menos una variable toma el valor cero.Solucin ptima: Es aquella solucin bsica posible que optimiza a la funcin objetivo.

EJEMPLO DEL MTODO GRFICO

Una compaa de auditores se especializa en preparar liquidaciones y auditoras de empresas pequeas. Tienen inters en saber cuntas auditoras y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisin. Una auditora en promedio requiere de 40 horas de trabajo directo y 10 horas de revisin, adems aporta un ingreso de 300 dls. Una liquidacin de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisin, produce un ingreso de 100 dls. El mximo de liquidaciones mensuales disponibles es de 60.OBJETIVO : Maximizar el ingreso total.VARIABLE DE DECISION: Cantidad de auditoras (X1).Cantidad de liquidaciones (X2).RESTRICCIONES : Tiempo disponible de trabajo directoTiempo disponible de revisinNmero mximo de liquidaciones.Maximizar Sujeto a:

La solucin ptima siempre se encuentra en uno de los vrtices del conjunto de soluciones factibles. Se analizan estos valores en la funcin objetivo. El vrtice que representa el mejor valor de la funcin objetivo ser la solucin ptima.

VARIABLES DE HOLGURA Y VARIABLES DE EXCEDENTE

PROBLEMAS NO ACOTADOSHay que distinguir el trmino problema no acotado con el trmino conjunto factible no acotado, ste ltimo se refiere a una regin factible en la que al menos una de las variables de decisin puede asumir valores indefinidamente grandes. Si un programa lineal es no acotado, el conjunto factible tambin debe ser no acotado. Sin embargo, es posible tener un conjunto factible no acotado sin que el problema sea no acotadoMax z= 5000A + 4000BS.A.A+B >=5A-3B=135A , B >=0

Planteamiento del problema

Cuando la regin factible no est acotada la nica solucin que podemos obtener es un mnimo.

- Construimos una tabla con los datos del enunciado

Regin factible no acotada

Mayorista AMayorista BDisponible

Naranjas8216

Pltanos115

Manzanas2720

Distancia150300

- Expresamos con ecuaciones e inecuaciones lineales la informacin descrita

- Representamos las restricciones y calculamos los puntos de la regin factible

PROBLEMAS NO FACTIBLES.Son problemas que tiene un conjunto factible vaco: es decir no existe combinacin de valores para las variables de decisin que satisfaga simultneamente todas las restriccionesEL MTODO SIMPLEX

El Mtodo Simplex es un mtodo iterativo que permite ir mejorando la solucin en cada paso. La razn matemtica de esta mejora radica en que el mtodo consiste en caminar del vrtice de un poliedro a un vrtice vecino de manera que aumente o disminuya (segn el contexto de la funcin objetivo, sea maximizar o minimizar), dado que el nmero de vrtices que presenta un poliedro solucin es finito siempre se hallar solucin. El algoritmo Simplex requiere que el Modelo Lineal, para ser solucionado, cumpla las condiciones de Forma Estndar y Sistema Cannico. La Forma Estndar: Incluye a) Una Funcin Objetivo a optimizar b) Lado derecho de las restricciones con valor positivo c) Variables de decisin no negativas d) Las restricciones deben ser expresadas como igualdades. Para transformar las restricciones en igualdades se deben incorporar las llamadas variables de holgura. Una variable de holgura tiene coeficiente cero en la Funcin Objetivo. Se suman en restricciones del Tipo .En trminos matemticos, expresan la diferencia entre el lado izquierdo y el lado derecho de las restricciones. Al igual que las variables de decisin deben ser mayores o iguales a cero. En trminos del modelo representan la cantidad de recurso no utilizado con relacin a un mximo disponible (Parte ociosa de los recursosEl Sistema Cannico En un Modelo Lineal significa que debe existir una variable bsica en cada restriccin. Esto permite obtener una primera solucin posible que satisface todas las restricciones. Una variable bsica tiene coeficiente 1 positivo en una restriccin y no existe en las dems. Las variables de decisin (estructurales) del modelo y las variables de holgura pueden ser variables bsicas. Cuando ninguna de ellas cumple con la condicin de ser bsica, se incorpora una variable como artificio matemtico, para cumplir con el sistema cannico y a esa variable se le llama variable artificial. Una variable artificial debe tener incorporado un coeficiente muy alto en la Funcin Objetivo, con signo negativo en maximizacin y con signo positivo en minimizacin. Con esto se logra que el procedimiento Simplex las elimine de la solucin en las primeras iteraciones. Estas variables deben valer cero en la solucin ptima del modelo. Una Tabla Simplex es un resumen detallado de toda la informacin del modelo para trabajar ms fcilmente con l. La siguiente tabla expresa cmo deben ser recogidos los datos para resolver el problema de programacin lineal por el Mtodo Simplex. Modelo de Tabla Simplex Interrelacin V.B. Ec. # Coeficientes L.D. Razn

PROCEDIMIENTO PARA LA RESOLUCIN DE PROBLEMAS MEDIANTE POR EL MTODO SIMPLEX. FASE I: Preparar el modelo inicial para construir la tabla: 1) Transformar los trminos independientes en positivos (multiplicando por -1). 2) Si en alguna restriccin, hay un solo proceso que est contenida en ella sola, lo convertiremos en unitario (dividiendo por su coeficiente) y si no lo hago meter una variable de holgura. 3) En las inecuaciones en las que encontramos introducimos una variable de holgura sumando. 4) En toda restriccin debe haber una variable unitaria positiva. 5) Las variables de holgura, a la hora de introducirlas en la funcin objetivo lo haremos siempre con coeficiente cero.6) Igualar a cero la funcin objetivo

Construir la tabla y resolver el algoritmo.

Paso 1: Construir la tabla del mtodo Simplex y rellenamos la tabla con los coeficientes. Comprobamos que las variables bsicas tienen un coeficiente de 1 en la interseccin de su rengln y columna correspondiente y cero en los dems renglones incluido la funcin objetivo

Paso 2: La S.B.F. es ptima, si y slo si todos los coeficientes del rengln (Z) son no negativos. De lo contrario se debe iterar. En

Paso 3: Si comprobamos que hay coeficientes negativos en el rengln (Z), marcamos el mayor en valor absoluto y esta ser la variable no bsica que entra a la base. Para determinar la variable bsica que sale de la base, divida cada elemento del lado derecho para cada elemento del vector entrante debe ser mayor que cero (POSITIVO) c) Se identifica el rengln con la menor razn La variable bsica para este rengln es la que sale y se le da el nombre de rengln pivote. La interseccin entre la columna pivote y el rengln pivote lo denominamos nmero pivote. El patrn de coeficientes en la columna de la variable que entra en la base, debe quedar como actualmente est el patrn de coeficientes de la variable que sale.

Paso 4: Calculamos los nuevos coeficientes de la matriz: a) Coeficientes del rengln de la variable que entra: Dividimos el rengln pivote entre el nmero pivote y el resultado sern los coeficientes del nuevo rengln de la variable que entra. b) Coeficientes de los dems renglones : Dividimos el nuevo rengln de la variable que entra por menos el coeficiente del de la variable que entra en el rengln que estamos calculando y al resultado, le sumamos el rengln que tenamos inicialmente

Paso 5: Construimos la tabla con los resultados.

Paso 6: En la nueva matriz, comprobamos los coeficientes del rengln Z, si todava existen coeficientes negativos, se sigue iterando, de lo contrario hemos terminado y hallamos la solucin ptima.

Existen problemas de programacin lineal que no proporcionan una solucin bsica inicial. Esta situacin se presenta cuando al menos una de las restricciones es del tipo (=) o (=). Estas variables se denominan variables artificiales y su adicin hace que las restricciones correspondientes.

Esta dificultad se elimina asegurando que las variables sean 0 en la solucin final. Esto se logra asignando una penalizacin muy grande por unidad a estas variables en la funcin objetivo. Tal penalizacin se designar como M para problemas de maximizacin y +M para problemas de minimizacin.3. Utiliza las variables artificiales en la solucin bsica inicial; sin embargo la funcin objetivo de la tabla inicial se prepara adecuadamente para expresarse en trminos de las variables no bsicas nicamente. Esto significa que los coeficientes de las variables artificiales en la funcin objetivo deben ser 0 un resultado que puede lograrse sumando mltiplos adecuados de las ecuaciones de restriccin al rengln objetivo.4. Proceda con los pasos regulares del mtodo simplex.MINIMIZACIN.Para resolver problemas de minimizacin mediante el algoritmo simplex existen dos procedimientos que se emplean con regularidad. - El primero, que a mi juicio es el ms recomendable se basa en un artificio aplicable al algoritmo fundamentado en la lgica matemtica que dicta que"para cualquier funcin f(x), todo punto que minimice a f(x) maximizar tambin a - f(x)". Por lo tanto el procedimiento a aplicar es multiplicar por el factor negativo (-1) a toda la funcin objetivo.