Problemi, soluzioni e applicazioni di programmazione lineare [con esempio]

La scienza dei dati ha molte applicazioni, una delle più importanti è l'ottimizzazione. Tutti tendiamo a concentrarci sull'ottimizzazione delle cose. L'ottimizzazione si concentra sull'ottenere i risultati più desiderati con le risorse limitate di cui disponi.

Sono disponibili tutti i tipi di problemi di ottimizzazione, alcuni sono piccoli, altri molto complicati. Mentre li esamini, troverai una categoria specifica chiamata problemi di programmazione lineare. In questo articolo, abbiamo discusso di cosa sono e come puoi lavorarci su.

Supponiamo che tu sia un fruttivendolo che può acquistare arance o mele o una certa combinazione di entrambe. Tuttavia hai solo un budget di INR 5.000 e puoi conservarne solo 30 sacchi. Ora, devi acquistarli nel modo che ti dà il massimo profitto.

Ora un sacchetto di arance ti costa INR 500 mentre un sacchetto di mele ti costa INR 750. Puoi guadagnare INR 100 dalla vendita di un sacchetto di arance e INR 200 dalla vendita di un sacchetto di mele.

Questo problema ha diverse possibilità. Potresti scegliere di acquistare solo arance, ma avresti solo 10 sacchi nel tuo magazzino e il tuo profitto sarebbe di 1000 INR. Allo stesso modo, potresti scegliere di acquistare solo mele e guadagnare 1500 INR. Puoi anche acquistare una combinazione dei due.

Tali problemi sono chiamati problemi di programmazione lineare e li discuteremo in dettaglio. Iniziamo:

Cos'è la programmazione lineare?

La programmazione lineare è un metodo per rappresentare relazioni complesse utilizzando funzioni lineari. Il nostro obiettivo con la programmazione lineare è trovare le soluzioni più adatte a tali funzioni. La vera relazione tra due punti può essere molto complessa, ma possiamo usare la programmazione lineare per rappresentarli con semplicità. La programmazione lineare trova applicazioni in molti settori.

Nozioni di base sulla programmazione lineare

Ecco alcuni termini fondamentali della programmazione lineare:

vincolo

Le limitazioni (o restrizioni) delle variabili decisionali sono chiamate vincoli. La maggior parte dei vincoli di tempo sono i limiti che hai sulle tue risorse per risolvere un problema.

Variabile di decisione

Queste variabili definiscono l'output. Il tuo risultato dipende da queste variabili, ecco perché le chiamiamo "variabili decisionali".

Restrizione di non negatività

Le variabili decisionali di un problema di programmazione lineare possono avere solo un valore non negativo. Significa che i valori per le tue variabili decisionali possono essere uguali o maggiori di zero solo.

Funzione obiettivo

La funzione obiettivo è l'obiettivo di prendere una decisione. In parole povere è il risultato finale del tuo problema di programmazione lineare. Ad esempio, quando trovi il massimo profitto che puoi realizzare con un determinato insieme di risorse, il massimo profitto è la funzione obiettivo.

Formulare problemi di programmazione lineare

Dovresti sapere come formulare una programmazione lineare per applicarla nella vita reale. Supponiamo che tu sia un produttore di giocattoli e produci solo due giocattoli: A e B. In parole povere, i tuoi giocattoli richiedono due risorse X e Y per essere fabbricati. Ecco i requisiti dei tuoi giocattoli:

• Un'unità di giocattolo A richiede un'unità di risorsa X e tre unità di risorsa Y

• Un'unità di giocattolo B richiede un'unità di risorsa X e due unità di risorsa Y

Hai cinque unità di risorsa X e 12 unità di risorsa Y. I tuoi margini di profitto sulla vendita di questi giocattoli sono:

• INR 6 su ciascuna unità venduta del giocattolo A
• INR 5 su ogni unità venduta del giocattolo B

Quante unità di ogni giocattolo produrresti per ottenere il massimo profitto?

La soluzione

Rappresentiamo il nostro problema di programmazione lineare in un'equazione:

Z = 6a + 5b

Qui, z sta per il profitto totale, a sta per il numero totale di unità giocattolo A e b sta per il numero totale di unità B. Il nostro obiettivo è massimizzare il valore di Z (il profitto).

Ora, la tua azienda vorrebbe produrre quante più unità possibili di questi giocattoli, ma hai risorse limitate. I limiti alle nostre risorse sono i vincoli di questo problema. Abbiamo solo un totale di

