Ulike former for LPP-notasjon (generell, kanonisk, symmetrisk)

Legg igjen en kommentar 6,950

Side 1

Problemets kanoniske form er preget av følgende tre trekk: 1) et homogent system av restriksjoner 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 ved at det er lett å finne det første toppunktet til det mulige området.

Tenk på den kanoniske formen for det lineære programmeringsproblemet og Jordan - Gauss-elimineringsmetoden.

Den kanoniske formen for et lineært programmeringsproblem viser seg ofte å være praktisk.

Når systemet av begrensninger transformeres til den kanoniske formen for det lineære programmeringsproblemet, må ulikheter (12) og (13) erstattes med likheter. For dette introduseres flere ikke-negative variabler.

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

I hovedsak kan (4) - (5) betraktes som den kanoniske formen for et ikke-lineært programmeringsproblem, siden metodene presentert i kap. Vanligvis, i problemer med ikke-lineær programmering, blir ikke kravet til et heltall av variabler fremsatt.

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.

Den kanoniske formen for problemer legger ingen tilleggsfunksjoner til det vurderte beregningsskjemaet.

Tenk først på den andre kanoniske formen for minimumsproblemet.

Simplex metaalgoritmen kan deles inn i to trinn. På det første trinnet finner man den grunnleggende løsningen ved å eliminere variablene. Hvis det blir funnet, har vi den kanoniske formen for problemet for overgangen til andre trinn. På det andre trinnet sjekkes det om det er et avgrenset optimum. Hvis det eksisterer, bestemmes de tillatte grunnleggende løsningene og hvor den optimale velges.

Hvis problemet løses i kanonisk form, brukes bare en del av operasjonene introdusert i andre ledd. Så for det kanoniske minimumsproblemet er det bare tilfellet i avsnitt 3.4.1 som er realisert, og bare operasjonene med syklisk permutasjon av kolonner, sveiping av en kolonne gjennom den vertikale grensesonen, korrigering av strukturelle brudd og en del av trunkeringsoperasjonen er behov for. Symmetrisk, når det kanoniske problemet løses maksimalt, realiseres bare tilfellet i avsnitt 3.4.2, og operasjoner med syklisk radpermutasjon, sveiping av en rad gjennom den horisontale grensesonen, korrigering av strukturelle brudd og andre deler av trunkeringsoperasjonen er behov for. Ellers legger ikke den kanoniske formen til problemet noen ytterligere detaljer.

