ma3701-optimizacion

PROGRAMADECURSO

Código NombreMA3701 OptimizaciónNombreenInglésOptimization

SCTUnidadesDocentes

HorasdeCátedra

HorasDocenciaAuxiliar

HorasdeTrabajoPersonal

6 10 3 2 5Requisitos CarácterdelCurso

MA2002CálculoAvanzadoyAplicaciones

CFB,cursodeLicenciaturaobligatorioparaIngenieríaCivilMatemática

ResultadosdeAprendizajeEl alumno sabrá resolver problemáticas que aparecen en el modelamiento deproblemas de ingeniería con herramientas de optimización lineal y no‐lineal tantocontinuacomoentera,conosinrestricciones,yutilizaralgunosalgoritmosadecuados.El alumno sabrá utilizar paquetes computacionales útiles en la resolución deproblemasdeoptimización.

MetodologíaDocente EvaluaciónGeneralClasesteóricas,demostrandosolamenteloesencialyejerciciosparatrabajopersonal.UnatareaconsistenteenmodelarcompletamenteunproblemacomplejoyresolverlousandosoftwarelibredelaWeb.

Trescontrolesyunexamen.Notadetarea:20%,seapruebaporseparado.

ResumendeUnidadesTemáticas

Número NombredelaUnidad DuraciónenSemanas

1 Principalesclasesdeproblemasenprogramaciónmatemática. 1.02 ProgramaciónLineal 6.03 Introducciónalosproblemaslienalesdegrantamaño 1.04 Optimizaciónsinrestricciones 3.05 Optimizaciónconrestricciones 3.06 Programacióndinámica 1.0 TOTAL 15.0

UnidadesTemáticas

Número NombredelaUnidad DuraciónenSemanas1 Principalesclasesdeproblemasenprogramación

matemática.1.0

ContenidosResultadosdeAprendizajesdela

UnidadReferenciasalaBibliografía

1.1 Resolucióndeproblemas

simplesdeprogramaciónlineal,programaciónenterayprogramaciónno‐linealconosinrestricciones.

1.2 Ejemplosdeproblemas

reales.

Elalumnodeberácomprenderyclasificarlosdistintostiposdeproblemasdeoptimización

(lienales,enteros,nolineales,estructurasdegrafos,etc).

WagnerHillier‐

Liebermann

Número NombredelaUnidad DuraciónenSemanas2 ProgramaciónLineal 6.0



2.1 ElmétodoSimplex:desarrollo

analíticoeinterpretacióngráfica.

2.2 Problemadual:

planteamientoypropiedadesconrespectoalprimal.InterpretaciónEconómica.

2.3 Nocionesdeanálisispost‐

optimal(variacióndelladoderecho,variacióndeloscostos,agregarcolumna,agregarfila).

2.4 Aplicacionesalaproduccióny

eltransporte.

ElalumnocomprendeelalgoritmoSimplexysuaplicaciónadiferentestiposdeproblemas,incluyendoproblemasdeflujosenredesyparaproblemasdeprogramaciónentera.Sabedistinguircomprendereinterpretarlanocióndedualidad.Elalumnopuedehaceranálisisdesensibilidadencasossimples,atravésdelcualcomprendeelconceptodeestabilidad.

Chvatal

2.5 Nocióndegrafoyproblemas

linealesrepresentablesengrafos(enunciarproblemaflujodecostomínimoyloscasosparticulares:transporte,asignación,caminomáscorto,flujomáximo).

2.6 Algoritmosdeflujosenredes:

transporte,flujomáximo,caminomáscorto.

2.7 Motivosdeno‐linealidaden

grafos.

2.8 Programaciónlinealentera:métododeramificaciónyacotamiento.Verloatravésdeunejemploilustrativo.

Número NombredelaUnidad DuraciónenSemanas3 Introducciónalosproblemaslienalesdegran

tamaño1.0



3.1 Introducción.3.2 Nocióndedescomposición.

EntreellosDantzig‐Wolfe.

3.3 Ejemplos

Elalumnosabeidentificarcasosdeoptimizaciónlinealenlaquesepuedenaplicarmétodosde

descomposición.

Número NombredelaUnidad DuraciónenSemanas4 Optimizaciónsinrestricciones 3.0



3.1 CondicionesdeOptimalidadde1er.y2do.orden.3.2 Nocionesdebúsqueda

Elalumnoconoceyaplicalanoción

fundamentaldealgoritmosdedescenso,

