Exercicis: Casos especials: solució única, múltiple, no acotada o infactible

La figura mostra dues regions factibles: la del panell A i la del panell B, tal com es mostra a la figura.

Indica quina d'elles és acotada i quina no, explicant el criteri que has utilitzat per decidir-ho.

Verdader o fals, raonant la resposta: «Si la regió factible d'un problema de programació lineal no és acotada, el problema mai no té solució òptima». Il·lustra el teu raonament amb l'exemple de $F(x, y) = x + y$ a la regió $x \geq 0$, $y \geq 0$, $x + y \geq 2$.

A la figura s'ha representat una regió factible i una recta de nivell de la funció objectiu $F(x, y) = 2x + y$ corresponent al valor $8$, tal com es mostra a la figura.

• a) Explica quina particularitat presenta la posició d'aquesta recta respecte de la regió.

• b) Indica el valor màxim de $F$ i dona dues solucions òptimes diferents.

Representa les rectes $x + y = 2$ i $x + y = 5$ i justifica, a partir del dibuix, que el sistema format per $x \geq 0$, $y \geq 0$, $x + y \leq 2$ i $x + y \geq 5$ no té cap solució. Com es diu en programació lineal que la regió factible és buida?

En Lucas s'enfronta al següent problema de programació lineal: maximitzar la funció $F(x, y) = 3x + 2y$ subjecta a les restriccions $x \geq 0$, $y \geq 0$ i $x + y \geq 4$.

En Lucas dibuixa la regió factible, calcula els vèrtexs $A(4, 0)$ i $B(0, 4)$, avalua la funció objectiu en tots dos ($F(4, 0) = 12$ i $F(0, 4) = 8$) i conclou: «El valor màxim és $12$ i s'assoleix en el punt $(4, 0)$».

1. a) Explica detalladament per què el procediment d'en Lucas conté un error conceptual greu, descrivint la forma geomètrica de la regió factible.
2. b) Justifica formalment per què la funció $F(x, y)$ no té màxim en aquest recinte i proposa les coordenades d'un punt factible on el valor de $F$ sigui estrictament més gran que $100$.
3. c) Si l'enunciat hagués demanat minimitzar $F(x, y)$ en lloc de maximitzar-la, hauria estat vàlid el càlcul d'en Lucas per trobar la solució òptima? Raona la teva resposta indicant el valor mínim si existeix.

Considera la regió factible tancada i acotada definida per les restriccions:

$x \geq 0$, $y \geq 0$, $x + 2y \leq 6$ i $2x + y \leq 6$.

Els seus vèrtexs són $O(0, 0)$, $A(3, 0)$, $B(2, 2)$ i $C(0, 3)$.

Es vol maximitzar la funció objectiu $F(x, y) = k \cdot x + 4y$, on $k$ és una constant real desconeguda.

1. a) Determina el valor del paràmetre $k$ perquè el problema tingui solució múltiple (infinites solucions òptimes) que continguin el vèrtex $C(0, 3)$.
2. b) Per a aquest valor de $k$, identifica el segment de la frontera on s'assoleixen aquestes solucions i calcula el valor màxim comú de la funció.
3. c) Escriu les coordenades d'un punt factible amb coordenades no enteres que també sigui solució òptima del problema.

Maximitza la funció objectiu $F(x, y) = 2x + 4y$ subjecta a $x \geq 0$, $y \geq 0$, $x + 2y \leq 8$ i $x + y \leq 5$.

• a) Troba els vèrtexs de la regió factible i avalua $F$ en aquests.

• b) Observaràs que el valor màxim es repeteix en dos vèrtexs: explica què significa això i escriu l'expressió de tots els punts òptims com a segment.

• c) Dona dues solucions òptimes de coordenades enteres.

Sigui la regió definida per $x \geq 0$, $y \geq 0$, $x + y \geq 3$ i $3x + y \geq 5$.

• a) Comprova que no és acotada i troba els seus vèrtexs.

• b) Estudia si la funció objectiu $F(x, y) = 3x + 2y$ assoleix un màxim a la regió.

• c) Estudia si assoleix un mínim i, en cas afirmatiu, calcula'l.

Una pastisseria rep una comanda d'almenys $50$ pastissos i $40$ braços de gitano per a una setmana. Cada pastís requereix $2$ hores d'obrador i cada braç, $1$ hora, i l'obrador només disposa de $60$ hores setmanals.

• a) Planteja el sistema de restriccions i demostra que la regió factible és buida.

• b) Proposa una modificació d'una sola dada de l'enunciat que faci el problema factible, i comprova-ho.

Sigui la regió no acotada definida per $x \geq 0$, $y \geq 0$, $x + 2y \geq 4$ i $2x + y \geq 4$, i la funció objectiu $F(x, y) = ax + 2y$ amb $a > 0$.

• a) Troba els vèrtexs de la regió.

