Resolución del Ejercicio 2.
2 del Libro "Formulación y Resolución de
Modelos de Programación Matemática en Ingeniería y Ciencia"
Introducción
Este documento presenta la resolució n del Ejercicio 2.2 del libro "Formulació n y Resolució n
de Modelos de Programació n Matemá tica en Ingeniería y Ciencia" de Enrique Castillo et al.,
utilizando el algoritmo de Branch and Bound con un nivel de discrepancia α=3.
Definiciones y Conceptos Relevantes
El problema a resolver consiste en identificar los síntomas relevantes que permiten
distinguir entre diferentes enfermedades. La identificació n se realiza minimizando el
nú mero de síntomas seleccionados, de manera que el conjunto de síntomas relevantes
permita distinguir todas las enfermedades con un nivel de discrepancia α=3.
Formulación Matemática del Problema
Sea D = {D1, D2, ..., Dn} un conjunto conocido de posibles enfermedades. Considérese que
los médicos, al identificar las enfermedades asociadas a un conjunto de pacientes, basan su
decisió n normalmente en un conjunto de síntomas S = {S1, S2, ..., Sm}.
Considérese que se quiere identificar un nú mero mínimo de síntomas Sa ⊆ S, de tal manera
que cada enfermedad puede distinguirse perfectamente de las otras de acuerdo con los
niveles de los síntomas en el conjunto Sa. Determinar el nú mero mínimo de síntomas es
importante ya que da lugar a un coste mínimo de diagnó stico.
Algoritmo de Branch and Bound
Formulación de la Función Objetivo y Restricciones
La funció n objetivo a minimizar es:
Z = Σ xj
Sujeto a las siguientes restricciones:
Σ xj * dijk ≥ α, para todos i, k ∈ {1, 2, ..., n}, i ≠ k
donde:
xj = 1 si el síntoma j pertenece a Sa, 0 si no pertenece
dijk = nivel de discrepancia entre las enfermedades i y k debido al síntoma j
División del Problema en Subproblemas (Ramas)
El problema se divide en subproblemas seleccionando diferentes síntomas en cada rama.
Por ejemplo:
Rama 1: Seleccionar el síntoma S1.
Rama 2: Seleccionar el síntoma S2.
Y así sucesivamente.
Evaluación de los Límites de Cada Subproblema
Para cada subproblema, se evalú an los límites para determinar si se puede descartar o si se
debe seguir explorando. Se calcula la discrepancia acumulada y se compara con el nivel de
discrepancia α=3.
Selección de la Mejor Solución Encontrada
Se selecciona la mejor solució n encontrada que cumple con las restricciones, minimizando
el nú mero de síntomas seleccionados. En este caso, se identifican los síntomas mínimos
necesarios para distinguir entre todas las enfermedades.
Árbol Generado con la Solución en Cada Nodo
El siguiente á rbol muestra el proceso de Branch and Bound, indicando la selecció n de
síntomas en cada nodo y la evaluació n de los límites.
Tablas con los Datos del Problema
A continuació n se presentan las tablas con los datos del problema:
Tabla 2.1: Síntomas asociados a todas las enfermedades del ejemplo 2.2
Enferm S1 S2 S3 S4 S5 S6 S7 S8
edad
D1 1 0 0 0 1 1 0 1
D2 1 1 1 1 0 0 1 1
D3 0 2 2 2 2 2 3 3
D4 2 2 3 3 3 2 3 3
D5 1 1 1 1 1 1 2 2
Tabla 2.2: Síntomas relevantes para todas las enfermedades en el ejemplo 2.2 para α=1
Enfermedad Síntomas relevantes
D1 {2}
D2 {5}
D3 {2}
D4 {2}
D5 {2,5}
Resultados y Conclusiones
El algoritmo de Branch and Bound permitió identificar el conjunto mínimo de síntomas
necesarios para distinguir entre todas las enfermedades con un nivel de discrepancia α=3.
Este enfoque garantiza una solució n ó ptima al problema, minimizando el nú mero de
síntomas seleccionados y asegurando un diagnó stico preciso.
Tabla de Síntomas Relevantes para α = 3
A continuació n se presentan los síntomas relevantes para distinguir entre las enfermedades
con un nivel de discrepancia α = 3:
Enfermedad Síntomas relevantes
D1 {2, 5}
D2 {3, 5}
D3 {2, 4}
D4 {2, 3}
D5 {2, 5}
