Metodos Heuristicos

Contenido
MÉTODOS HEURÍSTICOS 2
Procedimiento heurísticos 5
Reglas de despacho 6
BIBLIOGRAFÍA 7

MÉTODOS HEURÍSTICOS
El problema de reaprovisionamiento multiproducto ha sido estudiado por más de 20 años y existen varios algoritmos heurísticos para resolver instancias de este problema.
Entre los modelos heurísticos más utilizados para enfrentar problemas de demanda variable seencuentran:
a) algoritmo Silver - Meal, o menor costo por periodo (Silver and Meal, 1973);
b) heurístico menor costo por unidad (Silver and Miltenburg, 1984);
c) heurístico balance parte - periodo (DeMatteis, 1968; Mendoza,1968), entre otros.
Un método heurístico es un enfoque   que aprovecha la estructura del problema. Mediante el uso de un conjunto de reglas “racionales”, obteniendo unasolución buena, es decir cercana a la óptima o en ocasiones la optima.
Los métodos heurísticos se usan cuando no es posible o no es computacionalmente factible obtener el óptimo.
Podemos definir una heurística como una técnica que aumenta la eficiencia de un proceso de búsqueda, posiblemente sacrificando demandas de completitud. Las heurísticas son como los guías de turismo: resultan adecuadosen el sentido de que generalmente suelen indicar las rutas interesantes; son malos en el sentido de que pueden olvidar puntos de interés para ciertas personas. Al usar buenas heurísticas se pueden expresar buenas (aunque posiblemente no óptimas) soluciones a problemas difíciles, como el del viajante de comercio.
Una función heurística es una correspondencia entre las descripciones de estados delproblema hacia alguna medida de deseabilidad, normalmente representada por números. Quiere decir que mensura cada estado del problema (solución) y dice qué tan cerca de la solución óptima está.
El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección más provechosa sugiriendo qué camino tomar cuando hay más de uno disponible. Cuanto más exactamente estimela función heurística los méritos de cada nodo del árbol (o grafo) que representa al problema, más directo será el proceso de solución. En general, hay que hacer una ponderación entre el costo de evaluación de una función heurística y el ahorro de tiempo de búsqueda que proporciona la función.
En un problema de minimización, el valor de la solución obtenida por la heurística es menor o igual queuna constante multiplicada por el verdadero valor óptimo. Esa constante se llama constante de calidad
Si llamamos:
OPT = Valor óptimo real.
HEUR = Valor encontrado por la heurística como óptimo.
K = Constante de calidad.
Sabemos que HEUR < K · OPT.
La constante de calidad nos da un límite superior en el error que podemos llegar a tener entre la solución óptima verdadera y la encontradapor la heurística.
Si para una función heurística se puede encontrar un valor de K que permanezca constante para todos los problemas de un mismo tipo, sin influencia del tamaño del problema o de otros factores, diremos que esa heurística tiene garantía de calidad.
Las heurísticas nos podían ayudar a conocer el problema, pues bien, existen dos formas fundamentales de incorporación de conocimientoheurístico específico del dominio a un proceso de búsqueda basado en reglas:
* En las mismas reglas (si sabemos diferenciar entre movimientos legales que son los que se pueden hacer, y movimientos “sensatos” que son los que nos van a llevar más rápida y seguramente a una solución óptima).
* Como una función heurística que evalúa los estados individuales del problema y determina su gradode “deseabilidad”.
Los algoritmos heurísticos se juzgan por su calidad y eficacia.
Hay dos enfoques principales para los problemas de programación que son: estático y dinámico.
* La programación estática consiste en un conjunto fijo de tareas que hay que programar hasta que se completen.
* La programación dinámica se refiere a una situación continua; se agregan continuamente nuevas...