oppgaver lineær programmering

2.1. Definisjon og opptaksformer

I tilfellet der alle begrensninger er ligninger og alle variabler tilfredsstiller ikke-negativitetsbetingelsen, kalles det lineære programmeringsproblemet kanonisk. Det kan representeres i koordinat, vektor eller matriseform poster.

a) det kanoniske LP-problemet i koordinatform har formen:

,
.

Dette problemet kan skrives ved å bruke summeringstegnet:

,

,

,
,
.

b) det kanoniske LP-problemet i vektorform har formen: ,

,

Hvor
;
;

,
;;
.

c) det kanoniske LP-problemet i matriseform har formen:

,
,

Hvor
,,.

2.2. Reduksjon av det generelle lineære problemet

programmering til kanonisk form

Når man kompilerer matematiske modeller for økonomiske problemer, blir begrensninger hovedsakelig formet til systemer av ulikheter. Derfor er det nødvendig å kunne gå fra dem til ligningssystemer. Tenk for eksempel på den lineære ulikheten

og legg til en viss verdi på venstre side
slik at ulikhet blir til likhet.

Ikke-negativ variabel
kalt en tilleggsvariabel. Følgende teorem gir grunnlag for muligheten for en slik transformasjon.

Teorem 2.2.1. Hver avgjørelse
ulikhet (2.2.1) tilsvarer en unik løsning på ligning (2.2.2) og ulikhet
, og omvendt til hver løsning av ligning (2.2.2)c
tilsvarer løsningen
ulikheter (2.2.1).

Bevis. La
løsning av ulikhet (2.2.1). Deretter. La oss ta et tall
. Det er klart det
. Setter vi inn i ligning (2.2.2), får vi

Den første delen av teoremet er bevist.

La nå være en vektor tilfredsstiller ligning (2.2.2) med
, dvs. forkaste den ikke-negative verdien på venstre side av den siste likheten
, vi mottar osv.

Dermed etablerer det beviste teoremet faktisk muligheten for å redusere ethvert LP-problem til kanonisk form. For å gjøre dette er det nok å innføre i hver begrensning som har form av en ulikhet sin egen ekstra ikke-negative variabel. Dessuten, i ulikheter i formen (1.2.1) vil disse variablene vises med "+"-tegnet, og i ulikheter i formen (1.2.2) - med "–"-tegnet. Ytterligere variabler introduseres i objektivfunksjonen med null koeffisienter og påvirker derfor ikke verdien.

Kommentar. I det følgende vil vi presentere simpleksmetoden for det kanoniske LP-problemet når vi studerer objektiv funksjon til et minimum. I de problemene hvor du må finne det maksimale
, er det nok å vurdere funksjonen
, finn minimumsverdien, og endre deretter tegnet til det motsatte, bestem ønsket maksimal verdi
.

3. Grafisk metode for å løse problemer

lineær programmering

3.1. Generelle begreper, eksempler

I tilfeller hvor det kun er to variabler i LP-oppgaven kan du bruke grafisk metode. La det være nødvendig å finne maksimal (minimum) verdi for funksjonen
under restriksjoner

(3.1.1)

Denne metoden er basert på muligheten for å grafisk avbilde regionen med gjennomførbare løsninger på et problem, dvs. tilfredsstillende system (3.1.1), og finne den optimale løsningen blant dem. Regionen med gjennomførbare løsninger på problemet er konstruert som skjæringspunktet (felles del) av løsningsregionene for hver av de gitte begrensningene (3.1.1). Hver av dem definerer et halvplan med grense
,
. For å bestemme hvilket av de to halvplanene som er løsningsdomenet, er det nok å erstatte koordinatene til ethvert punkt som ikke ligger på linjen med ulikheten: hvis den er tilfredsstilt, er løsningsdomenet halvplanet som inneholder dette punktet, hvis ulikheten ikke er tilfredsstilt, så er løsningsdomenet et halvplan som ikke inneholder det gitte punktet.

Skjæringspunktet mellom disse halvplanene danner et bestemt område kalt en løsningspolygon, som er en konveks mengde. (Anta at systemet med begrensninger er konsistent, og at polygonen til løsningene er begrenset.) For å finne den optimale blant de mulige løsningene, brukes nivålinjer og rette referanselinjer.

