Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero"

Transcripción

1 Fundamentos de Investigación de Operaciones y Vendedor Viajero 23 de mayo de 2004 Si bien la resolución del problema de transporte mediante tableau parece ser muy expedita, existen ciertos tipos de problemas de transporte, para los cuales el método no es eficiente. Estos problemas son los llamados Problemas de. 1. Formulación del Problema de A modo de ejemplo, construyamos el modelo de programación lineal para el siguiente problema. Ejemplo 1 Una fábrica dispone de cuatro obreros para completar cuatro trabajos. Cada obrero sólo puede hacer uno de los trabajos. El tiempo que requiere cada obrero para completar cada trabajo se entrega en el Cuadro 1.1. Tiempo (Horas) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Obrero Obrero Obrero Obrero Cuadro 1.1: Tiempos requeridos por obreros La fábrica desea minimizar el tiempo total dedicado a los cuatro trabajos. Formule y resuelva un modelo que determine la mejor asignación de los obreros. En primer lugar debemos definir las variables de decisión necesarias para representar las posibles alternativas de asignación. Evidentemente, de acuerdo a la naturaleza del problema conviene emplear variables binarias. Sea: x ij = asignación de obrero i a trabajo j (1.1) La variable binaria x ij valdrá 1 si se asigna al obrero i al trabajo j y 0 en caso contrario. Por lo tanto, la formulación del problema queda: 1

2 mín s.t. 4 n i=1 j=1 c ijx ij j=4 i=4 j=1 x ij = 1 (i = ) (Restricciones de obreros) i=1 x ij = 1 (j = ) (Restricciones de trabajos) x ij = {0, 1} (i = ; j = ) (Variables binarias) (1.2) Donde c ij representa el costo (tiempo) de la asignación del obrero i al trabajo j. Las restricciones de trabajos obligan a que todo trabajo deba ser asignado a un obrero. Las restricciones de obreros imponen que sólo puede ser asignado un trabajo a cada obrero. Olvidando la naturaleza de las variables, podemos decir que el problema anterior es un problema de transporte balanceado donde cada punto de oferta entrega una unidad y cada punto de demanda requiere una unidad. En general, un problema de asignación es un problema de transporte balanceado con oferta y demanda igual a 1. Se puede demostrar que como las ofertas y demandas tienen valores numéricos enteros, la solución óptima debe corresponder a un conjunto de valores enteros. Como a la derecha de cada restricción se tiene un 1, los únicos valores posibles para las variables son 1 y 0. Luego, podemos olvidarnos de la condición de que las variables deben ser enteras y resolver el problema mediante un tableau de transporte. Siguiendo ese camino, se obtiene el Cuadro 1.2. Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Oferta Obrero Obrero Obrero Obrero Demanda Cuadro 1.2: Tableau de Transporte para el Ejemplo 1 Por lo tanto, se asigna el obrero 1 al trabajo 2, el 2 al 4, el 3 al 3 y el 4 al 1, incurriendo en un tiempo total de = 15 horas. 2

3 2. Método Húngaro 2.1. Descripción En general, el método Simplex para problemas de transporte es poco eficiente para resolver problemas de asignación, especialmente en problemas de gran tamaño. Por ello, para resolver problemas de asignación (minimización) se emplea normalmente el Método Húngaro. La principal ventaja es que el método húngaro es considerablemente más simple que el método Simplex del problema de transporte. Para aplicar el método se deben seguir los siguientes pasos: Paso 1 Determine el menor elemento en cada fila de la matriz de costos (m m). Construya una nueva matriz restando a cada costo el costo menor de esa fila. A continuación determine el costo mínimo en cada columna de la matriz resultante. Construya una nueva matriz (matriz de costos reducidos) restando a cada costo el menor costo de esa columna. Paso 2 Trace el número mínimo de líneas (horizontales o verticales) que son necesarias para cubrir todos los ceros de la matriz reducida. Si se requieren m líneas, los ceros de la matriz reducida indican la asignación óptima. Si se requieren menos de m líneas, siga al Paso 3. Paso 3 Determine el menor costo de la matriz reducida que no está tarjado por las líneas del Paso 2. Sea dicho costo k. Luego, reste a todos los coeficientes no tarjados el valor k y sume a todos los coeficientes tarjados por dos líneas el valor k. Vuelva al Paso 1. El método Húngaro resuelve un problema de minimización a partir de una matriz de costos cuadrada. Sin embargo, haciendo algunas modificaciones puede ser más versátil: 1. Para resolver un problema de asignación cuyo objetivo es maximizar la función objetivo, multiplique la matriz de costos por 1 y resuelva el problema de minimización. 2. Si el número de filas y columnas en la matriz de costos no son iguales, el problema de asignación no está balanceado. Similarmente al problema de transporte, balancee la matriz agregando filas o columnas artificiales según corresponda. Los costos de las filas o columnas artificiales deben ser idénticos para todas las combinaciones de forma de no generar preferencias. 3. Si se puede hacer una asignación más de una vez, repita la fila o columna según corresponda cuantas veces sea necesario. Balancee el problema Ejemplo de Resolución A continuación se resuelve el problema del ejemplo mediante el Método Húngaro. En primer lugar se busca el mínimo por filas en la matriz de costos. Mínimo por fila Luego se resta el valor determinado en cada fila y se busca el mínimo por columna: 3

4 Mínimo por columna Se resta el menor costo por columna y se trazan el menor número de líneas que cubran todos los ceros de la matriz de costos reducida: Luego, de los coeficientes no tarjados el menor es 1. Restamos a todos los no tarjados 1 y sumamos 1 a los tarjados dos veces. Volvemos a trazar el número mínimo de líneas que cubran todos los ceros Como el número de líneas trazadas es igual a la dimensión de la matriz se ha encontrado el óptimo. Para interpretar la asignación debemos buscar aquellas filas y columnas que posean un único cero. Por ejemplo, la fila y columna 3 posee un único 0, luego x 33 = 1. Por otro lado, la segunda columna posee un único cero en la primera fila, luego x 12 = Luego, el cero de la primera fila y cuarta columna puede ser descartado pues ya existe una asignación obligatoria en la primera fila. De esta forma, el único cero restante en la cuarta columna es el de la segunda fila, por lo tanto x 24 = A continuación se puede descartar el cero de la segunda fila y la primera columna pues ya existe una asignación obligatoria en esa fila. Finalmente, en la primera columna y cuarta fila sólo queda un cero, luego x 41 = El resultado verifica la solución obtenida mediante el tableau de transporte. 4

5 2.3. Justificación Intuitiva del Método Húngaro Para entregar una justificación intuitiva de cómo trabaja el Método Húngaro, es necesario discutir el siguiente resultado: Si se suma una constante a cada costo de una fila o de una columna de un problema de transporte balanceado, la solución al problema es invariante. Para mostrar que el resultado es correcto, supongamos que se agrega una constante k a cada costo en la primera fila del ejemplo en estudio. Entonces: Nuevo valor de la función objetivo = valor anterior + k(x 11 + x 12 + x 13 + x 14 ) Como cualquier solución factible del problema debe cumplir que: x 11 + x 12 + x 13 + x 14 = 1 Nuevo valor de la función objetivo = valor anterior + k Debido a que minimizar el valor de una función más una constante es equivalente a minimizar la función, la solución óptima no cambia si se agrega una constante k a cada costo de la primera fila. Se puede aplicar el mismo argumento a cualquier otra fila o columna. El paso 1 del Método Húngaro consiste (para cada fila y columna) en restar una constante a cada elemento de la fila o columna. Entonces, el paso 1 crea una nueva matriz de costos que posee la misma solución óptima que el problema original. El paso 3 del método es equivalente a sumar k a cada costo de una fila tarjada y restar k a cada costo de las columnas no tarjadas (o viceversa). Por lo tanto, el paso 3 también crea una nueva matriz con la misma solución óptima que la matriz original. Cada vez que se realiza el paso 3, se crea al menos un nuevo cero en la matriz de costos. Los pasos 1 y 3 también aseguran que todos los costos sean no negativos. En suma, el efecto neto de los pasos 1 y 3 del Método Húngaro es crear una secuencia de problemas de asignación (con costos no negativos) tal que todos ellos poseen la misma solución óptima al problema de asignación original. Luego, considerando un problema de asignación con costos no negativos, cualquier asignación factible para la cual todos los x ij iguales a 1 tienen un costo asociado nulo, deben ser una solución óptima. Por lo tanto, cuando el paso 2 indica que se requieren m líneas para cubrir todos los ceros de la matriz, se ha encontrado una solución óptima para el problema original Ejemplos Adicionales Ejercicio 1 Una constructora debe contratar obreros para realizar 4 trabajos. Existen 3 obreros disponibles para ejecutar dichas labores. El monto (en miles de pesos) cobrado por cada obrero para realizar cada trabajo se indica en el Cuadro 2.1. Trabajos Obrero Obrero Obrero Cuadro 2.1: Montos para realizar trabajos El obrero 1 tiene disponibilidad para ejecutar sólo un trabajo. Los obreros 2 y 3 pueden ejecutar hasta dos trabajos. Determine la asignación que minimiza los costos de ejecutar los cuatro trabajos. 5

