Introduzione alla programmazione matematica

Riassunto

La programmazione matematica comprende strumenti di analisi in più variabili, problemi di ottimizzazione e programmazione lineare. Gli obiettivi comprendono riconoscere vincoli e funzione da ottimizzare, studiare la regione ammissibile e scegliere metodi adeguati; per i problemi lineari si studierà il metodo del simplesso. Si mostra come tradurre una descrizione verbale in variabili, disuguaglianze e funzione da ottimizzare, poi risolvere graficamente un problema con due variabili. Nell'esempio del falegname, la produzione ottima è di 10 tavoli e 45 sedie, con un guadagno di 2100 euro. Nell'esempio dei succhi, la soluzione è di 40 cartoni di succo di mela e 5 di succo d'arancia, con un profitto di 140 euro.

Concetti chiave

• Problema decisionale — problema in cui occorre scegliere una decisione nella maniera migliore possibile.
• Variabili decisionali — quantità non note da determinare per descrivere le possibili decisioni; indicano quantità prodotte.
• Vincoli — limitazioni sulle decisioni, espresse mediante disuguaglianze che devono essere soddisfatte contemporaneamente.
• Regione ammissibile — insieme dei punti che soddisfano tutti i vincoli e rappresentano produzioni realizzabili.
• Formulazione matematica — rappresentazione di un problema decisionale tramite variabili, vincoli e una funzione da massimizzare o minimizzare.
• Funzione di profitto — funzione che esprime il guadagno associato a una produzione e che si vuole massimizzare.
• Retta di profitto costante — retta i cui punti rappresentano produzioni con lo stesso profitto; si ottiene fissando a una costante il valore della funzione di profitto.

Sviluppo

Struttura e programma del corso

Il corso ha una prima parte di circa 30 ore dedicata a strumenti di analisi matematica per funzioni di più variabili e per lo spazio $\mathbb{R}^n$: proprietà degli insiemi, insiemi aperti e chiusi, limiti, funzioni, continuità e successioni.

Il programma prosegue con un'introduzione ai problemi di ottimizzazione, problemi convessi e concavi, programmazione lineare e ottimizzazione non lineare. Per i problemi lineari si presenta il metodo del simplesso, con esercizi ed esempi; per l'ottimizzazione non lineare si vedono alcuni metodi. La formulazione matematica dei problemi decisionali affronterà in parallelo il resto del corso, fin dalle prime lezioni.

Obiettivi formativi

Occorre saper maneggiare funzioni di più variabili, determinarne il dominio e riconoscere alcune proprietà del dominio, per esempio se è aperto o chiuso. Lo studio completo e il disegno dei grafici sono più complicati rispetto alle funzioni di una variabile: per una funzione di due variabili, il grafico è una superficie.

Una parte centrale consiste nel formulare matematicamente problemi decisionali. Dopo averli formulati, bisogna saper riconoscere se sono lineari o non lineari, convessi o non convessi, e stabilire quali metodi siano adatti. In generale, per problemi non banali la soluzione non si esprime con una formula chiusa, ma si calcola iterativamente. Per i problemi lineari si svolgono alcuni passaggi del metodo del simplesso. È inoltre importante interpretare la soluzione: nella pratica, l'interpretazione può suggerire modifiche al modello per renderlo più aderente alla realtà.

Dal problema verbale alle variabili

Dopo un'introduzione teorica, si trasforma una descrizione verbale in un sistema di disuguaglianze e in una funzione di costo o di profitto da minimizzare o massimizzare. Si rappresenta poi graficamente la situazione e se ne cerca la soluzione. I dati numerici degli esempi sono inventati per l'esercizio.

Il problema del falegname

Un falegname produce tavoli e sedie. Ogni tavolo richiede 3 ore di lavoro e 1 kg di legno; ogni sedia richiede 2 ore e 2 kg di legno. Sono disponibili al massimo 120 ore di lavoro e 100 kg di legno. Ogni tavolo venduto dà un guadagno di 30 euro e ogni sedia di 40 euro.

Vincoli e regione ammissibile

Si indicano con $x$ il numero di tavoli e con $y$ il numero di sedie da produrre. Per $x$ tavoli servono $3x$ ore; per $y$ sedie, $2y$ ore. La somma non può superare le ore disponibili. Analogamente, il legno richiesto è $x+2y$ kg e non può superare la disponibilità.

Ogni produzione corrisponde a un punto $(x,y)$ nel piano cartesiano. Le quantità non possono essere negative. I punti che rispettano insieme i vincoli di lavoro, legno e non negatività formano la regione delle produzioni realizzabili; produrre zero tavoli e zero sedie è possibile, anche se non genera guadagno.

Rappresentazione grafica dei vincoli

La retta $3x+2y=120$ rappresenta le produzioni che usano tutte le ore disponibili; il semipiano corrispondente a $3x+2y\leq120$ comprende quelle che ne usano al massimo 120. Una parte del semipiano contiene valori negativi di $x$ o $y$, che non rappresentano produzioni possibili. Il vincolo sul legno aggiunge il semipiano $x+2y\leq100$. Intersecando entrambi i semipiani con il primo quadrante si ottiene il poligono delle produzioni ammissibili.