Nivålinje kalles en rett linje som objektivet fungerer på tar en konstant verdi. Nivålinjeligningen har formen

, Hvor
. Alle nivålinjer er parallelle med hverandre. Deres normale
.

Referanselinje kalles en nivålinje som har minst ett felles punkt med området for gjennomførbare løsninger, i forhold til hvilket denne regionen ligger i et av halvplanene (fig. 1).

Verdier
økning i vektorens retning
. Derfor er det nødvendig å flytte nivålinjen
i retning av denne vektoren parallelt med seg selv til referanselinjen L 1 i maksimumsoppgaven og i motsatt retning - i minimumsoppgaven (opp til referanselinjen L 2).

La oss gi løsningen til eksempel 1.1. Husk at vi må finne maksimum av funksjonen
under restriksjoner

Løsning. Vi bygger en region med gjennomførbare løsninger. Vi nummererer begrensningene til problemet. I et rektangulært kartesisk koordinatsystem (fig. 2) konstruerer vi en rett linje

, tilsvarende begrensning (1). Vi finner hvilke av halvplanene som denne rette linjen deler hele koordinatplanet inn i som er domenet for løsninger på ulikhet (1).

For å gjøre dette er det nok å erstatte koordinatene til ethvert punkt som ikke ligger på linjen i ulikheten. Siden det er rett går ikke gjennom opprinnelsen, erstatter
til den første begrensningen. Vi oppnår en streng ulikhet
. Derfor er poenget
ligger i løsningens halvplan. På samme måte konstruerer vi en rett linje

og løsningsdomenet til begrensningen (2). Vi finner fellesdelen av halvplanene av løsninger, tatt i betraktning restriksjoner (3). Vi fremhever den resulterende regionen med mulige løsninger i mørk farge i fig. 2.

Bygge en nivålinje
og vektor
, som indikerer økningsretningen til funksjonen og vinkelrett på linjen

. Nivålinje
bevege seg parallelt med seg selv i retningen
til referanselinjen. Vi finner at objektivfunksjonen når sitt maksimum på punktet
skjæringspunktet mellom linjer Og . Løse et ligningssystem av disse linjene
, får vi koordinatene til punktet
. Derfor, og
,
optimal løsning.

Eksempel 3.1. Finn minimum av en funksjon
under et system av restriksjoner

Løsning. Vi konstruerer området med gjennomførbare løsninger (se fig. 3), vektor
og en av nivålinjene
. Flytt nivålinjen i motsatt retning
, siden problemet med å finne minimum av en funksjon blir løst. Referanselinjen i dette tilfellet går gjennom punkt A (fig. 3), hvis koordinater vil bli funnet fra systemets løsning

Så,
. La oss beregne.

Kommentar. Faktisk avhenger det av typen domene for gjennomførbare løsninger og den objektive funksjonen
Et LP-problem kan ha en enkelt løsning, et uendelig antall løsninger, eller ingen løsning i det hele tatt.

Eksempel 3.2. Finn minimum av en funksjon
under restriksjoner

Løsning. Konstruere regionen med gjennomførbare løsninger, normalen til nivålinjer
og en av nivålinjene , som har fellestrekk med dette området. Flytte nivålinjen i motsatt retning av normal retning , siden problemet med å finne minimum av en funksjon blir løst. Normal av nivålinjer
og normalen til grenselinjen , i hvilken retning nivålinjene beveger seg, er parallelle, siden deres koordinater er proporsjonale
. Derfor faller referanselinjen sammen med grenselinjen region med gjennomførbare løsninger og passerer gjennom to hjørnepunkter i denne regionen Og (Fig. 4).

Problemet har et uendelig antall optimale løsninger, som er punkter i segmentet
. Disse punktene
,
finner vi ved å løse de tilsvarende likningssystemene:

;
;

,
;
,
;

;
.

La oss beregne.

Svar:
på
,
.

Eksempel 3.3. Løs et lineært programmeringsproblem

Løsning. Vi konstruerer regionen med gjennomførbare løsninger, det normale
og en av nivålinjene. I dette problemet er det nødvendig å finne det maksimale av målfunksjonen, så nivålinjen bevege seg i retning av det normale. På grunn av det faktum at utvalget av mulige løsninger i denne retningen ikke er begrenset, går nivålinjen til uendelig (fig. 5).

