Problema di ottimizzazione
Salve, ho intenzione di tentare il concorso nel Sant'Anna a Pisa e cercando tra i problemi degli anni precedenti, sono incappato in questo quesito di ottimizzazione
"Esistono due tipi di mangimi per conigli, A e B. La combinazione di nutrienti in ogni sacco è la seguente:
Mangime A Proteine 1 Carboidrati 6 coloranti 1 grasso 4
Mangime B Proteine 2 Carboidrati 5 coloranti 3 grasso 3
Per una corretta dieta, i coniglie necessitano di almeno 7 proteine, 28 carboidrati, non più di 13 coloranti, non più di 24 grassi.
1-Essendo 8€ il prezzo di un sacco del mangime A e 3€ il prezzo di un sacco di mangime B, qual è la combinazione migliore per minimizzare il costo?
2-Posto p il prezzo di un sacco di A (sempre 3€ per B) determinare l'insieme di valori per cui la scelta effettuata al punto precedente è ottima"
Potreste darmi una mano? Io sinceramente non ho proprio idea di come risolverlo.
"Esistono due tipi di mangimi per conigli, A e B. La combinazione di nutrienti in ogni sacco è la seguente:
Mangime A Proteine 1 Carboidrati 6 coloranti 1 grasso 4
Mangime B Proteine 2 Carboidrati 5 coloranti 3 grasso 3
Per una corretta dieta, i coniglie necessitano di almeno 7 proteine, 28 carboidrati, non più di 13 coloranti, non più di 24 grassi.
1-Essendo 8€ il prezzo di un sacco del mangime A e 3€ il prezzo di un sacco di mangime B, qual è la combinazione migliore per minimizzare il costo?
2-Posto p il prezzo di un sacco di A (sempre 3€ per B) determinare l'insieme di valori per cui la scelta effettuata al punto precedente è ottima"
Potreste darmi una mano? Io sinceramente non ho proprio idea di come risolverlo.
Risposte
Ciao,
è un classico, si chiama "problema della dieta" o "un problema di dieta".
Il problema non ci da un'unità di misura sui dati, perciò consideriamo che siamo in grammi per semplificare la comprensione. Ma possiamo anche non utilizzare nulla, non cambia
Sia $x_1$ e $x_2$ le quantità fattoriali in grammi da estrarre rispettivamente dal sacco $A$ e $B$.
Il sacco $A$ è così composto: $1g$ di proteine, $6g$ di carboidrati, $1g$ di coloranti (che bontà!!), $4g$ di grassi = $12g$
Il sacco $B$ è così composto: $2g$ di proteine, $5g$ di carboidrati, $3g$ di coloranti, $3g$ di grassi = $13g$
la dieta corrisponde in vincolare la quantità proporzionale di ogni sacco/grammi con la quantità tabellata, perciò:
$1x_1 + 2x_2 >= 7$ (almeno 7 grammi di proteine)
$6x_1 + 5x_2 >= 28$
$1x_1 + 3x_2 <= 13$ (non più di 13 coloranti)
$4x_1 + 3x_2 <= 24$
1.
ci chiede di trovare una funzione obiettivo che minimizza i costi. Noi consideriamo il costo a sacco secondo il suo "peso" cioè la somma delle quantità elencate:
es. sacco A = 8 euro
somma quantità interne sacco A = 12 (grammi)
cioè $(8\text{euro})/(12\text{grammi})$
perciò
funzione obiettivo: $\min_{x_1,x_2} : {\frac{8}{12}x_1 + \frac{3}{13}x_2}$
vincoli:
$1x_1 + 2x_2 >= 7$
$6x_1 + 5x_2 >= 28$
$1x_1 + 3x_2 <= 13$
$4x_1 + 3x_2 <= 24$
$x_1,x_2 >= 0$ (vincoli di non negatività, non hanno senso valori negativi)
2.
lo lascio a te.
1. 2. per rispondere ai quesiti, perchè devi dare un valore, semplicemente risolvi il programma matematico con la programmazione lineare. Visto che siamo con due vincoli, consiglio di utilizzare il simplesso grafico che è più veloce.
Se hai domande chiedi pure
è un classico, si chiama "problema della dieta" o "un problema di dieta".
Il problema non ci da un'unità di misura sui dati, perciò consideriamo che siamo in grammi per semplificare la comprensione. Ma possiamo anche non utilizzare nulla, non cambia
Sia $x_1$ e $x_2$ le quantità fattoriali in grammi da estrarre rispettivamente dal sacco $A$ e $B$.
Il sacco $A$ è così composto: $1g$ di proteine, $6g$ di carboidrati, $1g$ di coloranti (che bontà!!), $4g$ di grassi = $12g$
Il sacco $B$ è così composto: $2g$ di proteine, $5g$ di carboidrati, $3g$ di coloranti, $3g$ di grassi = $13g$
la dieta corrisponde in vincolare la quantità proporzionale di ogni sacco/grammi con la quantità tabellata, perciò:
$1x_1 + 2x_2 >= 7$ (almeno 7 grammi di proteine)
$6x_1 + 5x_2 >= 28$
$1x_1 + 3x_2 <= 13$ (non più di 13 coloranti)
$4x_1 + 3x_2 <= 24$
1.
ci chiede di trovare una funzione obiettivo che minimizza i costi. Noi consideriamo il costo a sacco secondo il suo "peso" cioè la somma delle quantità elencate:
es. sacco A = 8 euro
somma quantità interne sacco A = 12 (grammi)
cioè $(8\text{euro})/(12\text{grammi})$
perciò
funzione obiettivo: $\min_{x_1,x_2} : {\frac{8}{12}x_1 + \frac{3}{13}x_2}$
vincoli:
$1x_1 + 2x_2 >= 7$
$6x_1 + 5x_2 >= 28$
$1x_1 + 3x_2 <= 13$
$4x_1 + 3x_2 <= 24$
$x_1,x_2 >= 0$ (vincoli di non negatività, non hanno senso valori negativi)
2.
lo lascio a te.
1. 2. per rispondere ai quesiti, perchè devi dare un valore, semplicemente risolvi il programma matematico con la programmazione lineare. Visto che siamo con due vincoli, consiglio di utilizzare il simplesso grafico che è più veloce.
Se hai domande chiedi pure
Ciao ho risolto il sistema dei vincoli come un sistema di disequazioni in due incognite ed il risultato è questo
[img]http://www.mathway.com/graph_image.aspx?p=x+2y=7_6x+5y=28_x+3y=13_4x+3y=24?p=520?p=450?p=False?p=False?p=False?p=False?p=False?p=False?p=True?p=True?p=?p=?p=?p=?p=4[/img]
dove le l'insieme delle soluzioni è il quadrilatero compreso tra le 4 rette.
Ora, come faccio a trovare tra il poligono delle soluzioni, i valori per cui $\min_{x_1,x_2} : {\frac{8}{12}x_1 + \frac{3}{13}x_2}$ ?
È necessaria la conoscenza delle funzioni in più variabili, giusto?
ho risolto il sistema dei vincoli come un sistema di disequazioni in due incognite ed il risultato è questo[img]http://www.mathway.com/graph_image.aspx?p=x+2y=7_6x+5y=28_x+3y=13_4x+3y=24?p=520?p=450?p=False?p=False?p=False?p=False?p=False?p=False?p=True?p=True?p=?p=?p=?p=?p=4[/img]
dove le l'insieme delle soluzioni è il quadrilatero compreso tra le 4 rette.
Ora, come faccio a trovare tra il poligono delle soluzioni, i valori per cui $\min_{x_1,x_2} : {\frac{8}{12}x_1 + \frac{3}{13}x_2}$ ?
È necessaria la conoscenza delle funzioni in più variabili, giusto?
È necessaria la conoscenza delle funzioni in più variabili, giusto?
ma poche cose, se il '93 è riferito al tuo anno di nascita, dovresti aver visto le funzioni ad una variabile e le derivate.
L'unica definizione per risolvere il programma lineare con il metodo grafico è la definizione di gradiente e il concetto di "direzione di massima crescita".
Un sunto, riferito al gradiente utilizzato in questi problemi, lo puoi trovare cercando in questa sezione, è piuttosto semplice; tipo:
- risoluzione-problema-di-pl-con-metodo-simplesso-t78194.html
- risoluzione-grafica-problema-di-pl-t89881.html
Più difficile è comprendere cosa avviene realmente, cioè la parte teorica. Ma non penso ti sia richiesta.
Potresti utilizzare la versione algebrica che si riduce ad alcune regole meccaniche ma è più lungo e incriccato il discorso.
Se vuoi un esempio: basi-ammissibili-t91257.html (vedi pag. 2)
"Kenny93":
Ciao
[img]http://www.mathway.com/graph_image.aspx?p=x+2y=7_6x+5y=28_x+3y=13_4x+3y=24?p=520?p=450?p=False?p=False?p=False?p=False?p=False?p=False?p=True?p=True?p=?p=?p=?p=?p=4[/img]
dove le l'insieme delle soluzioni è il quadrilatero compreso tra le 4 rette
ottimo, hai compreso come funziona il primo passo
quel quadrilatero si chiama simplesso ed è un poliedro. Non sono rette, ma semi-piani (perchè siamo in $RR^3$, un poligono (rispettivamente rette) è in $RR^2$).
Ora, come faccio a trovare tra il poligono delle soluzioni, i valori per cui $\min_{x_1,x_2} : {\frac{8}{12}x_1 + \frac{3}{13}x_2}$ ?
devi intersecare il piano generato da questa funzione con il simplesso.
vedi un po' i link sopra sul metodo grafico e poi ne riparliamo, se avrai dubbi scrivi pure qui
NOTA:
il gradiente utilizzato nella programmazione lineare, quando si applica il metodo grafico, ha la proprietà di essere sempre costante in tutto lo spazio. Se ti crea dubbi questa definzione ad astrarla, forse ti è di aiuto questa risposta ad una mia domanda (che ho risolto poco tempo fa...): gradiente-costante-t86467.html
Okay, grazie, credo di aver capito
Solo una domanda, tu dici che il poligono è un simplesso, cioè un poliedro; ma che tipo di poliedro? Un prisma che ha come base quel quadrilatero? Lo chiedo per farmi un'idea dei grafici delle funzioni di due variabili (al cui studio mi sono appena avvicinato e quindi ho un po' di dubbi).
A breve posterò, quella che penso sia, la soluzione
Solo una domanda, tu dici che il poligono è un simplesso, cioè un poliedro; ma che tipo di poliedro? Un prisma che ha come base quel quadrilatero? Lo chiedo per farmi un'idea dei grafici delle funzioni di due variabili (al cui studio mi sono appena avvicinato e quindi ho un po' di dubbi).
A breve posterò, quella che penso sia, la soluzione
"Kenny93":
Okay, grazie, credo di aver capito
Solo una domanda, tu dici che il poligono è un simplesso, cioè un poliedro; ma che tipo di poliedro? Un prisma che ha come base quel quadrilatero? Lo chiedo per farmi un'idea dei grafici delle funzioni di due variabili (al cui studio mi sono appena avvicinato e quindi ho un po' di dubbi).
attentenzione, quelli non sono rette, ma sono PIANI (meglio semi-piani per via della disuguaglianza) che formano per intersezione un poliedro convesso. La quota è creta dalla funzione obiettivo (il "tappo").
Un prisma? sì mi pare che possa essere, ma direi che non si possa generalizzare a tutti i "prismi" ma solo a quelli definibili "convessi". Risottolineo: la base è sì il quadrilatero (mi pare, non ho guardato dove fossero orientate le disuguaglianze), ma è implicato dall'intersezione dei vincoli
Consigli:
- per un aiuto grafico vedi http://gim.altervista.org/ro/index.php
- oppure un plotter, mi aiutò parecchio all'inizio (es. Derive o wolfram-alpha ovviamente fino a 2-variabili)
(con 3 varibili già siamo a corsi avanzati con 4 si utilizzano tecniche algebriche ed una visione grafica è impensabile).
Okay, ho scaricato Derive e mi sono un po' chiarito le idee. Ma, poichè non avrò, al momento del test, accesso a programmi come Derive, è possibile risolvere questo tipo di problemi anche con metodo algebrico?
"Kenny93":
Okay, ho scaricato Derive e mi sono un po' chiarito le idee. Ma, poichè non avrò, al momento del test, accesso a programmi come Derive,
che c'entra questo?
L'utilizzo di un plotter era solo un aiuto astratto per farti capire dove stanno i piani intersecati per formare il simplesso.
Con due variabili non si disegna mica in 3D ma si utilizza il piano cartesiano in due varibili senza la quota.
L'unica cosa che si utilizza dell'analisi a più variabili, come detto, è il gradiente che ti da una direzione (freccia). tutto qui, è semplice ed immediato.
Non serve comprendere nulla di analisi (o pochissimo), se non è richiesto da altri esercizi di questo esame non ti consiglio di approfondire, ne avrai le "tasche" piene durante il cdl (anzi, per curiosità che cdl avresti intenzione di fare?).
Ma se hai dubbi poni pure domande, cercherò di esser più chiaro, oltre l'utilizo del metodo del simplesso.
è possibile risolvere questo tipo di problemi anche con metodo algebrico?
ti posso spiegare qualcosina ma diventa tedioso e di sicuro non ne avrai bisogno. Ma hai trovato esercizi dove si utilizzano più di 2 variabili di decisione in problemi di ottimizzazione?
Il metodo algebrico si intenderebbe un sistema da più equazioni con più incognite, in 2 varibili con 3 vincoli:
- tre equazioni
- due incognite
un sistema accettabile da risolvere al livello di quell'esame. Poi con >=4 diventa da suicidio a mano...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo