Du vet hva det vil si å optimalisere et system for å få best mulig resultat hvis du er ingeniørstudent eller ingeniør.
Å optimalisere en løsning er nøkkelen til suksess i alt fra å bygge broer til å lage programvare.
Ideen om en grunnleggende gjennomførbar løsning kommer inn på dette punktet.
Det er en grunnleggende idé innen lineær programmering som lar deg finne ut hvilken av et sett med mulige løsninger som er best.
Men hvorfor betyr det så mye? I denne artikkelen vil jeg snakke om grunnleggende gjennomførbare løsninger og hvordan de kan brukes til å løse tekniske problemer i den virkelige verden.
Jeg skal snakke om hvordan du finner dem, hva de er laget av og hvorfor de er viktige.
Så, enten du er en erfaren ingeniør eller en student som nettopp har begynt, kom med oss mens jeg dykker inn i verden av grunnleggende gjennomførbare løsninger og viser deg hvordan du kan bruke kraften til lineær programmering.
Forstå grunnleggende gjennomførbar løsning
Formell definisjon:
En grunnleggende løsning på en lineær programmodell der alle variablene er ikke-negative.
En grunnleggende gjennomførbar løsning (BFS) er en nøkkelide i lineær programmering som hjelper til med å finne de beste løsningene.
En BFS er en løsning med minst mulig antall ikke-null variabler.
Det er et hjørne av polyederet av gjennomførbare løsninger.
Med andre ord er en BFS en grunnleggende løsning som oppfyller de ikke-negative begrensningene og er i den gjennomførbare regionen eller problemområdet.
Finne en optimal grunnleggende gjennomførbar løsning
For å finne den beste BFS, må vi gjøre følgende:
- Skriv programmet i standardform for en lineær sekvens.
- Gjør systemet av ulikheter til en utvidet matrise.
- Finn ut hvilke variabler som er grunnleggende og hvilke som ikke er det.
- Finn ut hva de grunnleggende variablene er når det gjelder de andre variablene.
- Sett disse uttrykkene inn i objektivfunksjonen for å få en funksjon av bare variablene som ikke er grunnleggende.
- Finn en ikke-grunnleggende variabel som kan økes uten å bryte noen begrensninger og som vil få objektivet til å fungere bedre.
Denne variabelen er nå en grunnvariabel, og en av de andre grunnvariablene er ikke lenger en grunnvariabel.
Hvis det finnes en optimal løsning, må den være i en av endene, eller toppunktene, av regionen hvor løsninger er mulige.
Så hvis en LP har en optimal løsning, har den en optimal løsning på et ekstremt punkt av det gjennomførbare settet.
Dessuten er det alltid en optimal BFS hvis det er en optimal løsning.
Bruke den enkle metoden for å finne en optimal BFS
Simplex-metoden er en algoritme for å løse problemer i lineær programmering.
Den flyttes fra en BFS til en "tilstøtende" BFS ved å bruke pivotprosedyren.
I pivotprosedyren velges en ikke-grunnvariabel til å bli en grunnvariabel, og deretter brukes gjeldende BFS for å løse de nye grunnvariablene.
Når ingen ikke-grunnleggende variabel kan endres for å få objektivet til å fungere bedre, er algoritmen ferdig.
Hvorfor grunnleggende gjennomførbare løsninger er avgjørende for å løse komplekse tekniske problemer
Fortsatt vanskelig å forstå? La meg endre synspunktet litt:
Hvem trenger enkle, gjennomførbare svar? Bare kast alt sammen og håp på det beste.
Tross alt, hvem trenger optimalisering når kaos er så mye morsommere? Velkommen til en verden av ikke-negative variabler, hvor alt bare er et forslag og feil er nesten sikkert.
Eller er det?
La oss utforske hvorfor det tilsynelatende grunnleggende konseptet med grunnleggende gjennomførbare løsninger er alt annet enn grunnleggende og hvorfor de bare kan være nøkkelen til å løse selv de mest komplekse tekniske problemene.
Ok, det var bare en spøk laget for å se ut som en TV-reklame.
La oss nå gå tilbake til forklaringen.
Finne grunnleggende gjennomførbar løsning
En grunnleggende gjennomførbar løsning (BFS) er en løsning på et lineært optimaliseringsproblem som oppfyller alle begrensninger og har færrest antall variabler som ikke er null.
Hver BFS er et hjørne av polyederet av gjennomførbare løsninger fra et geometrisk synspunkt.
Hvis det finnes en beste løsning, må det også være et beste første skritt.
I denne artikkelen vil vi snakke om hvordan du finner en innledende grunnleggende gjennomførbar løsning, hvordan du finner alle grunnleggende gjennomførbare løsninger og hvordan du finner en grunnleggende gjennomførbar løsning uten svake variabler.
Finne en innledende grunnleggende gjennomførbar løsning
Vi kan bruke ulike metoder, avhengig av hvordan problemet er satt opp, for å finne en innledende grunnleggende løsning som fungerer for et lineært optimaliseringsproblem.
En måte er å legge til slakkvariabler til begrensningene på ulikheter og sette alle de andre variablene til null.
Slakkvariablene blir grunnvariablene, og resten er ikke-basisvariabler.
Den to-fase simpleksmetoden er en annen måte å løse problemet på.
Denne metoden innebærer å løse et ekstra lineært programmeringsproblem for å finne en innledende grunnleggende løsning som er gjennomførbar.
Når først en grunnleggende gjennomførbar løsning er funnet, kan Simplex-metoden brukes til å gå fra en grunnleggende gjennomførbar løsning til den neste og deretter til den beste løsningen.
Finne alle grunnleggende gjennomførbare løsninger
Det kan være mer enn én grunnleggende løsning som fungerer for et lineært program.
Vi kan endre systemet ved å legge til slakkvariabler og deretter bruke det nye systemet til å finne alle grunnleggende gjennomførbare løsninger for et lineært program.
Deretter brukes disse grunnleggende gjennomførbare løsningene for å finne de grunnleggende gjennomførbare løsningene for det opprinnelige problemet.
Finne en grunnleggende gjennomførbar løsning uten slakkvariabler
Vi må bruke slakkvariabler for å bli kvitt mindre enn begrensningene, slik at vi kan finne en grunnleggende løsning som fungerer uten slakkvariabler.
En slakkvariabel er bare forskjellen mellom høyre side av en begrensning og venstre side.
For den første begrensningen definerer vi for eksempel en slakkvariabel x4 = 14 - 2x1 - x2 - x3. Når det gjelder denne nye variabelen, tilsvarer den første begrensningen ganske enkelt x4 ≥ 0, som er en positivitetsbegrensning for x4.
Når vi legger til disse slakkvariablene får vi et lineært program som er det samme som det opprinnelige, bortsett fra at alle begrensningene er enten ligninger eller begrensninger som sier at noe er positivt.
Settet med basisvariabler, som har andre verdier enn null i basisløsningen, kalles basis.
Variabler som har en verdi på null i grunnløsningen er ikke grunnvariable.
For å finne den beste løsningen må vi finne en vektor x som oppfyller alle reglene og får størst eller minste verdi for målet.
Men å finne den beste løsningen tar flere skritt enn bare å finne en løsning som fungerer og som ikke har svake variabler.
Det er ikke alltid mulig å finne en grunnleggende løsning uten svake variabler, spesielt for problemer med mindre enn begrensninger.
For å finne en grunnleggende gjennomførbar løsning, må du bruke simpleksmetoden eller en annen lineær programmeringsalgoritme for å se etter en løsning som oppfyller alle begrensninger og har færrest variabler som ikke er null.
Egenskaper og betydning av grunnleggende gjennomførbar løsning
Egenskaper til grunnleggende gjennomførbar løsning
En grunnleggende gjennomførbar løsning har maksimalt m variabler som ikke er null og minst nm variabler som er null, hvor n er antall beslutningsvariabler og m er antall begrensninger.
En BFS er et hjørne av polyederet av mulige løsninger, og hver BFS har n aktive begrensninger som er lineært uavhengige.
Hvis det finnes en beste løsning, må det også være et beste første skritt.
Det viktigste med grunnleggende gjennomførbare løsninger er at de er enden av settet med konvekse løsninger for et lineært programmeringsproblem.
For å finne det beste svaret går simpleksalgoritmen gjennom en serie BFS-er.
Simplex-algoritmen søker gjennom alle de grunnleggende mulige løsningene på en organisert måte for å finne den beste.
Betydningen av grunnleggende gjennomførbar løsning
Å finne en grunnleggende løsning som er mulig er viktig fordi den hjelper til med å finne det beste svaret på problemer med lineær programmering.
Det gir også komplekse algoritmer et sted å starte og kan brukes til å finne ut om et lineært program er mulig eller ikke.
For å finne alle grunnleggende gjennomførbare løsninger for et lineært program, kan du endre systemet ved å legge til slakkvariabler og deretter bruke det endrede systemet til å finne alle grunnleggende gjennomførbare løsninger.
Deretter brukes disse grunnleggende gjennomførbare løsningene for å finne de grunnleggende gjennomførbare løsningene for det opprinnelige problemet.
Video: Grunnleggende gjennomførbare løsninger
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: | BFS kan brukes til å dele begrensede ressurser på flere prosjekter slik at mest mulig kan gjøres med minst mulig. Denne metoden kan brukes på mange forskjellige felt, som transport, jordbruk og finans. |
| Optimalisering av nettverket: | BFS kan brukes til å få kommunikasjons-, transport- og logistikknettverk til å fungere bedre. BFS kan hjelpe med å finne de beste rutene for varer og tjenester, kutte ned på tid og penger brukt på transport, og fremskynde og gjøre mer nøyaktige leveranser. |
| Planlegging for produksjon: | BFS kan brukes til å planlegge produksjonen slik at ressurser som arbeidskraft, råvarer og utstyr brukes på best mulig måte for å få mest mulig ut av dem. BFS kan bidra til å redusere produksjonskostnadene, redusere avfallsmengden og forbedre effektiviteten. |
| Finansiell planlegging: | I finansiell planlegging kan BFS brukes til å optimalisere investeringsporteføljer, redusere risiko og få mest mulig penger tilbake. BFS kan hjelpe med å finne den beste måten å dele opp eiendeler på, redusere transaksjonskostnader og tjene mer penger. |
| Ledelse av forsyningskjeden: | BFS kan brukes til å forbedre flyten av varer og tjenester fra leverandører til kunder som en del av supply chain management. BFS kan hjelpe med å finne ut den beste mengden lager å ha for hånden, forkorte ledetider og forbedre kundeservicen. |
Konklusjon
Når denne titten på grunnleggende gjennomførbare løsninger nærmer seg slutten, er det tydelig at de er et viktig verktøy for enhver ingeniør eller ingeniørstudent.
Fra å finne ut den beste måten å bygge et komplisert system på til å utnytte ressursene som er tilgjengelige, gir grunnleggende gjennomførbare løsninger et rammeverk for å få best mulig resultat.
Men mer enn bare å være nyttig, viser de hvor elegant og vakker matematikk kan være.
Det er utrolig at du kan koke ned kompliserte problemer til et enkelt sett med ligninger og deretter bruke disse ligningene til å løse problemer i den virkelige verden.
Det er en god påminnelse om at ingeniørfag handler om å løse problemer, og at vi ved å bruke matematikkens kraft kan finne svar som en gang ble antatt å være umulige.
Så når du lærer mer om ingeniørkunst, husk det du har lært om enkle løsninger som fungerer, og bruk dem til å gjøre verden til et bedre og mer effektivt sted.
Lenker og referanser
Bøker:
- Lineær programmering: fundamenter og utvidelser
- Lineær programmering: teori og anvendelser
Dele på…