Problemet har ingen løsning på grunn av den ubegrensede objektivfunksjonen.

Svar:
.

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 det er restriksjoner høyre del er negativ, skal denne grensen 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 = 2 x 1 + x 2 - x 3;
2 x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2 x 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.

I den kanoniske formen for å skrive lineære programmeringsproblemer, må alle variabler som er inkludert i systemet med begrensninger være negative. La oss anta det x 1 = x 1" - x 7 , Hvor x 1 "≥ 0, x 7 ≥ 0 .

Ved å erstatte dette uttrykket i systemet av begrensninger og den objektive funksjonen og skrive variablene i økende indeksrekkefølge, får vi et lineært programmeringsproblem presentert i kanonisk form:

L min = 2x 1" + x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Optimalitetsbetingelse for grunnplanen til det kanoniske LP-problemet. Enkel metode og dens konvergens.

Enkel metode er universell, siden det lar deg løse nesten alle lineære programmeringsproblemer skrevet inn kanonisk form.

Ideen om simpleksmetoden konsekvent forbedring plan er at, med utgangspunkt i en innledende referanseløsning, sekvensielt rettet bevegelse fra referanseløsningene for problemet til den optimale.

Verdien av objektivfunksjonen reduseres ikke under denne bevegelsen for problemer maksimalt.

Siden antallet støtteløsninger er begrenset, får vi etter et begrenset antall trinn den optimale støtteløsningen.

En referanseløsning er en grunnleggende ikke-negativ løsning.

Enkel metodealgoritme

1. Den matematiske modellen av problemet må være kanonisk. Hvis det er ikke-kanonisk, må det bringes til kanonisk form.

2. Finn den første referanseløsningen og kontroller den for optimalitet.
For å gjøre dette, fyll ut simplex bord 1.
Vi fyller ut alle rader i tabellen i det første trinnet i henhold til dataene til restriksjonssystemet og målfunksjonen.

Mulig følgende tilfeller når du løser problemer maksimum:

1. Hvis alle koeffisienter siste linje simplex tabeller DJ³ 0, så funnet

løsning optimal.

2 Hvis minst én koeffisient DJ £ 0, men for den tilsvarende variabelen er det ikke en eneste positiv evalueringssammenheng, da løsningen vi stopper oppgaver, siden F(X) ® ¥ , det vil si at den objektive funksjonen ikke er begrenset i området for gjennomførbare løsninger.

Hvis minst én koeffisient i den siste raden er negativ, og for den tilsvarende variabelen er det minst én positiv evaluerende holdning, så må du flytte til en annen referanseløsning.

4. E hvis det er flere negative koeffisienter i den siste raden, da til den underliggende variabelkolonnen(BP) introduser det variabel, som tilsvarer den største negative koeffisienten i absolutt verdi.

5. Dersom minst én koeffisient Dk< 0 ,At k - th kolonne godta for programlederen.

6. For ledende linje vi aksepterer den som tilsvarer minimum forholdet mellom gratis medlemmer bi til positive koeffisienter ledende, k – den kolonne.

7. Elementet som ligger i skjæringspunktet mellom de ledende radene og kolonnen kalles ledende element.

Fylle ut simplekstabell 2 :

· fyll grunnkolonnen med nuller og enere

· omskriv ledende linje ved å dele den med ledende element

· hvis den innledende raden har nuller, kan de tilsvarende kolonnene flyttes til neste simplekstabell

· vi finner de resterende koeffisientene ved å bruke "rektangel"-regelen

Vi skaffer en ny referanseløsning, som vi sjekker for optimalitet:

Hvis alle koeffisientene til den siste raden DJ³ 0, så fant løsningen maksimum.

Hvis ikke, fyll ut simplekstabellen for det åttende trinnet og så videre.

Hvis den objektive funksjonen F(X) krever å finne minimumsverdi, deretter kriteriet optimaliteten til problemet er ikke-positive koeffisienter D j for alle j = 1,2,...n.

