Enkel metode kunstig grunnlag. Løse lineære programmeringsproblemer ved bruk av kunstig basismetode
Når vilkåret inneholder begrensninger som likhet. La oss vurdere problemet:
max(F(x)=∑c i x i |∑a ji x i =b j, j=1,m; x i ≥0).
De såkalte "kunstige variablene" R j introduseres i begrensningene og i målfunksjonen som følger:
∑a ji x+R j =b j, j=1,m ;F(x)=∑c i x i -M∑R j
Ved introduksjon av kunstige variabler i en metode kunstig grunnlag de er tildelt en tilstrekkelig stor koeffisient M til målfunksjonen, som har betydningen av en straff for å introdusere kunstige variabler. Ved minimering legges kunstige variabler til målfunksjonen med en koeffisient M. Innføring av kunstige variabler er tillatt dersom de i prosessen med å løse problemet suksessivt forsvinner.
En simplekstabell, som settes sammen under løsningsprosessen ved bruk av kunstig basismetoden, kalles utvidet. Den skiller seg fra den vanlige ved at den inneholder to linjer for målfunksjonen: en for komponenten F = ∑c i x i, og den andre for komponenten M ∑R j La oss vurdere prosedyren for å løse problemet ved å bruke et spesifikt eksempel.
Eksempel 1. Finn maksimum for funksjonen F(x) = -x 1 + 2x 2 - x 3 under begrensningene:
2x 1 +3x 2 +x 3 =3,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
La oss bruke den kunstige basismetoden. La oss introdusere kunstige variabler i problembegrensningene
2x 1 + 3x 2 + x 3 + R1 = 3;
x 1 + 3 x 3 + R2 = 2;
Objektiv funksjon F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).
La oss uttrykke summen R 1 + R 2 fra systemet av restriksjoner: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3, deretter F(x) = -x 1 + 2x 2 - x 3 - M (5 - 3x 1 - 3x 2 - 4x 3) .
Ved kompilering av den første simplekstabellen (tabell 1) vil vi anta at de opprinnelige variablene x 1 , x 2 , x 3 er ikke-grunnleggende, og de introduserte kunstige variablene er grunnleggende. I maksimeringsproblemer blir fortegnet til koeffisientene for ikke-grunnleggende variabler i F- og M-raden reversert. Tegnet til konstantverdien i M-linjen endres ikke. Optimalisering utføres først langs M-linjen. Velg ledende kolonne og rad, alle simpleks transformasjoner Ved bruk av den kunstige basismetoden utføres de som i den konvensjonelle simpleksmetoden.
Den maksimale negative koeffisienten i absolutt verdi (-4) bestemmer den ledende kolonnen og variabelen x 3, som vil gå inn i grunnlaget. Minimum simpleksforhold (2/3) tilsvarer den andre raden i tabellen, derfor må variabelen R 2 ekskluderes fra grunnlaget. Det ledende elementet er skissert.
I den kunstige basismetoden returneres ikke lenger kunstige variabler som er ekskludert fra grunnlaget, så kolonnene med elementer i slike variabler er utelatt. Bord 2. redusert med 1 kolonne. Ved å foreta en omberegning av denne tabellen, går vi videre til tabellen. 3., hvor linjen M er tilbakestilt, kan den fjernes. Etter å ha eliminert alle kunstige variabler fra grunnlaget, får vi det tillatelige grunnleggende løsning av det opprinnelige problemet, som i eksemplet under vurdering er optimalt:
x 1 = 0; x 2 = 7/9; F maks = 8/9.
Hvis løsningen ikke er optimal ved eliminering av M-strengen, fortsetter optimaliseringsprosedyren og utføres ved bruk av den vanlige simpleksmetoden. La oss vurdere et eksempel der det er begrensninger av alle typer: ≤,=,≥
Eksempel 2. Finne minimumsverdi funksjoner F(x) = 2x 1 + 3x 2 - x 3 under følgende begrensninger
2x 1 +x 2 -3x 3 ≥6,
x 1 -x 2 +2x 3 =4,
x 1 +x 2 +x 3 ≤5,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
La oss multiplisere den første av restriksjonene med (-1) og introdusere tilleggsvariabler x 4, x 5 og den kunstige variabelen R i restriksjonene som følger:
2x 1 -x 2 +3x 3 +x 4 =-6,
x 1 -x 2 +2x 3 +R=4,
x 1 +x 2 +x 3 +x 5 =5,
La x 4, R og x 5 være grunnleggende variabler, og x 1, x 2, x 3 – ikke-grunnleggende. Objektivfunksjon F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).
I den første (tabell 4) endrer ikke koeffisientene for ikke-grunnleggende variabler i F-rad og M-rad fortegn, siden funksjonen minimeres. Frileddet i kunstig basismetoden i M-raden er tatt med motsatt fortegn. Løsningen tilsvarer tabellen. 4 er ikke gyldig fordi det er en negativ dummy term.
La oss velge den ledende kolonnen og raden i samsvar med trinn 2 i løsningsalgoritmen. Etter omregning får vi tabell. 5. Optimalisering av løsningen i den kunstige basismetoden (trinn 5 i algoritmen) utføres først langs M-linjen. Som et resultat introduserer vi x 3 i grunnlaget, og ekskluderer variabelen R fra vurdering, og reduserer antall kolonner. Etter omregning får vi tabell. 6, som tilsvarer den optimale løsningen på problemet.
Tabell 4
| grunnleggende variabler | Gratis medlemmer | Ikke-grunnleggende variabler | ||
| x 1 | x 2 | x 3 | ||
| x 4 | -6 | -2 | -1 | 3 |
| R | 4 | 1 | -1 | 2 |
| x 5 | 5 | 1 | 1 | 1 |
| F | 0 | 2 | 3 | -1 |
| M | -4 | -1 | 1 | -2 |
Tabell 5
| grunnleggende variabler | Gratis medlemmer | Ikke-grunnleggende variabler | ||
| x 4 | x 2 | x 3 | ||
| x 1 | 3 | -1/2 | 1/2 | -3/2 |
| R | 1 | 1/2 | -3/2 | 7/2 |
| x 5 | 2 | 1/2 | 1/2 | 5/2 |
| F | -6 | 1 | 2 | 2 |
| M | -1 | -1/2 | 3/2 | -7/2 |
Tabell 6
Det nødvendige minimum for funksjonen F(x) er lik frileddet til F-raden i tabellen. 6, tatt med motsatt fortegn, siden min F(x) = -max(-F(x)); x 4 = x 2 = 0;
x 1 = 24/7; x 3 = 2/7; x 5 = 9/7; F min = 46/7;
Algoritmen for kunstig basismetode har følgende funksjoner:
1. På grunn av det faktum at den første referanseløsningen av det utvidede problemet inneholder kunstige variabler inkludert i målfunksjon med koeffisient - M(i en maksimal oppgave) eller + M(i minimumsproblemet) består estimater av utvidelser av vektorer av tilstander av to ledd og 
, hvorav en ikke er avhengig av M, og den andre 
kommer an på M. Fordi M vilkårlig stor sammenlignet med enhet ( M>> 1), så i det første trinnet av beregningen for å finne vektorene som er introdusert i grunnlaget, brukes bare vilkårene for estimatene 
.
2. Vektorer som tilsvarer kunstige variabler som er utledet fra grunnlaget for referanseløsningen er unntatt fra vurdering.
3. Etter at alle vektorer som tilsvarer kunstige variabler er ekskludert fra grunnlaget, fortsetter beregningen som vanlig simpleks metode ved å bruke estimater uavhengig av M.
4. Overgangen fra å løse det utvidede problemet til å løse det opprinnelige problemet gjøres ved å bruke teoremene 4.1-4.3 som er bevist ovenfor.
Eksempel 4.4. Løse et problem lineær programmering kunstig basismetode
.
Løsning. La oss lage en utvidet oppgave. Vi introduserer ikke-negative kunstige variabler med en koeffisient (alltid) +1 i venstre side av ligningene til systemet av begrensninger. Det er praktisk å skrive de introduserte kunstige variablene til høyre for ligningene. I den første ligningen legger vi inn , i den andre - . Dette problemet er et problem med å finne maksimum, derfor blir de introdusert i objektivfunksjonen med en koeffisient - M. Vi får
Problemet har en innledende referanseløsning 
med enhetsgrunnlag 
.
Vi beregner estimater av tilstandsvektorene basert på referanseløsningen og verdien av objektivfunksjonen på referanseløsningen.
. 
.
Vi registrerer kildedataene i en simplekstabell (tabell 4.6).
Tabell 4.6
Samtidig anslår og 
for enkelhets skyld skriver vi på to linjer: i den første - termer som ikke er avhengige av M, i det andre - vilkårene 
, avhengig av M. Verdier 
praktisk å indikere uten M, men husk at det er tilstede der.
Den første støtteløsningen er ikke optimal, siden det maksimale problemet har negative estimater. Vi velger nummeret på vektoren som er lagt inn i grunnlaget for referanseløsningen, og nummeret på vektoren utledet fra grunnlaget. For å gjøre dette, beregner vi inkrementene til objektivfunksjonen når vi introduserer hver av vektorene med et negativt estimat i grunnlaget og finner maksimum av denne økningen. I dette tilfellet vil vilkårene for estimatene (uten M) er neglisjert så lenge som minst én periode 
(Med M) vil ikke være forskjellig fra null. I denne forbindelse kan linjen med vilkårene for estimatene ikke være i tabellen så lenge linjen er til stede 
. Vi finner kl k= 3.
I den tredje kolonnen " " velger vi koeffisient 1 i den andre raden som oppløsningselement og utfører Jordan-transformasjonen.
Vektoren utledet fra grunnlaget er ekskludert fra vurdering (krysset ut). Vi skaffer referanseløsningen 
med grunnlag 
(Tabell 4.7). Løsningen er ikke optimal fordi det er et negativt estimat 
= —
1.
Tabell 4.7
I kolonnen " " tar vi det eneste positive elementet som løsende og går videre til en ny referanseløsning 
med grunnlag 
(Tabell 4.8).
Tabell 4.8
Denne referanseløsningen er den eneste optimale løsningen på det utvidede problemet, siden i maksimalproblemet er estimatene for alle vektorer som ikke er inkludert i grunnlaget positive. Ved teorem 4.1 originalt problem også har optimal løsning, som oppnås fra den optimale løsningen av det utvidede problemet ved å forkaste null kunstige variabler, dvs. X* = (0,0,6,2).
Svar:maks Z(X) = -10 kl 
.
Eksempel 4.5. Løs et lineært programmeringsproblem med blandede begrensninger ved å bruke den kunstige basismetoden
Løsning. Vi reduserer det lineære programmeringsproblemet til kanonisk form. For å gjøre dette introduserer vi tilleggsvariabler i henholdsvis første og tredje begrensning. Vi får
.
Vi lager et utvidet problem, som vi introduserer kunstige variabler for i henholdsvis andre og tredje ligning. Vi får
Dette utvidede problemet har en første støtteløsning
Med enhetsbasis 
, 
. Vi beregner estimater av tilstandsvektorene basert på referanseløsningen og skriver dem i simplekstabellen på samme måte som i forrige eksempel. Løsningen er ikke optimal, siden i minimumsproblemet vektorene og har positive estimater. Forbedre støtteløsninger. Hver referanseløsning har sin egen tabell. Alle tabeller kan skrives under hverandre, og kombinere dem til en enkelt tabell (tabell 4.9).
Tabell 4.9
Vi bestemmer hvilken av vektorene eller inn i grunnlaget for den første støtteløsningen vil føre til større reduksjon målfunksjon. Vi finner kl k= 2, det vil si at det er bedre å introdusere vektoren i grunnlaget. Vi får den andre støtteløsningen med grunnlaget 
. Objektiv funksjon 
. Denne løsningen er heller ikke optimal, siden vektoren har en positiv verdi 
. Vi introduserer vektoren i basisen, vi får den tredje referanseløsningen med basisen 
. Objektiv funksjon 
. Denne løsningen er optimal, men ikke den eneste, siden vektoren som ikke er inkludert i grunnlaget har et nullestimat. Derfor er det nødvendig å gå over til en ny referanseløsning, som også vil være optimal. For å gjøre dette må du introdusere vektoren i grunnlaget.
La oss gå videre til den fjerde (optimale) referanseløsningen
Med grunnlag 
, hvori 
. Optimale løsninger på det utvidede problemet har null kunstige variabler. Derfor (ved teorem 4.1) har den opprinnelige oppgaven også to optimale løsninger 
Og 
. Vi skriver ikke tilleggsvariabler i den optimale løsningen av det opprinnelige problemet.
Svar: 
på 
, 
, 
, 
.
Ordet simpleks
Ordet simpleks i engelske bokstaver (translit) - simpleks
Ordet simpleks består av 8 bokstaver: e og k l m p s s
Betydningen av ordet simpleks. Hva er simpleks?
Enkelt
Simplex (fra latin simplex - enkel) (matematisk), det enkleste konvekse polyederet gitt nummer dimensjoner n. Når n = 3, er den tredimensjonale strukturen en vilkårlig, inkludert uregelmessig, tetraeder.
TSB. - 1969-1978
En simpleks er en konveks polygon i n-dimensjonalt rom med n+1 toppunkter som ikke ligger i samme hyperplan. S. fremhevet i egen klasse fordi i n-dimensjonalt rom alltid n punkter ligger i samme hyperplan.
slovar-lopatnikov.ru
SIMPLEX er en konveks polygon i n-dimensjonalt rom med n+1 toppunkter som ikke ligger i samme hyperplan. S. er skilt ut som en egen klasse fordi i n-dimensjonalt rom alltid n punkter ligger i samme hyperplan.
Lopatnikov. - 2003
Sub simpleks
Sub simplex Bruksanvisning og dosering: Oralt, under eller etter måltider og om nødvendig før leggetid. Rist flasken kraftig før bruk.
Løse ZLP ved simpleksmetoden med kunstig grunnlag
For at suspensjonen skal begynne å strømme fra pipetten...
Sub simplex Aktiv ingrediens ›› Simetikon* (Simetikon*) latinsk navn Sab simplex ATX:›› A02DA Karminative legemidler Farmakologisk gruppe...
Ordbok over medisiner. – 2005
SAB® SIMPLEX (SAB® SIMPLEX) Oral suspensjon fra hvit til grå-hvit, litt tyktflytende, med en karakteristisk fruktig (vanilje-bringebær) lukt. 100 ml simetikon 6.919 g...
SJOKKE SIMPLEX
CHOQUET SIMPLEX er et ikke-tomt kompakt konveks sett X i et lokalt konveks rom E, som har følgende egenskap: når E er innebygd som et hyperplan i rommet, er det en utstikkende kjegle.
Sheffield Simplex
"Sheffield-Simplex" - lett maskingevær pansret kjøretøy Armerte styrker Det russiske imperiet. Utviklet av det britiske selskapet Sheffield-Simplex basert på chassiset til sin egen personbil...
en.wikipedia.org
Norditropin Simplex
Norditropin Simplex Indikasjoner: Veksthemning hos barn på grunn av veksthormonmangel eller kronisk nyresvikt (i prepubertal alder), Shereshevsky-Turner syndrom...
NORDITROPIN® SIMPLEX® (NORDITROPIN SimpleXx) Oppløsning for subkutan administrasjon 1,5 ml (1 sylinderampulle) somatropin 10 mg 1,5 ml - patroner (1) - konturcelleemballasje (1) - papppakninger.
Katalog over medisiner "Vidal"
STANDARD ENKEL
STANDARD SIMPLEX - 1) S. s. - et simpleks med dimensjon n i rommet med toppunkter i punktene e i=(0,..., 1,..., 0), i=0,..., n (den enheten er på i-te plass), dvs.
Matematisk leksikon. — 1977-1985
Dobbel simpleks metode
Dual simplex-metoden kan brukes til å løse et lineært programmeringsproblem, hvor de frie vilkårene til ligningssystemet kan være alle tall. I normalen simpleks algoritme planen skal alltid være gyldig.
en.wikipedia.org
russisk språk
Enkelt/.
Morfemisk-staveordbok. - 2002
Søk i forelesninger
Et eksempel på å løse et problem ved bruk av kunstig basismetode.
Finn minimum av en funksjon F=-2×1+3×2 – 6×3 – x4 under forhold
Løsning. La oss skrive det ned denne oppgaven i form av hovedproblemet: finn maksimum av funksjonen F1=2×1 – 3×2 + 6×3 + x4 under forhold
I likningssystemet til det siste problemet, vurder vektorene til koeffisientene for de ukjente:
A1= A2= EN 3= EN 4= EN 5= EN 6=
Blant vektorene A1,…, EN 6 bare to enkle ( EN 4 og EN 5). Derfor legger vi til en ekstra ikke-negativ variabel til venstre side av den tredje ligningen av restriksjonssystemet x 7 og vurdere det utvidede problemet med å maksimere funksjonen
F=2×1 – 3×2 + 6×3 + x4 – Mx7
under forhold
Det utvidede problemet har en referanseplan X=(0; 0; 0; 24; 22; 0; 10), definert av et system med tre enhetsvektorer: EN 4 , A5 , A7 .
Tabell 1
| Jeg | Basis | Сσ | A0 | -3 | —M | |
| A1 | A2 | A3 | A4 | A5 | A6 | P7 |
| A4 | -2 | |||||
| A5 | ||||||
| A7 | —M | -1 | -1 | |||
| m+1 | -8 | |||||
| m+2 | -10 | -1 | -2 |
Vi kompilerer tabell (1) av iterasjon I, som inneholder fem rader. For å fylle ut 4. og 5. linje finner vi F 0 og differanseverdier zj – cj(j=):
F 0 = 24–10M;
z1–c1= 0–M;
z2–c2 = 4+M;
z3–c3= –8–2M;
z4–c4=0+M;
z5–c5=0+M;
z6–c6= 0+M;
z7–c7=0+M;
Verdier F 0 og zj–cj består av to begreper, hvorav ett inneholder M, og den andre er ikke det.
For enkelhets skyld i den iterative prosessen, antallet som består av M, skriv i 5. linje, og begrepet som ikke inneholder M, – i 4. linje.
I den 5. linjen i tabell 1 i kolonnene med vektorer Аj (j= ) det er to negative tall (-1 Og -2). Tilstedeværelsen av disse tallene indikerer at denne referanseplanen for det utvidede problemet ikke er optimal. La oss gå videre til den nye referanseplanen for det utvidede problemet.
Kunstig basismetode.
Vi introduserer vektoren i grunnlaget A3. For å bestemme vektoren som er ekskludert fra grunnlaget, finner vi θ=min(22/4; 10/2)=10/2. Derfor er vektoren A7 utelukket fra grunnlaget. Det gir ingen mening å legge inn denne vektoren i noen av de påfølgende basene, så i fremtiden er ikke kolonnen til denne vektoren fylt ut (tabell 2 og 3).
Vi komponerer tabell II av iterasjon (tabell 2). Den inneholder bare fire rader, siden den kunstige vektoren er ekskludert fra grunnlaget.
Tabell 2
| Jeg | Basis | Сσ | A0 | -3 | |
| A1 | A2 | A3 | A4 | A5 | A6 |
| A4 | -1 | ||||
| A5 | -1 | ||||
| A3 | 1/2 | -1/2 | -1/2 | ||
| m+1 | -4 |
Som det fremgår av tabellen. 2, for det opprinnelige problemet er referansen planen X=(0;0;5;34;2).
La oss sjekke det for optimalitet. For å gjøre dette, vurder elementene i den fjerde linjen. I denne raden i vektorkolonnen A6 tilgjengelig et negativt tall(-4). Følgelig er ikke denne referanseplanen optimal og kan forbedres ved å introdusere vektoren A6. Vektoren er ekskludert fra grunnlaget A5. Vi kompilerer tabell III med iterasjon.
Tabell 3
I 4. linje i tabell 3 blant tallene ∆j ingen negative. Dette betyr at den nye referanseplanen for det opprinnelige problemet X*=(0; 0; 11/2; 35; 0; 1) er optimal. I denne forbindelse, verdien lineær formFmax = 68.
Løsningen på dette problemet kan utføres ved å bruke én tabell der alle iterasjoner er sekvensielt registrert.
©2015-2018 poisk-ru.ru
Alle rettigheter tilhører deres forfattere. Dette nettstedet krever ikke forfatterskap, men gir gratis bruk.
Brudd på opphavsrett og brudd på personopplysninger
Til nå har vi grundig vurdert problemet, hvis løsning ble utført på grunnlag av den enkleste algoritmen til simpleksmetoden, siden alle begrensningene var av formen mindre enn eller lik. I dette tilfellet danner tilleggsvariablene til problemet et enhetsgrunnlag. Men det kan vise seg at restriksjonssystemet presenteres i kanonisk form, men det er ikke redusert til enhetsgrunnlag.
Ved løsning av slike problemer ble det introdusert kunstig basismetode. Det er spesielt praktisk når antallet variabler betydelig overstiger antall ligninger.
La oss vurdere algoritmen for å løse problemet ved hjelp av simpleksmetoden med et kunstig grunnlag ved å bruke et eksempel.
Eksempel 1
Finn maksimalt Z=4X1+2X2+X3
3Х1+2Х2+Х3=15
Хj³0, j=1,...,3
La oss gå videre til den kanoniske formen:
X1+X2+X3-X4=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3=15
Хj³0, j=1,...,5
Zmax=4X1+2X2+X3+0×X4+0×X5
Dette systemet restriksjoner har ikke en enhetsbasis, siden tilleggsvariabelen X4 har en koeffisient på minus én, og den tredje begrensningen ble representert av en ligning og ikke har en basisvariabel. For å ha et enhetsgrunnlag, innfører vi i tilsvarende begrensninger kunstige variabler y1 og y2 med positive koeffisienter (+1).
Det skal bemerkes at kunstige variabler kun introduseres for den matematiske formaliseringen av problemet. Derfor må beregningsopplegget være slik at kunstige variabler ikke kan inkluderes i den endelige løsningen blant grunnvariablene. For dette formål, for kunstige variabler i objektivfunksjonen, introduseres en koeffisient M, som betegner en veldig stort antall. I praksis (spesielt når du løser et problem på en datamaskin), i stedet for M, tar de et spesifikt stort antall, for eksempel 10000. Dessuten, når du løser et problem til det maksimale, legges denne koeffisienten inn i objektivfunksjonen med et minus tegn, og ved løsning til et minimum, med et plusstegn. Nå skal vi løse T (M)-problemet, hvis objektivfunksjon inneholder objektivfunksjonen til Z-oppgaven og kunstige variabler med en koeffisient ±M, dvs.
T=Z-M S yi, når man løser for maksimum av objektivfunksjonen og
T=Z+M S y, når man løser for minimum av objektivfunksjonen
I vårt tilfelle:
X1+X2+X3-X4+y1=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3+y2=15
Хj³0, j=1,...,5
Тmaks= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)
Dette problemet er løst i simplekstabeller, men for enkelhets skyld er objektivfunksjonen delt inn i 2 linjer:
I den første linjen skriver vi ned estimater som ikke inneholder koeffisienten M;
Den andre linjen inneholder estimater for hver fri variabel, som inneholder koeffisienten M.
Beregningen av elementene (poengene) til disse to linjene utføres i henhold til formel (2). Eneste forskjell:
Ved beregning av Z-rad estimater må koeffisientene Cj som inngår i Z-funksjonen tas i betraktning;
Ved beregning av M-linjeestimat tas det ikke hensyn til denne koeffisienten, og M tas ut som en felles faktor.
For at T-oppgaven og Z-oppgaven skal være like, er det nødvendig at yi er lik null. Derfor, så lenge y i ikke er null, velges løsningskolonnen basert på estimatene i den andre raden ved bruk av simpleksmetodealgoritmen.
Først etter at alle y i blir lik null, vil videre beregning utføres ved å bruke den første indekslinjen, dvs. -vanlig Z-oppgave.
Dessuten, når den kunstige variabelen er utledet fra basisen, vil vi kaste den ut av simplekstabellen, og den neste simplekstabellen vil ikke ha den tidligere oppløsningskolonnen.
Det er en sammenheng mellom de optimale løsningene av M-problemet og Z-problemet, etablert av følgende teorem:
1. Hvis i den optimale løsningen på M-problemet alle kunstige variabler (y i) er lik null, så vil denne løsningen være den optimale løsningen på Z-problemet.
2. Hvis i den optimale løsningen av M-problemet er minst én av de kunstige variablene forskjellig fra null, så har Z-problemet ingen løsning på grunn av inkompatibiliteten til systemet av begrensninger.
3. Hvis M-problemet viser seg å være uløselig (T®+¥ eller -¥), så er det opprinnelige problemet også uløselig enten på grunn av inkompatibiliteten til systemet av begrensninger eller fordi funksjonen Z er ubegrenset.
La oss lage den første simplekstabellen. Ved løsning ved bruk av M-metoden kan løsningskolonnen i M-raden velges ikke i henhold til det største negative estimatet i absolutt verdi (når man løser for maksimum) og ikke i henhold til det største positive estimatet (når man løser for minimum) ), men ifølge den som viser Y raskere fra grunnlaget. I i dette eksemplet den løsende kolonnen vil være kolonnen til den frie variabelen X2 med en poengsum på (-3).
Tabell 3.1.
Først simplex bord
Fylling av Z-linjen utføres i henhold til formel (2):
a00 = 0 × 8– 0 = 0
a01 =0 × 2– 4 = -4
a02 =0 × 1– 2 = -2
a03 =0 × 1– 1 = -1
а02 =0 × 0– 0 = 0
Fyller ut M-linjen:
а¢00 = -М × 8 + (–М) × 15 = -23М
a¢01 = -M × 1 + (–M) × 3 = -4M
а¢02 = -М × 1 + (–М) × 2= -3М
а¢03 = -М × 1+ (–М) × 1 = -2М
а¢04 = -М ×(-1)+ (–М) × 0 = 1М
Vi tar ut M som en felles faktor.
Den siste kolonnen i oppløsningslinjen inneholder 0, så kolonnen til den frie variabelen X4 overføres uten endringer.
Tabell 3.2.
Andre simpleksbord
I den andre tabellen får vi en degenerert løsning, siden vi får to identiske minimale simpleksrelasjoner. Derfor finner vi forholdet mellom elementene i kolonnen ved siden av den løsende til elementene i den løsende kolonnen, tatt i betraktning fortegnet.
Tabell 3.3.
Tredje simpleksbord
Nå løser vi ved å bruke den vanlige simpleksmetoden.
Tabell 3.4.
Fjerde simplekstabell
| St.P | Cj | |||
| B.P. | Ci | ai0 | X5 | X4 |
| X3 | -1 | |||
| X1 | ||||
| X2 | -2 | -1 | ||
| Z |
I evalueringslinjen er alle elementer ikke-negative verdier, derfor oppnås den optimale løsningen:
Zmax=15 Xopt(0,7,1,0,0)
Eksempel 2
Problemet ble løst til minimum (Z®min) av objektivfunksjonen. Ved siste iterasjon fikk vi følgende tabell:
Tabell 3.5.
Siste simplekstabell
| St.P | Cj | ||||
| B.P. | Ci | ai0 | X1 | X3 | X4 |
| U1 | M | -1/2 | -1/2 | -1/2 | -1 |
| X5 | 1/2 | 1/2 | 1/2 | ||
| X2 | 15/2 | 3/2 | 1/2 | ||
| Z | -1 | ||||
| M | -1/2 | -1/2 | -1/2 | -1 |
I T-problemet ble det oppnådd en optimal løsning, siden det ikke er flere positive estimater i M-raden, d.v.s. valget av en løsende kolonne er umulig, og U1 er i grunnlaget. I dette tilfellet har det opprinnelige problemet ingen løsning pga inkompatibilitet av restriksjonssystemet.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Advarsel
Vil du slette alle celler?
Lukk Slett
Instruksjoner for dataregistrering. Tall legges inn som heltall (eksempler: 487, 5, -7623 osv.), desimaler (eks. 67., 102.54 osv.) eller brøker. Brøken skal legges inn på formen a/b, hvor a og b (b>0) er heltall eller desimaltall. Eksempler 45/5, 6.6/76.4, -7/6.7 osv.
Enkel metode
Eksempler på løsning av ZLP ved bruk av simpleksmetoden
Eksempel 1. Løs følgende lineære programmeringsproblem:
 |
