Den simpleksmetoden er. Løse problemet ved hjelp av simpleksmetoden

Denne metoden er en metode for målrettet oppregning av referanseløsninger til et lineært programmeringsproblem. Den tillater, i et begrenset antall trinn, enten å finne en optimal løsning eller å fastslå at det ikke finnes noen optimal løsning.

1. Angi en metode for å finne den optimale referanseløsningen
2. Angi metoden for overgang fra en referanseløsning til en annen, hvor verdien av objektivfunksjonen vil være nærmere den optimale, dvs. angi en måte å forbedre referanseløsningen på
3. Sett kriterier som lar deg umiddelbart slutte å søke etter støtteløsninger ved den optimale løsningen eller trekke en konklusjon om fraværet av en optimal løsning.

Algoritme av simpleksmetoden for å løse lineære programmeringsproblemer

1. Bring problemet til kanonisk form
2. Finn den første støtteløsningen med en "enhetsbasis" (hvis det ikke er noen støtteløsning, har ikke problemet en løsning på grunn av inkompatibiliteten til systemet med begrensninger)
3. Beregn estimater av vektordekomponeringer basert på referanseløsningen og fyll ut tabellen for simpleksmetoden
4. Hvis kriteriet for unikheten til den optimale løsningen er oppfylt, slutter løsningen av problemet
5. Hvis betingelsen for eksistensen av et sett med optimale løsninger er oppfylt, blir alle optimale løsninger funnet ved enkel oppregning

Et eksempel på å løse et problem ved hjelp av simpleksmetoden

Løs problemet ved å bruke simpleksmetoden:

Løsning:

Vi bringer problemet til kanonisk form.

For å gjøre dette introduserer vi en ekstra variabel x 6 med koeffisient +1 til venstre side av den første ulikhetsbegrensningen. Variabelen x 6 er inkludert i objektivfunksjonen med en koeffisient på null (dvs. den er ikke inkludert).

Vi får:

Vi finner den første støtteløsningen. For å gjøre dette, likestiller vi frie (uløste) variabler til null x1 = x2 = x3 = 0.

Vi får referanseløsning X1 = (0,0,0,24,30,6) med enhetsbasis B1 = (A4, A5, A6).

Vi beregner estimater av vektornedbrytninger forhold på grunnlag av referanseløsningen i henhold til formelen:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vektor av koeffisienter til objektivfunksjonen for de grunnleggende variablene
• X k = (x 1k, x 2k, ..., x mk) - ekspansjonsvektor for den tilsvarende vektoren A k i henhold til grunnlaget for referanseløsningen
• C k er koeffisienten til objektivfunksjonen for variabelen x k.

Estimatene for vektorene som inngår i grunnlaget er alltid lik null. Referanseløsningen, ekspansjonskoeffisienter og estimater for utvidelser av tilstandsvektorer basert på referanseløsningen skrives inn simplex bord:

Øverst i tabellen, for å lette beregningen av estimater, er koeffisientene til objektivfunksjonen skrevet. I første kolonne "B" er vektorene som er inkludert i grunnlaget for referanseløsningen skrevet. Rekkefølgen som disse vektorene er skrevet tilsvarer antallet tillatte ukjente i begrensningsligningene. I den andre kolonnen i tabellen "C b" er koeffisientene til objektivfunksjonen for de grunnleggende variablene skrevet i samme rekkefølge. På riktig plassering Koeffisientene til objektivfunksjonen i kolonnen "C b" i estimatet av enhetsvektorene som er inkludert i grunnlaget, er alltid lik null.

I den siste raden i tabellen med estimater av Δ k i kolonnen "A 0" er verdiene til objektivfunksjonen på referanseløsningen Z(X 1) skrevet.

Den initiale støtteløsningen er ikke optimal, siden i maksimalproblemet er estimatene Δ 1 = -2, Δ 3 = -9 for vektorene A 1 og A 3 negative.

I følge teoremet om å forbedre støtteløsningen, hvis i et maksimalt problem minst én vektor har et negativt estimat, kan du finne en ny støtteløsning der verdien av objektivfunksjonen vil være større.

La oss bestemme hvilken av de to vektorene som vil føre til en større økning i objektivfunksjonen.

Økningen til målfunksjonen finner du av formelen: .

Vi beregner verdiene til parameteren θ 01 for den første og tredje kolonnen ved å bruke formelen:

Vi får θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (tabell 26.1).

Vi finner økningen av objektivfunksjonen når vi innfører den første vektoren ΔZ 1 = - 6*(- 2) = 12, og den tredje vektoren ΔZ 3 = - 3*(- 9) = 27 i basisen.

Følgelig, for en raskere tilnærming til den optimale løsningen, er det nødvendig å introdusere vektor A3 i grunnlaget for referanseløsningen i stedet for den første vektoren av basis A6, siden minimum av parameteren θ 03 oppnås i den første raden ( l = 1).

Vi utfører Jordan-transformasjonen med elementet X13 = 2, vi får den andre referanseløsningen X2 = (0,0,3,21,42,0) med basis B2 = (A3, A4, A5). (Tabell 26.2)

Denne løsningen er ikke optimal, siden vektor A2 har et negativt estimat Δ2 = - 6. For å forbedre løsningen er det nødvendig å introdusere vektor A2 i grunnlaget for referanseløsningen.

Vi bestemmer nummeret på vektoren utledet fra grunnlaget. For å gjøre dette, beregner vi parameteren θ 02 for den andre kolonnen, den er lik 7 for l = 2. Følgelig utleder vi den andre basisvektoren A4 fra basisen. Vi utfører Jordan-transformasjonen med elementet x 22 = 3, vi får den tredje referanseløsningen X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabell 26.3).

Denne løsningen er den eneste optimale, siden for alle vektorer som ikke er inkludert i grunnlaget, er estimatene positive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Svar: maks. Z(X) = 201 ved X = (0,7,10,0,63).

Lineær programmeringsmetode i økonomisk analyse

Lineær programmeringsmetode gjør det mulig å rettferdiggjøre den mest optimale økonomiske løsningen under forhold med strenge restriksjoner knyttet til ressursene som brukes i produksjonen (anleggsmidler, materialer, arbeidsressurser). Bruken av denne metoden i økonomisk analyse gjør det mulig å løse problemer knyttet hovedsakelig til planlegging av aktivitetene til en organisasjon. Denne metoden hjelper med å bestemme optimale verdier produksjon, samt retningen for den mest effektive bruken av produksjonsressursene som er tilgjengelig for organisasjonen.

Ved hjelp av denne metoden løses de såkalte ekstreme problemene, som består i å finne ekstreme verdier, det vil si maksimum og minimum av funksjoner av variable mengder.

Denne perioden er basert på å løse et system av lineære ligninger i tilfeller der de analyserte økonomiske fenomenene er forbundet med en lineær, strengt funksjonell avhengighet. Den lineære programmeringsmetoden brukes til å analysere variabler i nærvær av visse begrensende faktorer.

Det er svært vanlig å løse det såkalte transportproblemet ved hjelp av den lineære programmeringsmetoden. Innholdet i denne oppgaven er å minimere kostnadene som påløper i forbindelse med driften Kjøretøy under eksisterende begrensninger med hensyn til antall kjøretøy, deres bæreevne, varigheten av deres drift, hvis det er behov for å betjene det maksimale antallet kunder.

I tillegg er denne metoden mye brukt for å løse planleggingsproblemet. Denne oppgaven består av en slik fordeling av driftstid for personellet i en gitt organisasjon som vil være mest akseptabel både for medlemmene av dette personellet og for organisasjonens klienter.

Denne oppgaven er å maksimere antallet klienter som betjenes under betingelser med begrensninger på antall tilgjengelige ansatte, samt arbeidstidsfondet.

