Probleme, soluții și aplicații de programare liniară [cu exemplu]

Știința datelor are multe aplicații, una dintre cele mai proeminente dintre ele este optimizarea. Cu toții avem tendința de a ne concentra pe optimizarea lucrurilor. Optimizarea se concentrează pe obținerea celor mai dorite rezultate cu resursele limitate de care dispuneți.

Există tot felul de probleme de optimizare disponibile, unele sunt mici, altele sunt foarte complicate. În timp ce le parcurgeți, veți găsi o categorie specifică numită probleme de programare liniară. În acest articol, am discutat despre ce sunt acestea și cum puteți lucra la ele.

Să presupunem că sunteți un vânzător de fructe care poate cumpăra fie portocale, fie mere, fie o anumită combinație a acestora. Cu toate acestea, aveți doar un buget de 5.000 INR și puteți depozita doar 30 de saci din ele. Acum, trebuie să le cumpărați în modul care vă aduce cel mai mare profit.

Acum o pungă de portocale vă costă 500 INR, în timp ce o pungă de mere vă costă 750 INR. Puteți câștiga 100 INR din vânzarea unei pungi de portocale și 200 INR din vânzarea unei pungi de mere.

Această problemă are diverse posibilități. Ați putea alege să cumpărați doar portocale, dar atunci ați avea doar 10 pungi în depozit, iar profitul dvs. ar fi de 1000 INR. În mod similar, ați putea alege să cumpărați doar mere și să obțineți 1500 INR ca profit. De asemenea, puteți cumpăra o combinație a celor două.

Astfel de probleme se numesc probleme de programare liniară și le vom discuta în detaliu. Să începem:

Ce este programarea liniară?

Programarea liniară este o metodă de reprezentare a relațiilor complexe prin utilizarea funcțiilor liniare. Scopul nostru cu programarea liniară este să găsim cele mai potrivite soluții pentru acele funcții. Relația reală dintre două puncte poate fi foarte complexă, dar putem folosi programarea liniară pentru a le reprezenta cu simplitate. Programarea liniară își găsește aplicații în multe industrii.

Bazele programării liniare

Iată câțiva termeni fundamentali ai programării liniare:

Constrângere

Limitările (sau restricțiile) variabilelor dumneavoastră de decizie se numesc constrângeri. De cele mai multe ori constrângerile de timp sunt limitările pe care le aveți asupra resurselor dumneavoastră pentru rezolvarea unei probleme.

Variabila de decizie

Aceste variabile definesc rezultatul. Rezultatul dvs. depinde de aceste variabile, de aceea le numim „variabile de decizie”.

Restricție de non-negativitate

Variabilele de decizie ale unei probleme de programare liniară pot avea doar valoare nenegativă. Înseamnă că valorile pentru variabilele de decizie pot fi doar egale sau mai mari decât zero.

Funcție obiectivă

Funcția obiectivă este obiectivul luării deciziei dvs. În termeni simpli, este rezultatul final al problemei dumneavoastră de programare liniară. De exemplu, când găsiți profitul maxim pe care îl puteți obține cu un anumit set de resurse, profitul maxim este funcția obiectiv.

Formularea problemelor de programare liniară

Ar trebui să știi cum să formulezi o programare liniară pentru a o aplica în viața reală. Să presupunem că sunteți producător de jucării și produceți doar două jucării: A și B. În linii mari, jucăriile dvs. necesită două resurse X și Y pentru a le fabrica. Iată cerințele jucăriilor tale:

• O unitate de jucărie A necesită o unitate de resursă X și trei unități de resursă Y

• O unitate de jucărie B necesită o unitate de resursă X și două unități de resursă Y

Aveți cinci unități de resursă X și 12 unități de resursă Y. Marjele dvs. de profit din vânzarea acestor jucării sunt:

• 6 INR pentru fiecare unitate vândută de jucărie A
• 5 INR pentru fiecare unitate vândută de jucărie B

Câte unități din fiecare jucărie ați produce pentru a obține profitul maxim?

Soluția

Să reprezentăm problema noastră de programare liniară într-o ecuație:

Z = 6a + 5b

Aici, z reprezintă profitul total, a reprezintă numărul total de unități de jucărie A și b reprezintă numărul total de unități B. Scopul nostru este de a maximiza valoarea lui Z (profitul).

Acum, compania dumneavoastră ar dori să producă cât mai multe unități din aceste jucării, dar aveți resurse limitate. Limitările resurselor noastre sunt constrângerile acestei probleme. Avem doar un total de

a + b 5