Høyre side av begrensningene til ligningssystemet har formen:
La oss skrive ned gjeldende referanseplan:
 |
Denne referanseplanen er ikke optimal, siden siste linje det er negative elementer. Det største negative elementet i modul er (-3), derfor er vektoren inkludert i grunnlaget x 
på 
. min(40:6, 28:2)=20/3 tilsvarer linje 1. Vektoren kommer ut av basisen x 3. La oss gjøre gaussisk eliminering for kolonnen x 2, gitt at det ledende elementet tilsvarer rad 1. La oss tilbakestille alle elementene i denne kolonnen bortsett fra det ledende elementet. For å gjøre dette, legg til linjene på linje 2, 3, 4 med linje 1, multiplisert med henholdsvis -1/3, 1/6, 1/2. Deretter deler vi linjen med det ledende elementet med det ledende elementet.
Denne referanseplanen er ikke optimal, siden den siste raden har et negativt element (-3), derfor inkluderer grunnlaget vektoren x 1 . Vi bestemmer hvilken vektor som kommer ut av grunnlaget. For å gjøre dette, beregner vi 
på 
. min(44/3:11/3, 62/3:5/3)=4 tilsvarer linje 2. Vektoren kommer ut av basisen x 4. La oss gjøre gaussisk eliminering for kolonnen x 1, gitt at det ledende elementet tilsvarer rad 2. La oss tilbakestille alle elementene i denne kolonnen bortsett fra det ledende elementet. For å gjøre dette, legg til linjene 1, 3, 4 med linje 2 multiplisert med henholdsvis 1/11, -5/11, 9/11. Deretter deler vi linjen med det ledende elementet med det ledende elementet.
Simplextabellen vil ha følgende form:
Gjeldende referanseplan er optimal, siden i linje 4 under variablene 
det er ingen negative elementer.
Løsningen kan skrives slik: 
.
Verdien av den objektive funksjonen på dette tidspunktet: F(X)=
.
Eksempel 2. Finn maksimum av en funksjon
Løsning.
Basisvektorer x 4 , x 3 derfor alle elementer i kolonner x 4 , x 3, nedenfor horisontal linje må være null.
Tilbakestill alle kolonneelementer til null x 4, bortsett fra det ledende elementet. For å gjøre dette, legg til rad 3 med rad 1 multiplisert med 4. Tilbakestill alle elementene i kolonnen til null x 3, bortsett fra det ledende elementet. For å gjøre dette, legg til linje 3 med linje 2 multiplisert med 1.
Simplextabellen vil ha formen:
Denne referanseplanen er ikke optimal, siden den siste raden har et negativt element (-11), derfor inkluderer grunnlaget vektoren x 2. Vi bestemmer hvilken vektor som kommer ut av grunnlaget. For å gjøre dette, beregner vi 
på 
. Derfor er den objektive funksjonen ubegrenset ovenfra. De. det lineære programmeringsproblemet er uløselig.
Eksempler på løsning av ZLP ved bruk av kunstig basismetode
Eksempel 1. Finn maksimum for en funksjon
Løsning Siden antall basisvektorer må være 3, legger vi til en kunstig variabel, og til objektivfunksjonen legger vi denne variabelen multiplisert med −M, der M er et veldig stort tall:
 |