• b) Avalua $F$ a cada vèrtex.

• c) Discuteix, segons els valors de $a$, en quin punt s'assoleix el mínim de $F$, assenyalant els casos amb solució múltiple.

Una cooperativa agrària de la comarca d'Antequera (Màlaga) planifica la producció mensual d'oli d'oliva verge extra ($x$, en centenars de litres) i oli d'oliva verge ($y$, en centenars de litres). Disposa de les següents limitacions de recursos i compromisos comercials:

• Capacitat màxima d'envasament: $x + y \leq 50$.

• Hores de molturació disponibles: $2x + y \leq 80$.

• Compromís mínim de subministrament amb una distribuïdora: $x + y \geq 60$.

• Condicions de no-negativitat: $x \geq 0$, $y \geq 0$.

1. a) Abans de fer qualsevol càlcul analític o representació gràfica, analitza conjuntament les restriccions $x + y \leq 50$ i $x + y \geq 60$. Estima raonadament si la cooperativa podrà trobar algun pla de producció viable que satisfaci totes les condicions.
2. b) Comprova analíticament la teva estimació analitzant la compatibilitat del sistema d'inequacions i classifica el tipus de regió factible que s'obté.
3. c) Si la distribuïdora renegocia el seu contracte i redueix el compromís mínim a $x + y \geq 30$, mantenint-se les altres restriccions, determina si el problema de maximitzar els ingressos $I(x, y) = 400x + 300y$ passa a tenir solució única, múltiple, no acotada o si continua sent infactible. Justifica la teva conclusió.

Una empresa de logística i distribució de paqueteria urgent que opera entre Madrid i el corredor del Henares planifica la seva flota diària utilitzant furgonetes elèctriques ($x$) i furgonetes dièsel de baixes emissions ($y$).

Les condicions d'operativitat i acords mediambientals són:

• El nombre total de vehicles en repartiment no pot excedir de $14$ al dia ($x + y \leq 14$).

• Per les limitacions de punts de recàrrega i emissions permeses, s'ha de complir $x + 2y \leq 20$.

• Per compromisos contractuals fixos, han d'operar almenys $2$ vehicles elèctrics ($x \geq 2$) i almenys $4$ vehicles dièsel ($y \geq 4$).

El benefici net diari generat s'estima en $150$ euros per cada furgoneta elèctrica i $300$ euros per cada furgoneta dièsel, sent la funció objectiu $B(x, y) = 150x + 300y$.

1. a) Modelitza matemàticament el recinte factible, determina les coordenades de tots els seus vèrtexs i comprova que es tracta d'un polígon acotat.
2. b) Demostra analíticament que la funció de benefici $B(x, y)$ assoleix el seu valor màxim en infinits punts de la regió factible (solució múltiple). Justifica la relació geomètrica entre les rectes de nivell de $B$ i els costats del recinte.
3. c) Troba totes les solucions òptimes que utilitzin un nombre enter de vehicles de cada tipus. Si l'equip directiu vol maximitzar el benefici però, a igualtat de guanys, prefereix minimitzar la petjada de carboni global usant el nombre més gran possible de vehicles elèctrics, quina combinació concreta hauria de triar?

Un festival benèfic ven abonaments generals ($x$) i abonaments amb zona d'acampada ($y$). Pel contracte amb el recinte s'ha de complir $2x + 3y \leq 120$ (unitats d'espai) i $x + y \leq 50$ (aforament), i l'organització es compromet amb el patrocinador a vendre almenys $12$ abonaments generals: $x \geq 12$. La recaptació és $F(x, y) = 20x + 30y$ euros.

• a) Planteja el sistema complet i troba els vèrtexs de la regió factible.

• b) Calcula la recaptació màxima.

• c) Comprova que el màxim s'assoleix en dos vèrtexs alhora i explica quina particularitat té la funció objectiu respecte d'una de les restriccions.

• d) Dona tres combinacions enteres diferents d'abonaments que produeixin la recaptació màxima.

Demostra que amb les restriccions $x \geq 0$, $y \geq 0$, $x + y \leq 4$ i $x + 2y \leq 5$, la funció objectiu $F(x, y) = x + 2y$ assoleix el seu valor màxim en infinits punts de la regió factible.

• a) Troba els vèrtexs de la regió i el valor màxim de $F$.

• b) Identifica el segment de punts òptims escrivint els seus extrems.

• c) Dona tres solucions òptimes diferents, dues de les quals de coordenades enteres.

Considera el sistema format per $x \geq 0$, $y \geq 0$, $x + y \geq 6$ i $x + 2y \leq k$, on $k$ és un paràmetre real.

• a) Representa la situació per a $k = 4$, $k = 6$ i $k = 10$.

• b) Determina per a quins valors de $k$ la regió factible és buida, per a quins consta d'un únic punt i per a quins té àrea positiva.

