Kanoniske poster. Enkel metode for å løse et lineært programmeringsproblem

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 å bringe 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 kanonisk problem LP når man studerer målfunksjonen 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, bestemme ønsket maksimalverdi
.

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å evnen til å grafisk avbilde et område tillatte løsninger oppgaver, 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 objektiv funksjontar 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 origo, 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 opprinnelige problemet krever fastsettelse av maksimum lineær funksjon, så 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 av planen, 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. Matematisk modell oppgaver skal 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å på stadiet for å velge verdien av r (seksjon 2") i tilfelle der det 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.

I den opprinnelige formuleringen kan PLP tillate ulike former for opptak. I noen problemer kreves det derfor å maksimere den objektive funksjonen, i andre kreves det å minimere den; noen lineære begrensninger kan ha form av likheter, andre - ulikheter, etc.

For å sikre ensartethet i registreringen av PAP, den såkalte kanonisk form poster.

ZLP sies å være skrevet i kanonisk form hvis den har følgende form:

La oss merke seg følgende trekk ved den kanoniske formen:

1) det er nødvendig å minimere den objektive funksjonen;

2) alle lineære restriksjoner, bortsett fra kravene til ikke-negativitet av variabler, har form av likheter;

Det stilles ikke-negativitetskrav til alle variabler.

La oss vise at enhver ZLP kan reduseres til kanonisk form.

1) Hvis det i ZLP er nødvendig å maksimere objektivfunksjonen f, setter vi g = - f og krever å minimere funksjonen g. Resultatet vil være en ny ZLP, som tilsvarer den originale i den forstand at hver optimal løsning på det opprinnelige problemet vil være optimal løsning ny oppgave og omvendt.

2) Anta at ZLP har en lineær begrensning av formen

La oss erstatte denne begrensningen med følgende to begrensninger:

Hvor z - en ny variabel som introduseres i objektivfunksjonen med en koeffisient på 0 (med andre ord, variabelen z er ikke introdusert i objektivfunksjonen). Verdien av variabelen z kan ignoreres etter å ha løst et nytt problem.

På samme måte er visningsbegrensningen erstattet av to begrensninger:

3) La oss anta at i ZLP ikke alle variabler er underlagt kravet om ikke-negativitet. Deretter hver variabel , som ikke er underlagt kravet om ikke-negativitet, kan representeres som forskjellen mellom to ikke-negative variabler:

Hver forekomst av en variabel inn i den objektive funksjonen eller begrensningene erstatter vi den med forskjellen
. Etter å ha løst det nye problemet ved å bruke (2.6), går vi tilbake til de forrige variablene.

Ved å bruke disse teknikkene reduseres enhver ZLP til kanonisk form.

Eksempel. Reduser til kanonisk form

La oss gjøre trinnene beskrevet.

Nå får vi ZLP i kanonisk form:

2.7. Konseptet med en støtteplan.

La VLP gis i kanonisk form (2.3 - 2.5). La oss anta at likningssystemet (2.4) er redusert til Jordan-form med ikke-negative høyresider:

(2.6)

Hvor
.

Ved å likestille de frie variablene til null, får vi den grunnleggende løsningen av systemet (2.4)

På grunn av forholdene
settet med verdier av variabler (2.7) tilfredsstiller også begrensninger (2.5). Derfor er (2.6). akseptabel beslutning fra OPS.

Den tillatte løsningen (2.7) kalles grunnleggende tillatt vedtak eller grunnleggende plan for ZLP. I dette tilfellet sier de at variablene
danne et tillatt grunnlag.

Det viser seg at hvis ODR er avbildet geometrisk, tilsvarer hver støtteplan for ZLP toppunktet til polyederet. Derfor er følgende teorem sann.

Hvis ZLP er løsbar, er det en optimal støtteplan.

3. Enkel metode for å løse problemer

3.1. Generelle kjennetegn og hovedstadier av simpleksmetoden

Grunnleggerne av simpleksmetoden er den sovjetiske matematikeren L.V. Kantorovich og den amerikanske matematikeren J. Dantzig.

Ved å bruke simpleksmetoden kan du løse ethvert problem eller oppdage dets uløselighet. Mange spesielle klasser av problemer kan løses med andre metoder som er mer effektive for disse klassene. Fordelen med simpleksmetoden er imidlertid dens allsidighet. Nesten alle datamaskiner er utviklet standard programmer for løsninger ZLP simpleks- metode.

La oss beskrive den generelle ideen om simpleksmetoden.