Dermed er den lineære programmeringsmetoden veldig vanlig i analysen av plassering og bruk av ulike typer ressurser, så vel som i prosessen med å planlegge og forutse organisasjoners aktiviteter.

Ikke desto mindre kan matematisk programmering også brukes på de økonomiske fenomenene, hvor forholdet mellom disse ikke er lineært. For dette formålet kan ikke-lineære, dynamiske og konvekse programmeringsmetoder brukes.

Ikke-lineær programmering er avhengig av den ikke-lineære naturen til den objektive funksjonen eller begrensningene, eller begge deler. Formene for den objektive funksjonen og ulikhetsbegrensningene i disse forholdene kan være forskjellige.

Ikke-lineær programmering brukes i økonomisk analyse, spesielt når man etablerer forholdet mellom indikatorer som uttrykker effektiviteten til en organisasjons aktiviteter og volumet av denne aktiviteten, strukturen til produksjonskostnader, markedsforhold, etc.

Dynamisk programmering er basert på å konstruere et beslutningstre. Hvert lag i dette treet fungerer som et stadium for å bestemme konsekvensene av en tidligere beslutning og for å eliminere ineffektive alternativer for den avgjørelsen. Dermed har dynamisk programmering en flertrinns, flertrinns natur. Denne typen programmering brukes i økonomisk analyse for å finne optimale alternativer utvikling av organisasjonen både nå og i fremtiden.

Konveks programmering er en type ikke-lineær programmering. Denne typen programmering uttrykker den ikke-lineære naturen til forholdet mellom resultatene av en organisasjons aktiviteter og kostnadene. Konveks (aka konkav) programmering analyserer konvekse objektivfunksjoner og konvekse begrensningssystemer (gjennomførbarhetspunkter). Konveks programmering brukt i analyse Økonomisk aktivitet for å minimere kostnader, og konkav - for å maksimere inntekten under de eksisterende restriksjonene på virkningen av faktorer som påvirker de analyserte indikatorene på motsatt måte. Følgelig, med de typer programmering som vurderes, minimeres konvekse objektivfunksjoner, og konkave objektivfunksjoner maksimeres.

Lineær programmering er en matematisk modelleringsteknikk utviklet for å optimalisere bruken av begrensede ressurser. LP er vellykket brukt i militærfeltet, industri, jordbruk, transportnæringen, økonomi, helsevesen og til og med innen samfunnsfag. Den utbredte bruken av denne metoden støttes også av svært effektive dataalgoritmer som implementerer denne metoden. Optimaliseringsalgoritmer for andre, mer komplekse typer modeller og operasjonsforskningsproblemer (OR), inkludert heltalls-, ikke-lineær og stokastisk programmering, er basert på lineære programmeringsalgoritmer.

Optimaliseringsproblem er et økonomisk og matematisk problem som består i å finne den optimale (maksimum eller minimum) verdien av den objektive funksjonen, og verdiene til variablene må tilhøre et visst utvalg av akseptable verdier.

I sin mest generelle form er det lineære programmeringsproblemet skrevet matematisk som følger:

Hvor X = (x 1 , x 2 , ... , x n ) ; W– rekkevidde av tillatte verdier av variabler x 1 , x 2 , ... , x n ;f(X)- objektiv funksjon.

For å løse et optimaliseringsproblem er det nok å finne sin optimale løsning, dvs. indikerer det til enhver .

Et optimaliseringsproblem er uløselig hvis det ikke har en optimal løsning. Spesielt vil maksimeringsproblemet være uløselig dersom objektivet fungerer f(X) er ikke avgrenset ovenfra på det tillatte settet W.

Metoder for å løse optimaliseringsproblemer avhenger både av typen objektiv funksjon f(X), og fra strukturen til det tillatte settet W. Hvis målfunksjonen i oppgaven er en funksjon n variabler, så kalles løsningsmetodene matematiske programmeringsmetoder.

De karakteristiske trekk ved lineære programmeringsproblemer er som følger:

optimalitetsindeks f(X) er en lineær funksjon av løsningselementene X = (x 1 , x 2 , ... , x n ) ;

restriktive vilkår pålagt mulige løsninger har form av lineære likheter eller ulikheter.

Lineært programmeringsproblem kalles et operasjonsforskningsproblem, hvis matematiske modell har formen:

(2) (3) (4) (5)

I dette tilfellet, systemet med lineære ligninger (3) og ulikheter (4), (5), som bestemmer det tillatte settet med løsninger på problemet W, kalt system av restriksjoner lineære programmeringsproblemer, og en lineær funksjon f(X) kalt målfunksjon eller optimalitetskriterium .

Gyldig løsning er en samling av tall ( plan ) X = (x 1 , x 2 , ... , x n ) , som tilfredsstiller begrensningene til problemet. Optimal løsning – dette er en plan der målfunksjonen tar sin maksimale (minimum) verdi.

Hvis den matematiske modellen for et lineært programmeringsproblem har formen:

så sier de at problemet er presentert i kanonisk form .

Ethvert lineært programmeringsproblem kan reduseres til et lineært programmeringsproblem i kanonisk form. For å gjøre dette, i det generelle tilfellet, må du være i stand til å redusere maksimeringsproblemet til minimeringsproblemet; gå fra ulikhetsbegrensninger til likhetsbegrensninger og erstatte variabler som ikke overholder ikke-negativitetsbetingelsen. Å maksimere en viss funksjon tilsvarer å minimere den samme funksjonen tatt med motsatt fortegn, og omvendt.

Regelen for å bringe et lineært programmeringsproblem til kanonisk form er som følger:

hvis det i det opprinnelige problemet er nødvendig å bestemme maksimum av en lineær funksjon, bør du endre tegnet og se etter minimum av denne funksjonen;

hvis høyre side av restriksjonene er negativ, bør denne begrensningen multipliseres med -1;

hvis det er ulikheter mellom restriksjonene, blir de forvandlet til likheter ved å introdusere ytterligere ikke-negative variabler;

hvis noen variabel x j har ingen fortegnsbegrensninger, så erstattes den (i objektivfunksjonen og i alle begrensninger) med differansen mellom to nye ikke-negative variabler: x 3 = x 3 + -x 3 - , Hvor x 3 + , x 3 - ≥ 0 .

Eksempel 1. Redusere det lineære programmeringsproblemet til kanonisk form:

min L = 2x 1 + x 2 -x 3 ; 2x 2 -x 3 ≤ 5; x 1 + x 2 -x 3 ≥ -1; 2x 1 -x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

La oss introdusere utjevningsvariabler i hver ligning i systemet av begrensninger x 4 , x 5 , x 6 . Systemet vil bli skrevet i form av likheter, og i den første og tredje ligningen i systemet av begrensninger variablene x 4 , x 6 legges inn på venstre side med et "+"-tegn, og i den andre ligningen variabelen x 5 legges inn med et "-"-tegn.

2x 2 -x 3 + x 4 = 5; x 1 + x 2 -x 3 -x 5 = -1; 2x 1 -x 2 + x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

De frie leddene i den kanoniske formen må være positive; for å gjøre dette, multipliser de to siste ligningene med -1:

2x 2 -x 3 + x 4 = 5; -x 1 -x 2 + x 3 + x 5 = 1; -2x 1 + x 2 -x 6 = 3.

Enkel metode for å løse lineære programmeringsproblemer.

Simplexmetodealgoritmen finner den optimale løsningen ved å vurdere et begrenset antall mulige grunnløsninger. Simplexmetodealgoritmen starter alltid med en gjennomførbar basisløsning og prøver deretter å finne en annen gjennomførbar basisløsning som "forbedrer" verdien av objektivfunksjonen. Dette er bare mulig hvis en økning i en hvilken som helst null (ikke-grunnleggende) variabel fører til en forbedring i verdien av målfunksjonen. Men for at en ikke-grunnvariabel skal bli positiv, må en av de aktuelle grunnvariablene settes til null, dvs. konvertere til ikke-grunnleggende. Dette er nødvendig for at den nye løsningen skal inneholde nøyaktig m grunnleggende variabler. I samsvar med terminologien til simpleksmetoden kalles den valgte nullvariabelen input (til grunnlaget), og basisvariabelen som skal slettes er ekskludert (fra grunnlaget).