Sigui la regió no acotada definida per $x \geq 0$, $y \geq 0$, $x + y \geq 2$ i $2x + y \geq 2$, i la funció objectiu $F(x, y) = x - 2y$.

• a) Troba els vèrtexs de la regió.

• b) Exhibeix una família de punts factibles que demostri que $F$ no assoleix cap màxim.

• c) Exhibeix una altra família de punts factibles que demostri que $F$ tampoc no assoleix cap mínim.

• d) Quina condició sobre els coeficients de la funció objectiu i la direcció en què creix la regió explica aquest comportament?

Per analitzar problemes de programació lineal on intervenen casos especials (regions no acotades o solucions múltiples), habitualment es plantegen dues estratègies:

• Mètode 1 (Avaluació exclusiva de vèrtexs): Trobar els punts de tall de les rectes frontera i avaluar algebraicament la funció objectiu en aquests, triant el valor més gran i el més petit.

• Mètode 2 (Feix de rectes de nivell i vector director): Traçar la direcció del vector de coeficients de la funció objectiu $(a, b)$ i desplaçar la recta $ax + by = k$ en el sentit d'optimització sobre la regió factible.

Considera la regió factible delimitada per:

$x \geq 0$, $y \geq 0$, $x + 2y \geq 6$, $x - y \leq 3$.

1. a) Representa esquemàticament la regió factible, calcula els seus vèrtexs i justifica per què és una regió no acotada.
2. b) Es vol maximitzar la funció $F(x, y) = 2x + y$. Si un alumne aplica mecànicament el Mètode 1, a quina conclusió errònia arriba? Explica com el Mètode 2 permet detectar immediatament que el problema no té màxim finit.
3. c) Si ara es demana minimitzar la funció $G(x, y) = x + 2y$ sobre aquest mateix recinte, compara l'eficàcia de tots dos mètodes per detectar que el problema presenta infinites solucions òptimes (solució múltiple) i escriu l'expressió analítica de tots els punts que fan mínima $G$.

Considera el sistema d'inequacions en el pla afí que defineix una regió factible subjecta a un paràmetre real $m$:

$x \geq 0$, $y \geq 0$, $x + y \leq 6$, $y - x \leq 2$, $x \geq m$.

Es defineix la funció objectiu $F(x, y) = a \cdot x + y$, on $a$ és un paràmetre real.

1. a) Determina raonadament per a quins valors del paràmetre $m$ el problema és infactible (la regió factible és el conjunt buit).
2. b) Fixat el paràmetre $m = 1$, troba les coordenades dels quatre vèrtexs que delimiten el polígon factible resultant.
3. c) Mantenint $m = 1$, estudia quins valors ha de prendre el paràmetre $a$ a la funció $F(x, y) = a \cdot x + y$ perquè el problema de maximitzar $F$:

• Tingui solució múltiple, indicant sobre quina aresta del polígon es situen les solucions òptimes per a cada valor de $a$ trobat.

• Tingui solució única exactament en el vèrtex amb més ordenada $y$ del recinte.

1. d) Sense modificar la funció objectiu $F(x, y) = x + y$, proposa el canvi d'una sola desigualtat del sistema inicial (amb $m = 1$) perquè el problema de maximització passi a ser no acotat (sense solució òptima finita) i justifica per què es produeix aquest comportament.

Repte del tema. Com optimitzar la despesa energètica d'un negoci local? Assumeix el rol d'assessor financer d'un forn de pa artesanal i dissenya el seu pla de fornada per minimitzar costos energètics.

1. Dades reals: Entra al web de Red Eléctrica (REE/ESIOS) i anota el preu mitjà del $kWh$ d'ahir en hores vall ($x$) i hores punta ($y$), utilitzant decimals (per exemple, $0,09$ €/$kWh$).

2. Modelització i GeoGebra: Defineix dues variables (lots produïts en vall i en punta) i estableix almenys quatre restriccions reals (capacitat dels forns, demanda diària mínima i pressupost). Representa a GeoGebra la regió factible i calcula analíticament les coordenades dels seus vèrtexs determinant la solució única òptima.

3. Simulació de casos especials: Modifica raonadament les restriccions per generar dos escenaris alternatius: un amb regió no acotada (o infactible) i un altre on la funció objectiu paral·lela a una restricció produeixi infinites solucions (solució múltiple).

4. Informe executiu: Elabora una proposta breu (una pàgina) amb la gràfica, la taula de vèrtexs, la solució òptima i la interpretació dels casos especials simulats.

Es valorarà:

• Rigor en l'obtenció de dades de REE i la seva traducció al sistema d'inequacions.

• Precisió en el càlcul analític de vèrtexs i representació a GeoGebra de la regió factible.

• Justificació matemàtica correcta dels casos especials analitzats.

• Claredat comunicativa i coherència de la proposta final.