Et viktig ledd i å kunne løse lineære problemer er å kunne oversette problemene til matematiske modeller. Det er ikke alltid opplagt hvordan man bør modellere problemet og det finnes noen ganger flere veier man kan gå for å finne en optimal løsning. For å bli god i modellering trenger man hovedsakelig trening. Her skal vi ta for oss ett eksempel på både modellering og grafisk løsing. I neste innlegg vil ta for oss simplex-metoden som er en analytisk algoritme for å løse lineære systemer.
Når vi leser en oppgave i lineær programmering så er det greit å merke seg nøkkelinformasjon, samt notere seg egenskaper ved problemet i tabeller.
Eksempel – Leketøysfabrikken Leker-R-Oss
Ledelsen hos leketøysfabrikken Leker-R-Oss AS har innstilt produksjon av et leketøy som ikke selger bra nok. De engasjerer designerne sine for å komme med konsepttegninger til potensielle nye leker. Etter noe siling sitter ledelsen igjen med to konsepttegninger de liker, en designerdukke og en modifisert versjon av en populær lekebil. Ledelsen ber de aktuelle avdelingene om hvor mye arbeidstimer leketøyene vil beslaglegge per stykk. Produksjonen antas å ta en halvtime per dukke, men ingen tid for lekebilene da delene kjøpes på det åpne markedet. Maling av dukkene er arbeidskrevende og tar en hel time per stykk, mens lekebilene bare trenger noe påskrift og enkel fargelegging, dette tar typisk et kvarter per stykk. Montering av dukkene er ganske enkelt og gjøres på 12 minutter, mens bilene har en del elektronikk og små deler som tar en halvtimes tid å montere. Det produksjon-, maling- og monteringsavdelingen har henholdsvis 400, 1100 og 1200 timer tilgjengelig. En markedsundersøkelse viser at dukkene kan selges med en profitt på kr 900 per stykk, mens lekebilene typisk har en profitt på kr 300. Hvor mye av hvert leketøy bør det produseres for å maksimere den totale profitten?
Vi ser at det er snakk om avdelinger med begrenset mengde arbeidstimer. Dette lukter det skranker av. La oss sette opp en tabell med oversikt over nødvendig tidsbruk per leketøy og ledige arbeidstimer.
|
Avdeling |
Minutter per dukke |
Minutter per lekebil |
Tilgjengelig arbeidstimer |
|
Produksjon |
30 |
0 |
400 |
|
Maling |
60 |
15 |
1100 |
|
Montering |
10 |
30 |
1200 |
Videre har vi noen tall om arbeidskostnadene, salgspris og inntakskost.
|
Leketøy |
Profitt per leketøy |
|
Dukke |
900 |
|
Lekebil |
300 |
Nå som vi har litt mer oversiktlig informasjon kan vi tenke litt på hvordan dette skal modelleres. La oss indeksere leketøyene med symbolet i og avdelingen med j. Da kan vi modellere nødvendig arbeidstid per leketøy i på avdeling j som Aij og tilgjengelig arbeidstid på avdelingen j med Bj. Videre kan vi kalle profitten per leketøy i Ci.
Nå mangler vi bare beslutningsvariablene, dvs hvor mye vi skal produsere av hvert leketøy. Antallet av leketøy i kan vi kalle xi. Vi skal maksimere profitten. Profittfunksjon eller, på lineær programmeringsterminologi, objektfunksjonen z er enkelt og greit summen av profitten per leketøy ganget med antall leketøy.
La oss sette dette opp litt mer formelt.
Objektfunksjon skal være samlet profitt
Gitt skrankene
Hvis vi nå setter inn tall får vi følgende lineære systemet
La oss justere slik at vi ser på timebruk per time
Dette gir følgende graf
Figur 1: Leker R Oss
Vi får altså en optimal løsning der
Legg merke til at objektfunksjonen ble valgt tilfeldig til 720k og så forskjøvet opp til hjørneløsningen med 1160k, dvs like under 1,2 millioner kroner inn på konto! En veldig lukrativ affære, muligens. Neste artikkel blir om simplex-metoden.