Du ved, hvad det vil sige at optimere et system for at få det bedst mulige resultat, hvis du er ingeniørstuderende eller ingeniør.
At optimere en løsning er nøglen til succes i alt fra at bygge broer til at lave software.
Ideen om en grundlæggende gennemførlig løsning kommer ind på dette tidspunkt.
Det er en grundlæggende idé i lineær programmering, der lader dig finde ud af, hvilken af et sæt mulige løsninger der er den bedste.
Men hvorfor betyder det så meget? I denne artikel vil jeg tale om grundlæggende gennemførlige løsninger, og hvordan de kan bruges til at løse tekniske problemer i den virkelige verden.
Jeg vil tale om, hvordan man finder dem, hvad de er lavet af, og hvorfor de er vigtige.
Så uanset om du er en erfaren ingeniør eller en studerende, der lige er begyndt, så kom med os, mens jeg dykker ned i en verden af grundlæggende gennemførlige løsninger og viser dig, hvordan du bruger kraften ved lineær programmering.
Forståelse af grundlæggende gennemførlig løsning
Formel definition:
En grundlæggende løsning til en lineær programmodel, hvor alle variablerne er ikke-negative.
En grundlæggende gennemførlig løsning (BFS) er en nøgleidé i lineær programmering, der hjælper med at finde de bedste løsninger.
En BFS er en løsning med det mindst mulige antal ikke-nul variable.
Det er et hjørne af polyederet af mulige løsninger.
Med andre ord er en BFS en grundlæggende løsning, der opfylder de ikke-negative begrænsninger og er i den mulige region eller problemområde.
At finde en optimal grundlæggende gennemførlig løsning
For at finde den bedste BFS skal vi gøre følgende:
- Skriv programmet i standardform for en lineær sekvens.
- Gør systemet af uligheder til en udvidet matrix.
- Find ud af, hvilke variabler der er grundlæggende, og hvilke der ikke er.
- Find ud af, hvad de grundlæggende variable er i forhold til de andre variable.
- Sæt disse udtryk i objektivfunktionen for kun at få en funktion af de variable, der ikke er grundlæggende.
- Find en ikke-grundlæggende variabel, der kan øges uden at bryde nogen begrænsninger, og som vil få objektivet til at fungere bedre.
Denne variabel er nu en grundvariabel, og en af de andre grundvariable er ikke længere en grundvariabel.
Hvis der er en optimal løsning, skal den være i en af enderne eller hjørnerne af den region, hvor løsninger er mulige.
Så hvis en LP har en optimal løsning, har den en optimal løsning på et ekstremt punkt af det mulige sæt.
Der er også altid en optimal BFS, hvis der er en optimal løsning.
Brug af den simple metode til at finde en optimal BFS
Simplex-metoden er en algoritme til løsning af problemer i lineær programmering.
Den flytter fra en BFS til en "tilstødende" BFS ved at bruge pivotproceduren.
I pivotproceduren vælges en ikke-grundvariabel til at blive en grundvariabel, og derefter bruges den nuværende BFS til at løse de nye grundvariable.
Når ingen ikke-grundlæggende variabel kan ændres for at få objektivet til at fungere bedre, er algoritmen færdig.
Hvorfor grundlæggende gennemførlige løsninger er afgørende for at løse komplekse tekniske problemer
Stadig svært at forstå? Lad mig ændre synspunktet lidt:
Hvem har overhovedet brug for enkle, brugbare svar? Bare smid det hele sammen og håb på det bedste.
Når alt kommer til alt, hvem har brug for optimering, når kaos er så meget sjovere? Velkommen til en verden af ikke-negative variabler, hvor alt kun er et forslag, og fiasko er næsten sikker.
Eller er det?
Lad os undersøge, hvorfor det tilsyneladende grundlæggende koncept med grundlæggende gennemførlige løsninger er alt andet end grundlæggende, og hvorfor de måske bare er nøglen til at løse selv de mest komplekse tekniske problemer.
Okay, det var bare en joke lavet til at ligne en tv-reklame.
Lad os nu gå tilbage til forklaringen.
At finde grundlæggende gennemførlig løsning
En grundlæggende gennemførlig løsning (BFS) er en løsning på et lineært optimeringsproblem, der opfylder alle begrænsninger og har det færreste antal variabler, der ikke er nul.
Hver BFS er et hjørne af polyederet af mulige løsninger fra et geometrisk synspunkt.
Hvis der er en bedste løsning, skal der også være et bedste første skridt.
I denne artikel vil vi tale om, hvordan man finder en indledende grundlæggende gennemførlig løsning, hvordan man finder alle grundlæggende gennemførlige løsninger, og hvordan man finder en grundlæggende gennemførlig løsning uden slappe variable.
At finde en indledende grundlæggende gennemførlig løsning
Vi kan bruge forskellige metoder, afhængig af hvordan problemet er sat op, til at finde en indledende grundlæggende løsning, der virker til et lineært optimeringsproblem.
En måde er at tilføje slack variabler til begrænsningerne på uligheder og sætte alle de andre variable til nul.
Slack-variablene bliver de grundlæggende variable, og resten er ikke-basale variable.
Den tofasede simpleksmetode er en anden måde at løse problemet på.
Denne metode involverer løsning af et ekstra lineært programmeringsproblem for at finde en indledende grundlæggende løsning, der er gennemførlig.
Når en indledende, grundlæggende gennemførlig løsning er fundet, kan Simplex-metoden bruges til at flytte fra en grundlæggende gennemførlig løsning til den næste og derefter til den bedste løsning.
At finde alle grundlæggende mulige løsninger
Der kan være mere end én grundlæggende løsning, der fungerer for et lineært program.
Vi kan ændre systemet ved at tilføje slack-variabler og derefter bruge det nye system til at finde alle basale mulige løsninger til et lineært program.
Derefter bruges disse grundlæggende gennemførlige løsninger til at finde de grundlæggende gennemførlige løsninger til det oprindelige problem.
At finde en grundlæggende gennemførlig løsning uden slappe variable
Vi skal bruge slack-variabler for at slippe af med mindre-end-begrænsningerne, så vi kan finde en grundlæggende løsning, der fungerer uden slack-variabler.
En slack variabel er blot forskellen mellem højre side af en begrænsning og venstre side.
For eksempel, for den første begrænsning, definerer vi en slack-variabel x4 = 14 - 2x1 - x2 - x3. Med hensyn til denne nye variabel svarer den første begrænsning blot til x4 ≥ 0, hvilket er en positivitetsbegrænsning for x4.
Når vi tilføjer disse slack-variabler, får vi et lineært program, der er det samme som det originale, bortset fra at alle begrænsningerne enten er ligninger eller begrænsninger, der siger, at noget er positivt.
Sættet af grundvariable, som har andre værdier end nul i basisløsningen, kaldes basis.
Variabler, der har en værdi på nul i basisløsningen, er ikke grundvariable.
For at finde den bedste løsning skal vi finde en vektor x, der opfylder alle reglerne og får den største eller mindste værdi for målet.
Men at finde den bedste løsning tager flere skridt end blot at finde en løsning, der virker og ikke har nogen slappe variable.
Det er ikke altid muligt at finde en grundlæggende løsning uden slack variabler, især for problemer med mindre end begrænsninger.
For at finde en grundlæggende gennemførlig løsning skal du bruge simplex-metoden eller en anden lineær programmeringsalgoritme til at lede efter en løsning, der opfylder alle begrænsninger og har færrest variable, der ikke er nul.
Egenskaber og betydning af grundlæggende gennemførlig løsning
Egenskaber for grundlæggende mulig løsning
En grundlæggende gennemførlig løsning har højst m variable, der ikke er nul og mindst nm variable, der er nul, hvor n er antallet af beslutningsvariable og m er antallet af begrænsninger.
En BFS er et hjørne af polyederen af mulige løsninger, og hver BFS har n aktive begrænsninger, der er lineært uafhængige.
Hvis der er en bedste løsning, skal der også være et bedste første skridt.
Det vigtigste ved grundlæggende gennemførlige løsninger er, at de er enden af sættet af konvekse løsninger til et lineært programmeringsproblem.
For at finde det bedste svar gennemgår simpleksalgoritmen en række BFS'er.
Simplex-algoritmen søger gennem alle de grundlæggende mulige løsninger på en organiseret måde for at finde den bedste.
Betydningen af grundlæggende gennemførlig løsning
At finde en grundlæggende løsning, der er mulig, er vigtig, fordi den hjælper med at finde det bedste svar på lineære programmeringsproblemer.
Det giver også komplekse algoritmer et sted at starte og kan bruges til at finde ud af, om et lineært program er muligt eller ej.
For at finde alle grundlæggende mulige løsninger til et lineært program, kan du ændre systemet ved at tilføje slack-variabler og derefter bruge det ændrede system til at finde alle grundlæggende gennemførlige løsninger.
Derefter bruges disse grundlæggende gennemførlige løsninger til at finde de grundlæggende gennemførlige løsninger til det oprindelige problem.
Video: Grundlæggende mulige løsninger
Tip: Slå billedtekstknappen til, hvis du har brug for det. Vælg "automatisk oversættelse" i indstillingsknappen, hvis du ikke er fortrolig med det talte sprog. Du skal muligvis først klikke på sproget for videoen, før dit yndlingssprog bliver tilgængeligt til oversættelse.
Brug cases
| Brugt i: | Beskrivelse: |
|---|---|
| Tildeling af ressourcer: | BFS kan bruges til at fordele begrænsede ressourcer på flere projekter, så der kan opnås mest muligt med mindst muligt. Denne metode kan bruges på mange forskellige områder, såsom transport, landbrug og finans. |
| Optimering af netværket: | BFS kan bruges til at få kommunikations-, transport- og logistiknetværk til at fungere bedre. BFS kan hjælpe med at finde de bedste ruter for varer og tjenester, skære ned på tid og penge brugt på transport og fremskynde og lave mere præcise leveringer. |
| Planlægning af produktion: | BFS kan bruges til at planlægge produktionen, så ressourcer som arbejdskraft, råmaterialer og udstyr bruges bedst muligt for at få mest muligt ud af dem. BFS kan hjælpe med at sænke produktionsomkostningerne, skære ned på spild og forbedre effektiviteten. |
| Finansiel planlægning: | I finansiel planlægning kan BFS bruges til at optimere investeringsporteføljer, sænke risikoen og få flest penge tilbage. BFS kan hjælpe med at finde den bedste måde at opdele aktiver på, sænke transaktionsomkostninger og tjene flere penge. |
| Ledelse af forsyningskæden: | BFS kan bruges til at forbedre flowet af varer og tjenester fra leverandører til kunder som en del af supply chain management. BFS kan hjælpe med at finde ud af den bedste mængde lager at have ved hånden, forkorte leveringstider og forbedre kundeservicen. |
Konklusion
Da dette kig på grundlæggende gennemførlige løsninger nærmer sig en afslutning, er det klart, at de er et vigtigt værktøj for enhver ingeniør eller ingeniørstuderende.
Fra at finde ud af den bedste måde at bygge et kompliceret system på til at få mest muligt ud af de tilgængelige ressourcer, giver grundlæggende gennemførlige løsninger en ramme for at få det bedst mulige resultat.
Men mere end blot at være nyttige, viser de, hvor elegant og smuk matematik kan være.
Det er forbløffende, at du kan koge komplicerede problemer ned til et simpelt sæt ligninger og derefter bruge disse ligninger til at løse problemer i den virkelige verden.
Det er en god påmindelse om, at teknik handler om at løse problemer, og at vi ved at bruge matematikkens kraft kan finde svar, som man engang troede var umulige.
Så når du lærer mere om teknik, skal du huske på, hvad du har lært om simple løsninger, der virker, og bruge dem til at gøre verden til et bedre og mere effektivt sted.
Links og referencer
Bøger:
- Lineær programmering: fundamenter og udvidelser
- Lineær programmering: teori og anvendelser
Del på…
