Exercicis de programació lineal — Matemàtiques Aplicades a les Ciències Socials 2n Batxillerat

Un punt pertany a la regió si compleix totes les inequacions a la vegada; n'hi ha prou que en falli una perquè quedi fora.
(2, 1): 2 + 1 = 3 ≤ 5, es compleix; 2 - 1 = 1 ≥ -2, es compleix; les coordenades no són negatives. Pertany a la regió.
(4, 3): 4 + 3 = 7 > 5. Falla la primera inequació: no hi pertany.
(0, 5): 0 + 5 = 5 ≤ 5, es compleix (és a la frontera); però 0 - 5 = -5 < -2. Falla la segona: no hi pertany.
Només (2, 1) és un punt de la regió factible.

Traducció: x ≤ 6, y ≤ 4, x + y ≥ 3, x ≥ 0, y ≥ 0.
La regió és el rectangle de vèrtexs (0, 0), (6, 0), (6, 4) i (0, 4) al qual la recta x + y = 3 retalla la cantonada de l'origen.
Vèrtexs: (3, 0) i (0, 3) (talls de x + y = 3 amb els eixos), (6, 0), (6, 4) i (0, 4).
És acotada: queda dins del rectangle, de manera que qualsevol funció objectiu lineal hi té màxim i mínim.
Comprovació: (6, 4) compleix 6 + 4 = 10 ≥ 3, i (0, 0) no, perquè 0 < 3.

Els vèrtexs són interseccions de dues rectes frontera que, a més, compleixen la resta de restriccions.
x = 0 i y = 0: (0, 0). y = 0 i x = 6: (6, 0).
x = 6 i x + 2y = 8: 6 + 2y = 8 → y = 1: (6, 1).
x = 0 i x + 2y = 8: y = 4: (0, 4).
La intersecció de y = 0 amb x + 2y = 8 seria (8, 0), però no compleix x ≤ 6 i no és cap vèrtex.
Vèrtexs: (0, 0), (6, 0), (6, 1) i (0, 4): la regió és un quadrilàter.

Com que la regió és un polígon acotat, el màxim i el mínim d'una funció lineal s'assoleixen en algun vèrtex: n'hi ha prou d'avaluar f a cada un.
f(0, 0) = 0; f(5, 0) = 15; f(3, 4) = 9 + 8 = 17; f(0, 6) = 12.
Màxim: 17, al vèrtex (3, 4). Mínim: 0, al vèrtex (0, 0).
Comprovació: en un punt interior com (2, 2), f = 10, un valor entre el mínim i el màxim.

Hores emprades: 2x per les cadires més 5y per les taules, que no poden superar les 40 disponibles: 2x + 5y ≤ 40 (amb x ≥ 0 i y ≥ 0).
10 cadires i 5 taules: 2·10 + 5·5 = 45 > 40. No és possible: faltarien 5 hores.
5 cadires i 6 taules: 2·5 + 5·6 = 10 + 30 = 40 ≤ 40. Sí que és possible, i s'aprofiten exactament totes les hores (el punt és a la frontera de la regió).
Error típic: escriure la inequació amb ≥, com si les hores fossin un mínim a complir.

Per trobar el tall amb l'eix OX es fa y = 0: 2x = 12 → x = 6, punt (6, 0). Per al tall amb l'eix OY es fa x = 0: 3y = 12 → y = 4, punt (0, 4).
L'alumne ha oblidat dividir pel coeficient de cada variable.
Per saber quin semiplà representa 2x + 3y ≤ 12, provem un punt que no sigui de la recta, per exemple l'origen: 2·0 + 3·0 = 0 ≤ 12, es compleix.
Per tant, el semiplà solució és el que conté l'origen (el costat de sota de la recta), inclosa la mateixa recta.

Resolem el sistema. Sumant les dues equacions: 3x = 15 → x = 5.
Substituïm a la primera: 5 + y = 10 → y = 5. El punt d'intersecció és (5, 5).
Comprovació: 2·5 − 5 = 5, correcte.
Restricció: 3·5 + 5 = 20 ≤ 25, es compleix; el punt (5, 5) podria ser un vèrtex de la regió factible definida per aquestes tres condicions.

Funció objectiu (ingressos en euros): f(x, y) = 2x + 3y.
Per a 40 kg de pomes i 20 kg de peres: f(40, 20) = 80 + 60 = 140 €.
Restriccions: x + y ≤ 80 (quilos totals), y ≥ 10 (mínim de peres), x ≥ 0 (no es pot vendre una quantitat negativa).
Comprovació: el punt (40, 20) compleix 60 ≤ 80 i 20 ≥ 10, de manera que és una venda possible.

La regió és la part del primer quadrant que queda per sobre de la recta x + y = 2: s'estén indefinidament cap a la dreta i cap amunt, de manera que no és acotada.
Màxim: no existeix, perquè podem agafar punts com (100, 0) o (0, 1000) i f creix tant com vulguem.
Mínim: com que els coeficients de f són positius, sí que existeix i s'assoleix en un dels vèrtexs: (2, 0) i (0, 2).
f(2, 0) = 4 i f(0, 2) = 6. El mínim és 4, al punt (2, 0).
En una regió no acotada cal pensar sempre si el problema té solució abans de buscar-la.

a) Certa. És el teorema fonamental de la programació lineal: en un polígon acotat, els valors extrems d'una funció lineal es troben als vèrtexs (si hi ha més d'un punt òptim, també n'hi ha a tot un costat, però els extrems d'aquest costat són vèrtexs).
b) Certa. Si les restriccions són incompatibles (per exemple x + y ≤ 2 i x + y ≥ 5), cap punt les compleix totes i el problema no té cap solució factible.
c) Falsa. Al contrari: el problema té infinites solucions, perquè tots els punts del segment que uneix els dos vèrtexs donen el mateix valor màxim; la funció objectiu és paral·lela a aquest costat.