Vi tror at ZLP er skrevet i kanonisk form og den objektive funksjonen må minimeres. Som vi allerede vet, bør den optimale planen søkes blant de grunnleggende planene til ZLP. Simplexmetoden går ikke gjennom alle referanseplanene (som ofte ville være umulig på grunn av deres stor mengde), og med utgangspunkt i en initial referanseplan, flyttes den sekvensielt til andre referanseplaner med en reduksjon i målfunksjonen. Simplexmetoden slutter å virke når enten den optimale referanseplanen er funnet eller problemets uløselighet er etablert.

På vedtak fra OPS Simplexmetoden kan brukes til å skille mellom følgende stadier:

1) bringe ZLP til kanonisk form;

2) å redusere systemet med lineære ligninger til Jordan-form med ikke-negative høyresider samtidig som det sjekkes for uløseligheten til LLP på grunn av inkonsistensen i systemet med lineære begrensninger;

3) studie av referanseplanen for optimalitet;

4) studie av ZLP for ubestemthet på grunn av ubegrenset nedenfra på ODD av den objektive funksjonen;

5) overgang til en ny, «bedre» referanseplan.

Side 1

Problemets kanoniske form er preget av følgende tre trekk: 1) et homogent system av begrensninger i form av et ligningssystem; 2) homogene ikke-negativitetsforhold som gjelder for alle variabler involvert i problemet, og 3) maksimering av en lineær funksjon. I dette problemet er alle tre av disse funksjonene krenket.

Den kanoniske formen for det lineære programmeringsproblemet er praktisk fordi startpunktet er lett å finne gyldig område.

La oss vurdere den kanoniske formen for det lineære programmeringsproblemet og Jordan-Gauss-elimineringsmetoden.

Den kanoniske formen for et lineært programmeringsproblem er ofte praktisk.

Når du transformerer et system av begrensninger til den kanoniske formen av et lineært programmeringsproblem, må ulikheter (12) og (13) erstattes av likheter. For å gjøre dette introduseres flere ikke-negative variabler.

Bevis at parvis pendlende reelle matriser samtidig reduseres til den kanoniske formen til Oppgave 1128 ved en likhetstransformasjon ved bruk av en ortogonal matrise.

I hovedsak kan (4) - (5) betraktes som den kanoniske formen for det ikke-lineære programmeringsproblemet, siden metodene skissert i kap. Vanligvis i ikke-lineære programmeringsproblemer er det ingen krav om at variablene skal være heltall.

Typer restriksjoner og metoder for deres transformasjon.

Problemets kanoniske form er preget av homogeniteten til systemet av begrensninger i form av et ligningssystem; maksimere den objektive funksjonen; betingelsen om ikke-negativitet for alle variabler som er involvert i problemet.

Ingen tilleggsfunksjoner den kanoniske formen for problemer bidrar ikke til beregningsskjemaet som vurderes.

La oss først vurdere den andre kanoniske formen for minimumsproblemet.

Simplex-mete-algoritmen kan deles inn i to trinn. På det første trinnet finner man en grunnleggende løsning ved å eliminere variabler. Hvis det blir funnet, har vi den kanoniske formen for problemet for å gå til andre trinn. Det andre trinnet er å sjekke om det er et avgrenset optimum. Hvis det eksisterer, bestemmes tillatte grunnleggende løsninger og hvorfra den optimale velges.

Hvis problemet løses i kanonisk form, brukes bare en del av operasjonene introdusert i andre ledd. Således, for det kanoniske minimumsproblemet, realiseres bare tilfellet i avsnitt 3.4.1, og bare operasjonene med syklisk omorganisering av kolonner, passering av kolonnen gjennom den vertikale kantsonen, korrigering av strukturelle brudd og en del av trunkeringsoperasjonen er nødvendig. Symmetrisk, når man løser det kanoniske maksimale problemet, realiseres bare tilfellet i paragraf 3.4.2, og operasjoner med syklisk omorganisering av strenger, passering av en streng gjennom den horisontale kantsonen, korrigering av strukturelle brudd og en annen del av trunkeringsoperasjonen er behov for. Ellers gir ikke den kanoniske formen for problemet noen ekstra spesifisitet.

Første avsnitt av innledningen viste hvordan felles oppgave Lineær programmering kan reduseres til en av dens kanoniske former. For kanoniske problemer er beskrivelsen av metoden for sekvensiell forbedring formelt forenklet, siden det ikke er behov for å vurdere to alternativer for brudd på optimalitetsbetingelser og to alternativer for å nå neste toppunkt. Dette øker imidlertid størrelsen basismatrise A [ /, J ], som hovedsakelig bestemmer kompleksiteten til en shat. I mange tilfeller viser det seg imidlertid å være å foretrekke å bruke metoden på de kanoniske formene av problemet, og i denne delen vil vi dvele ved varianter av metoden oppnådd for spesielle lineære programmeringsproblemer.

Sider: 1

MP-oppgaver