La oss kalle to regler for valg av input- og eksklusjonsvariabler i simpleksmetoden optimalitetstilstand Og adgangsbetingelse . La oss formulere disse reglene og også vurdere sekvensen av handlinger som utføres når du implementerer simpleksmetoden.

Optimalitetstilstand. Inndatavariabelen i maksimerings- (minimerings)problemet er en ikke-grunnleggende variabel som har den største negative (positive) koeffisienten i mål-linje. Hvis i mål-line inneholder flere slike koeffisienter, så gjøres valget av den angitte variabelen vilkårlig. Den optimale løsningen oppnås når mål-linje vil alle koeffisienter for ikke-grunnleggende variable være ikke-negative (ikke-positive).

Tillatte vilkår. I både maksimerings- og minimeringsproblemene velges basisvariabelen der forholdet mellom verdien av høyre side av begrensningen og den positive koeffisienten til den ledende kolonnen er minimal, som den ekskluderte. Hvis det er flere grunnleggende variabler med denne egenskapen, er valget av den ekskluderte variabelen vilkårlig.

La oss presentere en algoritme for å løse et lineært programmeringsproblem for å finne et maksimum ved å bruke simplekstabeller.

F = с 1 x 1 +с 2 x 2 +…+с n x n maks

x 1 0, x 2 0,..., x n 0.

1. trinn. Vi introduserer tilleggsvariabler og skriver det resulterende likningssystemet og lineær funksjon i form av et utvidet system.

F–c 1 x 1 –c 2 x 2 –...–c n x n =0=c p.

2. trinn. Vi komponerer den innledende simplekstabellen.

3. trinn. Vi sjekker oppfyllelsen av optimalitetskriteriet - tilstedeværelsen av negative koeffisienter i siste linje. Hvis det ikke er noen, er løsningen optimal og F * =co o, de grunnleggende variablene er lik de tilsvarende koeffisientene b j, de ikke-grunnleggende variablene er lik null, dvs. X * =(b 1,b 2,..., b m, 0,..., 0).

4. trinn. Hvis optimalitetskriteriet ikke er oppfylt, bestemmer den største absolutte negative koeffisienten i den siste (estimerte) raden løsningskolonnen s.

For å bestemme oppløsningslinjen beregner vi evalueringsforholdene og fyll ut den siste kolonnen i tabellen.

Det estimerte forholdet til den i-te raden er

 hvis b i og a er har forskjellige tegn;

 hvis b i =0 og a er<0;

 hvis a er =0;

0 hvis bi =0 og a er >0;

I kolonnen med evaluerende relasjoner finner vi minimumselementet min som definerer aktiveringsstrengen g.

Hvis det ikke er noe minimum, har ikke problemet et endelig optimum I og er uløselig.

I skjæringspunktet mellom den løsende raden og kolonnen er det et løsende element a gs.

5. trinn. La oss bygge følgende tabell. For dette

La oss gå videre til det tredje trinnet.

M-metode Noen ganger, når man løser en ZLP, har ikke matrisen av koeffisienter for ukjente systembegrensninger enhetskolonner som en enhetsmatrise kan komponeres fra, dvs. det oppstår et problem ved valg av basisvariabler, eller den første løsningen er uakseptabel. I slike tilfeller bruk kunstig basismetode (M - metode). I alle restriksjoner der det ikke er noen grunnleggende variabler, kunstige variabler. Kunstige variabler introduseres i objektivfunksjonen med en koeffisient (- M) for problemer med maks og med en koeffisient (+ M) for problemer med min, der M er et tilstrekkelig stort positivt tall. Deretter løses det utvidede problemet ved å bruke reglene for simpleksmetoden. Hvis alle kunstige variabler er lik null, dvs. er utelukket fra grunnlaget, vil enten en optimal løsning på det opprinnelige problemet oppnås, eller det opprinnelige problemet løses videre og dets optimale løsning er funnet eller dets uløselighet etableres. Hvis minst en av de kunstige variablene viser seg å være forskjellig fra null, har det opprinnelige problemet ingen løsning

For å la appleten kjøre på datamaskinen din, må du gjøre følgende - klikk Start>Kontrollpanel>Programmer>Java. I Java-kontrollpanelvinduet velger du kategorien Sikkerhet, klikker på Rediger nettstedsliste-knappen, legg til-knappen og limer inn banen til denne siden fra nettleserens adresselinje i det ledige feltet. Klikk deretter OK og start datamaskinen på nytt.

For å starte appleten, klikk på "Simplex"-knappen. Hvis "Simplex"-knappen ikke er synlig over denne linjen, er ikke Java installert på datamaskinen din.

Etter å ha klikket på "Simplex"-knappen, vises det første vinduet for å angi antall variabler og antall begrensninger for problemet på simplex-metoden.

Etter å ha klikket på "ok"-knappen, vises et vindu for å legge inn gjenværende data for problemet ved hjelp av simpleksmetoden: visningsmodus (desimalbrøk eller vanlig), type oppgavekriterium min eller maks, inntasting av koeffisienter for målfunksjonen og koeffisienter for systemet av begrensninger med tegnene "≤", " ≥ "eller "=", begrensninger av formen x i ≥ 0 trenger ikke å innføres, tar hensyn til dem i sin algoritme.

Etter å ha klikket på "Løs"-knappen, vises et vindu med resultatene av å løse problemet .Vinduet består av to deler, i den øvre delen er det et tekstfelt som inneholder en beskrivelse av å redusere det opprinnelige problemet til den kanoniske formen, som brukes til å kompilere den første simplekstabellen. Nederst i vinduet, i et panel med faner, er det simplekstabeller for hver iterasjon med et lite tekstfelt nederst som indikerer oppløsningskolonnen, oppløsningsraden og annen informasjon, som gjør programmet til trening. I fanen med den optimale (siste) tabellen, vises den resulterende optimale løsningen på problemet i tekstfeltet.

Send eventuelle feil du legger merke til og kommentarer på appleten til: [e-postbeskyttet] eller ring 8 962 700 77 06, noe vi vil være deg veldig takknemlig for.

M-metode program

Program for å løse et transportproblem

Her er en manuell (ikke applet) løsning av to problemer ved bruk av simpleksmetoden (lik appletløsningen) med detaljerte forklaringer for å forstå algoritmen for å løse problemene. Den første oppgaven inneholder kun ulikhetstegn «≤» (problem med utgangspunkt), den andre kan inneholde tegn «≥», «≤» eller «=» (problem med kunstig grunnlag), de løses annerledes.

Enkel metode, løse et problem med en innledende basis

1)Enkel metode for et problem med en initial basis (alle tegn på ulikhetsbegrensninger " ≤ ").

La oss skrive problemet inn kanonisk form, dvs. vi omskriver ulikhetsrestriksjonene i form av likheter, legger vi til balanse variabler:

Dette systemet er et system med en basis (grunnlag s 1, s 2, s 3, hver av dem er inkludert i bare en ligning av systemet med en koeffisient på 1), x 1 og x 2 er frie variabler. Problemer som skal løses ved hjelp av simpleksmetoden må ha følgende to egenskaper:
-systemet av begrensninger må være et likningssystem med en basis;
-frie ledd for alle ligninger i systemet må være ikke-negative.

Det resulterende systemet er et system med en basis og dets frie vilkår er ikke-negative, så simpleksmetoden kan brukes. La oss lage den første simplekstabellen (Iterasjon 0), dvs. en tabell med koeffisienter for objektivfunksjonen og et likningssystem for de tilsvarende variablene. Her betyr "BP" kolonnen med grunnleggende variabler, "Løsning" betyr kolonnen på høyre side av systemligningene. Løsningen er ikke optimal, pga det er negative koeffisienter i z-raden.

iterasjon 0

For å forbedre løsningen går vi videre til neste iterasjon og får den følgende simplekstabellen. For å gjøre dette må du velge aktiver kolonne, dvs. en variabel som vil inngå i grunnlaget ved neste iterasjon. Den velges av den største absolutte negative koeffisienten i z-raden (i maksimumsoppgaven) - i den første iterasjonen er dette x 2-kolonnen (koeffisienten -6).

Velg deretter aktiver streng, dvs. en variabel som vil forlate grunnlaget ved neste iterasjon. Det velges av det minste forholdet mellom "Beslutning"-kolonnen og de tilsvarende positive elementene i oppløsningskolonnen (kolonne "Forhold") - i den første iterasjonen er dette rad s 3 (koeffisient 20).

Permitterende element er i skjæringspunktet mellom den løsende kolonnen og den løsende raden, er dens celle uthevet i farger, den er lik 1. Derfor, ved neste iterasjon, vil variabelen x 2 erstatte s 3 i basisen. Merk at det ikke søkes etter relasjonen i z-strengen; en bindestrek "-" er plassert der. Hvis det er identiske minimale relasjoner, er noen av dem valgt. Hvis alle koeffisientene i oppløsningskolonnen er mindre enn eller lik 0, er løsningen på problemet uendelig.

La oss fylle ut følgende tabell "Iterasjon 1". Vi får det fra "Iteration 0"-tabellen. Målet med ytterligere transformasjoner er å gjøre x2-oppløsningskolonnen om til en enhetskolonne (med en i stedet for oppløsningselementet og nuller i stedet for de gjenværende elementene).

1) Beregn rad x 2 i «Iterasjon 1»-tabellen. Først deler vi alle medlemmene av oppløsningsraden s 3 i "Iteration 0"-tabellen med oppløsningselementet (det er lik 1 i dette tilfellet) i denne tabellen, vi får rad x 2 i "Iteration 1"-tabellen . Fordi det løsende elementet i dette tilfellet er lik 1, så vil rad s 3 i "Iteration 0"-tabellen falle sammen med rad x 2 i "Iteration 1"-tabellen. Rad x 2 i Iteration 1-tabellen fikk vi 0 1 0 0 1 20, de resterende radene i Iteration 1-tabellen vil bli hentet fra denne raden og radene i Iteration 0-tabellen som følger:

2) Beregning av z-raden i «Iterasjon 1»-tabellen. I stedet for -6 i den første raden (z-rad) i x2-kolonnen i Iteration 0-tabellen, skal det være en 0 i den første raden i Iteration 1-tabellen. For å gjøre dette, multipliser alle elementene i raden x 2 i tabellen "Iterasjon 1" 0 1 0 0 1 20 med 6, vi får 0 6 0 0 6 120 og legger til denne raden med den første raden (z - rad) av tabellen "Iterasjon 0" -4 -6 0 0 0 0, får vi -4 0 0 0 6 120. En null 0 vises i x 2-kolonnen, målet er oppnådd. Elementer i oppløsningskolonnen x 2 er uthevet i rødt.

3) Beregning av rad s 1 i «Iterasjon 1»-tabellen. I stedet for 1 i s 1 rad i "Iteration 0"-tabellen skal det være en 0 i "Iteration 1"-tabellen. For å gjøre dette, multipliser alle elementene i rad x 2 i tabellen "Iterasjon 1" 0 1 0 0 1 20 med -1, få 0 -1 0 0 -1 -20 og legg til denne raden med s 1 - rad av tabell "Iterasjon 0" 2 1 1 0 0 64, får vi raden 2 0 1 0 -1 44. I kolonnen x 2 får vi den nødvendige 0.

4) Beregn rad s 2 i «Iterasjon 1»-tabellen. På plass 3 i s 2 rad i tabellen "Iterasjon 0" skal det være 0 i tabellen "Iterasjon 1". For å gjøre dette, multipliser alle elementene i rad x 2 i tabellen "Iterasjon 1" 0 1 0 0 1 20 med -3, få 0 -3 0 0 -3 -60 og legg til denne raden med s 2 - rad i tabellen «Iterasjon 0» 1 3 0 1 0 72, vi får raden 1 0 0 1 -3 12. I kolonnen x 2 oppnås den nødvendige 0. Kolonnen x 2 i tabellen «Iterasjon 1» har blitt en enhet , den inneholder en 1 og resten 0.

Radene i tabellen «Iterasjon 1» er hentet av neste regel:

Ny rad = Gammel rad – (kolonnekoeffisient for gammel radoppløsning)*(Ny oppløsningsrad).

For eksempel, for en z-streng har vi:

Gammel z-streng (-4 -6 0 0 0 0)
-(-6)*Ny oppløsningslinje -(0-6 0 0 -6 -120)
=Ny z-streng(-4 0 0 0 6 120) .

For de følgende tabellene gjøres omberegningen av tabellelementer på lignende måte, så vi utelater den.

iterasjon 1

Løser kolonne x 1, løser rad s 2, s 2 går ut av grunnlaget, x 1 går inn i grunnlaget. På nøyaktig samme måte får vi de resterende simplekstabellene til vi får en tabell med alle positive koeffisienter i z-raden. Dette er et tegn på et optimalt bord.

Iterasjon 2

Løser kolonne s 3, løser rad s 1, s 1 går ut av grunnlaget, s 3 går inn i grunnlaget.

Iterasjon 3

I z-raden er alle koeffisienter ikke-negative, derfor oppnås den optimale løsningen x 1 = 24, x 2 = 16, z max = 192.

Enkel metode, løse et problem med et kunstig grunnlag

2) La oss løse problemet med et kunstig grunnlag (minst ett ulikhetsbegrensningstegn "≥" eller "=").

La oss skrive problemet i kanonisk form (i form av et ligningssystem, som krever simpleksmetoden), for å gjøre dette introduserer vi to variabler x 3 ≥ 0 og x 4 ≥ 0, vi får:

Systemet med restriksjoner tilbyr bare én tillatt grunnvariabel x 4, bare den er inkludert i bare én ligning i den tredje med en koeffisient på 1, så vi legger til kunstige variable R 1 ≥ 0 og R 2 ≥ 0 til den første og andre ligningen slik at simpleksmetoden kan brukes må systembegrensningsligninger være et system med basis, dvs. i hver ligning må det være en variabel med koeffisient på 1, som er inkludert i kun én ligning av systemet, i vårt tilfelle er disse R 1, R 2 og x 4. Vi fikk den såkalte M-oppgaven:

Dette systemet er et system med basis, der R 1, R 2 og x 4 er grunnleggende variabler, og x 1, x 2 og x 3 er frie variabler, de frie leddene til alle ligninger er ikke-negative. Derfor kan simpleksmetoden brukes til å løse problemet. La oss skrive ned den innledende simplekstabellen:

iterasjon 0

Linjen «Evaluering» er lagt til i tabellen for problemer med kunstig grunnlag. Det oppnås ved å summere de tilsvarende koeffisientene til rader med kunstige variabler (R) med motsatt fortegn. Den vil være til stede i tabellen så lenge minst én av de kunstige variablene er i grunnlaget. Basert på den største modulo negative koeffisienten til "Evaluering"-linjen, bestemmes løsningskolonnen mens den er i tabellen. Når "Evaluering"-raden forlater tabellen (det er ingen kunstige variabler i grunnlaget), vil løsningskolonnen bli bestemt av z-raden, som i oppgaven med startgrunnlaget. I denne tabellen er den løsende kolonnen x 2, den er valgt basert på den største absolutte negative poengsummen (-7). Løsningsraden R 2 velges basert på det minste forholdet mellom "Løsning"-kolonnen og de tilsvarende positive elementene i løsningskolonnen, som i problemet uten kunstige variabler. Dette betyr at ved neste iterasjon vil variabelen x2 gå fra free til basic, og variabelen R2 vil gå fra basic til free. La oss skrive følgende simplekstabell:

Løser kolonne x 1, løser rad R 1, R 1 forlater grunnlaget, x 1 går inn i grunnlaget. Etter dette er det ingen kunstige variabler igjen i grunnlaget, så det er ingen "Evaluering"-linje i følgende tabell:

iterasjon 2

Deretter velges oppløsningskolonnen av z-raden. I z-raden er alle koeffisienter ikke-negative bortsett fra koeffisienten for den kunstige variabelen R 1, som ikke påvirker optimaliteten når de kunstige variablene forlater grunnlaget. Følgelig oppnås den optimale løsningen x 1 = 6/5; x 2 = 3/5; z maks = 72/5.

Spesielle tilfeller av bruk av simpleksmetoden

1) Når den rette linjen (hvis et todimensjonalt lineært programmeringsproblem vurderes, og i det generelle tilfellet et hyperplan) som representerer den objektive funksjonen er parallell med den rette linjen (hyperplanet) som tilsvarer en av ulikhetsbegrensningene (som ved optimalt punkt er oppfylt som en eksakt likhet), tar den objektive funksjonen en og er også en optimal verdi ved et visst sett med punkter på grensen til regionen med gjennomførbare løsninger. Disse løsningene kalles alternativ optimale løsninger . Tilstedeværelsen av alternative løsninger kan bestemmes ved å bruke den optimale simplekstabellen. Hvis z-raden i den optimale tabellen inneholder null koeffisienter av ikke-grunnleggende variabler, så finnes det alternative løsninger.

2) Hvis i løsningskolonnen i simplekstabellen alle koeffisientene er mindre enn eller lik null, er det umulig å velge en løsende rad, i dette tilfellet er løsningen ubegrenset.

3) Hvis begrensningene til et lineært programmeringsproblem er inkonsekvente (det vil si at de ikke kan tilfredsstilles samtidig), så har problemet ingen gjennomførbare løsninger. Denne situasjonen kan ikke oppstå hvis alle ulikhetene som utgjør restriksjonssystemet er av typen "≤" med ikke-negative høyresider, fordi i dette tilfellet kan tilleggsvariabler utgjøre en gjennomførbar løsning. For andre typer begrensninger brukes kunstige variabler. Hvis problemet har en løsning, er det i den optimale tabellen ingen kunstige variabler (R i) i grunnlaget. Hvis de er der, har problemet ingen løsninger.

Hvis du trenger å løse et lineært programmeringsproblem ved hjelp av simplekstabeller, er vår online tjeneste vil være til stor hjelp for deg. Simplexmetoden innebærer å søke sekvensielt gjennom alle toppunktene i området med akseptable verdier for å finne toppunktet der funksjonen har en ekstrem verdi. På det første trinnet finner man en løsning, som forbedres ved hvert påfølgende trinn. Denne løsningen kalles grunnleggende. Her er handlingssekvensen når du løser et lineært programmeringsproblem ved å bruke simpleksmetoden:

Første skritt. I den kompilerte tabellen må du først og fremst se på kolonnen med gratis medlemmer. Hvis det er negative elementer i det, er det nødvendig å gå til det andre trinnet, hvis ikke, så til det femte.

Andre trinn. På det andre trinnet er det nødvendig å bestemme hvilken variabel som skal ekskluderes fra grunnlaget og hvilken som skal inkluderes for å beregne simplekstabellen på nytt. For å gjøre dette, se gjennom kolonnen med frie termer og finn et negativt element i den. Linjen med et negativt element vil bli kalt ledende. I den finner vi det maksimale negative elementet i modul, den tilsvarende kolonnen er slaven. Hvis det er negative verdier blant de frie termene, men det er ingen i den tilsvarende raden, vil en slik tabell ikke ha løsninger. Variabelen i den ledende raden i kolonnen med frie termer er ekskludert fra grunnlaget, og variabelen som tilsvarer den ledende kolonnen er inkludert i grunnlaget.

Tabell 1.

Tredje trinn. I det tredje trinnet regner vi om hele simplekstabellen ved hjelp av spesielle formler; disse formlene kan sees ved hjelp av.

Fjerde trinn. Hvis det etter omberegning er negative elementer igjen i kolonnen med frie termer, gå til det første trinnet; hvis det ikke er noen, så til det femte.

Femte trinn. Har du kommet til det femte trinnet, så har du funnet en løsning som er akseptabel. Dette betyr imidlertid ikke at det er optimalt. Det vil bare være optimalt hvis alle elementene i F-strengen er positive. Hvis dette ikke er tilfelle, er det nødvendig å forbedre løsningen, for hvilken vi finner den ledende raden og kolonnen for neste omberegning ved hjelp av følgende algoritme. Til å begynne med finner vi det minste negative tallet i strengen F, unntatt funksjonsverdien. Kolonnen med dette nummeret vil være den ledende. For å finne den ledende raden finner vi forholdet mellom det tilsvarende frie leddet og elementet fra den ledende kolonnen, forutsatt at de er positive. Minimumsforholdet lar deg bestemme den ledende linjen. Vi regner om tabellen igjen ved å bruke formlene, dvs. gå til trinn 3.

>> >> >> Enkel metode

Enkel metode

Enhver løsning kan bli funnet simpleks metode. Før du bruker simpleksmetoden, bør du skrive den opprinnelige oppgaven i form av en grunnleggende lineær programmeringsoppgave, hvis den ikke har en slik form.

Simplexmetoden for å løse et lineært programmeringsproblem er basert på overgangen fra en referanseplan til en annen, der verdien av målfunksjonen øker(forutsatt at dette problemet har en optimal plan og hver av støtteplanene er ikke-degenererte). Den angitte overgangen er mulig dersom en innledende referanseplan er kjent. La oss vurdere et problem som denne planen kan skrives direkte for.

La det være nødvendig å finne maksimalverdien til funksjonen

under forhold

Her og – gitt konstante tall

Vektorformen til denne oppgaven er som følger: finn maksimum av funksjonen

under forhold

da, per definisjon, er referanseplanen referanseplanen for dette problemet (de siste komponentene i vektoren X er lik null). Denne planen bestemmes av systemet av enhetsvektorer som danner grunnlaget m- målt rom. Derfor kan hver av vektorene og også representeres som en lineær kombinasjon av vektorer på en gitt basis. La

La oss sette Siden vektorer – singel, da og

Teorem 5

(et tegn på optimalitet av referanseplanen). Grunnleggende oppgaveplan (22) – (24) er optimal hvis for enhver j

Teorem 6.

Hvis for noen j=k og det er ingen positive tall blant tallene , deretter den objektive funksjonen(22) oppgaver (22) – (24) er ikke begrenset på sine mange planer.

Teorem 7.

Hvis referanseplanen X for oppgaven (22) – (24)ikke-degenerertOg , Men blant tallenedet er positive (ikke alle), så er det en referanseplan X" slik at

De formulerte teoremene gjør det mulig å sjekke om den funnet referanseplanen er optimal og å identifisere muligheten for å gå over til en ny referanseplan.

Det er mer praktisk å studere referanseplanen for optimalitet, så vel som den videre beregningsprosessen, hvis betingelsene for problemet og de første dataene som er oppnådd etter å ha bestemt den første referanseplanen er skrevet som vist i tabell. 3.

I kolonne C 6 i denne tabellen er koeffisientene for de ukjente objektivfunksjonene skrevet, med samme indekser som vektorene til det gitte grunnlaget.