Vèrtexs de la regió factible: (0, 0); tall de y = 0 amb 2x + y = 12: (6, 0); tall de x = 0 amb x + y = 8: (0, 8); intersecció de x + y = 8 i 2x + y = 12: restant, x = 4 i y = 4: (4, 4).
Comprovem que (8, 0) no és vàlid (2·8 = 16 > 12) i que (0, 12) tampoc (12 > 8).
Avaluem f: f(0, 0) = 0; f(6, 0) = 24; f(4, 4) = 16 + 12 = 28; f(0, 8) = 24.
El màxim és 28 i s'assoleix al punt (4, 4).
Comprovació: (4, 4) compleix 4 + 4 = 8 ≤ 8 i 2·4 + 4 = 12 ≤ 12 (les dues restriccions s'esgoten).

Les restriccions x + y ≥ 6 i x + 3y ≥ 10 deixen la regió per sobre de les dues rectes, i x ≤ 7, y ≤ 6 la tanquen: és acotada.
Vèrtexs: intersecció de x + y = 6 i x + 3y = 10: restant, 2y = 4 → y = 2, x = 4: (4, 2). Intersecció de x + 3y = 10 amb x = 7: y = 1: (7, 1). Intersecció de x = 7 i y = 6: (7, 6). Intersecció de x = 0 i y = 6: (0, 6).
(El tall de x = 0 amb x + 3y = 10 és (0; 3,33), però no compleix x + y ≥ 6 i no és vèrtex.)
f(4, 2) = 8 + 10 = 18; f(7, 1) = 14 + 5 = 19; f(7, 6) = 14 + 30 = 44; f(0, 6) = 30.
El mínim és 18, al punt (4, 2).

Variables: x = pastissos A, y = pastissos B. Funció objectiu: benefici f = 5x + 6y (a maximitzar).
Restriccions: farina x + 2y ≤ 40; ous 2x + y ≤ 50; x ≥ 0, y ≥ 0.
Vèrtexs: (0, 0); (25, 0) (de 2x + y = 50 amb y = 0); (0, 20) (de x + 2y = 40 amb x = 0); intersecció de x + 2y = 40 i 2x + y = 50: de la primera, x = 40 - 2y, i 80 - 4y + y = 50 → y = 10, x = 20: (20, 10).
f(0, 0) = 0; f(25, 0) = 125; f(0, 20) = 120; f(20, 10) = 100 + 60 = 160.
Ha de fer 20 pastissos A i 10 pastissos B, amb un benefici màxim de 160 €.
Comprovació: farina 20 + 20 = 40 kg i ous 40 + 10 = 50; s'esgoten els dos recursos.

Variables: x = kg de pinso A, y = kg de pinso B. Cost a minimitzar: f = 2x + 1,5y.
Restriccions: proteïna 3x + y ≥ 12; fibra x + 2y ≥ 10; x ≥ 0, y ≥ 0. La regió no és acotada (cap amunt i cap a la dreta), però com que minimitzem una funció de coeficients positius, el mínim existeix.
Vèrtexs: (0, 12) (de 3x + y = 12 amb x = 0); (10, 0) (de x + 2y = 10 amb y = 0); intersecció de 3x + y = 12 i x + 2y = 10: y = 12 - 3x → x + 24 - 6x = 10 → x = 2,8, y = 3,6: (2,8; 3,6).
f(0, 12) = 18; f(10, 0) = 20; f(2,8; 3,6) = 5,6 + 5,4 = 11.
Cost mínim: 11 € diaris, amb 2,8 kg de pinso A i 3,6 kg de pinso B.
Comprovació: proteïna 3·2,8 + 3,6 = 12 i fibra 2,8 + 7,2 = 10; es compleixen just els mínims.

Variables: x = euros al fons A, y = euros al fons B. Interès anual a maximitzar: f = 0,04x + 0,07y.
Restriccions: x + y ≤ 12000; y ≤ 2x; x ≥ 2000; y ≥ 0.
Vèrtexs: (2000, 0); (12000, 0); intersecció de x = 2000 amb y = 2x: (2000, 4000); intersecció de y = 2x amb x + y = 12000: 3x = 12000 → x = 4000, y = 8000: (4000, 8000).
f(2000, 0) = 80; f(12000, 0) = 480; f(2000, 4000) = 80 + 280 = 360; f(4000, 8000) = 160 + 560 = 720.
Interès màxim: 720 € anuals, invertint 4000 € al fons A i 8000 € al fons B.
Comprovació: 8000 = 2·4000 (compleix just el límit de risc) i 4000 + 8000 = 12000 €.

Variables: x = màquines A, y = màquines B. Cost a minimitzar: f = 300x + 500y.
Restriccions: x + y ≥ 20; 2x + 3y ≤ 54; y ≥ 4; x ≥ 0.
Vèrtexs: intersecció de y = 4 amb x + y = 20: (16, 4); intersecció de y = 4 amb 2x + 3y = 54: 2x = 42 → (21, 4); intersecció de x + y = 20 amb 2x + 3y = 54: y = 14, x = 6: (6, 14).
f(16, 4) = 4800 + 2000 = 6800; f(21, 4) = 6300 + 2000 = 8300; f(6, 14) = 1800 + 7000 = 8800.
Cost mínim: 6800 €, amb 16 màquines A i 4 màquines B.
Comprovació: 16 + 4 = 20 màquines i 32 + 12 = 44 m² ≤ 54 m².

La funció objectiu f = ax + by és lineal: les seves corbes de nivell (ax + by = k) són rectes paral·leles, i f creix sempre en la mateixa direcció. Si desplacem aquestes rectes en aquesta direcció, l'última que toca la regió (un polígon convex) ho fa en un vèrtex o, com a molt, en tot un costat; per això el màxim i el mínim es troben sempre en vèrtexs.
Si la regió no és acotada, la funció pot créixer (o decréixer) indefinidament en alguna direcció de la regió, i aleshores el màxim (o el mínim) no existeix; només tenen sentit els òptims que queden als vèrtexs del tros acotat de la frontera.
Per tant, abans d'avaluar els vèrtexs cal comprovar si la regió és acotada o si la funció té sentit optimitzar-la en aquella direcció.

Cada costat és un tros de recta, i la regió queda al costat de la recta on hi ha l'origen (o, si la recta passa per l'origen, al costat dels altres vèrtexs).
Costat de (0, 0) a (6, 0): eix OX, y = 0 → y ≥ 0. Costat de (0, 5) a (0, 0): eix OY, x = 0 → x ≥ 0.
Costat de (6, 0) a (4, 4): pendent $\tfrac{(4 - 0)}{(4 - 6)}$ = -2; recta y = -2(x - 6), és a dir, 2x + y = 12. L'origen dona 0 ≤ 12: 2x + y ≤ 12.
Costat de (4, 4) a (0, 5): pendent $\tfrac{(5 - 4)}{(0 - 4)}$ = -$\tfrac{1}{4}$; recta y = 5 - $\tfrac{x}{4}$, és a dir, x + 4y = 20. L'origen dona 0 ≤ 20: x + 4y ≤ 20.
Sistema: x ≥ 0, y ≥ 0, 2x + y ≤ 12, x + 4y ≤ 20.
Comprovació: (4, 4) compleix 2·4 + 4 = 12 i 4 + 16 = 20, com correspon a un vèrtex comú a les dues rectes.

