Metodos numéricos

Métodos matemátcos
José Antono López Ortí

Departamento De matemáticas Cod d’assgnatura 321

José Antono López Ortí - ISBN: 978-84-693-4783-6



Métodos matemátcos - UJI

Edita: Publicacions de la Universitat Jaume I. Servei de Comunicació i Publicacions Campus del Riu Sec. Edifici Rectorat i Serveis Centrals. 12071 Castelló de la Plana http://www.tenda.uji.es e-mail:publicacions@uji.es Col·lecció Sapientia, 41 Primera edició, 2010 www.sapientia.uji.es ISBN: 978-84-693-4783-6

Aquest text està subjecte a una llicència Reconeixement-NoComercial-Compartir Igual de Creative Commons, que permet copiar, distribuir i comunicar públicament l’obra sempre que especifique l’autor i el nom de la publicació i sense objectius comercials, i també permet crear obres derivades,sempre que siguen distribuïdes amb aquesta mateixa llicència. http://creativecommons.org/licenses/by-nc-sa/2.5/es/deed.ca

José Antono López Ortí - ISBN: 978-84-693-4783-6



Métodos matemátcos - UJI

´ Indice General
1. Teor´a de grafos ı 1.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . . o 1.2. Grafos y d´grafos . . . . . . . . . . . . . . . . . . ı 1.2.1. Definicionesgenerales . . . . . . . . . . . 1.2.2. Matriz de adyacencia y matriz de incidencia 1.2.3. Operaciones con grafos . . . . . . . . . . . 1.2.4. Grafos con nombre propio . . . . . . . . . 1.2.5. Grafos generales . . . . . . . . . . . . . . 1.2.6. D´grafos . . . . . . . . . . . . . . . . . . . ı 1.3. Recorridos en grafos y d´grafos. Conexi´ n . . . . . ı o 1.3.1. Secuencias de aristas, colas ytrayectorias . 1.3.2. Conexi´ n . . . . . . . . . . . . . . . . . . o 1.4. Grafos eulerianos y hamiltonianos . . . . . . . . . ´ 1.5. Arboles . . . . . . . . . . . . . . . . . . . . . . . 2. Grafos ponderados y redes 2.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . o 2.2. Grafos ponderados . . . . . . . . . . . . . . . . 2.2.1. El problema del conector m´nimo . . . . ı 2.2.2. El problema delcamino m´ s corto . . . . a 2.3. Optimizaci´ n en d´grafos . . . . . . . . . . . . . o ı 2.3.1. El problema de la trayectoria cr´tica . . . ı 2.3.2. El problema del flujo m´ ximo en una red a 3. Programaci´ n lineal o 3.1. Introducci´ n . . . . . . . . . . . . . . . . . . . o 3.2. Conjuntos convexos . . . . . . . . . . . . . . . 3.3. Programaci´ n lineal . . . . . . . . . . . . . . . o 3.3.1.Algoritmo del simplex . . . . . . . . . 3.3.2. Algoritmo del simplex: forma abstracta 3.3.3. Algoritmo del simplex: m´ todo tabular e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 5 6 11 14 15 17 17 19 27 31 34 34 34 35 42 45 47 48 57 57 58 66 71 74 76

4. Programaci´ n entera o 87 4.1. Introducci´ n . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 87 o 4.2. M´ todo de ramificaci´ n . . . . . . . . . . . . . . . . . . . . . . . . 88 e o 4.3. M´ todo del plano de corte . . . . . . . . . . . . . . . . . . . . . . 101 e

M´ todos Matem´ ticos – 321 - ISBN: 978-84-693-4783-6 e José Antono López Ortí a 2009/2010

I



Métodos � UJI matemátcos - UJI c

5. Resoluci´ n de ecuaciones o 5.1. Introducci´ n . .. . . . . . . . . . . . . o 5.2. M´ todos cerrados. . . . . . . . . . . . . e 5.2.1. M´ todo de bisecci´ n . . . . . . e o 5.2.2. M´ todo de la regula falsi . . . . e 5.3. M´ todos abiertos . . . . . . . . . . . . e 5.3.1. M´ todo de Newton . . . . . . . e 5.3.2. M´ todo de Newton modificado . e 5.3.3. M´ todo de la secante . . . . . . e 5.3.4. M´ todos de punto fijo . . . . . e 5.4. Sistemas de...