De positive komponentene i den opprinnelige referanseplanen er skrevet i kolonnen, og som et resultat av beregninger oppnås de positive komponentene i den optimale planen i den. Kolonnene med vektorer representerer koeffisientene for utvidelsen av disse vektorene til vektorene på en gitt basis.

I tabellen 3 først m rader bestemmes av de første dataene for problemet, og indikatorene for (m+1) rad beregnes. På denne linjen, i vektorkolonnen, skriv verdien av målfunksjonen som den tar for en gitt referanseplan, og i vektorkolonnen – betydning

Verdien av Z j finnes som skalarproduktet av en vektor og en vektor

Verdien er lik skalarproduktet av vektoren P 0 og vektoren:

Etter utfylling av tabell 3 kontrolleres den opprinnelige referanseplanen for optimalitet. For å gjøre dette, se gjennom elementene i den tredje raden i tabellen. Som et resultat kan ett av følgende tre tilfeller oppstå:

1) for j=m+1, (kl ). Derfor, i dette tilfellet, tall for alle j fra 1 til n;

2) for noen j, og alle verdier som tilsvarer denne indeksen

3) for noen indekser j, og for hver slik j minst ett av tallene er positivt.

I det første tilfellet, basert på optimalitetskriteriet, er den første referanseplanen optimal. I det andre tilfellet er ikke målfunksjonen begrenset ovenfra på settet med planer, og i det tredje tilfellet kan du gå fra den opprinnelige planen til en ny referanseplan, der verdien av målfunksjonen vil øke. Denne overgangen fra en referanseplan til en annen utføres ved å ekskludere noen av vektorene fra det opprinnelige grunnlaget og introdusere en ny vektor i den. Som en vektor introdusert i basisen kan du ta hvilken som helst av vektorene med indeksen j, for hvilket . Anta for eksempel at det er besluttet å introdusere en vektor i grunnlaget

For å bestemme vektoren som skal ekskluderes fra grunnlaget, finn for alle La dette minimum oppnås når i=r. Deretter ekskluderes vektoren fra grunnlaget, og tallet kalles tillatt element.

Kolonnen og raden i skjæringspunktet der det er et løsende element kalles guider.

Etter valg av guiderekke og guidekolonne, blir en ny referanseplan og vektorekspansjonskoeffisienter funnet gjennom vektorene til det nye grunnlaget som tilsvarer den nye referanseplanen. Dette er enkelt å implementere hvis du bruker Jordan–Gauss-metoden. I dette tilfellet kan det vises at de positive komponentene i den nye referanseplanen beregnes ved hjelp av formlene

(25)

og ekspansjonskoeffisientene av vektorer gjennom vektorene til det nye grunnlaget som tilsvarer den nye referanseplanen - i henhold til formlene

(26)

Etter beregning og i henhold til formlene (25) og (26), er deres verdier lagt inn i tabellen. 4. Elementene i den tredje raden i denne tabellen kan beregnes enten ved hjelp av formler

(27)

(28)

eller basert på deres definisjon.

Tabell 3

Tabell 4

Tilstedeværelsen av to måter å finne elementene i th rad lar deg kontrollere riktigheten av de utførte beregningene.

Fra formel (27) følger det at når man går fra en referanseplan til en annen, er det mest tilrådelig å innføre en vektor med indeksen i grunnlaget j, der maksimum i absolutt verdi er tallet . Men for å forenkle beregningsprosessen, vil vi i fremtiden bestemme vektoren som er introdusert i grunnlaget basert på den maksimale absolutte verdien av negative tall. Hvis det er flere slike tall, vil vi introdusere i grunnlaget en vektor som har samme indeks som maksimum av tallene definert av disse tallene

Så overgangen fra en referanseplan til en annen kommer ned til overgangen fra en simplekstabell til en annen. Elementene i den nye simplekstabellen kan beregnes både ved hjelp av tilbakevendende formler (25)-(28) og ved bruk av reglene som direkte følger av dem. Disse reglene er som følger.

I kolonnene med vektorer som er inkludert i grunnlaget, i skjæringspunktet mellom rader og kolonner med vektorer med samme navn, plasseres enheter, og alle andre elementer i disse kolonnene settes lik null.

Elementene i vektorene og i raden i den nye simplekstabellen, der vektoren som er lagt inn i grunnlaget er skrevet, hentes fra elementene i den samme raden i den opprinnelige tabellen ved å dele dem med verdien til det løsende elementet. I kolonnen i raden til inngangsvektoren skriver du inn verdien , hvor k – indeksen til inngangsvektoren.

De resterende elementene i vektorkolonnene og den nye simplekstabellen beregnes ved hjelp av trekantregelen. For å beregne noen av disse elementene, er tre tall funnet:

1) et tall som står i den opprinnelige simplekstabellen i stedet for ønsket element i den nye simplekstabellen;

2) et tall i den opprinnelige simplekstabellen i skjæringspunktet mellom raden som inneholder det ønskede elementet i den nye simplekstabellen og kolonnen som tilsvarer vektoren som er lagt inn i grunnlaget;

3) et tall i den nye simplekstabellen i skjæringspunktet mellom kolonnen der det nødvendige elementet er plassert og raden til vektoren som nylig er introdusert i basisen (som nevnt ovenfor, denne raden er hentet fra raden i den opprinnelige simplekstabellen ved å dele elementene med det løsende elementet).

Disse tre tallene danner en slags trekant, hvor to av hjørnene tilsvarer tallene i den opprinnelige simplekstabellen, og den tredje til tallet i den nye simplekstabellen. For å bestemme det nødvendige elementet i den nye simplekstabellen, trekkes produktet av det andre og det tredje fra det første tallet.

Etter å ha fylt den nye simplekstabellen, blir elementene i den th raden sett gjennom. Hvis alt er , så er den nye referanseplanen optimal. Hvis det er negative blant de angitte tallene, blir en ny referanseplan funnet ved hjelp av handlingssekvensen beskrevet ovenfor. Denne prosessen fortsettes til enten den optimale utformingen av problemet er oppnådd eller dets uløselighet er etablert.

Når vi fant en løsning på det lineære programmeringsproblemet, antok vi at dette problemet har støtteplaner og hver slik plan er ikke-degenerert. Hvis problemet har degenererte støtteplaner, kan en eller flere variabler i støtteplanen ved en av iterasjonene vise seg å være lik null. Dermed, når du flytter fra en referanseplan til en annen, kan verdien av funksjonen forbli den samme. Dessuten er det mulig at funksjonen beholder sin verdi over flere iterasjoner, og det er også mulig å gå tilbake til det opprinnelige grunnlaget. I det siste tilfellet sier de vanligvis hva som skjedde looping. Men når du løser praktiske problemer, forekommer denne saken svært sjelden, så vi vil ikke dvele ved den.

Så å finne den optimale planen ved å bruke simplex-metoden inkluderer følgende trinn:

1. Finn en referanseplan.

2. Lag et simpleksbord.

3. Finn ut om det er minst ett negativt tall. Hvis ikke, er den funnet referanseplanen optimal. Hvis det er negative tall blant tallene, fastslår de enten problemets uløselighet eller går videre til en ny referanseplan.

4. Finn kolonne- og radguidene. Guidekolonnen bestemmes av det største negative tallet i absolutt verdi, og guideraden bestemmes av minimumsforholdet mellom vektorkolonnekomponentene og de positive komponentene i guidekolonnen.

5. Ved å bruke formlene (25) – (28), bestemmes de positive komponentene i den nye referanseplanen og vektorekspansjonskoeffisientene Pysjamas ved vektorer av det nye grunnlaget og antallet, . Alle disse tallene er skrevet i en ny simplekstabell.

6. Sjekk den funnet referanseplanen for optimalitet. Hvis planen ikke er optimal og det er nødvendig å flytte til en ny referanseplan, går de tilbake til trinn 4, og hvis en optimal plan oppnås eller uløselighet er etablert, er prosessen med å løse problemet fullført.