I første del av introduksjonen ble det vist hvordan et generelt lineært programmeringsproblem kan reduseres til en av de kanoniske formene. For kanonisk (på den annen side er beskrivelsen av den sekvensielle forbedringsmetoden formelt forenklet, siden det ikke er behov for å vurdere to alternativer for brudd på optimalitetsbetingelsene og to alternativer for å nå neste toppunkt. Likevel er det i mange tilfeller bruk av metoden fremfor de kanoniske problemformene viser seg å være å foretrekke, og i denne delen vil vi fokusere på variantene av metoden som oppnås for spesielle lineære programmeringsproblemer.

Sider: 1

lineære programmeringsproblemer

2.1. Definisjon og oppføringsform

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

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 legge til litt verdi til 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. Til hver avgjørelse
ulikhet (2.2.1) tilsvarer den unike løsningen av ligning (2.2.2) og ulikheten
, og omvendt til hver løsning av ligning (2.2.2) med
samsvarer med vedtaket
ulikhet (2.2.1).

Bevis. La være
løsning av ulikhet (2.2.1). Deretter. La oss ta nummeret
... Det er klart det
... Ved å erstatte i ligning (2.2.2), får vi

Den første delen av teoremet er bevist.

La nå vektoren tilfredsstiller ligning (2.2.2) med
, dvs. forkaste den ikke-negative verdien på venstre side av den siste likheten
, vi får osv.

Dermed etablerer det beviste teoremet faktisk muligheten for å redusere ethvert LP-problem til den kanoniske formen. For å gjøre dette er det tilstrekkelig å introdusere en ekstra ikke-negativ variabel i hver begrensning, som har form av en ulikhet. Dessuten, i ulikheter i formen (1.2.1) vil disse variablene komme inn 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 en simpleksmetode for det kanoniske LP-problemet i studiet av objektivfunksjonen for et minimum. I de oppgavene hvor du må finne det maksimale
, er det nok å vurdere funksjonen
, finn minimumsverdien, og endre deretter tegnet til det motsatte, bestem ø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 en grafisk metode brukes for å løse det. La det være nødvendig å finne den maksimale (minimum) verdien av funksjonen
med restriksjoner

(3.1.1)

Denne metoden er basert på evnen til å grafisk representere regionen med gjennomførbare løsninger på problemet, dvs. tilfredsstillende system (3.1.1), og finne den optimale løsningen blant dem. Domenet av gjennomførbare løsninger på problemet er konstruert som skjæringspunktet (felles del) av domenene av løsninger til hver av de gitte begrensningene (3.1.1). Hver av dem definerer et halvplan med en grense
,
... For å bestemme hvilket av de to halvplanene som er løsningens domene, er det tilstrekkelig å erstatte koordinatene til et punkt som ikke ligger på en rett linje inn i 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 dette punktet.

Skjæringspunktet mellom disse halvplanene danner et bestemt område, kalt løsningspolygonet, som er et konveks sett. (Anta at systemet med begrensninger er kompatibelt, og polygonen til dets løsninger er avgrenset.) For å finne den optimale løsningen blant de mulige løsningene, brukes nivålinjer og støttelinjer.

Nivålinje kalles linjen som objektivet fungerer på får en konstant verdi. Nivålinjeligningen har formen

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

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

Verdiene
ø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 det maksimale problemet og i motsatt retning - i det minste problemet (opp til referanselinjen L 2).

La oss gi en løsning på eksempel 1.1. Husk at du må finne det maksimale av funksjonen
med restriksjoner

Løsning. Vi bygger området med gjennomførbare løsninger. La oss nummerere begrensningene til problemet. I et rektangulært kartesisk koordinatsystem (fig. 2) bygger vi en rett linje

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

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

og løsningsdomenet for begrensning (2). Finn fellesdelen av halvplanene til løsningene, ta hensyn til begrensninger (3). Det oppnådde området med mulige løsninger vil bli uthevet i fig. 2 med en mørk farge.

Bygge en nivålinje
og vektor
som angir økningsretningen til funksjonen og vinkelrett på den rette linjen

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

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

Løsning. Vi bygger regionen med tillatte løsninger (se fig. 3), vektoren
og en av nivålinjene
... Flytt nivålinjen i motsatt retning
, siden problemet med å finne minimum av funksjonen blir løst. I dette tilfellet går støttelinjen gjennom punkt A (fig. 3), hvis koordinater kan finnes fra systemets løsning

Så,
... Vi beregner.

Kommentar. Faktisk, i form av regionen gjennomførbare løsninger og den objektive funksjon
LP-problem kan ha en enkelt løsning, et uendelig sett med løsninger, eller ikke ha en enkelt løsning.

Eksempel 3.2. Finn minimum av en funksjon
med restriksjoner

Løsning. Vi bygger området med tillatte løsninger, normalen til nivålinjene
og en av nivålinjene som har fellestrekk med dette området. Flytte nivålinjen i motsatt retning av normalen , siden problemet med å finne minimum av funksjonen blir løst. Nivålinje normal
og normalen til grenselinjen , i hvilken retning nivålinjene beveger seg, er parallelle, siden deres koordinater er proporsjonale
... Derfor faller støttelinjen 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 sett med optimale løsninger, som er punktene i segmentet
... Disse punktene
,
finner vi ved å løse de tilsvarende ligningssystemene:

;
;

,
;
,
;

;
.

Vi beregner.

Svar:
på
,
.

Eksempel 3.3. Løs et lineært programmeringsproblem

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

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

Svar:
.

Et lineært programmeringsproblem av formen ax = b hvor a er en matrise av koeffisienter, b er en vektor av begrensninger.
Eksempel:

I hvert LP-problem søkes verdiene til variablene under forutsetning av at:

disse verdiene tilfredsstiller et visst system med lineære ligninger eller ulikheter;
ved disse verdiene vil objektivfunksjonen gå til et minimum eller maksimum.

Instruksjon. Velg antall variabler og antall linjer (antall begrensninger). Den resulterende løsningen lagres i en Word-fil.

En av de universelle LP-metodene er simpleksmetoden, som imidlertid kan brukes dersom LP-problemet har en kanonisk form.

Definisjon... LP-problemet har en kanonisk form hvis alle begrensninger i systemet kun består av likninger (bortsett fra ulikheter som uttrykker variablenes ikke-negativitet) og den objektive funksjonen må minimeres.
Et eksempel på et slikt LP-problem i kanonisk form er oppgave 1 - et balansert transportproblem med et system av begrensninger (1) og en objektiv funksjon (2).
I de fleste økonomiske problemer inkluderer imidlertid restriksjonssystemet i utgangspunktet ikke bare ligninger, men også ulikheter.

Uttalelse. Ethvert generelt LP-problem kan reduseres til en kanonisk form.
Reduksjonen av det generelle LP-problemet til den kanoniske formen oppnås ved å introdusere nye (de kalles tilleggsvariabler).
Systemet av begrensninger (3) i dette problemet består av fire ulikheter. Ved å introdusere tilleggsvariabler y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, kan du gå til systemet med restriksjoner:

Disse tilleggsvariablene y Jeg har en helt klar økonomisk betydning, nemlig at de betyr mengden ubrukt driftstid (maskinstans Jeg-te typen).
For eksempel, hvis maskiner av den første typen jobbet i alle 18 timer, så er x + y = 18, derfor er y 1 = 0. Men vi innrømmer muligheten for ufullstendig bruk av driftstiden til den første maskinen x + y<18. В этом случае y 1 blir positiv og kan anses som en ubrukt frist. For eksempel, å vite løsningen på dette problemet fra avsnitt 3.3.2, x = 12, y= 6, kan vi konkludere fra systemet av begrensninger (3.9) at y 1 = y 2 = y 3 = 0, og y 4 = 12 - 6 = 6. Det vil si at maskiner av den første, andre, tredje typen bruker arbeidstiden sin fullt ut. Men den fjerde bilen er bare halvlastet, 6 timer, og står på tomgang ved en gitt optimal plan. Kanskje, etter slike konklusjoner, vil lederen av foretaket ønske å laste det med annet arbeid, leie det ut for denne gang osv.
Så, ved å introdusere tilleggsvariabler, kan vi redusere enhver ulikhetstype-begrensning til en ligning.

Vurder blandingsproblemet. Systemet med restriksjoner er som følger:
Ulikhetene var rettet mot "mer", og ved å introdusere tilleggsvariabler y 1, y 2, y 3 ≥ 0, må de trekkes fra venstre side for å utjevne den med høyre. Vi får systemet med restriksjoner i kanonisk form:
Variabler y i vil også gi økonomisk mening. Hvis du husker det praktiske innholdet i problemet, vil variabelen y 1 bety mengden av overflødig stoff A i blandingen, y 2 - mengden av overflødig stoff V i blandingen, y 3 - overskudd MED i blandingen.
Problemet med å finne maksimumsverdien til objektivfunksjonen kan reduseres til å finne minimumsverdien for funksjonen - F i lys av det åpenbare i påstanden maks F = –min (- F). Se på bildet: hvis på et tidspunkt x= x 0 funksjon y= F(x) når sitt maksimum, deretter funksjonen y= –F(x) symmetrisk til den om aksen OKSE, på samme punkt x 0 når et minimum, og F maks = - (- F min) kl x = x 0 .

Produksjon. For å representere LP-problemet i en kanonisk form, er det nødvendig:

ulikheter inkludert i systemet med begrensninger av problemet, transformeres til ligninger ved å introdusere tilleggsvariabler;
hvis den objektive funksjon F→ maks (maksimert), den erstattes med en funksjon - F→ min (som er minimert).

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 problemet med maksimering til problemet med minimering; gå fra ulikhetsbegrensninger til likhetsbegrensninger og erstatte variabler som ikke overholder ikke-negativitetsbetingelsen. Maksimering av en funksjon tilsvarer minimering av samme funksjon, tatt med motsatt fortegn, og omvendt.

Regelen for å redusere et lineært programmeringsproblem til den kanoniske formen er som følger:

hvis det i den opprinnelige oppgaven 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 begrensningene er negativ, bør denne begrensningen multipliseres med -1;
hvis det er ulikheter mellom begrensningene, blir de transformert 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 den kanoniske formen:

min L = 2x 1 + x 2 - x 3;
2x 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.

Vi introduserer utjevningsvariablene i hver ligning i systemet av begrensninger x 4, x 5, x 6... Systemet vil bli skrevet i form av likheter, og i restriksjonssystemets første og tredje ligning variablene x 4, x 6 legges inn på venstre side med "+"-tegnet, og i den andre ligningen variabelen x 5 angis 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.

Frie termer i kanonisk form må være positive, for dette multipliserer vi 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 med begrensninger og den objektive funksjonen og skrive variablene i stigende rekkefølge av indeksen, 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.

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

Ideen om simpleksmetoden konsekvent forbedring av planen, ligger i det faktum at, med utgangspunkt i en innledende støtteløsning, konsekvent rettet bevegelse ved støtteløsninger av problemet til den optimale.

Verdien av objektivfunksjonen reduseres ikke med denne bevegelsen for oppgaver maksimalt.

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

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

Enkel metodealgoritme

1. Den matematiske modellen av problemet bør være kanonisk. Hvis det er ikke-kanonisk, må det bringes til den kanoniske formen.

2. Finn den originale støtteløsningen og kontroller den for optimalitet.
For å gjøre dette, fyll ut simplekstabell 1.
Vi fyller ut alle radene i tabellen i det første trinnet i henhold til dataene til systemet med restriksjoner og den objektive funksjonen.

Følgende tilfeller er mulige når du løser problemer på maksimum:

1. Hvis alle koeffisientene til den siste raden i simplekstabellen DJ ³ 0, så funnet

løsning optimal.

2 Hvis minst én koeffisient DJ £ 0, men for den tilsvarende variabelen er det ikke et eneste positivt evalueringsforhold, da er 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 relasjon, så må du gå til en annen referanseløsning.

4.E hvis det er flere negative koeffisienter i den siste linjen, da til basisvariabelkolonnen(Bp) introduser det variabel som tilsvarer den største negative koeffisienten i absolutt verdi.

5. Dersom minst én koeffisient Dk< 0 ,deretter k - th kolonne vi godtar for verten.

6. For ledende linje vi aksepterer den som tilsvarer minimal gratis medlemsholdning bi til positive koeffisienter ledende, k - det kolonne.

7. Et element som ligger i skjæringspunktet mellom ledende rader og en kolonne 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 overføres til neste simplekstabell

· resten av koeffisientene er funnet av "rektangel"-regelen

Vi får en ny støtteløsning, som vi sjekker for optimalitet:

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

Hvis ikke, fyll ut den 8. trinns simplekstabellen og så videre.

Hvis den objektive funksjonen F (X) krever å finne minimumsverdi, deretter kriteriet optimaliteten til problemet er en ikke-positive odds 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å, i løpet av dens anvendelse, de ønskede resultatene (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 (element 2 ") i tilfelle de samme minimumsverdiene av forholdet

vil nås for flere rader i tabellen T (q) samtidig. Så, ved neste iterasjon, vil kolonne b (β (q + 1)) inneholde null elementer.

I den originale innstillingen kan LPP-er tillate ulike former for opptak. Så i noen oppgaver er det nødvendig å maksimere den objektive funksjonen, i andre - å minimere; noen lineære begrensninger kan være i form av likheter, andre som ulikheter, og så videre.

For ensartetheten til LPP-posten, den såkalte kanonisk form poster.

De sier at ZLP er skrevet i kanonisk form hvis den har følgende form:

Legg merke til følgende trekk ved den kanoniske formen:

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

2) alle lineære begrensninger, bortsett fra kravet om ikke-negativitet av variabler, har form av likheter;

alle variabler er underlagt ikke-negativitetskrav.

La oss vise at enhver LPP kan reduseres til en kanonisk form.

1) Hvis det i LPP kreves å maksimere målfunksjonen f, så setter vi g = - f og krever at funksjonen g minimeres. Du får en ny LPP, som tilsvarer den opprinnelige i den forstand at hver optimal løsning på det opprinnelige problemet vil være den optimale løsningen på det nye problemet og omvendt.

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

Vi erstatter denne begrensningen med følgende to begrensninger:

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

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

3) Anta at i LPP kreves det at ikke alle variabler er ikke-negative. Deretter hver variabel , som kravet om ikke-negativitet ikke er pålagt, kan representeres som forskjellen mellom to ikke-negative variabler:

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