Acum fiecare unitate de jucărie A și B necesită 3 și, respectiv, 2 unități de resursă Y. Și avem doar un total de 12 unități de resursă Y, așa că din punct de vedere matematic, ar arăta astfel:

3a + 2b 12

Amintiți-vă că valorile pentru unitățile jucăriei A pot fi doar în numere întregi. Aceasta înseamnă că avem și constrângerile a->0 și b<-0.

Deci, acum aveți o problemă de programare liniară adecvată. Puteți formula alte probleme de programare liniară urmând acest exemplu. Deși acest exemplu a fost destul de simplu, problemele LP pot deveni extrem de complicate.

Citiți: Idei și subiecte pentru proiecte de programare liniară

Etapele formulării problemelor de programare liniară

Pentru a formula o problemă de programare liniară, urmați acești pași:

• Găsiți variabilele de decizie
• Găsiți funcția obiectiv
• Identificați constrângerile
• Amintiți-vă de restricția de non-negativitate

Dacă o problemă îndeplinește criteriile de mai sus, este o problemă de programare liniară. Este cea mai bună practică să țineți cont de acest criteriu atunci când lucrați la identificarea tipului de problemă.

Rezolvarea problemelor de programare liniară cu R

Dacă utilizați R, rezolvarea problemelor de programare liniară devine mult mai simplă. Asta pentru că R are pachetul lpsolve care vine cu diverse funcții special concepute pentru rezolvarea unor astfel de probleme. Este foarte probabil că veți folosi R foarte frecvent pentru a rezolva problemele LP în calitate de cercetător de date. De aceea, am împărtășit două exemple distincte pentru a vă ajuta să înțelegeți mai bine implementarea acestuia:

Exemplu

Să începem cu o problemă de bază. O organizație are două produse cu prețuri de vânzare de 25 INR și 20 INR și se numesc produs A și respectiv B. În fiecare zi, au 1800 de unități de resurse pentru a produce aceste produse. Produsul A necesită 20 de unități de resurse și B necesită 12 unități de resurse. Timpul de producție pentru ambele produse este de patru minute, iar organizația primește un total de opt ore de lucru în fiecare zi. Problema este, care ar trebui să fie cantitatea de producție pentru fiecare dintre aceste produse pentru a maximiza profiturile companiei?

Soluţie:

Vom începe să rezolvăm această problemă prin definirea funcției sale obiective:

max(Vânzări) = max( 25 y 1 + 20 y 2 )

Aici, 25 și 20 sunt prețurile produsului A și respectiv B, y1 este unitățile totale de produs A produse și y2 este unitățile totale de produs B produse. Variabilele noastre de decizie sunt y1 și y2.

Acum vom stabili constrângerile pentru problema noastră:

Constrângere de resurse:

20 y 1 + 12 y 2 1800

Limită de timp:

4 y 1 + 4 y 2 8*60

Ne propunem să găsim numărul corect de produse pe care trebuie să le fabricăm pentru a obține profitul maxim.

Folosind R pentru a rezolva problema:

Vom folosi lpsolve pentru a rezolva această problemă LP și vom începe cu setarea funcției obiectiv:

> necesită(lpSolve)

Se încarcă pachetul necesar: lpSolve

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

> obiectiv.in

[1] 25 20

Apoi vom construi o matrice pentru constrângeri:

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

> const

[,1] [,2]

[1,] 20 12

[2,] 4 4

> constrângeri de timp <- (8*60)

> constrângeri_resurse <- 1800

> constrângeri de timp

[1] 480

> constrângeri_resurse

[1] 1800

Să creăm acum ecuațiile deja definite:

> rhs <- c(resource_constraints, time_constraints)

> rhs

[1] 1800 480

> direcția <- c(„<=”, „<=”)

> directie

[1] „<=" „<="

Odată ce sunt adăugate toate informațiile necesare, putem începe să găsim răspunsul optim. Sintaxa pentru pachetul nostru este:

lp( direcție, obiectiv, const.mat, const.dir, const.rhs )

> optim <- lp(direction=”max”, obiectiv.in, const, direction, rhs)

> optim

Succes: funcția obiectiv este 2625

> rezumat(optim)

Modul clasa de lungime

directia 1 -niciuna- numerica

x.număr 1 -nici unul- numeric

obiectivul 2 -niciuna- numeric

const.count 1 -niciuna- numeric

constrângeri 8 -niciuna- numerice

int.count 1 -niciuna- numeric

int.vec 1 -niciuna- numeric

bin.număr 1 -nici unul- numeric

binar.vec 1 -niciuna- numeric