Konvergens av simpleksmetoden. Degenerasjon i LP-problemer. Den viktigste egenskapen til enhver beregningsalgoritme er konvergens, det vil si muligheten for å oppnå de ønskede resultatene under bruken (med en gitt nøyaktighet) i et begrenset antall trinn (iterasjoner).

Det er lett å se at problemer med konvergensen av simpleksmetoden potensielt kan oppstå ved valg av verdien av r (seksjon 2") i tilfelle der den samme minimumsverdier forhold

vil oppnås for flere rader av tabell T (q) samtidig. Så ved neste iterasjon vil kolonne b(β(q+1)) inneholde null elementer.

: Lineære programmeringsproblemer (LPP)

1. Lineær programmering

2. Typer lineære programmeringsproblemer

3. Skjemaer for registrering av PAP-er

4. Kanonisk form for lineære programmeringsproblemer

Lineær programmering

Lineær programmering er en gren av matematisk programmering som brukes i utviklingen av metoder for å finne ekstremumet av lineære funksjoner til flere variabler under lineære ytterligere restriksjoner, pålagt variablene.

Basert på hva slags problemer de løser, deles LP-metoder inn i universelle og spesielle. Ved bruk av universelle metoder Eventuelle problemer med lineær programmering (LPP) kan løses. Spesielle tar hensyn til funksjonene til problemmodellen, dens objektive funksjon og system av begrensninger.

Hovedtrekket ved lineære programmeringsproblemer er at ytterpunktet av den objektive funksjonen er på grensen til regionen med gjennomførbare løsninger.

Figur 1 - Extremum av objektivfunksjonen

Den matematiske modellen til ZLP er skrevet som følger:

maks (eller min) Z=z(X),(1)

ODR kan representeres av systemet lineære ligninger eller ulikheter.

Vektor X = (x 1, x 2, .... x p) er en kontrollvektor eller kontrolleffekt.

En tillatt plan X, der optimalitetskriteriet Z=z(X) når en ekstremverdi, kalles optimal og er betegnet med X*, ekstremverdien til objektivfunksjonen med Z*=z(X*).

Typer lineære programmeringsproblemer

Lineære programmeringsmetoder er mye brukt i industribedrifter for optimalisering produksjonsprogram, distribuere det på tvers av verksteder og etter tidsintervaller, ved lasting av utstyrssortimenter, planlegging av lastestrømmer, fastsettelse av en omsetningsplan, etc.

Den vanligste typen oppgaver er problemet med optimal bruk av ressursene. La en produksjonsenhet (verksted, bedrift, forening, etc.), basert på markedsforhold, tekniske evner og tilgjengelige ressurser, kan produsere n forskjellige typer produkter kjent under nummer j.

Ved produksjon av produkter begrenses bedriften av de tilgjengelige ressursene, mengden av disse vil bli betegnet med m, og vektoren av ressursene B = (b 1, b 2, ..., b t). Teknologiske koeffisienter a ij er også kjent, som viser forbrukshastigheten til den i-te ressursen for produksjon av en enhet av j-te produkt. Slipp effektivitet j-i enheter produksjon er preget av profitt p j .

Det er nødvendig å bestemme produksjonsplanen X = (x 1, x 2, ..., x p), maksimere fortjenesten til bedriften med gitte ressurser.

Objektivfunksjonen ser slik ut

under restriksjoner

Ofte er produktutvalget etablert av en høyere organisasjon, det vil si at volumene må være innenfor visse grenser D i j og D i j: da settes følgende begrensning:

Modellen for problemet med optimal ressursbruk ligger til grunn modeller for å optimalisere bedriftens årlige produksjonsprogram. Modellen inkluderer restriksjoner på driftstiden til utstyr.

Med samme notasjon skriver vi gjennom henholdsvis b j og c j, salgsprisen og kostnaden per enhet jth produkter. Følgende kan tas som optimalitetskriterier:

1) maksimal fortjeneste

2) minimum produksjonskostnader

3) maksimal produksjon i verdi (inntekter fra produktsalg)

Eksempel. Bedriften kan produsere fire typer produkter 1, 2, 3 og 4. Salg av ethvert volum er garantert. I løpet av kvartalet har bedriften en arbeidsstyrke på 100 arbeidsskift, halvfabrikata på 260 kg og maskinutstyr på 370 maskinskift. Ressursforbruksrater og fortjeneste per enhet for hver type produkt er presentert i tabell 1.