6 Como los obreros 2 y 3 pueden realizar hasta dos trabajos, repetiremos una vez las filas dos y tres. Así, la matriz queda de 5 filas. Luego, cuadramos la matriz agregando una columna ficticia. Los costos de dicha columna deben ser idénticos para no generar preferencias, por simplicidad emplearemos el cero. Luego, la matriz de costos queda (las M indican asignación imposible): M M 0 M M Restando por filas la matriz no cambia, pues en cada fila hay un cero. Restando por columnas se obtiene: M M 0 M M Luego, se obtiene que el mínimo de líneas para cubrir todos los ceros es 2. El menor valor no tarjado es M M 0 M M Restamos a los coeficientes no tarjados el 1 y se los sumamos a los tarjados dos veces. Volvemos a identificar el número mínimo de líneas y al menor valor no tarjado: M M 0 M M En este caso el número mínimo de líneas para cubrir todos los ceros es 5, por lo que se está en el óptimo. De la cuarta columna podemos asignar inmediatamente un cero, descartando el de la primera fila: M M 0 M M A continuación, ni por filas ni por columnas existe un único cero, por lo que pueden existir soluciones alternativas. Arbitrariamente asignaremos un cero en la primera celda de la segunda fila, lo que obliga a hacer otras asignaciones: 6

7 M M 0 M M Para completar la asignación volvemos a asignar arbitrariamente el cero de la cuarta fila y la segunda columna: Por lo tanto, la asignación queda: M M 0 M M Obrero 1 Trabajo 4 Obrero 2 Trabajo 1 y 3 Obrero 3 Trabajo 2 Buscando las otras asignaciones alternativas, se repite la misma solución óptima. Ejercicio 2 Para participar en el próximo campeonato de bridge, el Club universitario debe enviar un equipo de 4 personas. Hay seis jugadores disponibles, cuyos rendimientos relativos en cada una de las posiciones se indican en el Cuadro 2.2. Determine el mejor equipo que se podría enviar al campeonato. N E S O Juan Pedro Raúl Sergio Arturo Carlos Cuadro 2.2: Rendimientos de los jugadores En este caso interesa maximizar el rendimiento del equipo, por lo tanto se debe plantear como un problema de maximización. Dado que el Método Húngaro sólo minimiza, multiplicaremos por 1 la matriz de ganancias. Además, agregaremos dos columnas artificiales para cuadrar la matriz, luego la matriz de costos queda:

8 A continuación se resta el mínimo costo por filas y por columnas y se busca el número mínimo de líneas que cubran todos los ceros: Restando 1 a las celdas no tarjadas y sumándoselo a las tarjadas dos veces se obtiene el siguiente tableau. Se vuelve a buscar el número mínimo de líneas que cubran todos los ceros y se identifica el coeficiente menor no tarjado: Se vuelve a aplicar el método a la matriz siguiente: En la nueva matriz de costos no es posible trazar un número inferior a 6 líneas para cubrir todos los ceros, luego se ha alcanzado el óptimo. A continuación se procede a asignar: Si bien en el tableau anterior, la tercera y cuarta fila (o quinta y sexta columna) no están asignadas, las dos opciones de asignación posibles representan que Raúl y Sergio no integrarán el equipo. Luego: Juan S 8 Pedro O 6 Arturo E 5 Carlos N 8 27 Por lo tanto, la asignación óptima tiene un rendimiento esperado de 27. 8

9 Simplet Grincheux Dormeur Atchoum Prof Agassi 0,2 0,3 0,1 0,4 0,5 Sampras 0,1 0,4 0,2 0,3 0,5 Kuerten 0,1 0,4 0,2 0,5 0,3 Cuadro 2.3: Probabilidad de ganar de cada tenista Ejercicio 3 Se está organizando un torneo de tenis en donde se deben jugar 5 partidos. Se cuenta con 3 tenistas: Agassi, Sampras y Kuerten. Cada uno debe jugar al menos un partido. La tabla 2.3 muestra la probabilidad de ganar de cada tenista dependiendo de su rival. Se pide determinar la mejor estrategia para ganar el torneo. 9

10 3. El Problema del Vendedor Viajero 3.1. Descripción General El problema del Vendedor viajero pertenece a la familia de problemas de optimización combinatoria, es decir, problemas que poseen un conjunto finito de soluciones factibles. En términos generales, el problema del vendedor viajero consiste en determinar cómo se debe recorrer la totalidad de un conjunto de puntos, sin pasar dos veces por un mismo lugar, volviendo al punto desde donde se partió, minimizando el camino total recorrido. Veamos un ejemplo. Ejemplo 2 El propietario de una pequeña cadena de almacenes visita una vez al mes todas sus tiendas. El dueño de los almacenes vive en la Ciudad 1. Las distancias (km) entre las ciudades donde se ubican sus almacenes se entrega en el Cuadro 3.1. Qué recorrido debe seguir para minimizar la distancia total recorrida? Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad Ciudad Ciudad Ciudad Ciudad Cuadro 3.1: Distancias entre ciudades Claramente, se debe determinar el orden en que se deben recorrer las 5 ciudades partiendo desde la ciudad 1. En primer lugar, formularemos un modelo de programación lineal entera. Supongamos que se deben visitar las ciudades 1, 2, 3,... N. Para todo i j se tiene c ij = distancia desde la ciudad i a la ciudad j, se c ii = M, donde M es un número muy grande en relación a las distancias del problema. Definamos: { 1 la solución indica ir desde la ciudad i a la j x ij = (3.1) 0 en caso contrario En forma alternativa simplemente se puede eliminar las variables x ii del modelo para evitar las asignaciones no deseadas. De acuerdo a las variables definidas, el modelo de programación lineal queda: Min st i=1 j=1 c ijx ij (a) i=n i=1 x ij = 1 (j = 1... N) (b) j=n j=1 x ij = 1 (i = 1... N) (c) u i u j + Nx ij N 1 (i j; i = 2... N; j = 2... N) (d) x ij = {0, 1} (i = 1... N; j = 1... N) u j 0 (j = 1... N) La función objetivo (a) refleja la longitud total del camino recorrido. Las restricciones (b) aseguran que se llegue sólo una vez a cada ciudad. Las restricciones (c) aseguran que se parta desde cada ciudad. Las restricciones (d) son las fundamentales, ellas aseguran que: 10 (3.2)

11 1. Cualquier conjunto de valores de x ij que conformen un subtour no sean soluciones factibles. 2. Cualquier conjunto de valores de x ij que conformen un tour sea una solución factible. Llamaremos tour a cualquier camino que satisfaga todas las condiciones del problema del vendedor viajero, es decir, pase por todos los puntos sin repetir, comience y termine en el mismo punto. En el ejemplo, un tour podría ser: , con una distancia total recorrida de: = 737 [km]. Un subtour es un camino cerrado, que comienza y termina en la misma ciudad, pero que no pasa por todas las ciudades. En el ejemplo, un subtour podría ser Para ilustrar el funcionamiento del modelo, supongamos que se tiene como solución al problema del ejemplo x 15 = x 21 = x 34 = x 43 = x 52 = 1. Esta asignación contiene 2 subtours: y Si escogemos el subtour que no contiene a la Ciudad 1 (3-4-3) y escribimos las restricciones (d) correspondiente a estas asignaciones se obtiene: Sumando ambas restricciones se obtiene: u 3 u 4 + 5x 34 4 y u 4 u 3 + 5x 43 4 (3.3) 5(x 34 + x 43 ) 8 (3.4) La restricción anterior no se puede satisfacer para la combinación x 43 = x 34 = 1, por lo tanto el subtour no es una solución factible para el modelo de programación lineal. Se puede verificar que las restricciones (d) son violadas por cualquier subtour posible. Supongamos ahora que la Ciudad 1 fue la primera visitada. Consideremos: t i = posición en el tour cuando la ciudad i es visitada. Luego, si u i = t i cualquier tour satisface las restricciones (d). A modo de ejemplo, consideremos el tour Entonces, las otras variables son: u 1 = 1, u 2 = 5, u 3 = 2, u 4 = 3 y u 5 = 4. Consideremos ahora cualquier restricción (d) que contenga un x ij = 1. Por ejemplo, la restricción correspondiente a x 52 es: u 5 u 2 + 5x 52 4 (3.5) Como la Ciudad 2 es la que sigue inmediatamente a la Ciudad 5 se tiene: Por lo tanto, la restricción (d) de x 52 se satisface ya que: u 5 u 2 = 1 (3.6) (3.7) Consideremos ahora una restricción correspondiente a un x ij = 0, por ejemplo x 32 de acuerdo al tour escogido. La restricción de x 32 queda: u 3 u 2 + 5x 32 4 u 3 u 2 4 (3.8) Como las variables u i representan la posición en el tour, se tiene que u i 5 y u i > 1 (i = 2,... N). En este caso: u 3 5 u 2 > 1 } u 3 u = 3 (3.9) 11

