• Author / Uploaded
• MishaelPrada

Citation preview

Problema de la mochila desarrollado con el software WINQSB

INGENIERIA DE SISTEMAS Programación Dinámica Integrantes:  Bravo medina Cinthya  Ilatoma Fustamante  Prada Salazar Cesar

1

Contenido INTRODUCCION ............................................................................................................................2 Problema de la mochila simple ................................................................................................3 Problema de la mochila de múltiple elección ...............................................................................4 Métodos de Resolución................................................................................................................4 Este problema se ha resuelto tradicionalmente mediante programación lineal entera. ..........................................................4 Algoritmos voraces ...................................................................................................................4 a) Aplicación del método: .....................................................................................................4 b) Concepto de solución óptima: .........................................................................................5 Algoritmos genéticos .............................................................................................................5 Programación dinámica............................................................................................................6 Utilizando el Software WINQSB ...................................................................................................7

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

2

INTRODUCCION En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Historia El problema de la mochila es uno de los21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972.1 Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathew Ballard. Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación.

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

3

Problema de la mochila simple Un problema de la mochila 0-1, si para cada tipo de ítem el beneficio y los pesos son idénticos (vi=wi), entonces el problema quedaría formulado de la siguiente forma

Por tanto si existe un vector xi tal que, entonces esa será una solución al problema. Si existe una solución xi de este tipo, resolver el problema de la mochila realmente es resolver el problema de la suma de subconjuntos. Además si el conjunto de los pesos de los elementos es una secuencia supe creciente, es decir, se verifica que:

Entonces se dice que se trata de un problema de la mochila simple o también problema de la mochila tramposa. Este tipo de problemas tiene importantes aplicaciones en el mundo de la criptografía.

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

4

Problema de la mochila de múltiple elección Si en un problema de la mochila 0-1 los ítems están subdivididos en k clases, denotadas por Ni, y exactamente un ítem tienen que ser tomado de cada clase, entonces hablamos del problema de la mochila de múltiple elección.

Métodos de Resolución Este problema se ha resuelto tradicionalmente mediante programación lineal entera. El hecho de que se trate de programación lineal hace referencia a que la función a optimizar y las inecuaciones que constituyen las restricciones han de ser lineales, es decir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad. Existe otra forma de resolver este tipo de problema, a través de los denominados algoritmos voraces. Una aproximación voraz consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma. Con este método no siempre es posible dar una solución a un problema. Otro sistema para resolver el problema de la mochila es mediante algoritmos genéticos que son métodos de optimización que tratan de hallar (xi,..., en) tales que sea máximo. Algoritmos voraces a) Aplicación del método:

Partimos de la formulación del problema de la mochila aportada anteriormente:

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

5

La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto. b) Concepto de solución óptima:

Teorema: si se ordenan los objetos de forma de decreciente en cuanto a su relación (utilidad/ponderación = vi/ci) y se introducen en la mochila enteros en este orden mientras quepan y cuando no quede capacidad para uno entero se añade la porción que aún tenga cabida el resultado al que se llega es una solución óptima. Algoritmos genéticos Consisten en métodos adaptativos de optimización que tratan de hallar (xi,..., en) tales que [Sumatoria (bi*xi) desde i= 1 hasta n] sea máximo. Pueden usarse para resolver problemas de búsqueda y optimización. Se basan en el proceso genético de los organismos vivos, por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Para utilizar un algoritmo genético hacen falta tres elementos: Descripción de la población de individuos: cada individuo representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución. Función de evaluación (llamada función de ajuste): encontrar una expresión matemática que puntúe a cada individuo de forma que nuestro ideal sea un máximo o un mínimo. Selección o Mecanismos de reproducción: la función de selección de padres más utilizada, es la denominada función de selección proporcional a la función objetivo, en la cual cada individuo tiene una probabilidad de ser seleccionado como padre que es proporcional al valor de su función objetivo, es decir, indica que cada objeto de la mochila tendrá una probabilidad de ser seleccionado que dependerá de la relación que exista entre beneficios y el peso que ocupa.

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

6

Programación dinámica

Una subestructura óptima significa que se pueden usar soluciones óptimas de sub problemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos: 1. Dividir el problema en subproblemas más pequeños. 2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente. 3. Usar estas soluciones óptimas para construir una solución óptima al problema original. Los su problemas se resuelven a su vez dividiéndolos en su problemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial. Decir que un problema tiene sus problemas superpuestos es decir que se usa un mismo su problema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya sub problemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a problemas que ya han sido resueltos anteriormente. Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memorización (no confundir con memorización; en inglés es llamado memorización,). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que de antemano sabemos que vamos a necesitar.

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

7

Utilizando el Software WINQSB

120

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

8

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

9

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

10

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II

11

INGENIERIA DE SISTEMAS

INVESTIGACION DE OPERACIONES II