Du vet vad det innebär att optimera ett system för att få bästa möjliga resultat om du är ingenjörsstudent eller ingenjör.
Att optimera en lösning är nyckeln till framgång i allt från att bygga broar till att göra mjukvara.
Idén om en grundläggande genomförbar lösning kommer in vid denna tidpunkt.
Det är en grundläggande idé inom linjär programmering som låter dig ta reda på vilken av en uppsättning möjliga lösningar som är bäst.
Men varför spelar det så stor roll? I den här artikeln kommer jag att prata om grundläggande genomförbara lösningar och hur de kan användas för att lösa tekniska problem i den verkliga världen.
Jag ska prata om hur man hittar dem, vad de är gjorda av och varför de är viktiga.
Så oavsett om du är en erfaren ingenjör eller en student som precis har börjat, kom med oss när jag dyker in i världen av grundläggande genomförbara lösningar och visar dig hur du använder kraften i linjär programmering.
Förstå grundläggande genomförbar lösning
Formell definition:
En grundläggande lösning på en linjär programmodell där alla variabler är icke-negativa.
En grundläggande genomförbar lösning (BFS) är en nyckelidé inom linjär programmering som hjälper till att hitta de bästa lösningarna.
En BFS är en lösning med minsta möjliga antal icke-nollvariabler.
Det är ett hörn av polyedern av genomförbara lösningar.
Med andra ord är en BFS en grundläggande lösning som möter de icke-negativa begränsningarna och som ligger i den genomförbara regionen eller problemområdet.
Att hitta en optimal grundläggande genomförbar lösning
För att hitta den bästa BFS måste vi göra följande:
- Skriv programmet i standardform för en linjär sekvens.
- Förvandla systemet av ojämlikheter till en utökad matris.
- Ta reda på vilka variabler som är grundläggande och vilka som inte är det.
- Ta reda på vad de grundläggande variablerna är när det gäller de andra variablerna.
- Sätt in dessa uttryck i objektivfunktionen för att få en funktion av endast de variabler som inte är grundläggande.
- Hitta en icke-grundläggande variabel som kan ökas utan att bryta några begränsningar och som gör att objektivet fungerar bättre.
Denna variabel är nu en basvariabel, och en av de andra basvariablerna är inte längre en basvariabel.
Om det finns en optimal lösning måste den finnas i en av ändarna, eller hörn, av regionen där lösningar är möjliga.
Så om en LP har en optimal lösning, har den en optimal lösning vid en extrem punkt av den genomförbara uppsättningen.
Dessutom finns det alltid en optimal BFS om det finns en optimal lösning.
Använda den enkla metoden för att hitta en optimal BFS
Simplex-metoden är en algoritm för att lösa problem inom linjär programmering.
Den flyttar från en BFS till en "intilliggande" BFS genom att använda pivotproceduren.
I pivotproceduren väljs en icke-basvariabel för att bli en basvariabel, och sedan används nuvarande BFS för att lösa de nya basvariablerna.
När ingen icke-grundläggande variabel kan ändras för att få objektivet att fungera bättre är algoritmen klar.
Varför grundläggande genomförbara lösningar är avgörande för att lösa komplexa tekniska problem
Fortfarande svårt att förstå? Låt mig ändra synvinkeln lite:
Vem behöver enkla, fungerande svar egentligen? Det är bara att samla ihop allt och hoppas på det bästa.
När allt kommer omkring, vem behöver optimering när kaos är så mycket roligare? Välkommen till en värld av icke-negativa variabler, där allt bara är ett förslag och misslyckande är nästan säkert.
Eller är det?
Låt oss utforska varför det till synes grundläggande konceptet med grundläggande genomförbara lösningar är allt annat än grundläggande och varför de bara kan vara nyckeln till att lösa även de mest komplexa tekniska problem.
Okej, det var bara ett skämt för att se ut som en tv-reklam.
Låt oss nu gå tillbaka till förklaringen.
Hitta grundläggande genomförbar lösning
En grundläggande genomförbar lösning (BFS) är en lösning på ett linjärt optimeringsproblem som uppfyller alla begränsningar och har det minsta antalet variabler som inte är noll.
Varje BFS är ett hörn av polyedern av möjliga lösningar ur geometrisk synvinkel.
Om det finns en bästa lösning måste det också finnas ett bästa första steg.
I den här artikeln kommer vi att prata om hur man hittar en grundläggande genomförbar lösning, hur man hittar alla grundläggande genomförbara lösningar och hur man hittar en grundläggande genomförbar lösning utan slackvariabler.
Att hitta en inledande grundläggande genomförbar lösning
Vi kan använda olika metoder, beroende på hur problemet är uppställt, för att hitta en initial grundlösning som fungerar för ett linjärt optimeringsproblem.
Ett sätt är att lägga till slack-variabler till begränsningarna för ojämlikheter och sätta alla andra variabler till noll.
Slackvariablerna blir grundvariablerna, och resten är icke-basvariabler.
Den tvåfasiga Simplex-metoden är ett annat sätt att lösa problemet.
Denna metod innebär att lösa ett extra linjärt programmeringsproblem för att hitta en initial grundläggande lösning som är genomförbar.
När en initial grundläggande genomförbar lösning har hittats, kan Simplex-metoden användas för att gå från en grundläggande genomförbar lösning till nästa och sedan till den bästa lösningen.
Hitta alla grundläggande möjliga lösningar
Det kan finnas mer än en grundläggande lösning som fungerar för ett linjärt program.
Vi kan ändra systemet genom att lägga till slackvariabler och sedan använda det nya systemet för att hitta alla grundläggande möjliga lösningar för ett linjärt program.
Sedan används dessa grundläggande genomförbara lösningar för att hitta de grundläggande genomförbara lösningarna för det ursprungliga problemet.
Att hitta en grundläggande genomförbar lösning utan slackvariabler
Vi måste använda slack-variabler för att bli av med mindre-än-begränsningarna så att vi kan hitta en grundläggande lösning som fungerar utan slack-variabler.
En slack-variabel är bara skillnaden mellan den högra sidan av en restriktion och den vänstra sidan.
Till exempel, för den första begränsningen, definierar vi en slackvariabel x4 = 14 - 2x1 - x2 - x3. När det gäller denna nya variabel är den första begränsningen helt enkelt ekvivalent med x4 ≥ 0, vilket är en positivitetsbegränsning för x4.
När vi adderar dessa slackvariabler får vi ett linjärt program som är detsamma som det ursprungliga, förutom att alla begränsningar är antingen ekvationer eller begränsningar som säger att något är positivt.
Uppsättningen av grundvariabler, som har andra värden än noll i grundlösningen, kallas bas.
Variabler som har värdet noll i grundlösningen är inte basvariabler.
För att hitta den bästa lösningen måste vi hitta en vektor x som uppfyller alla regler och får det största eller minsta värdet för målet.
Men att hitta den bästa lösningen tar fler steg än att bara hitta en lösning som fungerar och inte har några slackvariabler.
Det är inte alltid möjligt att hitta en grundläggande lösning utan slackvariabler, särskilt för problem med mindre begränsningar.
För att hitta en grundläggande genomförbar lösning måste du använda simplexmetoden eller en annan linjär programmeringsalgoritm för att leta efter en lösning som uppfyller alla begränsningar och som har minsta variabler som inte är noll.
Egenskaper och betydelse för grundläggande genomförbar lösning
Egenskaper för grundläggande genomförbar lösning
En grundläggande genomförbar lösning har högst m variabler som inte är noll och minst nm variabler som är noll, där n är antalet beslutsvariabler och m är antalet begränsningar.
En BFS är ett hörn av polyedern av möjliga lösningar, och varje BFS har n aktiva begränsningar som är linjärt oberoende.
Om det finns en bästa lösning måste det också finnas ett bästa första steg.
Det viktigaste med grundläggande genomförbara lösningar är att de är slutet på uppsättningen av konvexa lösningar för ett linjärt programmeringsproblem.
För att hitta det bästa svaret går simplexalgoritmen igenom en serie BFS:er.
Simplex-algoritmen söker igenom alla grundläggande möjliga lösningar på ett organiserat sätt för att hitta den bästa.
Betydelsen av grundläggande genomförbar lösning
Att hitta en grundläggande lösning som är möjlig är viktigt eftersom det hjälper till att hitta det bästa svaret på linjära programmeringsproblem.
Det ger också komplexa algoritmer en plats att börja och kan användas för att ta reda på om ett linjärt program är möjligt eller inte.
För att hitta alla grundläggande tänkbara lösningar för ett linjärt program kan du ändra systemet genom att lägga till slackvariabler och sedan använda det ändrade systemet för att hitta alla grundläggande tänkbara lösningar.
Sedan används dessa grundläggande genomförbara lösningar för att hitta de grundläggande genomförbara lösningarna för det ursprungliga problemet.
Video: Grundläggande genomförbara lösningar
Tips: Slå på bildtextknappen om du behöver den. Välj "automatisk översättning" i inställningsknappen om du inte är bekant med det talade språket. Du kan behöva klicka på språket för videon först innan ditt favoritspråk blir tillgängligt för översättning.
Användningsfall
| Använd i: | Beskrivning: |
|---|---|
| Resursfördelning: | BFS kan användas för att fördela begränsade resurser på flera projekt så att det mesta kan göras med minsta möjliga. Denna metod kan användas inom många olika områden, som transport, jordbruk och finans. |
| Optimering av nätverket: | BFS kan användas för att få kommunikations-, transport- och logistiknätverk att fungera bättre. BFS kan hjälpa till att hitta de bästa vägarna för varor och tjänster, skära ner på tid och pengar som spenderas på transporter och snabba upp och göra mer exakta leveranser. |
| Planering för produktion: | BFS kan användas för att planera produktionen så att resurser som arbetskraft, råvaror och utrustning används på bästa möjliga sätt för att få ut det mesta av dem. BFS kan hjälpa till att sänka produktionskostnaderna, minska avfallet och förbättra effektiviteten. |
| Finansiell planering: | I finansiell planering kan BFS användas för att optimera investeringsportföljer, minska risken och få mest pengar tillbaka. BFS kan hjälpa till att hitta det bästa sättet att dela upp tillgångar, sänka transaktionskostnaderna och tjäna mer pengar. |
| Hantering av leveranskedjan: | BFS kan användas för att förbättra flödet av varor och tjänster från leverantörer till kunder som en del av supply chain management. BFS kan hjälpa till att räkna ut den bästa mängden lager att ha till hands, förkorta ledtiderna och förbättra kundservicen. |
Slutsats
När denna titt på grundläggande genomförbara lösningar närmar sig sitt slut, är det tydligt att de är ett viktigt verktyg för alla ingenjörer eller ingenjörsstudenter.
Från att ta reda på det bästa sättet att bygga ett komplicerat system till att göra det bästa av de tillgängliga resurserna, grundläggande genomförbara lösningar ger ett ramverk för att få bästa möjliga resultat.
Men mer än att bara vara användbar, de visar hur elegant och vacker matematik kan vara.
Det är fantastiskt att du kan koka ner komplicerade problem till en enkel uppsättning ekvationer och sedan använda dessa ekvationer för att lösa problem i den verkliga världen.
Det är en bra påminnelse om att teknik handlar om att lösa problem, och att vi genom att använda matematikens kraft kan hitta svar som en gång ansågs vara omöjliga.
Så när du lär dig mer om teknik, kom ihåg vad du har lärt dig om enkla lösningar som fungerar och använder dem för att göra världen till en bättre och mer effektiv plats.
Länkar och referenser
Böcker:
- Linjär programmering: Grunder och tillägg
- Linjär programmering: teori och tillämpningar
Dela på…