num.bin.solns 1 -niciuna- numeric

objval 1 -niciuna- numeric

soluția 2 -niciuna- numerică

presolve 1 -niciuna- numeric

calcula.sens 1 -niciuna- numeric

sens.coef.din 1 -niciuna- numeric

sens.coef.la 1 -niciuna- numeric

duale 1 -niciuna- numerice

duale.de la 1 -niciuna- numeric

duale.la 1 -niciuna- numeric

scara 1 -niciuna- numerica

folosi.dens 1 -niciuna- numeric

dens.col 1 -niciuna- numeric

dens.val 1 -niciuna- numeric

dens.const.nrow 1 -niciuna- numeric

dens.ctr 1 -niciuna- numeric

foloseste.rw 1 -niciuna- numeric

tmp 1 -niciun- caracter

starea 1 -niciuna- numeric

După rularea codului de mai sus, puteți obține soluțiile dorite pentru problema noastră.

Valorile optime pentru y1 și y2:

Amintiți-vă că y1 și y2 au fost unitățile produsului A și ale produsului B pe care a trebuit să le producem:

> soluție$optimă

[1] 45 75

Cifra optimă de vânzări:

Profitul maxim pe care îl putem genera cu valorile obținute ale lui y1 și y2 este:

> optim$objval

[1] 2625

Citește și: Algebră liniară pentru învățarea automată

Utilizări ale programării liniare

După cum am menționat anterior, programarea liniară își găsește aplicații în multe industrii. Iată câteva zone în care îl folosim:

• Odată cu popularitatea în creștere a serviciilor de livrare, programarea liniară a devenit una dintre cele mai preferate metode de găsire a rutelor optime. Când luați un Ola sau un Uber, software-ul va folosi programarea liniară pentru a găsi cea mai bună rută. Companiile de livrare precum Amazon și FedEx îl folosesc și pentru a determina cele mai bune rute pentru livratorii lor. Aceștia se concentrează pe reducerea timpului și costurilor de livrare.
• Învățarea supravegheată a învățării automate funcționează pe conceptele fundamentale ale programării liniare. În învățarea supravegheată, trebuie să găsiți modelul matematic optim pentru a prezice rezultatul în funcție de datele de intrare furnizate.
• Sectorul comerțului cu amănuntul folosește programarea liniară pentru optimizarea spațiului pe raft. Cu atât de multe mărci și produse disponibile, a determina unde să le plaseze în magazin este o sarcină foarte riguroasă. Amplasarea unui produs în magazin poate afecta foarte mult vânzările acestuia. Principalele lanțuri de vânzare cu amănuntul, cum ar fi Big Bazaar, Reliance, Walmart etc. utilizează programarea liniară pentru a determina plasarea produsului. Ei trebuie să țină cont de interesul consumatorilor, asigurând în același timp cea mai bună plasare a produsului pentru a obține profit maxim.
• Companiile folosesc programarea liniară pentru a-și îmbunătăți lanțurile de aprovizionare. Eficiența unui lanț de aprovizionare depinde de mulți factori, cum ar fi rutele alese, calendarele etc. Folosind programarea liniară, aceștia pot găsi cele mai bune rute, momente și alte alocări de resurse pentru a-și optimiza eficiența.

Aflați mai multe despre programarea liniară și știința datelor

Programarea liniară este unul dintre cele mai vitale concepte ale științei datelor. Este, de asemenea, un subiect fundamental pe care ar trebui să-l cunoașteți pentru a deveni un expert în știință de date. După cum am discutat, există multe aplicații pentru acest concept și îi puteți găsi cazuri de utilizare în viața de zi cu zi.

Puteți afla mai multe despre știința datelor și conceptele aferente acesteia, accesând blogul nostru. Avem multe resurse valoroase pentru a vă ajuta să aflați mai multe. Iată câteva pentru a le citi în continuare:

• Principalele motive pentru a deveni un Data Scientist
• Algoritmii pe care fiecare cercetător de date ar trebui să-i cunoască
• Cum să devii un Data Scientist

Pe de altă parte, puteți obține un curs de știință a datelor pentru a învăța de la experții din industrie. Veți putea învăța în mod interactiv prin videoclipuri, chestionare și proiecte. Urmărirea unui curs vă va ajuta să învățați abilitățile necesare pentru a deveni un cercetător profesionist de date. Consultați Diploma PG în știința datelor de la IIIT-B și upGrad, care este creată pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1-la-1 cu mentori din industrie, peste 400 de ore de învățare și asistență la locul de muncă cu firme de top.