Nødvendig:

a) sminke matematisk modell oppgaven med å bestemme en produksjonsplan som vil oppnå maksimal fortjeneste;

b) løse problemet med kravet om emballasje slik at antall enheter av det tredje produktet er 3 ganger mer mengde enheter først;

c) finn ut det optimale sortimentet for tilleggsbetingelser: produsere minst 25 enheter av det første produktet, ikke mer enn 30 enheter av det tredje, og det andre og fjerde i forholdet 1:3.

Tabell 1

Innledende data

Matematisk modell av problemet:

objektiv funksjon:

maks: Z=40x 1 +50x 2 +100x 3 +80x 4

med restriksjoner:

a) for arbeidsressurser:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

for halvfabrikata:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

for maskinverktøy:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

ikke-negativitetstilstand:

b) tilleggskrav konfigurasjonen vil bli uttrykt av betingelsen

3 x 1 = x 3, dvs. 3 x 1 x 3 = 0;

c) la oss presentere grensebetingelsene og konfigurasjonsbetingelsene som følger: x 1 ? 25,

x 3-30, 3* x 2 = x 4.

Problemet med å legge inn bestillinger eller laste inn utskiftbare utstyrsgrupper. Vi snakker om fordelingen av bestillinger mellom m (i=1,..., m) bedrifter (butikker, maskiner, utøvere) med forskjellige produksjons- og teknologiske egenskaper, men utskiftbare når det gjelder å oppfylle bestillinger. Det er påkrevd å utarbeide en ordreplasseringsplan der oppgaven vil bli fullført og effektivitetsindikatoren vil nå en ekstrem verdi.

La oss formulere problemet matematisk. La n typer produkter må produseres ved hjelp av m homogene grupper av utstyr. Produksjonsplan for hver type produkt viss periode gitt av mengden x j (j=1,2, …n). Kraften til hver type utstyr er begrenset og lik b i. Den teknologiske matrisen A=||a ij || er kjent, der a ij er antall enheter av det j-te produktet produsert per tidsenhet for i-th utstyr. Matrise C er en kostnadsmatrise, der c ij er kostnadene knyttet til produksjonen av en enhet av det j-te produktet på det i-te utstyret. X er en vektor for utgangsvolum.

Problemmodellen vil ha følgende form:

objektiv funksjon - minimere kostnadene ved å implementere alle bestillinger

med restriksjoner:

a) ved utstyrskraft

b) for produksjon

c) ikke-negativitetstilstand

Dette problemet kalles et distribusjons- eller distribusjonsproblem.

Hvis planen er tillatt å overskride for noen typer produkter, vil begrensning (b) ha formen

Følgende kan også tas som målfortjeneste:

a) maksimal fortjeneste

b) minimumskostnad for maskintid

Fordi Enhver modell inneholder forenklede premisser; for riktig anvendelse av de oppnådde resultatene er det nødvendig med en klar forståelse av essensen av disse forenklingene, noe som til syvende og sist lar oss trekke en konklusjon om deres tillatelighet eller avvisning. Den mest betydningsfulle forenklingen i de vurderte modellene er antakelsen om et direkte proporsjonalt (lineært) forhold mellom volumene av ressursforbruk og produksjonsvolumer, som spesifiseres ved bruk av kostnadsnormer a ij . Denne forutsetningen er åpenbart ikke alltid oppfylt. Dermed endres forbruksvolumene for mange ressurser (for eksempel anleggsmidler) brått - avhengig av endringer i produksjonsprogrammet X. Andre forenklingspremisser inkluderer antakelser om uavhengigheten av prisene j fra volumene x j, som bare gjelder for visse grenser av deres endring. Det er også viktig å kjenne til disse "sårbare" punktene fordi de indikerer grunnleggende retninger for å forbedre modellen.

PAP-opptaksskjemaer

Det er 3 former for opptak av PAP:

1) i form av funksjoner

maks(eller min)Z=,maks(eller min)Z=,

2) vektorform

(skalært produkt av vektorer)

under restriksjoner