12 Por lo tanto, las restricciones (d) para las variables x ij = 0 también se satisfacen cuando las variables contienen un tour. Luego, el modelo efectivamente elimina cualquier secuencia de N ciudades que comiencen en la Ciudad 1 y que contengan un subtour. Por lo tanto, el modelo resuelve el problema del Vendedor Viajero. Evidentemente, el modelo crece rápidamente según aumente el número de ciudades incluidas en el problema, por lo tanto tiende a ser poco eficiente. Para el problema del ejemplo, el modelo en LINDO queda: min 132 x x x x x x x x x x x x x x x x x x x x54 st x12 + x13 + x14 + x15 = 1 x21 + x23 + x24 + x25 = 1 x31 + x32 + x34 + x35 = 1 x41 + x42 + x43 + x45 = 1 x51 + x52 + x53 + x54 = 1 x21 + x31 + x41 + x51 = 1 x12 + x32 + x42 + x52 = 1 x13 + x23 + x43 + x53 = 1 x14 + x24 + x34 + x54 = 1 x15 + x25 + x35 + x45 = 1 u2 - u3 + 5 x23 <= 4 u2 - u4 + 5 x24 <= 4 u2 - u5 + 5 x25 <= 4 u3 - u2 + 5 x32 <= 4 u3 - u4 + 5 x34 <= 4 u3 - u5 + 5 x35 <= 4 u4 - u2 + 5 x42 <= 4 u4 - u3 + 5 x43 <= 4 u4 - u5 + 5 x45 <= 4 u5 - u2 + 5 x52 <= 4 u5 - u3 + 5 x53 <= 4 u5 - u4 + 5 x54 <= 4 end int x12 int x13 int x14 int x15 int x21 int x23 int x24 int x25 int x31 int x32 int x34 int x35 12

13 int x41 int x42 int x43 int x45 int x51 int x52 int x53 int x54 La instrucción int xij de LINDO permite definir como variable binaria a xij. Al resolver el modelo con LINDO, luego de una serie de iteraciones se obtiene: LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST x x x x x x x x x x x x x x x x x x x x u u u u Por lo tanto, el óptimo encontrado corresponde al tour con una distancia total a recorrer de 668. La solución encontrada no es única, ya que el modelo podría también haber entregado la misma secuencia en sentido inverso. 13

14 Si bien el planteo anterior permite resolver el problema mediante Simplex, existe un método más simple que permite resolver el problema manualmente a través una combinación del Método Húngaro y la técnica de Ramificación y Acotamiento (Branch-and-Bound) Resolución del Problema del Vendedor Viajero A continuación se resolverá el problema del Vendedor Viajero como un problema de asignación. Para ello construiremos una matriz de costos, donde se incluyan las distancias c ij (i j) desde cada ciudad i a cada ciudad j. Además, incluiremos en la diagonal de la matriz de costos c ii = M (i = 1... N), para evitar la asignación de una ciudad a si misma como se muestra en el Cuadro 3.2. M M M M M Cuadro 3.2: Matriz de Costos del Problema Original La resolución del problema anterior como un problema de asignación constituye una relajación del problema original, ya que no incorpora restricciones adicionales para evitar que en la asignación aparezcan subtours. De todas maneras, si la solución del problema de asignación constituye un tour, también será solución al problema del vendedor viajero. Resolviendo, se obtiene la matriz reducida del problema original (Cuadro 3.3). M M M M M Cuadro 3.3: Matriz de Costos Reducida Si bien el Cuadro 3.3 presenta dos soluciones alternativas, se verifica que una es hacer el recorrido en el sentido opuesto a a la otra. La asignación es: y 3 4 3, con un largo total: z = = 495. La solución contiene dos subtours, por lo tanto no es óptima. A continuación se procede a ramificar rompiendo el subtour de menor longitud, es decir, resolveremos dos suproblemas: Subproblema 1 Se impone 3 4, es decir, x 34 = 0 y c 34 = M sobre el problema original. Subproblema 2 Se impone 4 3, es decir, x 43 = 0 y c 43 = M sobre el problema original. Luego, podemos comenzar a construir el árbol de ramificación (Figura 3.1). Para resolver el Subproblema 1 incorporamos una M al Cuadro 3.3 y aplicamos el Método Húngaro a la nueva matriz (Cuadro 3.4). Se resta el menor valor por filas y luego por columnas. Buscando el número menor de líneas que cubran todos los ceros se determina que se está en el óptimo (Cuadro 3.5). Luego se asigna y se verifica 14

15 z = Subproblema Subproblema 2 Figura 3.1: Árbol de Ramificación M M M M M M Cuadro 3.4: Matriz de Costos Subproblema 1 si la asignación corresponde a un tour. M M M M M M Cuadro 3.5: Matriz Final Subproblema 1 Luego, el Subproblema 1 genera como solución los subtours y 2 5 2, con un largo total: z = = 652. Por lo tanto, la solución obtenida tampoco es factible. Antes de volver a ramificar debemos verificar que solución entrega la otra rama (Subproblema 2). En caso que dicha rama tampoco genere una solución factible, deberemos escoger aquel Subproblema con menor valor de función objetivo y volver a ramificar. Para resolver el Subproblema 2 incorporamos al Cuadro 3.3 una M en la asignación 4 3 (Cuadro 3.6). Luego restamos el menor valor por fila y luego por columna. Nuevamente, el número menor de líneas que cubran todos los ceros es 5 por lo tanto se está en el óptimo y se procede a asignar. La asignación obtenida corresponde a la secuencia y 2 5 2, con un largo total: z = = 652 (Cuadro 3.7). La solución encontrada tampoco es un tour. Como el camino obtenido por ambas ramas es de idéntica longitud, escogeremos arbitrariamente abrir la rama de la izquierda. En este caso, interrumpiremos el subtour 2 5 2, es decir generamos los 15

16 M M M M M M Cuadro 3.6: Matriz de Costos Subproblema 2 M M M M M M Cuadro 3.7: Matriz Final Subproblema 2 subproblemas: Subproblema 3 Se impone 2 5, es decir, x 25 = 0 y c 25 = M sobre el Subproblema 1. Subproblema 4 Se impone 5 2, es decir, x 52 = 0 y c 52 = M sobre el Subproblema 1. El árbol de ramificación hasta este punto se ilustra en la Figura 3.2. z = Subproblema 1 z = Subproblema 2 z = Subproblema Subproblema 4 Figura 3.2: Árbol de Ramificación Actualizado Para resolver el Subproblema 3 agregamos una M en la combinación 2 5 en el Cuadro 3.5. El tableau deja de ser final ya que el número mínimo de líneas para cubrir todos los ceros es 4 (Cuadro 3.8). Iterando se obtiene el Cuadro 3.9 en cual se puede asignar. Luego, la solución óptima para el Subproblema 3 corresponde a la secuencia con una distancia total asociada de: z = = 668. La secuencia anterior 16