Generelt PAP kalt <,=,>=)bi (i=1,n) (2) underlagt xj>

Symmetrisk < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Kanonisk blandet.

min f(x) = -maks(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Geometrisk tolkning av den objektive funksjonen og begrensningene til ZLP. Geometrisk formulering av ZLP.

La oppgaven f=c1x1+c2x2-max (1) gis

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Planen for oppgaven (x1,x2) er et punkt på planet. Hver ulikhet med-vi 2 representasjoner. er et halvt fly. Et halvplan er et konveks sett. Konveks kalles et sett der punktene til segmentet som forbinder (x1 og x2) som hører til dette settet også tilhører settet. C-ma 2 representerer skjæringspunktet mellom halvplan. Ved kryssing kan du få:

1) konveks polygonalt lukket område.

2) konveks åpent polygonalt område

3) enkelt poeng

4) tomt sett

5) bjelke og segment

Geometrisk tolkning av objektivfunksjonen: Funksjon 1 er en familie av parallelle rette linjer, som kalles nivålinjer (linjer med konstant verdi av objektivfunksjonen). De partielle deriverte av funksjonen med hensyn til x1 og x2 viser økningshastigheten til objektivfunksjonen langs koordinatene til aksene. Gradientvektor viser retningen for den raskeste økningen i objektivfunksjonen For oppgave 1-3 forlater gradientvektoren = (c1; c2) punktet (0,0) og rettes til punktet med koordinater (c1; c2). Gradientvektoren er vinkelrett på nivålinjene. Skjæringspunktet mellom halvplan kalles vanligvis område for tillatte løsninger (ADD).

Hovedteoremet til LP. Skjematisk diagram løsning av ZLP, som følger av denne teoremet.

Hvis ZLP har en løsning, når målfunksjonen en ekstrem verdi ved minst ett av ytterpunktene til planpolyederet. Hvis objektivfunksjonen når en ekstrem verdi ved mer enn ett ekstrempunkt, når den en og samme verdi, som er en konveks lineær kombinasjon av dem, når som helst. Når du løser ZLP manuelt, er det praktisk å bruke en tabelloppføring.

BP		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	buh	bo1 bo2 bon-m

Algoritme for simpleksmetoden.

1. bringe problemmodellen til kanonisk form;

2. finne den første referanseplanen;

3. skriv oppgaven i en enkel form. bord;

5. flytte til en ny referanseplan, til en ny symp. bord. For å gå over til en ny referanseplan er det nok å erstatte én grunnvariabel med en ledig. Variabelen som er inkludert i grunnlaget og den tilsvarende oppløsningskolonnen bestemmes av det største absolutte negative elementet i f-raden. Variabelen som ekskluderer fra grunnlaget og den tilsvarende oppløsningslinjen bestemmes av det minste simpleksforholdet, dvs. forholdet mellom elementene i enhetskolonnen og det tilsvarende elementet i oppløsningskolonnen. Simplexforholdet er en ikke-negativ størrelse. I skjæringspunktet mellom den løsende raden og den løsende kolonnen er det et løsende element med hensyn til simpleks transformasjon neste regel: 1. elementene i den tillate strengen er delt inn i det tillate elementet; 2. elementene i oppløsningskolonnen deles inn i oppløsningselementet og endrer fortegn til det motsatte; 3. de gjenværende elementene i tabellen er omorganisert i henhold til rektangelregelen:

bij bis bkj=(bkj*bis-bij*bks)/bi

Det andre dualitetsteoremet.

hvis ett av de doble problemene har en optimal plan, så er det andre også løsbart, dvs. har en optisk plan. I dette tilfellet faller ekstremverdiene til objektivfunksjonene sammen (j=fra 1 til n) Σcjxj*= (i=fra 1 til m)Σbiyi* hvis den er i originalen. problem, objektivfunksjonen er ubegrenset på settet med planer, deretter inn dobbelt problem restriksjonssystemet er inkonsekvent.

Teorem om rangeringen til TK-matrisen.

Rangeringen av matrise A for transportproblemet er én mindre enn antall ligninger: r(A)=m+n-1.

39. Algoritme for å konstruere den første referanseplanen til ZLP.

For å finne den første referanseplanen kan vi foreslå følgende algoritme:

1. skriv oppgaven i form av en Jordan-tabell slik at alle elementene i kolonnen med frie termer er ikke-negative, dvs. ulikheten aio>=0 (i=1,m) ble tilfredsstilt. De ligningene der de frie leddene er negative, multipliseres først med -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1…..amn
f=		-c1…. -cn

