Upload
gastonvertiz
View
221
Download
2
Embed Size (px)
DESCRIPTION
Este archivo contiene
Citation preview
U P C
U P C FIB. MIOPD
(3.a) PROGRAMACIN LINEAL ENTERA: MTODOS
INTRODUCCIN.
MTODO DE BRANCH & BOUND.
Conjunto factible y Relajacin lineal de un PLE.
Particin y rbol de exploracin. Incumbente.
Algoritmo bsico de B & B.
Ejemplos.
U P CU P C FIB. MIOPD
INTRODUCCIN.
Definicin de PLE
U P C a U P C FIB. MIOPD i
Algoritmos exactos: Aseguran la obtencin de la soluci ptima Coste computacional elevado (exponencial). B&B , Planos Secantes ,...
Algoritmos de aproximacin: Solucin subptima con estimacin de su calidad. Coste computacional razonable (polinmico). Relajacin Lagrangiana , ...
Heursticas: Solucin subptima sin estimacin de su calidad. Los ms rpidos. Mtodes de bsqueda local, algoritmos
genticos,...
CATEGORIAS DE ALGORITMOS PARA PLE
U P CU P C FIB.MIOPD i
U P C I.O.E. Diploma U P C FIB. MIOPD i
RBOL DE EXPLORACIN
Nodo 0
Nodo 1
Nodo 2
Nodo 3
Nodo 3
Nodo 4
tresteveSESIN DE PROBLEMAS
Nudo 2
Nudo 4
Nudo 4
Nudo 2
Soluciones:
^C