Eksempel 9.

For produksjon av ulike produkter EN,I og C foretaket bruker tre forskjellige typer råvarer. Satser for råvareforbruk for produksjon av ett produkt av hver type, pris på ett produkt EN,I Og MED, samt den totale mengden råvarer av hver type som kan brukes av bedriften, er gitt i tabell. 5.

Tabell 5

Produkter EN,I Og MED kan produseres i alle proporsjoner (salg er garantert), men produksjonen er begrenset til råvarene av hver type som er tildelt bedriften.

Lag en produksjonsplan for produkter der totalkostnaden for alle produkter produsert av bedriften er maksimal.

Løsning. La oss lage en matematisk modell av problemet. Nødvendig produktutgivelse EN angi med x 1, produkter IN - gjennom , produkter MED - gjennom. Siden det er begrensninger på fondet av råvarer av hver type som tildeles foretaket, må variablene tilfredsstille følgende ulikhetssystem:

(29)

Den totale kostnaden for produkter produsert av bedriften, med forbehold om utgivelsen av x 1 produkter EN, Produkter I og produkter MED beløper seg til

I henhold til deres økonomiske innhold kan variabler bare ha ikke-negative verdier:

Dermed kommer vi frem til følgende matematiske problem: blant alle ikke-negative løsninger til systemet med ulikheter (29), er det nødvendig å finne en ved hvilken funksjon (30) tar maksimalverdien.

La oss skrive denne oppgaven i form av et grunnleggende lineært programmeringsproblem. For å gjøre dette, la oss gå fra ulikhetsbegrensninger til likhetsbegrensninger. La oss introdusere tre ekstra variabler, som et resultat av hvilke restriksjonene vil bli skrevet i form av et ligningssystem

I økonomiske termer betyr disse tilleggsvariablene mengden råstoff av en eller annen type som ikke brukes i en gitt produksjonsplan. For eksempel, – Dette er den ubrukte mengden råvarer av type I.

Vi skriver det transformerte ligningssystemet i vektorform:

Siden blant vektorene Siden det er tre enhetsvektorer, kan referanseplanen skrives direkte for denne oppgaven. Det er planen X=(0; 0; 0; 360; 192; 180), definert av et system av tredimensjonale enhetsvektorer som danner grunnlaget for et tredimensjonalt vektorrom.

Vi kompilerer en simplekstabell for iterasjon I (tabell 6), beregner verdiene og kontrollerer den første referanseplanen for optimalitet:

For basisvektorer

Tabell 6

Som det fremgår av tabell 6, er verdiene til alle hovedvariabler lik null, og tilleggsvariabler tar verdiene deres i samsvar med begrensningene til problemet. Disse variable verdiene tilsvarer en "plan" der ingenting produseres, ingen råvarer brukes, og verdien av målfunksjonen er null (dvs. det er ingen produksjonskostnader). Denne planen er selvsagt ikke optimal.

Dette kan sees fra 4. linje i tabellen. 6, siden den inneholder tre negative tall: og Negative tall indikerer ikke bare muligheten for å øke de totale produksjonskostnadene, men viser også hvor mye dette beløpet vil øke når en enhet av en eller annen type produkt introduseres i planen.

Så, tallet - 9 betyr at når ett produkt er inkludert i produksjonsplanen EN sikrer en økning i produksjonen med 9 rubler. Hvis du inkluderer ett produkt i produksjonsplanen I og C, da vil de totale kostnadene for produserte produkter øke med henholdsvis 10 og 16 rubler. Derfor, fra et økonomisk synspunkt, er det mest hensiktsmessig å inkludere produkter i produksjonsplanen MED. Det samme må gjøres på grunnlag av det formelle tegnet til simpleksmetoden, siden det maksimale negative tallet i absolutt verdi er i 4. rad i vektorkolonnen R 3. Derfor introduserer vi vektoren i grunnlaget R 3. vi bestemmer vektoren som skal ekskluderes fra grunnlaget. For å gjøre dette finner vi

Etter å ha funnet tallet, bestemte vi dermed fra et økonomisk synspunkt hvor mange produkter MED bedriften kan produsere under hensyntagen til forbruksrater og tilgjengelige mengder råvarer av hver type. Siden det er henholdsvis 360, 192 og 180 kg råvarer av denne typen, og for ett produkt MED som kreves for å bruke råvarer av hver type er henholdsvis 12, 8 og 3 kg, deretter maksimalt antall produkter MED, som kan produseres av bedriften, er lik dvs. en begrensende faktor for produksjon av produkter MED er tilgjengelig volum av råvarer av type II. Tatt i betraktning tilgjengeligheten, kan selskapet produsere 24 produkter MED. I dette tilfellet vil type II-råvarer bli brukt fullt ut.

Derfor er vektoren R 5 er underlagt utelukkelse fra grunnlaget. Vektor kolonne R 3 til 2 rad er guidene. Vi kompilerer en tabell for iterasjon II (tabell 7).

Tabell 7

Først fyller vi linjen til vektoren som nylig er introdusert i grunnlaget, det vil si linjen hvis nummer sammenfaller med nummeret til ledelinjen. Her er guiden 2. linje. Elementene i denne raden er i tabellen. 7 oppnås fra de tilsvarende elementene i tabell 6 ved å dele dem med det oppløselige elementet (dvs. med 8). Dessuten i kolonnen C b Vi skriver ned koeffisienten i kolonnen til vektoren som er lagt inn i grunnlaget. Deretter fyller vi inn elementene i kolonnene for vektorene som er inkludert i det nye grunnlaget. I disse kolonnene, i skjæringspunktet mellom rader og kolonner med vektorer med samme navn, setter vi enheter, og alle andre elementer er satt lik null.

For å bestemme de resterende elementene i tabellen. 7 bruker vi trekantregelen. Disse elementene kan også beregnes direkte ved hjelp av gjentakelsesformler.

La oss beregne elementene i tabellen. 7 står i en vektorkolonne R 0 . Den første er i 1. rad i denne kolonnen. For å beregne det finner vi tre tall:

1) tallet i tabellen. 6 ved skjæringspunktet mellom vektorkolonnen R 0 og 1. linje (360);

2) tallet i tabellen. 6 ved skjæringspunktet mellom vektorkolonnen P 3. og 1. linje (12);

3) tallet i tabellen. 7 ved skjæringspunktet mellom vektorkolonnen R 0 og 2. linje (24).

Trekker vi produktet av de to andre fra det første tallet, finner vi det nødvendige elementet: 360 – 12 x 24 = 72; skriv det i 1. rad i vektorkolonnen R 0 fane. 7.

Andre kolonneelement i vektoren R 0 fane. 7 ble allerede beregnet tidligere. For å beregne det tredje kolonneelementet i en vektor R 0 finner vi også tre tall. Den første av dem (180) ligger i skjæringspunktet mellom den tredje raden og kolonnen i vektoren R 0 fane. 6, andre (3) – i skjæringspunktet mellom den tredje raden og kolonnen i vektoren P 3 bord 6, tredje (24) – i skjæringspunktet mellom den andre raden og kolonnen i vektoren R 0 fane. 8. Så det indikerte elementet er 180 - 24 x 3 = 108. Vi skriver tallet 108 i 3. linje i vektorkolonnen R 0 fane. 7.

Betydning F 0 i 4. rad i kolonnen i samme vektor kan finnes på to måter:

1) i henhold til formelen, dvs.

2) i henhold til trekantregelen; i dette tilfellet er trekanten dannet av tallene 0, -16, 24. Denne metoden fører til samme resultat: 0 - (-16) x 24 = 384.