Transformer tabellen ved å bruke Jordan-elimineringstrinn, og bytt ut nullene i venstre kolonne med den tilsvarende x. Samtidig, på hvert trinn permissive kan velges enhver kolonne som inneholder minst ett positivt element. Den løsende raden bestemmes av det minste av forholdet mellom de frie leddene og de tilsvarende positive elementene i den løsende kolonnen. Hvis det i elimineringsprosessen støtes på en 0-rad, hvis elementer er null, og frileddet er ikke-null, så har systemet med begrensningsligninger ingen løsninger. Hvis vi møter en 0-rad der det, bortsett fra frileddet, ikke er andre positive elementer, så har ikke settet med restriktive ligninger ikke-negative løsninger Hvis settet med restriktive ligninger ledd, så etter et visst antall trinn vil alle nullene i venstre kolonne bli erstattet med x og derved oppnå en viss basis, og følgelig en tilsvarende referanseplan.

40. Algoritme for å konstruere den optimale referanseplanen til ZLP.

Ho sin første støtteplan undersøkes for optimalitet.

Hvis det ikke er negative elementer i f-raden (ikke medregnet frileddet), er -planen optimal. Hvis det heller ikke er nullelementer i f-raden, så er det bare en optimal plan; hvis det er minst en null blant elementene, er det et uendelig antall optimale planer. Hvis det er minst ett negativt element i f-raden, og det ikke er noen positive elementer i den tilsvarende kolonnen, er objektivfunksjonen ikke begrenset i det mulige området. Problemet er ikke løsbart. Hvis det er minst ett negativt element i f-raden, og i hver kolonne med et slikt element er det minst ett positivt element, så kan du flytte til en ny referanseplan som er nærmere den optimale. For å gjøre dette tas kolonnen med et negativt element i f-raden som ettergivende; De bestemmer oppløsningsstrengen fra minimum simpleksrelasjonen og utfører Jordan-elimineringstrinnet. Den resulterende referanseplanen undersøkes igjen for optimalitet. Dette gjentas til den optimale referanseplanen er funnet eller problemets uløselighet er etablert.

Algoritme for Gomori-metoden.

1. Ved å bruke simpleksmetoden finner man den optimale planen for problemet. Hvis alle komponenter optimal plan hel, så er det optimalt. Ellers går du til trinn 2

2. Blant ikke-heltallskomponentene bør du velge den med brøkdel er den største, og ved å bruke den tilsvarende raden i simplekstabellen formulerer du den korrekte avskjæringen ved å bruke formelen

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Transformer den formulerte ulikheten til en ekvivalent nulllikhet og inkluder den i en simplekstabell med en optimal plan uten heltall

4. Det resulterende utvidede problemet løses ved hjelp av simpleksmetoden. Hvis den resulterende planen ikke er heltall, fortsett til trinn 2.

Hvis det under løsningsprosessen dukker opp en linje med et ikke-heltalls fri ledd og andre heltallskoeffisienter, så har ikke den tilsvarende ligningen en løsning i heltall. I dette tilfellet, og originalt problem kan ikke avgjøres i heltall. Gomoris metode har begrenset anvendelse. Med dens hjelp er det tilrådelig å løse små problemer, fordi... antall interaksjoner kan være svært stort.

Ulike former for notasjon av ZLP (generelt, kanonisk, symmetrisk)

MP-oppgaver: bestemmelse av den optimale planen, bestemmelse av det optimale produksjonsvolumet, bestemmelse av den optimale kombinasjonen av avlinger, dannelse av den optimale pakken av eiendeler, maksimering av bankfortjeneste, etc.

General ZLP kalles maksimering (minimisering) problem lineær funksjon f=Σcj*xj-max(min) (1) under lineære begrensninger ∑aij *xj(=<,=,>=)bi (i=1,n) (2) gitt xj>=0(j=1,n1), xj-vilkårlig (j=n1+1,n)(3) hvor cj,aij, bi-konstanter tall .

Symmetrisk Formen for å skrive ZLP kalles problemet med å maksimere funksjon (1) under lineære begrensninger i signerte ulikheter< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >eller = og ikke-negative variabler. Kanonisk Formen for å skrive ZLP kalles problemet med maksimal funksjon (1) under lineære begrensninger av likheter og ikke-negative variabler. Enhver annen form kalles blandet.

min f(x) = -maks(-f(x))

Transformasjonen av en ulikhet til en ligning og vice versa utføres på grunnlag av Lemma: for hver løsning x1...xn av ulikheten a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) og omvendt. Hver løsning x1…xn,xn+1 av ligning 6 og ulikhet 7 tilsvarer en løsning x1…xn av ulikhet 5.

For å gå fra den bakre sim-formen til den bakerste kanoniske formen, må du gå inn balanse (utjevne) variabler. Dette er basert på ulikhetsteoremet: enhver ulikhet kan representeres som en ligning eller en enkel ulikhet.