Al mòdul anterior vam aprendre a analitzar: expressar costos, calcular-los i recolzar-nos en les estructures de dades adequades. A partir d'aquí, Rutalia canvia de pregunta. Ja no vol saber quant costa una operació, sinó quina és la millor decisió possible: quantes hores de furgoneta i quantes de bicicleta elèctrica contracto demà per lliurar el màxim de paquets sense passar-me de pressupost? La programació lineal (PL) és l'eina més antiga, més estudiada i més utilitzada a la indústria per respondre aquesta mena de preguntes, i és la porta d'entrada natural a tot el mòdul d'optimització: ens obliga a pensar en termes de variables de decisió, funció objectiu i restriccions, un vocabulari que reutilitzarem a cada lliçó que ve.

1. D'analitzar a decidir: què és un problema d'optimització
2. Formulació d'un programa lineal
3. La regió factible: intuïció geomètrica amb un exemple resoluble a mà
4. El mètode símplex, a vista d'ocell
5. Resolució pràctica amb scipy.optimize.linprog
6. Programació lineal entera: quan les variables no es poden partir

Tot problema d'optimització, sigui lineal o no, es compon de tres peces:

• Variables de decisió: els números que nosaltres controlem. A Rutalia: quantes hores de furgoneta contractar, quants paquets assignar a cada repartidor, quina ruta seguir.
• Funció objectiu: una fórmula que, donades unes variables de decisió, retorna un número que volem maximitzar (paquets lliurats, ingressos) o minimitzar (quilòmetres, cost, emissions).
• Restriccions: les condicions que una solució ha de complir per ser vàlida: pressupost màxim, hores de personal disponibles, capacitat de càrrega.

Una assignació de valors a les variables que compleix totes les restriccions s'anomena solució factible. La millor solució factible segons la funció objectiu és la solució òptima. Optimitzar és, literalment, buscar el millor punt dins del conjunt de solucions factibles.

Un problema és de programació lineal quan la funció objectiu i totes les restriccions són lineals: sumes de variables multiplicades per constants, sense productes entre variables, sense quadrats, sense funcions estranyes. 3x + 5y és lineal; x·y o x² no ho són. Aquesta limitació, que sembla severa, resulta enormement productiva: els problemes lineals es resolen de manera exacta i rapidíssima fins i tot amb milions de variables, cosa que veurem que no passa amb els problemes combinatoris de les properes lliçons.

Formular bé és el 80 % de la feina. Vegem el problema concret de Rutalia per al torn de matí:

• Una hora de furgoneta lliura de mitjana 30 paquets i costa 25 € (combustible + conductor).
• Una hora de bicicleta elèctrica lliura de mitjana 15 paquets i costa 10 €.
• El pressupost del torn és de 400 €.
• Entre tots els repartidors disponibles es poden cobrir com a màxim 25 hores de feina.
• Només hi ha furgonetes per cobrir 12 hores de furgoneta com a màxim.

Traducció pas a pas:

1. Variables: x = hores de furgoneta, y = hores de bici. (De moment acceptem valors fraccionaris: 10,5 hores és una assignació vàlida.)
2. Objectiu: maximitzar Z = 30x + 15y (paquets lliurats).
3. Restriccions:
   • Pressupost: 25x + 10y ≤ 400
   • Personal: x + y ≤ 25
   • Flota: x ≤ 12
   • No negativitat: x ≥ 0, y ≥ 0 (no existeixen hores negatives; sembla obvi, però cal declarar-ho).

El programa lineal complet queda així:

Observa que cada línia és una desigualtat lineal. Si l'enunciat ens demanés alguna cosa com "el rendiment de la furgoneta cau un 2 % per cada hora acumulada", la relació deixaria de ser lineal i necessitaríem altres tècniques.

Amb dues variables podem dibuixar el problema. Cada restricció és una recta que divideix el pla en dues meitats; la regió factible és la intersecció de totes les meitats vàlides: un polígon convex.