Når du bestemmer vektorkolonneelementene ved hjelp av trekantregelen R 0 det tredje tallet, som sto i det nedre toppunktet av trekanten, forble uendret hele tiden og bare de to første tallene endret seg. La oss ta dette i betraktning når vi finner elementene i vektorkolonnen P 1 bord 7. For å beregne de angitte elementene tar vi de to første tallene fra kolonnene med vektorer P 1 og R 3 bord 6, og det tredje tallet er fra tabellen. 7. Dette tallet er i skjæringspunktet mellom 2. rad og kolonne i vektoren P 1 av den siste tabellen. Som et resultat får vi verdiene til de nødvendige elementene: 18 – 12 x (3/4) =9; 5 – 3 x (3/4) = 11/4.

Nummer i fjerde rad i vektorkolonnen P 1 bord 7 kan finnes på to måter:

1) i henhold til formelen Z 1 -C 1 = (C,P 1) -C 1 har vi

2) etter trekantregelen vi får

På samme måte finner vi elementene i vektorkolonnen P 2 .

Vector kolonneelementer R 5 beregnes ved hjelp av trekantregelen. Imidlertid ser trekantene som er konstruert for å definere disse elementene annerledes ut.

Når du beregner elementet i den første raden i den angitte kolonnen, oppnås en trekant dannet av tallene 0,12 og 1/8. Derfor er det nødvendige elementet 0 – 12x (1/8) = -3/2. Elementet i den tredje raden i denne kolonnen er lik 0 - 3 x (1/8) = -3/8.

Etter fullføring av beregningen av alle elementene i tabellen. 7 i den oppnås en ny referanseplan og vektorekspansjonskoeffisienter gjennom basisvektorene P 4, P 3, P 6 og verdiene og . Som det fremgår av denne tabellen, er den nye referanseplanen for oppgaven planen X=(0; 0; 24; 72; 0; 108). Med denne produksjonsplanen produseres 24 produkter MED og 72 kg råvarer av type 1 og 108 kg råvarer av type III forblir ubrukte. Kostnaden for alle produkter produsert under denne planen er 384 rubler. De angitte tallene er skrevet i vektorkolonnen R 0 fane. 7. Som du kan se, representerer dataene i denne kolonnen fortsatt parametrene for problemet under vurdering, selv om de har gjennomgått betydelige endringer. Dataene i andre kolonner har også endret seg, og deres økonomiske innhold er blitt mer komplekst. Så ta for eksempel vektorkolonnedataene R 2 . Tallet 1/2 i 2. linje i denne kolonnen viser hvor mye produksjonen av produkter bør reduseres MED, hvis du planlegger å gi ut ett produkt I. Tallene 9 og 3/2 i 1. og 3. rad i vektoren P 2 viser henholdsvis hvor mye råstoff av type I og II som kreves når det inngår i produksjonsplanen for ett produkt I, og tallet - 2 i 4. linje viser at hvis utgivelsen av ett produkt er planlagt I, da vil dette sikre en økning i produksjonsproduksjonen i verdi med 2 rubler. Med andre ord, hvis du inkluderer ett produkt i produksjonsplanen I, så vil dette kreve en reduksjon i produktproduksjonen MED med 1/2 enhet og vil kreve ekstra kostnader på 9 kg råvarer av type I og 3/2 kg råvarer av type III, og de totale kostnadene for produserte produkter i samsvar med den nye optimale planen vil øke med 2 rubler. Dermed fungerer tallene 9 og 3/2 som nye "normer" for kostnadene for råvarer av type I og III for produksjon av ett produkt I(som man kan se av tabell 6, tidligere var de lik 15 og 3), noe som forklares med en nedgang i produktproduksjonen MED.

Vektorkolonnedataene har også samme økonomiske betydning R 1 bord 7. Tallene skrevet i vektorkolonnen har et litt annet økonomisk innhold R 5 . Tallet 1/8 i den andre linjen i denne kolonnen viser at en økning i volumet av råvarer av type II med 1 kg ville tillate å øke produksjonen av produkter MED med 1/8 enheter Samtidig vil det kreves ytterligere 3/2 kg råvarer av type I og 3/8 kg råvarer av type III. Økning i produktproduksjon MED med 1/8 enheter vil føre til en økning i produksjonen med 2 rubler.

Fra ovennevnte økonomiske innhold av dataene i tabell. 7 følger det at problemplanen funnet ved iterasjon II ikke er optimal. Dette kan sees fra 4. linje i tabellen. 7, siden i vektorkolonnen P 2 av denne linjen er et negativt tall - 2. Dette betyr at vektoren skal legges inn i grunnlaget P 2, dvs. den nye planen skal sørge for produksjon av produkter I. Når man skal bestemme mulig antall produkter som skal produseres I den tilgjengelige mengden råvarer av hver type bør tas i betraktning, nemlig: mulig produksjon av produkter I er definert for , dvs. vi finner

Derfor må vektoren utelukkes fra grunnlaget R 4 med andre ord, produktutgivelse I begrenset av råvarene av type I tilgjengelig for foretaket. Tatt i betraktning de tilgjengelige volumene av disse råvarene, bør selskapet produsere 8 produkter I. Tallet 9 er det løsende elementet, og kolonnen til vektoren P 2 og 1. linje i tabellen. 7 er guider. Vi kompilerer en tabell for iterasjon III (tabell 8).

Tabell 8

I tabellen 8, først fyller vi inn elementene i den første raden, som er raden til vektoren som nylig er introdusert i basisen R 2 . Elementene i denne raden er hentet fra elementene i den første raden i tabellen. 7 ved å dele sistnevnte med oppløsningselementet (dvs. med 9). Dessuten i kolonnen C b av denne linjen skriver vi .

Deretter fyller vi inn elementene i kolonnene til basisvektorene, og ved hjelp av trekantregelen beregner vi elementene i de gjenværende kolonnene. Som et resultat, i Tabell. 8 får vi en ny referanseplan X=(0; 8; 20; 0; 0; 96) og koeffisienter for vektorekspansjon gjennom basisvektorer og tilsvarende verdier og

Vi sjekker om gitt referanseplan er optimal eller ikke. For å gjøre dette, vurder den fjerde linjen, tabellen. 8. Det er ingen negative tall blant tallene på denne linjen. Dette betyr at den funnet referanseplanen er optimal og

Derfor en produksjonsplan som inkluderer produksjon av 8 produkter I og 20 produkter MED, er optimal. Med denne planen for produksjon av produkter er råvarer av type I og II fullt brukt og 96 kg råvarer av type III forblir ubrukte, og kostnadene for produktene som produseres er 400 rubler.

Den optimale produksjonsplanen sørger ikke for produksjon av produkter EN. Innføring i produksjonsplan for produkter av typen EN vil medføre en reduksjon i oppgitt totalkostnad. Dette kan sees fra 4. rad i vektorkolonnen P 1, hvor tallet 5 viser at for en gitt plan, inkludert frigjøring av en produktenhet EN fører bare til en reduksjon i totalkostnaden med 5 rubler.

Dette eksemplet kan løses ved å bruke simpleksmetoden ved å bruke bare én tabell (tabell 9). I denne tabellen er alle tre iterasjonene av beregningsprosessen registrert sekvensielt, etter hverandre.

Tabell 9

Som det fremgår av tabellen. 10, er den opprinnelige referanseplanen ikke optimal. Derfor går vi videre til en ny referanseplan. Dette kan gjøres fordi i kolonnene med vektorer P 1 og s 5, hvor den fjerde raden inneholder negative tall, har positive elementer. For å flytte til en ny referanseplan, introduserer vi vektoren i grunnlaget s 5 og ekskluder vektoren fra basisen s 4. Vi setter sammen tabell II av iterasjon.

Tabell 11

Som det fremgår av tabellen. 11, er den nye referanseplanen for problemet ikke optimal, siden i den fjerde raden i vektorkolonnen P 1 er verdt et negativt tall -11/3. Siden det ikke er noen positive elementer i kolonnen til denne vektoren, har ikke dette problemet en optimal plan.