Koeffisientmatrisen til ligningssystemet har formen:
Basisvektorer må derfor alle elementer i kolonnene under den horisontale linjen være null.
La oss tilbakestille alle elementene i kolonnen bortsett fra det ledende elementet. For å gjøre dette, legg til linje 5 med linje 3 multiplisert med -1.
Simplextabellen vil ha formen:
Denne referanseplanen er ikke optimal fordi det er negative elementer i siste rad. Det største absolutte negative elementet er (-5), derfor er vektoren inkludert i grunnlaget Vi bestemmer hvilken vektor som kommer ut av grunnlaget. For å gjøre dette, beregner vi 
på 
tilsvarer rad 3. En vektor kommer ut av grunnlaget La oss gjøre et gaussisk unntak for kolonnen, gitt at det ledende elementet tilsvarer rad 3. La oss nullstille alle elementene i denne kolonnen, bortsett fra det ledende elementet. For å gjøre dette, legg til linjene linje 5 med linje 3 multiplisert med 1. Deretter deler du linjen med det ledende elementet med det ledende elementet.
Simplextabellen vil ha følgende form:
Denne referanseplanen er ikke optimal fordi det er negative elementer i siste rad. Det største absolutte negative elementet er (-3), derfor er vektoren inkludert i grunnlaget Vi bestemmer hvilken vektor som kommer ut av grunnlaget. For å gjøre dette, beregner vi 
på 
tilsvarer rad 1. Vektoren kommer ut av grunnlaget x 2. La oss gjøre gaussisk eliminering for kolonnen x 1 , gitt at det ledende elementet tilsvarer rad 1. La oss tilbakestille alle elementene i denne kolonnen bortsett fra det ledende elementet. For å gjøre dette, legg til linjene på linje 2, 3, 4 med linje 1, multiplisert med henholdsvis 3/2, -1/10, 3/2. Deretter deler vi linjen med det ledende elementet med det ledende elementet.
Simplextabellen vil ha følgende form:
Denne referanseplanen er ikke optimal fordi det er negative elementer i siste rad. Det største negative elementet i modul (-13/2), derfor inkluderer grunnlaget vektoren x 3. Vi bestemmer hvilken vektor som kommer ut av grunnlaget. For å gjøre dette, beregner vi 
på 
tilsvarer linje 3. Vektoren kommer ut av grunnlaget x 5 . La oss gjøre gaussisk eliminering for kolonnen x 3, gitt at det ledende elementet tilsvarer rad 3. La oss tilbakestille alle elementene i denne kolonnen bortsett fra det ledende elementet. For å gjøre dette, legg til linjene på linje 1, 2, 4 med linje 3, multiplisert med henholdsvis 5/3, 25/9, 65/9. Deretter deler vi linjen med det ledende elementet med det ledende elementet.
Simplextabellen vil ha følgende form:
Gjeldende referanseplan er optimal, siden det ikke er negative elementer under variablene i linje 4−5.
Løsningen på det opprinnelige problemet kan skrives som følger:
Eksempel 2. Finn optimal plan lineære programmeringsproblemer:
Koeffisientmatrisen til ligningssystemet har formen:
Basisvektorer x 4 , x 5 , x 6 derfor alle elementer i kolonner x 4 , x 5 , x 6, under den horisontale linjen skal være null.
Tilbakestill alle kolonneelementer til null x 4, bortsett fra det ledende elementet. For å gjøre dette, legg til linje 4 med linje 1 multiplisert med -1. Tilbakestill alle kolonneelementer til null x 5, bortsett fra det ledende elementet. For å gjøre dette, legg til linje 5 med linje 2 multiplisert med -1. Tilbakestill alle kolonneelementer til null x 6, bortsett fra det ledende elementet. For å gjøre dette, legg til linje 5 med linje 3 multiplisert med -1.
Simplextabellen vil ha formen:
I linje 5 er elementene som tilsvarer variablene x 1 , x 2 , x 3 , x 4 , x 5 , x 6 er ikke-negative, og tallet ligger i skjæringspunktet mellom en gitt rad og kolonne x 0 er negativ. Da har det opprinnelige problemet ikke referanseplan. Derfor er det uavgjørelig.