Diapositiva 1

UNIDAD IIIPROGRAMACIN MATEMTICADiapositivas Unidad IIIM.A. Erika Straffon Del Castillo

Ejemplo 1Programacin lineal

Una empresa fabrica dos productos, A y B. Cada uno requiere tiempo en dos mquinas. La primera mquina tiene 24 horas disponibles y la segunda tiene 16. Cada unidad del producto A requiere dos horas en ambas mquinas y cada unidad del producto necesita tres horas en la primera mquina y una en la segunda. Los beneficios son seis dlares por unidad de A y de siete dlares por unidad de B, la empresa puede vender todas las unidades que fabrique de ambos productos.

Suponga que el objetivo es maximizar el beneficio; cuntas unidades de los productos A y B debe producir?

Formulacin:

X1 = Nmero de unidades del producto A que se fabricarn.X2 = Nmero de unidades del producto B que se fabricarnP = Beneficio total para la empresa.

Maximizar: P = 6 X1 + 7 X2

Sujeto a: 2 X1 + 3 X2 24 2 X1 + X2 16 X1 + X2 0

La figura anterior muestra las dos ecuaciones de restriccin. La ecuacin 2 X1 + 3 X2 24 es la restriccin que impone la limitacin de horas disponibles (24) en la primera mquina, y todos los puntos situados a la izquierda y debajo de la lnea son combinaciones posibles (factibles) de X1 y X2 . Anlogamente; 2 X1 + X2 16 es la restriccin que se relaciona con la segunda mquina, y todos los puntos situados abajo y ala izquierda son factibles. Tambin estn las restricciones X1 + X2 0, ya quela produccin no puede ser negativa.

Considera el punto F dentro de la regin sombreada, la cual comprende la produccin de cinco unidades del producto A y cuatro unidades del producto B. Para ello se requieren 2 * 5 + 3 * 4 = 22 horas en la primera mquina. Esta cifra es menor que las 24 horas disponibles y por lo tanto cumple con la restriccin de la primera mquina. As mismo, se requieren 2 * 5 + 1 * 4 = 14 horas en la segunda mquina, tambin menor que el lmite de 16 horas disponibles.El vrtice especfico que ser la solucin depender de la pendiente de la funcin de beneficio, es decir, de la rentabilidad relativa de los productos A y B.Ejemplo 2Mtodo simplex

Se retomar la informacin del ejemplo 1 de la Unidad 1 (Caso Reddy Mikks) para poder explicar el mtodo simplex.Se considerar la siguiente forma estndar:

Maximizar z: 3XE + 2X1 + 0s1 + 0s1 + 0s2 + 0s3 + 0s4

Sujeto a: XE + 2XI + S1 = 6 2XE + XI + S2 = 8 - XE + XI + S3 = 1 XI + S4= 2 XE , XI , S1, S2, S3, S4 0

El modelo tiene m = 4 ecuaciones y n = 6 variables.

