Układy nierówności liniowych cz. II PDF

Preview

Summary

Materiały do zajęć z matematyki. WSB Poznań....

Description

UKŁADY NIERÓWNOŚCI LINIOWYCH ANALIZA MATEMATYCZNA- Joanna Pomianowska

Układy nierówności liniowych cz. II Definicja Układem 𝑚 nierówności liniowych o 𝑛 niewiadomych nazywamy jest układ

gdzie

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2 , ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑛

𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 𝑨= … … … … jest macierzą współczynników, 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛

𝑥1 𝑥2 𝒙 = … jest wektorem niewiadomych, 𝑥𝑛

𝒃=

𝑏1 𝑏2 jest wektorem wyrazów wolnych. … 𝑏𝑚

Powyższy układ nierówności liniowych można zapisad macierzowo 𝑨 ∙ 𝒙 ≤ 𝒃 𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1 𝑥2 𝑎21 𝑎22 … 𝑎2𝑛 𝑏2 … ≤ …. … … … … ∙ 𝑥𝑛 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑏𝑚

W tym układzie nierówności przyjmujemy, że wszystkie nierówności są ≤ (mniejsze równe). Gdyby któraś z nierówności była przeciwna, to przemnażamy ją przez −1. Gdyby nierównośd była ostra ( 0. Takie uporządkowanie znaków nierówności ułatwia wprowadzenie przejrzystej i niezbyt skomplikowanej metody rozwiązywania. Aby rozwiązad układ nierówności liniowych

1. należy zamienid go na układ równao liniowych wprowadzając 𝑚 nowych zmiennych 𝑧1 , 𝑧2 , … , 𝑧𝑚 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝒛𝟏 = 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 + 𝒛𝟐 = 𝑏2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + 𝒛𝒎 = 𝑏𝑛

∗

Zauważmy, że 𝒛𝟏 , 𝒛𝟐 , … , 𝒛𝒎 ≥ 0 , bo inaczej poszczególne nierówności nie mogłyby zamienid się na równania. Wszystkie 𝑧1 , 𝑧2 , … , 𝑧𝑚 nie mogą byd jednocześnie równe zero, ponieważ oznaczałoby to, że nie mieliśmy układu nierówności, a układ równao liniowych.

2. Układ równao ∗, rozwiązujemy jak układ równao liniowych o 𝑛 + 𝑚 niewiadomych. W tym celu wykorzystujemy metodę przekształceo elementarnych

1

UKŁADY NIERÓWNOŚCI LINIOWYCH ANALIZA MATEMATYCZNA- Joanna Pomianowska przekszta łcenia elementarne na wierszach oraz zamiana miejscami dw óch kolumn w obrębie macierzy 𝐀 lub macierzy 𝐈

𝑨 ⋮ 𝑰⋮ 𝒃

𝑰⋯ ⋯⋮ 𝑩⋯ 𝟏 𝟎

⋮ 𝑩𝟐

Macierz jednostkowa pojawia się dlatego, że są to współczynniki wprowadzonych zmiennych 𝑧1 , 𝑧2 , … , 𝑧𝑚 . Jeżeli po przekształceniu macierzy uzupełnionej 𝑨 ⋮ postad kanoniczną:  𝑰⋮



𝑰 ⋮ 𝒃 uzyskamy poniższą

𝑩, to układ nierówności liniowych ma rozwiązanie

𝑰 ⋮ 𝑩𝟏 ⋯ ⋯ ⋯ , to układ nierówności liniowych 𝟎 ⋮ 𝑩𝟐 a) ma rozwiązanie, gdy układ równao 𝑩2 ma przynajmniej jedno nieujemne rozwiązanie bazowe b) jest sprzeczny w przeciwnym przypadku.

Uwaga Rozwiązaniem bazowym nieoznaczonego układu równao nazywamy takie rozwiązanie, w którym za parametry przyjmujemy zera. Przykład Rozwiąż układy nierówności: a)

𝑥1 − 𝑥2 − 3𝑥3 ≤ 2 −𝑥1 + 2𝑥2 + 3𝑥3 ≤ −2 −2𝑥1 + 2 𝑥2 + 6𝑥3 ≤ −5

rozwiązanie Ten układ nierówności zapisujemy w postaci układu równao wprowadzając nowe zmienne 𝑧1 , 𝑧2 , 𝑧3 ≥ 0 𝑥1 − 𝑥2 − 3𝑥3 + 𝑧1 = 2 −𝑥1 + 2𝑥2 + 3𝑥3 + 𝑧2 = −2 −2𝑥1 + 2 𝑥2 + 6𝑥3 + 𝑧3 = −5

Następnie uzyskany w ten sposób układ równao zapisujemy w postaci macierzy uzupełnionej. Po czym ustawiamy pierwszą kolumnę zaczynając od jedynki, która już jest na właściwej pozycji, a następnie ustawiamy brakujące zera. 1 −1 −3 ⋮ 1 0 0 ⋮ 2𝑤 + 𝑤 −1 2 3 ⋮ 0 1 0 ⋮ −2 2𝑤 +1𝑤 ∙ 2~ 3 1 −2 2 6 ⋮ 0 0 1 ⋮ −5 Potem ustawiamy drugą kolumnę zaczynając od jedynki, która też już jest, a potem zera. 1 −1 −3 ⋮ 1 0 0 ⋮ 2 0 1 0 ⋮ 1 1 0 ⋮ 0𝑤1 + 𝑤2 ~ 0 0 0 ⋮ 2 0 1 ⋮ −1