17 M M M 0 52 M M M M Cuadro 3.8: Matriz Inicial Subproblema 3 M M M 0 36 M M M M Cuadro 3.9: Matriz Final Subproblema 3 conforma un tour, por la tanto constituye una solución factible para el problema del Vendedor Viajero. Como por el momento es la mejor solución disponible fijaremos 668 como cota superior para el problema. El resultado anterior no evita resolver el Subproblema 4, ya que aún es posible encontrar una solución que sea mayor a 652, pero inferior a 668. Para resolver el Subproblema 4 incorporamos una M a la combinación 5 2 del Cuadro 3.5. Una vez más podemos trazar un número inferior a 5 líneas por lo que debemos volver a iterar (Cuadro 3.10). Nuevamente se puede volver a trazar 4 líneas y volver a iterar (Cuadro 3.11). Finalmente podemos asignar, obteniendo la secuencia con una distancia total asociada de: z = = 704 (Cuadro 12). La secuencia encontrada constituye un tour, por lo que representa una solución factible. Sin embargo, la solución obtenida está por sobre la cota superior por lo que puede ser desechada. Como en la rama de la derecha (Subproblema 2), el valor de la función objetivo está por debajo de la cota superior, debemos completar la ramificación pues aún es factible encontrar una solución que sea igual o mayor a 652, pero por debajo de la cota superior. Como la secuencia obtenida en el Subproblema 2 es y 2 5 2, con un largo total: z = = 652 (Cuadro 3.7) debemos escoger uno de los subtour e M M M M M M M Cuadro 3.10: Matriz Inicial Subproblema 4 17

18 M M M M M M M Cuadro 3.11: Segunda Iteración Subproblema 4 M M M M M M M Cuadro 3.12: Matriz final Subproblema 4 impedirlo, por ejemplo el más más corto. Por lo tanto, debemos interrumpir el subtour 2 5 2, es decir generamos los subproblemas: Subproblema 5 Se impone 2 5, es decir, x 25 = 0 y c 25 = M sobre el Subproblema 2. Subproblema 6 Se impone 5 2, es decir, x 52 = 0 y c 52 = M sobre el Subproblema 2. Siguiendo la metodología empleada anteriormente, reemplazamos la M respectiva en cada problema en la matriz final del Subproblema 2 e iteramos en caso de ser necesario. La solución del Subproblema 5 genera la secuencia: , con una distancia total asociada de z = 704. La solución constituye un tour, pero está por sobre la cota superior, por lo que puede ser descartada. La solución del Subproblema 6 genera la secuencia: y , con una distancia total asociada de z = 910. Como la solución obtenida contiene dos subtours, no representa una solución óptima. Además, no conviene seguir ramificando pues el valor de la función objetivo está muy por sobre la cota superior y al ramificar sólo se obtendrán valores iguales o peores al de partida. En suma, la mejor solución es la obtenida a través del Subproblema 3, dada por la secuencia: con una distancia total asociada de: z = = 668. La Figura 3.3 muestra el árbol de ramificación completo. 18

19 3 4 z = Subproblema 3 z = Subproblema 1 z = Subproblema 4 z = Subproblema 2 z = Subproblema 5 z = Subproblema 6 z = Figura 3.3: Árbol de Ramificación Final 19

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Fundamentos de Investigación de Operaciones Investigación de Operaciones de agosto de 200. Estandarización Cuando se plantea un modelo de LP pueden existir igualdades y desigualdades. De la misma forma

Más detalles

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 1 de agosto de 2003 1. Introducción Cualquier modelo de una situación es una simplificación de la situación real. Por lo tanto,

Más detalles

Fundamentos de Investigación de Operaciones El Problema de Transporte

Fundamentos de Investigación de Operaciones El Problema de Transporte Fundamentos de Investigación de Operaciones El Problema de Transporte Septiembre 2002 El Problema de Transporte corresponde a un tipo particular de un problema de programación lineal. Si bien este tipo

Más detalles

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de 2003 1. Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema

Más detalles

Programación Lineal Entera

Programación Lineal Entera Programación Lineal Entera P.M. Mateo y David Lahoz 2 de julio de 2009 En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción

Más detalles

APUNTES SOBRE EL MÉTODO SÍMPLEX DE PROGRAMACIÓN LINEAL. Adriel R. Collazo Pedraja

APUNTES SOBRE EL MÉTODO SÍMPLEX DE PROGRAMACIÓN LINEAL. Adriel R. Collazo Pedraja APUNTES SOBRE EL MÉTODO SÍMPLEX DE PROGRAMACIÓN LINEAL Adriel R. Collazo Pedraja 2 INTRODUCCIÓN Este trabajo tiene como propósito proveer ayuda al estudiante para que pueda comprender y manejar más efectivamente

Más detalles

Unidad 5 Utilización de Excel para la solución de problemas de programación lineal

Unidad 5 Utilización de Excel para la solución de problemas de programación lineal Unidad 5 Utilización de Excel para la solución de problemas de programación lineal La solución del modelo de programación lineal (pl) es una adaptación de los métodos matriciales ya que el modelo tiene

Más detalles

APLICACIONES CON SOLVER OPCIONES DE SOLVER

APLICACIONES CON SOLVER OPCIONES DE SOLVER APLICACIONES CON SOLVER Una de las herramientas con que cuenta el Excel es el solver, que sirve para crear modelos al poderse, diseñar, construir y resolver problemas de optimización. Es una poderosa herramienta

Más detalles

CURSO CERO. Departamento de Matemáticas. Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre

CURSO CERO. Departamento de Matemáticas. Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre CURSO CERO Departamento de Matemáticas Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre Capítulo 1 La demostración matemática Demostración por inducción El razonamiento por inducción es una

Más detalles

Investigación Operacional I EII 445

Investigación Operacional I EII 445 Investigación Operacional I EII 445 Programación Lineal Método Simple Gabriel Gutiérrez Jarpa. Propiedades Básicas de Programación Lineal Formato Estándar Un problema de programación lineal es un programa

Más detalles

Programación Lineal y Optimización Segundo Examen Parcial Respuesta: :Solución Profr. Eduardo Uresti, Enero-Mayo 2011