Profitto e soluzione grafica del falegname

Per una produzione $(x,y)$ il guadagno è $30x+40y$. Si cerca, tra i punti ammissibili, quello che rende massima questa funzione. Nel piano, l'equazione $30x+40y=k$ rappresenta le produzioni con lo stesso guadagno. Aumentando $k$, le rette si spostano; l'ultima che incontra la regione ammissibile passa per un vertice, all'intersezione dei due vincoli sulle risorse.

Risolvendo il sistema dei due vincoli come uguaglianze si ottiene $x=10$ e $y=45$. La produzione di 10 tavoli e 45 sedie dà un guadagno di 2100 euro. Aumentando ulteriormente il profitto richiesto, la retta non incontra più la regione ammissibile; perciò questa produzione è ottima.

Procedura di formulazione e soluzione

Il percorso proposto è: leggere con attenzione la situazione operativa, individuare le quantità da decidere e chiamarle variabili, ricavare i vincoli, scrivere la funzione di guadagno e specificare che cosa si vuole massimizzare. Con due variabili si può disegnare la regione ammissibile e usare le rette di profitto costante per individuare graficamente la soluzione.

Esempio della produzione di succhi

Un secondo problema riguarda la produzione di cartoni di succo di mela e di succo d'arancia. Anche questo è un esempio semplificato: nella realtà entrerebbero in gioco altri elementi, come l'acqua. Si indicano con $x$ i cartoni di succo di mela e con $y$ quelli di succo d'arancia. Ogni cartone di mela richiede 2 kg di mele e 1 kg di zucchero; ogni cartone d'arancia richiede 3 kg di arance e 2 kg di zucchero. Le disponibilità sono 80 kg di mele, 60 kg di arance e 50 kg di zucchero. Ogni cartone di mela dà un profitto di 3 euro e ogni cartone d'arancia di 4 euro.

Vincoli e regione ammissibile dei succhi

La disponibilità di mele impone $2x\leq80$, quindi $x\leq40$. Quella di arance impone $3y\leq60$, quindi $y\leq20$. Lo zucchero impone $x+2y\leq50$. Inoltre $x$ e $y$ devono essere non negativi. Nel piano, i limiti $0\leq x\leq40$ e $0\leq y\leq20$ definiscono un rettangolo; il vincolo sullo zucchero lo restringe a un poligono. I punti di tale poligono rappresentano le produzioni realizzabili.

Profitto e soluzione grafica dei succhi

La funzione di profitto è $3x+4y$ e si vuole massimizzarla nella regione ammissibile. Il punto ottimo è $(40,5)$, intersezione di $x=40$ con $x+2y=50$: corrisponde a 40 cartoni di succo di mela e 5 di succo d'arancia. Il profitto è $3\cdot40+4\cdot5=140$ euro; spostando la retta di profitto a un valore maggiore, non si hanno più punti in comune con la regione ammissibile.

Formule e dimostrazioni

Modello del falegname

Variabili: x è il numero di tavoli; y è il numero di sedie.

Vincolo sulle ore di lavoro:

$$3x+2y\leq120$$

I coefficienti 3 e 2 sono le ore richieste rispettivamente da un tavolo e da una sedia; 120 è il totale di ore disponibile.

Vincolo sul legno:

$$x+2y\leq100$$

I coefficienti 1 e 2 sono i chilogrammi di legno richiesti rispettivamente da un tavolo e da una sedia; 100 è la disponibilità in chilogrammi.

Non negatività:

$$x\geq0,\qquad y\geq0$$

Funzione di profitto e obiettivo:

$$\max\; 30x+40y$$

Ogni tavolo contribuisce 30 euro e ogni sedia 40 euro.

Per individuare il vertice ottimo si intersecano le rette dei due vincoli attivi:

$$\begin{cases} 3x+2y=120\\ x+2y=100 \end{cases} \quad\Longrightarrow\quad 2x=20,\quad x=10,\quad y=45.$$

Il profitto corrispondente è:

$$30\cdot10+40\cdot45=2100.$$

Le rette a profitto costante hanno equazione 30x+40y=k, dove k è il profitto fissato.

Modello della produzione di succhi

Variabili: x è il numero di cartoni di succo di mela; y è il numero di cartoni di succo d'arancia.

Vincolo sulle mele:

$$2x\leq80$$

Ogni cartone di succo di mela richiede 2 kg di mele e la disponibilità è 80 kg.

Vincolo sulle arance:

$$3y\leq60$$

Ogni cartone di succo d'arancia richiede 3 kg di arance e la disponibilità è 60 kg.

Vincolo sullo zucchero:

$$x+2y\leq50$$

Ogni cartone di succo di mela richiede 1 kg di zucchero, ogni cartone d'arancia 2 kg; la disponibilità è 50 kg.

Non negatività e limiti equivalenti sulle prime due risorse:

$$0\leq x\leq40,\qquad 0\leq y\leq20$$

Funzione di profitto e obiettivo:

$$\max\; 3x+4y$$

I profitti unitari sono rispettivamente 3 e 4 euro per cartone. Nel punto individuato $(x,y)=(40,5)$ il profitto è:

$$3\cdot40+4\cdot5=140.$$