Om du är ingenjör eller ingenjörsstudent vet du kanske vad det innebär att optimera.
För att få bästa möjliga resultat är det viktigt att hitta det bästa sättet att göra saker på.
I linjär programmering kan du använda en baslösning för att hitta den bästa lösningen.
Men vad är en grundläggande lösning, och varför är det så viktigt för ingenjörer att känna till dem? I den här artikeln kommer jag att prata om vad grundläggande lösningar är, varför de är viktiga inom teknik och hur de kan användas för att få bästa resultat i olika situationer.
Så spänn fast dig och gör dig redo att dyka in i en värld av grundläggande lösningar, där jag ska bryta ner mysterierna och visa dig hur kraftfull denna teknik kan vara.
Grundläggande lösningar inom linjär programmering
Formell definition:
En lösning till en linjär programmodell bestående av mekvationer i n variabler erhålls genom att lösa för m variabler i termer av de återstående (nm) variablerna och sätta (nm) variablerna lika med noll.
En grundläggande lösning inom linjär programmering är ett sätt att lösa ett linjärt programmeringsproblem som uppfyller vissa tekniska krav.
Speciellt är en vektor x en grundläggande lösning för en polyeder om vektorerna {ai : xi = 0} är linjärt oberoende.
Det betyder att kolumnerna i A som har variabler xi som inte är noll är linjärt oberoende.
En grundläggande lösning med icke-negativa komponenter kallas en grundläggande genomförbar lösning (BFS) (BFS).
En BFS uppfyller alla regler som definierar en polyeder.
Varje BFS är ett hörn av polyedern av möjliga lösningar ur geometrisk synvinkel.
För att hitta en grundläggande lösning måste du ställa in nm-variabler som inte är grundläggande till noll och lösa de m-variabler som är grundläggande.
Det är möjligt för olika grunder att leda till samma grundläggande lösning, vilket gör att det kan finnas mer än ett sätt att lösa samma problem.
Simplex-metoden är en iterativ process som går från en BFS till nästa BFS tills den hittar den bästa BFS.
Efter att ha använt simplexmetoden för att hitta en BFS kan vi se om lösningen är den bästa genom att se om någon annan BFS i närheten ger ett bättre värde för objektivfunktionen.
Om det inte finns någon sådan BFS är den nuvarande BFS den bästa.
Linjär programmeringsmodell
En linjär programmeringsmodell innefattar tre huvudkomponenter: beslutsvariabler, en objektiv funktion och begränsningar.
Både objektivfunktionen och begränsningarna måste vara linjära funktioner, och beslutsvariablerna måste vara kontinuerliga.
Objektivfunktionen används för att antingen öka eller minska ett tal som representerar vinst, kostnad, antal tillverkade produkter, etc.
Restriktioner är gränser eller restriktioner för den totala mängden av en viss resurs som behövs för att utföra de uppgifter som kommer att avgöra graden av framgång i beslutsvariablerna.
Dessutom kräver vissa linjära program att alla beslutsvariabler är icke-negativa.
I linjära programmeringsmodeller kan du även använda heltal och binära variabler.
Binära variabler kan bara ha värdet 0 eller 1, så de kan bara ha värdet 0 eller 1.
Den enkla metoden
Ett av de mest använda sätten att lösa linjära programmeringsproblem är Simplex-metoden.
Grundlösningar är viktiga i simplexmetoden eftersom de motsvarar hörnpunkterna i det möjliga området, och simplexmetoden flyttas från ett hörn till ett annat tills en optimal lösning hittas.
Simplexmetoden är ett snabbt sätt att hitta det bästa svaret på ett linjärt programmeringsproblem genom att använda egenskaperna hos grundläggande lösningar.
För att använda simplexmetoden för att hitta bästa BFS måste vi hitta en bas B för begränsningsmatrisen A och lösa systemet Ax = b med alla andra variabler än basen satta till noll.
De resulterande värdena för de grundläggande variablerna bildar en BFS.
Om det finns en optimal lösning, så finns det en optimal BFS.
Simplex-metoden flyttas från en BFS till en angränsande BFS tills den når en optimal BFS genom att använda pivotprocedurer.
Jämförelse mellan Basic Solutions och Feasible Solutions
Skillnaden mellan en baslösning och en genomförbar lösning är att en baslösning inte behöver uppfylla några villkor.
I synnerhet måste den ha vektorer som är linjärt oberoende och har värden som inte är noll för xi, och x måste vara mindre än 0.
Å andra sidan är en genomförbar lösning vilken punkt som helst som ligger inom gränserna för problemet.
Men inte alla genomförbara lösningar är grundläggande genomförbara lösningar.
Grundläggande genomförbara lösningar (BFS) är bara de som matchar hörnen av polyedern av genomförbara lösningar.
Tillbaka till grunderna: Lås upp kraften hos grundläggande lösningar inom teknik
Fortfarande svårt att förstå? Låt mig ändra synvinkeln lite:
Är du trött på att använda komplicerade metoder och algoritmer för att lösa svåra problem? Önskar du att det fanns ett enklare och mer okomplicerat sätt att hantera dina linjära programmodellproblem?
Tja, oroa dig inte, eftersom svaret är här: lös för m variabler i termer av de återstående (nm) variablerna, och ställ in (nm) variablerna till noll.
Vem behöver algoritmer som låter snygga när du kan gå tillbaka till grunderna? Så lägg undan dina miniräknare och låt oss börja lära oss om enkla lösningar.
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.
Grundläggande lösning Linjär programmering
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: | Grundlösning kan användas vid resursallokeringsproblem, där målet är att dela upp begränsade resurser mellan konkurrerande behov. Ett företag kan till exempel behöva dela upp sin budget mellan olika avdelningar eller projekt. Genom att använda grundläggande lösningar kan de komma på det bästa sättet att använda sina resurser för att tjäna så mycket pengar som möjligt eller spendera så lite som möjligt. |
| Planering för produktion: | I produktionsplanering kan den grundläggande lösningen användas för att ta reda på den bästa mixen av produkter att göra för att tjäna mest pengar. Företag kan hitta den bästa produktionsmixen som ger mest pengar och kostar minst genom att använda grundlösningen. |
| Schemaläggning: | Grundläggande lösning kan användas för att ta reda på hur man schemalägger uppgifter eller jobb så att de kan utföras på det mest effektiva sättet. Till exempel kan ett företag behöva planera sina anställdas arbetstider för att se till att de har tillräckligt med anställda när verksamheten är upptagen. Genom att använda en grundläggande lösning kan de komma på det bästa sättet att schemalägga saker så att det blir så lite stillestånd som möjligt och så mycket arbete som blir gjort som möjligt. |
| Hantering av leveranskedjan: | Inom supply chain management är målet att se till att varor och tjänster rör sig så smidigt som möjligt från leverantör till kund. Till exempel kan ett företag behöva ta reda på de bästa vägarna för att transportera varor så att kostnaderna hålls till ett minimum och varor levereras i tid. Genom att använda grundläggande lösningar kan de hitta den bästa planen för att hantera leveranskedjan som håller kostnaderna låga och håller kunderna nöjda. |
| Portföljoptimering: | Inom portföljoptimering, där målet är att hitta den bästa mixen av investeringar för att tjäna mest pengar samtidigt som man tar minsta risker, kan grundläggande lösningar användas. Till exempel kan ett värdepappersföretag behöva ta reda på den bästa mixen av aktier, obligationer och andra värdepapper för att hjälpa sina kunder att nå sina investeringsmål. Genom att använda en enkel lösning kan de hitta det bästa sättet att blanda sina portföljer så att de får den bästa avkastningen samtidigt som de tar minsta möjliga risk. |
Slutsats
Sammanfattningsvis är idén om en grundläggande lösning mycket viktig inom teknikområdet och kan användas på många olika sätt.
Genom att veta vad en grundläggande lösning är och vad den gör inom linjär programmering kan vi förbättra lösningar, sänka kostnader och göra dem mer effektiva.
Men det är viktigt att komma ihåg att den grundläggande lösningen inte är en lösning som passar alla, även om det är ett kraftfullt verktyg.
För att få bästa resultat måste varje problem granskas noggrant och övervägas.
Som ingenjörer måste vi fortsätta undersöka hur grundläggande lösningar och andra optimeringstekniker kan hjälpa oss att göra framsteg och komma med nya idéer.
Så låt oss inse kraften i enkla lösningar och fortsätta att tänja på gränserna för vad som är möjligt genom att använda nya tekniker och strategier.
Länkar och referenser
Böcker:
- Linjär programmering av Vasek Chvatal
- Modellering och lösning av linjär programmering med R av Jose M. Sallan
Dela på…