Trzeciej kolumny nie da się już ustawid, bo w wierszu trzecim wyszły do kropek same zera. 1 0 −3 ⋮ 2 1 0 ⋮ 2 0 1 0 ⋮ 1 1 0 ⋮ 0 0 0 0 ⋮ 2 0 1 ⋮ −1

Zapiszmy ten układ w postaci kanonicznej

2

UKŁADY NIERÓWNOŚCI LINIOWYCH 𝒙𝟏

𝒙𝟐

ANALIZA MATEMATYCZNA- Joanna Pomianowska

𝒛𝟏

𝒙𝟑

𝟏𝟎 𝟎𝟏 ⋮⋮ ⋯ ⋯ ⋯

𝒛𝟐

𝒛𝟑

−𝟑𝟎 ⋮ ⋮ 𝟐 𝟏𝟏 𝟏𝟎 𝟎 ⋮ ⋮ 𝟐 𝟎 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯

Układem równao 𝑩𝟐 jest tylko jedno równanie 𝟎 𝟎 ⋮ 𝟎 ⋮

𝟐 𝟎 𝟏 ⋮ −𝟏 𝟐𝒛𝟏 + 𝒛𝟑 = −1

=

𝑰2

⋯ ⋯ ⋯ 𝟎⋮1×2 𝑩𝟏⋮ 𝑩𝟐

Ponieważ układ 𝑩𝟐 ma jedno równanie, a dwie niewiadome, to jedną niewiadomą, albo 𝒛𝟑 , albo 𝒛𝟏 przyjmujemy za parametr. Oczywiście parametrem jest także 𝑧2 zarówno w jednym jak i drugim rozwiązaniu. Czyli rozwiązanie wygląda tak 𝑧1 = −

− 𝑏 1

1

1. 𝑧2 = 𝑎, 𝑎 ∈ 𝑅+ ∪ 0 𝑧3 = 𝑏, 𝑏 ∈ 𝑅 2

2

lub tak

w zależności od tego, która ze zmiennych będzie parametrem. Zatem równanie o macierzy 𝑩𝟐 ma dwa rozwiązania bazowe: 𝑧1 = − 𝟐 1. 𝑧2 = 0 𝑧3 = 0 𝟏

oraz

𝑧1 = 𝑎, 𝑎 ∈ 𝑅 2. 𝑧2 = 𝑏, 𝑏 ∈ 𝑅+ ∪ 0 𝑧3 = −1 − 2𝑎

𝑧1 = 0 2. 𝑧2 = 0 𝑧3 = −𝟏

Jak widad równanie o macierzy 𝑩𝟐 posiada same rozwiązania bazowe ujemne. Wobec tego układ nierówności liniowych jest sprzeczny, ponieważ 𝑧1 i 𝑧3 z założenia miały byd dodatnie.

b)

2𝑥1 + 𝑥2 − 4𝑥3 ≤ 3

𝑥1 + 𝑥2 − 2𝑥3 ≥ −1 1

2

rozwiązanie Najpierw przemnażamy drugie równanie przez −1, a następnie zamieniamy ten układ nierówności liniowych na układ równao liniowych wprowadzając nowe zmienne 𝑧1 , 𝑧2 ≥ 0. 2𝑥1 + 𝑥2 − 4𝑥3 + 𝑧1 = 3 1 −𝑥1 − 𝑥2 + 2𝑥3 + 𝑧2 = 1 2

Macierz uzupełniona dla tego układu równao liniowych ma postad 2

−1

1 −4 ⋮ 1 0 ⋮ 3 1 𝑤 ∙ −1~ 2 ⋮ 0 1 ⋮ 1 2 − 2

Po zamianie miejscami wierszy i po przemnożeniu pierwszego wiersza przez liczbę −1 otrzymujemy 1 −2 ⋮ 0 −1 2 2 1 −4 ⋮ 1 0

1

Postacią kanoniczną tego układu jest 𝒙𝟏

Tutaj układ równao

⋮ −1 𝑤 + 𝑤 ∙ −2~ 1 1 2 ⋮ 3

1

2 0 0

−2 0

⋮ 0

⋮ 1

𝒙𝟐 𝒙𝟑 𝒛𝟏 𝒛𝟐 𝟏 𝑰𝟏 ⋮ 𝑩𝟏 −𝟐 ⋮ 𝟎 −𝟏 ⋮ −𝟏 𝟏 ⋮ 𝟐 ⋯ ⋯ ⋯ = ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 𝟎𝟏×𝟏 ⋮ 𝑩𝟐 𝟎 ⋮ 𝟎 𝟎 ⋮ 𝟏 𝟐 ⋮ 𝟓

𝑩𝟐 jest też tylko jednym równaniem