Med de angitte metodene reduseres enhver LPP til den kanoniske formen.

Eksempel. Bring til kanonisk form

La oss gjøre de beskrevne handlingene.

Nå får vi ZLP i kanonisk form:

2.7. Konseptet med den grunnleggende planen zlp.

La ILP gis i kanonisk form (2.3 - 2.5). Anta at ligningssystemet (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 tilstanden
settet med verdier av variabler (2.7) tilfredsstiller også begrensninger (2.5). Derfor er (2.6). akseptabel avgjørelse fra LPP.

En gjennomførbar løsning (2.7) kalles grunnleggende tillatt vedtak eller grunnleggende plan for ZLP. Samtidig 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 LPP er løsbart, er det en optimal støtteplan.

3. Enkel metode for å løse zlp

3.1. Generelle kjennetegn og hovedstadier av simpleksmetoden

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

Enhver LPP kan løses ved simpleksmetoden eller dens ubestembarhet kan oppdages. Mange spesialklasser av LPP kan løses med andre metoder som er mer effektive for disse klassene. Imidlertid er fordelen med simpleksmetoden dens allsidighet. For nesten alle datamaskiner er det utviklet standardprogrammer for å løse LPP ved simpleksmetoden.

La oss beskrive den generelle ideen om simpleksmetoden.

Vi antar at LPP er skrevet i kanonisk form og at objektivfunksjonen må minimeres. Som vi allerede vet, bør den optimale planen søkes blant støtteplanene til LPP. Simplex-metoden itererer ikke over alle grunnlinjeplanene (noe som ofte ville være umulig på grunn av deres enorme antall), men, med utgangspunkt i en innledende grunnlinjeplan, flyttes den sekvensielt til andre grunnlinjeplaner med en reduksjon i målfunksjonen. Simplex-metoden slutter å virke når enten en optimal grunnlinjeplan er funnet eller problemet er uavgjørelig.

Når du løser LPP ved hjelp av simpleksmetoden, kan følgende stadier skilles:

1) bringe LPP til den kanoniske formen;

2) reduksjon av systemet med lineære ligninger til Jordan-formen med ikke-negative høyresider med en samtidig sjekk for ubestembarhet av LPP på grunn av inkonsistensen i systemet med lineære begrensninger;

3) forskning av den grunnleggende planen for optimalitet;

4) undersøkelse av LPP for uavgjørlighet på grunn av uavgrenset nedenfra på ODR for den objektive funksjonen;

5) overgang til ny, «bedre» referanseplan.