A 1 x 1 +A 2 x 2 +..+A n x n = B

Hvor er vektorene

C = (C 1, C 2 .. C n), X = ( X 1, X 2 .. X n), og.

3) matriseform

under restriksjoner

hvor C = (c 1, c 2, ... c n),

Kanonisk form for lineære programmeringsproblemer

Hvis alle begrensningene i et lineært programmeringsproblem er ligninger og ikke-negativitetsbetingelser pålegges alle variabler x j, kalles det et lineært programmeringsproblem i kanonisk form eller kanonisk problem lineær programmering (KZLP).

under restriksjoner

For å gå fra ZLP til CLLP er det nødvendig å gå fra ulikhetsbegrensninger til likhetsbegrensninger og erstatte variabler som ikke overholder ikke-negativitetsbetingelsene.

Regler for å bringe ZLP til kanonisk form:

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

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

3) hvis en variabel xk ikke har noen tegnrestriksjoner, erstattes den i objektivfunksjonen og i alle restriksjoner med differansen mellom to nye ikke-negative variabler: xk=x * k - xl, der l er oppsummeringsindeksen, x * k>=, xl >=0.

La oss se på et eksempel. La oss bringe det til den kanoniske formen:

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

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

I den kanoniske formen for å skrive lineære programmeringsproblemer, må alle variabler som er inkludert i systemet med begrensninger være ikke-negative. La oss anta det

Ved å erstatte dette uttrykket i systemet med begrensninger og den objektive funksjonen og skrive variablene i stigende indeksrekkefølge, får vi et lineært programmeringsproblem presentert i kanonisk form:

optimering simpleks lineær programmering

Registreringen av objektivfunksjonen og systemet med begrensninger i forskjellige lineære programmeringsproblemer er ikke det samme: i noen problemer er det nødvendig å finne minimum av objektivfunksjonen, og i andre - maksimum; i noen tilfeller er de søkte variablene avhengige av én indeks, og i andre av to; i noen problemer spesifiseres begrensningene i form av et system lineære ulikheter, og i andre – i form av et system av lineære ligninger. I praksis er det også mulig å ha problemer der noen av begrensningene er i form av lineære ulikheter, og noen er i form av lineære ligninger. Dessuten kan ikke alle problemer kreve at variabler ikke er negative.

Å ta hensyn til en slik rekke lineære programmeringsproblemer krever utvikling av spesielle metoder for å løse individuelle klasser av dem. Vi vil fokusere vår oppmerksomhet på å studere de generelle egenskapene og metodene for lineær programmering, skrevet i den såkalte kanoniske formen.

Hvis i et lineært programmeringsproblem, har systemet med innledende begrensninger form av ligninger som

og du må finne maksimum av den lineære objektivfunksjonen

da anses det lineære programmeringsproblemet for å være skrevet i kanonisk form.

Ethvert lineært programmeringsproblem kan enkelt reduseres til kanonisk form. I det generelle tilfellet, for dette er det nok å for det første redusere problemet med å minimere den objektive funksjonen til problemet med å maksimere den, for det andre gå fra ulikhetsbegrensninger til likhetsbegrensninger, og for det tredje endre de variablene som er ikke underlagt betingelsen om ikke-negativitet.

I tilfelle når du trenger å finne minimum av en funksjon , kan vi fortsette med å finne maksimum av funksjonen , siden følgende utsagn er sann:
.

Ulikhetsbegrensningen til det opprinnelige problemet, som har formen " ", kan gjøres om til en ligningsbegrensning ved å legge til en ekstra ikke-negativ variabel til venstre side, og en ulikhetsbegrensning av formen " ” – ved å trekke en ekstra ikke-negativ variabel fra venstre side.

Merk at antallet introduserte ekstra ikke-negative variabler alltid er lik antallet ulikheter i det opprinnelige systemet av begrensninger.

De ekstra variablene som er introdusert har en veldig spesifikk økonomisk betydning. Så hvis begrensningene til det opprinnelige lineære programmeringsproblemet gjenspeiler kostnadene og tilgjengeligheten til produksjonsressurser, da numerisk verdi tilleggsvariabelen viser mengden av den tilsvarende ubrukte ressursen.

