01007 Solpac1 1002
SOLUCIÓ PAC1. Programació lineal
PREGUNTES CURTES
Pregunta 1. Podem representar el conjunt factible seguint els passos indicats a la GES 2 per tal d’obtenir
Així, el conjunt factible queda delimitat pel triangle compacte de vèrtexs els punts (3,7), (5,3) i (9,7). Per tal de determinar els punts d’òptim ens calavaluar la funció objectiu en cadascun dels vèrtexs: f(3,7) = 27, f(5,3) = 19 i f(9,7)=39, d’on podem concloure que el punt de mínim es troba en el vèrtex (5, 3) i el punt de màxim en el vèrtex (9,7).
Pregunta 2. Per tal que la funció objectiu tingui infinits punts de màxim o mínim en el segment que uneix dos vèrtexs cal igualem les seves imatges obtenim
que les imatges d’aquests vèrtexscoincideixin. Així, si valorem v1 = ( 3,1) i v3 = ( 6, a ) a la funció objectiu i
f (3,1) = 6 − 3 = 3 f (6, a ) = 12 − 3a 3 = 12 − 3a ⇒ a = 3
Finalment, queda per comprovar que efectivament aquests dos punts són de màxim. Avaluant la funció objectiu en l’altre vèrtex tenim que f(4,5) = -7 < 3.
01007_SolPAC1_1002.doc
1/6
Pregunta 3. Si representem el conjunt factible de vèrtexs els punts(2,2), (4,6) i (5,3) obtenim que:
Llavors, el procediment per tal de determinar les restriccions que ens defineixen el conjunt factible anterior això determinarem la frontera de la primera restricció (desigualtat).
comença per buscar la recta que passa per dos dels vèrtexs, per exemple, v1 = ( 2, 2 ) i v2 = ( 4,6 ) . Amb
Recordem que l’equació d’una recta és de la forma y = m ⋅ x + n , on més el pendent i n el punt de tall amb l’eix d’ordenades. Per tal de determinar els valors de m i n només ens cal substituir els vèrtexs v1 i v2 en l’equació general de la recta i resoldre el sistema resultant:
(2, 2) → 2 = m ⋅ 2 + n → m = 2 i n = −2 (4, 6) → 6 = m ⋅ 4 + n de manera que la recta que passa per aquests dos vèrtexs és y = 2 ⋅ x − 2 . Un cop fet això ens caldrà determinar elsentit de la desigualtat, és a dir, si la restricció és de la forma y ≤ 2 ⋅ x − 2 o de la forma y ≥ 2 ⋅ x − 2 . Donat que els punts del conjunt factible que compleixen amb la restricció que estem buscant
són els que queden per sota de la recta (per exemple el punt (5,3) i no el (2,3)), hem de mirar quina de les dues formes anteriors és satisfeta pel punt (5,3). Fent això, comprovem que 3 ≤ 2 ⋅ 5− 2 és cert, de manera que la primera de les restriccions que busquem serà y ≤ 2 ⋅ x − 2 .
Procedim ara d’igual manera agafant els vèrtexs v1 = ( 2, 2 ) i v3 = ( 5,3) i obtenim que l’equació de la recta
1 4 ⋅ x + , mentre que la desigualtat compatible amb el conjunt factible (la 3 3 1 4 que satisfà per exemple el punt (4,6) que queda per sobre d’aquesta recta) és y ≥ ⋅ x + . 3 3 Finalment, perals punts v2 = ( 4,6 ) i v3 = ( 5,3) obtenim que l’equació de la recta que passa per tots dos és y = −3 ⋅ x + 18 . Els punts del conjunt factible que compleixen amb la tercera restricció són els que queden a
que els uneix és de la forma y = l’esquerra de la recta, per exemple, el punt (2,2). Així, la desigualtat que defineix la restricció és y ≤ −3 ⋅ x + 18 . Així, les restriccions quedefineixen el conjunt factible són:
y ≤ 2⋅ x − 2 1 4 y ≥ ⋅ x + 3 3 y ≤ −3 ⋅ x + 18
01007_SolPAC1_1002.doc
2/6
Pregunta 4. Seguint la nomenclatura indicada per a les variables de decisió, el problema lineal a resoldre és
Min C ( AN , AI , BN , BI ) = 20 AN + 26 AI + 21BN + 28 BI subjecte a AN + AI ≤ 5.000 BN + BI ≤ 8.000 AN + BN ≥ 8.000 AI + BI ≥ 4.000 AN , AI ,BN , BI ≥ 0
Exercici 1 Apartat a) Representem el conjunt factible seguint els passos indicats a la GES 2 i obtenim
Podem observar que el conjunt factible és el recinte compacte de vèrtexs els punts (3,3), (9/2,0), (5,5) i (15/2,0). Finalment, per tal de determinar els punts òptims avaluem la funció objectiu en els vèrtexs anteriors: f(3,3) = 24 , f(9/2,0) = 27, f(5,5) = 40 i f(15/2,0)=...
Regístrate para leer el documento completo.