Hvis du er ingeniør eller ingeniørstudent, vet du kanskje hva det vil si å optimalisere.
For å få et best mulig resultat er det viktig å finne den beste måten å gjøre ting på.
I lineær programmering kan du bruke en grunnleggende løsning for å finne den beste løsningen.
Men hva er en grunnleggende løsning, og hvorfor er det så viktig for ingeniører å vite om dem? I denne artikkelen skal jeg snakke om hva grunnleggende løsninger er, hvorfor de er viktige i ingeniørfag, og hvordan de kan brukes for å få de beste resultatene i ulike situasjoner.
Så spenn deg fast og gjør deg klar til å dykke inn i verden av grunnleggende løsninger, hvor jeg skal bryte ned mysteriene og vise deg hvor kraftig denne teknikken kan være.
Grunnleggende løsninger innen lineær programmering
Formell definisjon:
En løsning på en lineær programmodell bestående av m likninger i n variabler oppnås ved å løse for m variabler i form av de resterende (nm) variablene og sette (nm) variablene lik null.
En grunnleggende løsning innen lineær programmering er en måte å løse et lineært programmeringsproblem som oppfyller visse tekniske krav.
Spesielt er en vektor x en grunnleggende løsning for et polyeder hvis vektorene {ai : xi = 0} er lineært uavhengige.
Dette betyr at kolonnene til A som har variabler xi som ikke er null er lineært uavhengige.
En grunnleggende løsning med ikke-negative komponenter kalles en grunnleggende gjennomførbar løsning (BFS) (BFS).
En BFS oppfyller alle reglene som definerer et polyeder.
Hver BFS er et hjørne av polyederet av gjennomførbare løsninger fra et geometrisk synspunkt.
For å finne en grunnleggende løsning må du sette nm-variabler som ikke er grunnleggende til null og løse de m-variablene som er grunnleggende.
Det er mulig for ulike grunnlag å føre til samme grunnleggende løsning, noe som betyr at det kan være mer enn én måte å løse samme problem på.
Simplex-metoden er en iterativ prosess som går fra en BFS til den neste BFS til den finner den beste BFS.
Etter å ha brukt simpleksmetoden for å finne en BFS, kan vi se om løsningen er den beste ved å se om noen andre BFS-er i nærheten gir en bedre verdi for objektivfunksjonen.
Hvis det ikke finnes en slik BFS, er den nåværende BFS den beste.
Lineær programmeringsmodell
En lineær programmeringsmodell involverer tre hovedkomponenter: beslutningsvariabler, en objektiv funksjon og begrensninger.
Både objektivfunksjonen og begrensningene må være lineære funksjoner, og beslutningsvariablene må være kontinuerlige.
Objektivfunksjonen brukes til å enten øke eller redusere et tall som representerer fortjeneste, kostnad, antall produserte produkter osv.
Begrensninger er begrensninger eller begrensninger på den totale mengden av en viss ressurs som er nødvendig for å utføre oppgavene som vil avgjøre suksessnivået i beslutningsvariablene.
I tillegg krever noen lineære programmer at alle beslutningsvariabler er ikke-negative.
I lineære programmeringsmodeller kan du også bruke heltalls- og binære variabler.
Binære variabler kan bare ha en verdi på 0 eller 1, så de kan bare ha en verdi på 0 eller 1.
Den enkle metoden
En av de mest brukte måtene å løse lineære programmeringsproblemer på er Simplex-metoden.
Grunnløsninger er viktige i simpleksmetoden fordi de tilsvarer hjørnepunktene i det mulige området, og simpleksmetoden beveger seg fra et hjørne til et annet til en optimal løsning er funnet.
Simplexmetoden er en rask måte å finne det beste svaret på et lineært programmeringsproblem ved å bruke egenskapene til grunnleggende løsninger.
For å bruke simpleksmetoden for å finne den beste BFS, må vi finne en basis B for begrensningsmatrisen A og løse systemet Ax = b med alle andre variabler enn basisen satt til null.
De resulterende verdiene for de grunnleggende variablene danner en BFS.
Hvis det finnes en optimal løsning, så eksisterer det en optimal BFS.
Simplex-metoden flyttes fra en BFS til en tilstøtende BFS til den når en optimal BFS ved å bruke pivotprosedyrer.
Sammenligning mellom grunnleggende løsninger og gjennomførbare løsninger
Forskjellen mellom en basisløsning og en gjennomførbar løsning er at en basisløsning ikke trenger å oppfylle noen betingelser.
Spesielt må den ha vektorer som er lineært uavhengige og har verdier som ikke er null for xi, og x må være mindre enn 0.
På den annen side er en gjennomførbar løsning ethvert punkt som passer innenfor problemets grenser.
Men ikke alle gjennomførbare løsninger er grunnleggende gjennomførbare løsninger.
Grunnleggende gjennomførbare løsninger (BFS) er bare de som samsvarer med hjørnene på polyederet til mulige løsninger.
Tilbake til det grunnleggende: Lås opp kraften til grunnleggende løsninger innen ingeniørfag
Fortsatt vanskelig å forstå? La meg endre synspunktet litt:
Er du lei av å bruke kompliserte metoder og algoritmer for å løse vanskelige problemer? Skulle du ønske det fantes en enklere og mer grei måte å håndtere problemene med lineære programmodeller på?
Vel, ikke bekymre deg, for svaret er her: løs for m variabler i form av de gjenværende (nm) variablene, og sett (nm) variablene til null.
Hvem trenger algoritmer som høres fancy ut når du kan gå tilbake til det grunnleggende? Så legg bort kalkulatorene og la oss begynne å lære om enkle løsninger.
Ok, det var bare en spøk laget for å se ut som en TV-reklame.
La oss nå gå tilbake til forklaringen.
Grunnleggende løsning Lineær programmering
Tips: Slå på bildetekstknappen hvis du trenger det. Velg "automatisk oversettelse" i innstillingsknappen hvis du ikke er kjent med talespråket. Du må kanskje klikke på språket til videoen først før favorittspråket ditt blir tilgjengelig for oversettelse.
Brukssaker
| Brukt i: | Beskrivelse: |
|---|---|
| Tildeling av ressurser: | Grunnløsning kan brukes i ressursallokeringsproblemer, hvor målet er å dele begrensede ressurser mellom konkurrerende behov. For eksempel kan et selskap trenge å dele budsjettet mellom ulike avdelinger eller prosjekter. Ved å bruke grunnleggende løsninger kan de finne ut den beste måten å bruke ressursene sine på for å tjene mest mulig penger eller bruke så lite som mulig. |
| Planlegging for produksjon: | I produksjonsplanlegging kan den grunnleggende løsningen brukes til å finne ut den beste blandingen av produkter å lage for å tjene mest mulig penger. Bedrifter kan finne den beste produksjonsmiksen som gir mest penger og koster minst ved å bruke basisløsningen. |
| Planlegging: | Grunnleggende løsning kan brukes til å finne ut hvordan du planlegger oppgaver eller jobber slik at de kan gjøres på den mest effektive måten. For eksempel kan et selskap trenge å planlegge arbeidstiden til de ansatte for å sikre at de har nok arbeidere når virksomheten er travel. Ved å bruke en grunnleggende løsning kan de finne ut den beste måten å planlegge ting på, slik at det er minst mulig nedetid og så mye arbeid som mulig. |
| Ledelse av forsyningskjeden: | I supply chain management er målet å sørge for at varer og tjenester beveger seg så smidig som mulig fra leverandør til kunde. For eksempel kan en bedrift trenge å finne de beste rutene for transport av varer, slik at kostnadene holdes på et minimum og varene leveres i tide. Ved å bruke grunnleggende løsninger kan de finne den beste planen for å administrere forsyningskjeden som holder kostnadene lave og holder kundene fornøyde. |
| Porteføljeoptimalisering: | I porteføljeoptimalisering, hvor målet er å finne den beste blandingen av investeringer for å tjene mest mulig penger og samtidig ta minst risiko, kan grunnleggende løsninger brukes. For eksempel kan et investeringsselskap trenge å finne den beste blandingen av aksjer, obligasjoner og andre verdipapirer for å hjelpe kundene sine med å nå investeringsmålene sine. Ved å bruke en enkel løsning kan de finne den beste måten å blande porteføljene sine slik at de får best mulig avkastning samtidig som de tar minst mulig risiko. |
Konklusjon
Avslutningsvis er ideen om en grunnleggende løsning svært viktig innen ingeniørfaget og kan brukes på mange forskjellige måter.
Ved å vite hva en grunnleggende løsning er og hva den gjør i lineær programmering, kan vi forbedre løsninger, kutte kostnader og gjøre dem mer effektive.
Men det er viktig å huske at grunnleggende løsning ikke er en løsning som passer alle, selv om den er et kraftig verktøy.
For å få de beste resultatene, må hvert problem ses nøye på og tenkes over.
Som ingeniører må vi fortsette å se på hvordan grunnleggende løsninger og andre optimaliseringsteknikker kan hjelpe oss å gjøre fremskritt og komme opp med nye ideer.
Så la oss gjenkjenne kraften i enkle løsninger og fortsette å presse grensene for hva som er mulig ved å bruke nye teknikker og strategier.
Lenker og referanser
Bøker:
- Lineær programmering av Vasek Chvatal
- Modellering og løsning av lineær programmering med R av Jose M. Sallan
Dele på…