basadoenlabúsquedasobreuna

unidimensional:Golstein‐Armijo,dicotomía,Fibonacciyotras.

3.3 Métododelgradienteysutasadeconvergencia(lineal).

3.4 Familiadealgoritmosdetipogradienteconjugado.Ejemplo:algoritmodeFletcheryReevesyotros.

3.5 AlgoritmodeNewton,cuasi‐Newton(DFPyBFGS)ytasasdeconvergencia(convergenciacuadráticaencasoparticulardeNewton).

direccióndada.

Conoceyaplicalascondicionesdeoptimalidaddeprimerysegundoordenenelcasodiferenciableyseintroducelaideaenelcasono

diferenciable.

Elalumnocomprendelosdistintosconceptosdelostipos

deconvergencia:lineal,superlioneal,cuadráticaatravésde

larevisióndemétodosespecíficos.

Número NombredelaUnidad DuraciónenSemanas5 Optimizaciónconrestricciones 3.0



4.1 Nocionesdeconvexidadyseparacióndeconvexos.TeoremadeFarkas.

4.2 CondicionesdeOptimalidad

de1erorden.Definiciones:direcciónadmisible,direccióndedescenso.TeoremadeKarush‐

Kuhn‐Tucker.

4.3 Nocionesdesensibilidadeinterpretacióneconómica.

4.4 Métododedireccionesadmisibles(casorestricciones

lineales).

4.5 Métododepenalidad,barrera.

4.6 Introduccióndelconceptodesub‐gradienteyoptimizaciónno‐

diferenciable.

Elalumnocomprendecabalmentelascondicionesnecesariasysuficientesdeoptimalidadconrestricciones.Conocelosconceptosdedirecciónadmisible,direccióndedescensoyengeneralcomoseconstruyeelTeoremadeKuhn‐Tuckercomounaideadeseparacióndeconvexos.SabelaslimitacionesdelTeoremadeKuhn‐Tuckeryconocealgunasdesusaplicacioneseneconomía.Conoceyaplicacorrectamentemétodosdedireccionesclásicos,dedireccionsadmisiblesydepenalizacióndebarrera.

Número NombredelaUnidad DuraciónenSemanas

6 Programacióndinámica 1.0



5.1 Fundamentosteóricosdelaprogramacióndinámica:optimalidad,nocióndeestado,ecuaciónfuncional(principiodeBellman).

5.2 Aplicaciones:problemadelamochila,problemadeproducción,portafoliodeinversiones,etc.

Elalumnoconocelasnocionesbásicasdelaprogramación

dinámicayelPrincipiodeBellman.

Bibliografía

• Bazaraa,M.ySheltly,C.,NonlinearProgramming,Wiley,(1979).• Chvatal,V.,LinearProgramming,Freeman&Co.(1983).• Dakin,R.,ATreeSearchAlgorithmforMixedIntegerProgrammingProblems.The

ComputerJournal8(1965),250‐255.• Hillier,F.,Lieberman,G.,IntroducciónalaInvestigacióndeOperaciones,McgrawHill‐

Interamericana,6ed,1997.• Luenberger,D.,IntroductiontoLinearandNonlinearProgramming,Addison‐Wesley,

(1973).• Marsten,R.&Morin,T.,AHybridApproachtoDiscreteMathematicalProgramming.

MathematicalProgramming14(:1)(1978),21‐40.• McCormick,G.,NonlinearProgramming,JohnWiley(1983).NewYork,MacGraw‐Hill,

1970.• Minoux,M.,ProgrammationMathematique,TomoIyII.Dunod(1983).• Murthy,K.,LinearandCombinatorialProgramming,Wiley,(1976).• Ortega,J.M.,Rheinbolt,W.C.,IterativesolutionofnonlinearequationsofSeveral

Variables.NewYork,AcademicPress,(1970).• Polak,E.,ComputationalMethodsinoptimization.NewYork,AcademicPress,(1971).• Rockafellar,R.T.,ConvexAnalysis.NewJersey,PrincetonUniversityPress,(1970).• Shapiro,J.F.,MathematicalProgramming:Structuresandalgorithms,JohnWiley&

Sons,(1979).• Wagner,H.,PrinciplesofOperationsResearch,PrenticeHall,(1975).

Vigenciadesde: Primavera2009Elaboradopor: JorgaAmayaRevisadopor: AxelOsses(JefeDocente)

ma3701-optimizacion

Documents