Hvis du er ingeniør eller ingeniørstuderende, ved du måske, hvad det vil sige at optimere.
For at få det bedst mulige resultat er det vigtigt at finde den bedste måde at gøre tingene på.
I lineær programmering kan du bruge en basisløsning til at finde den bedste løsning.
Men hvad er en grundlæggende løsning, og hvorfor er det så vigtigt for ingeniører at vide om dem? I denne artikel vil jeg tale om, hvad grundlæggende løsninger er, hvorfor de er vigtige i teknik, og hvordan de kan bruges til at få de bedste resultater i forskellige situationer.
Så spænd op og gør dig klar til at dykke ned i en verden af grundlæggende løsninger, hvor jeg nedbryder mysterierne og viser dig, hvor kraftfuld denne teknik kan være.
Grundlæggende løsninger i lineær programmering
Formel definition:
En løsning til en lineær programmodel bestående af m ligninger i n variable fås ved at løse for m variable i form af de resterende (nm) variable og sætte (nm) variablerne lig med nul.
En grundlæggende løsning i lineær programmering er en måde at løse et lineært programmeringsproblem, der opfylder visse tekniske krav.
Især en vektor x er en basisløsning for et polyeder, hvis vektorerne {ai : xi = 0} er lineært uafhængige.
Det betyder, at kolonnerne i A, der har variable xi, der ikke er nul, er lineært uafhængige.
En basisløsning med ikke-negative komponenter kaldes en grundlæggende gennemførlig løsning (BFS) (BFS).
En BFS opfylder alle de regler, der definerer et polyeder.
Hver BFS er et hjørne af polyederet af mulige løsninger fra et geometrisk synspunkt.
For at finde en grundlæggende løsning skal du sætte nm-variabler, der ikke er grundlæggende, til nul og løse de m-variable, der er grundlæggende.
Det er muligt for forskellige baser at føre til den samme grundlæggende løsning, hvilket betyder, at der kan være mere end én måde at løse det samme problem på.
Simplex-metoden er en iterativ proces, der flytter fra en BFS til den næste BFS, indtil den finder den bedste BFS.
Efter at have brugt simplex-metoden til at finde en BFS, kan vi se, om løsningen er den bedste, ved at se, om andre BFS'er i nærheden giver en bedre værdi for den objektive funktion.
Hvis der ikke er en sådan BFS, så er den nuværende BFS den bedste.
Lineær programmeringsmodel
En lineær programmeringsmodel involverer tre hovedkomponenter: beslutningsvariable, en objektiv funktion og begrænsninger.
Både objektivfunktionen og begrænsningerne skal være lineære funktioner, og beslutningsvariablerne skal være kontinuerte.
Objektivfunktionen bruges til enten at øge eller mindske et tal, der repræsenterer fortjeneste, omkostninger, antal fremstillede produkter osv.
Begrænsninger er grænser eller begrænsninger på den samlede mængde af en bestemt ressource, der er nødvendig for at udføre de opgaver, der vil bestemme niveauet af succes i beslutningsvariablerne.
Derudover kræver nogle lineære programmer, at alle beslutningsvariable er ikke-negative.
I lineære programmeringsmodeller kan du også bruge heltal og binære variable.
Binære variabler kan kun have en værdi på 0 eller 1, så de kan kun have en værdi på 0 eller 1.
Den simple metode
En af de mest brugte måder at løse lineære programmeringsproblemer på er Simplex-metoden.
Grundlæggende løsninger er vigtige i simplex-metoden, fordi de svarer til hjørnepunkterne i den mulige region, og simplex-metoden bevæger sig fra et hjørne til et andet, indtil en optimal løsning er fundet.
Simplex-metoden er en hurtig måde at finde det bedste svar på et lineært programmeringsproblem ved at bruge egenskaberne for grundlæggende løsninger.
For at bruge simpleksmetoden til at finde den bedste BFS, skal vi finde en basis B for begrænsningsmatricen A og løse systemet Ax = b med alle andre variable end basis sat til nul.
De resulterende værdier for de grundlæggende variable danner en BFS.
Hvis der findes en optimal løsning, så eksisterer der en optimal BFS.
Simplex-metoden flytter fra én BFS til en tilstødende BFS, indtil den når en optimal BFS ved at bruge pivotprocedurer.
Sammenligning mellem basisløsninger og gennemførlige løsninger
Forskellen mellem en basisløsning og en gennemførlig løsning er, at en basisløsning ikke behøver at opfylde nogen betingelser.
Især skal den have vektorer, der er lineært uafhængige og har værdier, der ikke er nul for xi, og x skal være mindre end 0.
På den anden side er en gennemførlig løsning ethvert punkt, der passer inden for problemets grænser.
Men ikke alle mulige løsninger er grundlæggende gennemførlige løsninger.
Grundlæggende mulige løsninger (BFS'er) er kun dem, der matcher hjørnerne af polyederen af mulige løsninger.
Tilbage til det grundlæggende: Frigør kraften ved grundlæggende løsninger inden for teknik
Stadig svært at forstå? Lad mig ændre synspunktet lidt:
Er du træt af at bruge komplicerede metoder og algoritmer til at løse svære problemer? Ønsker du, at der var en enklere og mere ligetil måde at håndtere dine lineære programmodelproblemer på?
Nå, bare rolig, for svaret er her: løs for m variable i form af de resterende (nm) variable, og sæt (nm) variablerne til nul.
Hvem har brug for algoritmer, der lyder fancy, når du kan gå tilbage til det grundlæggende? Så læg dine lommeregnere væk, og lad os begynde at lære om simple løsninger.
Okay, det var bare en joke lavet til at ligne en tv-reklame.
Lad os nu gå tilbage til forklaringen.
Grundlæggende løsning Lineær programmering
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: | Basisløsning kan bruges i ressourceallokeringsproblemer, hvor målet er at fordele begrænsede ressourcer mellem konkurrerende behov. For eksempel kan en virksomhed være nødt til at dele sit budget mellem forskellige afdelinger eller projekter. Ved at bruge grundlæggende løsninger kan de finde ud af den bedste måde at bruge deres ressourcer til at tjene flest penge eller bruge så lidt som muligt. |
| Planlægning af produktion: | I produktionsplanlægning kan den grundlæggende løsning bruges til at finde ud af den bedste blanding af produkter at lave for at tjene flest penge. Virksomheder kan finde det bedste produktionsmix, der indbringer flest penge og koster mindst ved at bruge basisløsningen. |
| Planlægning: | Grundlæggende løsning kan bruges til at finde ud af, hvordan man planlægger opgaver eller job, så de kan udføres på den mest effektive måde. For eksempel kan en virksomhed være nødt til at planlægge sine ansattes arbejdstid for at sikre, at de har nok medarbejdere, når virksomheden er travl. Ved at bruge en grundlæggende løsning kan de finde ud af den bedste måde at planlægge tingene på, så der er så lidt nedetid som muligt, og så meget arbejde bliver gjort som muligt. |
| Ledelse af forsyningskæden: | I supply chain management er målet at sikre, at varer og tjenester bevæger sig så gnidningsløst som muligt fra leverandøren til kunden. For eksempel kan en virksomhed have brug for at finde ud af de bedste ruter til transport af varer, så omkostningerne holdes på et minimum, og varerne leveres til tiden. Ved at bruge basisløsninger kan de finde den bedste plan for styring af forsyningskæden, der holder omkostningerne lave og holder kunderne glade. |
| Porteføljeoptimering: | I porteføljeoptimering, hvor målet er at finde den bedste blanding af investeringer for at tjene flest penge og samtidig tage mindst risiko, kan basisløsninger bruges. For eksempel kan et investeringsselskab være nødt til at finde ud af den bedste blanding af aktier, obligationer og andre værdipapirer for at hjælpe deres kunder med at nå deres investeringsmål. Ved at bruge en simpel løsning kan de finde den bedste måde at blande deres porteføljer på, så de får det bedste afkast, mens de tager den mindste risiko. |
Konklusion
Afslutningsvis er ideen om en grundlæggende løsning meget vigtig inden for ingeniørområdet og kan bruges på mange forskellige måder.
Ved at vide, hvad en grundlæggende løsning er, og hvad den gør i lineær programmering, kan vi forbedre løsninger, reducere omkostningerne og gøre dem mere effektive.
Men det er vigtigt at huske, at den grundlæggende løsning ikke er en løsning, der passer til alle, selvom den er et kraftfuldt værktøj.
For at få de bedste resultater skal hvert problem ses nøje på og tænkes over.
Som ingeniører er vi nødt til at blive ved med at se på, hvordan grundlæggende løsninger og andre optimeringsteknikker kan hjælpe os med at gøre fremskridt og komme med nye ideer.
Så lad os erkende kraften i simple løsninger og blive ved med at skubbe grænserne for, hvad der er muligt ved at bruge nye teknikker og strategier.
Links og referencer
Bøger:
- Lineær programmering af Vasek Chvatal
- Modellering og løsning af lineær programmering med R af Jose M. Sallan
Del på…
