Algoritmo Simplex
Páginas: 70 (17346 palabras)
Publicado: 19 de abril de 2012
L’algoritme símplex.
Fonaments i metodologia
Daniel Blabia Girau
P01/08024/00409
Universitat Oberta
de Catalunya
1 x1 2 1 1
2 x2 1 1 2
0 x3 1 0 0
© Universitat Oberta de Catalunya • P01/08024/00409
L’algoritme símplex
Índex
Introducció ........................................................................................... Objectius................................................................................................ 1. Formulació de problemes lineals................................................ 1.1. La forma estàndard d’un programa lineal................................... 1.1.1. Variables de folgança......................................................... 1.2. La forma canònica d’un programa lineal.................................... 1.3.Operacions de transformació ...................................................... 2. Conceptes i teoremes fonamentals............................................. 2.1. Convexitat ................................................................................... 2.1.1. Combinació lineal convexa .............................................. 2.1.2. Conjunt convex................................................................ 2.1.3. Vèrtex ................................................................................ 2.2. Teoremes fonamentals de la programació lineal ........................ 3. Funcionament de l’algoritme símplex...................................... 3.1. El mètode símplex per matrius.................................................... 3.1.1. Filosofia de l’algoritmesímplex per matrius .................... 3.1.2. L’algoritme símplex ........................................................... 3.2. El mètode símplex per taules ...................................................... 3.2.1. Introducció al mètode per taules ...................................... 3.2.2. Estructura i funcionament de la taula de l’algoritmesímplex....................................................... 3.2.3. Variables artificials............................................................. 4. Tipologia de solucions ................................................................... 5. Degeneració i bucles infinits ....................................................... Resum .....................................................................................................Exercicis d’autoavaluació ................................................................. Solucionari ............................................................................................ Bibliografia ...........................................................................................
5 6 7 7 10 11 12 14 14 14 14 15 15 19 19 19 20 25 25 27 35 39 42 44 45 47 55
© UniversitatOberta de Catalunya • P01/08024/00409
5
L’algoritme símplex
Introducció
En aquest mòdul didàctic introduirem l’algoritme de resolució de programes lineals desenvolupat per George Dantzig el 1947. Avui dia és l’algoritme més utilitzat, fonamentalment perquè els càlculs són senzills i per la facilitat amb què s’interpreten els seus resultats des d’una perspectiva econòmica. A fi de poderentendre a fons aquest mòdul és imprescindible haver superat amb èxit el mòdul “Introducció a la investigació operativa”, ja que farem referències constantment a conceptes com vèrtexs, conjunts convexos, solucions impròpies, solucions múltiples, i d’altres.
!
El mòdul comença amb la descripció dels fonaments de l’algoritme símplex, és a dir, la base de què cal disposar per a poder aplicaraquest algoritme a un programa lineal. A continuació ens centrarem en l’algoritme en si, i mirarem d’entendre com funciona per dins, és a dir, no ens limitarem simplement a veure’n la mecànica de resolució. Finalment estudiarem els diferents tipus de solucions que podem trobar durant la resolució i al terme d’aquesta. Per a presentar l’algoritme símplex comencem per explicar l’algoritme en la seva...
Fonaments i metodologia
Daniel Blabia Girau
P01/08024/00409
Universitat Oberta
de Catalunya
1 x1 2 1 1
2 x2 1 1 2
0 x3 1 0 0
© Universitat Oberta de Catalunya • P01/08024/00409
L’algoritme símplex
Índex
Introducció ........................................................................................... Objectius................................................................................................ 1. Formulació de problemes lineals................................................ 1.1. La forma estàndard d’un programa lineal................................... 1.1.1. Variables de folgança......................................................... 1.2. La forma canònica d’un programa lineal.................................... 1.3.Operacions de transformació ...................................................... 2. Conceptes i teoremes fonamentals............................................. 2.1. Convexitat ................................................................................... 2.1.1. Combinació lineal convexa .............................................. 2.1.2. Conjunt convex................................................................ 2.1.3. Vèrtex ................................................................................ 2.2. Teoremes fonamentals de la programació lineal ........................ 3. Funcionament de l’algoritme símplex...................................... 3.1. El mètode símplex per matrius.................................................... 3.1.1. Filosofia de l’algoritmesímplex per matrius .................... 3.1.2. L’algoritme símplex ........................................................... 3.2. El mètode símplex per taules ...................................................... 3.2.1. Introducció al mètode per taules ...................................... 3.2.2. Estructura i funcionament de la taula de l’algoritmesímplex....................................................... 3.2.3. Variables artificials............................................................. 4. Tipologia de solucions ................................................................... 5. Degeneració i bucles infinits ....................................................... Resum .....................................................................................................Exercicis d’autoavaluació ................................................................. Solucionari ............................................................................................ Bibliografia ...........................................................................................
5 6 7 7 10 11 12 14 14 14 14 15 15 19 19 19 20 25 25 27 35 39 42 44 45 47 55
© UniversitatOberta de Catalunya • P01/08024/00409
5
L’algoritme símplex
Introducció
En aquest mòdul didàctic introduirem l’algoritme de resolució de programes lineals desenvolupat per George Dantzig el 1947. Avui dia és l’algoritme més utilitzat, fonamentalment perquè els càlculs són senzills i per la facilitat amb què s’interpreten els seus resultats des d’una perspectiva econòmica. A fi de poderentendre a fons aquest mòdul és imprescindible haver superat amb èxit el mòdul “Introducció a la investigació operativa”, ja que farem referències constantment a conceptes com vèrtexs, conjunts convexos, solucions impròpies, solucions múltiples, i d’altres.
!
El mòdul comença amb la descripció dels fonaments de l’algoritme símplex, és a dir, la base de què cal disposar per a poder aplicaraquest algoritme a un programa lineal. A continuació ens centrarem en l’algoritme en si, i mirarem d’entendre com funciona per dins, és a dir, no ens limitarem simplement a veure’n la mecànica de resolució. Finalment estudiarem els diferents tipus de solucions que podem trobar durant la resolució i al terme d’aquesta. Per a presentar l’algoritme símplex comencem per explicar l’algoritme en la seva...
Leer documento completo
Regístrate para leer el documento completo.