Przyjmijmy w tym równaniu za parametr 𝒛𝟐 . Wówczas postacią parametryczną równania jest

a rozwiązanie bazowe jest dodatnie.

𝒛𝟏 + 𝟐𝒛𝟐 = 𝟓.

𝑧1 = 5 − 2𝑎 𝑧2 = 𝑎, 𝑎 ∈ 𝑅

3

−1 ⋮ −1 2

⋮

5

UKŁADY NIERÓWNOŚCI LINIOWYCH ANALIZA MATEMATYCZNA- Joanna Pomianowska

𝑧1 = 5 𝑧2 = 0 Układ nierówności jest nieoznaczony, bo przynajmniej jedno rozwiązanie bazowe jest nieujemne. 1 𝑥1 = −1 − 𝑎 + 2𝑏 + 𝑧2 2 𝑥2 = 𝑎, 𝑎 ∈ 𝑅 𝑥3 = 𝑏, 𝑏 ∈ 𝑅 𝑧1 + 2𝑧2 = 5 𝑧1 , 𝑧2 ≥ 0

−𝑥1 + 2 𝑥2 + 2𝑥3 ≤ −1 c) 2𝑥1 − 4𝑥2 − 3𝑥3 ≤ 2 𝑥1 − 𝑥2 + 𝑥3 ≤ 2

rozwiązanie Zamieniamy układ nierówności na układ równao −𝑥1 + 2 𝑥2 + 2𝑥3 + 𝑧1 = −1 2𝑥1 − 4𝑥2 − 3𝑥3 + 𝑧2 = 2 𝑥1 − 𝑥2 + 𝑥3 + 𝑧3 = 2

przy czym zakładamy, że 𝑧1 , 𝑧2 , 𝑧3 ≥ 0. Macierz uzupełniona dla tego układu równao ma postad −1 2 1

2 2 ⋮ 1 0 0 ⋮ −1 −4 −3 ⋮ 0 1 0 ⋮ 2 𝑤1 ∙ −1~ −1 1 ⋮ 0 0 1 ⋮ 2

1 −2 −2 ⋮ −1 2 −4 −3 ⋮ 1 −1 1 ⋮

1 −2 −2 ⋮ −1 0 0 ⋮ 1 zamieniamy 0 0 1 ⋮ 2 1 0 ⋮ 0 miejscami 𝑤 i 𝑤 3 2 0 1 3 ⋮ 1 0 1 ⋮ 1 1 0 0 1 0 0

0 0 ⋮ 1 𝑤 + 𝑤1 ∙ −2 ~ 0 1 0 ⋮ 2 2 𝑤 + 𝑤1 ∙ −1 0 0 1 ⋮ 2 3

1 −2 −2 ⋮ −1 0 0 ⋮ 1 0 1 3 ⋮ 1 0 1 ⋮ 1 𝑤1 + 𝑤2 ∙ 2~ 0 0 1 ⋮ 2 1 0 ⋮ 0

4 ⋮ 1 0 2 ⋮ 3 𝑤 + 𝑤 ∙ −4 3 ~ 3 ⋮ 1 0 1 ⋮ 1 1 𝑤2 + 𝑤3 ∙ −3 1 ⋮ 2 1 0 ⋮ 0

1 0 0 ⋮ −7 −4 2 ⋮ 3 0 1 0 ⋮ −5 −3 1 ⋮ 1 0 0 1 ⋮ 2 1 0 ⋮ 0

Z postaci kanonicznej tego układu odczytujemy, że układ nierówności był nieoznaczony.

Zatem rozwiązanie wygląda tak

𝑥1 𝑥2 𝑥3 𝒛𝟏 𝒛𝟐 𝒛𝟑 𝟏 𝟎 𝟎 ⋮ −𝟕 −𝟒 𝟐 ⋮ 𝟑 = 𝑰 ⋮ 𝑩. 𝟎 𝟏 𝟎 ⋮ −𝟓 −𝟑 𝟏 ⋮ 𝟏 𝟎𝟎𝟏 ⋮ 𝟐 𝟏 𝟎 ⋮ 𝟎 𝑥1 = 3 + 7𝒛𝟏 + 4𝒛𝟐 − 2𝒛𝟑 𝑥2 = 1 + 5𝒛𝟏 + 3𝒛𝟐 − 𝒛𝟑 𝑥3 = −2𝒛𝟏 − 𝒛𝟐 𝑧1 , 𝑧2 , 𝑧3 ≥ 0

Gdybyśmy chcieli wskazad którekolwiek z nieskooczenie wielu rozwiązao, należy za parametry wstawid jakiekolwiek nieujemne liczby rzeczywiste, np. 𝑧1 = 𝑧2 = 𝑧3 = 0, wówczas 𝑥1 = 3 + 7 ∙ 0 + 4 ∙ 0 − 2 ∙ 0 = 3 𝑥2 = 1 + 5 ∙ 0 + 3 ∙ 0 − 0 = 1 𝑥3 = −2 ∙ 0 − 0 = 0

jest rozwiązaniem nierówności c).

𝑥1 = 3 𝑥2 = 1 𝑥3 = 0

4...