Știți ce înseamnă optimizarea unui sistem pentru a obține cel mai bun rezultat posibil dacă ești student la inginerie sau inginer.
Optimizarea unei soluții este cheia succesului în orice, de la construirea de punți la crearea de software.
Ideea unei soluții de bază fezabile apare în acest moment.
Este o idee de bază în programarea liniară care vă permite să vă dați seama care dintre un set de soluții posibile este cea mai bună.
Dar de ce contează atât de mult? În acest articol, voi vorbi despre soluțiile de bază fezabile și despre cum pot fi utilizate pentru a rezolva problemele de inginerie din lumea reală.
Voi vorbi despre cum să le găsesc, din ce sunt făcute și de ce sunt importante.
Deci, indiferent dacă sunteți un inginer cu experiență sau un student care abia la început, veniți cu noi în timp ce mă scufund în lumea soluțiilor de bază fezabile și vă arăt cum să utilizați puterea programării liniare.
Înțelegerea soluției de bază fezabile
Definiție formală:
O soluție de bază pentru un model de program liniar în care toate variabilele sunt nenegative.
O soluție fezabilă de bază (BFS) este o idee cheie în programarea liniară care ajută la găsirea celor mai bune soluții.
Un BFS este o soluție cu cel mai mic număr posibil de variabile diferite de zero.
Este un colț al poliedrului soluțiilor fezabile.
Cu alte cuvinte, un BFS este o soluție de bază care îndeplinește constrângerile nenegative și se află în regiunea fezabilă sau zona cu probleme.
Găsirea unei soluții de bază fezabile optime
Pentru a găsi cel mai bun BFS, trebuie să facem următoarele:
- Scrieți programul în formă standard pentru o secvență liniară.
- Transformați sistemul de inegalități într-o matrice augmentată.
- Aflați care variabile sunt de bază și care nu.
- Aflați care sunt variabilele de bază în ceea ce privește celelalte variabile.
- Puneți aceste expresii în funcția obiectiv pentru a obține o funcție numai a variabilelor care nu sunt de bază.
- Găsiți o variabilă nebază care poate fi crescută fără a încălca nicio constrângere și care va îmbunătăți funcția obiectiv.
Această variabilă este acum o variabilă de bază, iar una dintre celelalte variabile de bază nu mai este o variabilă de bază.
Dacă există o soluție optimă, aceasta trebuie să fie la unul dintre capetele, sau vârfurile, ale regiunii în care soluțiile sunt posibile.
Deci, dacă un LP are o soluție optimă, are o soluție optimă într-un punct extrem al mulțimii fezabile.
De asemenea, există întotdeauna un BFS optim dacă există o soluție optimă.
Folosind metoda Simplex pentru a găsi un BFS optim
Metoda Simplex este un algoritm pentru rezolvarea problemelor din programarea liniară.
Se mută de la un BFS la un BFS „adiacent” utilizând procedura pivot.
În procedura pivot, o variabilă non-bază este aleasă pentru a deveni o variabilă de bază, iar apoi BFS-ul curent este folosit pentru a rezolva noile variabile de bază.
Când nicio variabilă non-bazică nu poate fi modificată pentru a îmbunătăți funcția obiectiv, algoritmul este terminat.
De ce soluțiile fezabile de bază sunt esențiale pentru rezolvarea problemelor complexe de inginerie
Inca greu de inteles? Hai sa schimb putin punctul de vedere:
Oricum, cine are nevoie de răspunsuri simple și practice? Doar pune totul laolaltă și speră la bine.
La urma urmei, cine are nevoie de optimizare când haosul este mult mai distractiv? Bine ați venit în lumea variabilelor nenegative, unde totul este doar o sugestie și eșecul este aproape sigur.
Sau este?
Să explorăm de ce conceptul aparent de bază al soluțiilor de bază fezabile nu este de bază și de ce ar putea fi doar cheia pentru rezolvarea chiar și a celor mai complexe probleme de inginerie.
Bine, a fost doar o glumă făcută să arate ca o reclamă TV.
Acum să revenim la explicație.
Găsirea soluției de bază fezabile
O soluție fezabilă de bază (BFS) este o soluție la o problemă de optimizare liniară care îndeplinește toate constrângerile și are cel mai puțin număr de variabile diferite de zero.
Fiecare BFS este un colț al poliedrului soluțiilor fezabile din punct de vedere geometric.
Dacă există cea mai bună soluție, trebuie să existe și un prim pas cel mai bun.
În acest articol, vom vorbi despre cum să găsiți o soluție fezabilă de bază inițială, cum să găsiți toate soluțiile fezabile de bază și cum să găsiți o soluție fezabilă de bază fără variabile de slăbire.
Găsirea unei soluții de bază fezabile inițiale
Putem folosi diferite metode, în funcție de modul în care este configurată problema, pentru a găsi o soluție de bază inițială care să funcționeze pentru o problemă de optimizare liniară.
O modalitate este de a adăuga variabile slack la constrângerile asupra inegalităților și de a seta toate celelalte variabile la zero.
Variabilele de slack devin variabilele de bază, iar restul sunt variabile non-bazice.
Metoda Simplex în două faze este o altă modalitate de a rezolva problema.
Această metodă implică rezolvarea unei probleme de programare liniară suplimentară pentru a găsi o soluție de bază inițială care este fezabilă.
Odată ce a fost găsită o soluție de bază fezabilă inițială, metoda Simplex poate fi utilizată pentru a trece de la o soluție fezabilă de bază la următoarea și apoi la cea mai bună soluție.
Găsirea tuturor soluțiilor de bază fezabile
Pot exista mai multe soluții de bază care funcționează pentru un program liniar.
Putem schimba sistemul adăugând variabile slack și apoi folosim noul sistem pentru a găsi toate soluțiile de bază fezabile pentru un program liniar.
Apoi, aceste soluții de bază fezabile sunt utilizate pentru a găsi soluțiile de bază fezabile pentru problema inițială.
Găsirea unei soluții de bază fezabile fără variabile de slăbiciune
Trebuie să folosim variabile slack pentru a scăpa de constrângerile mai puțin decât, astfel încât să putem găsi o soluție de bază care funcționează fără variabile slack.
O variabilă slack este doar diferența dintre partea dreaptă a unei constrângeri și partea stângă.
De exemplu, pentru prima constrângere, definim o variabilă slack x4 = 14 - 2x1 - x2 - x3. În ceea ce privește această nouă variabilă, prima constrângere este echivalentă pur și simplu cu x4 ≥ 0, care este o constrângere de pozitivitate pentru x4.
Când adăugăm aceste variabile slack, obținem un program liniar care este același cu cel original, cu excepția faptului că toate constrângerile sunt fie ecuații, fie constrângeri care spun că ceva este pozitiv.
Setul de variabile de bază, care au alte valori decât zero în soluția de bază, se numește bază.
Variabilele care au valoarea zero în soluția de bază nu sunt variabile de bază.
Pentru a găsi cea mai bună soluție, trebuie să găsim un vector x care îndeplinește toate regulile și obține cea mai mare sau cea mai mică valoare pentru obiectiv.
Dar găsirea celei mai bune soluții necesită mai mulți pași decât găsirea unei soluții care funcționează și nu are variabile de slăbiciune.
Nu este întotdeauna posibil să găsiți o soluție de bază fără variabile slack, în special pentru problemele cu constrângeri mai puțin decât.
Pentru a găsi o soluție fezabilă de bază, trebuie să utilizați metoda simplex sau un alt algoritm de programare liniară pentru a căuta o soluție care îndeplinește toate constrângerile și are cele mai puține variabile diferite de zero.
Proprietățile și semnificația soluției de bază fezabile
Proprietățile soluției de bază fezabile
O soluție fezabilă de bază are cel mult m variabile care nu sunt zero și cel puțin nm variabile care sunt zero, unde n este numărul de variabile de decizie și m este numărul de constrângeri.
Un BFS este un colț al poliedrului de soluții posibile, iar fiecare BFS are n constrângeri active care sunt liniar independente.
Dacă există cea mai bună soluție, trebuie să existe și un prim pas cel mai bun.
Cel mai important lucru despre soluțiile de bază fezabile este că acestea sunt capetele setului de soluții convexe pentru o problemă de programare liniară.
Pentru a găsi cel mai bun răspuns, algoritmul simplex trece printr-o serie de BFS.
Algoritmul Simplex caută prin toate soluțiile de bază posibile într-un mod organizat pentru a găsi cea mai bună.
Semnificația soluției de bază fezabile
Găsirea unei soluții de bază care este posibilă este importantă deoarece ajută la găsirea celui mai bun răspuns la problemele de programare liniară.
De asemenea, oferă algoritmilor complecși un loc de pornire și poate fi folosit pentru a afla dacă un program liniar este posibil sau nu.
Pentru a găsi toate soluțiile de bază fezabile pentru un program liniar, puteți schimba sistemul adăugând variabile de slack și apoi utilizați sistemul modificat pentru a găsi toate soluțiile de bază fezabile.
Apoi, aceste soluții de bază fezabile sunt utilizate pentru a găsi soluțiile de bază fezabile pentru problema inițială.
Video: Soluții de bază fezabile
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: | BFS poate fi folosit pentru a împărți resursele limitate între mai multe proiecte, astfel încât cel mai mult să se poată face cu cel mai puțin. Această metodă poate fi utilizată în multe domenii diferite, cum ar fi transportul, agricultura și finanțele. |
| Optimizarea rețelei: | BFS poate fi folosit pentru a face ca rețelele de comunicații, transport și logistică să funcționeze mai bine. BFS vă poate ajuta să găsiți cele mai bune rute pentru bunuri și servicii, să reducă timpul și banii cheltuiți pentru transport și să accelereze și să facă livrări mai precise. |
| Planificarea producției: | BFS poate fi utilizat pentru a planifica producția, astfel încât resursele precum forța de muncă, materiile prime și echipamentele să fie utilizate în cel mai bun mod posibil pentru a profita la maximum de ele. BFS poate ajuta la reducerea costurilor de producție, la reducerea deșeurilor și la îmbunătățirea eficienței. |
| Planificare financiara: | În planificarea financiară, BFS poate fi folosit pentru a optimiza portofoliile de investiții, pentru a reduce riscul și pentru a obține cei mai mulți bani înapoi. BFS vă poate ajuta să găsiți cea mai bună modalitate de a împărți activele, de a reduce costurile de tranzacție și de a câștiga mai mulți bani. |
| Managementul lanțului de aprovizionare: | BFS poate fi utilizat pentru a îmbunătăți fluxul de bunuri și servicii de la furnizori la clienți, ca parte a managementului lanțului de aprovizionare. BFS poate ajuta la determinarea celei mai bune cantități de stoc de păstrat la îndemână, la scurtarea timpilor de livrare și la îmbunătățirea serviciului pentru clienți. |
Concluzie
Pe măsură ce această privire asupra soluțiilor de bază fezabile se apropie de sfârșit, este clar că acestea sunt un instrument important pentru orice inginer sau student la inginerie.
De la găsirea celui mai bun mod de a construi un sistem complicat până la valorificarea la maximum a resurselor disponibile, soluțiile de bază fezabile oferă un cadru pentru obținerea celui mai bun rezultat posibil.
Dar mai mult decât să fie utile, ele arată cât de elegantă și frumoasă poate fi matematica.
Este uimitor că puteți reduce probleme complicate într-un set simplu de ecuații și apoi puteți utiliza acele ecuații pentru a rezolva probleme din lumea reală.
Este o bună reamintire că ingineria înseamnă rezolvarea problemelor și că, folosind puterea matematicii, putem găsi răspunsuri despre care odată se credeau imposibile.
Așadar, pe măsură ce învățați mai multe despre inginerie, țineți cont de ceea ce ați învățat despre soluțiile simple care funcționează și le utilizați pentru a face lumea un loc mai bun și mai eficient.
Link-uri și referințe
Cărți:
- Programare liniară: fundații și extensii
- Programare liniară: teorie și aplicații
Distribuie pe…