Variables: x = menús A, y = menús B. Benefici a maximitzar: f = 6x + 9y.
Restriccions: cuina 20x + 40y ≤ 600 (10 h = 600 min), que simplificada és x + 2y ≤ 30; menús x + y ≤ 24; mínims x ≥ 5 i y ≥ 5.
Vèrtexs: (5, 5); intersecció de y = 5 amb x + y = 24: (19, 5); intersecció de x + y = 24 i x + 2y = 30: y = 6, x = 18: (18, 6); intersecció de x = 5 amb x + 2y = 30: (5; 12,5).
f(5, 5) = 75; f(19, 5) = 114 + 45 = 159; f(18, 6) = 108 + 54 = 162; f(5; 12,5) = 30 + 112,5 = 142,5.
Benefici màxim: 162 € amb 18 menús A i 6 menús B.
Comprovació: 18·20 + 6·40 = 600 min i 18 + 6 = 24 menús: s'esgoten les dues capacitats.

a) Benefici a maximitzar: f = 60x + 100y. Restriccions: tall x + 2y ≤ 40; muntatge 2x + 2y ≤ 56, és a dir, x + y ≤ 28; envernissat x + 3y ≤ 48; x ≥ 0, y ≥ 0.
Vèrtexs: (0, 0); (28, 0); (0, 16) (de x + 3y = 48 amb x = 0); intersecció de x + y = 28 i x + 3y = 48: 2y = 20 → y = 10, x = 18: (18, 10). La intersecció de x + y = 28 amb x + 2y = 40, (16, 12), no compleix 16 + 36 ≤ 48 i no és vèrtex.
f(0, 0) = 0; f(28, 0) = 1680; f(0, 16) = 1600; f(18, 10) = 1080 + 1000 = 2080.
Benefici màxim: 2080 € amb 18 prestatgeries i 10 armaris.
b) Al punt òptim: tall 18 + 20 = 38 h de 40 (sobren 2 h); muntatge 36 + 20 = 56 h (s'esgota); envernissat 18 + 30 = 48 h (s'esgota). El recurs que no s'esgota és el tall, amb 2 hores sobrants.

Variables: x = cambrers, y = ajudants. Despesa a minimitzar: f = 1200x + 900y.
Restriccions: x + y ≥ 8; y ≤ x; y ≥ 3; x ≥ 0. La regió no és acotada (es poden contractar tantes persones com es vulgui), però la despesa mínima existeix perquè els coeficients són positius.
Vèrtexs: intersecció de x + y = 8 amb y = x: (4, 4); intersecció de x + y = 8 amb y = 3: (5, 3).
f(4, 4) = 4800 + 3600 = 8400; f(5, 3) = 6000 + 2700 = 8700.
Despesa mínima: 8400 € mensuals, amb 4 cambrers i 4 ajudants.
Comprovació: 4 + 4 = 8 persones, 4 ≤ 4 ajudants i 4 ≥ 3.

a) Vèrtexs: (0, 0); (5, 0) (de 3x + y = 15 amb y = 0); (0, 5) (de x + 2y = 10 amb x = 0); intersecció de x + 2y = 10 i 3x + y = 15: y = 15 - 3x → x + 30 - 6x = 10 → x = 4, y = 3: (4, 3).
b) f(0, 0) = 0; f(5, 0) = 10; f(4, 3) = 8 + 12 = 20; f(0, 5) = 20. El màxim és 20 i s'assoleix a dos vèrtexs, (4, 3) i (0, 5).
Passa perquè f = 2x + 4y = 2·(x + 2y): les rectes de nivell de f són paral·leles al costat x + 2y = 10, i tots els punts d'aquest costat donen el mateix valor màxim, 20.
c) Qualsevol punt del segment que va de (4, 3) a (0, 5), per exemple el punt mitjà (2, 4): f = 4 + 16 = 20; o bé (1; 4,5): f = 2 + 18 = 20.
Hi ha infinites solucions òptimes, però el valor màxim (20) és únic.

a) Com que P necessita 70 unitats i Q 90, B envia 70 - x unitats a P i 90 - y unitats a Q.
Restriccions: A no pot enviar més del que té: x + y ≤ 100; B tampoc: (70 - x) + (90 - y) ≤ 80 → x + y ≥ 80; les quantitats no poden ser negatives: 0 ≤ x ≤ 70 i 0 ≤ y ≤ 90.
b) Cost: C = 3x + 5y + 4(70 - x) + 2(90 - y) = 3x + 5y + 280 - 4x + 180 - 2y = -x + 3y + 460.
Vèrtexs de la regió (la franja 80 ≤ x + y ≤ 100 dins del rectangle): (70, 10), (70, 30), (10, 90), (0, 90) i (0, 80).
C(70, 10) = -70 + 30 + 460 = 420; C(70, 30) = 480; C(10, 90) = 720; C(0, 90) = 730; C(0, 80) = 700.
Pla òptim: A envia 70 unitats a P i 10 a Q; B no envia res a P i 80 unitats a Q. Cost mínim: 420 €.
Comprovació: A envia 80 ≤ 100 unitats i B envia 0 + 80 = 80 ≤ 80; cost directe 70·3 + 10·5 + 0·4 + 80·2 = 210 + 50 + 160 = 420 €.