Per al nostre problema, els vèrtexs del polígon factible són:

Per què n'hi ha prou de mirar els vèrtexs? La funció objectiu 30x + 15y = Z defineix, per a cada valor de Z, una recta. En augmentar Z, aquesta recta es desplaça paral·lelament. El Z més gran assolible és el darrer instant en què la recta encara toca la regió factible, i aquest darrer contacte es produeix sempre en un vèrtex (o, en cas d'empat, en tota una aresta). Aquest és el teorema fonamental de la programació lineal: si existeix òptim finit, hi ha un vèrtex òptim.

Comprovem el vèrtex guanyador a mà. Intersecció de pressupost i personal:

Decisió òptima: 10 hores de furgoneta i 15 de bici → 525 paquets, gastant exactament els 400 € i les 25 hores de personal. Fixa't en un detall amb contingut econòmic: la restricció de flota (x ≤ 12) no està saturada — comprar més furgonetes no milloraria res; contractar més personal o ampliar pressupost, sí. Aquesta mena de lectura ("quina restricció m'està frenant?") és una de les raons per les quals la PL és tan valuosa per decidir.

Amb 2 variables dibuixem; amb 200.000 no. El mètode símplex (Dantzig, 1947) automatitza exactament la intuïció anterior:

1. Parteix d'un vèrtex factible qualsevol (per exemple, l'origen).
2. Mira les arestes que surten d'aquest vèrtex i en tria una per la qual la funció objectiu millora.
3. Avança per aquesta aresta fins al vèrtex següent.
4. Repeteix fins que cap veí millora: aquest vèrtex és l'òptim.

En el nostre exemple, un recorregut possible seria (0,0) → (12,0) → (12,10) → (10,15), millorant Z a cada salt (0 → 360 → 510 → 525). Com que la regió és convexa, un vèrtex sense veïns millors és un òptim global, no només local — no hi ha "valls" on quedar atrapat, a diferència del que veurem amb les metaheurístiques a 02-04.

Dos apunts de complexitat, connectant amb el mòdul 1:

• En el pitjor cas teòric, símplex pot visitar un nombre exponencial de vèrtexs (existeixen instàncies patològiques construïdes expressament).
• A la pràctica és gairebé sempre rapidíssim, i a més existeixen algorismes de punt interior amb garantia polinòmica. Per a l'enginyer, el missatge és: un PL amb milers o milions de variables contínues és un problema resolt; el passes a un solver i llestos.

No implementarem símplex: és un algorisme delicat de programar bé (degeneració, estabilitat numèrica) i els solvers existents porten dècades d'enginyeria al damunt. La nostra feina és formular; la del solver, resoldre.

scipy inclou un solver de PL de qualitat industrial (HiGHS). La seva convenció: sempre minimitza i les desigualtats són de tipus ≤. Com que volem maximitzar Z, minimitzem −Z (és el mateix problema amb el signe canviat).

Desglossem el que pot despistar la primera vegada:

• c són els coeficients de l'objectiu amb el signe canviat, perquè linprog minimitza. Al final recuperem el valor real amb -res.fun.
• Cada fila d'A_ub és una restricció ≤, i b_ub en guarda el costat dret en el mateix ordre. La restricció x ≤ 12 s'escriu com la fila [1, 0] (coeficient 1 per a x, 0 per a y).
• bounds cobreix la no negativitat; l'hauríem pogut posar a A_ub, però és més clar (i més eficient per al solver) declarar-la com a fita.
• Comprova sempre res.status: 0 és òptim; 2 significa infactible (les restriccions es contradiuen: per exemple, exigir 30 hores amb 25 de disponibles); 3 significa no fitat (t'has oblidat una restricció i l'objectiu pot créixer sense límit — gairebé sempre és un error de formulació, no una màquina d'imprimir diners).

Si demà Rutalia afegeix motos (20 paquets/h, 15 €/h), no cal repensar res: una variable més, una columna més a A_ub, i el mateix codi resol el problema en mil·lisegons. Aquesta escalabilitat sense dolor és el gran regal de la linealitat.

Les nostres "hores" admetien fraccions. Però moltes decisions de Rutalia són indivisibles: no es poden llogar 2,5 furgonetes ni obrir 0,75 micromagatzems. Si exigim que les variables siguin enteres, el problema passa a anomenar-se programació lineal entera (PLE o ILP), i canvia de naturalesa completament.

La temptació òbvia — "resolc el PL continu i arrodoneixo" — falla, i convé veure'n un contraexemple amb números. Suposa que Rutalia estudia quants contractes mensuals signar de furgonetes grans (x, aporten 13 punts de capacitat) i petites (y, n'aporten 8), amb dos recursos limitats:

• Òptim del PL continu (ignorant la integritat): x = 2,5, y = 3,75, amb valor 62,5.
• Arrodoniment a l'enter més proper, (3, 4): infactible (viola x + 2y ≤ 10: dona 11).
• Arrodoniment cap avall, (2, 3): factible, valor 50.
• Òptim enter real: (2, 4), valor 58 — que no s'obté arrodonint l'òptim continu en cap direcció.

Amb 2 variables l'error sembla petit; amb centenars, l'arrodoniment pot violar restriccions en cadena o deixar-se molt valor pel camí. Geomètricament, l'explicació és que el conjunt factible enter ja no és un polígon continu sinó un núvol de punts aïllats, i el teorema del vèrtex òptim deixa d'aplicar.

scipy també resol PLE (paràmetre integrality, disponible amb el mètode HiGHS):

I per què diem que la PLE "és més dura"? Perquè exigir integritat converteix un problema resoluble en temps polinòmic en un de NP-dur: en el pitjor cas, no es coneix (i probablement no existeix) cap algorisme essencialment millor que explorar una quantitat exponencial de combinacions. De fet, molts problemes combinatoris famosos — la motxilla, el viatjant — es poden escriure com a PLE. Els solvers moderns els ataquen amb una tècnica anomenada branch and bound, que estudiarem a fons a la lliçó 02-03; i quan ni això no arriba, entren les metaheurístiques de 02-04 i 02-05. Aquesta és exactament la ruta que recorrerem en aquest mòdul.

• Oblidar la no negativitat. Sense x, y ≥ 0 el solver pot retornar "hores negatives" (o un problema no fitat!). Declara sempre les fites naturals de cada variable.
• Confondre el sentit de l'optimització. linprog minimitza. Si maximitzes, nega els coeficients de c i recorda negar res.fun en llegir el resultat. És el despist número u.
• Barrejar unitats. Si el pressupost és en euros i una fila d'A_ub barreja euros amb hores, el model és brossa silenciosa: resoldrà "bé" un problema que no és el teu. Escriu les unitats de cada restricció en un comentari.
• No mirar res.status. Un model infactible o no fitat també "acaba"; si uses res.x sense comprovar l'estat, propagaràs None o valors sense sentit.
• Arrodonir un PL continu per obtenir enters. Com acabem de veure, pot ser infactible o subòptim. Si les variables són indivisibles, usa integrality (o modela amb PLE directament).
• Forçar linealitat on no n'hi ha. Si el cost per hora canvia amb el volum (descomptes per trams), de vegades es pot linealitzar per trams amb variables extra; de vegades no. Sigues honest amb el model: un PL elegant d'un problema equivocat no decideix res d'útil.
• Consell: abans de programar, escriu el model en paper amb el format maximitzar / subjecte a. Si no el saps escriure així, encara no entens el problema — i scipy tampoc no l'entendrà per tu.

