Methode kunstmatige basis(M-taak).
Voor veel lineaire programmeerproblemen die zijn geschreven in de vorm van het hoofdprobleem en die referentieplannen hebben, zijn er niet altijd m eenheidsvectoren onder de vectoren Pj.
Beschouw het volgende probleem:
Stel dat we het maximum van een functie moeten vinden
F = C 1 X 1 + C 2 X 2 + ……+ C N X N (1)
onder voorwaarden
……………………………………… (2)
Waar B i 0 ( i= l, m), M<.>N en onder de vectoren P1, P2, …, Pn zijn er geen m eenheidsvectoren.
Definitie. De taak om de maximale waarde van een functie te bepalen
F= c 1 X 1 + C 2 X 2 + ……+ C N X N -MX N +1 - ... - MX N + M (3)
onder voorwaarden
……………………………………… (4)
waarbij M een voldoende groot positief getal is, waarvan de specifieke waarde meestal niet gespecificeerd is, wordt een uitgebreid probleem (M-taak) genoemd in relatie tot probleem (1) - (2).
De uitgebreide taak heeft referentieplan
X=(0; 0; ...; 0; b1; B 2 ; ...;bm).
bepaald door het systeem van eenheidsvectoren Pn+1; R n+2 , … R p+t , die de basis vormt van de m-ro-vectorruimte, die wordt genoemd kunstmatig. De vectoren zelf, evenals de variabelen X n + ik ( i=l, M), worden genoemd kunstmatig. Omdat het uitgebreide probleem een referentieplan heeft, kan de oplossing ervan worden gevonden simplex methode.
Stelling Als optimaal X*=( X* 1 , X* 2 , ...; X*N , X*n+1 ; ...; X*n+m) uitgebreide taak (3) - (4) waarden van kunstmatige variabelen X* n + ik =0 ( i=1, M), Dat X*=( X* 1 , X* 2 , ...; X*N) is het optimale plan voor het probleem (1) - (2).
Dus als in het gevonden optimale plan voor het uitgebreide probleem de waarden van de kunstmatige variabelen gelijk zijn aan nul, dan wordt het optimale plan voor het oorspronkelijke probleem verkregen.
De indexlijnwaarden ∆ 0 , ∆ 1 , …, ∆ n bestaan uit twee delen, waarvan er één afhankelijk is van M, maar de ander niet. Vul een simplextabel in die één rij meer bevat dan een gewone simplextabel. In dit geval bevat de (m+2)de lijn de coëfficiënten voor M, en in de (m+1)de – termen die niet bevatten M. Wanneer u van het ene referentieplan naar het andere gaat, wordt een vector die overeenkomt met het grootste negatieve getal in de absolute waarde van de (m+2)de rij in de basis geïntroduceerd. Een kunstmatige vector die van de basis is uitgesloten, wordt niet opgenomen in de volgende simplextabel. Herberekening van simplextabellen bij het verplaatsen van het ene referentieplan naar het andere wordt uitgevoerd volgens algemene regels simplex methode.
Het iteratieve proces langs de (m+2)-lijn gaat door totdat:
ofwel worden niet alle kunstmatige vectoren van de basis uitgesloten;
of niet alle kunstmatige vectoren zijn uitgesloten, maar de (m+2)de rij bevat geen negatieve elementen meer in de indices ∆ 1, …, ∆ n.
In het eerste geval komt de basis overeen met een referentieplan van het oorspronkelijke probleem en gaat de bepaling van het optimale plan verder langs de (m+1)de lijn.
In het tweede geval, als de waarde van ∆ 0 negatief is, heeft het oorspronkelijke probleem geen oplossing; als ∆ 0 =0, dan is het gevonden referentieplan van het oorspronkelijke probleem gedegenereerd en bevat de basis ten minste één van de kunstmatige basisvectoren.
Stadia van het vinden van een oplossing voor het probleem (1) - (2)
kunstmatige basismethode:
Stel een uitgebreid probleem (3) - (4) samen.
Zoek het referentieplan van het uitgebreide probleem.
Door het gebruiken van gewone berekeningen De simplexmethode sluit kunstmatige variabelen uit van de basis. Als resultaat wordt óf het referentieplan van het oorspronkelijke probleem (1) - (2) gevonden, óf de onoplosbaarheid ervan vastgesteld.
Met behulp van het gevonden referentieplan van het probleem (1) - (2) vinden ze ofwel het optimale plan van het oorspronkelijke probleem met behulp van de simplexmethode, ofwel stellen ze de onoplosbaarheid ervan vast.
Voorbeeld.
Zoek het minimum van een functie F= - 2X 1 + 3X 2 - 6X 3 - X 4
P 
met beperkingen:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 ≤22
x 1 -x 2 +2x 3 ≥10
X i ≥0, i=1,4
Oplossing.
Laten we het opschrijven deze opdracht in de vorm van het hoofdprobleem: vind het maximum van de functie F= 2X 1 - 3X 2 + 6X 3 + X 4
met beperkingen:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6= 10
X i ≥0, i=1, 6
Beschouw in het systeem van vergelijkingen van het laatste probleem de vectoren van de coëfficiënten voor de onbekenden:
Onder de vectoren P 1, R 2 , ... P 6 slechts twee enkele (P 4 en P 5). Daarom binnen linkerkant van de derde vergelijking van het probleembeperkingssysteem voegen we een extra niet-negatieve variabele x toe 7 en overweeg het uitgebreide probleem van het maximaliseren van de functie
F= 2X 1 - 3X 2 + 6X 3 + X 4 - Мх7
met beperkingen:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6 +x 7= 10
Het uitgebreide probleem heeft een referentieplan X = (0; 0; 0; 24; 22; 0; 10), gedefinieerd door een systeem van drie eenheidsvectoren: P 4 , P 5 , P 7 .
Het concept van een duaal (adjunct) probleem lineair programmeren.
Bouwregels dubbel probleem.
Bij elk lineair programmeerprobleem (LPP), dat het duale probleem (of adjoint) wordt genoemd, ten opzichte van het oorspronkelijke probleem, dat het directe probleem wordt genoemd.
Het dubbele probleem is geconstrueerd in relatie tot het directe probleem, geschreven in standaardvorm:
F=c 1 x 1 +c 2 x 2 +…+c n x n max (3,6)
a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1,
a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2,
………………………………
a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3,7)
a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1 ,
………………………………
a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,
x j ≥ 0, , l≤ n (3,8)
Het probleem van het vinden van de minimumwaarde van een functie
L = b 1 y 1 + b 2 y 2 + … + b m y m (3,9)
onder voorwaarden
a 11 j 1 + a 12 j 2 +…+ a m1 j m ≥ c 1
a 21 j 1 + a 22 j 2 +…+ a m2 j m ≥ c 2
………………………………
een 1 l j 1 + een 2 l j 2 +…+ een m l j m ≥ c l (3.10)
A l+1,1 j 1 + een l+1,2 j 2 +…+ a l+1, m y m = c ik+1
………………………………
een m1 y 1 + een m2 y 2 +…+ a mn y m = cm
y ik ≥ 0, , k ≤ m (3,11)
wordt duaal genoemd voor probleem (3.6) – (3.8).
De regels voor het construeren van een duaal probleem worden gegeven in de tabel:
|
Structurele kenmerken van ZLP |
Lineair programmeerprobleem |
|
|
Dubbel |
||
|
1. Doelfunctie |
Maximalisatie (max) |
Minimalisatie (min) |
|
2. Aantal variabelen |
n variabelen |
Gelijk aan het aantal beperkingen van het directe probleem (3.7), y i , d.w.z. M |
|
3. Aantal beperkingen |
m beperkingen |
Gelijk aan het aantal variabelen van het directe probleem x j , d.w.z. n |
|
4. Matrix van coëfficiënten in het systeem van beperkingen |
|
|
|
5. Coëfficiënten van variabelen in de doelfunctie |
c 1 ,c 2, …,c n |
b 1 ,b 2, …,b m |
|
6. Rechter deel systemen van beperkingen |
b 1 ,b 2, …,b m |
c 1 ,c 2, …,c n |
|
7. Tekenen in het systeem van beperkingen |
a) x j ≥ 0 - niet-negativiteitsconditie |
De jde beperking heeft het teken “≥” |
|
b) de niet-negativiteitsvoorwaarde wordt niet opgelegd aan de variabele x j |
De j-de beperking heeft het teken “=”. |
|
|
c) de i-de beperking heeft het teken “≤” |
variabele y i ≥0 |
|
|
d) de i-de beperking heeft het teken “=”. |
de niet-negativiteitsvoorwaarde wordt niet opgelegd aan de variabele y i |
|
Opmerking
Het directe maximumprobleem en het duale minimumprobleem zijn wederzijds duale problemen. Daarom kunnen we probleem (3.9) – (3.11) als een direct ZLP beschouwen, en probleem (3.6) – (3.8) als een dubbel probleem. In dit geval blijven de regels voor het construeren van een dubbele PLP behouden, alleen met door die verandering, dat het minimale probleem als het initiële probleem wordt beschouwd.
Als het oorspronkelijke probleem wordt opgelost op max (min), en in het systeem van beperkingen) i-e ( J-f) de beperking heeft het teken “≤” (“≥”), en om het dubbele probleem te construeren is het noodzakelijk:
a) of vermenigvuldig beide delen i e ( J-th) ongelijkheid met (-1) en verander het teken in “≤” (“≥”)
b) of meenemen i-e ( J-e) beperking van gelijkheid door het introduceren van een extra variabele x n+ i ≥0
Laten we de ZLP in de vorm oplossen
In dit geval algemeen schema simplex methode ondergaat enkele veranderingen. Namelijk:
1) Laat de basis van een of andere ondersteunende oplossing en de bijbehorende oplossing bestaan simplex tafel. IN bovenste regel Deze tabel (kolomkoppen) bevat vrije variabelen; de meest linkse kolom bevat basisvariabelen; de meest rechtse kolom is de kolom met vrije leden, en de meeste onderste regel is een touwtje objectieve functie en wordt de vector van relatieve schattingen genoemd. De rest van de tabelinhoud bestaat uit kolommen van de beperkingsmatrix die overeenkomen met de overeenkomstige kolommen met vrije variabelen. De coördinaten van de vector van relatieve schattingen worden gevonden volgens de regel: de vector van de coëfficiënten van de basisvariabelen in de objectieve functie wordt scalair vermenigvuldigd met i de kolom van de simplextabel en trek de coëfficiënt van de doelfunctie voor de overeenkomstige vrije variabele af van het gevonden getal.
2) Als alle relatieve schattingen (onderste rij van deze tabel) niet-negatief zijn, is er een optimale referentieoplossing geconstrueerd.
3) Als er een negatieve schatting is en de bijbehorende kolom (oplossen) uit niet-positieve elementen bestaat, dan is de doelfunctie onoplosbaar Z(X), dat wil zeggen maximaal Z(X) ®+¥.
4) Selecteer anders het leidende element (specificeert de leidende rij) en voer er een Jordan-eliminatiestap mee uit, waarbij u naar een nieuwe simplextabel gaat, die wordt geanalyseerd zoals in punt 2).
Kunstmatige basismethode
De kunstmatige basismethode wordt gebruikt om LP-problemen op te lossen in het geval dat het probleem geen initiële referentieoplossing heeft op basis van eenheidsvectoren.
Laat het LP-probleem worden opgegeven canonieke vorm, dat wil zeggen, het heeft de vorm (2.1.1) en er zit geen eenheidsbasis in. Voor dit probleem construeren we een hulpprobleem (AP): 
Hier w 1 , w 2 ,…, w m– kunstmatige variabelen. Laten we de beperkingen in vectorvorm schrijven: A 1 X 1 +A 2 X 2 +…+Een n x n+Een +1 w 1 +…+A n + m w m =B, Waar , , …, , , , …, , . De vectoren , , ... vormen dus een eenheidsbasis in R M, en alle kunstmatige variabelen die met deze vectoren overeenkomen, zullen basaal zijn. Vervolgens wordt een gewone simplextafel geconstrueerd. Als het probleem geen oplossing heeft vanwege de onbegrensdheid van de objectieve functie, dan heeft het oorspronkelijke probleem om dezelfde reden ook geen oplossing. Laten we aannemen dat we, als resultaat van de noodzakelijke transformaties die bekend zijn uit de simplexmethode, de optimale simplextabel voor de VZ verkrijgen. Dat is duidelijk maximale waarde de doelfunctie VZ is gelijk aan 0, dat wil zeggen max F=0. Als max F<0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F=0. Dan zijn de volgende situaties mogelijk:
1) alle kunstmatige variabelen werden gratis en werden uitgesloten van de tabel. In dit geval schrappen we de kolommen die overeenkomen met de kunstmatige variabelen en de laatste rij. In plaats daarvan wijzen we een nieuwe reeks schattingen toe, maar gebruiken we de oorspronkelijke objectieve functie Z(X). We hebben dus de initiële simplextabel voor het oorspronkelijke LP-probleem verkregen, waarop we de simplexmethode toepassen;
2) bij de optimale oplossing van het probleem blijft ten minste één kunstmatige variabele fundamenteel. Dan:
a) ofwel zijn alle getallen in de regels die overeenkomen met de resterende kunstmatige basisvariabelen gelijk aan 0;
b) of er is er minstens één verschillend van 0.
In het eerste geval doen we hetzelfde als in punt 1). In het tweede geval selecteren we elk element dat niet nul is als leidend element en voeren we een Jordan-eliminatiestap uit. Na een eindig aantal stappen komen we uit bij punt 1) of punt 2)a).
Merk op dat als tussen de vectoren Een j , J=1,2,…,N Als er vectoren waren die de basis konden binnendringen, worden kunstmatige variabelen alleen geïntroduceerd in die vergelijkingen van het systeem van beperkingen waarin er geen basisvariabele is.
Voorbeeld. Maximaliseer de functie Z=X 1 +2X 2 -2X 3 met beperkingen
Oplossing. Laten we het oorspronkelijke lineaire programmeringsprobleem transformeren naar een canoniek probleem (zie (2.1.1). Om dit te doen introduceren we aanvullende niet-negatieve variabelen in de beperkingen. Namelijk in de eerste ongelijkheid: de variabele X 4 met een “+” teken, de tweede – X 5 met een “-” teken (zie §2.2). Het systeem van beperkingen zal de volgende vorm aannemen:
Laten we dit systeem in vectorvorm schrijven: A 1 X 1 +A 2 X 2 +A 3 X 3 +A 4 X 4 +A 5 X 5 =B, Waar
Het is duidelijk dat er in dit systeem van beperkingen geen eenheidsbasis bestaat. Dit betekent dat tussen de vectoren Een j er zijn geen drie noodzakelijke eenheidsvectoren die een basis moeten vormen R 3. Houd er echter rekening mee dat de vector A 4 maakt deel uit van de basis. Het komt overeen met de basisvariabele X 4. Het is noodzakelijk om nog twee eenheidsvectoren te vinden. Hiervoor passen we de kunstmatige basismethode toe. Laten we kunstmatige variabelen introduceren in die beperkingsvergelijkingen waarin de basisvariabele niet aanwezig is X 4 en construeer het volgende hulpprobleem (AP):
F=-w 1 -w 2 ®max
Waar w 1 , w 2 – kunstmatige variabelen. Het systeem van beperkingen op luchtverontreiniging in vectorvorm heeft de vorm: A 1 X 1 +A 2 X 2 +A 3 X 3 +A 4 X 4 +A 5 X 5 +A 6 w 1 +A 7 w 2 =B, waar de vectoren Een j , J=1,2,3,4,5 worden op dezelfde manier gedefinieerd als hierboven, en en . De vectoren dus A 4 , A 6 , A 7 vormen een basis in R 3 en ze komen overeen met basisvariabelen (BP) – X 4 , w 1 , w 2. Alle andere variabelen, namelijk X 1 , X 2 , X 3 , X 5 zijn vrij verklaard (SP). Vervolgens passen we de gebruikelijke simplex-methode toe op de luchtinlaat. Net als voorheen, zie §5.1, wordt het initiële referentieontwerp verkregen door waarden gelijk aan nul toe te kennen aan de vrije variabelen. In dit geval nemen de basisvariabelen waarden aan die gelijk zijn aan de getallen in de overeenkomstige rij van de kolom met vrije coëfficiënten IN, dat is X 1 =X 2 =X 3 =X 5 =0¸ een X 4 =8, w 1 =4, w 2 =12. We bouwen een simplextabel die overeenkomt met het initiële referentieplan:
| SP BP. | x 1 | x 2 | X 3 | X 5 | B |
| x 4 | -3 | ||||
| w 1 | -1 | ||||
| w 2 | -2 | ||||
| F | -4 | -3 | -16 |
Met deze tabel voeren we de noodzakelijke transformaties (zie §5.1) van de simplexmethode uit totdat we een optimale simplextabel verkrijgen of onoplosbaarheid verkrijgen. In ons geval hebben we al bij de tweede stap de volgende simplextabel:
| SP BP. | w 1 | x 2 | X 3 | w 2 | B |
| x 4 | -0,5 | -3 | -0,5 | -0,5 | |
| x 1 | 0,25 | 0,75 | 0,25 | ||
| X 5 | -0,75 | -2 | |||
| F |
Deze tabel is optimaal voor EOI. Tegelijkertijd werden alle kunstmatige variabelen gratis en max F=0. Het doorstrepen van de kolommen die overeenkomen met de dummyvariabelen en de laatste rij, en het toewijzen van een nieuwe rij met schattingen met behulp van de oorspronkelijke doelfunctie Z(X), verkrijgen we de initiële simplextabel voor het oorspronkelijke LP-probleem:
| SP BP. | x 2 | X 3 | B |
| x 4 | -3 | -0,5 | |
| x 1 | 0,75 | ||
| X 5 | -2 | ||
| Z | -2 | 2,75 |
Na analyse van de laatste tabel concluderen we dat het oorspronkelijke LP-probleem geen oplossing heeft vanwege de onbegrensdheid van de objectieve functie.
Voorbeeld. Minimaliseer de functie 
onder beperkingen
Als we aanvullende niet-negatieve variabelen , , , , introduceren en verder gaan met het probleem van het vinden van het maximum van de objectieve functie, zal het oorspronkelijke probleem de vorm aannemen:
De basisoplossing (toelaatbaar plan) heeft de vorm: , a , , w 1 =10, w 2 =5. We bouwen een simplextabel voor het vliegveld die overeenkomt met het initiële referentieplan:
| SP BP. | x 1 | x 2 | X 3 | X 4 | B |
| w 1 | -1 | ||||
| w 2 | -1 | ||||
| x 5 | |||||
| x 6 | -1 | ||||
| F | -1 | -1 | -15 |
Door transformaties uit te voeren met behulp van de Jordan-Gauss-methode, zullen we in de tweede stap een optimale simplextabel van de VZ hebben (5.2.2). Doorstrepen van de kolommen die overeenkomen met de dummyvariabelen en de laatste rij, en toewijzen van een nieuwe rij met scores met behulp van de objectieve functie Z 1 (X), verkrijgen we de initiële simplextabel voor probleem (5.2.1).
Het kunstmatige basismethode-algoritme heeft de volgende kenmerken:
1. Vanwege het feit dat de initiële referentieoplossing van het uitgebreide probleem kunstmatige variabelen bevat die zijn opgenomen in de objectieve functie met een coëfficiënt - M(in een maximale taak) of + M(in het minimumprobleem) bestaan schattingen van uitbreidingen van vectoren van omstandigheden uit twee termen en 
, waarvan er één niet afhankelijk is van M, en de andere 
hangt af van M. Omdat M willekeurig groot vergeleken met eenheid ( M >> 1), waarna in de eerste fase van de berekening om de vectoren te vinden die in de basis zijn geïntroduceerd, alleen de termen van de schattingen worden gebruikt 
.
2. Vectoren die overeenkomen met kunstmatige variabelen die zijn afgeleid van de basis van de referentieoplossing worden buiten beschouwing gelaten.
3. Nadat alle vectoren die overeenkomen met kunstmatige variabelen van de basis zijn uitgesloten, gaat de berekening verder met behulp van de gebruikelijke simplexmethode, waarbij schattingen worden gebruikt die niet afhankelijk zijn van M.
4. De overgang van het oplossen van het uitgebreide probleem naar het oplossen van het oorspronkelijke probleem wordt gemaakt met behulp van de hierboven bewezen stellingen 4.1-4.3.
Voorbeeld 4.4. Los een lineair programmeerprobleem op met behulp van de kunstmatige basismethode
.
Oplossing. Laten we een uitgebreide taak maken. We introduceren niet-negatieve kunstmatige variabelen met een coëfficiënt (altijd) +1 in de linkerkant van de vergelijkingen van het systeem van beperkingen. Het is handig om de geïntroduceerde kunstmatige variabelen rechts van de vergelijkingen te schrijven. In de eerste vergelijking voeren we in, in de tweede -. Dit probleem is een probleem bij het vinden van het maximum, daarom worden ze in de objectieve functie geïntroduceerd met een coëfficiënt - M. We krijgen
Het probleem heeft een initiële referentieoplossing 
met eenheidsbasis 
.
We berekenen schattingen van de conditievectoren op basis van de referentieoplossing en de waarde van de objectieve functie op de referentieoplossing.
. 
.
We leggen de brongegevens vast in een simplextabel (Tabel 4.6).
Tabel 4.6
Tegelijkertijd zijn schattingen en 
voor het gemak van berekeningen schrijven we in twee regels: in de eerste - termen die er niet van afhankelijk zijn M, in de tweede - de voorwaarden 
, afhankelijk van M. Waarden 
handig om zonder aan te geven M, maar houd er rekening mee dat het daar aanwezig is.
De initiële ondersteuningsoplossing is niet optimaal, omdat het maximale probleem negatieve schattingen heeft. We selecteren het nummer van de vector die in de basis van de referentieoplossing is ingevoerd, en het nummer van de vector dat van de basis is afgeleid. Om dit te doen, berekenen we de toenamen van de doelfunctie bij het introduceren van elk van de vectoren met een negatieve schatting in de basis en vinden we het maximum van deze toename. In dit geval zijn de voorwaarden van de schattingen (zonder M) wordt verwaarloosd zolang er minstens één term is 
(Met M) zal niet verschillend zijn van nul. In dit opzicht is het mogelijk dat de lijn met de voorwaarden van de schattingen niet in de tabel staat zolang de lijn aanwezig is 
. Wij vinden op k= 3.
In de derde kolom " " selecteren we coëfficiënt 1 in de tweede rij als het oplossende element en voeren we de Jordan-transformatie uit.
De van de basis afgeleide vector wordt buiten beschouwing gelaten (doorgestreept). We verkrijgen de referentieoplossing 
met basis 
(Tabel 4.7). De oplossing is niet optimaal omdat er sprake is van een negatieve schatting 
= —
1.
Tabel 4.7
In de kolom " " nemen we het enige positieve element als oplossend en gaan we verder met een nieuwe referentieoplossing 
met basis 
(Tabel 4.8).
Tabel 4.8
Deze referentieoplossing is de enige optimale oplossing voor het uitgebreide probleem, aangezien in het maximale probleem de schattingen voor alle vectoren die niet in de basis zijn opgenomen positief zijn. Volgens Stelling 4.1 geldt dit ook voor het oorspronkelijke probleem optimale oplossing, die wordt verkregen uit de optimale oplossing van het uitgebreide probleem door nul kunstmatige variabelen weg te gooien, dat wil zeggen X* = (0,0,6,2).
Antwoord:max Z(X) = -10 bij 
.
Voorbeeld 4.5. Los een lineair programmeerprobleem met gemengde beperkingen op met behulp van de kunstmatige basismethode
Oplossing. We reduceren het lineaire programmeringsprobleem tot canonieke vorm. Om dit te doen, introduceren we extra variabelen in respectievelijk de eerste en de derde beperking. We krijgen
.
We creëren een uitgebreid probleem, waarvoor we kunstmatige variabelen introduceren in respectievelijk de tweede en derde vergelijking. We krijgen
Dit uitgebreide probleem heeft een initiële ondersteuningsoplossing
Met eenheidsbasis 
, 
. We berekenen schattingen van de conditievectoren op basis van de referentieoplossing en schrijven deze op dezelfde manier in de simplextabel als in het vorige voorbeeld. De oplossing is niet optimaal, omdat in het minimale probleem de vectoren positieve schattingen hebben. Ondersteuningsoplossingen verbeteren. Elke referentieoplossing heeft zijn eigen tabel. Alle tabellen kunnen onder elkaar worden geschreven, waardoor ze in één tabel worden gecombineerd (Tabel 4.9).
Tabel 4.9
We bepalen welke van de vectoren of in de basis van de initiële ondersteuningsoplossing zal leiden tot een grotere afname van de objectieve functie. Wij vinden op k= 2, d.w.z. het is beter om de vector in de basis te introduceren. Met de basis verkrijgen we de tweede ondersteuningsoplossing 
. Objectieve functie 
. Deze oplossing is ook niet optimaal, aangezien de vector een positieve waarde heeft 
. We introduceren de vector in de basis, we verkrijgen de derde referentieoplossing met de basis 
. Objectieve functie 
. Deze oplossing is optimaal, maar niet de enige, aangezien de vector die niet in de basis is opgenomen een nulschatting heeft. Daarom is het noodzakelijk om over te stappen op een nieuwe referentieoplossing, die ook optimaal zal zijn. Om dit te doen, moet je de vector in de basis introduceren.
Laten we verder gaan met de vierde (optimale) referentieoplossing
Met basis 
, waarin 
. Optimale oplossingen voor het uitgebreide probleem hebben geen kunstmatige variabelen. Daarom heeft het oorspronkelijke probleem (volgens Stelling 4.1) ook twee optimale oplossingen 
En 
. We schrijven geen extra variabelen in de optimale oplossing van het oorspronkelijke probleem.
Antwoord: 
bij 
, 
, 
, 
.
Het woord simpel
Het woord simplex in Engelse letters (translit) - simpleks
Het woord simplex bestaat uit 8 letters: e en k l m p s s
Betekenis van het woord simplex. Wat is simplex?
Eenvoudig
Simplex (van het Latijnse simplex - eenvoudig) (wiskundig), het eenvoudigste convexe veelvlak gegeven nummer afmetingen n. Wanneer n = 3 is de driedimensionale structuur een willekeurige, inclusief onregelmatige, tetraëder.
TSB. - 1969-1978
Een simplex is een convexe veelhoek in een n-dimensionale ruimte met n+1 hoekpunten die niet in hetzelfde hypervlak liggen. S. worden als een aparte klasse uitgekozen omdat in de n-dimensionale ruimte n punten altijd in hetzelfde hypervlak liggen.
slovar-lopatnikov.ru
SIMPLEX is een convexe veelhoek in een n-dimensionale ruimte met n+1 hoekpunten die niet in hetzelfde hypervlak liggen. S. worden als een aparte klasse uitgekozen omdat in de n-dimensionale ruimte n punten altijd in hetzelfde hypervlak liggen.
Lopatnikov. - 2003
Sub-simplex
Sub simplex Gebruiksaanwijzing en dosering: Oraal, tijdens of na de maaltijd en indien nodig voor het slapengaan. Schud de fles krachtig voor gebruik.
De ZLP oplossen volgens de simplexmethode met een kunstmatige basis
Om de suspensie uit de pipet te laten stromen...
Sab simplex Werkzame stof ›› Simethicone* (Simethicone*) Latijnse naam Sab simplex ATX:›› A02DA Windafdrijvende geneesmiddelen Farmacologische groep…
Woordenboek van medicijnen. — 2005
SAB® SIMPLEX (SAB® SIMPLEX) Orale suspensie van wit tot grijswit van kleur, licht stroperig, met een karakteristieke fruitige (vanille-frambozen) geur. 100 ml simethicon 6,919 g…
SCHOK SIMPLEX
CHOQUET SIMPLEX is een niet-lege compacte convexe verzameling X in een lokaal convexe ruimte E, die de volgende eigenschap heeft: wanneer E als hypervlak in de ruimte is ingebed, is er een uitstekende kegel.
Sheffield Simplex
"Sheffield-Simplex" - licht gepantserd machinegeweervoertuig Krijgsmacht Russische Rijk. Ontwikkeld door het Britse bedrijf Sheffield-Simplex op basis van het chassis van een eigen personenauto...
en.wikipedia.org
Norditropin Simplex
Norditropin Simplex-indicaties: Groeivertraging bij kinderen als gevolg van groeihormoondeficiëntie of chronisch nierfalen (in de prepuberale leeftijd), Shereshevsky-Turner-syndroom...
NORDITROPIN® SIMPLEX® (NORDITROPIN SimpleXx) Oplossing voor subcutane toediening 1,5 ml (1 patroon) somatropine 10 mg 1,5 ml - patronen (1) - contourcelverpakking (1) - kartonnen verpakkingen.
Directory geneesmiddelen"Vidal"
STANDAARD SIMPLEX
STANDAARD SIMPLEX - 1) S. s. - een simplex van dimensie n in de ruimte met hoekpunten op punten e i=(0,..., 1,..., 0), i=0,..., n (de eenheid is ingeschakeld i-de plaats), d.w.z.
Wiskundige encyclopedie. — 1977-1985
Dubbele simplex-methode
De dual simplex-methode kan worden gebruikt om een lineair programmeerprobleem op te lossen, waarvan de vrije termen van het stelsel vergelijkingen elk getal kunnen zijn. Normaal simplex algoritme het plan moet altijd geldig zijn.
en.wikipedia.org
Russische taal
Simplex/.
Woordenboek met morfemische spelling. - 2002
Zoek lezingen
Een voorbeeld van het oplossen van een probleem met behulp van de kunstmatige basismethode.
Zoek het minimum van een functie F=-2×1+3×2 – 6×3 – x4 onder voorwaarden
Oplossing. Laten we dit probleem schrijven in de vorm van het hoofdprobleem: vind het maximum van de functie F1=2×1 – 3×2 + 6×3 + x4 onder voorwaarden
Beschouw in het systeem van vergelijkingen van het laatste probleem de vectoren van de coëfficiënten voor de onbekenden:
A1= A2= A 3= A 4= A 5= A 6=
Onder de vectoren A1,…, A 6 slechts twee enkele ( A 4 en A 5). Daarom voegen we een extra niet-negatieve variabele toe aan de linkerkant van de derde vergelijking van het systeem van beperkingen X 7 en beschouw het uitgebreide probleem van het maximaliseren van de functie
F=2×1 – 3×2 + 6×3 + x4 – Mx7
onder voorwaarden
Het uitgebreide probleem heeft een referentieplan X=(0; 0; 0; 24; 22; 0; 10), gedefinieerd door een systeem van drie eenheidsvectoren: A 4 , A5 , A7 .
tafel 1
| i | 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 |
We stellen tabel (1) van iteratie I samen, die vijf rijen bevat. Om de 4e en 5e regel in te vullen vinden we F 0 en verschilwaarden 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;
Waarden F 0 en zj-cj bestaan uit twee termen, waarvan er één bevat M, en de ander niet.
Voor het gemak van het iteratieve proces wordt het getal bestaande uit M, schrijf in de 5e regel, en de term die niet bevat M, – in de 4e regel.
In de 5e regel van tabel 1 in de kolommen met vectoren Аj (J= ) er zijn twee negatieve getallen (-1 En -2). De aanwezigheid van deze cijfers geeft aan dat dit referentieplan voor het uitgebreide probleem niet optimaal is. Laten we verder gaan met het nieuwe referentieplan van het uitgebreide probleem.
Kunstmatige basismethode.
We introduceren de vector in de basis A3. Om de vector te bepalen die van de basis is uitgesloten, vinden we θ=min(22/4; 10/2)=10/2. Daarom de vector A7 uitgesloten van de basis. Het heeft geen zin om deze vector in een van de volgende basen in te voeren, dus in de toekomst wordt de kolom van deze vector niet ingevuld (tabellen 2 en 3).
We stellen tabel II van iteratie samen (Tabel 2). Het bevat slechts vier rijen, omdat de kunstmatige vector van de basis is uitgesloten.
tafel 2
| i | Basis | Сσ | A0 | -3 | |
| A1 | A2 | A3 | A4 | A5 | A6 |
| A4 | -1 | ||||
| A5 | -1 | ||||
| A3 | 1/2 | -1/2 | -1/2 | ||
| M+1 | -4 |
Zoals uit de tabel blijkt. 2, voor het oorspronkelijke probleem is de referentie het plan X=(0;0;5;34;2).
Laten we het controleren op optimaliteit. Overweeg hiervoor de elementen van de 4e regel. In deze rij in de vectorkolom A6 er is een negatief getal (-4). Dit referentieplan is dus niet optimaal en kan worden verbeterd door de vector te introduceren A6. De vector is uitgesloten van de basis A5. We stellen tabel III van iteratie samen.
tafel 3
In de 4e regel van tabel 3 tussen de cijfers ∆j geen negatieve. Dit betekent dat het gevonden nieuwe referentieplan van het oorspronkelijke probleem is X*=(0; 0; 11/2; 35; 0; 1) is optimaal. Met dit plan wordt de waarde van de lineaire vorm benadrukt Fmax = 68.
De oplossing voor dit probleem kan worden uitgevoerd met behulp van één tabel waarin alle iteraties opeenvolgend worden vastgelegd.
©2015-2018 poisk-ru.ru
Alle rechten behoren toe aan hun auteurs. Deze site claimt geen auteurschap, maar biedt gratis gebruik.
Schending van het auteursrecht en schending van persoonlijke gegevens
Tot nu toe hebben we het probleem uitgebreid overwogen, waarvan de oplossing werd uitgevoerd op basis van het eenvoudigste algoritme van de simplex-methode, aangezien alle beperkingen de vorm kleiner dan of gelijk aan hadden. In dit geval extra taakvariabelen vormen een eenheidsbasis. Maar het kan blijken dat het systeem van beperkingen in canonieke vorm wordt gepresenteerd, maar niet wordt gereduceerd tot een eenheidsbasis.
Bij het oplossen van dergelijke problemen werd het geïntroduceerd kunstmatige basismethode. Dit is vooral handig als het aantal variabelen aanzienlijk groter is dan het aantal vergelijkingen.
Laten we het algoritme voor het oplossen van het probleem bekijken met behulp van de simplex-methode met een kunstmatige basis aan de hand van een voorbeeld.
voorbeeld 1
Zoek het maximum Z=4X1+2X2+X3
3Х1+2Х2+Х3=15
Хj³0, j=1,...,3
Laten we verder gaan met de canonieke vorm:
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
Dit systeem beperkingen hebben geen eenheidsbasis, aangezien de aanvullende variabele X4 een coëfficiënt van min één heeft, en de derde beperking werd weergegeven door een vergelijking en geen basisvariabele heeft. Om een eenheidsbasis te hebben, introduceren we de overeenkomstige beperkingen kunstmatige variabelen y1 en y2 met positieve coëfficiënten (+1).
Opgemerkt moet worden dat kunstmatige variabelen alleen worden geïntroduceerd voor de wiskundige formalisering van het probleem. Daarom moet het berekeningsschema zodanig zijn dat kunstmatige variabelen niet kunnen worden opgenomen in de uiteindelijke oplossing onder de basisvariabelen. Voor dit doel wordt voor kunstmatige variabelen in de objectieve functie een coëfficiënt M geïntroduceerd, die een zeer aangeeft groot aantal. In de praktijk (vooral bij het oplossen van een probleem op een computer) nemen ze in plaats van M een specifiek groot getal, bijvoorbeeld 10000. Bovendien wordt deze coëfficiënt bij het maximaal oplossen van een probleem met een minteken in de objectieve functie ingevoerd. teken, en bij het oplossen tot een minimum, met een plusteken. Nu gaan we het T(M)-probleem oplossen, waarvan de objectieve functie de objectieve functie van de Z-taak en kunstmatige variabelen met een coëfficiënt ±M bevat, d.w.z.
T=Z-M S yi, bij het oplossen van het maximum van de objectieve functie en
T=Z+M S y, bij het oplossen van het minimum van de objectieve functie
In ons geval:
X1+X2+X3-X4+y1=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3+y2=15
Хj³0, j=1,...,5
Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)
Dit probleem wordt opgelost in simplextabellen, maar voor het gemak is de doelfunctie verdeeld in 2 regels:
In de eerste regel noteren we schattingen die de coëfficiënt M niet bevatten;
De tweede regel bevat schattingen voor elke vrije variabele, met daarin de coëfficiënt M.
De berekening van de elementen (scores) van deze twee lijnen wordt uitgevoerd volgens formule (2). Enige verschil:
Bij het berekenen van Z-rijschattingen moet rekening worden gehouden met de coëfficiënten Cj die zijn opgenomen in de Z-functie;
Bij het berekenen van M-lijnschattingen wordt deze coëfficiënt niet in aanmerking genomen en wordt M als gemeenschappelijke factor weggelaten.
Om ervoor te zorgen dat de T-taak en de Z-taak gelijk zijn, is het noodzakelijk dat yi gelijk is aan nul. Daarom wordt, zolang yi niet nul is, de oplossingskolom geselecteerd op basis van de schattingen in de tweede rij met behulp van het simplexmethode-algoritme.
Pas nadat alle y i gelijk zijn geworden aan nul, zal verdere berekening worden uitgevoerd met behulp van de eerste indexlijn, d.w.z. -reguliere Z-taak.
Bovendien, wanneer de kunstmatige variabele is afgeleid van de basis, gooien we deze uit de simplextabel en zal de volgende simplextabel niet de vorige oplossingskolom hebben.
Er bestaat een verband tussen de optimale oplossingen van het M-probleem en het Z-probleem, zoals vastgesteld door het volgende stelling:
1. Als in de optimale oplossing van het M-probleem alle kunstmatige variabelen (y i) gelijk zijn aan nul, dan zal deze oplossing de optimale oplossing voor het Z-probleem zijn.
2. Als in de optimale oplossing van het M-probleem ten minste één van de kunstmatige variabelen verschillend is van nul, dan heeft het Z-probleem geen oplossing vanwege de incompatibiliteit van het systeem van beperkingen.
3. Als het M-probleem onoplosbaar blijkt te zijn (T®+¥ of -¥), dan is het oorspronkelijke probleem ook onoplosbaar vanwege de incompatibiliteit van het systeem van beperkingen of omdat de functie Z onbegrensd is.
Laten we de eerste simplextabel maken. Bij het oplossen met de M-methode kan de oplossingskolom in de M-rij worden geselecteerd, niet op basis van de grootste absolute waarde negatieve schatting (bij het oplossen van het maximum) en niet volgens de grootste positieve schatting (bij het oplossen van het minimum), maar volgens degene die Y snel uit de basis verwijdert. IN in dit voorbeeld de oplossingskolom zal de kolom zijn van de vrije variabele X2 met een score van (-3).
Tabel 3.1.
Eerst simplex tafel
Het vullen van de Z-lijn gebeurt volgens formule (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
Het invullen van de M-lijn:
а¢00 = -М × 8 + (–М) × 15 = -23М
a¢01 = -M × 1 + (–M) × 3 = -4M
а¢02 = -М × 1 + (–М) × 2= -3М
а¢03 = -М × 1+ (–М) × 1 = -2М
а¢04 = -М ×(-1)+ (–М) × 0 = 1М
We nemen M als gemeenschappelijke deler.
De laatste kolom in de resolutieregel bevat 0, dus de kolom van de vrije variabele X4 wordt ongewijzigd overgedragen.
Tabel 3.2.
Tweede simplextafel
In de tweede tabel verkrijgen we een gedegenereerde oplossing, omdat we twee identieke minimaal simplex-relaties verkrijgen. Daarom vinden we de relatie tussen de elementen van de kolom naast de oplossende kolom en de elementen van de oplossende kolom, rekening houdend met het teken.
Tabel 3.3.
Derde simplextabel
Nu lossen we op met behulp van de gebruikelijke simplexmethode.
Tabel 3.4.
Vierde simplextabel
| St.P | Cj | |||
| B.P. | Ci | ai0 | X5 | X4 |
| X3 | -1 | |||
| X1 | ||||
| X2 | -2 | -1 | ||
| Z |
In de evaluatielijn zijn alle elementen niet-negatieve waarden, daarom wordt de optimale oplossing verkregen:
Zmax=15 Xopt(0,7,1,0,0)
Voorbeeld2
Het probleem werd opgelost tot het minimum (Z®min) van de objectieve functie. Bij de laatste iteratie kregen we de volgende tabel:
Tabel 3.5.
Nieuwste simplextabel
| 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 |
In het T-probleem werd een optimale oplossing verkregen, aangezien er geen positieve schattingen meer zijn in de M-rij, d.w.z. de keuze van een oplossingskolom is onmogelijk en U1 vormt de basis. In dit geval heeft het oorspronkelijke probleem geen oplossing vanwege onverenigbaarheid van het systeem van beperkingen.