BsicazxExIs1s2s3s4Solucinz1-3-200000ecuacinzs101210006ecuacins1s202101008ecuacins2s30-1100101ecuacins3s400100012ecuacins4La anterior tabla muestra a la solucin bsica inicial del modelo. La informacin en la tabla se lee de la siguiente manera. La columna bsica identifica las variables bsicas actuales s1 , s2 , s3 y s4 , cuyos valores de dan en la columna solucin. Esto supone implcitamente que las variables no bsicas X1 y X2 (aquellas no presentes en la columna bsica tienen valor cero. El valor correspondiente de la funcin objetivo es:Z = 3 * 0 + 2 * 0 + 0 * 6 + 0 * 8 + 0 * 1 + 0 * 2 = 0 , como se muestra en la columna solucin.Al aplicar la condicin de optimidad, XE tiene el coeficiente ms negativo en la ecuacin z y por ello, se escoge como la variable entrante. La condicin de factibilidad muestra que s2 corresponde a la menor interseccin, por lo que deber salir de la interseccin.

Al aplicar el mtodo Gauss-Jordan la tabla quedara de la siguiente forma:

La nueva solucin resulta ser: XE = 4 y XI = 0

Ver grfica es el punto B, solucin optima.

Ejemplo 3Modelo de transporte

MG Auto Company tiene plantas en los ngeles, Detroit y Nueva Orleans. Sus centros de distribucin principales estn ubicados en Denver y Miami. Las capacidades de las tres plantas durante el trimestre prximo son de 1000, 1500 y 1200 automviles. Las demandas trimestrales en los dos centros de distribucin son de 2300 y 1400 vehculos. El costo del transporte de un automvil por tren es aproximadamente de 8 centavos por milla. El diagrama de la distancia recorrida entre las plantas y los centros de distribucin es el siguiente.DenverMiamiLos ngeles10002690Detroit12501350Nueva Orleans1275850El diagrama de la distancia del recorrido puede traducirse en costo por automvil a razn de 8 centavos por milla recorrida. Esto produce los costos siguientes (redondeados a nmeros enteros), que representan a cij del modelo original:

Denver (1)Miami (2)Los ngeles (1)10002690Detroit (2)12501350Nueva Orleans (3)1275850Mediante el uso de cdigo numricos para representar las plantas y centros de distribucin, hacemos que xij represente el nmero de automviles transportados de la fuente i al destino j. Como la oferta total (igual 1000 + 1500 + 1200 = 3700) es igual a la demanda total (=2300 + 1400 = 3700), el modelo de transporte resultante est equilibrado. Por lo tanto, el siguiente modelo muestra el problema tiene todas la restricciones de igualdad:Minimizar z = 80x11 + 215x12 + 100x21 + 108x12 + 102x31 + 68x32

Sujeto a x11 + x12 = 1000 + x21 + x22 = 1500 + x31 + x32 = 1200 x11 + x21 + x31 = 2300 + x12 + x22 + x32 = 1400xij 0 , para todas las i y j

La tabla de transporte es la forma de matriz donde sus renglones representan las fuentes y sus columnas el destino. Los elementos de costo cij se resumen en la esquina noreste de la celda de la matriz (i, j).

Ejemplo 3Modelo de redes

La compaa Cablevisin, est planeado una red para dar servicio de TV por cable a cinco nuevas reas de desarrollo habitacional. La red del sistema de cable se resume en la siguiente figura. Los nmeros asociados con cada rama representan la longitud de cable (en millas) que se necesita para conectar dos sitios cualesquiera. El nodo 1 representa la estacin de TV por cable y los nodos restantes (2 a 6) representan las cinco reas de desarrollo. Una rama faltante entre dos nodos implica que es prohibitivamente costo o fsicamente imposible conectar las reas de desarrollo asociadas. Se necesita determinar los enlaces que originarn el uso mnimo de cable a la vez que se garantiza que todas las reas se conecten (directa o indirectamente) a la estacin de TV por cable.

Solucin grfica, mediante iteraciones. El procedimiento puede iniciarse desde cualquier nodo, terminado siempre con la misma solucin ptima.

El nodo 1 representa el conjunto de nodos conectados. El conjunto de nodos no conectados lo representan los nodos 2, 3, 4, 5 y 6. En forma simblica es:

C = {1} , = {2, 3, 4, 5, 6}

Iteracin 1: El nodo 1 debe conectarse al nodo 2, que es el nodo ms prximo en = {2, 3, 4, 5, 6}. Por tanto: C = {1,2} , = {3, 4, 5, 6}

Iteracin 2: Los nodos 1 y 2 (del conjunto C) ahora estn unidos permanentemente. En la iteracin 2 seleccionamos un nodo en = {3, 4, 5, 6} que ste es el ms prximo a un nodo C = {1, 2}. Como la distancia que ocurre entre 2 y 5.C = {1,2, 5} , = {3, 4, 6}

Iteracin 3: Son las distancias de los nodos C = {1,2, 5} a todos los nodos en C = {3, 4, 6}. Por tanto, los nodos 2 y 4 estn conectados, que produce:C = {1,2, 4, 5} , = {3, 6}

Iteracin 4: Se refiere a los nodos 4 y 6 los cuales deben estar conectados.C = {1,2, 4, 5, 6} , = {3}

Iteracin 5: Existe un empate que se puede romper arbitrariamente. Esto quiere decir que podemos conectar 1 y 3 o 4 y 3. Ambas soluciones (alternativas) nos conducen a:C = {1,2,3, 4, 5, 6} , = {0}

Como todos los nodos estn conectados, el procedimiento est completo. La longitud mnima (en millas) de cable que se utiliza para conectar las reas de desarrollo habitacional a la estacin de TV es igual a 1 + 3 + 4 + 3 + 5 = 16 millas.Referencias bibliogrficasBierman, Bonini y Hausman (1994). Anlisis cuantitativo para la toma de decisiones. Wilmington, Delaware: Addison-Wesley Iberoamericana.Taha, Hamdy A. (2004) Investigacin de operaciones. Mxico: Alfaomega.