Simplex -metoden for lineær optimalisering er ganske enkelt forklart

instagram viewer

Lineær optimalisering handler om optimal tildeling av knappe ressurser til forskjellige bruksområder. De knappe ressursene kan for eksempel være maskinkapasitet eller plassbehov for varer. Det optimale bestemmes matematisk, ofte ved hjelp av simplex -metoden.

Modellering av lineære programmer

Ved modellering av lineære programmer, forskjellige parametere som f.eks B. Behandlingstider for arbeidsstykker eller maskinkapasiteter kan bestemmes. Deretter defineres en objektiv funksjon, som skal maksimeres under visse begrensninger. Objektivfunksjonen er ofte profittfunksjonen, ettersom maksimering av nettoresultat er et sentralt mål for selskaper. Begrensningene er beskrevet av knapphet på ressurser (f.eks. B. Kapasitet, tid, plass). Du kan deretter løse problemet ved å bruke simpleksmetoden.

  • Du kan lære fremgangsmåten for å lage lineære modeller spesielt enkelt hvis du gjør deg til et enkelt eksempel: Anta at du har tre maskiner M1, M.2 og M3 som de to produktene P1 og P.2 bør produseres. Maskinene har ulik kapasitet, og det tar tid å behandle et bestemt produkt på maskinene i forskjellige lengder og de ferdige sluttproduktene genererer forskjellig fortjeneste borte.
  • Vi leter nå etter produksjonsprogrammet med maksimal fortjeneste, dvs. produksjonsprogrammet der størst fortjeneste oppnås.

Eksempel med numeriske verdier og introduksjon til simpleksmetoden

I neste trinn trenger du konkrete numeriske verdier for å modellere problemet ditt. Anta at for redigering av P1 på M1 2 timer påløper på M2 3 timer og på M3 4 timer. For P.2 falle på M.1 4 timer på, på M2 5 timer og på M3 3 timer. Maskinens kapasitet for M1 500 timer, for M2 300 timer og i M3 600 timer. Overskuddet for de ferdige sluttproduktene P1 er 3 euro / stykk, for de ferdige sluttproduktene P2 4 euro / stk.

  1. Det er best å lage en tabell med tre rader og tre kolonner, med ekstra plass til overskriftene til radene og kolonnene. Bør forlate kolonner. For eksempel er behandlingstiden til P i feltet "Kolonne 1 og rad 1"1 på M1, i feltet "kolonne 2 og linje 3" behandlingstiden til P2 på M3. Kolonne 3 viser maskinkapasiteten til de tre maskinene.
    2. Den gaussiske algoritmen til lineære ligningssystemer forklart i et nøtteskall

    Du vil møte lineære ligningssystemer for første gang på ungdomsskolen på ...

  2. Nå trenger du to variabler x1, x2 definere produksjonsmengdene til P1 og P.2 tilsvare.
  3. Så du får begrensningene 2x1+ 4x2 ≤ 500 (maskin 1), 3x1+ 5x2 ≤ 300 (maskin 2) og 4x1+ 3x2 ≤ 600 (maskin 3). I hvert tilfelle er det ulikheter, siden kapasitetene ikke trenger å være helt oppbrukt.
  4. Den objektive funksjonen (profitt) som skal maksimeres er G (x1, x2) = 3x1+ 4x2 -> maks.
  5. I tillegg gjelder ikke-negativitetsbetingelsene til x for produksjonsmengden1, x2 ≥ 0. Du ser, alle ligninger er lineære ligninger. Hvis du ser på dem sammen, får du et lineært optimaliseringsproblem.

Lineær optimalisering og anvendelse av simplex -metoden

Ideen for å løse et lineært program er at ulikhetene ved å introdusere "slake variabler" i Likninger og det modifiserte optimaliseringsproblemet er løst som LGS. Simpleksmetoden er derfor veldig lik den gaussiske algoritmen for å løse LGS.

  1. Eksempel: Et fly er delt med tre varer G1, G.2, G.3 å lastes med høyest mulig total fraktverdi. Disse har et plassbehov på 1, 0,2 eller 6 dm3, har en vekt på 1, 0, 4 og 8 kg og en verdi på 10, 3 eller 50 euro. Hvordan lastes flyet ideelt når lasterommet er 2000dm3 og den kan bære maksimalt 3000 kg last?
  2. Du definerer x1, x2, x3 som mengder av varer G1, G.2, G.3.
  3. Du kan nå sette opp begrensningene med slake variabler som følger: x1+ 0,4x2+ 8x3+ x4 = 3000 og x1+ 0,2x2+ 6x3+ x5 = 2000. Målfunksjonen (total fraktverdi) er G (x1, x2, x3) = 10x1+ 3x2+ 50x3 -> maks. Du kan endre dette ved å bringe alle variablene til en side (G-10x1-3x2-50x3 = 0).
  4. Sett deretter opp Simplex -panelet. Den har 3 rader og 7 kolonner. På venstre side angir du x i kolonnene1, x2, x3, x4, x5 og G som overskrifter. Til høyre er b den eneste kolonnen. Det er her de optimale varemengdene og den høyest mulige totale fraktverdien er oppført. Den tredje linjen er mållinjen. (Sjekk: i de tre linjene med de ovennevnte overskriftene er det tallene: Linje 1: 1, 0,4, 8, 1, 0, 0, 3000, linje 2: 1, 0,2 6, 0, 1, 0, 2000 og linje 3: -10, -3, -50, 0, 0, 1, 0).
  5. Fortsett nå som når du bruker den gaussiske metoden for å løse en LGS. I det første trinnet endrer du linje 1 hhv. Linje 2 blir sendt rundt og lagt til den andre linjen slik at bare en 1 vises i "Linje 1 + Kolonne 1" og en 0 i "Linje 2 + Kolonne 1". Som et resultat endres også verdiene i mållinjen automatisk.
  6. I dette tilfellet kan du for eksempel multiplisere rad 2 med -1 og legge den til rad 1 og multiplisere rad 2 med 10 og legg til linje 3 (kontroll: linje 1: 0, 0,2, 2, 1, -1, 0, 1000, linje 2: forblir den samme, linje 3: 0, -1, 10, 0, 10, 1, 20.000).
  7. I det andre trinnet, ta kolonne 2 og opprett en 0 ved å transformere "rad 2 + kolonne 2" og deretter en 1 i "rad 1 og kolonne 2". Igjen bør det bemerkes hvordan mållinjen endres.
  8. Transformasjonstrinnene vil for eksempel være å multiplisere rad 1 med -1 og legge til rad 2 og rad 1 til 5 og legge til rad 3 (Sjekk: etter å ha utført begge trinnene, er resultatet: linje 1: 0, 1, 10, 5, -5, 0, 5000, linje 2: 1, 0, 4, -1, 2, 0, 1000 og linje 3: 0, 0, 20, 5, 5, 1, 25.000).
  9. Du kan nå lese løsningene på høyre side av panelet. Dette resulterer i en total fraktverdi på 25.000 euro, 5000 enheter med god 1, 1000 enheter med god 2 og ingen enhet med gode 3 blir transportert.

Vær oppmerksom på at løsningen på simplex -tablået bare resulterer i en optimal løsning hvis bare positive resultater vises på mållinjen til venstre etter det siste omformingstrinnet Teller stå. Du har internalisert systemet etter 2-3 andre eksempler og vil kunne løse slike oppgaver i fremtiden på en leken måte.

click fraud protection