a + b 5

Ora ogni unità di giocattolo A e B richiede rispettivamente 3 e 2 unità di risorsa Y. E abbiamo solo un totale di 12 unità di risorsa Y, quindi matematicamente sarebbe simile a questo:

3a + 2b 12

Ricorda che i valori per le unità del giocattolo A possono essere solo in numeri interi. Ciò significa che abbiamo anche i vincoli di a->0 e b<-0.

Quindi, ora hai un vero problema di programmazione lineare. È possibile formulare altri problemi di programmazione lineare seguendo questo esempio. Sebbene questo esempio sia abbastanza semplice, i problemi di LP possono diventare molto complicati.

Leggi: Idee e argomenti per progetti di programmazione lineare

Passaggi per la formulazione di problemi di programmazione lineare

Per formulare un problema di programmazione lineare, attenersi alla seguente procedura:

• Trova le variabili decisionali
• Trova la funzione obiettivo
• Identificare i vincoli
• Ricorda la restrizione di non negatività

Se un problema soddisfa i criteri di cui sopra, è un problema di programmazione lineare. È buona norma tenere presente questo criterio quando si lavora per identificare il tipo di problema.

Risolvere problemi di programmazione lineare con R

Se stai usando R, risolvere i problemi di programmazione lineare diventa molto più semplice. Questo perché R ha il pacchetto lpsolve che viene fornito con varie funzioni progettate specificamente per risolvere tali problemi. È molto probabile che utilizzerai R molto frequentemente per risolvere problemi di LP come scienziato dei dati. Ecco perché abbiamo condiviso due esempi distinti per aiutarti a comprenderne meglio l'implementazione:

Esempio

Cominciamo con un problema di base. Un'organizzazione ha due prodotti con prezzi di vendita di INR 25 e INR 20 e sono chiamati rispettivamente prodotto A e B. Ogni giorno hanno 1800 unità di risorse per produrre questi prodotti. Il prodotto A richiede 20 unità di risorse e B richiede 12 unità di risorse. Il tempo di produzione per entrambi questi prodotti è di quattro minuti e l'organizzazione ottiene un totale di otto ore lavorative ogni giorno. Il problema è, quale dovrebbe essere la quantità di produzione per ciascuno di questi prodotti per massimizzare i profitti dell'azienda?

Soluzione:

Inizieremo a risolvere questo problema definendo la sua funzione obiettivo:

max(Vendite) = max( 25 y 1 + 20 y 2 )

Qui, 25 e 20 sono rispettivamente i prezzi del prodotto A e B, y1 è l'unità totale del prodotto A prodotto e y2 è l'unità totale del prodotto B prodotto. Le nostre variabili decisionali sono y1 e y2.

Ora imposteremo i vincoli per il nostro problema:

Vincolo delle risorse:

20 anni 1 + 12 anni 2 1800

Vincolo di tempo:

4 anni 1 + 4 anni 2 8*60

Miriamo a trovare il numero corretto di prodotti che dobbiamo produrre per ottenere il massimo profitto.

Usare R per risolvere il problema:

Useremo lpsolve per risolvere questo problema di LP e inizieremo con l'impostazione della funzione obiettivo:

> richiedi (lpRisolvi)

Caricamento del pacchetto richiesto: lpSolve

> obiettivo.in <- c(25, 20)

> obiettivo.in

[1] 25 20

Quindi costruiremo una matrice per i vincoli:

> const <- matrice(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> cost

[,1] [,2]

[1,] 20 12

[2,] 4 4

> vincoli_di_tempo <- (8*60)

> vincoli_risorse <- 1800

> vincoli_di_tempo

[1] 480

> vincoli_risorse

[1] 1800

Creiamo ora le equazioni già definite:

> rhs <- c(vincoli_risorsa, vincoli_tempo)

> dx

[1] 1800 480

> direzione <- c(“<=”, “<=”)

> direzione

[1] “<=” “<=”

Una volta aggiunte tutte le informazioni necessarie, possiamo iniziare a trovare la risposta ottimale. La sintassi del nostro pacchetto è:

lp( direzione, obiettivo, const.mat, const.dir, const.rhs )

> ottimo <- lp(direction=”max”, obiettivo.in, const, direction, rhs)

> ottimale

Successo: la funzione obiettivo è 2625

> riassunto (ottimo)

Modalità classe di lunghezza

direzione 1 -nessuno- numerico

x.count 1 -none- numerico

obiettivo 2 -nessuno- numerico

const.count 1 -none- numerico

vincoli 8 -nessuno- numerico

int.count 1 -none- numerico

int.vec 1 -none- numerico

bin.count 1 -none- numerico

binary.vec 1 -none- numerico

num.bin.solns 1 -none- numerico

objval 1 -none- numerico

soluzione 2 -nessuna- numerica

presolve 1 -none- numerico

compute.sens 1 -none- numerico

sens.coef.da 1 -none- numerico

sens.coef.to 1 -none- numerico

duals 1 -none- numerico

duals.from 1 -none- numerico

duals.to 1 -none- numerico

scala 1 -nessuna- numerica

use.dense 1 -none- numerico

dense.col 1 -none- numerico

dense.val 1 -none- numerico

dense.const.nrow 1 -none- numerico

dense.ctr 1 -none- numerico

use.rw 1 -none- numerico

tmp 1 -none- carattere

stato 1 -nessuno- numerico

Dopo aver eseguito il codice sopra, puoi ottenere le soluzioni desiderate per il nostro problema.

I valori ottimali per y1 e y2:

Ricordiamo che y1 e y2 erano le unità del prodotto A e del prodotto B che dovevamo produrre:

> soluzione$ ottimale

[1] 45 75

La cifra di vendita ottimale:

Il massimo profitto che possiamo generare con i valori ottenuti di y1 e y2 è:

> valore$ottimo

[1] 2625

Leggi anche: Algebra lineare per l'apprendimento automatico

Usi della programmazione lineare

Come accennato in precedenza, la programmazione lineare trova applicazioni in molti settori. Ecco alcune aree in cui lo utilizziamo:

• Con la crescente popolarità dei servizi di consegna, la programmazione lineare è diventata uno dei metodi preferiti per trovare i percorsi ottimali. Quando prendi un Ola o un Uber, il software utilizzerà la programmazione lineare per trovare il percorso migliore. Anche società di consegna come Amazon e FedEx lo utilizzano per determinare i percorsi migliori per i loro addetti alle consegne. Si concentrano sulla riduzione dei tempi e dei costi di consegna.
• L'apprendimento supervisionato del machine learning lavora sui concetti fondamentali della programmazione lineare. Nell'apprendimento supervisionato, devi trovare il modello matematico ottimale per prevedere l'output in base ai dati di input forniti.
• Il settore della vendita al dettaglio utilizza la programmazione lineare per ottimizzare lo spazio sugli scaffali. Con così tanti marchi e prodotti disponibili, determinare dove collocarli nel negozio è un compito molto rigoroso. Il posizionamento di un prodotto nel negozio può influire notevolmente sulle sue vendite. Le principali catene di vendita al dettaglio come Big Bazaar, Reliance, Walmart, ecc. utilizzano la programmazione lineare per determinare il posizionamento dei prodotti. Devono tenere a mente l'interesse dei consumatori garantendo al contempo il miglior posizionamento del prodotto per ottenere il massimo profitto.
• Le aziende utilizzano la programmazione lineare per migliorare le loro catene di approvvigionamento. L'efficienza di una catena di approvvigionamento dipende da molti fattori come i percorsi scelti, i tempi, ecc. Utilizzando la programmazione lineare, possono trovare i percorsi, i tempi e altre allocazioni di risorse migliori per ottimizzare la propria efficienza.

Ulteriori informazioni sulla programmazione lineare e sulla scienza dei dati

La programmazione lineare è uno dei concetti più vitali della scienza dei dati. È anche un argomento fondamentale che dovresti conoscere per diventare un esperto di data scientist. Come abbiamo discusso, ci sono molte applicazioni per questo concetto e puoi trovare i suoi casi d'uso nella tua vita quotidiana.

Puoi saperne di più sulla scienza dei dati e sui concetti correlati visitando il nostro blog. Abbiamo molte risorse preziose per aiutarti a saperne di più. Eccone alcuni per ulteriori letture:

• I principali motivi per diventare un Data Scientist
• Gli algoritmi che ogni scienziato di dati dovrebbe conoscere
• Come diventare un Data Scientist

D'altra parte, puoi ottenere un corso di scienza dei dati per imparare da esperti del settore. Imparerai in modo interattivo attraverso video, quiz e progetti. Seguire un corso ti aiuterà ad apprendere le competenze necessarie per diventare un data scientist professionista. Dai un'occhiata al Diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1 contro 1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.