a) Valors de f als vèrtexs: f(0, 0) = 0; f(6, 0) = 6k; f(4, 4) = 4k + 8; f(0, 5) = 10.
Perquè (4, 4) sigui el màxim cal 4k + 8 ≥ 6k i 4k + 8 ≥ 10: la primera condició dona k ≤ 4 i la segona k ≥ 0,5.
Per tant, el màxim és a (4, 4) quan 0,5 ≤ k ≤ 4.
b) Si k = 4: f(4, 4) = 24 = f(6, 0): hi ha infinites solucions (tot el costat de (6, 0) a (4, 4)), perquè f = 4x + 2y és paral·lela a la recta 2x + y = 12 que conté aquest costat.
Si k = 6: f(6, 0) = 36 > f(4, 4) = 32: el màxim passa al vèrtex (6, 0). Quan x pesa molt més que y a la funció objectiu, convé posar-ho tot a x.
Comprovació amb k = 1 (dins de l'interval): f(4, 4) = 12, f(6, 0) = 6 i f(0, 5) = 10; el màxim és a (4, 4).

a) Maximitzar f = 7x + 10y amb 2x + 5y ≤ 31, x + y ≤ 10, x ≥ 0, y ≥ 0.
Vèrtexs: (0, 0); (10, 0); (0; 6,2); intersecció de 2x + 5y = 31 i x + y = 10: x = 10 − y → 20 − 2y + 5y = 31 → y = 11/3 ≈ 3,67 i x = 19/3 ≈ 6,33. f(0, 0) = 0; f(10, 0) = 70; f(0; 6,2) = 62; f(19/3, 11/3) = 133/3 + 110/3 = 81.
b) El vèrtex òptim no té coordenades enteres i no es poden fabricar 6,33 unitats. Arrodonir sense més pot donar un punt no factible: (6, 4) necessita 12 + 20 = 32 h > 31.
Punts enters factibles propers: (6, 3): f = 72; (7, 3): 14 + 15 = 29 ≤ 31 i 7 + 3 = 10 ≤ 10, f = 49 + 30 = 79; (8, 2): f = 76; (5, 4): 10 + 20 = 30 ≤ 31, f = 75.
La millor solució entera és fabricar 7 unitats d'A i 3 de B, amb un benefici de 79 € (inferior als 81 € teòrics del vèrtex).
Error típic: donar la solució (6, 3) per truncament sense mirar els altres punts enters de la regió.

Benefici a maximitzar: f = 120x + 150y. Restriccions: y ≥ x/2 (és a dir, x − 2y ≤ 0); x + y ≤ 60; 3x + 4y ≤ 216; x ≥ 0, y ≥ 0.
Vèrtexs: (0, 0); (0, 54) (de 3x + 4y = 216 amb x = 0); intersecció de x + y = 60 i 3x + 4y = 216: y = 216 − 180 = 36, x = 24: (24, 36); intersecció de y = x/2 amb x + y = 60: 1,5x = 60 → x = 40, y = 20: (40, 20), que compleix 120 + 80 = 200 ≤ 216.
f(0, 0) = 0; f(0, 54) = 8100; f(24, 36) = 2880 + 5400 = 8280; f(40, 20) = 4800 + 3000 = 7800.
Benefici màxim: 8280 € amb 24 bicicletes de muntanya i 36 de carretera.
Comprovació: 36 ≥ 12, 24 + 36 = 60 i 72 + 144 = 216 hores: s'esgoten la capacitat i la mà d'obra.

a) Variables: x = racions d'A, y = racions de B. Cost a minimitzar: f = 2x + 1,5y.
Restriccions: proteïna 20x + 10y ≥ 90 → 2x + y ≥ 9; hidrats 30x + 60y ≥ 180 → x + 2y ≥ 6; racions x + y ≤ 8; x ≥ 0, y ≥ 0.
Vèrtexs: intersecció de 2x + y = 9 i x + 2y = 6: y = 9 − 2x → x + 18 − 4x = 6 → x = 4, y = 1: (4, 1). Intersecció de 2x + y = 9 i x + y = 8: x = 1, y = 7: (1, 7). Talls amb y = 0: x + 2y = 6 dona (6, 0) i x + y = 8 dona (8, 0).
b) f(4, 1) = 8 + 1,5 = 9,5; f(1, 7) = 2 + 10,5 = 12,5; f(6, 0) = 12; f(8, 0) = 16.
Cost mínim: 9,50 € amb 4 racions d'A i 1 ració de B.
Comprovació: proteïna 80 + 10 = 90 g i hidrats 120 + 60 = 180 g (es compleixen just els mínims), i 5 racions ≤ 8.

a) Restriccions: x + y ≥ 50, x + 2y ≤ 60, x ≤ 30, x ≥ 0, y ≥ 0.
Si x ≤ 30 i x + y ≥ 50, aleshores y ≥ 50 - x ≥ 20. Però llavors x + 2y = (x + y) + y ≥ 50 + 20 = 70 > 60, cosa que contradiu la segona restricció.
Cap punt pot complir-les totes: la regió factible és buida i el problema no té solució.
b) Amb x ≤ 40: el mateix raonament dona y ≥ 10 i x + 2y ≥ 50 + 10 = 60, de manera que la condició x + 2y ≤ 60 només es compleix amb igualtat: x + 2y = 60, x + y = 50 i x = 40.
L'única solució és x = 40 i y = 10: la regió factible es redueix a un sol punt.
Comprovació: 40 + 10 = 50, 40 + 20 = 60 i 40 ≤ 40.

