Flashcards: Programació lineal

Totes les targetes del tema

Per fer-hi una ullada ràpida o repassar-les en paper.

1. 1. Què és un problema de programació lineal amb dues variables?

   Maximitzar o minimitzar una funció objectiu lineal $f(x, y) = ax + by$ subjecta a unes restriccions que són inequacions lineals.

2. 2. Primer pas per plantejar un problema de programació lineal amb context?

   Definir les variables: què és $x$ i què és $y$, amb unitats. Després escrius la funció objectiu i les restriccions.

3. 3. Què és la funció objectiu?

   La funció lineal que vols optimitzar, com un benefici, un cost o uns ingressos: $f(x, y) = ax + by$.

4. 4. Com tradueixes «com a mínim» i «com a màxim» (o «no pot superar») a una restricció?

   «Com a mínim» o «almenys» és $\geq$. «Com a màxim» o «no pot superar» és $\leq$.

5. 5. Què volen dir les restriccions $x \geq 0$ i $y \geq 0$?

   Són les condicions de no-negativitat: les quantitats no poden ser negatives. Limiten la regió al primer quadrant.

6. 6. Com tradueixes «almenys el 30 % del total han de ser del tipus $x$»?

   $x \geq 0{,}3\,(x + y)$, que equival a $0{,}7x - 0{,}3y \geq 0$.

7. 7. Què representa geomètricament una inequació lineal $ax + by \leq c$?

   Un semiplà limitat per la recta $ax + by = c$.

8. 8. Com trobes de pressa els talls d'una recta $ax + by = c$ amb els eixos?

   Fas $x = 0$ per al tall amb l'eix vertical i $y = 0$ per a l'horitzontal. Per exemple, $3x + 4y = 12$ talla a $(4, 0)$ i $(0, 3)$.

9. 9. Com decideixes quin semiplà correspon a una inequació?

   Hi substitueixes un punt de fora de la recta, sovint $(0, 0)$: si compleix la inequació, el semiplà és el del costat d'aquest punt; si no, l'altre.

10. 10. Què és la regió factible?

    El conjunt de punts $(x, y)$ que compleixen totes les restriccions alhora: la intersecció de tots els semiplans.

11. 11. Com comproves si un punt pertany a la regió factible?

    Substitueixes les seves coordenades a totes les restriccions: n'hi ha prou que n'incompleixi una perquè quedi fora.

12. 12. Com calcules un vèrtex de la regió factible?

    Resols el sistema format per les dues rectes que s'hi tallen i comproves que el punt compleix totes les altres restriccions.

13. 13. Què vol dir que una regió factible és acotada (fitada)?

    Que és un polígon tancat: no s'estén indefinidament en cap direcció.

14. 14. Teorema fonamental: on s'assoleixen el màxim i el mínim en una regió factible acotada?

    Si la regió és acotada i no buida, la funció objectiu té màxim i mínim, i tots dos s'assoleixen en algun vèrtex.

15. 15. Mètode dels vèrtexs: quins passos segueixes?

    Calcules tots els vèrtexs, avalues la funció objectiu a cadascun i tries el valor més gran per al màxim o el més petit per al mínim.

16. 16. Què són les rectes de nivell de $f(x, y) = ax + by$?

    Les rectes $ax + by = k$: els punts on $f$ val $k$. Són paral·leles entre si; desplaçant-les en el sentit en què $f$ creix, l'últim punt de la regió que toquen és el màxim.

17. 17. Si la regió factible no és acotada, la funció objectiu sempre té màxim i mínim?

    No: pot créixer o decréixer sense límit, i llavors li falta el màxim, el mínim o tots dos. Si l'òptim existeix, també s'assoleix en un vèrtex.

18. 18. Regió no acotada «cap amunt», per restriccions de «com a mínim», i $f = ax + by$ amb $a, b > 0$. Hi ha màxim? I mínim?

    No hi ha màxim, perquè $f$ creix sense límit. El mínim sí que existeix i és en un vèrtex: és el cas típic de minimitzar costos.

19. 19. Quan té infinites solucions òptimes un problema de programació lineal?

    Quan dos vèrtexs consecutius donen el mateix valor òptim: tots els punts del costat que els uneix també són òptims. Passa quan les rectes de nivell són paral·leles a aquell costat.

20. 20. Què vol dir que un problema de programació lineal és infactible?

    Que la regió factible és buida: cap punt compleix totes les restriccions alhora, o sigui que el problema no té solució.

21. 21. Al punt òptim, com saps si un recurs s'esgota o en sobra?

    Substitueixes l'òptim a la restricció: si es compleix amb igualtat, el recurs s'esgota; si no, en sobra la diferència entre el disponible i el gastat.

22. 22. Què és una restricció redundant?

    La que no modifica la regió factible, perquè les altres restriccions ja la garanteixen. Treure-la no canvia l'òptim.

23. 23. Les variables han de ser nombres enters i el vèrtex òptim no ho és. Què fas?

    No n'hi ha prou d'arrodonir: comproves els punts enters de la regió propers al vèrtex i tries el millor que compleixi totes les restriccions.

24. 24. Si canvia un coeficient de la funció objectiu, què pot canviar de la solució?

    La regió factible i els vèrtexs no canvien, perquè les restriccions són les mateixes. Pot canviar el valor òptim i quin vèrtex és l'òptim.