Den mest optimale løsningen i saken. Bestemme den optimale løsningen på et lineært programmeringsproblem. Fortjeneste på salg av pakken
Hvis i problemet nettopp vurdert den første grunnleggende løsningen som ble oppnådd viste seg å være akseptabel, kan den i andre tilfeller ikke bli funnet umiddelbart, men etter et visst antall trinn.
Det må huskes at i det første stadiet av simpleksmetoden, det vil si når man finner en mulig løsning, tas den lineære formen ikke i betraktning, og alle transformasjoner er bare relatert til systemet med begrensninger.
La det lineære programmeringsproblemet gis i generell form, dvs. system av m lineære ligninger med n variabler (m Følgelig tilsvarer denne metoden for å dele variabler i grunnleggende og ikke-grunnleggende til den grunnleggende løsningen...; 0; 0;…;0. La oss vurdere det generelle tilfellet når denne løsningen er uakseptabel. Fra den oppnådde basisløsningen må man først gå over til en tillatt basisløsning, og det er ikke nødvendig at denne overgangen utføres umiddelbart, i ett trinn. Hvis systemet med begrensninger ikke er inkonsekvent, vil overgangen til en tillatt grunnleggende løsning etter et begrenset antall trinn utføres. Ved antagelse er den opprinnelige grunnløsningen ugyldig. Følgelig, blant de frie medlemmene av systemet av begrensninger er det minst én negativ (antallet negative frie medlemmer av dette systemet faller sammen med antallet negative komponenter i den opprinnelige grunnløsningen). La det være et gratis medlem k i i-ro-ligninger, dvs. hovedvariabelen x i i den tilsvarende grunnløsningen er negativ. For å gå over til en ny grunnleggende løsning, må to problemer løses: 1) fastslå hvilken ikke-grunnvariabel som skal konverteres til hovedvariabelen; 2) velg en variabel som skal overføres fra de viktigste til de ikke-grunnleggende i stedet for den som er fjernet fra de viktigste. Når du konverterer en ikke-grunnleggende variabel til en større, reduseres den ikke, men øker som regel: i stedet for null i den opprinnelige grunnløsningen, vil den ha en positiv verdi i den nye grunnløsningen (et unntak forekommer bare i tilfelle degenerasjon). Derfor, for å løse spørsmålet om hvilke ikke-grunnleggende variabler som kan konverteres til grunnleggende, må du kunne finne ikke-grunnleggende variabler, med en økning der hovedvariabelen, negativ i den opprinnelige grunnløsningen, øker. La oss gå tilbake til den i-te ligningen av systemet, der det frie leddet k i negativ. Det viser at variabelen x iøker med økningen av de ikke-grunnleggende variablene hvis koeffisienter i denne ligningen er positive. Det følger at de ikke-grunnleggende variablene som har positive koeffisienter i ligningen til et system med et negativt friledd, kan konverteres til grunnleggende. Tre saker kan presentere seg her. 1. I systemets i-te ligning er det ingen småvariabler med positive koeffisienter, dvs. alle koeffisienter b i, j er negative (det samme er fribegrepet k i). I dette tilfellet er dette restriksjonssystemet inkonsekvent - det har ikke en eneste tillatt løsning. Faktisk, på grunn av ikke-negativiteten til alle variabler, inkludert x m + l ,...,x n , den i-te ligningen der frileddet k i og alle koeffisienter b i, m + l,...,b i, n er negative, følger det at variabelen x i- kan ikke ta ikke-negative verdier. Men hvis det ikke er en enkelt gjennomførbar løsning på et system av begrensninger, så er det ingen optimal løsning. 2. Den i-te ligningen har én variabel x t+ j, hvis koeffisient er positiv. I dette tilfellet er det denne variabelen som overføres til de viktigste. 3. Den i-te ligningen har flere variabler med positive koeffisienter. I dette tilfellet kan hvilken som helst av dem konverteres til grunnleggende. Deretter må du bestemme hvilken hovedvariabel som skal konverteres til ikke-grunnleggende. For å gjøre dette bør du bruke regelen: finn forholdene mellom de frie leddene og koeffisientene til variabelen som konverteres til de viktigste fra alle ligninger der tegnene til de frie leddene og de indikerte koeffisientene er motsatte, og vurder deretter absoluttverdien av disse forholdene og velg den minste fra dem (hvis i noen ligninger tegnene frie ledd og koeffisienter faller sammen eller i noen ligninger er det ingen variabel som kan konverteres til grunnleggende, så anses forholdet som lik ∞). Ligningen som det minste forholdet er oppnådd fra er isolert. Den uthevede ligningen viser hvilke av hovedvariablene som skal konverteres til ikke-grunnleggende. Etter å ha uttrykt de nye hovedvariablene i form av ikke-grunnleggende, går de videre til neste grunnleggende løsning. Resultatet er et ligningssystem som ligner på systemet, der antallet negative frie lønner enten sammenfaller med antallet i systemet eller er ett mindre. Dette avhenger av om avskjæringen i den uthevede ligningen er positiv eller negativ. Hvis frileddet i den valgte ligningen er negativ, vil antallet negative komponenter i den nye grunnløsningen være én mindre enn i den opprinnelige. Hvis frileddet i den valgte ligningen er positivt (eller lik null), vil antallet negative komponenter i den nye grunnløsningen forbli det samme som i den opprinnelige. Så vi får en ny, forbedret grunnleggende løsning, som er nærmere regionen med gjennomførbare løsninger på systemet med begrensninger. Hvis det viser seg å være uakseptabelt, bør den samme ordningen brukes på det igjen. Som et resultat, etter et begrenset antall trinn, vil en tillatt grunnløsning oppnås. Fortsettelse av eksempel 4.1. Vi må finne en akseptabel grunnleggende løsning på dette systemet av begrensninger som vil maksimere den lineære formen. Siden systemet av begrensninger er et system av fire uavhengige ligninger med seks variabler, bør antallet hovedvariabler være fire, og antallet ikke-grunnleggende skal være to. For å løse et problem ved å bruke simplex-metoden, må du først og fremst finne en grunnleggende løsning. I dette tilfellet er det enkelt å gjøre. For å gjøre dette er det nok å ta tilleggsvariabler som de viktigste X 3 , X 4 , X 5 , X 6. Siden koeffisientene til disse variablene danner en identitetsmatrise, er det ikke nødvendig å beregne determinanten. Teller ikke-kjernevariabler X 1 , x 2 lik null, får vi den grunnleggende løsningen (0; 0; 120; 160; 120; 80), som også viste seg å være tillatt. Derfor er det ikke nødvendig å bruke den første fasen av simpleksmetoden. Vi går direkte videre til det andre trinnet, det vil si søket etter en optimal løsning. 1 trinn. Hovedvariabler: x 3, x 4, x 5, x 6; ikke-kjernevariabler: X 1 , x 2. I systemet uttrykker vi hovedvariablene gjennom ikke-grunnleggende. For å bedømme om man skal la ikke-grunnleggende variable være blant de ikke-grunnleggende, eller om det er mer lønnsomt med tanke på å nærme seg den optimale løsningen å overføre dem til de viktigste, er det nødvendig å uttrykke en lineær form gjennom dem (i dette tilfellet er det allerede uttrykt gjennom variablene X 1 , x 2) Da får vi: På X 1 = X 2 = 0 vi har X 3 = 120, X 4 = 160, X 5 = 120, X 6 = 80, som gir den grunnleggende løsningen (0; 0; 120; 160; 120; 80), som vi tok som den første. Med denne grunnleggende løsningen er verdien av den lineære formen =0. Når vi tenkte X 1 = X 2 = 0 (produksjon produserer ikke noe), var målet satt - å finne den første, uansett hva, grunnleggende løsningen. Dette målet er nådd. Nå må vi gå fra denne innledende løsningen til en annen, der verdien av den lineære formen vil øke. Fra vurderingen av den lineære formen er det klart at verdien øker med økende verdier av variablene X 1 og X 2. Med andre ord er det ulønnsomt å betrakte disse variablene som ikke-grunnleggende, det vil si lik null, de må konverteres til antall grunnleggende. Dette innebærer en overgang til ny basisløsning. Med simpleksmetoden antas det ved hvert trinn i løsningen at kun én av de frie variablene konverteres til hovedvariablene. La oss konvertere variabelen til antall grunnleggende X 2, siden den er inkludert i uttrykket av den lineære formen med en stor koeffisient. Så snart en av de frie variablene blir en av hovedvariablene, må en av hovedvariablene overføres i stedet for til antall ikke-grunnleggende. Hvilken av de fire hovedvariablene bør utledes? Følgende betraktninger vil bidra til å svare på dette spørsmålet. Betydning X 2 må gjøres så stor som mulig, siden dette tilsvarer det endelige målet - maksimering F. Det viser seg imidlertid at økningen X 2 kan bare fortsette opp til kjente grenser, nemlig inntil kravet om ikke-negativitet av variabler brytes. Så fra den første ligningen til systemet følger det at variabelen x 2 ikke skal overstige tallet 120/4, dvs. X 2 ≤30, siden bare med disse verdiene X 2 variable X 3 forblir positiv (hvis X 2 = 30, da X 3 = 0; hvis X 2 >30, da X 3 < 0). Из третьего уравнения системы следует, что X 2 ≤ 120/2, dvs. X 2 ≤ 60, fra den fjerde - hva X 2 ≤ 80/2, dvs. X 2 ≤ 40 (i den andre ligningen er variabelen X 2 ikke inkludert). Oppfyller alle disse betingelsene X 2 ≤ 30. Med andre ord, for å svare på spørsmålet om hvilken variabel som skal konverteres til ikke-grunnleggende, må du godta X 2 = min (120/4; 120/2; 80/2) = min (30; 60; 40) = 30. Deretter X 3 = 0 og X 3 blir en ikke-primær variabel, og x 4 og x 5 forblir positive, Steg 2. Nøkkelvariabler: X 2 , X 4 , X 5 , X 6 mindre variabler: X 1 og X 3. La oss uttrykke hovedvariablene og den lineære formen i form av ikke-grunnleggende. I systemet tar vi ligningen hvorfra minimumsverdien av forholdet mellom frileddet og koeffisienten ved X 2. I dette tilfellet er det den første ligningen. Uttrykk fra denne ligningen X 2, vi har, X 2 = 30 - 0,25 · X 3. La oss erstatte dette uttrykket X 2 inn i alle andre systemlikninger (4.4) og i lineær form F og med lignende vilkår får vi På X 1 = X 3 = 0 vi har F= 90. Dette er allerede bedre enn ved trinn 1, men ikke ønsket maksimum. Ytterligere økning i funksjon F mulig ved å introdusere en variabel X 1 blant de viktigste; siden denne variabelen er inkludert i uttrykket F med en positiv koeffisient, derfor fører økningen til en økning i den lineære formen, og det er ulønnsomt å betrakte det som ikke-grunnleggende, dvs. lik null. For å svare på spørsmålet om hvilken variabel som skal utledes fra de viktigste til de ikke-grunnleggende, godtar vi X 1 = min (160/4; 60/2; 20/1) = 20. Deretter X 6 = 0 og X 6 blir en ikke-hovedvariabel, og X 4 og X 5 forblir positive. Den første ligningen brukes ikke når man finner det spesifiserte minimumet, siden X] er ikke inkludert i denne ligningen. Trinn 3. Nøkkelvariabler: X 1 , x 2 , x 4 , x 5; mindre variabler: x 3, x 6. La oss uttrykke hovedvariablene og lineær form i form av ikke-grunnleggende. Fra siste likning av system (4.5) (den er uthevet) har vi X 1 = 20 + 0,5 · X 3 - X 6. Ved å erstatte dette uttrykket i de resterende ligningene og i lineær form, får vi Fra uttrykket av den lineære formen følger det at dens maksimale verdi ennå ikke er oppnådd, siden en økning er mulig F ved å introdusere i hovedvariabelen X 3 (den har en positiv koeffisient). Vi tror X 3 = min (∞; 30/0,25; 80/2; 20/0,5) =40. Her møter vi først to bestemmelser som krever ytterligere presisering. Først, selv om variabelen X 3 og inngår i uttrykket for X 1 (den første ligningen av systemet (4.6), men har en positiv koeffisient for enhver økning X 3 variable X 1 kan ikke bli negativ. Med andre ord, i den første ligningen er det ingen begrensninger på økningen av variabelen X 3 overlapper ikke, så vi skriver konvensjonelt ∞. La oss i det følgende bli enige om å bruke samme notasjon hvis variabelen som gjeninnføres som en fundamental variabel ikke er inkludert i noen ligning for begrensningssystemet. For det andre vil vi få to identiske minimumsverdier lik 40. Hvis X 3 = 40, da X 4 =
0 og x 5 = 0, dvs. konklusjonen antyder at i stedet for én variabel, bør to overføres til antallet ikke-grunnleggende på en gang: X 4 og x 5. Men antallet hovedvariabler bør ikke være mindre enn fire. For å gjøre dette, fortsett som følger. En av variablene ( X 4 eller X 5.) er igjen blant de grunnleggende, men samtidig anses verdien som lik null, det vil si at den grunnleggende løsningen oppnådd i neste trinn viser seg å være degenerert. La oss forlate f.eks. X 4 blant hovedvariablene, og X 5 vil bli overført til antall ikke-kjerne. Trinn 4 Nøkkelvariabler: X 1, x 2, X 3 , X 4; ikke-hovedvariabler: x 5, x 6. La oss uttrykke hovedvariablene og lineær form F gjennom ikke-primære, og starter dette uttrykket fra den fjerde systemligningen (4.6). Som et resultat får vi Siden i uttrykket av en lineær form variablene X 5 og X 6 angi med negative koeffisienter, deretter ingen økning F på grunn av disse variablene er umulig. Fraværet på et eller annet trinn av simpleksmetoden i uttrykket av den lineære formen F, hvis maksimum søkes etter, av ikke-grunnleggende variabler med positive koeffisienter er et optimalitetskriterium. Følgelig oppnås ved trinn 4 optimalitetskriteriet og problemet er løst. Den optimale løsningen er (40; 20; 40; 0; 0; 0), der F maks =140. Dermed for å oppnå størst fortjeneste lik 140 den. enheter, fra disse ressursene er det nødvendig å skaffe 40 enheter produksjon fra slåttemark og 20 fra dyrkbar mark. I dette tilfellet vil ressurser av type II, III og IV bli fullstendig brukt, og 40 enheter. Type I forblir ubrukt. Eksempel 4.2. Finn maksimum av en funksjon F=x 1 + 2 X 2 med restriksjoner Vi introduserer flere ikke-negative variabler X 3 ,X 4 ,X 5 ,X 6 og redusere dette systemet av ulikheter til dets ekvivalente system av ligninger Vi tar de introduserte tilleggsvariablene som de viktigste, siden i dette tilfellet er den grunnleggende løsningen til systemet lett å finne. Deretter X 1 og X 2 - mindre variabler. 1 trinn. Nøkkelvariabler: X 3 ,X 4 , X 5 , X 6; ikke-kjernevariabler; X 1 og X 2. Å uttrykke hovedvariablene i form av ikke-grunnleggende, får vi Følgelig tilsvarer denne inndelingen av variabler i grunnleggende og ikke-grunnleggende den grunnleggende løsningen (0; 0; - 2; - 4; 2; 6), som er uakseptabel (to variabler er negative), og derfor er den ikke optimal. Fra denne grunnleggende løsningen går vi videre til en forbedret. For å bestemme hvilken variabel som skal overføres fra minor til fundamental, vurder en av de to tilgjengelige likningene i sistnevnte system med negative frie ledd, for eksempel den andre. Den viser at det er mulig å oversette til grunnleggende variabler X 1 og X 2, siden de i denne ligningen har positive koeffisienter (derfor, når de øker, hva vil skje hvis vi oversetter noen av dem til hovedvariablene, variabelen X 4 vil øke). La oss prøve å oversette det til hovedvariabelen X 1 . For å fastslå hvilken variabel som skal overføres fra grunnleggende til ikke-grunnleggende, finner vi absoluttverdien av det minste forholdet mellom systemets frie ledd og koeffisientene ved X 1 ,
vi har X 1 = min (∞; 4/1; 2/1; ∞) = 2. Den er hentet fra den tredje ligningen, som viser at variabelen må konverteres til minor. X 5, noe som er positivt i den opprinnelige grunnløsningen. Følgelig inneholder den resulterende basisløsningen, i likhet med den opprinnelige, to negative komponenter, dvs. når du flytter til en slik basisløsning, vil det ikke være noen forbedring. Hvis vi oversetter til hovedvariabelen X 2 ,
deretter det minste forholdet mellom frie ledd og koeffisienter ved X 2 blir X 2 -
min (2/2; 4/1; ∞; 6/1) = 1. Den er hentet fra den første ligningen, der frileddet er negativt. Derfor oversetter X 2 i de viktigste, og X 3 inn i mindre variabler, får vi en grunnleggende løsning der antallet negative komponenter er én mindre enn i den opprinnelige. La oss derfor fokusere på denne muligheten: vi oversetter X 2 i de viktigste, og X 3 i ikke-kjernevariabler; da vil den første ligningen bli uthevet. Steg 2. Nøkkelvariabler: X 2 ,X 4 ,X 5 ,X 6; ikke-kjernevariabler: X 1 og X 3. La oss uttrykke de nye hovedvariablene gjennom de nye ikke-grunnleggende, og starter med ligningen uthevet i trinn 1. Som et resultat får vi Følgelig har vi en ny basisløsning (0; 1; 0; -3; 3; 5), som også er uakseptabel og derfor ikke optimal. Men i den, som vi spådde, er bare én variabel negativ (nemlig X 4). Fra den oppnådde grunnleggende løsningen er det nødvendig å gå videre til en annen. La oss vurdere en ligning med et negativt friledd, dvs. andre ligning. Den viser at det er mulig å oversette til grunnleggende variabler X 1 og X 3. La oss konvertere til hovedvariabler X 1 .
La oss finne den minste av de absolutte verdiene av forholdene mellom systemets frie ledd og koeffisientene ved X 1 ; vi har X 1 =
min (∞; 3/1,5; 3/0,5; 5/0,5) = 2. Dette betyr at vi må konvertere X 4. Siden det minste forholdet er hentet fra den andre ligningen, isolerer vi det. Den nye basisløsningen vil ikke lenger inneholde negative komponenter, det vil si at den er tillatt. Trinn 3. Nøkkelvariabler: X 1 , X 2 , X 5 , X 6; ikke-kjernevariabler: X 3 , X 4. Å uttrykke hovedvariablene i form av ikke-grunnleggende, får vi Den nye basisløsningen har formen (2; 2; 0; 0; 2; 4). Hvorvidt det er optimalt kan bestemmes ved å uttrykke en lineær form i form av de mindre variablene for den grunnleggende løsningen som vurderes. Etter å ha gjort dette, får vi . Dermed tyr vi til den lineære formen bare når den grunnleggende løsningen er gjennomførbar. Siden vi ser etter det maksimale av en lineær form, er den resulterende grunnløsningen ikke optimal. Konvertering av antall hovedvariabler X 4 har en større positiv koeffisient. Vi finner X 4 = min (∞; ∞; 2: (1/3); 4/(1/3)) = 6. Dette minste forholdet er hentet fra den tredje ligningen i systemet, som vi velger. Det viser at når X 4 =6 variabel X 5 = 0 og vil derfor bli ikke-primær. Trinn 4 Nøkkelvariabler: X 1 , X 2 , X 4 , X 6;mindre variabler: X 3 , X 5 . Å uttrykke hovedvariablene i form av ikke-grunnleggende, får vi Den lineære formen, uttrykt gjennom de samme ikke-grunnleggende variablene, vil ha formen . Derfor er grunnløsningen (6; 4; 0; 6; 0; 2) som vi flyttet til ikke optimal. En økning i den lineære formen er mulig ved overgang til en ny basisløsning, der variabelen x 3 er den viktigste. Vi finner X 3 = min (∞; ∞; co; 2/1) = 2. Dette minste forholdet er hentet fra systemets fjerde ligning og viser at når X 3 = 2 variabel X 6 = 0 og blir ikke-primær. Trinn 5 Nøkkelvariabler: X 1 , X 2 , X 3 , X 4 mindre variabler X 5 ,X 6. Å uttrykke hovedvariablene i form av ikke-grunnleggende, får vi Den lineære formen, uttrykt i form av småvariablene til den nye grunnløsningen, har formen . Optimalitetskriteriet for lineær formmaksimering er oppfylt. Derfor er den grunnleggende løsningen (8; 6; 2; 10, 0; 0) optimal, og maksimum av den lineære formen F maks =
20. 4.5 Grafisk problemløsning lineær programmering Det anbefales å bruke en grafisk metode for å løse lineære programmeringsproblemer for: Løsninger på problemer med to variabler når begrensninger uttrykkes ved ulikheter; Løsninger på problemer med mange variabler, forutsatt at deres kanoniske notasjon ikke inneholder mer enn to frie variabler. La oss skrive et lineært programmeringsproblem med to variabler: objektiv funksjon: begrensninger: Hver av ulikhetene (4.8) i systemet av begrensninger av problemet definerer geometrisk henholdsvis et halvplan med rette grenselinjer; . Hvis systemet med ulikheter (4.8) er konsistent, er domenet til løsningene det settet med punkter som tilhører alle de indikerte halvplanene. Siden settet med skjæringspunkter til disse halvplanene er konveks, er området med mulige løsninger et konveks sett, som kalles en løsningspolygon. Sidene av denne polygonen ligger på rette linjer, hvis likninger er hentet fra det opprinnelige systemet av begrensninger ved å erstatte ulikhetstegn med likhetstegn. Regionen med tillatte løsninger for ulikhetssystemet (4.8) kan være: konveks polygon; Konveks polygonalt ubegrenset område; Tomt område; Linjestykke; Det eneste poenget. Objektivfunksjonen (4.7) definerer en familie av parallelle linjer på planet, som hver tilsvarer en viss Z-verdi. En vektor med koordinater og , vinkelrett på disse linjene, indikerer retningen for den raskeste økningen i Z, og den motsatte vektoren indikerer retningen for nedgangen i Z. Hvis vi skildrer området med tillatte løsninger av systemet med ulikheter (4.8) og familien av parallelle linjer (4.7) i det samme koordinatsystemet, vil problemet med å bestemme maksimumet av funksjonen Z bli redusert til å finne i det tillatelige region punktet som en linje fra familien Z = const går gjennom, og som tilsvarer den største verdien av Z-parameteren. Dette punktet eksisterer når løsningspolygonet ikke er tomt og objektivfunksjonen på den er avgrenset ovenfra. Under de spesifiserte forholdene, ved et av toppunktene til løsningspolygonet, får objektivfunksjonen maksimalverdien. For å bestemme dette toppunktet vil vi konstruere en nivålinje som går gjennom origo til koordinater og vinkelrett på vektoren, og vi vil flytte den i retning av vektoren til den berører det siste ytterpunktet (hjørne) av løsningspolygonet. Koordinatene til det angitte punktet bestemmer den optimale planen for denne oppgaven. Figur 4.1 - Det optimale for funksjon Z er oppnåelig ved punkt A Figur 4.2 - Den optimale funksjonen Z oppnås når som helst [AB] Ved å avslutte vår vurdering av den geometriske tolkningen av problemet (4.7) - (4.8), merker vi at når vi finner løsningen, er tilfellene vist i fig. 4.1 - 4.4. Figur 4.1 karakteriserer tilfellet når målfunksjonen tar sin maksimale verdi ved et enkelt punkt A. Fra figur 4.2 er det tydelig at målfunksjonen tar sin maksimale verdi på et hvilket som helst punkt på segmentet AB. Figur 4.3 - Det optimale for Z-funksjonen er uoppnåelig Figur 4.4 - Område med gjennomførbare løsninger - tomt område Figur 4.3 viser tilfellet når maksimum er uoppnåelig, og figur 4.4 viser tilfellet når systemet med begrensninger for problemet er inkonsekvent. Merk at å finne minimumsverdien til Z under et gitt system av restriksjoner skiller seg fra å finne maksimumsverdien under de samme restriksjonene bare ved at Z-nivålinjen beveger seg ikke i retning av vektoren, men i motsatt retning. Således oppstår tilfellene nevnt ovenfor som oppstår når man finner maksimumsverdien til objektivfunksjonen, også når man bestemmer minimumsverdien. For å praktisk talt løse det lineære programmeringsproblemet (4.7) - (4.8) basert på dens geometriske tolkning, er følgende nødvendig. 1. Konstruer rette linjer hvis likninger er oppnådd ved å erstatte ulikhetstegn i restriksjoner (4.4) med likhetstegn. 2. Finn halvplanene definert av hver av begrensningene til problemet. 3.Definer løsningspolygonet. 4. Konstruer en vektor. 5.Konstruer en rett linje som går gjennom origo til koordinater og vinkelrett på vektoren. 6. Flytt den rette linjen i retningen til vektoren , som et resultat av at de enten finner punktet (punktene) der den objektive funksjonen tar maksimalverdien, eller etablerer funksjonens uavgrensning ovenfra på settet med planer . 7. Bestem koordinatene til maksimumspunktet for funksjonen og beregn verdien av objektivfunksjonen på dette punktet. Eksempel 4.3. Selskapet produserer to typer produkter P og R, som selges i engros. For produksjon av produkter benyttes to typer råvarer A og B. Maksimalt mulig tilførsel av råvarer per dag vil være henholdsvis 9 og 13 enheter. Forbruket av råvarer av type A til produksjon av produktene P og P vil være henholdsvis 2 og 3 enheter av type B - 3 og 2 enheter. Erfaring har vist at den daglige etterspørselen etter produkt P aldri overstiger etterspørselen etter produkt P med mer enn 1 enhet. I tillegg er det kjent at etterspørselen etter produkt P aldri overstiger 2 enheter per dag. Engrospriser per produksjonsenhet er lik 3 enheter for P, og 4 enheter for P. Hvor mye av hver type produkt bør bedriften produsere for at salgsinntektene skal maksimeres. Løs oppgaven ved hjelp av en geometrisk metode. Løsning. La oss konstruere en polygon av løsninger (fig. 7.5). For å gjøre dette, i koordinatsystemet X 1 OX 2 på planet, tegner vi grenselinjene: Ved å ta et hvilket som helst punkt, for eksempel opprinnelsen, bestemmer vi hvilket halvplan som definerer den tilsvarende ulikheten. Halvplan definert av ulikheter i fig. 7.5 er vist med piler. Løsningsdomenet er polygonet OABCD. For å konstruere en rett linje konstruerer vi en gradientvektor og gjennom punkt 0 tegner vi en rett linje vinkelrett på den. Vi flytter den konstruerte rette linjen Z= 0 parallelt med seg selv i vektorens retning. Av figur 4.5 følger det at i forhold til løsningspolygonet blir denne linjen referanselinjen i punkt C, hvor funksjonen får sin maksimale verdi. Punkt C ligger i skjæringspunktet mellom linjene L 1 og Z 3. For å bestemme koordinatene løser vi likningssystemet: Optimal oppgaveplan = 2,4; =1,4. Ved å erstatte verdiene og inn i den lineære funksjonen får vi: 3 2,4 + 4 1,4 = 12,8. Den resulterende løsningen betyr at produksjonsvolumet av produkt P skal være lik 2,4 enheter, og av produkt P - 1,4 enheter. Inntekten mottatt i dette tilfellet vil være: Z = 12,8 cu. Figur 4.5 - Løse et lineært programmeringsproblem ved hjelp av en geometrisk metode 5. DOBBELTE PROBLEMER Sammensetning av et dobbeltproblem. Vurder to lineære programmeringsproblemer: Maksimer funksjonen under restriksjoner Minimer funksjon under restriksjoner Disse oppgavene har følgende egenskaper: 1. I den ene oppgaven søkes maksimum av en lineær form, og i den andre minimum. 2°. Koeffisienter av variabler i den lineære formen av ett problem er frie medlemmer av systemet av begrensninger av et annet problem, tvert imot, frie medlemmer av systemet av begrensninger av ett problem er koeffisienter av variabler i lineær form av et annet problem. 3°. I hver oppgave er et system av begrensninger spesifisert i form av ulikheter, og de har alle samme betydning, nemlig: når man finner maksimum av en lineær form, har disse ulikhetene formen, og når man finner minimum, har de form 4°. Koeffisienter av variabler i begrensningssystemer er beskrevet av matriser som er transponert i forhold til hverandre. 5°. Antall ulikheter i systemet av begrensninger for ett problem faller sammen med antall variabler for et annet problem. 6 f. Betingelsene for ikke-negativitet av variabler er bevart i begge oppgavene. To lineære programmeringsproblemer som tilfredsstiller betingelsene ovenfor kalles symmetriske dobbeltproblemer. Vi skal kun studere symmetriske doble problemer, og derfor vil vi kort og godt kalle dem - doble problemer. Dermed kan hvert lineært programmeringsproblem assosieres med dets doble problem. Vi vil kalle det opprinnelige problemet det opprinnelige (eller direkte) problemet. Det direkte problemet og dets doble problem, tatt sammen, danner et par gjensidige doble problemer, og hvilket som helst av dem kan betraktes som det første, så vil det andre være dobbelt med det. Fra det ovenstående følger følgende regler for å komponere et problem som er dobbelt til det opprinnelige: 1. Alle ulikheter i systemet av begrensninger av det opprinnelige problemet reduseres til ulikheter av samme betydning: hvis det i den opprinnelige oppgaven søkes etter maksimum av en lineær form, til formen ≤, hvis minimum, til formen ≥. For dette multipliseres ulikheter der dette kravet ikke er oppfylt med -1. 2. Skriv ut matrisen A for koeffisientene for variablene i det opprinnelige problemet, oppnådd etter transformasjonen av trinn 1, og komponer matrisen A" transponert med hensyn til matrisen A. 3. Sett sammen et system med restriksjoner for det dobbelte problemet, ta elementene i matrisen A som koeffisienter for variablene, og koeffisientene for variablene i den lineære formen av det opprinnelige problemet som frie ledd, og skriv ned ulikheter i det motsatte betydning sammenlignet med ulikhetene oppnådd i trinn 1. 4. Komponer en lineær form av det dobbelte problemet, og ta de frie leddene til systemet av begrensninger til det opprinnelige problemet oppnådd i trinn 1 som koeffisienter for variablene. 5. Angi hva som må finnes ved løsning av et dobbeltproblem, nemlig: minimum lineær form dersom det søkes maksimum i den opprinnelige oppgaven, og maksimum hvis minimum søkes i originaloppgaven. 6. Skriv ned betingelsen for ikke-negativiteten til variablene i det dobbelte problemet. Eksempel 5.1. Lag et problem dual til følgende: finn maksimum av en funksjon under begrensningene Den tredje ulikheten i systemet (*) tilfredsstiller ikke paragraf 1 i reglene for å sette sammen et dobbeltproblem. Så la oss gange det med –1: For å lette utarbeidelsen av et dobbeltproblem, er det bedre å bruke den utvidede matrisen B, der vi, sammen med koeffisientene for variablene til systemet med begrensninger for det opprinnelige problemet, skriver ned de frie termene og koeffisientene for variablene i lineær form, uthever en ekstra kolonne og rad for dette formålet. Vi transponerer matrisen B, og ved å bruke den transponerte matrisen B / komponerer vi en oppgave dual til denne. Det doble problemet reduserer til å finne minimum av en funksjon under begrensningene Grunnleggende dualitetsteoremer Teorien om dualitet i lineær programmering er basert på følgende grunnleggende teoremer. Teorem 1. Hvis et av de lineære programmeringsproblemene har et endelig optimum, har dets dual også et endelig optimum, og de optimale verdiene for de lineære formene til begge oppgavene faller sammen, dvs. F max = Zmin
eller F min = Z maks.
Hvis den lineære formen til et av de doble problemene ikke er begrenset, er betingelsene for det andre problemet motstridende. Før vi formulerer neste teorem, la oss etablere samsvar mellom variablene i den opprinnelige og duale oppgaven. Når du løser det opprinnelige problemet ved hjelp av simpleksmetoden, for å redusere systemet med ulikheter til dets ekvivalente ligningssystem, er det nødvendig å introdusere m ekstra ikke-negative variabler (i henhold til antall ulikheter i systemet av begrensninger) der i =
1, 2,…,t betyr nummeret på ulikheten som tilleggsvariabelen ble introdusert i. Systemet med begrensninger for det doble problemet består av n ulikheter som inneholder m variabler. Hvis du løser dette problemet ved å bruke simpleksmetoden, bør du introdusere n ekstra ikke-negative variabler der j = 1, 2,...,m betyr nummeret på ulikhetssystemet av begrensninger for det dobbelte problemet der tilleggsvariabelen Ble introdusert. La oss etablere følgende korrespondanse mellom variablene i de originale og doble oppgavene: Med andre ord, hver innledende variabel Teorem 2 .
Komponentene til den optimale løsningen på ett av problemene (direkte eller doble) er lik de absolutte verdiene av koeffisientene for de tilsvarende variablene i uttrykket av den lineære formen til det andre problemet (dobbelt eller direkte) når det når det er optimalt og forutsatt at den resulterende optimale løsningen ikke er degenerert. Fra setning 1 og 2 følger det at hvis du løser ett av de gjensidige doble problemene, det vil si finner dens optimale løsning og det optimale for den lineære formen, så kan du skrive ned den optimale løsningen og det optimale for den lineære formen til annet problem. Eksempel 5.2. Bruk simpleksmetoden for å løse de direkte og doble problemene gitt i forrige eksempel. Løsning av det direkte problemet. La oss redusere systemet med ulikhetsbegrensninger (se s. 268) til et system av ligninger ved å introdusere ikke-negative tilleggsvariabler: Vi vil ta tilleggsvariablene x 3, x 4, x 5, x 6 som hovedvariablene i det første trinnet i løsningen. 1 trinn. Hovedvariabler: x 3, x 4, x 5, x 6; ikke-hovedvariabler: x 1, x 2. La oss uttrykke hovedvariablene i form av ikke-grunnleggende (vi vurderer ikke den lineære formen på dette løsningstrinnet, siden den tilsvarende grunnleggende løsningen ikke er tillatt): For å få en tillatt grunnløsning, transformerer vi variabelen til grunnleggende. Vi finner = min (2/1; ∞; 1/1; 5/1) = 1. I dette tilfellet er variabelen x 5 går inn i ikke-kjerne. Steg 2. Hovedvariabler: x 1, x 3, x 4, x 6 ikke-hovedvariabler; x 2, x 5. La oss uttrykke hovedvariablene og lineær form i form av ikke-grunnleggende: La oss konvertere den til hovedvariabelen x 5. Troende x 5=min (∞; 1/1; ∞; 4/1) = 1, konkluderer vi med at variabelen x 3 må konverteres til ikke-primær. Trinn 3. Hovedvariabler: x 1, X 4, x 5, x 6, mindre variabler x 3, x 2. Vi har Variabelen x 2 konverteres til basic. Finn x 2 = min (∞; ∞;∞; 1/1)=1. Da blir variabelen x 6 ikke-primær. Trinn 4. Hovedvariabler: x 1, x 2, X 4, x 5, ; ikke-hovedvariabler: x 2, x 6. Vi har Optimalitetskriteriet er oppfylt. Den optimale løsningen har formen (4; 1; 0; 5; 4; 0); med denne løsningen F max = 13. Fortsettelse av eksempel 5.1. Vi reduserer systemet med begrensninger for det doble problemet til likningssystemet: Vi vil ta tilleggsvariablene y 5 y 6 som de viktigste på 1. trinn i løsningen. 1 trinn. Hovedvariabler: y 5, y 6; mindre variabler: y 1, y 2, y 3, y 4. La oss uttrykke hovedvariablene i form av ikke-grunnleggende: La oss konvertere y til hovedvariabelen 4. Vi finner y 4 = mm (3/1: 1/1 = 1. Variabelen y 6 går inn i mindre. Steg 2. Hovedvariabler: y 4, y 5 mindre variabler: y 1, y 2, y 3, y 6. Vi har La oss konvertere variabelen y 1 til grunnleggende. Siden y 1 = min (∞; 2/3) = 2/3, så blir variabelen y 5 ikke-primær. Trinn 3. Hovedvariabler y 1, y 4, mindre variabler: y 2, y 3, y 5, y 6. Siden den tilsvarende grunnleggende løsningen på problemet er tillatt, uttrykker vi ikke bare de viktigste i form av ikke-grunnleggende variabler, men også en lineær form: Optimalitetskriteriet (for tilfellet med å minimere en lineær form) er oppfylt. Den optimale løsningen har formen (2/3; 0; 0; 7/3; 0; 0), med Z min = 13. Etter å ha løst det dobbelte problemet, er vi overbevist om gyldigheten av den første delen av setning 1: det dobbelte problemet har også et endelig optimum, og Z min. =
=F maks = 13. La oss forsikre oss om at utsagnet i setning 2 også er sant. For å gjøre dette, skriver vi ned variablene til de direkte og doble problemene, og opprettholder korrespondansen deres. La oss uttrykke den lineære formen oppnådd i det siste trinnet for å løse det doble problemet i form av alle variablene i dette problemet: Vurdere koeffisientene til variablene y j i denne lineære formen og tar i betraktning deres samsvar med koeffisientene til variablene xi, vi får en løsning (4; 1; 0; 5; 4; 0), sammenfallende med den optimale løsningen av det direkte problemet. Kommentar. Etter å ha løst det direkte problemet, kan du umiddelbart få en løsning på det doble problemet. Hvis vi uttrykker den lineære formen F oppnådd på det fjerde trinnet for å løse det direkte problemet i form av alle variablene i dette problemet, får vi Basert på setning 2, tar vi hensyn til samsvaret mellom variablene i de direkte og doble problemene og tar den absolutte verdien av koeffisientene til variablene, finner vi den optimale løsningen på det doble problemet (2/3; 0; 0; 7 /3; 0; 0). I dette tilfellet er Z min = F maks = 13. 6 TRANSPORTPROBLEM Et lineært programmeringsproblem (LPP) er problemet med å finne den største (eller minste) verdien av en lineær funksjon på et konveks polyedrisk sett. Simplexmetoden er en metode for å løse et lineært programmeringsproblem. Essensen av metoden er å finne en innledende gjennomførbar plan, og deretter forbedre planen inntil maksimal (eller minimum) verdi av den objektive funksjonen i et gitt konveks polyedrisk sett er oppnådd eller problemets uløselighet er bestemt. Vurder følgende lineære programmeringsproblem i kanonisk form: Som vist ovenfor, for et problem skrevet i kanonisk form, hvis blant kolonnevektorene til matrisen EN Det er m enhet og lineært uavhengig, kan du direkte spesifisere referanseplanen. Imidlertid, for mange lineære programmeringsproblemer skrevet i kanonisk form og med referanseplaner, blant kolonnevektorene i matrisen EN ikke alltid tilgjengelig m enhet og lineært uavhengig. Vurder følgende problem: Anta at vi må finne maksimum av en funksjon under forhold hvor er de første n elementer er null. Variabler danne et såkalt kunstig grunnlag m-dimensjonalt vektorrom. Siden det utvidede problemet har en referanseplan, kan løsningen bli funnet ved simpleksmetoden. Teorem 4. Hvis i den optimale planen Således, hvis i den funnet optimale planen for det utvidede problemet, verdiene til de kunstige variablene er lik null, oppnås den optimale planen for det opprinnelige problemet. La oss dvele mer detaljert på å finne en løsning på det utvidede problemet. Verdien av målfunksjonen for referanseplanen (27): Det merker vi F(X) og består av to uavhengige deler, hvorav den ene er avhengig av M, og den andre - nei. Etter utregning F(X) og deres verdier, så vel som de første dataene for den utvidede oppgaven, legges inn i en simplekstabell, som vist ovenfor. Den eneste forskjellen er at denne tabellen inneholder en rad mer enn en vanlig simplekstabell. Samtidig i ( m Den +1)te linjen inneholder koeffisienter som ikke inneholder M, og i ( m+2) linje − koeffisienter for M. Når du flytter fra en referanseplan til en annen, vil en vektor som tilsvarer det største negative tallet i absolutt verdi ( m+2) linjer. En kunstig vektor ekskludert fra grunnlaget gir ikke mening å bli gjeninnført i grunnlaget. Ved flytting til annen referanseplan kan det skje at ingen av de kunstige vektorene utelukkes fra grunnlaget. Omberegning av simplekstabellen ved flytting fra en referanseplan til en annen utføres i henhold til de vanlige reglene for simpleksmetoden (se ovenfor). Den iterative prosessen utføres iht m+2 linje så lang som elementer m+2 linjer som tilsvarer variabler m+2 rader, kolonner x 0 er negativ, så har det opprinnelige problemet ingen løsning. Hvis ikke alle kunstige variabler er ekskludert fra grunnlaget og elementet m+2 rader, kolonner x 0 er lik null, da er referanseplanen til det opprinnelige problemet degenerert og grunnlaget inneholder minst én av vektorene til det kunstige grunnlaget. Hvis den opprinnelige oppgaven inneholder flere enhetsvektorer, bør de inkluderes i det kunstige grunnlaget. Hvis under iterasjoner m+2-linjen inneholder ikke lenger negative elementer, deretter fortsetter iterasjonsprosessen med m+1 linje, til den optimale planen for det utvidede problemet er funnet eller problemets uløselighet avsløres. Dermed inkluderer prosessen med å finne en løsning på det lineære programmeringsproblemet (21)-(23) ved bruk av den kunstige basismetoden følgende hovedstadier: For å løse lineære programmeringsproblemer online, bruk en kalkulator La oss vurdere det viktigste lineære programmeringsproblemet (LPLP): finn ikke-negative verdier av variablene x1, x2, ..., xn, som tilfredsstiller m betingelser - likheter og maksimere den lineære funksjonen til disse variablene For enkelhets skyld antar vi at alle betingelser (1) er lineært uavhengige (r=m), og vi vil føre resonnementet vårt under denne forutsetningen. La oss kalle en tillatt løsning av OLP ethvert sett med ikke-negative verdier x1, x2, ..., xn som tilfredsstiller betingelsene (1). La oss kalle optimal den av de tillatte løsningene som maksimerer funksjonen (2). Vi må finne den optimale løsningen. Har dette problemet alltid en løsning? Nei ikke alltid. ZLP er uløselig (har ikke en optimal løsning): På grunn av inkompatibiliteten til restriksjonssystemet. De. systemet har ikke en eneste løsning, som vist i figur 1. Figur 1 - Inkonsekvens av restriksjonssystemet På grunn av den ubegrensede objektivfunksjonen på settet med løsninger. Med andre ord, når du løser LLP ved maks, har verdien av objektivfunksjonen en tendens til uendelig, og i tilfelle av LLP ved min - til minus uendelig, som vist i figur 2. Figur 2 - Uavgrensning av objektivfunksjonen på settet med løsninger ZLP er løsbar: Settet med løsninger består av ett enkelt punkt. Det er også optimalt, som vist i figur 3. Figur 3 - Settet med løsninger består av ett punkt Den eneste optimale løsningen på ZLP. Den rette linjen som tilsvarer objektivfunksjonen ved grenseposisjonen skjærer med løsningssettet på ett punkt, som vist i figur 4. Figur 4 - Den eneste optimale løsningen Den optimale løsningen til ZLP er ikke unik. Vektor N er vinkelrett på en av sidene av løsningssettet. I dette tilfellet er et hvilket som helst punkt på segmentet AB optimalt, som vist i figur 5. Figur 5 - Den optimale løsningen er ikke unik Simplexmetoden er en algoritme for å løse et LP-problem som implementerer oppregning av hjørnepunktene i regionen med gjennomførbare løsninger i retning av å forbedre verdien av objektivfunksjonen C. Simplexmetoden er den viktigste innen lineær programmering. Bruken av denne metoden i et avgangsprosjekt for å løse LP-problemet skyldes følgende faktorer: Metoden er universell, anvendelig for ethvert lineært programmeringsproblem i kanonisk form; Metodens algoritmiske natur gjør at den kan programmeres og implementeres på en vellykket måte ved hjelp av tekniske midler. Det ytterste av målfunksjonen nås alltid ved hjørnepunktene i regionen med gjennomførbare løsninger. Først og fremst er det funnet en gjennomførbar innledende (referanse)løsning, dvs. ethvert hjørnepunkt i regionen med gjennomførbare løsninger. Fremgangsmåten for metoden lar deg svare på spørsmålet om denne løsningen er optimal. Hvis "ja", er problemet løst. Hvis "nei", foretas en overgang til det tilstøtende hjørnepunktet i regionen med gjennomførbare løsninger, hvor verdien av målfunksjonen forbedres. Prosessen med å telle opp hjørnepunktene i regionen med mulige løsninger gjentas inntil et punkt er funnet som tilsvarer ytterpunktet til den objektive funksjonen. Siden antall toppunkter i polyederet er begrenset, er det garantert å finne den optimale verdien i et begrenset antall trinn eller fastslå at problemet er uløselig. Systemet med begrensninger her er et system med lineære ligninger der antallet ukjente er større enn antallet ligninger. Hvis rangeringen av systemet er lik, er det mulig å velge ukjente som uttrykkes i form av de gjenværende ukjente. For å være sikker, antas det vanligvis at de første påfølgende ukjente er valgt. Disse ukjente (variablene) kalles grunnleggende, resten er gratis. Antall grunnleggende variabler er alltid lik antall begrensninger. Ved å tilordne visse verdier til frie variabler og beregne verdiene til de grunnleggende (uttrykt i form av frie), oppnås ulike løsninger på systemet med begrensninger. Av spesiell interesse er løsningene som oppnås i tilfellet når de frie variablene er lik null. Slike løsninger kalles grunnleggende. En basisløsning kalles en tillatt grunnløsning eller støtteløsning hvis verdiene til dens variabler er ikke-negative. Den oppfyller alle begrensninger. Ved å ha et system med begrensninger, finnes enhver grunnleggende løsning på dette systemet. Hvis den første grunnleggende løsningen som ble funnet viser seg å være gjennomførbar, sjekkes den for optimalitet. Dersom det ikke er optimalt, så gjøres en overgang til en annen gjennomførbar grunnløsning. Simplexmetoden garanterer at med denne nye løsningen vil den lineære formen, hvis den ikke når det optimale, nærme seg den. Det samme gjør de med den nye gjennomførbare basisløsningen til de finner en løsning som er optimal. Hvis den første basisløsningen som ble funnet viser seg å være uakseptabel, vil man ved hjelp av simpleksmetoden gå over til andre basisløsninger, inntil den grunnleggende løsningen ved et eller annet løsningstrinn viser seg å være akseptabel, eller det kan trekkes en konklusjon om inkonsekvensen. av restriksjonssystemet. Dermed er bruken av simpleksmetoden delt inn i to stadier: Å finne en akseptabel grunnleggende løsning på et system av begrensninger eller fastslå dets inkonsekvens; Å finne den optimale løsningen når det gjelder kompatibilitet av systemet med begrensninger. Algoritmen for å gå til neste mulige løsning er som følger: I linjen med koeffisienter til objektivfunksjonen velges det minste negative tallet når man finner maksimum. Serienummeret til koeffisienten er . Hvis det ikke er noen, er den opprinnelige grunnløsningen optimal; Blant elementene i matrisen med kolonnenummeret (denne kolonnen kalles den ledende eller løsende kolonnen), velges positive elementer. Hvis det ikke er noen, er den objektive funksjonen ubegrenset i området av tillatte verdier for variablene, og problemet har ingen løsninger; Blant de valgte elementene i den ledende kolonnen i matrisen, velges den som verdien av forholdet mellom den tilsvarende frie termen til dette elementet er minimal. Dette elementet kalles ledende, og linjen det er plassert i kalles ledende; Grunnvariabelen som tilsvarer raden til det ledende elementet skal overføres til kategorien fri, og den frie variabelen som tilsvarer kolonnen til det ledende elementet må legges inn i antallet grunnleggende. En ny løsning er konstruert som inneholder nye antall grunnleggende variabler. Betingelse for optimaliteten til planen når du løser problemet maksimalt: det er ingen negative elementer blant koeffisientene til målfunksjonen. Produksjonsledelse innebærer konstant beslutningstaking. Hver beslutning som tas er valgt fra et visst sett med mulige alternativer. Ledelsesoppgaven i dette tilfellet er å velge den optimale løsningen, det vil si den løsningen som i henhold til visse egenskaper er å foretrekke fremfor andre. En beslutning vil anses som optimal hvis den fører til størst mulig positiv effekt (for eksempel en økning i foretakets overskudd). En av metodene som lar deg finne den optimale løsningen blant hele settet med gjennomførbare løsninger er operasjonsforskning. Operasjonsforskning er en av grenene til anvendt matematikk, hvis essens er å finne maksimum (minimum) av den objektive funksjonen, tatt i betraktning alle eksisterende begrensninger. Essensen av bedriftsøkonomi er å maksimere fortjenesten, tatt i betraktning de begrensede ressursene som er tilgjengelige for organisasjonen. Dette bestemmer anvendeligheten av operasjonsforskningsmetoder for å løse problemer med å organisere produksjonsprosessen i en bedrift. I bedriftsøkonomi kalles slike oppgaver problemer med ressursfordeling(eller optimaliseringsproblemer). La oss se på et eksempel på hvordan operasjonsforskningsmetoder kan brukes for å løse produksjonsproblemer og hvordan denne prosessen kan akselereres ved å bruke innebygde evner MS Excel. La oss anta at et bilservicefirma har utviklet sesongmessige insentiver for kunder, hvor essensen er at kunden, etter å ha betalt et fast beløp, mottar en hel pakke med tjenester for å forberede bilen til sommersesongen. Totalt tilbudt til kunder to typer tjenestepakker: 1) pakke" Rent glass» koster 3600 rubler, som inkluderer et sett med arbeider for diagnostisering og inspeksjon av bilen, rengjøring av den indre overflaten av bilvinduene med en spesiell spray (pluss en flaske spray som gave); fylle spylerreservoaret med vindusrensevæske (pluss en flaske vindusrensevæske som gave); 2) pakke " Frisk luft» koster 4300 rubler, som inkluderer et sett med arbeider for diagnostisering og inspeksjon av bilen, inkludert rengjøring og desinfeksjon av bilens klimaanlegg ved hjelp av et spesialprodukt; rengjøring av den indre overflaten av bilvinduene ved hjelp av en spesiell spray; Fylle spylerreservoaret med vindusrensevæske. I tabellen 1 presenterer et sett med arbeider for diagnostisering og inspeksjon av en bil (antall standardtimer). Tabell 1. Sett med arbeider for kjøretøydiagnostikk og inspeksjon (antall standardtimer) Jobb Plastpose "Rent glass" Plastpose "Frisk luft" Kontrollerer motoroljenivået Kontrollerer kjølevæskenivået og tettheten Kontrollerer bremsevæskenivået Kontroller tilstanden til kabinfilteret Visuell inspeksjon av enhetenes tetthet Visuell kontroll av tilstanden til bremseskiver og -klosser Kontrollerer bremsesystemet på en testbenk Justering av dekktrykket Funksjonstest av vindusviskere og -vaskere Sjekk gummiviskerbladene for slitasje og sprekker Kontrollerer tilstanden til kjøleradiatoren for forurensning Kontroll og justering av frontlykter Kontrollerer batteriladingen Kort test med diagnoseprogram Rengjøring og desinfisering av klimaanlegget Total Dermed skiller disse to servicepakkene seg fra hverandre ved at den første pakken i tillegg inkluderer en gave i form av en flaske spray for innvendig glassrengjøring og en flaske vindusrensevæske, og den andre pakken inkluderer rengjøring og desinfeksjon av luften balsam ved hjelp av et spesialprodukt. Gjennomføring av sesongbaserte kampanjer lar en bedrift bestemme en hel rekke oppgaver: 1. Tiltrekke kunder. 2. Salg av bedervede sesongvarer (autokjemikalier). 4. Motta tilleggsfortjeneste. Ifølge organisasjonens ledelse er antall pakker begrenset: for det første, kampanjen vil fortsette til beholdningen av de autokjemiske varene som deltar i kampanjen er tom; for det andre, kampanjeperioden er begrenset til én måned (april); For det tredje, kan bare fire mekanikere være involvert i å utføre serviceaktiviteter. Dermed er ressursene som er avsatt til å gjennomføre denne aksjonen begrenset. Ressursbegrensninger for å holde en sesongbasert kampanje er presentert i tabell. 2. Tabell 2. Ressursbegrensninger for gjennomføring av sesongopprykk Ressurser involvert Ressursforbruk Lager ressurser plastpose "Rent glass" plastpose "Frisk luft" Mekanikerarbeid, h Spray for rengjøring av innsiden av glass, pakk. Vindusspylervæske, pakke. Væske for rengjøring og desinfisering av klimaanlegg, pakke. For en sesongbasert kampanje ikke mer enn det som kan tildeles: I tillegg er arbeidstiden til mekanikere begrenset: i april er det 22 arbeidsdager, en produktiv arbeidsdag for en mekaniker er 7 timer om dagen. Derfor er tilgjengelig arbeidstid for fire mekanikere 616 timer (4 × 22 × 7). Bare for en pakke" Rent glass» det er nødvendig å bruke: Per pakke" Frisk luft» det er nødvendig å bruke: Ressursbegrensning er en av betingelsene foren. Karakteristisk trekk Driftsforskning er en systemtilnærming. I denne forbindelse kan eksisterende ressursbegrensninger representeres som et system av ligninger. Først, la oss introdusere litt notasjon for variablene i problemet vårt: X 1 - antall "Clean Glass"-pakker; X 2 — antall "Fresh Air"-pakker; EN— antall mekanikertimer; B— antall sprayflasker for innvendig glassrengjøring; C— antall flasker med spylervæske; D— antall flasker med væske for rengjøring og desinfisering av klimaanlegg. 1) for det første kan antallet pakker ikke være negativt: X1, X2 ≥ 0; 2) For det andre bør ressursforbruket ikke overstige tilgjengelige reserver. Dette kan uttrykkes ved å bruke ulikheter: etter ressurs EN: 2,5× X 1 + 3,6 × X 2 ≤ 616; etter ressurs I: 2 × X 1+1× X 2 ≤ 320; etter ressurs MED: 2 × X 1+1× X 2 ≤ 260; etter ressurs D: 0 × X 1+1× X 2 ≤ 150. Da bør du bestemme deg målfunksjon(retning for optimalisering). Det vil være logisk å fordele kvoten for levering av tjenestepakker på en slik måte at bedriften får maksimal fortjeneste. For å gjøre dette må du beregne hvor mye fortjeneste salget av en tjenestepakke gir, det vil si sammenligne salgsprisen på pakken og kostnadene for ressursene som er brukt. Som nevnt ovenfor er kostnaden for "Clean Glass" -pakken 3600 rubler, og " Frisk luft» — 4300 gni. Disse beløpene må sammenlignes med kostnader ved å utføre tjenester: Mekanikerens timepris er 350 rubler. per standard time (inkludert skatter og lønnsbidrag); kostnaden for en flaske væske for rengjøring av den indre overflaten av glass er 661 rubler; kostnaden for en flaske vindusrensevæske er 250 rubler; kostnaden for en flaske væske for rengjøring og desinfisering av klimaanlegg er 1 589 rubler. Beregning av fortjeneste fra salg av hver pakke basert på tilgjengelige data er presentert i tabell. 3. Tabell 3. Fortjeneste ved salg av servicepakker, gni. Ressurs Ressurspris Plastpose "Rent glass" Plastpose "Frisk luft" Mekaniske arbeidskostnader Kostnad for glassrengjøringsspray Spylervæske koster Kostnader for væske for rengjøring og desinfisering av klimaanlegget Totale pakkekostnader Pakkekostnad Fortjeneste på salg av pakken Så, selger en pakke " Rent glass» vil bringe selskapet 903 rubler. profitt og pakken " Frisk luft» — 540 gni. Objektiv funksjon (Z) i dette tilfellet vil ta formen. Innen teknologi optimal(alternativ, beslutning, valg, etc.) - den beste (alternativ, beslutning, valg, ...) blant de som er akseptable hvis det er en regel om preferanse for den ene fremfor den andre. Denne regelen kalles et optimalitetskriterium, og kvalitetsindikatorer vil tjene som et mål på preferanse. Vi kan snakke om det optimale alternativet bare hvis to betingelser er oppfylt: Hvert valg av det beste alternativet er spesifikt, siden det er laget i henhold til visse kriterier. Derfor, når du snakker om det optimale alternativet, må du alltid angi disse kriteriene (det vil si "optimal i henhold til ..."). Og det som kan være optimalt under ett kriterium, vil ikke nødvendigvis være det under et annet. For eksempel, en scene som er "optimal i området" vil ikke nødvendigvis være "optimal i akustikk." Den optimale løsningen er resultatet av en av valgtypene (kriterievalg). Operasjonsforskningsteori og beslutningsteori studerer problemene knyttet til å velge optimale beslutninger. Wikimedia Foundation. 2010. Optimal løsning- en løsning som minimerer eller maksimerer (avhengig av problemets art) kvalitetskriteriet til optimaliseringsmodellen (optimalitetskriteriet) under gitte forhold og begrensninger presentert i denne modellen. Men… … Økonomisk og matematisk ordbok optimal løsning- En løsning som minimerer eller maksimerer (avhengig av problemets art) kvalitetskriteriet til optimaliseringsmodellen (optimalitetskriteriet) under gitte forhold og begrensninger presentert i denne modellen. Men siden modellen aldri... ... Teknisk oversetterveiledning Optimal kontroll- Optimal kontroll er oppgaven med å designe et system som gir, for et gitt kontrollobjekt eller prosess, en kontrolllov eller en kontrollsekvens av påvirkninger som sikrer maksimalt eller minimum av en gitt ... ... Wikipedia løsning- foreta en ny beslutning handling foreta en beslutning handling foreta en beslutning handling gjennomføre en beslutningsimplementering vente på en beslutningsmodalitet, forventning avhenger beslutningssubjekt, avhengighet, grunn effekt håndtere en beslutning handling ... løsning- substantiv, s., brukt ofte Morfologi: (nei) hva? løsninger, hva? avgjørelse, (se) hva? løsning, hva? avgjørelse, om hva? om avgjørelsen; pl. Hva? løsninger, (nei) hva? beslutninger, hva? avgjørelser, (se) hva? løsninger, hva? beslutninger, om hva? om vedtak 1. Ved vedtak... Dmitrievs forklarende ordbok optimal- finne den optimale løsningen eksistens / opprettelse... Verbal kompatibilitet av ikke-objektive navn OPTIMAL POSISJONSKONTROLL- løsning av det optimale kontrollproblemet til matematisk teori, bestående i syntesen av optimal kontroll i form av en kontrollstrategi basert på tilbakemeldingsprinsippet, som en funksjon av den nåværende tilstanden (posisjonen) av prosessen (se). Siste ting… … Matematisk leksikon OPTIMAL PROGRAMVAREKONTROLL- en løsning på det optimale kontrollproblemet i matematisk teori, der kontrollhandlingen u=u(t) dannes i form av en funksjon av tid (derved antas det at under prosessen ingen annen informasjon enn den gitt ved helt begynnelsen kommer inn i systemet ... ... Matematisk leksikon Optimal planlegging- et sett med metoder og midler som lar deg velge fra en rekke mulige alternativer for utvikling av et økonomisk system alternativet som sikrer den mest effektive ressursbruken. Grunnlaget for optimal planlegging er løsningen av problemet... ... Finansiell ordbok Optimal kontroll- flyseksjon av flydynamikk, dedikert til utvikling og bruk av optimaliseringsmetoder for å bestemme lovene for kontroll av bevegelsen til flyet og dets baner, og gir maksimum eller minimum av det valgte kriteriet ... ... Encyclopedia of technology
problem x j (j = 1,2,..., n) er assosiert med tilleggsvariabelen introdusert i j - e-ulikheten til det doble problemet, og hver tilleggsvariabel i det opprinnelige problemet (i =
1,2,…,
t), introdusert i Jeg- e ulikhet i det opprinnelige problemet, er den opprinnelige variabelen til det duale problemet.
(1)
(2)
(3)
Kunstig basismetode
kalles kunstig. Vektorer kolonner
(28)
utvidet problem (24)–(26) verdier av kunstige variabler 
, Det 
er den optimale planen for problem (21)–(23).
vil ikke bli ikke-negativ. Dessuten, hvis kunstige variabler er ekskludert fra grunnlaget, tilsvarer den funnet planen for det utvidede problemet en referanseplan for det opprinnelige problemet.
Løse lineære programmeringsproblemer ved hjelp av simpleksmetoden
Notater
Se hva "Optimal løsning" er i andre ordbøker:
Bøker