Ju e dini se çfarë do të thotë të optimizoni një sistem për të marrë rezultatin më të mirë të mundshëm nëse jeni student i inxhinierisë ose inxhinier.
Optimizimi i një zgjidhjeje është çelësi i suksesit në çdo gjë, nga ndërtimi i urave te krijimi i softuerit.
Ideja e një zgjidhjeje bazë të realizueshme vjen në këtë pikë.
Është një ide bazë në programimin linear që ju lejon të kuptoni se cila nga një grup zgjidhjesh të mundshme është më e mira.
Por pse ka kaq shumë rëndësi? Në këtë artikull, unë do të flas për zgjidhjet themelore të realizueshme dhe se si ato mund të përdoren për të zgjidhur problemet inxhinierike në botën reale.
Unë do të flas se si t'i gjejmë ato, nga çfarë janë bërë dhe pse janë të rëndësishme.
Pra, nëse jeni një inxhinier me përvojë ose një student që sapo filloni, ejani me ne ndërsa unë zhytem në botën e zgjidhjeve bazë të realizueshme dhe t'ju tregoj se si të përdorni fuqinë e programimit linear.
Kuptimi i zgjidhjes themelore të realizueshme
Përkufizimi zyrtar:
Një zgjidhje bazë për një model programi linear në të cilin të gjitha variablat janë jonegative.
Një zgjidhje bazë e realizueshme (BFS) është një ide kyçe në programimin linear që ndihmon në gjetjen e zgjidhjeve më të mira.
Një BFS është një zgjidhje me numrin më të vogël të mundshëm të variablave jo zero.
Është një cep i poliedrit të zgjidhjeve të realizueshme.
Me fjalë të tjera, një BFS është një zgjidhje bazë që plotëson kufizimet jo negative dhe është në rajonin ose zonën e problemit të realizueshëm.
Gjetja e një zgjidhje optimale themelore të realizueshme
Për të gjetur BFS-në më të mirë, duhet të bëjmë sa më poshtë:
- Shkruani programin në formë standarde për një sekuencë lineare.
- Kthejeni sistemin e pabarazive në një matricë të shtuar.
- Kuptoni se cilat variabla janë bazë dhe cilat jo.
- Kuptoni se cilat janë variablat bazë në lidhje me variablat e tjerë.
- Vendosini këto shprehje në funksionin objektiv për të marrë një funksion vetëm të variablave që nuk janë bazë.
- Gjeni një variabël jo bazë që mund të rritet pa thyer asnjë kufizim dhe që do ta bëjë objektivin funksion më të mirë.
Kjo variabël tani është një variabël bazë, dhe një nga variablat e tjerë bazë nuk është më një variabël bazë.
Nëse ka një zgjidhje optimale, ajo duhet të jetë në një nga skajet, ose kulmet, të rajonit ku zgjidhjet janë të mundshme.
Pra, nëse një LP ka një zgjidhje optimale, ajo ka një zgjidhje optimale në një pikë ekstreme të grupit të realizueshëm.
Gjithashtu, ekziston gjithmonë një BFS optimale nëse ka një zgjidhje optimale.
Përdorimi i metodës Simplex për të gjetur një BFS optimale
Metoda Simplex është një algoritëm për zgjidhjen e problemeve në programimin linear.
Ai lëviz nga një BFS në një BFS "të afërt" duke përdorur procedurën e rrotullimit.
Në procedurën e rrotullimit, një variabël jo-bazë zgjidhet për t'u bërë një variabël bazë, dhe më pas përdoret BFS-ja aktuale për të zgjidhur variablat e reja bazë.
Kur asnjë variabël jo-bazë nuk mund të ndryshohet për të përmirësuar funksionin objektiv, algoritmi kryhet.
Pse zgjidhjet themelore të realizueshme janë vendimtare për zgjidhjen e problemeve komplekse inxhinierike
Ende e vështirë për t'u kuptuar? Më lejoni të ndryshoj pak këndvështrimin:
Kush ka nevojë për përgjigje të thjeshta dhe të zbatueshme gjithsesi? Thjesht bashkoni gjithçka dhe shpresoni për më të mirën.
Në fund të fundit, kujt i duhet optimizimi kur kaosi është shumë më argëtues? Mirë se vini në botën e variablave jonegativë, ku gjithçka është vetëm një sugjerim dhe dështimi është pothuajse i sigurt.
Apo është ajo?
Le të shqyrtojmë pse koncepti në dukje themelor i zgjidhjeve bazë të realizueshme është gjithçka tjetër veçse bazë dhe pse ato mund të jenë thjesht çelësi për zgjidhjen edhe të problemeve më komplekse inxhinierike.
Mirë, kjo ishte vetëm një shaka e bërë për t'u dukur si një reklamë televizive.
Tani le të kthehemi te shpjegimi.
Gjetja e zgjidhjes bazë të realizueshme
Një zgjidhje bazë e realizueshme (BFS) është një zgjidhje për një problem të optimizimit linear që plotëson të gjitha kufizimet dhe ka numrin më të vogël të ndryshoreve jo zero.
Çdo BFS është një cep i poliedrit të zgjidhjeve të realizueshme nga pikëpamja gjeometrike.
Nëse ka një zgjidhje më të mirë, duhet të ketë edhe një hap të parë më të mirë.
Në këtë artikull, ne do të flasim se si të gjejmë një zgjidhje fillestare të realizueshme bazë, si të gjejmë të gjitha zgjidhjet themelore të realizueshme dhe si të gjejmë një zgjidhje bazë të realizueshme pa variabla të dobët.
Gjetja e një zgjidhjeje fillestare themelore të realizueshme
Ne mund të përdorim metoda të ndryshme, në varësi të mënyrës se si është vendosur problemi, për të gjetur një zgjidhje bazë fillestare që funksionon për një problem të optimizimit linear.
Një mënyrë është shtimi i variablave slack në kufizimet për pabarazitë dhe vendosja e të gjithë variablave të tjerë në zero.
Variablat Slack bëhen variablat bazë, dhe pjesa tjetër janë variabla jo-bazë.
Metoda Simplex dyfazore është një mënyrë tjetër për të zgjidhur problemin.
Kjo metodë përfshin zgjidhjen e një problemi programimi ekstra linear për të gjetur një zgjidhje bazë fillestare që është e realizueshme.
Pasi të jetë gjetur një zgjidhje fillestare e realizueshme, Metoda Simplex mund të përdoret për të kaluar nga një zgjidhje bazë e realizueshme në tjetrën dhe më pas në zgjidhjen më të mirë.
Gjetja e të gjitha zgjidhjeve themelore të realizueshme
Mund të ketë më shumë se një zgjidhje bazë që funksionon për një program linear.
Ne mund ta ndryshojmë sistemin duke shtuar variabla slack dhe më pas të përdorim sistemin e ri për të gjetur të gjitha zgjidhjet themelore të realizueshme për një program linear.
Më pas, këto zgjidhje themelore të realizueshme përdoren për të gjetur zgjidhjet themelore të realizueshme për problemin origjinal.
Gjetja e një zgjidhjeje bazë të realizueshme pa variabla të dobët
Ne duhet të përdorim variablat Slack për të hequr qafe kufizimet më pak se në mënyrë që të gjejmë një zgjidhje bazë që funksionon pa variabla të zbehta.
Një variabël Slack është vetëm ndryshimi midis anës së djathtë të një kufizimi dhe anës së majtë.
Për shembull, për kufizimin e parë, ne përcaktojmë një ndryshore të ngadaltë x4 = 14 - 2x1 - x2 - x3. Për sa i përket kësaj ndryshoreje të re, kufizimi i parë është thjesht ekuivalent me x4 ≥ 0, që është një kufizim pozitiviteti për x4.
Kur i shtojmë këto variabla të zbehta, marrim një program linear që është i njëjtë me atë origjinal, përveç që të gjitha kufizimet janë ose ekuacione ose kufizime që thonë se diçka është pozitive.
Bashkësia e ndryshoreve bazë, të cilat kanë vlera të tjera nga zero në zgjidhjen bazë, quhet bazë.
Variablat që kanë vlerën zero në zgjidhjen bazë nuk janë variabla bazë.
Për të gjetur zgjidhjen më të mirë, duhet të gjejmë një vektor x që plotëson të gjitha rregullat dhe merr vlerën më të madhe ose më të vogël për objektivin.
Por gjetja e zgjidhjes më të mirë kërkon më shumë hapa sesa thjesht gjetja e një zgjidhjeje që funksionon dhe nuk ka variabla të zbehta.
Nuk është gjithmonë e mundur të gjesh një zgjidhje bazë pa variabla të ngadaltë, veçanërisht për problemet me më pak se kufizime.
Për të gjetur një zgjidhje bazë të realizueshme, duhet të përdorni metodën simplex ose një algoritëm tjetër të programimit linear për të kërkuar një zgjidhje që plotëson të gjitha kufizimet dhe ka më pak ndryshore jo zero.
Vetitë dhe rëndësia e zgjidhjes bazë të realizueshme
Vetitë e zgjidhjes bazë të realizueshme
Një zgjidhje bazë e realizueshme ka më së shumti m variabla që nuk janë zero dhe të paktën nm variabla që janë zero, ku n është numri i variablave të vendimit dhe m është numri i kufizimeve.
Një BFS është një cep i poliedrit të zgjidhjeve të mundshme, dhe çdo BFS ka n kufizime aktive që janë linearisht të pavarur.
Nëse ka një zgjidhje më të mirë, duhet të ketë edhe një hap të parë më të mirë.
Gjëja më e rëndësishme për zgjidhjet themelore të realizueshme është se ato janë skajet e grupit të zgjidhjeve konvekse për një problem të programimit linear.
Për të gjetur përgjigjen më të mirë, algoritmi simplex kalon nëpër një seri BFS.
Algoritmi Simplex kërkon të gjitha zgjidhjet e mundshme themelore në mënyrë të organizuar për të gjetur më të mirën.
Rëndësia e zgjidhjes bazë të realizueshme
Gjetja e një zgjidhjeje bazë që është e mundur është e rëndësishme sepse ndihmon në gjetjen e përgjigjes më të mirë për problemet e programimit linear.
Ai gjithashtu u jep algoritmeve komplekse një vend për të filluar dhe mund të përdoret për të kuptuar nëse një program linear është i mundur apo jo.
Për të gjetur të gjitha zgjidhjet bazë të realizueshme për një program linear, mund ta ndryshoni sistemin duke shtuar variabla të zbehta dhe më pas të përdorni sistemin e ndryshuar për të gjetur të gjitha zgjidhjet bazë të realizueshme.
Më pas, këto zgjidhje themelore të realizueshme përdoren për të gjetur zgjidhjet themelore të realizueshme për problemin origjinal.
Video: Zgjidhjet themelore të realizueshme
Këshillë: Aktivizoni butonin e titrave nëse ju nevojitet. Zgjidhni "përkthim automatik" në butonin e cilësimeve, nëse nuk jeni të njohur me gjuhën e folur. Mund t'ju duhet së pari të klikoni në gjuhën e videos përpara se gjuha juaj e preferuar të bëhet e disponueshme për përkthim.
Raste te perdorimit
| Përdorur në: | Përshkrim: |
|---|---|
| Shpërndarja e burimeve: | BFS mund të përdoret për të ndarë burimet e kufizuara midis disa projekteve në mënyrë që më së shumti të mund të bëhet me më pak. Kjo metodë mund të përdoret në shumë fusha të ndryshme, si transporti, bujqësia dhe financa. |
| Optimizimi i rrjetit: | BFS mund të përdoret për të funksionuar më mirë rrjetet e komunikimit, transportit dhe logjistikës. BFS mund të ndihmojë në gjetjen e rrugëve më të mira për mallra dhe shërbime, të shkurtojë kohën dhe paratë e shpenzuara për transport dhe të përshpejtojë dhe të bëjë dërgesa më të sakta. |
| Planifikimi i prodhimit: | BFS mund të përdoret për të planifikuar prodhimin në mënyrë që burimet si puna, lëndët e para dhe pajisjet të përdoren në mënyrën më të mirë të mundshme për të përfituar sa më shumë prej tyre. BFS mund të ndihmojë në uljen e kostove të prodhimit, uljen e mbetjeve dhe përmirësimin e efikasitetit. |
| Planifikimi Financiar: | Në planifikimin financiar, BFS mund të përdoret për të optimizuar portofolet e investimeve, për të ulur rrezikun dhe për të marrë sa më shumë para. BFS mund të ndihmojë në gjetjen e mënyrës më të mirë për të ndarë aktivet, për të ulur kostot e transaksionit dhe për të fituar më shumë para. |
| Menaxhimi i zinxhirit të furnizimit: | BFS mund të përdoret për të përmirësuar rrjedhën e mallrave dhe shërbimeve nga furnitorët te klientët si pjesë e menaxhimit të zinxhirit të furnizimit. BFS mund të ndihmojë në gjetjen e sasisë më të mirë të stokut për të mbajtur në dorë, të shkurtojë kohën e ofrimit dhe të përmirësojë shërbimin ndaj klientit. |
konkluzioni
Ndërsa ky vështrim i zgjidhjeve bazë të realizueshme po përfundon, është e qartë se ato janë një mjet i rëndësishëm për çdo inxhinier apo student inxhinierie.
Nga gjetja e mënyrës më të mirë për të ndërtuar një sistem të ndërlikuar deri në shfrytëzimin maksimal të burimeve të disponueshme, zgjidhjet bazë të realizueshme ofrojnë një kornizë për marrjen e rezultatit më të mirë të mundshëm.
Por më shumë sesa thjesht të jenë të dobishme, ato tregojnë se sa elegante dhe e bukur mund të jetë matematika.
Është e mahnitshme që ju mund t'i zbërtheni problemet e ndërlikuara në një grup të thjeshtë ekuacionesh dhe më pas t'i përdorni ato ekuacione për të zgjidhur problemet në botën reale.
Është një kujtesë e mirë se inxhinieria ka të bëjë me zgjidhjen e problemeve dhe se duke përdorur fuqinë e matematikës, ne mund të gjejmë përgjigje që dikur mendoheshin të pamundura.
Pra, ndërsa mësoni më shumë rreth inxhinierisë, mbani në mend atë që keni mësuar për zgjidhjet e thjeshta që funksionojnë dhe përdorni ato për ta bërë botën një vend më të mirë dhe më efikas.
Lidhjet dhe referencat
Libra:
- Programimi Linear: Bazat dhe Zgjerimet
- Programimi linear: Teoria dhe Zbatimet
Shpërndaje në…