Merk også at hvis noen variabel ikke adlyder ikke-negativitetsbetingelsen, må den erstattes av to ikke-negative variabler Og , etter å ha akseptert
.

Eksempel. Skriv følgende lineære optimaliseringsproblem i kanonisk form: finn minimum av funksjonen
under restriksjoner

Løsning

I dette problemet må du finne minimum av objektivfunksjonen, og systemet med begrensninger inkluderer fire ulikheter. For å skrive det i kanonisk form, må du gå fra ulikhetsbegrensninger til likningsbegrensninger, og også transformere den objektive funksjonen.

Siden antallet ulikheter inkludert i systemet med begrensninger av problemet er lik fire, må denne overgangen utføres med introduksjon av fire ekstra ikke-negative variabler. Dessuten, i den andre og fjerde ulikheten er det et tegn " ", så vi legger til flere variabler på venstre side. I den første og tredje ulikheten er det et tegn " ", noe som betyr at vi trekker tilleggsvariabler fra venstre side.

Vi transformerer også den objektive funksjonen, endrer alle tegnene til det motsatte, og finner dens maksimum.

Dermed, denne oppgaven lineær programmering vil bli skrevet i følgende kanoniske form:

finne maksimum av en funksjon

under restriksjoner

En analytisk metode for å løse et lineært programmeringsproblem er simpleks metode. For å anvende det, må LP-problemer presentert på forskjellige måter reduseres til kanonisk form. Det lineære programmeringsproblemet, skrevet i formen (2.1.1)-(2.1.3), er en utvidet form for notasjon felles oppgave lineær programmering (LPP).

Vi vil kalle følgende problem et kanonisk lineært programmeringsproblem (CLPT):

under restriksjoner i form av likestilling,

Hvis for et problem i formen (2.3.1)-(2.3.4) er betingelsen oppfylt t = n, så reduseres løsningen til å løse ligningssystemet

• (2.3.2) . I dette tilfellet vil problemet ikke ha noen løsninger hvis tilstanden
• (2.3.3) er ikke oppfylt eller ligningssystemet har ingen løsning.

betingelse T

• 1. Å gå fra maksimeringsproblemet objektiv funksjon (2.3.1) til minimeringsproblem nok ta alle koeffisienter Cj objektiv funksjon med omvendte tegn og løse det resulterende problemet maksimalt. Etter å ha funnet maksimum, må verdien av objektivfunksjonen tas med motsatt fortegn. Den optimale løsningen vil forbli den samme.
• 2. Å gå fra mindre enn eller lik likhetsbegrensning det er nødvendig med et plusstegn:

3. Å gå fra en "større enn eller lik" begrensning til likhet det er nødvendig introdusere en ekstra ikke-negativ variabel med et minustegn:

I dette tilfellet introduserer hver ulikhet sin egen (n +/)-th tilleggsvariabel.

• 4. Alt likheter som har negative frie vilkår er delt inn i-1, for at betingelse (2.3.4) skal være oppfylt.
• 5. Hvis på en variabel Xj ikke-negativitetsbetingelsen er ikke pålagt, Det gjør en endring av variablene Xj=x".- X" x"j > 0, x"> 0. I den transformerte oppgaven alle variabler er ikke-negative.

Det er en erklæring om at enhver ZLP kan reduseres til en kanonisk form.

Eksempel 2.3.1. La oss transformere problemet gitt i eksempel 2.2.2 til kanonisk form. Den objektive funksjonen og systemet med begrensninger ser slik ut:

La oss introdusere en ekstra variabel jc 3 > 0 med et plusstegn i den første ulikheten, og i den andre x 4> 0 med et minustegn og i den tredje x 5> 0 også med et plusstegn. Som et resultat får vi et system med problembegrensninger i kanonisk form:

Gitt disse begrensningene, må du finne maksimalverdien for funksjonen:

La oss vurdere den økonomiske betydningen av tilleggsvariabler i det kanoniske problemet med optimal bruk av ressurser.

