MÉTODO HEURÍSTICO PARA PROBLEMAS BINARIOS

[pic 1]

TEMA: MÉTODO HEURÍSTICO PARA PROBLEMAS BINARIOS.

EQUIPO 5

JOSÉ AID HERNÁNDEZ DOMÍNGUEZ

ERNESTO GARCÍA SÁENZ

ERICK JESÚS SAUCEDA MÁRQUEZ

JORGE MIGUEL HERNÁNDEZ MARTÍNEZ

RUTH ABIGAIL RUIZ TELLO

NOMBRE DE LA MATERIA:

INVESTIGACION DE OPERACIONES I

NOMBRE DEL DOCENTE ASESOR DE LA MATERIA:

OMAR IGNACIO LUGO VILLAREAL

H MATAMOROS TAMAULIPAS A 11 DE JULIO DE 2021

INTRODUCCIÓN

La programación entera binaria es un método perteneciente a la programación lineal, por lo que su base es un algoritmo matemático que tiene como finalidad resolver un problema indeterminado formulado a través de ecuaciones lineales, optimizando así una función objetivo también lineal que generalmente se refiere a costo o a tiempo. La programación binaria se utiliza en problemas de asignación o de toma de decisiones enfocadas a hacer o no una tarea, entre su campo de aplicación más comunes se encuentra el despacho de envíos, el diseño de redes, la elección de un sitio, el diseño de redes, la ubicación del personal y la programación de actividades, que es la aplicación objeto de estudio en este artículo.

La heurística está diseñada para encontrar buenas soluciones aproximadas de problemas combinatorios difíciles que de lo contrario no pueden resolverse mediante los algoritmos de optimización disponibles. Una heurística es una técnica de búsqueda directa que utiliza reglas favorables prácticas para localizar soluciones mejoradas.

La ventaja de la heurística es que en general determina (buenas) soluciones con rapidez, utilizando reglas de solución simples. La desventaja es que la calidad de la solución (con respecto a la óptima) suele desconocerse. Las primeras generaciones de heurística se basan en la regla de búsqueda codiciosa que dicta que se mejore el valor de la función objetivo con cada movimiento de búsqueda. La búsqueda termina en un óptimo local donde ya no son posibles más mejoras.

En la década de 1980, una nueva generación de metaheurística buscó mejorar la calidad de las soluciones heurísticas al permitir la búsqueda de una trampa de escape en óptimos locales. La ventaja obtenida se logra a expensas de los cálculos incrementados.

MÉTODO HEURÍSTICO PARA PROBLEMAS BINARIOS.

Origen del término “heurístico”

Reciben el nombre de algoritmos heurísticos, metaheurísticos o sencillamente heurísticos. Este término deriva de la palabra griega “heuriskein” que significa encontrar o descubrir y se usa en el ámbito de la optimización para describir una clase de algoritmos de resolución de problemas.

Definición

Ciencia que estudia los procesos de decisión respecto a un campo de conocimiento concreto, como son las estrategias cognitivas. Su contrapartida formal en computación es el algoritmo.

Por heurística entendemos una estrategia, método, usado para hacer más sencilla la solución de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los humanos para resolver problemas complejos. En este caso el adjetivo heurístico significa medio para descubrir.

Programación Entera Binaria (PEB)

En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 0-1. Son de particular interés debido a que se pueden usar las variables 0-1 para representar decisiones dicotómicas (sí o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0-1

¿Qué son los algoritmos heurísticos?

Debido a la existencia de algunos problemas importantes con un gran interés práctico difíciles de resolver, comienzan a surgir algoritmos capaces de ofrecer posibles soluciones que, aunque no consiguen el resultado óptimo, sí que se acercan en un tiempo de cálculo razonable. Estos algoritmos están basados en el conocimiento heurístico y por lo tanto reciben el nombre de algoritmos heurísticos.

Procedimiento:

Un método heurístico es un conjunto de pasos que deben realizarse para identificar en el menor tiempo posible una solución de alta calidad para un determinado problema.

El método heurístico conocido como "IDEAL", formulado por Bransford y Stein (1984), incluye cinco pasos: Identificar el problema; definir y presentar el problema; explorar las estrategias viables; avanzar en las estrategias; y lograr la solución y volver para evaluar los efectos de las actividades (Bransford & Stein, 1984).

El matemático Pólya (1957) también formuló un método heurístico para resolver problemas que se aproxima mucho al ciclo utilizado para programar computadores.

Según Pólya (1957), cuando se resuelven problemas, intervienen cuatro operaciones mentales:

1. Entender el problema

2. Trazar un plan

3. Ejecutar el plan (resolver)

4. Revisar

1. COMPRENDER EL PROBLEMA.

a) Leer el problema varias veces.

b) Establecer los datos del problema.

c) Aclarar lo que se va a resolver (¿Cuál es la pregunta?).

d) Precisar el resultado que se desea lograr.

e) Determinar la incógnita del problema.

f) Organizar la información

g) Agrupar los datos en categorías

h) Trazar una figura o diagrama.

2. HACER EL PLAN.

i) Escoger y decidir las operaciones a efectuar.

j) Eliminar los datos inútiles.

k) Descomponer el problema en otros más pequeños.

3. EJECUTAR EL PLAN (Resolver).

l) Ejecutar en detalle cada operación.

m) Simplificar antes de calcular.

n) Realizar un dibujo o diagrama.

4. ANALIZAR LA SOLUCIÓN (Revisar).

ñ) Dar una respuesta completa

o) Hallar el mismo resultado de otra manera.

...