a) Vèrtexs: (0, 4) i (4, 0) (talls de x + y = 4 amb els eixos) i (6, 0) (de x = 6 amb y = 0). La regió és la franja 0 ≤ x ≤ 6 situada per sobre de la recta x + y = 4: y pot ser tan gran com es vulgui, de manera que no és acotada.
b) f = 3x + 2y creix quan y creix, i y no té límit: no hi ha màxim. El mínim sí que existeix (coeficients positius) i és en un vèrtex: f(0, 4) = 8, f(4, 0) = 12, f(6, 0) = 18. Mínim: 8, al punt (0, 4).
c) g = 2x − y decreix quan y creix sense límit: no hi ha mínim. El màxim existeix perquè x està limitat (x ≤ 6) i y hi resta: g(0, 4) = −4, g(4, 0) = 8, g(6, 0) = 12. Màxim: 12, al punt (6, 0).
Conclusió: en una regió no acotada, l'existència de l'òptim depèn de la direcció en què creix la funció objectiu.

a) Variables: x = unitats d'A, y = unitats de B. Benefici: f = 30x + 40y. Restriccions: x + y ≤ 50; x + 2y ≤ 80; x ≤ 30; y ≥ 10; x ≥ 0.
Vèrtexs: (0, 10); (30, 10); intersecció de x = 30 amb x + y = 50: (30, 20); intersecció de x + y = 50 i x + 2y = 80: y = 30, x = 20: (20, 30); (0, 40) (de x + 2y = 80 amb x = 0).
f(0, 10) = 400; f(30, 10) = 1300; f(30, 20) = 1700; f(20, 30) = 600 + 1200 = 1800; f(0, 40) = 1600.
Producció òptima: 20 unitats d'A i 30 de B, amb un benefici de 1800 € diaris (s'esgoten les 50 unitats i les 80 hores).
b) Amb g = 30x + 70y: g(20, 30) = 600 + 2100 = 2700, però g(0, 40) = 2800 i g(30, 20) = 2300. L'òptim passa al vèrtex (0, 40): només producte B, amb 2800 € diaris.
Canviar un coeficient de la funció objectiu modifica el pendent de les rectes de nivell i pot desplaçar l'òptim a un vèrtex veí. A (0, 40) s'esgoten les 80 hores de màquina i sobren 10 unitats de capacitat.

a) Maximitzar $B=30x+40y$ amb

La regió és un pentàgon. Vèrtexs: $O(0,0)$; $(40,0)$ (muntatge amb l'eix $x$); $(30,20)$ (fuster i muntatge: restant, $2y=40$); $(15,30)$ (fuster i pintura); $(0,30)$. Valors de $B$: 0; 1200; $900+800=1700$; $450+1200=1650$; 1200. El màxim és 1 700 €, fent 30 cadires i 20 tauletes.

b) A $(30,20)$: fuster $60+60=120$ (s'esgota), muntatge $60+20=80$ (s'esgota), pintura $20$ de 30: sobren 10 hores de pintura.

c) Amb 121 hores de fuster, el nou vèrtex compleix $2x+3y=121,\ 2x+y=80$: $y=20{,}5,\ x=29{,}75$, i $B=1712{,}5$ €: +12,50 € per hora. Amb 81 hores de muntatge: $2x+3y=120,\ 2x+y=81$: $y=19{,}5,\ x=30{,}75$, i $B=1702{,}5$ €: +2,50 € per hora. Convé l'hora de fuster (sempre que costi menys de 12,50 €). Una hora extra de pintura no aporta res: ja en sobren 10, la restricció no és activa.

d) Amb 50 €/tauleta: $B(30,20)=1900$ i $B(15,30)=450+1500=1950$. El pla òptim canvia a 15 cadires i 30 tauletes. En general, amb benefici $b$ per tauleta, $(30,20)$ és òptim mentre el pendent $-\frac{30}{b}$ estigui entre el de la recta de muntatge ($-2$) i el de la de fuster ($-\frac{2}{3}$): $\frac{2}{3}\le\frac{30}{b}\le 2\iff 15\le b\le 45$ €.

Errors típics

• Avaluar la funció objectiu només en alguns vèrtexs o en punts que no són de la regió factible.
• Pensar que un recurs amb hores sobrants també augmenta el benefici si se n'afegeix més.
• A c), arrodonir el nou vèrtex a enters i comparar beneficis que no corresponen al mateix problema.

Conceptes treballats: plantejament de programació lineal, vèrtexs de la regió factible, restriccions actives i folgances, valor marginal d'un recurs, anàlisi de sensibilitat de la funció objectiu.

a) Amb $x$ camions d'A i $y$ de B: minimitzar $C=600x+800y$ amb

La regió és la zona per sobre de les dues rectes al primer quadrant: no és fitada (es pot contractar tants camions com es vulgui). Vèrtexs: $(0,12)$ (la primera recta talla l'eix $y$; compleix $36\ge 15$), el tall de les dues rectes, $x=15-3y\Rightarrow 30-6y+y=12\Rightarrow y=3{,}6,\ x=4{,}2$, i $(15,0)$ (la segona recta talla l'eix $x$; compleix $30\ge 12$).

b) $C(0,12)=9600$, $C(4{,}2;\,3{,}6)=2520+2880=5400$, $C(15,0)=9000$. Com que $C$ creix en allunyar-se de l'origen, el mínim és 5 400 € a $(4{,}2;\,3{,}6)$. Però no es poden contractar 4,2 camions: és una cota inferior del cost, no una solució real.

c) Arrodonir cap avall dona $(4,3)$: $2\cdot 4+3=11\lt 12$, no arriben prou àpats. Provem punts enters propers: $(5,3)$: $5+9=14\lt 15$, no factible; $(4,4)$: $12\ge 12$ i $16\ge 15$, factible, cost 5 600 €; $(6,3)$: factible, 6 000 €; $(5,4)$: 6 200 €. La millor opció és 4 camions de cada proveïdor, 5 600 €. Arrodonir no funciona perquè el vèrtex és a la frontera: en moure'l, es pot sortir de la regió o deixar de ser òptim.

