L’essencial
Un problema de programació lineal demana el valor més gran (o el més petit) d’una funció lineal, la funció objectiu , entre els punts que compleixen alhora diverses desigualtats lineals, les restriccions. Aquest conjunt de punts és la regió factible. Es resol en quatre passos: plantejar, dibuixar la regió, trobar-ne els vèrtexs i calcular-hi .
Plantejar és el que més es falla. Anomena i el que es pot decidir i digues què és cadascuna, amb la seva unitat. Fes una taula amb el que gasta cada unitat de cada tipus i amb el que hi ha disponible. La funció objectiu és el que es vol fer màxim o mínim: el que aporta cada unitat, multiplicat per la quantitat. Hi ha una desigualtat per cada recurs: si la dada és un topall («com a màxim», «disposa de») i si és un mínim («almenys»). Afegeix sempre i . I passa-ho tot a les mateixes unitats abans d’escriure res (grams i quilos, per exemple).
| Pas | Què es fa | On es falla |
|---|---|---|
| Plantejar | Què es faVariables amb unitat; ; una desigualtat per recurs; | On es fallaBarrejar unitats; canviar per ; oblidar i |
| Dibuixar | Què es faTalls de cada recta amb els eixos; provar ; ombrejar la zona comuna | On es fallaOmbrejar el costat contrari d’una recta; traçar una recta amb un tall mal calculat |
| Vèrtexs | Què es faCada vèrtex, tall de dues rectes que compleix totes les altres restriccions | On es fallaDonar un tall que surt de la regió; deixar-se un vèrtex |
| Optimitzar | Què es fa en cada vèrtex; el més gran és el màxim i el més petit el mínim; resposta amb unitats | On es fallaIntercanviar màxim i mínim; donar un valor que no és F del punt; no veure que, en una regió no acotada, el màxim (o el mínim) pot no existir |
Per dibuixar la regió, traça cada recta frontera amb els seus talls amb els eixos (posa per al tall amb l’eix , i per a l’altre). Després prova un punt que no sigui a la recta, gairebé sempre : si compleix la desigualtat, la zona bona és el costat on és; si no, és l’altre. La regió factible és la part comuna a totes les zones bones: sempre és convexa i els seus costats són trossos de les rectes.
Cada vèrtex de la regió és el tall de dues rectes frontera veïnes: resol el sistema de cada parella (els talls amb els eixos surten directes). Un tall només és vèrtex si compleix també totes les altres restriccions: si alguna no es compleix, aquest punt és fora de la regió. Comprova sempre cada candidat en totes les desigualtats.
Si la regió és acotada, la funció objectiu assoleix el màxim i el mínim en vèrtexs: calcula en tots; el valor més gran és el màxim i el més petit, el mínim, i el punt és aquest vèrtex. Si dos vèrtexs donen el mateix valor òptim, també el dona tot el costat que els uneix (infinites solucions; amb quantitats enteres, els punts enters d’aquest costat). Si la regió no és acotada, pot créixer (o decréixer) sense límit en alguna direcció: llavors no existeix el màxim (o el mínim) i cal dir-ho; l’altre extrem sí que pot existir, i és en un vèrtex.
Exemples resolts
Una fusteria fabrica prestatgeries i taules. Cada prestatgeria necessita 2 h de tall i 1 h de poliment; cada taula necessita 1 h de tall i 2 h de poliment. Cada setmana hi ha 20 h de tall i 16 h de poliment. Es guanya 30 € per prestatgeria i 40 € per taula. Quantes de cada tipus cal fabricar cada setmana per obtenir el màxim benefici?
Anomena el nombre de prestatgeries i el de taules per setmana, i ordena les dades en una taula (el que gasta cada unitat i el que hi ha):
La funció objectiu és el benefici setmanal, que volem maximitzar: 30 € per prestatgeria i 40 € per taula.
Una desigualtat per cada recurs (les hores són un topall, per tant ) i les quantitats no negatives:
Per dibuixar les rectes frontera busquem els seus talls amb els eixos. El punt compleix les dues desigualtats, per tant la regió factible és la part del primer quadrant per sota de les dues rectes.
Vèrtexs. : i . : amb (l’altre tall amb l’eix, , no compleix ). : amb . : les dues rectes alhora; restem del doble de la segona la primera:
Valor de la funció objectiu a cada vèrtex:
El valor més gran és . Es gasten totes les hores de tall i de poliment:
Resultat Cal fabricar prestatgeries i taules a la setmana: el benefici màxim és de € (màxim al vèrtex ).
Una granja barreja dos pinsos, A i B. Cada kg d’A aporta 2 unitats de proteïna i 1 de fibra; cada kg de B, 1 de proteïna i 2 de fibra. Cada dia calen almenys 10 unitats de proteïna i 8 de fibra, i la menjadora admet com a màxim 9 kg de barreja. El pinso A costa 3 €/kg i el B, 2 €/kg. Quina quantitat de cada pinso minimitza el cost diari?
Anomena els kg d’A i els de B. La funció objectiu és el cost, que volem minimitzar:
Aquí els requisits de proteïna i de fibra són mínims () i la capacitat de la menjadora és un topall ():
Talls amb els eixos de les tres rectes. El punt no compleix les dues primeres desigualtats, per tant la regió queda per sobre d’aquestes dues rectes i per sota de la tercera:
Vèrtexs (cada tall es prova en les altres desigualtats). Amb : no compleix , però i valen. Amb cap tall val: i no compleixen, respectivament, i , i no compleix .
Talls de dues rectes. amb : restant, i . amb : de la primera ; substituint, , d’on i . ( amb dona : fora de la regió.) Tots dos compleixen el que falta ( i ):
Cost a cada vèrtex:
El valor més petit és . Els requisits de proteïna i de fibra es compleixen amb el mínim exacte:
Resultat Cal barrejar kg d’A i kg de B, amb un cost mínim de € al dia (mínim al vèrtex ; el màxim d’aquesta regió, €, és a , no és el que es demana).
La mateixa granja compra una menjadora sense límit de capacitat: només queden les condicions (proteïna) i (fibra), amb el cost en €. Calcula el cost mínim i digues si existeix un cost màxim.
Restriccions i regió. Les rectes són les mateixes, però ara no hi ha topall: la regió queda per sobre de les dues rectes i es prolonga sense límit cap a la dreta i cap amunt, per tant no és acotada.
Vèrtexs: amb (compleix ); les dues rectes entre elles (com abans, i ); amb (compleix ). Els altres talls amb els eixos, i , no compleixen l’altra desigualtat.
Cost a cada vèrtex:
Mínim. La regió només es prolonga cap a i més grans, i augmenta en augmentar qualsevol de les dues: allunyar-se dels vèrtexs sempre encareix, per tant el mínim existeix i és al vèrtex de menor valor, .
Màxim. Tots els punts amb són a la regió (compleixen i ), i en ells el cost és tan gran com es vulgui. No hi ha màxim:
Resultat El cost mínim és de € amb kg d’A i kg de B (vèrtex ). No existeix cost màxim: la regió no és acotada i creix sense límit.
Exercicis
De menys a més. «Prova-ho al comprovador» te’l deixa preparat a dalt perquè el resolguis tu i el codi el corregeixi; la solució és plegada a sota.
En tots els exercicis, i són quantitats no negatives i es demana el màxim o el mínim de la funció objectiu sobre la regió factible, amb el seu valor i en el context de l’enunciat.
- Exercici 1Nivell 1Comprovat per codi
Considera la regió del primer quadrant limitada per i , i la funció . Troba els vèrtexs de la regió factible i el màxim de .
Mostra la solució
Les restriccions són , , i . Talls amb els eixos: a i ; no talla l’eix .
Vèrtexs: ( i ), ( amb ; el tall no compleix ), ( amb ) i ( amb ):
Valor de a cada vèrtex:
El màxim és a , no a : té més , però a cada unitat de val i cada unitat de , :
Vèrtexs: (0; 0), (4; 0), (4; 2), (0; 6). Màxim: F = 18 a (0; 6). - Exercici 2Nivell 1Comprovat per codi
Una gelateria prepara cada dia litres de gelat de vainilla i litres de xocolata. Cada litre de vainilla gasta 2 kg de nata i cada litre de xocolata, 1 kg; hi ha 18 kg de nata. L’obrador només admet 12 litres al dia en total. Es guanya 5 € per litre de vainilla i 4 € per litre de xocolata. Quants litres de cadascun cal preparar per guanyar el màxim?
Mostra la solució
Funció objectiu (benefici diari, que es maximitza) i restriccions (nata, capacitat i quantitats no negatives):
Talls amb els eixos: a i ; a i . L’origen ho compleix tot: la regió queda per sota de les dues rectes.
Vèrtexs: ; (l’altre tall, , no compleix ); (el tall no compleix ); i el tall de les dues rectes: restant de surt i, d’aquí, .
Valor de a cada vèrtex i màxim:
Vèrtexs: (0; 0), (9; 0), (6; 6), (0; 12). Màxim: F = 54 a (6; 6). - Exercici 3Nivell 2Comprovat per codi
Un hotel té 210 habitacions dobles. Vol reservar amb la tarifa reduïda (70 € per nit) almenys 40 habitacions, i que les de tarifa estàndard (100 € per nit) siguin com a mínim el doble que les de tarifa reduïda. Sigui el nombre d’habitacions estàndard i el de reduïdes. Quantes de cada tarifa donen els màxims ingressos per nit?
Mostra la solució
Funció objectiu (ingressos per nit): . Restriccions: «com a màxim 210 habitacions» és ; «almenys 40 reduïdes» és ; «estàndard almenys el doble que reduïdes» és . Amb aquestes tres, , per tant ja es compleix.
Regió: el triangle que queda per sota de , per sobre de i a la dreta de . Vèrtexs (talls de dues rectes):
Ingressos a cada vèrtex:
El màxim és a : convé reservar amb la tarifa reduïda només el mínim exigit.
Vèrtexs: (80; 40), (170; 40), (140; 70). Màxim: F = 19.800 a (170; 40). - Exercici 4Nivell 2Comprovat per codi
Un obrador fa cada dia barres de pa i pastissets. Una barra porta 500 g de farina i 50 g de mantega; un pastisset porta 250 g de farina i 100 g de mantega. Cada dia disposa de 40 kg de farina i 7 kg de mantega. Ven la barra a 1,20 € i el pastisset a 2 €. Quantes barres i pastissets li donen els màxims ingressos?
Mostra la solució
Tot a quilos abans de plantejar: 500 g = 0,5 kg, 250 g = 0,25 kg, 50 g = 0,05 kg i 100 g = 0,1 kg. Funció objectiu (ingressos) i restriccions (farina i mantega):
Per treballar sense decimals multipliquem la primera per 4 i la segona per 20 (són la mateixa desigualtat escrita d’una altra manera):
Talls amb els eixos: a i ; a i . Vèrtexs: , , i el tall de les dues rectes: restem de la primera, .
Ingressos a cada vèrtex:
El màxim és € amb barres i pastissets. Es gasta tota la farina i tota la mantega:
Vèrtexs: (0; 0), (80; 0), (60; 40), (0; 70). Màxim: F = 152 a (60; 40). - Exercici 5Nivell 3Comprovat per codi
Una cooperativa compra sacs d’adob A i sacs d’adob B. Cada sac d’A aporta 2 kg de nitrogen i 1 kg de fòsfor; cada sac de B, 1 kg de nitrogen i 2 kg de fòsfor. Necessita almenys 14 kg de nitrogen i 10 kg de fòsfor. El sac d’A costa 40 € i el de B, 30 €. Quants sacs de cada tipus fan mínima la despesa?
Mostra la solució
Funció objectiu (despesa, que es minimitza) i restriccions (els dos nutrients són mínims, per tant ):
Talls: a i ; a i . L’origen no compleix: la regió queda per sobre de les dues rectes i no és acotada. Vèrtexs: ; ( no compleix i no compleix ); i el tall de les dues rectes: de la primera , substituïm, , , .
Despesa a cada vèrtex:
En una regió no acotada el mínim existeix aquí perquè els costos són positius (allunyar-se dels vèrtexs encareix). El valor més petit és el de : sacs d’A i de B.
Vèrtexs: (0; 14), (6; 2), (10; 0). Mínim: F = 300 a (6; 2). - Exercici 6Nivell 3Comprovat per codi
Amb les mateixes condicions de l’exercici anterior (almenys 14 kg de nitrogen i 10 kg de fòsfor, sacs de 40 € i de 30 €), quina és la despesa màxima que pot arribar a fer la cooperativa comprant adob que compleixi aquestes condicions? Justifica la resposta.
Mostra la solució
La funció és la mateixa, , però ara es demana el màxim. La regió és la de l’exercici anterior, amb vèrtexs , i , i no és acotada.
Els punts amb són a la regió (compleixen i ) i en ells la despesa creix sense límit:
No existeix una despesa màxima: no hi ha cap vèrtex que sigui el «millor», perquè sempre es pot comprar més adob i gastar més. Que sigui el valor més gran entre els vèrtexs no el converteix en màxim.
Vèrtexs: (0; 14), (6; 2), (10; 0). No existeix el màxim: la regió no és acotada i F creix sense límit. - Exercici 7Nivell 3Comprovat per codi
Una impremta fa targetes petites i targetes grans a cada tanda, sempre en quantitats enteres. Cada targeta, de qualsevol mida, necessita 1 hora de màquina, i n’hi ha 9. La petita gasta 2 kg de paper i la gran 1 kg, i n’hi ha 14. Només es disposa de cartolina especial per a 7 targetes grans. Cada targeta es ven a 3 €, sigui de la mida que sigui. Amb quantes de cada mida s’ingressa el màxim? És única la solució?
Mostra la solució
Funció objectiu (ingressos) i restriccions (hores, paper, cartolina especial i quantitats no negatives):
Vèrtexs: ; ( amb ; el tall de no compleix la del paper); ( amb ); ( amb ); i (restant de surt , i ). i no compleixen .
Valor de a cada vèrtex:
Dos vèrtexs, i , donen el màxim, €: la funció objectiu és : les seves rectes de nivell són paral·leles a , i tot el costat que uneix aquests dos vèrtexs dona el mateix. La solució no és única: tot el costat entre els dos vèrtexs dona € i, com que les quantitats són enteres, les solucions són els seus quatre punts enters:
Vèrtexs: (0; 0), (7; 0), (5; 4), (2; 7), (0; 7). Màxim: F = 27 a tot el costat entre (5; 4) i (2; 7). - Exercici 8Nivell 3Comprovat per codi
Un agricultor conrea dotzenes d’enciam iceberg i dotzenes d’enciam romà a cada cicle. La quantitat d’iceberg ha de ser almenys la meitat de la de romà i no pot superar les 40 dotzenes. Entre les dues cal conrear com a mínim 30 i com a màxim 90 dotzenes. Es guanya 6 € per dotzena d’iceberg i 5 € per dotzena de romà. Quantes dotzenes de cada tipus donen el màxim benefici?
Mostra la solució
Funció objectiu (benefici) i restriccions. «Iceberg almenys la meitat de romà» és , o sigui ; «no més de 40» és ; el total entre 30 i 90 són dues desigualtats:
Regió: per sota de la recta , a l’esquerra de , entre i i per sobre de l’eix (l’origen no compleix ). Vèrtexs:
Cadascun compleix el que falta (per exemple, compleix ). Es descarten amb , que dona (), i amb , que dona i no compleix . Benefici a cada vèrtex:
El màxim és a : dotzenes d’iceberg i de romà.
Vèrtexs: (10; 20), (30; 0), (40; 0), (40; 50), (30; 60). Màxim: F = 490 a (40; 50).
Així surt a la PAU
Els exercicis oficials de la PAU sobre aquest tema, resolts pas a pas a EducaIA:
Els exercicis oficials de programació lineal de la PAU de Matemàtiques CCSS de Catalunya, resolts pas a pasI els de la Comunitat Valenciana, amb l’enunciat oficial en castellà i en valencià
Més preguntes reals d’exàmens oficials sobre aquest tema. Et diem de què van; l’enunciat és a l’examen.
Catalunya 2023 convocatòria extraordinària · pregunta 3 (S2)
Caixes de dos tipus amb taronges i mandarines: funció objectiu, restriccions i regió factible, i després el màxim d’ingressos en un vèrtex.
Obre l’examen (p. 6)Catalunya 2023 convocatòria ordinària · pregunta 4 (S1)
Bateigs de submarinisme i excursions en barca, amb quantitats enteres: ingressos màxims amb restriccions d’instructors i embarcacions.
Obre l’examen (p. 8)Catalunya 2023 convocatòria ordinària · pregunta 2 (S5)
Coques amb farina i sucre i comandes mínimes: restriccions amb i , unitats en kg i, a més, el que sobra de cada ingredient.
Obre l’examen (p. 20)Catalunya 2022 convocatòria ordinària · pregunta 3 (S2)
Paneres de Nadal amb dos tipus de panera: maximitzar el nombre de paneres i, després, repetir el càlcul amb una condició afegida ().
Obre l’examen (p. 6)Catalunya 2022 convocatòria ordinària · pregunta 4 (S5)
Habitacions d’hotel amb dues tarifes: restriccions com «almenys el 20 %» i «el doble que», una regió triangular i el màxim en un vèrtex.
Obre l’examen (p. 24)Catalunya 2022 convocatòria extraordinària · pregunta 4 (S3)
Un mínim amb una restricció i una altra , i un pla concret que compleix les restriccions però no és l’òptim.
Obre l’examen (p. 8)
Errors típics
Plantejar i dibuixar abans d’optimitzar: la pauta puntua per separat les restriccions ( punts), el dibuix de la regió factible ( punts) i la funció objectiu ( punts).
Criteri de correccióDonar el que sobra de cada ingredient quan l’enunciat ho pregunta ( punts), a més dels vèrtexs ( punts), el punt del màxim ( punts) i el seu valor ( punts).
Criteri de correccióSi l’enunciat dona un pla concret (el 2022, un tractament de 7 grays de cobalt i 5 de cesi), comprovar que compleix les dues restriccions ( punts) i justificar per què és pitjor que l’òptim ( punts): que les compleixi no n’hi ha prou, cal comparar la funció objectiu.
Criteri de correcció
Preguntes freqüents
Per què el màxim i el mínim són en un vèrtex?
Perquè canvia de forma constant en moure’t en línia recta. Des d’un punt de l’interior sempre pots avançar en la direcció en què creix fins a arribar a un costat, així que el màxim no és a dins; i sobre un costat només puja cap a un extrem o baixa cap a l’altre (o no canvia), així que el millor punt del costat és un dels seus extrems, que són vèrtexs. Per això, en una regió acotada, n’hi ha prou de comparar als vèrtexs.
Què faig si dos vèrtexs donen el mateix valor òptim?
Llavors tot el costat que els uneix dona aquest mateix valor: hi ha infinites solucions. Digues-ho, dona els dos vèrtexs i el valor. Si les quantitats han de ser enteres, les solucions són els punts enters d’aquest costat.
I si la regió no és acotada?
Calcula igualment els vèrtexs i en ells, però no et quedis amb el valor més gran com «el màxim»: mira si creix sense límit en alguna direcció de la regió (amb un punt com i gran). Si és així, no hi ha màxim (o no hi ha mínim, si decreix); l’altre extrem sí que pot existir i serà en un vèrtex.
Cal dibuixar la regió o n’hi ha prou amb calcular els vèrtexs?
Si l’enunciat demana dibuixar-la, cal fer-ho: a l’examen de 2023 (extraordinària, sèrie 2) la pauta puntua per separat les restriccions, el dibuix de la regió i la funció objectiu. A més, el dibuix és el que et diu quins talls de rectes són vèrtexs.
Què faig si i han de ser enteres i el vèrtex òptim no ho és?
No n’hi ha prou d’arrodonir les coordenades: el punt arrodonit pot sortir de la regió. Cal comprovar els punts enters de la regió propers al vèrtex i quedar-te amb el que doni millor valor de . El comprovador d’aquesta pàgina no resol aquest cas: als exercicis del tema el vèrtex òptim ja és enter.
Fonts
Contesta amb el que demana l’enunciat i amb el seu context: quantes unitats de cada tipus, el valor òptim amb la seva unitat (€, kg, grays) i, si ho pregunten, el que sobra de cada recurs. Si i han de ser enteres i el vèrtex no ho és, arrodonir no n’hi ha prou: cal mirar els punts enters de la regió propers. El comprovador d’aquesta pàgina treballa amb dues variables i amb les restriccions i la funció objectiu que hi escriguis; comprova els vèrtexs, l’òptim i el seu valor, però no resol el cas enter ni una semirecta de solucions.
- PAU Catalunya, Matemàtiques Aplicades a les Ciències Socials 2023, extraordinària, sèrie 2: exercici 3, enunciat p. 6 i pauta pp. 4 i 5. Obre
- PAU Catalunya, Matemàtiques Aplicades a les Ciències Socials 2023, ordinària: exercici 4 de la sèrie 1 (enunciat p. 8, pauta p. 4) i exercici 2 de la sèrie 5 (enunciat p. 20, pauta pp. 9 i 10). Obre
- PAU Catalunya, Matemàtiques Aplicades a les Ciències Socials 2022, ordinària: exercici 3 de la sèrie 2 (enunciat p. 6, pauta pp. 3 a 5) i exercici 4 de la sèrie 5 (enunciat p. 24, pauta p. 12); l’exercici 3 d’aquests apunts n’és una adaptació. Obre
- PAU Catalunya, Matemàtiques Aplicades a les Ciències Socials 2022, extraordinària, sèrie 3: exercici 4, enunciat p. 8 i pauta p. 4. Obre
- Exercici 8 adaptat de la PAU d’Andalusia, Matemàtiques Aplicades a les Ciències Socials II 2025, convocatòria extraordinària, exercici 2. Informació obtinguda del Portal de la Junta d’Andalusia (CC BY 3.0). Obre