Page 14 - CADENA DE SUMINISTROS
P. 14
INGENIERIA EN Página 13
GESTIÒN EMPRESARIAL
1.3 LA PROGRAMACIÓN DINÁMICA APLICADA A PROBLEMAS DE REDES.
1.3.1 El problema de la mochila de Knapsack.
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 finito 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.
Definición.
Knapsack problem:“Empacado de objetos dentro de la mochila”
El problema de la mochila es definido formalmente como: Se tiene una determinada instancia de
KPcon un conjunto de objetos N, que consiste de n objetos j con ganancia pj y peso wj, y una
capacidad c. (Usualmente, los valores toman números enteros positivos). El objetivo es
seleccionar un subconjunto de N tal que la ganancia total de esos objetos seleccionados es
maximizado y el total de los pesos no excede a c.
1.3.2 RUTA MÁS CORTA.
El método de la ruta más corta es un método de programación lineal, que permite buscar la
solución a un problema de optimización que resulte de una combinatoria y de diferentes
aplicaciones, el objetivo de este método está en encontrar rutas cortas o de menor costo, según
sea el caso, que va desde un nodo especifico hasta cada uno de los demás nodos de la red. En
este sentido un nodo es una representación gráfica en forma de circulo, este nodo es muy
importante ya que denota los orígenes y destinos del problema que se realice, asimismo una red
representa un conjunto de puntos y líneas que conectan pares de puntos, estos puntos son los
que llamaremos nodos y las líneas serían las aristas., por ejemplo:
CADENA DE SUMINISTROS | MTRA. NADIA Y. HERNÀNDEZ OSORIO
