Programmazione lineare con i fogli di calcolo

Come manager di un'azienda, ti trovi sempre con risorse finite o limitate, e la direzione si aspetta che tu ne tragga il massimo. Dalla produttività del tempo all'utilizzo del capitale, dalla terra al lavoro, e dalla supply chain alla produzione: quasi tutto quello che fai punta a ottimizzare la produttività.

La maggior parte delle compagnie aeree ottimizza gli orari dei voli per ottenere i ricavi più alti al costo più basso. Questi orari includono molte situazioni e vincoli, come il numero di aerei in una determinata località, il carburante, l'equipaggio e il tipo di rotta (rotte popolari e redditizie). Queste situazioni e restrizioni sono note come vincoli del volo sulle rotte più popolari e redditizie. La programmazione lineare viene utilizzata per trovare la soluzione del problema con vincoli dato.

In questo tutorial imparerai la programmazione lineare e tratterai i seguenti argomenti:

• Introduzione alla programmazione lineare
• Concetti di base della LPP
  • Variabile decisionale
  • Vincoli
  • Funzione obiettivo
  • Soluzione ottimale
  • Soluzione ammissibile
  • Soluzione inammissibile
  • Regione ammissibile
  • Vincoli di non negatività
• Formulazione del problema LPP (con esempio)
• Metodo grafico per risolvere una LPP in un foglio di calcolo
• Casi d'uso della LPP
• Conclusione

Introduzione alla programmazione lineare

Matematicamente, la programmazione lineare ottimizza (minimizza o massimizza) l'obiettivo lineare di più variabili soggette a condizioni/vincoli dati che soddisfano un insieme di disequazioni lineari. La programmazione lineare può essere applicata nella pianificazione di attività economiche come il trasporto di beni e servizi, la produzione, l'ottimizzazione dei sistemi elettrici e i flussi di rete. I problemi di LP possono essere risolti con diverse tecniche come il metodo grafico, il simplesso e il metodo di Karmakar.

Concetti di base della LPP

Vediamo le terminologie di base della programmazione lineare:

• Le variabili decisionali sono le variabili che verranno usate come argomenti della funzione obiettivo. Queste variabili determinano l'output. Il decisore può controllare il valore della funzione obiettivo usando la variabile decisionale. Quando risolvi un problema di programmazione lineare, devi prima identificare le variabili decisionali.

• I vincoli sono un insieme di restrizioni o condizioni situazionali. Possono essere in forma di uguaglianze o disuguaglianze. I vincoli limitano il valore delle variabili decisionali.

• La funzione obiettivo è una funzione di profitto o di costo che si vuole massimizzare o minimizzare. È il principale obiettivo delle decisioni.

• La soluzione ottimale è una delle soluzioni ammissibili in cui la funzione obiettivo è massima o minima, per esempio, profitto massimo o costo minimo. È il miglior valore della funzione obiettivo.

• Una soluzione ammissibile è l'insieme dei possibili valori delle variabili decisionali che soddisfa tutti i vincoli. Un problema di LP è ammissibile se almeno una soluzione è ammissibile.

• La soluzione inammissibile è l'insieme dei possibili valori delle variabili decisionali che non soddisfano tutti i vincoli, cioè non esiste una soluzione ottimale. Un problema di LP è inammissibile se non esiste alcuna soluzione che soddisfi tutti i vincoli.

• La regione ammissibile è la regione coperta da tutti i possibili insiemi di valori che soddisfano i vincoli, ovvero l'intersezione di tutti i vincoli. Include disuguaglianze, uguaglianze e vincoli di integrità.

• I vincoli di non negatività per le variabili decisionali ammettono solo valori non negativi. Tali vincoli sono maggiori o uguali a zero.

Formulazione del problema LPP (con esempio)

La formulazione di modelli di programmazione lineare prevede i seguenti passaggi:

• Identificare le variabili decisionali
• Determinare la funzione obiettivo
• Identificare i vincoli
• Definire i vincoli di non negatività

In un problema di programmazione lineare, variabili decisionali, funzione obiettivo e vincoli devono essere tutti funzioni lineari