1. Torn de tarda. A la tarda el trànsit empitjora: la furgoneta baixa a 24 paquets/hora (mateix cost, 25 €/h) i la bici manté 15 paquets/hora a 10 €/h. Pressupost: 300 €; hores de personal: 20; màxim de furgoneta: 8 hores. Formula el PL i resol-lo gràficament (enumera els vèrtexs i avalua l'objectiu a cadascun).

2. Tres modes de transport. Afegeix motos al model original de la lliçó: 22 paquets/h i 15 €/h, amb un màxim de 10 hores de moto. El pressupost puja a 500 € i el personal a 30 hores (furgoneta: màxim 12 h, com abans). Escriu el codi linprog complet i obtén l'assignació òptima. Queda alguna restricció sense saturar?

3. Per què no arrodonir? Considera el PLE maximitzar 5x + 4y subjecte a 6x + 4y ≤ 24, x + 2y ≤ 6, x, y ≥ 0 enteres. (a) Resol el PL continu a mà (dues restriccions, dues variables). (b) Arrodoneix el resultat i comprova'n la factibilitat. (c) Troba l'òptim enter per enumeració (hi ha pocs punts factibles) i compara.

Exercici 1.

Vèrtexs i valors: (0,0)→0; (8,0)→192; (8,10) (flota ∩ pressupost: 25·8+10y=300 → y=10) → 342; pressupost ∩ personal: 25x+10(20−x)=300 → 15x=100 → x=20/3≈6,67, y≈13,33 → 24·6,67+15·13,33 ≈ 360; (0,20)→300. Òptim: x = 20/3 ≈ 6,67 hores de furgoneta i y = 40/3 ≈ 13,33 de bici, amb 360 paquets. Nota: surt fraccionari i és vàlid, perquè les hores sí que són divisibles. Compara amb el torn de matí: en empitjorar el rendiment de la furgoneta, l'òptim desplaça càrrega cap a les bicis i la restricció de flota deixa d'estar saturada.

Exercici 2.

Òptim: 10 h de furgoneta, 10 h de bici i 10 h de moto → 670 paquets. Verifica les restriccions amb la solució retornada (un assert de dues línies evita decisions basades en una lectura errònia): pressupost 25·10 + 10·10 + 15·10 = 500 ✔ saturat; personal 10+10+10 = 30 ✔ saturat; motos z = 10 ✔ saturada. L'única restricció sense saturar és la flota de furgonetes (x = 10 < 12): amb aquests preus i rendiments, comprar més furgonetes no aportaria res; el coll d'ampolla són el pressupost i el personal. Observa que el solver no omple la furgoneta fins al topall encara que sigui el mode que més paquets lliura per hora: per euro gastat, la bici (1,5 paq/€) i la moto (≈1,47 paq/€) rendeixen més que la furgoneta (1,2 paq/€), i el pressupost és escàs.

Exercici 3. (a) Continu: intersecció 6x+4y=24 i x+2y=6 → x = 3, y = 1,5, valor Z = 21. (b) Arrodoniments: (3,2) viola 6x+4y ≤ 24 (26 > 24); (3,1) és factible amb Z = 19. (c) Enumerant els enters factibles, l'òptim és (4,0) amb Z = 20 (comprova: 24 ≤ 24, 4 ≤ 6). Ni (3,1) ni cap arrodoniment de l'òptim continu no el troba: cal cercar entre els enters, que és just el que farà branch and bound a 02-03.

Hem fet el salt d'analitzar a decidir. La programació lineal ens ha ensenyat el vocabulari de tot el mòdul — variables de decisió, funció objectiu, restriccions, regió factible, òptim — i ens ha deixat dos resultats pràctics: quan el problema és lineal i continu, un solver com linprog el resol de manera exacta i gairebé instantània (formular és la nostra feina; resoldre, la seva); i quan les variables han de ser enteres, el problema esdevé NP-dur i l'arrodoniment no és una drecera vàlida. Just aquí comença la lliçó següent: la majoria de les decisions reals de Rutalia — quins paquets carrego en aquesta furgoneta, en quin ordre visito aquestes adreces — són intrínsecament discretes. Benvinguts a l'optimització combinatòria, on l'espai de solucions no és un polígon suau sinó una explosió de combinacions, i on triar bé l'algorisme marca la diferència entre segons i segles.