Dacă ești inginer sau student la inginerie, poate știi ce înseamnă optimizarea.
Pentru a obține cel mai bun rezultat posibil, este important să găsiți cel mai bun mod de a face lucrurile.
În programarea liniară, puteți folosi o soluție de bază pentru a găsi cea mai bună soluție.
Dar care este o soluție de bază și de ce este atât de important ca inginerii să știe despre ele? În acest articol, voi vorbi despre soluțiile de bază, de ce sunt importante în inginerie și despre cum pot fi folosite pentru a obține cele mai bune rezultate în diferite situații.
Așa că puneți-vă centura și pregătiți-vă să vă scufundați în lumea soluțiilor de bază, unde voi sparge misterele și vă voi arăta cât de puternică poate fi această tehnică.
Soluții de bază în programarea liniară
Definiție formală:
O soluție a unui model de program liniar constând din m ecuații în n variabile este obținută prin rezolvarea pentru m variabile în termenii variabilelor rămase (nm) și setarea variabilelor (nm) egale cu zero.
O soluție de bază în programarea liniară este o modalitate de a rezolva o problemă de programare liniară care îndeplinește anumite cerințe tehnice.
În special, un vector x este o soluție de bază pentru un poliedru dacă vectorii {ai : xi = 0} sunt liniar independenți.
Aceasta înseamnă că coloanele lui A care au variabile xi care nu sunt zero sunt liniar independente.
O soluție de bază cu componente nenegative se numește soluție fezabilă de bază (BFS) (BFS).
Un BFS îndeplinește toate regulile care definesc un poliedru.
Fiecare BFS este un colț al poliedrului soluțiilor fezabile din punct de vedere geometric.
Pentru a găsi o soluție de bază, trebuie să setați nm variabile care nu sunt de bază la zero și să rezolvați m variabile care sunt de bază.
Este posibil ca baze diferite să conducă la aceeași soluție de bază, ceea ce înseamnă că pot exista mai multe modalități de a rezolva aceeași problemă.
Metoda Simplex este un proces iterativ care trece de la un BFS la următorul BFS până când găsește cel mai bun BFS.
După ce am folosit metoda simplex pentru a găsi un BFS, putem spune dacă soluția este cea mai bună, văzând dacă alte BFS din apropiere oferă o valoare mai bună pentru funcția obiectiv.
Dacă nu există un astfel de BFS, atunci BFS actual este cel mai bun.
Model de programare liniară
Un model de programare liniară implică trei componente principale: variabile de decizie, o funcție obiectivă și constrângeri.
Atât funcția obiectiv, cât și constrângerile trebuie să fie funcții liniare, iar variabilele de decizie trebuie să fie continue.
Funcția obiectiv este folosită fie pentru a crește, fie pentru a micșora un număr care reprezintă profit, cost, număr de produse realizate etc.
Constrângerile sunt limite sau restricții asupra cantității totale a unei anumite resurse care este necesară pentru îndeplinirea sarcinilor care vor determina nivelul de succes în variabilele de decizie.
În plus, unele programe liniare necesită ca toate variabilele de decizie să fie nenegative.
În modelele de programare liniară, puteți utiliza și variabile întregi și binare.
Variabilele binare pot avea doar o valoare de 0 sau 1, deci pot avea doar o valoare de 0 sau 1.
Metoda Simplex
Una dintre cele mai utilizate moduri de rezolvare a problemelor de programare liniara este Metoda Simplex.
Soluțiile de bază sunt importante în metoda simplex deoarece corespund punctelor de colț ale regiunii fezabile, iar metoda simplex se deplasează de la un colț la altul până când se găsește o soluție optimă.
Metoda simplex este o modalitate rapidă de a găsi cel mai bun răspuns la o problemă de programare liniară folosind proprietățile soluțiilor de bază.
Pentru a folosi metoda simplex pentru a găsi cel mai bun BFS, trebuie să găsim o bază B pentru matricea de constrângeri A și să rezolvăm sistemul Ax = b cu toate variabilele, altele decât baza setată la zero.
Valorile rezultate pentru variabilele de bază formează un BFS.
Dacă există o soluție optimă, atunci există un BFS optim.
Metoda Simplex se mută de la un BFS la un BFS adiacent până când ajunge la un BFS optim utilizând proceduri pivot.
Comparație între soluțiile de bază și soluțiile fezabile
Diferența dintre o soluție de bază și o soluție fezabilă este că o soluție de bază nu trebuie să îndeplinească nicio condiție.
În special, trebuie să aibă vectori care sunt independenți liniar și au valori diferite de zero pentru xi, iar x trebuie să fie mai mic decât 0.
Pe de altă parte, o soluție fezabilă este orice punct care se încadrează în limitele problemei.
Dar nu toate soluțiile fezabile sunt soluții fezabile de bază.
Soluțiile fezabile de bază (BFS) sunt numai cele care se potrivesc cu colțurile poliedrului soluțiilor fezabile.
Înapoi la elemente de bază: deblocarea puterii soluțiilor de bază în inginerie
Inca greu de inteles? Hai sa schimb putin punctul de vedere:
Te-ai săturat să folosești metode și algoritmi complicati pentru a rezolva probleme dificile? V-ați dori să existe o modalitate mai simplă și mai simplă de a rezolva problemele modelului de program liniar?
Ei bine, nu vă faceți griji, pentru că răspunsul este aici: rezolvați pentru m variabile în ceea ce privește variabilele rămase (nm) și setați variabilele (nm) la zero.
Cine are nevoie de algoritmi care sună fantezis când te poți întoarce la elementele de bază? Așa că puneți-vă deoparte calculatoarele și să începem să învățăm despre soluții simple.
Bine, a fost doar o glumă făcută să arate ca o reclamă TV.
Acum să revenim la explicație.
Soluție de bază Programare liniară
Sfat: activați butonul de subtitrare dacă aveți nevoie de el. Alegeți „traducere automată” în butonul de setări, dacă nu sunteți familiarizat cu limba vorbită. Poate fi necesar să faceți mai întâi clic pe limba videoclipului înainte ca limba preferată să devină disponibilă pentru traducere.
Cazuri de utilizare
| Folosit in: | Descriere: |
|---|---|
| Alocarea resurselor: | Soluția de bază poate fi utilizată în problemele de alocare a resurselor, unde scopul este împărțirea resurselor limitate între nevoile concurente. De exemplu, o companie ar putea avea nevoie să-și împartă bugetul între diferite departamente sau proiecte. Folosind soluții de bază, aceștia pot găsi cea mai bună modalitate de a-și folosi resursele pentru a câștiga cei mai mulți bani sau a cheltui cât mai puțin posibil. |
| Planificarea producției: | În planificarea producției, soluția de bază poate fi folosită pentru a găsi cea mai bună combinație de produse de făcut pentru a câștiga cei mai mulți bani. Companiile pot găsi cel mai bun mix de producție care aduce cei mai mulți bani și costă cel mai puțin folosind soluția de bază. |
| Programare: | Soluția de bază poate fi folosită pentru a înțelege cum să programați sarcini sau lucrări, astfel încât acestea să poată fi realizate în cel mai eficient mod. De exemplu, o companie poate avea nevoie să planifice orele de lucru ale angajaților săi pentru a se asigura că au destui lucrători atunci când afacerile sunt ocupate. Folosind o soluție de bază, aceștia pot găsi cea mai bună modalitate de a programa lucrurile, astfel încât să existe cât mai puțin timp de nefuncționare și să se realizeze cât mai multă muncă. |
| Managementul lanțului de aprovizionare: | În managementul lanțului de aprovizionare, scopul este de a se asigura că bunurile și serviciile se deplasează cât mai ușor de la furnizor la client. De exemplu, o afacere poate avea nevoie să găsească cele mai bune rute pentru transportul mărfurilor, astfel încât costurile să fie menținute la minimum și mărfurile să fie livrate la timp. Folosind soluții de bază, aceștia pot găsi cel mai bun plan de gestionare a lanțului de aprovizionare care menține costurile scăzute și îi mulțumește pe clienți. |
| Optimizarea portofoliului: | În optimizarea portofoliului, în care scopul este de a găsi cel mai bun mix de investiții pentru a câștiga cei mai mulți bani, asumându-și cel mai mic risc, pot fi utilizate soluții de bază. De exemplu, o firmă de investiții poate avea nevoie să găsească cea mai bună combinație de acțiuni, obligațiuni și alte valori mobiliare pentru a-și ajuta clienții să-și atingă obiectivele de investiții. Folosind o soluție simplă, aceștia pot găsi cea mai bună modalitate de a-și combina portofoliile, astfel încât să obțină cele mai bune randamente, în timp ce își asumă cel mai mic risc. |
Concluzie
În concluzie, ideea unei soluții de bază este foarte importantă în domeniul ingineriei și poate fi folosită în multe moduri diferite.
Știind ce este o soluție de bază și ce face ea în programarea liniară, putem îmbunătăți soluțiile, reduce costurile și le facem mai eficiente.
Dar este important să ne amintim că soluția de bază nu este o soluție unică, chiar dacă este un instrument puternic.
Pentru a obține cele mai bune rezultate, fiecare problemă trebuie analizată și gândită cu atenție.
În calitate de ingineri, trebuie să ne uităm în continuare la modul în care soluțiile de bază și alte tehnici de optimizare ne pot ajuta să facem progrese și să venim cu idei noi.
Așadar, să recunoaștem puterea soluțiilor simple și să continuăm să depășim limitele a ceea ce este posibil utilizând noi tehnici și strategii.
Link-uri și referințe
Cărți:
- Programare liniară de Vasek Chvatal
- Modelarea și rezolvarea programării liniare cu R de Jose M. Sallan
Distribuie pe…
