De Gauss-Jordan-methode is bedoeld voor het oplossen van stelsels van lineaire algebraïsche vergelijkingen (SLAE's). Het is een wijziging van de Gauss-methode. Als de Gauss-methode in twee fasen wordt uitgevoerd (vooruit en achteruit), kunt u met de Gauss-Jordan-methode het systeem in één fase oplossen. Details en directe toepassing van de Gauss-Jordan-methode worden in de voorbeelden beschreven.

In alle voorbeelden geeft $A$ de systeemmatrix aan, $\widetilde(A)$ de uitgebreide systeemmatrix. U kunt lezen over de matrixvorm van het opnemen van SLAE.

Voorbeeld nr. 1

SLAE $ \left\( \begin(uitgelijnd) & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end(uitgelijnd ) \right.$ volgens de Gauss-Jordan-methode.

Laten we van de laatste matrix die we hebben ontvangen naar het systeem gaan:

$$ \left\( \begin(uitgelijnd) & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2; \\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1. \end(uitgelijnd) \rechts. $$

Als we het resulterende systeem vereenvoudigen, hebben we:

$$ \left\( \begin(uitgelijnd) & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end(uitgelijnd) \right. $$

Volledige oplossing zonder uitleg ziet het er zo uit:

Hoewel deze methode voor het selecteren van oplossende elementen zeer acceptabel is, verdient het de voorkeur om diagonale elementen van de systeemmatrix als oplossende elementen te selecteren. We zullen deze methode hieronder bekijken.

Selectie van oplossende elementen op de hoofddiagonaal van de systeemmatrix.

Omdat deze oplossingsmethode volledig vergelijkbaar is met de vorige (behalve de selectie van inschakelelementen), slaan we gedetailleerde uitleg over. Het principe van het selecteren van activerende elementen is eenvoudig: in de eerste kolom selecteren we het element van de eerste rij, in de tweede kolom nemen we het element van de tweede rij, in de derde kolom nemen we het element van de derde rij, enzovoort. op.

Eerste stap

Selecteer in de eerste kolom het element van de eerste rij, d.w.z. we hebben element 4 als oplossend element. Ik begrijp dat het kiezen van getal 2 de voorkeur verdient, aangezien dit getal nog steeds kleiner is dan 4. Laten we, om ervoor te zorgen dat getal 2 in de eerste kolom naar de eerste plaats gaat, de eerste verwisselen en tweede rijen:

$$ \left(\begin(matrix) (ccc|c) 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end(matrix) \ rechts)\pijl rechts \left(\begin(matrix) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(matrix ) \rechts)$$

Het inschakelelement wordt dus weergegeven door het getal 2. Deel op dezelfde manier als voorheen de eerste rij door 2 en zet vervolgens de elementen van de eerste kolom terug op nul:

$$ \left(\begin(matrix) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(matrix) \ rechts) \begin(array) (l) I:2 \\\phantom(0) \\ \phantom(0) \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & - 2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end(array) \right) \begin(array) (l) \phantom(0 ) \\ II-4\cdot I\\ III+3\cdot I \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & -2& 5/2 & -13/2\ \0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end(array) \right). $$

Tweede stap

De tweede stap vereist het op nul zetten van de elementen van de tweede kolom. We selecteren het element van de tweede regel als het oplossende element, d.w.z. 1. Het oplossende element is al gelijk aan één, dus we zullen geen regels verwisselen. Als we rijen zouden willen verwisselen, zouden we trouwens de eerste rij niet aanraken, omdat deze al in de eerste stap werd gebruikt. Maar de tweede en derde regel kunnen eenvoudig worden verwisseld. Ik herhaal echter dat het in deze situatie niet nodig is om de lijnen te verwisselen, omdat het oplossende element al optimaal is: het is gelijk aan één.

$$ \left(\begin(matrix) (ccc|c) 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/ 2 \end(array) \right) \begin(array) (l) I+2\cdot II \\ \phantom(0)\\ III-5\cdot II \end(array) \rightarrow \left(\begin (array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end(array) \rechts). $$

De tweede stap is voltooid. Laten we verder gaan met de derde stap.

Derde stap

De derde stap vereist het op nul zetten van de elementen van de derde kolom. Als oplossend element selecteren we het element van de derde regel, d.w.z. 37/2. Laten we de elementen van de derde rij delen door 37/2 (zodat het oplossende element gelijk wordt aan 1) en vervolgens de overeenkomstige elementen van de derde kolom opnieuw instellen op nul:

$$ \left(\begin(array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37 /2 \end(array) \right) \begin(array) (l) \phantom(0)\\ \phantom(0)\\ III:\frac(37)(2) \end(array) \pijl naar rechts \ left(\begin(matrix) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end(matrix) \right) \begin(array) (l) I+2\cdot III\\II+3/2\cdot III\\ \phantom(0) \end(array) \rightarrow \left(\begin(array) ( ccc|c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end(array) \right). $$

Ontvangen antwoord: $x_1=-2$, $x_2=1$, $x_3=-1$. De volledige oplossing zonder uitleg ziet er als volgt uit:

Alle andere voorbeelden op deze pagina zullen precies op de tweede manier worden opgelost: we zullen diagonale elementen van de systeemmatrix selecteren als oplossende elementen.

Antwoord: $x_1=-2$, $x_2=1$, $x_3=-1$.

Voorbeeld nr. 2

SLAE $ \left\( \begin(uitgelijnd) & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27; \\ & -3x_1-2x_2-2x_3-10x_4 = 1. \end(uitgelijnd) \right.$ volgens de Gauss-Jordan-methode.

Laten we de uitgebreide matrix van dit systeem schrijven: $\widetilde(A)=\left(\begin(array) (cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end(array) \right)$.

We zullen diagonale elementen van de systeemmatrix selecteren als oplossende elementen: bij de eerste stap nemen we het element van de eerste rij, bij de tweede stap nemen we het element van de tweede rij, enzovoort.

Eerste stap

We moeten de overeenkomstige elementen van de eerste kolom opnieuw instellen. Laten we het element van de eerste regel als een oplossend element nemen, d.w.z. 3. Dienovereenkomstig zal de eerste regel door 3 moeten worden gedeeld, zodat het oplossende element gelijk wordt aan één. En reset vervolgens alle elementen van de eerste kolom, behalve de toegestane:

$$ \left(\begin(array)(cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\ \ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) I:3\\ \phantom(0)\\\phantom(0)\\\ phantom(0)\end(array) \rechterpijl \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) \phantom(0) \\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end(array) \rightarrow\\ \rightarrow\left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & - 5 & ​​-5\end(matrix)\rechts). $$

Tweede stap

We gaan verder met het op nul zetten van de overeenkomstige elementen van de tweede kolom. We hebben afgesproken om het element van de tweede rij als oplossend element te nemen, maar we kunnen dit niet doen, omdat het vereiste element gelijk is aan nul. Conclusie: we zullen de lijnen verwisselen. De eerste regel kan niet worden aangeraakt, omdat deze al in de eerste stap werd gebruikt. De keuze is niet rijk: we wisselen de tweede en derde regel om, of we wisselen de vierde en tweede regel om. Omdat de vierde regel (-1) bevat, laat dan de vierde regel deelnemen aan de “uitwisseling”. Wissel dus de tweede en vierde regel om:

$$ \left(\begin(matrix)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end(array)\right)\pijl rechts \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4 \end(array)\right) $$

Nu is alles normaal: het resolutie-element is gelijk aan (-1). Het komt overigens voor dat het veranderen van de posities van lijnen onmogelijk is, maar we zullen dit in het volgende voorbeeld nr. 3 bespreken. Voorlopig delen we de tweede rij door (-1) en resetten we vervolgens de elementen van de tweede kolom. Houd er rekening mee dat in de tweede kolom het element in de vierde rij al gelijk is aan nul, dus we zullen de vierde rij niet aanraken.

$$ \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \begin(array) (l) \phantom(0)\\II:(-1) \\\phantom(0)\\\phantom(0)\end(array) \rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(matrix)\right) \begin(matrix) (l) I-1/3\cdot II\\ \phantom(0) \\III-2\cdot II\\\phantom(0)\end(array) \rightarrow\\ \rightarrow\left(\begin( array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(matrix)\rechts). $$

Derde stap

Laten we beginnen met het verwerken van de derde kolom. We hebben afgesproken om de diagonale elementen van de systeemmatrix als oplossend element te nemen. Voor de derde stap betekent dit het selecteren van het element op de derde rij. Als we echter simpelweg element 7 als oplossend element nemen, dan zal de gehele derde regel door 7 moeten worden gedeeld. Het lijkt mij dat delen door (-2) eenvoudiger is. Laten we daarom de derde en vierde regel verwisselen, en dan wordt het oplossende element (-2):

$$ \left(\begin(matrix)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \pijl naar rechts \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end(array)\right) $$

Resolutie-element - (-2). Deel de derde rij door (-2) en reset de overeenkomstige elementen van de derde kolom:

$$ \left(\begin(matrix)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & - 3 & -4\\ 0 & 0 & 7 & -9 & -25\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\III:( -2)\\\phantom(0)\end(array)\rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end(array)\right) \begin(array) (l) I-2 /3\cdot III\\ \phantom(0) \\ \phantom(0)\\IV-7\cdot III\end(array)\pijl naar rechts\\ \pijl naar rechts\left(\begin(array)(cccc|c ) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & - 39\eind(matrix)\rechts). $$

Vierde stap

Laten we verder gaan met het op nul zetten van de vierde kolom. Het oplossende element bevindt zich in de vierde regel en is gelijk aan het getal $-\frac(39)(2)$.

$$ \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\ \phantom(0) \\IV:\left(-\frac(39)(2)\right) \end(array)\pijl rechts \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end(array)\right) \begin(array) (l ) I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom(0) \end(array)\pijl naar rechts\\ \pijl naar rechts\left(\begin(array)(cccc |c) 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\einde (matrix)\rechts). $$

De beslissing is voorbij. Het antwoord is: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Volledige oplossing zonder uitleg:

Antwoord: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.

Voorbeeld nr. 3

SLAE $\left\(\begin(uitgelijnd) & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4 +14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5=- 9. \end(aligned)\right.$ volgens Gauss-Jordan methode Als het systeem onzeker is, geef dan de basisoplossing aan.

Soortgelijke voorbeelden worden besproken in het onderwerp “Algemene en basisoplossingen van SLAE’s”. In het tweede deel van het genoemde onderwerp dit voorbeeld opgelost met behulp van de Gaussische methode. We zullen het oplossen met behulp van de Gauss-Jordan-methode. We zullen de oplossing niet stap voor stap afbreken, aangezien dit in eerdere voorbeelden al is gedaan.

$$ \left(\begin(matrix)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end(array)\right) \begin(array) (l) \phantom(0) \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I \\ V+2\cdot I\\VI+4\cdot I \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\ \\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \begin(array) (l) \phantom(0) \\ II:5 \\ \ phantom(0)\\ \phantom(0)\\ \phantom(0) \\ \phantom(0)\end(array) \rightarrow \\ \left(\begin(array)(ccccc|c) 1 & - 2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \ begin (array) (l) I+2\cdot II \\ \phantom(0)\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \ end (array) \pijl rechts \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2 /5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & - 4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right). $$

Ik geloof dat een van de gemaakte transformaties nog steeds uitleg behoeft: $IV:3$. Alle elementen van de vierde regel zijn volledig deelbaar door drie, dus puur om redenen van vereenvoudiging hebben we alle elementen van deze regel in drieën gedeeld. De derde rij in de getransformeerde matrix werd nul. Laten we de nullijn doorstrepen:

$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right) $$

Het is tijd voor ons om verder te gaan naar de derde stap, waarbij de elementen van de derde kolom opnieuw moeten worden ingesteld. Het diagonale element (derde rij) is echter nul. En het veranderen van de posities van de lijnen zal niets opleveren. We hebben de eerste en tweede regel al gebruikt, dus we kunnen ze niet aanraken. Maar het heeft geen zin om de vierde en vijfde regel aan te raken, omdat het probleem dat het resolutie-element gelijk is aan nul niet zal verdwijnen.

In deze situatie kan het probleem op een uiterst eenvoudige manier worden opgelost. Kunnen we de derde colonne niet aan? Oké, laten we verder gaan met nummer vier. Misschien is in de vierde kolom het element van de derde rij niet gelijk aan nul. De vierde kolom kampt echter met hetzelfde probleem als de derde. Het derde rij-element in de vierde kolom is nul. En het opnieuw veranderen van de plaatsen van de lijnen levert niets op. Kunnen wij de vierde kolom ook niet verwerken? Oké, laten we verder gaan met nummer vijf. Maar in de vijfde kolom is het element van de derde rij niet eens nul. Het is gelijk aan één, wat behoorlijk goed is. Het oplossende element in de vijfde kolom is dus gelijk aan 1. Het oplossende element is geselecteerd, dus we zullen verdere transformaties van de Gauss-Jordan-methode uitvoeren:

$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right) \begin(array) (l) I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom(0)\\ IV+III\\ V+ 2 \cdot III \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1 / 5 & ​​2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end(array)\right) \rightarrow \\ \rightarrow\left|\text(Nulregels verwijderen)\right|\rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\ rechts )$$

We hebben de systeemmatrix en de uitgebreide systeemmatrix teruggebracht tot een stapsgewijze vorm. De rangen van beide matrices zijn gelijk aan $r=3$, d.w.z. je moet 3 basisvariabelen kiezen. Het aantal onbekenden is $n=5$, dus we moeten $n-r=2$ vrije variabelen kiezen. Sinds $r< n$, то согласно следствию из теоремы Кронекера-Капелли dit systeem is onzeker (dat wil zeggen heeft een oneindig aantal oplossingen). Om oplossingen voor het systeem te vinden, creëren we “stappen”:

Op de “stappen” staan ​​elementen uit kolommen nr. 1, nr. 2, nr. 5. De basisvariabelen zijn dus $x_1$, $x_2$, $x_5$. De vrije variabelen zijn respectievelijk $x_3$, $x_4$. We zullen de kolommen nr. 3 en nr. 4, die overeenkomen met vrije variabelen, voorbij de lijn verplaatsen, waarbij we uiteraard niet vergeten hun tekens te veranderen.

$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\right)\pijl rechts \left(\begin(array)(ccc|ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end(matrix)\rechts) . $$

Uit de laatste matrix die we krijgen gemeenschappelijk besluit: $\left\(\begin(uitgelijnd) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5)x_4;\\ & x_2=\ frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4 .\end(aligned)\right.$ We vinden de basisoplossing door vrije variabelen te nemen gelijk aan nul, d.w.z. $x_3=0$, $x_4=0$:

$$ \left\(\begin(uitgelijnd) & x_1=-\frac(99)(5);\\ & x_2=\frac(3)(5);\\ & x_3=0;\\ & x_4= 0;\\ & x_5=4.\end(uitgelijnd)\right.$$

Het probleem is opgelost, het enige dat overblijft is het antwoord opschrijven.

Antwoord: Algemene oplossing: $\left\(\begin(uitgelijnd) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5)x_4;\\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4.\end(uitgelijnd)\right.$, basisoplossing: $\left\(\begin(uitgelijnd) & x_1=-\frac(99)(5);\\ & x_2=\frac(3) (5);\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end(uitgelijnd)\rechts.$.

Zoals bekend is de Jordan-Gauss-methode, ook bekend als de methode voor de sequentiële eliminatie van onbekenden, een wijziging van de Gauss-methode voor het oplossen van stelsels van lineaire algebraïsche vergelijkingen (SLAE's).

De methode is gebaseerd op elementaire transformaties (waarbij het systeem wordt omgezet in een gelijkwaardig systeem), waaronder:

• aan beide zijden van de vergelijking van een systeem een ​​andere vergelijking van hetzelfde systeem toevoegen, vermenigvuldigd met een ander getal dan nul;
• het herschikken van vergelijkingen in het systeem;
• verwijdering uit het systeem van vergelijkingen van de vorm 0 = 0.

In tegenstelling tot de Gaussische methode wordt bij elke stap één variabele geëlimineerd uit alle vergelijkingen op één na.

De methodestap is als volgt:

• selecteer een onbekende in de volgende vergelijking met een coëfficiënt die verschilt van nul (oplossend element);
• deel de geselecteerde vergelijking door het oplossende element;
• sluit met behulp van de geselecteerde vergelijking het onbekende bij het oplossende element uit van alle andere vergelijkingen;
• bij de volgende stap wordt een andere onbekende op dezelfde manier uitgesloten van alle vergelijkingen behalve één;
• het proces gaat door totdat alle vergelijkingen zijn gebruikt.

Je kunt het als volgt algoritmen:

Voor SLAU-in matrixvorm A*x=b (matrix A met afmeting m*n, niet noodzakelijk vierkant), wordt de volgende tabel samengesteld:

Het oplossende element a r,s ≠0 wordt in de tabel geselecteerd, dan is r de oplossende rij, s is de oplossende kolom.

De overgang naar de volgende tabel wordt uitgevoerd volgens de regels:

1. de elementen van de oplossende rij worden berekend: a" r,j =a r,j /a r,s - dat wil zeggen, de r-rij van de tabel wordt gedeeld door het oplossende element;

2. alle elementen van de resolutiekolom, behalve een r,s gelijk aan één, worden gelijk aan nul;

3. Elementen buiten de toegestane rij en kolom worden berekend met behulp van de onderstaande formule:

Het is gemakkelijk om verwarring te voorkomen als je ziet dat de teller van deze formule vergelijkbaar is met het berekenen van de determinant van een 2-bij-2-matrix.

4. Bij handmatige berekening wordt de waarde in de laatste controlekolom vergeleken met de som voorgaande elementen lijnen. Als de waarden niet overeenkomen, moet in deze regel naar fouten worden gezocht. Voor geautomatiseerde berekeningen kan de controlekolom worden weggelaten.

De volgende gevallen zijn mogelijk:

1. In het proces van eliminaties linkerkant De vergelijking van het systeem wordt 0, en de rechterhand b≠0, dan heeft het systeem geen oplossing.

2. De identiteit 0 = 0 wordt verkregen - de vergelijking is lineaire combinatie de rest en de reeks nullen kunnen uit het systeem worden verwijderd.

3. Nadat alle vergelijkingen zijn gebruikt om de onbekenden te elimineren, bevat de tabel de gewenste oplossing of wordt de inconsistentie van het systeem van beperkingen weergegeven.

Laten we de methode in Excel programmeren met behulp van één formule, die niet zo moeilijk te veranderen mag zijn. Om bijvoorbeeld SLAE op te lossen

Laten we de bladcellen van A1 tot en met D4 vullen met de coëfficiënten van het systeem, het oplossende element a 1,1 =1 selecteren en de eerste stap van de methode maken in cel A6, waar we de "universele" formule voor zullen invoeren de Jordan-Gauss-transformatie:

ALS(RIJ($A$1)=RIJ(A1);A1/$A$1;
ALS(KOLOM($A$1)=KOLOM(A1),0,(A1*$A$1-
INDIRECT(ADRES(RIJ(A1),KOLOM($A$1)))*
INDIRECT(ADRES(RIJ($A$1),KOLOM(A1)))/$A$1))

In de volgende stap zou het oplossende element bijvoorbeeld een 2,2 =1 kunnen zijn (cel B7). Het enige wat we hoeven te doen is de formule kopiëren van A6 naar A11 (door lege regel laat de stappen van de methode visueel scheiden), ga naar de formulebewerkingsmodus ( Dubbelklik per cel of selecteer deze en druk op de F2-toets) en corrigeer (sleep de muis voorzichtig buiten de rand) alle vastgezette koppelingen van cel A1 naar B7.

Natuurlijk kunt u de vastgezette verwijzing $A$1 overal in de formule vervangen door een constructie van de vorm INDIRECT(CELL) , waardoor dynamisch adres koppelingen. Laten we zeggen INDIRECT(F8), en in cel F8 wordt het adres van de resolutie-elementcel automatisch gegenereerd door opgegeven door gebruiker rij- en kolomnummer. Vervolgens moet u voor deze rij- en kolomnummers aparte cellen opgeven, bijvoorbeeld als volgt:

Helaas levert dit allemaal niets op - in plaats van $A$1 zullen we eenvoudigweg INDIRECT($F$8) in de formule moeten corrigeren en toch hetzelfde aantal links moeten slepen en neerzetten bij het kopiëren van de formule. Daarnaast zullen ook de “handmatig” ingevoerde rij- en kolomnummers gecontroleerd moeten worden op geldigheid (althans zoals in de figuur), dus we gaan geen entiteiten vermenigvuldigen.

U kunt de methode in actie zien op de eerste twee bladen van de bijlage Excel bestand(2 verschillende voorbeelden).

Het volgende is ook gebaseerd op de Jordan-Gauss-transformatie universele methode oplossingen lineaire problemen optimalisatie, hoe simplex methode. Beschrijvingen ervan zijn meestal eng, lang en overladen met stellingen. Laten we proberen een eenvoudige beschrijving te maken en een algoritme te ontwikkelen dat geschikt is voor berekeningen in Excel. In feite is de simplex-methode al ingebouwd standaard toevoeging Een analysepakket, en het is niet nodig om het “handmatig” te programmeren, dus onze code heeft nogal educatieve waarde.

Eerst een minimum aan theorie.

Als de kolomvectoren van de SLAE lineair onafhankelijk zijn, zijn de overeenkomstige variabelen dat ook eenvoudig, en de rest - vrij. Bijvoorbeeld in SLAU

de variabelen x 2 en x 4 zijn eenvoudig, en x 1 en x 3 zijn gratis. De basisvariabelen zijn onafhankelijk van elkaar, en de vrije variabelen kunnen bijvoorbeeld worden gemaakt met nullen en get ( x 2 =2, x 4 =1) – basisoplossing systemen.

Door verschillende oplossende elementen te kiezen, is het mogelijk oplossingen van SLAE's met verschillende bases te verkrijgen. Elke niet-negatieve basisoplossing van een SLAE wordt aangeroepen ondersteunen.

De simplexmethode biedt een overgang van de ene referentieoplossing naar de andere totdat deze is bereikt optimaal oplossing die het minimum oplevert objectieve functie.

Het simplexmethode-algoritme is als volgt:

1. Het LP-probleem wordt getransformeerd naar een canonieke vorm:

Dit kan altijd als volgt: naar het probleem dat in de standaardformulering is geschreven

er worden extra toegevoegd balansvariabelen, waarvan het aantal overeenkomt met het aantal ongelijkheidsbeperkingen m (er wordt geen rekening gehouden met beperkingen op de niet-negativiteit van de waarden van de onbekenden). Hierna veranderen ongelijkheden met het teken “≤” in gelijkheden, bijvoorbeeld een systeem van beperkingen van de vorm

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1, x 2 ≥0

zal de vorm aannemen

2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0

Dat wil zeggen, de ‘economische’ betekenis van balansvariabelen is heel eenvoudig: dit zijn de ‘overblijfselen’ van ongebruikte hulpbronnen van elk type.

Als binnen origineel probleem niet het minimum, maar het maximum werd nagestreefd, wordt de objectieffunctie Z vervangen door Z 1 = -Z. De oplossingen voor de problemen vallen samen, met min Z = - max Z 1 . Doel bijvoorbeeld

Z(x 1,x 2)=2*x 1 +5*x 2 (max.)

herschreven als

Z 1 (x 1,x 2)=-2*x 1 -5*x 2 (min)

Als het oorspronkelijke probleem ongelijkheidsvergelijkingen had met tekens "≥" in plaats van "≤", worden beide zijden van elke dergelijke ongelijkheid vermenigvuldigd met -1 en wordt het teken van de ongelijkheid omgekeerd, bijvoorbeeld:

3*x 1 +x 2 +x 4 ≥15

verandert in

3*x 1 -x 2 -x 4 ≤15

De canonieke vorm van het model wordt verkregen en daarvoor schrijven we simplex tafel:

Basisvariabelen (BP) worden in de linkerkolom geschreven; als ze nog niet zijn geselecteerd, is deze leeg.

2. Met behulp van de Jordan-Gauss-stappen wordt gezocht naar het initiële referentieplan, d.w.z. De SLAE wordt teruggebracht tot zijn basisvorm met niet-negatieve vrije termen bi >0. In dit geval moet de objectieve functie Z alleen worden uitgedrukt in termen van vrije onbekenden (nulcoëfficiënten in de Z-rij bevinden zich alleen onder de variabelen x i die in de basis staan). Bij het selecteren van het oplossende element a r,s noteren we de variabele x s in rij r van de BP-kolom; als daar al een variabele aanwezig was, schrappen we deze (we verwijderen deze uit de basis).

3. We noteren het referentieplan X * onder de kolommen x i: onder de vrije variabelen - nullen, onder de basisvariabelen - de coëfficiënten uit kolom b die overeenkomen met de basisvariabele.

Hieronder schrijven we de vector R uit volgens de regel: onder de basisvariabelen staan ​​​​nullen, onder de vrije R i =Z i .

Als alle R i ≥0 worden gevonden, wordt de optimale oplossing X * en de doelwaarde Z min = -q gevonden, anders hebben we nieuw plan, heb je het, kameraad Zhyukov? (clausule 4).

4. Om de oplossingskolom s te selecteren, selecteert u de maximale absoluut negatieve component van de vector R. De oplossingskolom s wordt geselecteerd. Vervolgens analyseren we de coëfficiënten van de s-de kolom van de matrix van het systeem van beperkingen. Als alle a i,s ≤0, is er geen oplossing en neigt Z min naar min oneindig, ga anders naar stap 5.

5. Om een ​​oplossende string r te selecteren, stellen we niet-negatieve relaties b i /A i,s ≥0, i=1,2,...,m op, en selecteren we de kleinste daarvan. Als het minimum voor meerdere lijnen wordt bereikt, kan elk ervan als oplossend worden beschouwd, en in het nieuwe referentieplan zullen de waarden van sommige basisvariabelen gelijk worden aan 0, dat wil zeggen dat we een gedegenereerd referentieplan krijgen.

6. We voeren de Jordan-Gauss-transformatie uit met het oplossende element a r,s en gaan naar stap 3

Geometrisch komt de simplexmethode overeen met de kortste doortocht van de hoekpunten van een n-dimensionaal convex veelvlak, dat het gebied vormt van haalbare oplossingen voor het probleem:

Hier gaan we vandaan referentieplan C, een van de hoekpunten van een multidimensionale veelhoek, naar het optimale plan E=X *.

Dit alles programmeren in Excel is niet eenvoudig, maar het kan wel. Het bijgevoegde document biedt 3 voorbeelden die de oplossing van problemen implementeren met behulp van de simplexmethode. Het is waar dat je bij het uitvoeren van de stap al 3 formules moet wijzigen; op het blad van het eerste voorbeeld voor de simplexmethode zijn ze geel gemarkeerd: het berekenen van de relaties voor het selecteren van de oplossingsrij in cel I2, het invullen van de BP-kolom in cel A12: de stap van de Jordan-Gauss-transformatie in cel B12. Net als in het voorbeeld van de Jordan-Gauss-transformatie wordt het veranderen van de formules alleen geassocieerd met de noodzaak om ernaar te verwijzen nieuwe lijn, met het adres van de cel met het activeringselement (voor de eerste stap - cel C9).

Op voorwaarde dat er geen “0-rijen” (gelijkheidsbeperkingen) en “vrije” variabelen zijn (d.w.z. variabelen die niet onderworpen zijn aan de eis van niet-negativiteit).

2. In het geval van de aanwezigheid van gelijkheidsbeperkingen en “vrije” variabelen, gaat u als volgt te werk.

Selecteer een oplossingselement in de “0-rij” en voer een aangepaste Jordan-eliminatiestap uit, waarna deze oplossingskolom wordt doorgestreept. Deze reeks acties wordt voortgezet totdat simplex tafel er blijft minimaal één “0-rij” over (in dit geval wordt de tabel verkleind).

Als er ook vrije variabelen zijn, dan is het noodzakelijk om deze variabelen basaal te maken. En nadat de vrije variabele basaal wordt, tijdens het bepalen van het oplossende element bij het zoeken naar de referentie en optimale plannen gegeven lijn niet meegerekend (maar wel omgezet).

Degeneratie bij lineaire programmeerproblemen

Gezien de simplexmethode gingen we ervan uit dat het probleem lineair programmeren is niet-gedegenereerd, d.w.z. elk referentieplan bevat precies
positieve componenten, waar
– aantal beperkingen in het probleem. In een gedegenereerd steunplan blijkt het aantal positieve componenten kleiner te zijn dan het aantal beperkingen: sommige basisvariabelen die overeenkomen met een bepaald steunplan hebben nulwaarden. Gebruikmakend van de geometrische interpretatie voor het eenvoudigste geval, wanneer
(het aantal niet-basisvariabelen is 2), is het gemakkelijk om een ​​gedegenereerd probleem te onderscheiden van een niet-gedegenereerd probleem. In een gedegenereerd probleem kruisen op één hoekpunt van het veelvlak van omstandigheden meer dan twee lijnen, beschreven door vergelijkingen van de vorm
. Dit betekent dat een of meer zijden van de conditiepolygoon tot een punt worden samengetrokken.

A belastbaar wanneer
bij een gedegenereerd probleem kruisen meer dan drie vlakken elkaar op één hoekpunt
.

In de veronderstelling dat het probleem niet-gedegenereerd was, was er maar één waarde
, waarmee de index van de vector van omstandigheden afgeleid van de basis (afgeleid van het aantal basisvariabelen) werd bepaald. Bij een gedegenereerd probleem
kan worden bereikt op meerdere indexen tegelijk (voor meerdere rijen). In dit geval zullen in het gevonden referentieplan verschillende basisvariabelen nul zijn.

Als het lineaire programmeringsprobleem gedegenereerd blijkt te zijn, kan bij een slechte keuze van de vector van voorwaarden afgeleid van de basis een oneindige beweging langs de bases van hetzelfde referentieplan optreden. Het zogenaamde fietsfenomeen. Hoewel looping een uiterst zeldzaam fenomeen is bij praktische lineaire programmeerproblemen, kan de mogelijkheid ervan niet worden uitgesloten.

Een van de methoden om degeneratie te bestrijden is het probleem te transformeren door de vector van de rechterkant van het systeem van beperkingen op hoeveelheden “klein” te veranderen. , op zo'n manier dat het probleem niet-gedegenereerd wordt, en tegelijkertijd zo dat deze verandering niet echt invloed heeft op het optimale plan van het probleem.

Vaker geïmplementeerde algoritmen bevatten enkele eenvoudige regels die de kans verkleinen dat een lus optreedt of wordt overwonnen.

Laat de variabele moet fundamenteel worden gemaakt. Overweeg een reeks indexen , bestaande uit deze , waarvoor het wordt bereikt
. Veel indexen , waarvoor aan deze voorwaarde is voldaan, duiden we dit aan met . Als uit één element bestaat, wordt de vector van voorwaarden uitgesloten van de basis (variabel wordt non-basic gemaakt).

Als uit meer dan één element bestaat, wordt er een set gevormd , Welke bestaat uit
, waarop het wordt bereikt
. Als bestaat uit één index , dan wordt de variabele afgeleid van de basis . Anders wordt er een set gevormd enz.

In de praktijk moet de regel worden toegepast als er al fietsen zijn gedetecteerd.

Over het algemeen heeft de lineaire vergelijking de vorm:

De vergelijking heeft een oplossing: als ten minste één van de coëfficiënten van de onbekenden verschillend is van nul. In dit geval wordt elke -dimensionale vector een oplossing voor de vergelijking genoemd als de vergelijking, bij het vervangen van de coördinaten, een identiteit wordt.

Algemene kenmerken van het opgeloste stelsel vergelijkingen

Voorbeeld 20.1

Beschrijf het stelsel van vergelijkingen.

Oplossing:

1. Is er sprake van een tegenstrijdige vergelijking?(Als de coëfficiënten, in dit geval, de vergelijking de vorm heeft: en wordt genoemd controverseel.)

• Als een systeem iets tegenstrijdigs bevat, dan is zo’n systeem inconsistent en heeft het geen oplossing.

2. Zoek alle toegestane variabelen. (Het onbekende wordt geroepentoegestaan voor een stelsel vergelijkingen, als het is opgenomen in een van de vergelijkingen van het systeem met een coëfficiënt van +1, maar niet is opgenomen in de overige vergelijkingen (dat wil zeggen, het is opgenomen met een coëfficiënt gelijk aan nul).

3. Is het stelsel van vergelijkingen opgelost? (Het systeem van vergelijkingen wordt opgelost genoemd, als elke vergelijking van het systeem een ​​opgeloste onbekende bevat, waaronder geen samenvallende)

De opgeloste onbekenden, één uit elke vergelijking van het systeem, vormen zich volledige set opgeloste onbekenden systemen. (in ons voorbeeld is dit)

Toegestane onbekenden in de complete set worden ook wel genoemd eenvoudig(), en niet inbegrepen in de set - vrij ().

In het algemene geval heeft het opgeloste stelsel vergelijkingen de vorm:

Op in dit stadium het belangrijkste is om te begrijpen wat het is opgelost onbekend(inbegrepen in de basis en gratis).

Algemeen Bijzonder Basisoplossingen

Algemene oplossing een opgelost systeem van vergelijkingen is een reeks uitdrukkingen van opgeloste onbekenden door middel van vrije termen en vrije onbekenden:

Privé beslissing wordt een oplossing genoemd die wordt verkregen uit een algemene oplossing voor specifieke waarden van vrije variabelen en onbekenden.

Basis oplossing wordt een bijzondere oplossing genoemd, verkregen uit de algemene oplossing nul waarden vrije variabelen.

• De basisoplossing (vector) wordt genoemd ontaarden, als het aantal niet-nulcoördinaten kleiner is dan het aantal toegestane onbekenden.
• De basisoplossing wordt genoemd niet-gedegenereerd, als het aantal niet-nulcoördinaten gelijk is aan het aantal toegestane onbekenden van het systeem dat in de volledige set is opgenomen.

Stelling (1)

Het opgeloste stelsel van vergelijkingen is altijd consistent(omdat het minstens één oplossing heeft); Bovendien, als het systeem geen vrije onbekenden heeft,(dat wil zeggen dat in een systeem van vergelijkingen alle toegestane vergelijkingen in de basis zijn opgenomen) dan is het gedefinieerd(heeft een unieke oplossing); als er minstens één vrije variabele is, is het systeem niet gedefinieerd(heeft een oneindig aantal oplossingen).

Voorbeeld 1. Vind de algemene, basis- en eventuele specifieke oplossing van het stelsel vergelijkingen:

Oplossing:

1. Controleren we of het systeem geautoriseerd is?

• Het systeem is opgelost (aangezien elk van de vergelijkingen een opgeloste onbekende bevat)

2. We nemen toegestane onbekenden op in de set: één uit elke vergelijking.

3. We schrijven de algemene oplossing op, afhankelijk van de toegestane onbekenden die we in de set hebben opgenomen.

4. Het vinden van een bepaalde oplossing. Om dit te doen, stellen we vrije variabelen die we niet in de set hebben opgenomen, gelijk aan willekeurige getallen.

Antwoord: particuliere oplossing(een van de opties)

5. Het vinden van de basisoplossing. Om dit te doen, stellen we de vrije variabelen die we niet in de set hebben opgenomen, gelijk aan nul.

Elementaire transformaties van lineaire vergelijkingen

Systemen lineaire vergelijkingen worden teruggebracht tot gelijkwaardig toegestaan ​​gebruik van systemen elementaire transformaties.

Stelling (2)

Indien aanwezig vermenigvuldig de vergelijking van het systeem met een getal dat niet nul is en laat de rest van de vergelijkingen ongewijzigd, dan . (dat wil zeggen, als je de linker en vermenigvuldigt rechter zijde vergelijkingen voor hetzelfde getal, dan krijg je een vergelijking die gelijkwaardig is aan de gegeven vergelijking)

Stelling (3)

Als voeg een andere toe aan elke vergelijking van het systeem en laat alle andere vergelijkingen ongewijzigd we krijgen een systeem dat gelijkwaardig is aan dit. (dat wil zeggen, als u twee vergelijkingen optelt (door hun linker- en rechterkant op te tellen), krijgt u een vergelijking die equivalent is aan de gegevens)

Uitvloeisel van stellingen (2 en 3)

Als een andere vergelijking toevoegen aan een vergelijking vermenigvuldigd met een bepaald getal, en laat alle andere vergelijkingen ongewijzigd, dan krijgen we een systeem dat gelijkwaardig is aan dit.

Formules voor het herberekenen van systeemcoëfficiënten

Als we een stelsel vergelijkingen hebben en dit willen omzetten in een opgelost stelsel vergelijkingen, zal de Jordan-Gauss-methode ons hierbij helpen.

Jordanië transformatie Met een oplossend element kun je voor een stelsel vergelijkingen de opgeloste onbekende in de vergelijking met getal verkrijgen. (voorbeeld 2).

De Jordan-transformatie bestaat uit elementaire transformaties van twee typen:

Laten we zeggen dat we van de onbekende in de onderste vergelijking een opgeloste onbekende willen maken. Om dit te doen, moeten we delen door , zodat de som .

Voorbeeld 2 Laten we de systeemcoëfficiënten herberekenen

Wanneer een vergelijking door een getal wordt gedeeld, worden de coëfficiënten ervan opnieuw berekend met behulp van de formules:

Om uit te sluiten van de vergelijking met getal , moet je de vergelijking met getal vermenigvuldigen met en aan deze vergelijking toevoegen.

Stelling (4) Over het verminderen van het aantal vergelijkingen van het systeem.

Als een stelsel vergelijkingen een triviale vergelijking bevat, kan deze van het systeem worden uitgesloten en wordt een systeem verkregen dat gelijkwaardig is aan het origineel.

Stelling (5) Over de onverenigbaarheid van het stelsel vergelijkingen.

Als een stelsel vergelijkingen een inconsistente vergelijking bevat, dan is het inconsistent.

Algoritme van de Jordan-Gauss-methode

Het algoritme voor het oplossen van stelsels vergelijkingen met behulp van de Jordan-Gauss-methode bestaat uit een aantal vergelijkbare stappen, waarbij acties in de volgende volgorde worden uitgevoerd:

1. Er wordt gecontroleerd of het systeem inconsistent is. Als een systeem een ​​inconsistente vergelijking bevat, is het inconsistent.
2. De mogelijkheid om het aantal vergelijkingen te verminderen wordt gecontroleerd. Als het systeem een ​​triviale vergelijking bevat, wordt deze doorgestreept.
3. Als het systeem van vergelijkingen is opgelost, noteer dan de algemene oplossing van het systeem en, indien nodig, specifieke oplossingen.
4. Als het systeem niet is opgelost, wordt in een vergelijking die geen opgeloste onbekende bevat, een oplossend element geselecteerd en wordt met dit element een Jordan-transformatie uitgevoerd.
5. Ga dan terug naar punt 1

Voorbeeld 3 Los een stelsel vergelijkingen op met behulp van de Jordan-Gauss-methode.

Vinden: twee algemene en twee overeenkomstige basisoplossingen

Oplossing:

De berekeningen worden weergegeven in de onderstaande tabel:

Aan de rechterkant van de tabel staan ​​acties op vergelijkingen. De pijlen geven aan bij welke vergelijking de vergelijking met het oplossende element wordt opgeteld, vermenigvuldigd met een geschikte factor.

De eerste drie rijen van de tabel bevatten de coëfficiënten voor de onbekenden en de rechterkant origineel systeem. De resultaten van de eerste Jordan-transformatie met een oplossend element gelijk aan één worden gegeven in regels 4, 5, 6. De resultaten van de tweede Jordan-transformatie met een oplossend element gelijk aan (-1) worden gegeven in regels 7, 8, 9 Aangezien de derde vergelijking triviaal is, kan deze worden weggelaten.

Laat ons nadenken simplex methode voor het oplossen van lineaire programmeerproblemen (LP). Het is gebaseerd op de overgang van het ene referentieplan naar het andere, waarbij de waarde van de doelfunctie toeneemt.

Het simplexmethode-algoritme is als volgt:

1. Wij vertalen het oorspronkelijke probleem naar canonieke visie door het introduceren van extra variabelen. Voor ongelijkheden van de vorm ≤ worden aanvullende variabelen geïntroduceerd met een teken (+), maar als ze de vorm ≥ hebben, dan met een teken (-). Extra variabelen worden in de doelfunctie geïntroduceerd met overeenkomstige tekens met een coëfficiënt gelijk aan 0 , omdat de doelfunctie mag de functie ervan niet veranderen economische zin.
2. Vectoren zijn uitgeschreven P ik uit de coëfficiënten van de variabelen en de kolom met vrije termen. Deze actie bepaalt het aantal eenheidsvectoren. De regel is dat er net zoveel eenheidsvectoren moeten zijn als er ongelijkheden zijn in het systeem van beperkingen.
3. Hierna worden de brongegevens in een simplextabel ingevoerd. Eenheidsvectoren worden in de basis geïntroduceerd en door ze uit de basis uit te sluiten, wordt de optimale oplossing gevonden. De coëfficiënten van de doelfunctie worden met het tegenovergestelde teken geschreven.
4. Een optimaliteitsteken voor een LP-probleem is dat de oplossing optimaal is als deze aanwezig is F– in de rij zijn alle coëfficiënten positief. Regel voor het vinden van de activeringskolom - bekeken F– een string en uit de negatieve elementen wordt de kleinste geselecteerd. Vector P ik het bevatten ervan wordt tolerant. De regel voor het kiezen van een oplossend element - de verhoudingen van de positieve elementen van de oplossende kolom tot de elementen van de vector worden samengesteld P0 en het getal dat de kleinste verhouding oplevert, wordt het oplossende element ten opzichte waarvan de simplextabel opnieuw zal worden berekend. De regel die dit element bevat, wordt de enable-regel genoemd. Als er geen positieve elementen in de resolutiekolom staan, heeft het probleem geen oplossing. Nadat ze het oplossende element hebben bepaald, gaan ze verder met de herberekening van een nieuwe simplextabel.
5. Regels voor het invullen van een nieuwe simplextabel. Eenheid wordt in plaats van het oplossende element geplaatst en er wordt aangenomen dat andere elementen gelijk zijn 0 . De oplossende vector wordt toegevoegd aan de basis, waarvan de overeenkomstige nulvector wordt uitgesloten, en de resterende basisvectoren worden zonder wijzigingen geschreven. De elementen van de resolutielijn worden gedeeld door het resolutie-element, en de overige elementen worden opnieuw berekend volgens de rechthoekregel.
6. Dit wordt gedaan tot F– alle elementen van de string worden niet positief.

Laten we overwegen het probleem op te lossen met behulp van het hierboven besproken algoritme.
Gegeven:

We brengen het probleem naar een canonieke vorm:

We stellen de vectoren samen:

Vul de simplextabel in:

:
Laten we het eerste element van de vector herberekenen P0, waarvoor we een rechthoek van getallen maken: en we krijgen: .

We voeren soortgelijke berekeningen uit voor alle andere elementen van de simplextabel:

In het ontvangen plan F– de lijn bevat één negatief element – ​​​​(-5/3), vector P1. Het bevat in zijn kolom één enkel positief element, dat het faciliterende element zal zijn. Laten we de tabel met betrekking tot dit element opnieuw berekenen:

Geen negatieve elementen erin F– lijn betekent gevonden optimaal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov SA Lineaire programmering, M: Nauka, 1998,
• Ventzel E.S. Operations Research, M: Sovjet-radio, 2001,
• Kuznetsov Yu.N., Kuzubov VI, Voloshenko AB Wiskundig programmeren, M: Higher School, 1986.

Aangepaste lineaire programmeeroplossing

Op onze website kunt u alle opdrachten in dit vakgebied bestellen. U kunt bestanden bijvoegen en deadlines opgeven op