Descrizione del problema: Un rivenditore di mobili tratta solo due articoli: tavoli e sedie. Ha 50.000 Rs da investire e uno spazio di magazzino per al massimo 60 pezzi. Un tavolo costa 2.500 Rs e una sedia 500 Rs. Stima che dalla vendita di un tavolo possa ricavare un profitto di 250 Rs e dalla vendita di una sedia un profitto di 75 Rs. Vuole sapere quanti tavoli e quante sedie dovrebbe acquistare con il denaro disponibile per massimizzare il profitto totale, supponendo di poter vendere tutti gli articoli acquistati. (Fonte)

In questo esempio, osservi che –

1. Il rivenditore può investire il suo denaro acquistando tavoli o sedie o una combinazione di entrambi. Inoltre, otterrà profitti diversi seguendo diverse strategie di investimento. (Fonte)
2. Il suo investimento è limitato a un massimo di 50.000 Rs, così come lo spazio di magazzino, che consente al massimo 60 pezzi. (Fonte)

Formulazione matematica:

Supponiamo che decida di acquistare solo tavoli e nessuna sedia. Può quindi comprare 50000/2500 = 20 tavoli. In questo caso, otterrà un profitto di 250 x 20 = 5.000 Rs. Oppure decide di acquistare solo sedie e nessun tavolo. Può quindi comprare 50000/500 = 100 sedie.

In questo caso, otterrà un profitto di 75 x 60 = 4.500 Rs.

Potrebbero esserci molte combinazioni di tavoli e sedie che potrebbe acquistare.

Supponiamo che acquisti X tavoli e Y sedie. Quindi X e Y devono essere non negativi.

1. Il rivenditore ha un importo massimo di 50.000 Rs per acquistare tavoli e sedie, quindi –

   2500 X + 500 Y <= 50000 (vincolo di investimento) oppure 5 * X + Y <= 100 ………………………………………………………. Eq.1

1. Il numero massimo di unità che può immagazzinare è 60.

   X + Y <= 60 ………………………………………………………. Eq.2

1. Il rivenditore vuole acquistare quantità tali da massimizzare il suo profitto Z, quindi l'equazione sarà –

   Max Z : 250 X + 75 Y

Funzione obiettivo: Max Z: 250 X + 75 Y

Soggetta ai vincoli:

5 * X + Y <= 100,
X + Y <= 60 and
X,Y >= 0

Fonte: http://ncert.nic.in/ncerts/l/lemh206.pdf

Metodo grafico per risolvere una LPP in un foglio di calcolo

Esempio di programmazione lineare

Funzione obiettivo: Max Z: 250 X + 75 Y

Soggetta ai vincoli:

5 * X + Y <= 100,

X + Y <= 60 and

Where X,Y >= 0

Passo 1: Scriviamo la funzione in Excel come mostrato sotto.

Passo 2: Dopo aver scritto funzione obiettivo e vincoli nel foglio di calcolo, calcoliamo i valori per i vincoli C1 e C2. Puoi calcolare i valori ponendo a zero l'altro valore della variabile. Ad esempio per C1, a X = 0, il valore di Y sarà Y = 100 e a Y = 0, il valore di X sarà X = 20. Analogamente per i vincoli C2.

Passo 3: Ora, dopo aver calcolato i valori, tracciamo il grafico. Seleziona i valori del vincolo C1, vai su Inserisci e traccia un grafico a dispersione con linee smussate. Potresti vedere un grafico come questo.

Se appare così, non preoccuparti, segui i passaggi sotto per modificarlo. Fai clic con il tasto destro sul grafico, vai su Seleziona dati, vedrai due serie: rimuovi Serie 2 e modifica Serie 1.

Assegna alla serie il nome C1 e cambia il suo valore X con i valori della colonna A di C1 e il valore Y con i valori della colonna B di C1. Poi fai clic su OK. Vedrai il grafico come quello qui sotto:

