View
32
Download
11
Category
Preview:
DESCRIPTION
La exclusión mutua se refiere a la posibilidad de que múltiples procesos (o hilos) compartan código, recursos, o datos de forma de que sólo uno de ellos tenga acceso al objeto compartido en cada momento.En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo para dar apariencia de ejecución simultánea. Aunque no se consigue un procesado en paralelo real, y aunque se produce un sobrecargado en la cpu por el hecho de tener que cambiar de tarea constantemente, las ventajas de todo esto son muy elevadas.
Citation preview
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 1
PROGRAMACIÓN DINÁMICA, PROBLEMA DE LA MOCHILA
Objetivo:
Desarrollar ejercicios de programación dinámica haciendo uso de herramientas informáticas como WinQSB, Solver y Lindo para obtener soluciones óptimas.
Resumen: El modelo de la mochila tiene que ver clásicamente con el hecho de determinar los artículos más valiosos que un combatiente carga en una mochila. El problema representa un modelo de asignación de recursos general en el cual se utilizan recursos limitados por varias actividades económicas
∑
∑
{ }
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 2
Ejemplo: La carga de un avión se distribuye con el propósito de maximizar el ingreso total. Se consideran 5 elementos y solo se necesita uno de cada uno. La compañía gana S/ 5,000 por elemento más una bonificación por elemento. El avión puede transportar 2,000 Kilos
Elemento Peso Kilos Volumen m3 Bonificación
A 1000 70 700
B 1100 100 800
C 700 100 1100
D 800 80 1000
E 500 50 700
a) ¿Cuáles elementos deben transportarse? b) Si se considera un peso máximo de 2,000 kilos ¿Cuáles elementos deben transportarse?
Desarrollando el programa usando programación lineal se tiene:
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 3
Seleccionar el tipo de problema.
Elegir el Paquete de Dynamic
Programming
Problema de la mochila
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 4
Ingresar un título del problema y el número
de items
Variables que indican decisión
El retorno o función a maximizar
Unidades disponibles
Capacidad máxima
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 5
Luego presionar en la opción “Solve and Analyze” para solucionar el problema, se obtiene el siguiente resultado.
La solución nos indica que se deben transportar los ítems c,d,e con un retorno total de S/ 17,800 Luego considerando un volumen máximo de 120 m3 Y ingresando los valores en la matriz como se indica.
Valor Retornado
Presionar Solve and Analyze
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 6
Se obtiene la siguiente solución con un valor de retorno de S/ 11,400
Valor de Retorno
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 7
El problema de la mochila puede ser desarrollado usando el solver de la hoja de cálculo excel
Ingresar los valores de la siguiente manera para poder hacer uso del Solver.
La celda G5 almacenara la el valor optimo del problema
Hacer uso de la función “sumaproducto” para la
multiplicación de vectores
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 8
Realizar el ingreso de las restricciones que se necesita en el solver con datos binarios
Método Simplex
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 9
El valor optimo obtenido con los elementos que se deben considerar C, D,E
Presionar Resolver para la solución
Valor de Retorno
Elementos seleccionados
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 10
Ejercicio 1 Un excursionista planea salir de campamento. Hay cinco artículos que desea llevar consigo, pero entre todos sobrepasan las 60 libras que considera puede cargar. Para ayudarse en la selección ha asignado un valor a cada artículo en orden ascendente de importancia.
Articulo a b c d e
Peso 42 23 21 15 7
Valor 100 60 70 15 15
Ejercicio 2 Un excursionista debe determinar que objetos debe llevar consigo en la mochila para realizar una excursión de un día. Cada uno de los objetos tiene asociado un peso y una utilidad personal para el excursionista. Los objetos que puede llevar, así como su peso y utilidad son los que se recogen en la tabla siguiente:
objeto peso utilidad
linterna 40 40
saco 50 80
cocina 30 10
manta 10 10
comida 10 4
ropa 40 20
varios 30 60
Sabiendo que el peso máximo que puede llevar en la mochila es de 100. Determinar que objetos debe llevar nuestro excursionista en la mochila para que la utilidad de los objetos sea Máxima Ejercicio 3 Mochila de capacidad W=15;
objeto a b c d e f
peso 3 7 4 2 1 3
Beneficio 12 3 7 4 3 8
Universidad Nacional Jorge Basadre Grohmann Facultad de Ingeniería/E.A.P de Ingeniería en Informática y Sistemas Asignatura: Investigación Operativa II Ciclo : Tercero- 2015
Página: 11
Ejercicio 4 Mochila de capacidad W=225;
objeto a b c d e f
peso 51 119 68 34 17 102
Beneficio 204 51 119 68 51 136
Ejercicio 5 Mochila de capacidad W=1000;
objeto a b c d e f
peso 130 570 140 200 360 400
Beneficio 120 300 570 423 300 800
Recommended