Eksempel 2.3.2. Problem med optimal ressursutnyttelse (teppeproblem)[17 J.

Fabrikken har til disposisjon en viss mengde ressurser av tre typer: arbeidskraft (80 dagsverk), råvarer (480 kg) og utstyr (130 maskintimer). Fabrikken kan produsere fire typer tepper. Informasjon om antall enheter av hver ressurs som kreves for å produsere ett teppe av hver type, og om inntekten mottatt av bedriften fra en enhet av hver type produkt er gitt i tabell. 2.3.1.

Det er nødvendig å finne en produksjonsplan der den totale kostnaden vil være maksimal.

Økonomisk og matematisk modell av problemet Variabler: x x, x 2, x 3, x 4 - antall tepper av hver type. Objektiv funksjon - er den totale produksjonskostnaden som må maksimeres:

Ressursgrenser:

La oss bringe problemet til kanonisk form ved å introdusere tilleggsvariabler x 5, x 6 Og x 7:

Det vil vises nedenfor at den optimale produksjonsplanen er vektoren X* =(0; 30; 10; 0), verdien av objektivfunksjonen er 150, dvs. For å maksimere de totale produksjonskostnadene, er det nødvendig å produsere 30 tepper av den andre typen og 10 tepper av den tredje typen. La oss erstatte optimale verdier vektor X i KZLP-restriksjoner:

Vi oppnår at ressursene "arbeid" og "utstyr" er fullt brukt, ressursen "råvarer" er tilgjengelig i overflod:

I dette tilfellet x inn viser at det er 200 kg råvarer igjen.

Så hovedvariablene x v x 2, x 3, x l betyr antall tepper av hver type, og tilleggsvariabler x 5, x 6 deres 7 - volum av underutnyttede ressurser.

Svar. Optimal produksjonsplan X* = (0; 30;

10; 0).

Plan, eller akseptabel løsning , KZLP kalles en vektor X =(jc s X 2 ,..., x n), som tilfredsstiller betingelser (2.3.2)-(2.3.4).

Hvis alle komponentene i den grunnleggende løsningen til systemet med CLLP-begrensninger er ikke-negative, kalles en slik løsning referanseløsning eller referanseplan. Antall positive komponenter i referanseplanen kan ikke overstige T.

Referanseplanen kalles ikke-degenerert, hvis den inneholder T positive komponenter, ellers kalles det degenerert.

Optimal plan eller optimal løsning En plan kalles en plan som leverer den største (minste) verdien av den lineære funksjonen (2.3.1).

Settet med alle planer for OPS (hvis de eksisterer) er konveks polyeder. Hvert hjørne (ekstremt) punkt av løsningspolyederet tilsvarer referanseplan(ikke-negative grunnleggende løsninger av KZLP-likningssystemet). Hver referanseplan bestemmes av systemet T lineært uavhengige vektorer inneholdt i et gitt system av P vektorer D, D,..., A s. Hvis det er en optimal plan, så er det et hjørnepunkt av beslutningspolyederet der lineær funksjon når sin høyeste (laveste) verdi.

For å finne den optimale planen er det nok å undersøke kun referanseplanene. Den øvre grensen for antall referanseplaner i en oppgave bestemmes av antall kombinasjoner S t s (se avsnitt 1.4).

Eksempel 2.3.3. Få en løsning på problemet vedr optimal bruk begrensede ressurser (løs AP P):

Løsning. La oss bringe problemet til kanonisk form ved å introdusere flere variabler x 3, x 4 og x 5:

La oss finne alle støtteplanene for restriksjonssystemet til denne KZLP (l? - 5; /77 - 3); deres antall overstiger ikke 10:

Ved å bruke Jordan-Gauss-metoden (se avsnitt 1.4) skriver vi ut alle de grunnleggende løsningene til ligningssystemet (tabell 2.3.2).

Antall basis Nei det går ikke løsninger	Basis						Plan

Blant ti grunnleggende løsninger fem støtte:

De angitte referanseplanene i fig. 2.3.1 tilsvarer henholdsvis følgende hjørnepunkter og verdiene til CF i dem:

Ris. 2.3.1.

I følge teorien LP optimal løsning finnes blant referanseplanene.

Dermed nås maksimalverdien lik 2300 av objektivfunksjonen på punktet I på referanseplan X 5 = (70; 80; 0; 60; 0).

Svar. Optimal oppgaveplan: x ( = 70, x 2 = 80, objektiv funksjon verdi f(x v x 2) = 2300.