Programación Lineal y Optimización Segundo Examen Parcial Respuesta: :Solución Profr. Eduardo Uresti, Enero-Mayo 2011 Matrícula: Nombre: Programación Lineal y Optimización Segundo Examen Parcial Respuesta: : Profr. Eduardo Uresti, Enero-Mayo 2011 1. Suponga que tiene una empresa que produce tres tipos de productos (P

Más detalles

Ejercicios de Programación Lineal

Ejercicios de Programación Lineal Ejercicios de Programación Lineal Investigación Operativa Ingeniería Informática, UCM Curso 8/9 Una compañía de transporte dispone de camiones con capacidad de 4 libras y de 5 camiones con capacidad de

Más detalles

Unidad 2 Método gráfico de solución

Unidad 2 Método gráfico de solución Unidad 2 Método gráfico de solución Los problemas de programación lineal (pl) que sólo tengan dos variables de decisión pueden resolverse gráficamente, ya que, como se ha visto en los Antecedentes, una

Más detalles

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1

Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Formulación de Modelos de Programacón Lineal 25 de julio de 2003 La (LP es una herramienta para resolver problemas de optimización

Más detalles

Programación Lineal y Optimización Segundo Examen Parcial :Solución Profr. Eduardo Uresti, Verano 2009

Programación Lineal y Optimización Segundo Examen Parcial :Solución Profr. Eduardo Uresti, Verano 2009 Programación Lineal y Optimización Segundo Examen Parcial : Profr. Eduardo Uresti, Verano 2009 Matrícula: Nombre: 1. Suponga que se tiene disponible la siguiente información salida de LINDO a un problema

Más detalles

MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13. Carlos Ivorra

MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13. Carlos Ivorra MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13 Carlos Ivorra Índice 1 Introducción a la optimización 1 2 Programación entera 18 3 Introducción a la programación lineal 24 4 El método símplex

Más detalles

4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD

4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD 4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD El problema de programación lineal se puede considerar como modelo de asignación de recursos, en el que el objetivo es maximizar los ingresos o las utilidades,

Más detalles

Dualidad y Análisis de Sensibilidad

Dualidad y Análisis de Sensibilidad Universidad de Chile Facultad de Ciencias Físicas y Matemáticas Departamento de Ingeniería Industrial IN34A: Clase Auxiliar Dualidad y Análisis de Sensibilidad Marcel Goic F. 1 1 Esta es una versión bastante

Más detalles

Unidad 1 Modelos de programación lineal

Unidad 1 Modelos de programación lineal Unidad 1 Modelos de programación lineal La programación lineal comenzó a utilizarse prácticamente en 1950 para resolver problemas en los que había que optimizar el uso de recursos escasos. Fueron de los

Más detalles

BREVE MANUAL DE SOLVER

BREVE MANUAL DE SOLVER BREVE MANUAL DE SOLVER PROFESOR: DAVID LAHOZ ARNEDO PROGRAMACIÓN LINEAL Definición: Un problema se define de programación lineal si se busca calcular el máximo o el mínimo de una función lineal, la relación

Más detalles

ANÁLISIS DE DATOS NO NUMERICOS

ANÁLISIS DE DATOS NO NUMERICOS ANÁLISIS DE DATOS NO NUMERICOS ESCALAS DE MEDIDA CATEGORICAS Jorge Galbiati Riesco Los datos categóricos son datos que provienen de resultados de experimentos en que sus resultados se miden en escalas

Más detalles

Definición 1.1.1. Dados dos números naturales m y n, una matriz de orden o dimensión m n es una tabla numérica rectangular con m filas y n columnas.

Definición 1.1.1. Dados dos números naturales m y n, una matriz de orden o dimensión m n es una tabla numérica rectangular con m filas y n columnas. Tema 1 Matrices Estructura del tema. Conceptos básicos y ejemplos Operaciones básicas con matrices Método de Gauss Rango de una matriz Concepto de matriz regular y propiedades Determinante asociado a una

Más detalles

El Problema del Transporte

El Problema del Transporte ASIGNATURA PROGRAMACIÓN LINEAL El Problema del Transporte Maestro Ing. Julio Rito Vargas Avilés Octubre 2014 1 Problema de Transporte Es un caso especial de problema de programación lineal (PPL), para

Más detalles

H E R R A M I E N T A S D E A N Á L I S I S D E D A T O S HERRAMIENTAS DE ANÁLISIS DE DATOS

H E R R A M I E N T A S D E A N Á L I S I S D E D A T O S HERRAMIENTAS DE ANÁLISIS DE DATOS H E R R A M I E N T A S D E A N Á L I S I S D E D A T O S HERRAMIENTAS DE ANÁLISIS DE DATOS Una situación que se nos plantea algunas veces es la de resolver un problema hacia atrás, esto es, encontrar

Más detalles

Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración

Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración 5053 Martes, 9 de abril Ramificación y acotamiento () Entregas: material de clase Resumen de técnicas para resolver problemas de programación entera Técnicas de enumeración Enumeración completa hace una

Más detalles

Análisis de los datos

Análisis de los datos Universidad Complutense de Madrid CURSOS DE FORMACIÓN EN INFORMÁTICA Análisis de los datos Hojas de cálculo Tema 6 Análisis de los datos Una de las capacidades más interesantes de Excel es la actualización

Más detalles

1. Juegos de suma cero con dos jugadores

1. Juegos de suma cero con dos jugadores Teoría de juegos Jesús López Fidalgo Esta teoría está íntimamente relacionada con la teoría de la decisión. Lo que diferencia una de otra es el rival contra el que se entra en juego. En la teoría de la

Más detalles

EL MÉTODO SIMPLEX ALGEBRAICO: MINIMIZACION. M. En C. Eduardo Bustos Farías

EL MÉTODO SIMPLEX ALGEBRAICO: MINIMIZACION. M. En C. Eduardo Bustos Farías EL MÉTODO SIMPLEX ALGEBRAICO: MINIMIZACION M. En C. Eduardo Bustos Farías 1 Minimización El método simplex puede aplicarse a un problema de minimización si se modifican los pasos del algoritmo: 1. Se cambia

Más detalles

Teoría del Juego - Juegos Combinatoriales Imparciales

Teoría del Juego - Juegos Combinatoriales Imparciales Teoría del Juego - Juegos Combinatoriales Imparciales Carlos Gámez Taller de Resolución de Problemas Escuela de Matemática Universidad de El Salvador Estudio de Casos Esquema Introducción Juegos de Agarrar

Más detalles

Programación Lineal. Ficha para enseñar a utilizar el Solver de EXCEL en la resolución de problemas de Programación Lineal

Programación Lineal. Ficha para enseñar a utilizar el Solver de EXCEL en la resolución de problemas de Programación Lineal Programación Lineal Ficha para enseñar a utilizar el Solver de EXCEL en la resolución de problemas de Programación Lineal Ejemplo: Plan de producción de PROTRAC En esta ficha vamos a comentar cómo se construyó

Más detalles

PROGRAMACIÓN LINEAL. 8.1. Introducción. 8.2. Inecuaciones lineales con 2 variables

PROGRAMACIÓN LINEAL. 8.1. Introducción. 8.2. Inecuaciones lineales con 2 variables Capítulo 8 PROGRAMACIÓN LINEAL 8.1. Introducción La programación lineal es una técnica matemática relativamente reciente (siglo XX), que consiste en una serie de métodos y procedimientos que permiten resolver

Más detalles

Introducción al programa WinQSB

Introducción al programa WinQSB Introducción al programa WinQSB WinQSB es un sistema interactivo de ayuda a la toma de decisiones que contiene herramientas muy útiles para resolver distintos tipos de problemas en el campo de la investigación

Más detalles

Problema - Acuario. No hay riesgo de ser comido por otro pez si su tamaño no está entre 1/10 y 1/2 inclusive, del tamaño de otro pez.

Problema - Acuario. No hay riesgo de ser comido por otro pez si su tamaño no está entre 1/10 y 1/2 inclusive, del tamaño de otro pez. Primera Olimpiada de Informática 1 Problema - Acuario Es bien conocido que en un acuario algunos peces se pueden comer a otros. Usted tiene un acuario que contiene un cantidad de peces del cual conoce

Más detalles

!!!!!!!! !!!!! Práctica!4.! Programación!básica!en!C.! ! Grado!en!Ingeniería!!en!Electrónica!y!Automática!Industrial! ! Curso!2015H2016!

!!!!!!!! !!!!! Práctica!4.! Programación!básica!en!C.! ! Grado!en!Ingeniería!!en!Electrónica!y!Automática!Industrial! ! Curso!2015H2016! INFORMÁTICA Práctica4. ProgramaciónbásicaenC. GradoenIngenieríaenElectrónicayAutomáticaIndustrial Curso2015H2016 v2.1(18.09.2015) A continuación figuran una serie de ejercicios propuestos, agrupados por

Más detalles

INTERPRETACION ECONOMICA DEL ANALISIS DE SENSIBILIDAD

INTERPRETACION ECONOMICA DEL ANALISIS DE SENSIBILIDAD ESCOLA UNIVERSITÀRIA D ESTUDIS EMPRESARIALS DEPARTAMENT D ECONOMIA I ORGANITZACIÓ D EMPRESES INTERPRETACION ECONOMICA DEL ANALISIS DE SENSIBILIDAD Dunia Durán Juvé Profesora Titular 1ª Edición de 1995:

Más detalles

1.3 Números racionales

1.3 Números racionales 1.3 1.3.1 El concepto de número racional Figura 1.2: Un reparto no equitativo: 12 5 =?. Figura 1.3: Un quinto de la unidad. Con los números naturales y enteros es imposible resolver cuestiones tan simples

Más detalles

Práctica de informática del programa LINDO

Práctica de informática del programa LINDO FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES PROGRAMACIÓN MATEMÁTICA Práctica de informática del programa LINDO Curso 2004-05 LINDO 6.1 es un programa de entorno Windows, que sirve para resolver problemas

Más detalles

1. Examen 21/Junio/1994. Para la inversión de una matriz cuadrada A de orden n n, cuya inversa existe, se ha definido la siguiente iteración

1. Examen 21/Junio/1994. Para la inversión de una matriz cuadrada A de orden n n, cuya inversa existe, se ha definido la siguiente iteración CAPÍTULO 5 EJERCICIOS RESUELTOS: MÉTODOS ITERATIVOS PARA ECUACIONES LINEALES Ejercicios resueltos 1 1. Examen 21/Junio/1994. Para la inversión de una matriz cuadrada A de orden n n cuya inversa existe

Más detalles

Representaciones de matrices

Representaciones de matrices LECCIÓN CONDENSADA 6. Representaciones de matrices En esta lección Representarás unos sistemas cerrados con unos diagramas de transición unas matrices de transición Usarás las matrices para organizar información

Más detalles

Métodos generales de generación de variables aleatorias

Métodos generales de generación de variables aleatorias Tema Métodos generales de generación de variables aleatorias.1. Generación de variables discretas A lo largo de esta sección, consideraremos una variable aleatoria X cuya función puntual es probabilidad

Más detalles

Ensayo: Construcción de la Frontera Eficiente de Markowitz mediante el uso de la herramienta SOLVER de Excel y el modelo Matricial.

Ensayo: Construcción de la Frontera Eficiente de Markowitz mediante el uso de la herramienta SOLVER de Excel y el modelo Matricial. UNIVERSIDAD DE ORIENTE NÚCLEO DE MONAGAS POST GRADO EN CIENCIAS ADMINISTRATIVAS MENCIÓN FINANZAS FINANZAS INTERNACIONALES Ensayo: Construcción de la Frontera Eficiente de Markowitz mediante el uso de la

Más detalles

Sistema Incremental Generador de Oraciones y de Descodificación Lingüística. José Luciano Maldonado. luzmalvy@telcel.net.ve maldonaj@faces.ula.

Sistema Incremental Generador de Oraciones y de Descodificación Lingüística. José Luciano Maldonado. luzmalvy@telcel.net.ve maldonaj@faces.ula. Sistema Incremental Generador de Oraciones y de Descodificación Lingüística. José Luciano Maldonado. luzmalvy@telcel.net.ve maldonaj@faces.ula.ve Resumen: se describe la implementación experimental de

Más detalles

Entorno de trabajo y funciones matemáticas en Excel

Entorno de trabajo y funciones matemáticas en Excel Libro 7 Entorno de trabajo y funciones matemáticas en Excel NTICx / Informática para Adultos Profesor: Carlos A. Sardá 2012 1. Entorno de trabajo de Excel Excel es un programa de computadora desarrollado

Más detalles

Capítulo 6. Modificar archivos de datos. Ordenar casos

Capítulo 6. Modificar archivos de datos. Ordenar casos Capítulo 6 Modificar archivos de datos Los archivos de datos no siempre están organizados de forma idónea. En ocasiones podemos desear cambiar el orden de los casos, o transponer las filas y las columnas,

Más detalles

Nota 1. Los determinantes de orden superior a 3 se calculan aplicando las siguientes propiedades:

Nota 1. Los determinantes de orden superior a 3 se calculan aplicando las siguientes propiedades: Capítulo 1 DETERMINANTES Definición 1 (Matriz traspuesta) Llamaremos matriz traspuesta de A = (a ij ) a la matriz A t = (a ji ); es decir la matriz que consiste en poner las filas de A como columnas Definición

Más detalles

ANÁLISIS DE CORRELACIÓN EMPLEANDO EXCEL Y GRAPH

ANÁLISIS DE CORRELACIÓN EMPLEANDO EXCEL Y GRAPH ANÁLISIS DE CORRELACIÓN EMPLEANDO EXCEL Y GRAPH Cuando se estudian en forma conjunta dos características (variables estadísticas) de una población o muestra, se dice que estamos analizando una variable

Más detalles

Tema 5: Dualidad y sensibilidad de los modelos lineales.

Tema 5: Dualidad y sensibilidad de los modelos lineales. ema 5: Dualidad y sensibilidad de los modelos lineales. Objetivos del tema: Introducir el concepto de Sensibilidad en la Programación Lineal Introducir el concepto de Dualidad en la Programación Lineal

Más detalles

Guía rápida de WinQSB

Guía rápida de WinQSB Guía rápida de WinQSB Puedes descargar la aplicación WinQSB desde nuestra página Web http://www.unizar.es/3w en el enlace Web Docente Herramientas Informáticas... Utilidades Zona de descargas. Para instalar

Más detalles

Tema 2. Espacios Vectoriales. 2.1. Introducción

Tema 2. Espacios Vectoriales. 2.1. Introducción Tema 2 Espacios Vectoriales 2.1. Introducción Estamos habituados en diferentes cursos a trabajar con el concepto de vector. Concretamente sabemos que un vector es un segmento orientado caracterizado por

Más detalles

Si el comando Solver no aparece en el menú Herramientas, deberá instalar la macro automática Solver como sigue:

Si el comando Solver no aparece en el menú Herramientas, deberá instalar la macro automática Solver como sigue: El Solver de Excel El Solver se utiliza para determinar el valor máximo o mínimo de una celda modificando otras celdas; por ejemplo, el beneficio máximo que puede generarse modificando los gastos de publicidad.

Más detalles

&$3Ì78/2 $/*25,7026 (92/87,926 $9$1=$'26 3$5$ 763 6.1. INTRODUCCIÓN

&$3Ì78/2 $/*25,7026 (92/87,926 $9$1=$'26 3$5$ 763 6.1. INTRODUCCIÓN &$3Ì78/2 6.1. INTRODUCCIÓN Los primeros avances para solucionar el TSP, por medio de Algoritmos Evolutivos han sido introducidos por Goldberg y Lingle en [68] y Grefenstette en [72]. En éste área muchos

Más detalles

Tipo de máquina Tiempo disponible. (h/maq. Por semana) Fresadora 500 Torno 350 Rectificadora 150

Tipo de máquina Tiempo disponible. (h/maq. Por semana) Fresadora 500 Torno 350 Rectificadora 150 Ejercicios Tema 1. 1.- Utilizar el procedimiento gráfico para resolver los siguientes P.L. a) Max z = 10x 1 + 20x 2 s.a x 1 + 2x 2 15 x 1 + x 2 12 5x 1 + 3x 2 45 x 1,x 2 0 b) Max z = 2x 1 + x 2 s.a. x

Más detalles

La gestión de proyectos es la rama de la ciencia de la administración que trata de la planificación y el control de proyectos.

La gestión de proyectos es la rama de la ciencia de la administración que trata de la planificación y el control de proyectos. DEFINICIÓN DE PROYECTO Un proyecto es un conjunto de acciones No repetitivas Únicas De duración determinada Formalmente organizadas Que utilizan recursos Podremos considerar un proyecto, a efectos de aplicarle

Más detalles

Matemáticas C.C.S.S. Repaso de Selectividad 1. Se desea obtener dos elementos químicos a partir de las sustancias A y B. Un kilo de A contiene 8

Matemáticas C.C.S.S. Repaso de Selectividad 1. Se desea obtener dos elementos químicos a partir de las sustancias A y B. Un kilo de A contiene 8 Matemáticas C.C.S.S. Repaso de Selectividad 1. Se desea obtener dos elementos químicos a partir de las sustancias A y B. Un kilo de A contiene 8 gramos del primer elemento y 1 gramo del segundo; un kilo

Más detalles

Repaso de matrices, determinantes y sistemas de ecuaciones lineales

Repaso de matrices, determinantes y sistemas de ecuaciones lineales Tema 1 Repaso de matrices, determinantes y sistemas de ecuaciones lineales Comenzamos este primer tema con un problema de motivación. Problema: El aire puro está compuesto esencialmente por un 78 por ciento

Más detalles

Anexo 1: Demostraciones

Anexo 1: Demostraciones 75 Matemáticas I : Álgebra Lineal Anexo 1: Demostraciones Espacios vectoriales Demostración de: Propiedades 89 de la página 41 Propiedades 89- Algunas propiedades que se deducen de las anteriores son:

Más detalles

Programación Entera. P.E pura: Todas las variables de decisión tienen valores enteros.

Programación Entera. P.E pura: Todas las variables de decisión tienen valores enteros. Clase # 7 Programación Entera. Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros. P.E pura: Todas las variables de decisión

Más detalles

INFORMÁTICA. Práctica 5. Programación en C. Grado en Ingeniería en Electrónica y Automática Industrial. Curso 2013-2014. v1.0 (05.03.

INFORMÁTICA. Práctica 5. Programación en C. Grado en Ingeniería en Electrónica y Automática Industrial. Curso 2013-2014. v1.0 (05.03. INFORMÁTICA Práctica 5. Programación en C. Grado en Ingeniería en Electrónica y Automática Industrial Curso 2013-2014 v1.0 (05.03.14) A continuación figuran una serie de ejercicios propuestos, agrupados

Más detalles

Capítulo 12: Indexación y asociación

Capítulo 12: Indexación y asociación Capítulo 12: Indexación y asociación Conceptos básicos Índices ordenados Archivos de índice de árbol B+ Archivos de índice de árbol B Asociación estática Asociación dinámica Comparación entre indexación

Más detalles

Espacios vectoriales y aplicaciones lineales

Espacios vectoriales y aplicaciones lineales Capítulo 3 Espacios vectoriales y aplicaciones lineales 3.1 Espacios vectoriales. Aplicaciones lineales Definición 3.1 Sea V un conjunto dotado de una operación interna + que llamaremos suma, y sea K un

Más detalles

Resolución de Problemas

Resolución de Problemas Introducción Resolución de Problemas La resolución de problemas es una capacidad que consideramos inteligente Somos capaces de resolver problemas muy diferentes Encontrar el camino en un laberinto Resolver

Más detalles

T E C N O L O G Í A OPTIMIZACIÓN DE MATERIALES MEDIANTE PATRONES DE CORTE EFICIENTE. Aplicación. a la INDUSTRIA

T E C N O L O G Í A OPTIMIZACIÓN DE MATERIALES MEDIANTE PATRONES DE CORTE EFICIENTE. Aplicación. a la INDUSTRIA OPTIMIZACIÓN DE MATERIALES MEDIANTE PATRONES DE CORTE EFICIENTE Aplicación a la INDUSTRIA de la construcción 1 El presente estudio propone el uso de un algoritmo comúnmente utilizado en la rama de investigación

Más detalles

Las matrices Parte 1-2 o bachillerato

Las matrices Parte 1-2 o bachillerato Parte 1-2 o bachillerato wwwmathandmatesurlph 2014 1 Introducción Generalidades 2 Definición Ejercicio 1 : Suma de dos matrices cuadradas 2x2 Ejercicio 2 : Suma de dos matrices cuadradas 3x3 Propiedades

Más detalles

OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA. Tema 2 Programación Lineal

OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA. Tema 2 Programación Lineal OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA Tema 2 Programación Lineal ORGANIZACIÓN DEL TEMA Sesiones: Introducción, definición y ejemplos Propiedades y procedimientos de solución Interpretación económica

Más detalles

Algoritmos. Autor: José Ángel Acosta Rodríguez

Algoritmos. Autor: José Ángel Acosta Rodríguez Autor: 2006 ÍNDICE Página Índice 1 Problema 1. Movimiento de figuras geométricas.2 Problema 2. Conversión decimal a binario....3 Problema 3. Secuencias binarias..4 Problema 4. Conversión a binario a octal...

Más detalles

Problemas del transporte

Problemas del transporte Taller 5 PROBLEA 8.- Problemas del transte Es necesario planear el sistema de energía de un nuevo edificio. Las tres fuentes posibles de energía son electricidad, gas natural, y una unidad de celdas solares.

Más detalles

Empresarial y Financiero NIVEL AVANZADO

Empresarial y Financiero NIVEL AVANZADO Curso de Excel Empresarial y Financiero NIVEL AVANZADO Rosa Rodríguez SESION 2: INDICE ANALISIS DE SENSIBILIDAD (3h) Validación de datos n Restricciones a la entrada de datos n Lista Dependiente n Administrador

Más detalles

1. (2 puntos) En la V Caminata Madrileño Manchega, los participantes caminan de Madrid

1. (2 puntos) En la V Caminata Madrileño Manchega, los participantes caminan de Madrid Matemática Discreta Segundo de Ingeniería Informática UAM Curso 2006-2007 Solucionario del examen final del 26-1-2007 Nota bene: A continuación exhibimos algunas de las distintas maneras de abordar los

Más detalles

Espacios generados, dependencia lineal y bases

Espacios generados, dependencia lineal y bases Espacios generados dependencia lineal y bases Departamento de Matemáticas CCIR/ITESM 14 de enero de 2011 Índice 14.1. Introducción............................................... 1 14.2. Espacio Generado............................................

Más detalles

Introducción a la Teoría de Probabilidad

Introducción a la Teoría de Probabilidad Capítulo 1 Introducción a la Teoría de Probabilidad Para la mayoría de la gente, probabilidad es un término vago utilizado en el lenguaje cotidiano para indicar la posibilidad de ocurrencia de un evento

Más detalles

EXPRESIONES ALGEBRAICAS

EXPRESIONES ALGEBRAICAS EXPRESIONES ALGEBRAICAS Un grupo de variables representadas por letras junto con un conjunto de números combinados con operaciones de suma, resta, multiplicación, división, potencia o etracción de raíces

Más detalles

L A P R O G R A M A C I O N

L A P R O G R A M A C I O N L A P R O G R A M A C I O N L I N E A L 1. INTRODUCCIÓN: la programación lineal como método de optimación La complejidad de nuestra sociedad en cuanto a organización general y económica exige disponer

Más detalles

VECTORES. Módulo, dirección y sentido de un vector fijo En un vector fijo se llama módulo del mismo a la longitud del segmento que lo define.

VECTORES. Módulo, dirección y sentido de un vector fijo En un vector fijo se llama módulo del mismo a la longitud del segmento que lo define. VECTORES El estudio de los vectores es uno de tantos conocimientos de las matemáticas que provienen de la física. En esta ciencia se distingue entre magnitudes escalares y magnitudes vectoriales. Se llaman

Más detalles

ANALISIS DE DATOS CON EXCEL

ANALISIS DE DATOS CON EXCEL 1 ANALISIS DE DATOS CON EXCEL 1 USAR FORMULAS Y FUNCIONES PARA CALCULAR VALORES Las funciones son fórmulas predefinidas que ejecutan cálculos utilizando valores específicos, denominados argumentos, en

Más detalles

x + y 4 2x + 3y 10 4x + 2y 12 x 0, y 0

x + y 4 2x + 3y 10 4x + 2y 12 x 0, y 0 PRUEBAS DE ACCESO A LA UNIVERSIDAD PROBLEMAS DE PROGRAMACIÓN LINEAL JUNIO 2000. OPCIÓN B. Una empresa especializada en la fabricación de mobiliario para casas de muñecas, produce cierto tipo de mesas y

Más detalles

Espacios Vectoriales

Espacios Vectoriales Espacios Vectoriales Departamento de Matemáticas, CCIR/ITESM 4 de enero de 2 Índice 3.. Objetivos................................................ 3.2. Motivación...............................................

Más detalles

1. Ecuaciones no lineales

1. Ecuaciones no lineales 1. Ecuaciones no lineales 1.1 Ejercicios resueltos Ejercicio 1.1 Dada la ecuación xe x 1 = 0, se pide: a) Estudiar gráficamente sus raíces reales y acotarlas. b) Aplicar el método de la bisección y acotar

Más detalles

Problemas de Conteo. 1. Problemas

Problemas de Conteo. 1. Problemas Problemas de Conteo 1. Problemas 1. En un torneo de básquetbol compiten 16 equipos. En cada ronda los equipos se dividen en grupos de 4. En cada grupo cada equipo juega una vez contra cada uno de los equipos

Más detalles

Optimización, Solemne 2. Semestre Otoño 2012 Profesores: Paul Bosch, Rodrigo López, Fernando Paredes, Pablo Rey Tiempo: 110 min.

Optimización, Solemne 2. Semestre Otoño 2012 Profesores: Paul Bosch, Rodrigo López, Fernando Paredes, Pablo Rey Tiempo: 110 min. UNIVERSIDAD DIEGO PORTALES. FACULTAD DE INGENIERIA. ESCUELA DE INGENIERIA INDUSTRIAL. Optimización, Solemne. Semestre Otoño Profesores: Paul Bosch, Rodrigo López, Fernando Paredes, Pablo Rey Tiempo: min.

Más detalles

Universidad de Costa Rica Escuela de Matemática ALGEBRA LINEAL. x x1 n. θ y. 1 n x1 n ȳ1 n. Carlos Arce S. William Castillo E. Jorge González V.

Universidad de Costa Rica Escuela de Matemática ALGEBRA LINEAL. x x1 n. θ y. 1 n x1 n ȳ1 n. Carlos Arce S. William Castillo E. Jorge González V. Universidad de Costa Rica Escuela de Matemática ALGEBRA LINEAL x x x1 n θ y y ȳ1 n 1 n x1 n ȳ1 n Carlos Arce S. William Castillo E. Jorge González V. 2003 Algebra Lineal Carlos Arce S., William Castillo

Más detalles

no descompone no descompone no descompone

no descompone no descompone no descompone Problema 1. Sea I n el conjunto de los n primeros números naturales impares. Por ejemplo: I 3 = {1, 3, 5, I 6 = {1, 3, 5, 7, 9, 11, etc. Para qué números n el conjunto I n se puede descomponer en dos partes

Más detalles

Polinomios y Ecuaciones

Polinomios y Ecuaciones Ejercicios de Cálculo 0 Prof. María D. Ferrer G. Polinomios y Ecuaciones.. Polinomios: Un polinomio o función polinómica es una epresión de la forma: n n n P a a a a a a = n + n + n + + + + 0 () Los números

Más detalles

Unidad II: Análisis de Redes

Unidad II: Análisis de Redes Unidad II: Análisis de Redes 2.1 Conceptos Básicos Un problema de redes es aquel que puede representarse por: LA IMPORTANCIA DE LOS MODELOS DE REDES: Muchos problemas comerciales pueden ser resueltos a

Más detalles

Curso Breve de Marco lógico. Visión General

Curso Breve de Marco lógico. Visión General Curso Breve de Marco lógico Visión General Para que sirve el marco Lógico? El Sistema de Marco Lógico es una de las herramientas principales que utilizan las instituciones para diseñar y planificar sus

Más detalles

Apuntes de Matemática Discreta 9. Funciones

Apuntes de Matemática Discreta 9. Funciones Apuntes de Matemática Discreta 9. Funciones Francisco José González Gutiérrez Cádiz, Octubre de 004 Universidad de Cádiz Departamento de Matemáticas ii Lección 9 Funciones Contenido 9.1 Definiciones y

Más detalles

COMBINACIONES página 29 COMBINACIONES

COMBINACIONES página 29 COMBINACIONES página 29 DEFINICIÓN: Dados n elementos, el número de conjuntos que se pueden formar con ellos, tomados der en r, se llaman combinaciones. Por ejemplo, sean cuatro elementos formar con esos cuatro elementos

Más detalles

CPE (SEGUNDO CURSO) PRÁCTICA 0 SOLUCIONES (Curso 2015 2016)

CPE (SEGUNDO CURSO) PRÁCTICA 0 SOLUCIONES (Curso 2015 2016) 1/11 CPE (SEGUNDO CURSO) PRÁCTICA 0 SOLUCIONES (Curso 2015 2016) 1. Considérese una función de n variables f(x 1, x 2,..., x n ). Cuántas derivadas parciales de orden r se pueden calcular? Teniendo en

Más detalles

La ventana de Microsoft Excel

La ventana de Microsoft Excel Actividad N 1 Conceptos básicos de Planilla de Cálculo La ventana del Microsoft Excel y sus partes. Movimiento del cursor. Tipos de datos. Metodología de trabajo con planillas. La ventana de Microsoft

Más detalles

Apuntes de Matemática Discreta 7. Relaciones de Orden

Apuntes de Matemática Discreta 7. Relaciones de Orden Apuntes de Matemática Discreta 7. Relaciones de Orden Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 7 Relaciones de Orden Contenido

Más detalles

1. INVERSA DE UNA MATRIZ REGULAR

1. INVERSA DE UNA MATRIZ REGULAR . INVERSA DE UNA MATRIZ REGULAR Calcular la inversa de una matriz regular es un trabajo bastante tedioso. A través de ejemplos se expondrán diferentes técnicas para calcular la matriz inversa de una matriz

Más detalles

MODELO DE ASIGNACIÓN $A$15:$D$15 < = $A$4:$D$4 $E$11:$E$13 = $E$1:$E$3 METODO DE TRANSPORTE - 129 - ING. José Luís Albornoz Salazar - 130 - - Máxi

MODELO DE ASIGNACIÓN $A$15:$D$15 < = $A$4:$D$4 $E$11:$E$13 = $E$1:$E$3 METODO DE TRANSPORTE - 129 - ING. José Luís Albornoz Salazar - 130 - - Máxi - Máxi En el espacio en blanco, en la parte inferior izquierda, Sujetas a las siguientes Restricciones indique las restricciones o condiciones del problema, para lo cual haga clic en Agregar. METODO DE

Más detalles

- Bases de Datos - - Diseño Físico - Luis D. García

- Bases de Datos - - Diseño Físico - Luis D. García - Diseño Físico - Luis D. García Abril de 2006 Introducción El diseño de una base de datos está compuesto por tres etapas, el Diseño Conceptual, en el cual se descubren la semántica de los datos, definiendo

Más detalles

ÁLGEBRA DE MATRICES. Al consejero A no le gusta ninguno de sus colegas como presidente.

ÁLGEBRA DE MATRICES. Al consejero A no le gusta ninguno de sus colegas como presidente. ÁLGEBRA DE MATRICES Página 49 REFLEXIONA Y RESUELVE Elección de presidente Ayudándote de la tabla, estudia detalladamente los resultados de la votación, analiza algunas características de los participantes

Más detalles

ALGEBRA LINEAL. Héctor Jairo Martínez R. Ana María Sanabria R.

ALGEBRA LINEAL. Héctor Jairo Martínez R. Ana María Sanabria R. ALGEBRA LINEAL Héctor Jairo Martínez R. Ana María Sanabria R. SEGUNDO SEMESTRE 8 Índice general. SISTEMAS DE ECUACIONES LINEALES.. Introducción................................................ Conceptos

Más detalles

Operación Microsoft Access 97

Operación Microsoft Access 97 Trabajar con Informes Características de los informes Un informe es una forma efectiva de presentar los datos en formato impreso. Como se tiene control sobre el tamaño y el aspecto de todos los elementos

Más detalles

Matrices: Conceptos y Operaciones Básicas

Matrices: Conceptos y Operaciones Básicas Matrices: Conceptos y Operaciones Básicas Departamento de Matemáticas, CCIR/ITESM 8 de septiembre de 010 Índice 111 Introducción 1 11 Matriz 1 113 Igualdad entre matrices 11 Matrices especiales 3 115 Suma

Más detalles

Nota : Los fundamentos teóricos fueron tomados del texto INVESTIGACION DE OPERACIONES HILLIER LIEBERMAN. Séptima edición

Nota : Los fundamentos teóricos fueron tomados del texto INVESTIGACION DE OPERACIONES HILLIER LIEBERMAN. Séptima edición MODELOS DE OPTIMIZACIÓN DE REDES Modelos de Optimización de Redes. Pág. 1 Terminología de Redes. 2 Problema de la Ruta Más Corta. 5 Problema del Árbol de Expansión Mínima. 13 Problema de Flujo Máximo.

Más detalles

construcción de programas Prof. Eliana Guzmán U.

construcción de programas Prof. Eliana Guzmán U. Unidad II. Metodología para la construcción de programas Prof. Eliana Guzmán U. Semestre: A-2015 Introducción Resolver un problema con una computadora conduce a la escritura de un programa y a su ejecución.

Más detalles

Ejemplos de conversión de reales a enteros

Ejemplos de conversión de reales a enteros Ejemplos de conversión de reales a enteros Con el siguiente programa se pueden apreciar las diferencias entre las cuatro funciones para convertir de reales a enteros: program convertir_real_a_entero print

Más detalles

3.- DETERMINANTES. a 11 a 22 a 12 a 21

3.- DETERMINANTES. a 11 a 22 a 12 a 21 3.- DETERMINANTES. 3.1. -DEFINICIÓN Dada una matriz cuadrada de orden n, se llama determinante de esta matriz (y se representa por A o deta al polinomio cuyos términos son todos los productos posibles

Más detalles
Sitemap