d) No: com que la regió no és fitada, $C$ hi pot prendre valors tan grans com es vulgui (per exemple, $(100,100)$ és factible). No hi ha màxim; en el context, sempre es pot gastar més contractant camions innecessaris.

Errors típics

• Escriure les restriccions amb $\le$ perquè «hi ha un límit de 1 200»: «almenys» vol dir $\ge$.
• Donar com a resposta 4,2 i 3,6 camions, o arrodonir sense comprovar que el punt és factible.
• Afirmar que tota regió no fitada no té òptim: pot tenir mínim i no màxim.

Conceptes treballats: programació lineal de minimització, regió factible no fitada, existència d'òptim, solucions enteres, interpretació en context.

a) Maximitzar $I=5000x+15\,000y$ amb

Vèrtexs: $(10,0)$ i $(30,0)$ a l'eix; $(30,16)$ ($x=30$ amb el pressupost: $5y=80$); $(20,20)$ ($y=x$ amb el pressupost: $7x=140$); $(10,10)$ ($y=x$ amb $x=10$).

b) $I(10,0)=50\,000$; $I(30,0)=150\,000$; $I(30,16)=150\,000+240\,000=390\,000$; $I(20,20)=100\,000+300\,000=400\,000$; $I(10,10)=200\,000$. Òptim: 20 falques i 20 campanyes, amb 400 000 impactes. Cost: $4000+10\,000=14\,000$ €, s'esgota el pressupost (és lògic: el vèrtex òptim és sobre la recta del pressupost).

c) Amb $a$ impactes per campanya: $I(20,20)=100\,000+20a$ i $I(30,16)=150\,000+16a$. El vèrtex $(30,16)$ és millor quan $150\,000+16a\gt 100\,000+20a\iff a\lt 12\,500$. Si cada campanya a xarxes arribés a menys de 12 500 impactes, convindria fer 30 falques i 16 campanyes; amb $a=12\,500$ els dos vèrtexs (i tot el segment entre ells) donen el mateix. Té sentit: com més rendeixen les xarxes, més es desplaça la despesa cap a xarxes, fins al límit que imposa $y\le x$.

d) No és correcte. Un «impacte» és una exposició a l'anunci: la mateixa persona pot sentir diverses falques o veure diverses campanyes, i es compta cada vegada. 400 000 impactes poden correspondre a moltes menys persones diferents. El model maximitza impactes, no abast.

Errors típics

• Traduir «les campanyes a xarxes no superen les falques» com a $x\le y$.
• Oblidar la restricció $x\ge 10$ i incloure l'origen com a vèrtex.
• A c), comparar només un vèrtex amb l'òptim actual sense comprovar que la resta no passa a ser millor.

Conceptes treballats: plantejament de restriccions verbals, vèrtexs de la regió factible, funció objectiu amb paràmetre, anàlisi de sensibilitat, interpretació crítica del model.

a) Maximitzar $B=4x+6y$ amb

Vèrtexs: $(0,0)$; $(500,0)$; $(300,200)$ (llet i envasat: $x=500-y\Rightarrow 1000+y=1200$); $(150,300)$ (llet i cambra); $(0,300)$.

b) $B(500,0)=2000$; $B(300,200)=1200+1200=2400$; $B(150,300)=600+1800=2400$; $B(0,300)=1800$. El màxim, 2 400 €, s'assoleix en dos vèrtexs i, per tant, a tot el segment que els uneix. Passa perquè $B=4x+6y=2(2x+3y)$ és paral·lela a la restricció de la llet: el benefici només depèn dels litres de llet que es fan servir, i qualsevol pla que gasti tota la llet (dins de les altres restriccions) és òptim, amb $B=2\cdot 1200=2400$.

c) Els punts del segment compleixen $2x+3y=1200$ amb $150\le x\le 300$. Perquè $y=\frac{1200-2x}{3}$ sigui enter cal que $x$ sigui múltiple de 3: $x=150,153,\dots,300$, és a dir, $\frac{300-150}{3}+1=51$ solucions enteres. L'envasat utilitzat és $x+y=x+\frac{1200-2x}{3}=400+\frac{x}{3}$, que és mínim per a $x=150$: 150 kg de tendre i 300 de curat, amb 450 kg envasats (en sobren 50).

d) Amb $B=4x+7y$ ja no és paral·lela a cap costat: $B(150,300)=2700$, $B(300,200)=2600$. La solució passa a ser única, $(150,300)$: convé omplir la cambra de curat, que ara és més rendible per litre de llet ($\frac{7}{12}$ contra $\frac{4}{8}$ €/L).

Errors típics

• Donar només un dels dos vèrtexs com a solució, sense veure que tot el segment és òptim.
• Comptar els punts enters del segment com si $x$ pogués ser qualsevol enter entre 150 i 300.
• Pensar que les solucions múltiples són un error del plantejament.

Conceptes treballats: programació lineal, solucions òptimes múltiples, paral·lelisme entre funció objectiu i restricció, solucions enteres sobre un segment, criteri secundari de decisió.

a) Maximitzar $B=300x+500y$ amb

Vèrtexs: $(0,0)$; $(90,0)$ (aigua amb l'eix); $(70,30)$ (aigua i terra: $3x+2(100-x)=270\Rightarrow x=70$); $(20,80)$ (terra i jornals: $y=80$); $(0,90)$ (jornals amb l'eix). Valors: 0; 27 000; 36 000; $6000+40\,000=46\,000$; 45 000. Òptim: 20 ha de blat i 80 de colza, 46 000 €.

b) Aigua utilitzada: $3\cdot 20+2\cdot 80=220$ mil m³; en sobren 50 mil. La restricció $y\le 95$ és redundant: la dels jornals ja obliga a $2y\le 180-x\le 180$, és a dir, $y\le 90\lt 95$. Treure-la no canvia la regió.