Passo 4: Di nuovo, vai su Seleziona dati facendo clic con il tasto destro sul grafico e aggiungi un'altra serie. Chiamala C2 e nei valori X seleziona i valori della colonna X del vincolo C2 e nei valori Y seleziona i valori della colonna Y del vincolo C2. Il grafico apparirà come quello qui sotto:

Passo 5: Ora il grafico è tracciato e devi individuare la regione ammissibile:

Ora hai 4 punti (O, A, B, C) nell'area della regione ammissibile; devi calcolare i valori della funzione obiettivo in tutti i punti per vedere quale punto ti dà il valore massimo dell'obiettivo.

Passo 6: Per calcolare i valori della funzione obiettivo, segui i passaggi sotto:

Calcola la funzione obiettivo per ciascun punto:

• Nel punto O le coordinate di (X, Y) sono (0, 0). Quindi il valore della funzione obiettivo sarà = (2500+750) = 0
• Nel punto A le coordinate di (X, Y) sono (0, 60). Quindi il valore della funzione obiettivo sarà = (2500+753) = 4500
• Nel punto B le coordinate di (X, Y) sono (20, 0). Quindi il valore della funzione obiettivo sarà = (2503+750) = 5000

• Nel punto C Per trovare le coordinate nel punto Z, devi individuare il punto di intersezione delle rette di vincolo C1 e C2. Userai le funzioni MMULT() e MINVERSE() per calcolare l'intersezione di due equazioni.

• MMULT(MINVERSE(array),array) # Questo restituisce i valori della soluzione di sistemi con due variabili. Oppure, =MMULT(MINVERSE(AB17:AC18), AE17:AE18). Prima di usare questa formula, seleziona le celle dei valori X e Y evidenziate in giallo e usa questa funzione per calcolare il punto di intersezione di due equazioni quindi premi CTRL+SHIFT+INVIO

I valori finali di Z:

Come puoi vedere, in questo problema di massimizzazione lineare hai ottenuto il valore massimo di Z nel punto B, e il valore massimo è 6.250 Rs. Quindi, per massimizzare il profitto, il rivenditore deve acquistare 10 tavoli e 50 sedie.

Casi d'uso della LPP

La programmazione lineare viene applicata per trovare soluzioni ottimali nella ricerca operativa. L'LP può trovare la soluzione più ottimale entro vincoli e restrizioni dati. L'LP è applicabile a ogni tipo di problema, come attività economiche in agricoltura, ingegneria, manifattura, energia, logistica e supply chain.

• Gli ingegneri applicano la programmazione lineare nel settore manifatturiero e produttivo per ottimizzare le risorse disponibili, così da ottenere il massimo profitto.

• Il settore della logistica e dei trasporti usa la programmazione lineare per trovare il percorso/tragitto più breve, i tempi di viaggio e le strategie di prezzo.

• Gli ingegneri applicano la programmazione lineare nel settore energetico. Ottimizzano il carico elettrico, le linee di distribuzione più brevi e progettano in modo ottimale la rete elettrica.

• Nel settore agricolo, la programmazione lineare può essere usata dagli ingegneri per determinare il tipo e la quantità di colture da piantare per aumentare efficientemente i ricavi.

• Nel settore alimentare, la programmazione lineare può aiutare i responsabili della salute e i nutrizionisti a pianificare le esigenze dietetiche e un insieme di alimenti a basso costo per prevenire le malattie non trasmissibili.

Conclusione

Congratulazioni, sei arrivato alla fine di questo tutorial!

Hai coperto molti dettagli sulla programmazione lineare. Hai imparato cos'è la programmazione lineare, i concetti e le terminologie di base usate nell'LP, la formulazione di problemi di LP, la risoluzione con il metodo grafico e i casi d'uso dei problemi di LP.

Ora, si spera, puoi utilizzare i concetti di programmazione lineare per prendere decisioni nella tua organizzazione o ottimizzare i risultati per i decisori. Grazie per aver letto questo tutorial!

Dai un'occhiata al nostro tutorial Grafici nei fogli di calcolo.

Se vuoi approfondire i fogli di calcolo, segui questi corsi DataCamp: