I dag tenkte jeg at jeg skulle takle et problem fra et av de mest "populære" kursene (les "påkrevd for nesten alle hovedfag") på denne skolen -begrenset matematikk. For de av dere som ikke har hørt om dette kurset før, er endelig matematikk faktisk en blanding av diverse emner fra sannsynlighetsteori, lineær algebra og statistikk, laget av matematiske avdelinger ved forskjellige universiteter som en måte å introdusere førsteårsstudenter til strenge, analytisk tenkning. Det er ikke et ekte felt av matematikk, i den forstand at du ikke vil finne noen profesjonelle matematikere som spesialiserer seg på "endelig matematikk". Imidlertid er det matematikere som spesialiserer seg på temaene som introduseres i dette kurset, som kombinatorikk og sannsynlighet.
Et av emnene som dekkes i finitt matematikk ("finite", av de som kjenner til) er lineær programmering. Dette er i utgangspunktet en fancy term for et begrenset optimaliseringsproblem som består av lineære begrensninger og en lineær objektivfunksjon. I dette blogginnlegget vil jeg ta tak i følgende problem, som jeg faktisk fant påYahoo svar. Til tross for tittelen på problemet, krever det faktisk ikke kalkulus (selv om detkunneløses med kalkulus). For å gjenta problemet:
Eksempel: Kustom Kars utfører varebilkonverteringer. Den tilpassede konverteringen krever 15 timers butikktid, 8 timers malingstid og 1 time inspeksjonstid. Deluxe-konverteringen krever 12 timers butikktid, 12 timers malingstid og 1,5 timers inspeksjonstid. Det er 90 timers butikktid, 72 timers malingstid og 10 timers inspeksjontid tilgjengeligi løpet av de neste to ukene. Hvor mange konverteringer av hver type bør Kustom Kars utføre forutsatt at hver tilpasset konvertering resulterer i$175 fortjeneste og hver deluxe-konvertering resulterer i $225 overskudd? Hva ermaksimal fortjeneste?
Dette er typisk for denne typen problemer, der de presenterer informasjonen i avsnittsform - det vil si det fryktede "ordproblemet". Det første vi må gjøre er å trekke ut de relevante dataene. Legg merke til at det er to typer tall de gir oss: tid (i timer) og profitt (i dollar). En av disse typene mengder kommer til å gi oss våre begrensninger, mens den andre vil fortelle oss hvordan vi skal formulere målet (hvis du ikke vet hva "begrensning" og "objektiv" betyr, vennligst ta deg tid til å se gjennom notatene dine /lærebok).
Jeg har fremhevet nøkkelsetningene som vil hjelpe oss å skille hva som er hva. "Tid tilgjengelig" er en død giveaway at vi ser på informasjon for våre begrensninger. Vi erbegrensetmed tidentilgjengelig. «Maksimal profitt», derimot, snakker om den objektive funksjonen – vårobjektiver åmaksimereprofitt.
Det neste trinnet er å identifisere variablene våre. Dette er delen hvor jeg tror mange elever blir fanget opp i lineær programmering og ordproblemer generelt. Nøkkelen her er å se på den objektive funksjonen - profitt, i dette tilfellet. Hvilken av tingene nevnt i oppgaven vil til slutt bli brukt til å beregne fortjenesten vår? Vel, la oss ta en titt på denne setningen:"hver tilpasset konvertering resulterer i$175 fortjeneste og hver deluxe-konvertering resulterer i $225 fortjeneste..."Så, fortjeneste avhenger avantall tilpassede konverteringerogantall deluxe-konverteringer. Disse, mine venner, er variablene våre.
La oss kalle antallet tilpassede konverteringer\(x\)og antall deluxe-konverteringer\(y\). Siden vi vet hvor mye profitt de tjener på hver av disse, kan vi skrive vår målfunksjon:
Så vårt mål er å maksimere\(P(x,y)\). Flott! Deretter har vi noen begrensninger. Disse er gitt av 2., 3. og 4. setning i oppgaven:"Den tilpassede konverteringen krever 15 timers butikktid, 8 timers malingstid og 1 time inspeksjonstid. Deluxe-konverteringen krever 12 timers butikktid, 12 timers malingstid og 1,5 timers inspeksjonstid. Det er 90 timer med butikktid, 72 timer malingstid og 10 timers inspeksjonstid tilgjengelig..."
Den enkleste måten å håndtere disse dataene på er å lage en tabell:
Fra dette kan vi trekke ut våre begrensninger. Legg først merke til at det er tre "ingredienser" som går inn i hver type konvertering. Hver av disse ingrediensene kan uttrykkes i form av antall konverteringer av hver type som selskapet gjør:
Legg deretter merke til at det er en grense for total butikktid, malingstid og inspeksjonstid (nedre rad i tabellen). Dette lar oss konstruere ulikhetene:
Jeg har merket disse\(EN\),\(B\), og\(C\). Jeg har også lagt til ytterligere to "trivielle" (faktisk veldig viktige) begrensninger:\(x\geq 0\)og\(y\geq 0\). Disse er viktige fordi vi ikke kan ha et negativt antall konverteringer. Mellom den objektive funksjonen og disse ulikhetene har vi en fullt utformetbegrenset optimaliseringsproblem. Med andre ord, vi har forvandlet en situasjon i den virkelige verden til en verden av matematikk, der vi kan bruke alt vi vet om matematikk for å løse problemet, og deretter bringe svaret vårt tilbake til den virkelige verden.
For å løse dette problemet starter vi med å tegne grafen for begrensningene. For å gjøre dette, konverterer vi først våre ulikheter til likheter. Disse likhetene er i utgangspunktet ligninger av linjer. Siden linjer kan defineres fullstendig av to punkter, er alt vi trenger å gjøre å finne to punkter for hver ligning og tegne en linje mellom dem. Den enkleste måten å finne to poeng på er å sette først\(x=0\)og løse for\(y\), og sett deretter\(y=0\)og løse for\(x\). Så la oss gjøre det for hver ulikhetsbegrensning:
Så for linje\(EN\), vi får poengene\((0, 7,5)\)og\((6, 0)\). Til\(B\), vi får:
Og for\(C\), vi får:
Ved å plotte disse seks punktene, og tegne linjer gjennom de tilsvarende parene med punkter for hver begrensning, får vi denne grafen:
Siden vi leter etter verdiene til\(x\)og\(y\)som maksimerer fortjenesten, vil løsningen vår være et punkt på denne grafen. Men, ikke hvilket som helst poeng! Det må være et punkt som adlyder våre begrensninger. Hvilke punkter følger våre begrensninger, spør du? For å svare på dette spørsmålet vil vi identifisere hva som er kjent sommulig region. Legg merke til at linjene vi nettopp tegnet faktisk skjærer opp x-y-planet i flere stykker (hvorav noen kanskje ikke er helt avgrenset!) Den gjennomførbare regionen kommer til å være en av disse stykkene, der alle punktene overholder våre begrensninger. Den enkleste måten å finne den gjennomførbare regionen er ved å velge entestpunktfra hver region, og koble den inn i begrensningene. Hvis poenget tilfredsstillerallebegrensningene, så er den regionen vår mulige region.
Vi kan også ha en gjetning om at siden alle våre begrensninger innebærer "mindre enn eller lik", at den mulige regionen vil være den nedre venstre delen, over\(x\)og\(y\)økser. For å bekrefte dette, velg testpunktet\((2, 2)\):
Flott! Poenget\((2, 2)\)(i rødt) tilfredsstiller alle begrensningene, så regionen den ligger i er vår mulige region. Legg merke til at denne regionen også kan ses på som en polygon (i dette tilfellet en firkant). Jeg har merket toppunktene til denne polygonen\(P\),\(Q\),\(R\), og\(S\), av grunner som vil bli klare om et øyeblikk.
Ok, nå som vi har vår gjennomførbare region, hvordan finner vi punktet som tilsvarer vår optimale løsning? Vel, vi har et teorem kalt maksimumsprinsippet, som for 2D lineære programmeringsproblemer som dette forteller oss at den optimale løsningen (hvis den finnes) vil ligge på en av toppunktene (også kjent somhjørnepunkter) av den gjennomførbare regionen.
Så alt vi trenger å gjøre er å teste hvert av disse punktene i vår objektive funksjon, og finne punktet som gir oss, i dette tilfellet, maksimal fortjeneste. For å gjøre dette trenger vi koordinatene til hvert punkt. Koordinatene til\(P\),\(Q\), og\(S\)er enkle:\(P\)er opprinnelsen, og\(Q\)og\(S\)er de samme punktene som vi brukte til å konstruere linjer\(EN\)og\(B\). Men hva med poenget\(R\)? Vi vil,\(R\)er rett og slett skjæringspunktet mellom linjer\(EN\)og\(B\). For å finne skjæringspunktet mellom to linjer, husk at vi må løse dem som et ligningssystem:
Den enkleste måten å løse dette på er ved å trekke fra de to ligningene, og deretter tilbake-substituere:
Nå som vi har våre fire hjørnepunkter, kan vi koble dem inn i objektivfunksjonen og finne fortjenesten for hver\((x, y)\)par:
Ok, så vi velger bare poeng\(R\)fordi det gir oss høyest fortjeneste, ikke sant?Nei.Vær forsiktig. Husk at\(x\)og\(y\)tilsvarer virkelige ting - antall tilpassede og deluxe-konverteringer. Vi kan ikke ha 2,57 jobber - ellers ville vi ha noen veldig sinte kunder! Vi må avrunde disse til hele tall, slik at de fortsatt tilfredsstiller alle begrensningene. Vi kunne runde til\((2, 4)\),\((3, 5)\),\((3, 4)\), eller\((2, 5)\). Vel, det eneste av disse punktene som ikke vil bryte med en av våre begrensninger er\((2, 4)\), så vi vil oppdatere R med dette punktet:
Når vi runder\(R\)til nærmeste hele tall, må vi beregne fortjenesten på nytt. Nå er det ikke det optimale punktet lenger - poeng\(S\)gir oss nå den høyeste fortjenesten! På en måte har vi introdusert en annen begrensning for problemet, nemlig det\(x\)og\(y\)være heltall. Denne typen begrensninger er faktisk et emne i seg selv, heltallsprogrammering, som vi ikke kommer inn på i dag. Det er nok å si at vi har funnet den optimale løsningen på problemet: Kustom Kars (forferdelig navn forresten), bør gjøre 0 tilpassede konverteringer og 6 deluxe-konverteringer for en fortjeneste på $1350.
Håper alle likte det!
Oppdater(takk til reddit-brukerenzifyoip): når vi arbeider med heltallsproblemer, garanterer avrunding av ikke-heltallspunkter oss ikke lenger en optimal løsning. For dette problemet fungerte det tilfeldigvis, men generelt sett er det beste vi kan si at den optimale fortjenesten eri det minste$1350. Takk!