c) Amb $3x+2y\le 200$, el punt $(20,80)$ ja no és factible ($220\gt 200$). Nous vèrtexs: $(0,0)$, $(66{,}7;\,0)$, $(10,85)$ (aigua i jornals: restant, $2x=20$), que compleix $x+y=95\le 100$, i $(0,90)$, que gasta 180 mil m³. Valors: 0; 20 000; $3000+42\,500=45\,500$; 45 000. Òptim: 10 ha de blat i 85 de colza, 45 500 €: es perden 500 €. Ara les restriccions actives són l'aigua i els jornals, i la terra deixa de ser-ho: queden 5 ha sense sembrar, perquè no hi ha aigua per regar-les.

d) El pla $(20,80)$ gasta 220 mil m³. Mentre hi hagi com a mínim 220 mil m³, segueix sent factible i òptim (retallar un recurs que sobra no afecta l'òptim). Es pot retallar fins a 220 mil m³, és a dir, 50 mil m³ (un 18,5 %), sense cap pèrdua.

Errors típics

• Considerar la restricció de la colza com a activa i calcular un vèrtex $(0,95)$ que no és de la regió.
• Pensar que una sequera sempre redueix el benefici: només ho fa si l'aigua passa a ser una restricció activa.
• A c), no comprovar que el nou vèrtex compleix la restricció de la terra.

Conceptes treballats: programació lineal, vèrtexs, restriccions actives i redundants, folgança, anàlisi de sensibilitat d'un recurs, interpretació econòmica.

a)

Vèrtexs: $(0,0)$; $(50,0)$; $(40,20)$ (sucre i fruita: restant, $x=40$); $(15,45)$ (fruita i cocció: $2y=90$); $(0,50)$.

b) Amb $B=45x+30y$: $B(50,0)=2250$, $B(40,20)=1800+600=2400$, $B(15,45)=675+1350=2025$, $B(0,50)=1500$. Òptim: 40 lots de melmelada i 20 de compota, 2 400 €. S'esgoten la fruita (60) i el sucre ($80+20=100$); de cocció se'n fan servir $40+60=100$ hores i en sobren 50.

c) A $(40,20)$ s'hi tallen les rectes del sucre (pendent $-2$) i de la fruita (pendent $-1$). El vèrtex és òptim si $1\le\frac{p}{30}\le 2$, és a dir, $30\le p\le 60$. Si $p\gt 60$, convé $(50,0)$: només melmelada fins a esgotar el sucre. Si $10\le p\le 30$, convé $(15,45)$ (s'hi tallen fruita i cocció, pendents $-1$ i $-\frac{1}{3}$), i si $p\le 10$, $(0,50)$.

d) Amb $p=30$, $B=30(x+y)$ és paral·lela a la restricció de la fruita: $B(40,20)=B(15,45)=1800$ i també tots els punts del segment entre ells. Quan els dos productes donen el mateix benefici per lot, només importa gastar tota la fruita; la cooperativa pot triar qualsevol combinació d'aquest segment segons altres criteris (demanda, hores de cocció lliures…).

Errors típics

• Comparar els coeficients de la funció objectiu entre ells i no amb els pendents de les restriccions.
• Dir que l'interval és obert: als extrems el vèrtex continua sent òptim (empatat amb un altre).
• Calcular malament el pendent d'una recta $ax+by=c$: és $-\frac{a}{b}$.

Conceptes treballats: programació lineal, vèrtexs, pendent de rectes, anàlisi de sensibilitat d'un coeficient, solucions múltiples, interpretació econòmica.

a) $x\ge 0{,}4(x+y)\iff 0{,}6x\ge 0{,}4y\iff 3x\ge 2y$. Minimitzar $C=250x+160y$ amb

b) Tall de $x+y=35$ amb $y=1{,}5x$: $2{,}5x=35\Rightarrow (14,21)$. Tall de $x+y=35$ amb $y=8$: $(27,8)$. Tots dos compleixen les altres condicions. La regió és no fitada (s'estén cap a dalt i a la dreta) i té aquests dos vèrtexs. $C(14,21)=3500+3360=6860$ €, $C(27,8)=6750+1280=8030$ €. Mínim: 14 infermeres i 21 auxiliars, 6 860 € per torn. La restricció $x\ge 12$ és redundant: amb $x+y\ge 35$ i $y\le 1{,}5x$, ja cal $2{,}5x\ge 35$, és a dir, $x\ge 14$.

c) No: la regió no és fitada i el cost creix sense límit si s'afegeix personal. El problema només té sentit com a minimització.

d) Ara $x\ge 0{,}5(x+y)\iff y\le x$. El tall de $x+y=35$ amb $y=x$ és $(17{,}5;\,17{,}5)$, que no és enter. Amb enters, cal $x\ge 17{,}5$, és a dir, $x\ge 18$. Amb $x=18$, el mínim d'auxiliars és $y=17$: $C=4500+2720=7220$ €. Amb $x=19,\ y=16$: 7 310 €, més car. Plantilla òptima: 18 infermeres i 17 auxiliars, 7 220 € per torn: la normativa encareix cada torn en 360 € (un 5,2 %).

Errors típics

• Escriure la condició del 40 % com a $x\ge 0{,}4\,y$ (el 40 % és del total, no dels auxiliars).
• Arrodonir $(17{,}5;\,17{,}5)$ a $(17,18)$, que incompleix $y\le x$.
• Pensar que un problema sense màxim està mal plantejat.

Conceptes treballats: traducció de percentatges a inequacions lineals, minimització, regió no fitada, restricció redundant, solucions enteres, cost d'una nova restricció.

a) Restriccions: $x+y\ge 40$, $y\ge 30$, $2x+3y\le 100$, $x\ge 0$. Però $2x+3y=2(x+y)+y\ge 2\cdot 40+30=110$. Qualsevol pla que compleixi els dos mínims necessita almenys 110 hores, i només n'hi ha 100: la regió factible és buida i el problema no té solució.

b) Minimitzar $H=2x+3y$ amb $x+y\ge 40$, $y\ge 30$, $x\ge 0$. La regió no és fitada i té vèrtexs $(10,30)$ (tall de $x+y=40$ i $y=30$) i $(0,40)$. $H(10,30)=20+90=110$ i $H(0,40)=120$. Calen com a mínim 110 hores, amb 10 classes individuals i 30 de col·lectives (coincideix amb la cota de a).

c) Amb $2x+3y\le 120$: vèrtexs $(10,30)$; $(15,30)$ (hores amb $y=30$: $2x=30$); $(0,40)$ (hores amb $x=0$: $y=40$, que compleix just $x+y=40$). La regió és un triangle. Ingressos $I=25x+60y$: $I(10,30)=2050$, $I(15,30)=375+1800=2175$, $I(0,40)=2400$. Òptim: 0 individuals i 40 col·lectives, 2 400 €.

d) Per hora de professorat, una classe individual ingressa $\frac{25}{2}=12{,}5$ €/h i una col·lectiva $\frac{60}{3}=20$ €/h. Com que les hores són el recurs escàs, el model les dedica totes a la classe que en treu més rendiment. Si l'escola vol mantenir classes individuals (per motius pedagògics o de demanda), ha d'afegir una restricció explícita, per exemple $x\ge 10$; aleshores el pla seria $(10,30)$ amb 2 050 € (si manté 120 hores, $x=10$ i $y=33$, amb 2 230 €, perquè les hores que sobren van a les col·lectives). El model només optimitza el que se li demana.

Errors típics

• Intentar trobar vèrtexs d'una regió buida i donar-ne un com a solució.
• Comparar ingressos per classe (60 € és més que 25 €) en lloc d'ingressos per hora, que és el recurs limitant.
• A c), oblidar que $(0,40)$ compleix la restricció $x+y\ge 40$ amb igualtat i descartar-lo.

Conceptes treballats: regió factible buida (problema infactible), minimització d'un recurs, programació lineal amb regió no fitada i fitada, rendiment per unitat de recurs, crítica del model.

a) Minimitzar $C=90x+200y$ amb

Vèrtexs: $(4,10)$ ($x=4$ amb $x+y=14$; compleix $34\ge 30$); $(6,8)$ (tall de $x+y=14$ i $x+3y=30$: $2y=16$); $(30,0)$ ($x+3y=30$ amb l'eix; compleix $30\ge 14$). El punt $(4,\tfrac{26}{3})$ no compleix $x+y\ge 14$, i $(14,0)$ no compleix la de paquets. La regió no és fitada.

b) $C(4,10)=360+2000=2360$; $C(6,8)=540+1600=2140$; $C(30,0)=2700$. Mínim: 6 motos i 8 furgonetes, 2 140 € diaris. A $(6,8)$ es compleixen amb igualtat la de rutes (14) i la de paquets ($240+960=1200$); de motos n'hi ha 2 més del mínim.

c) Amb cost $c$: $C(4,10)=360+10c$, $C(6,8)=540+8c$, $C(30,0)=2700$. $(6,8)$ és millor que $(4,10)$ si $540+8c\lt 360+10c\iff c\gt 90$, i millor que $(30,0)$ si $540+8c\lt 2700\iff c\lt 270$. Si $c\gt 270$ €, convé passar a 30 motos i cap furgoneta. Per a $c=260$: $C(6,8)=2620\lt 2700$, es manté el pla. Per a $c=280$: $C(6,8)=2780\gt 2700$, canvia a $(30,0)$.

d) Els paquets, $40x+120y$, creixen sense límit en una regió no fitada: sempre es poden afegir vehicles. Sense un límit superior (pressupost, flota disponible o conductors) el màxim no existeix. Caldria afegir, per exemple, $90x+200y\le P$ amb un pressupost $P$ donat.

Errors típics

• Incloure com a vèrtexs punts que són talls de rectes però no compleixen totes les restriccions, com $(14,0)$.
• Concloure que, si el combustible s'encareix, sempre convé reduir furgonetes de seguida: el pla es manté fins a $c=270$ €.
• Pensar que una regió no fitada no té ni mínim ni màxim.

Conceptes treballats: programació lineal de minimització, regió no fitada, vèrtexs i restriccions actives, funció objectiu amb paràmetre, existència d'òptims.

a) Minimitzar $C=600x+350y$ amb

Vèrtexs: $(4,6)$ (places i conductors: $x=4$); $(5,4)$ (places amb $x=5$); $(5,5)$ (conductors amb $x=5$). La regió és un triangle.

b) $C(4,6)=2400+2100=4500$; $C(5,4)=3000+1400=4400$; $C(5,5)=4750$. Òptim: 5 grans i 4 petits, 4 400 €. Places: $250+100=350$, cap de buida; queda un conductor lliure.

c) Amb 300 €: $C(4,6)=2400+1800=4200$ i $C(5,4)=3000+1200=4200$: empat, i qualsevol punt del segment entre ells costaria el mateix (però els únics enters són els dos extrems). Passa perquè el cost per plaça s'iguala: $\frac{600}{50}=12$ €/plaça i $\frac{300}{25}=12$ €/plaça. Amb 350 € el petit surt a 14 €/plaça i per això convé omplir primer els grans.

d) Amb $x\le 4$: de $2x+y\ge 14$ i $x+y\le 10$ es dedueix $14-2x\le y\le 10-x$, que exigeix $14-2x\le 10-x\iff x\ge 4$. Per tant $x=4$ i $y=6$: és l'única opció. Cost: 4 500 €, 100 € més que el pla inicial, i s'ocupen els 10 conductors. Si s'espatllés un altre autocar gran, el problema ja no tindria solució amb els conductors disponibles.

Errors típics

• Plantejar les places com a $x+y\ge 350$, barrejant autocars amb persones.
• Oblidar la restricció de conductors i proposar més de 10 autocars.
• A d), buscar el nou òptim avaluant els vèrtexs antics, que ja no són factibles.

Conceptes treballats: programació lineal amb solució entera, vèrtexs, solucions múltiples, cost per unitat, sensibilitat davant la pèrdua d'un recurs.