BOiE 01 układy równań liniowych

Rozdział 1
Układy równań liniowych
1.1 Pojęcia wstępne
Załóżmy, że dane są liczby rzeczywiste aij, gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n, oraz bi,
gdzie i = 1, 2, . . . , m. Rozważmy układ równań liniowych z niewiadomymi x1, x2, . . ., xn:
ńł
�ł
�ł
�ł
a11x1 + a12x2 + . . . + a1nxn = b1,
�ł
�ł
�ł
�ł
�ł
�ł
�ł
a21x1 + a22x2 + . . . + a2nxn = b2,
(1.1)
�ł
�ł
�ł
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
�ł
�ł
�ł
�ł
�ł
�ł
ół
am1x1 + am2x2 + . . . + amnxn = bm.
Macierz
�ł łł
a11 a12 . . . a1n b1
�ł śł
�ł śł
�ł
a21 a22 . . . a2n b2 śł
�ł śł
�ł śł (1.2)
. . . . .
�ł śł
. . . . .
. . . . .
�ł śł
�ł �ł
am1 am2 . . . amn bm
będziemy nazywać macierzą układu (1.1), zaś macierze
�ł łł �ł łł
a11 a12 . . . a1n b1
�ł śł �ł śł
�ł śł �ł śł
�ł �ł śł
a21 a22 . . . a2n śł b2
�ł śł �ł śł
A = �ł śł oraz B = �ł śł (1.3)
. . . . .
�ł śł �ł śł
. . . . .
. . . . .
�ł śł �ł śł
�ł �ł �ł �ł
am1 am2 . . . amn bm
będziemy odpowiednio nazywać macierzą współczynników i macierzą wyrazów wol-
nych tego układu równań. Macierz A określa się również jako macierz główną, zaś ma-
cierz B jako wektor prawych stron układu równań (1.1).
1
Przy oznaczeniach wprowadzonych równościami (1.3) macierz (1.2) zapisuje się często
w postaci blokowej:
[A B],
zaś układ równań liniowych (1.1) w postaci macierzowej:
AX = B, (1.4)
gdzie
�ł łł
x1
�ł śł
�ł śł
�ł śł
x2
�ł śł
X = �ł śł
.
�ł śł
.
.
�ł śł
�ł �ł
xm
jest wektorem niewiadomych. Jest oczywiste, że współrzędne każdego wektora X speł-
niającego równanie macierzowe (1.4) tworzą rozwiązanie układu równań liniowych (1.1) i
odwrotnie.
1.2 Bazowa postać układu równań liniowych
W celu uproszczenia zapisu w dalszym ciągu rozważań będziemy zakładać, że spełnione
jest następujące założenie:
Założenie: Jeżeli nie zostanie wyraznie powiedziane inaczej, to będziemy
przyjmować, że przy powyższych oznaczeniach spełnione są następujące warun-
ki:
m n oraz rząd A = m,
a więc wiersze macierzy A, traktowane jako wektory, tworzą układ liniowo nieza-
leżny i wśród kolumn macierzy A (również traktowanych jako wektory) można
znalezć m kolumn liniowo niezależnych.
Zgodnie z przyjętym założeniem przyjmijmy, że kolumny macierzy A o numerach j1, j2,
. . ., jm, tworzących ciąg rosnący, są liniowo niezależne i oznaczmy:
�ł łł
a1j a1j . . . a1j
1 2 m
�ł śł
�ł śł
�ł
a2j a2j . . . a2j śł
1 2 m
�ł śł
Ab = �ł śł , (1.5)
. . . .
�ł śł
. . . .
. . . .
�ł śł
�ł �ł
amj amj . . . amj
1 2 m
2
zaś przez An oznaczmy macierz otrzymaną z macierzy A po usunięciu z niej kolumn o
numerach j1, j2, . . ., jm. Dalej przyjmijmy oznaczenie:
�ł łł
xj
1
�ł śł
�ł śł
�ł śł
xj
2
�ł śł
Xb = �ł śł
.
�ł śł
.
.
�ł śł
�ł �ł
xj
m
i niech Xn oznacza wektor otrzymany z wektora X przez usunięcie z niego współrzędnych
o numerach j1, j2, . . ., jm. Przy tych oznaczeniach układ równań liniowych (1.6) AX = B
można zapisać w następującej postaci:
AbXb + AnXn = B (1.6)
Ponieważ macierz Ab jest macierzą kwadratową wymiaru m � m i jej rząd wynosi m (bo
ma tyle liniowo niezależnych kolumn), więc jest macierzą odwracalną. Mnożąc obie strony
równości (1.6) przez macierz (Ab)-1 otrzymujemy
Xb + (Ab)-1AnXn = (Ab)-1B. (1.7)
Otrzymaną postać układu równań liniowych nazywamy bazową postacią układu równań
liniowych (1.1).
1.3 Rozwiązania bazowe
Z równości (1.7) otrzymujemy natychmiast
Xb = (Ab)-1 (B - AnXn) . (1.8)
Zauważmy, że wartości zmiennych xi występujące w wektorze Xn można ustalić dowolnie,
a następnie, za pomocą wzoru (1.8), obliczyć wartości współrzędnych wektora Xb. Wzór
(1.8) pozwala więc na znalezienie wszystkich rozwiązań układu równań liniowych (1.1) (lub,
równoważnie, układu (1.4)). W rozwiązaniach tych n - m niewiadomych może przyjmować
dowolne wartości nazywamy je zmiennymi niezależnymi lub niebazowymi i mówi-
my, że rozwiązanie zależy od n - m parametrów. Pozostałe niewiadome: xj , xj , . . ., xj
1 2 m
nazywane są zmiennymi zależnymi lub bazowymi i zależą od zmiennych niebazowych
w sposób opisany wzorem (1.8).
Należy podkreślić, że to czy dana niewiadoma w układzie równań liniowych zostanie
sklasyfikowana jako zmienna bazowa, czy też niebazowa, zalęży od wyboru macierzy Ab:
3
konstruujemy ją wybierając z macierzy A m liniowo niezależnych kolumn i zmienne o nu-
merach tych kolumn stają się zmiennymi bazowymi. Inny wybór macierzy Ab prowadzi do
innego przydziału ról niewiadomym. Wynika stąd, że liczba możliwych wyborów zmien-
nych bazowych w układzie równań liniowych (1.1) jest równa liczbie mozliwych wyborów
macierzy kwadratowej Ab rzędu m. Ponieważ budujemy taką macierz wybierając m ko-
lumn spośród n kolumn macierzy A, więc maksymalną liczbą wyborów różnych układów
zmiennych bazowych jest

n
.
m
Definicja 1. Rozwiązaniem bazowym układu równań liniowych (1.1) nazywamy każde
rozwiązanie tego układu, w którym zmienne niebazowe przyjmują wartość 0. Dopuszczal-
nym rozwiązaniem bazowym nazywamy takie rozwiązanie bazowe, w którym wartości
wszystkich zmiennych są nieujemne.
Bezpośrednio z uwag poprzedzających tę definicję wynika twierdzenie:

n
Twierdzenie 1. Układ równań liniowych (1.1) może mieć co najwyżej rozwiązań
m
bazowych.
Zauważmy, że rozwiązanie bazowe otrzymujemy podstawiając Xn = [0 0 . . . 0]T we
wzorze (1.8). Wobec tego
Xb = (Ab)-1B
i, w konsekwencji, w celu wyznaczenia rozwiązania bazowego nie potrzeba używać macierzy
An.
Przykład 1. Rozważmy układ równań liniowych:
ńł
�ł
�ł
2x1 + x2 - 2x3 + 2x4 = 3,
�ł
ół
x1 + x2 - x3 + 2x4 = 2.
Z kolumn macierzy głównej tego układu
�ł łł
2 1 -2 2
�ł �ł
A =
1 1 -1 2
można utworzyć sześć macierzy kwadratowych stopnia 2, ale wśród nich tylko cztery na-
stępujące mają rząd równy 2:
�ł łł �ł łł �ł łł �ł łł
2 1 2 2 1 -2 -2 2
�ł �ł �ł �ł �ł �ł �ł �ł
Ab = , Ab = , Ab = , Ab =
1 2 3 4
1 1 1 2 1 -1 -1 2
4
i odpowiadają kolejno następującym układom zmiennych bazowych:
(x1, x2), (x1, x4), (x2, x3), (x3, x4).
Wynika stąd, że rozważany układ równań ma dokładnie cztery rozwiązania bazowe. Aby
je znalezć należy wyznaczyć wektory zmiennych bazowych korzystając ze wzoru:
�ł łł
3
�ł �ł
Xib = (Ab)-1B, gdzie B = , i = 1, 2, 3, 4.
i
2
Ponieważ
�ł łł �ł łł �ł łł �ł łł
-1 -1 -1 -1
1 -1 1 -1 -1 2 -1 1
�ł �ł �ł �ł �ł �ł �ł �ł
Ab = , Ab = , Ab = , Ab =
1 2 3 4
-1 2 -1 1 -1 1 -1 1
2 2
dostajemy kolejno:
�ł łł �ł łł �ł łł �ł łł
x1 1 -1 3 1
b
�ł �ł �ł �ł �ł �ł �ł �ł
X1 = = = ,
x2 -1 2 2 1
�ł łł �ł łł �ł łł �ł łł
x1 1 -1 3 1
b
�ł �ł �ł �ł �ł �ł �ł �ł
X2 = = = ,
1
x4 -1 1 2
2 2
�ł łł �ł łł �ł łł �ł łł
x2 -1 2 3 1
b
�ł �ł �ł �ł �ł �ł �ł �ł
X3 = = = ,
x3 -1 1 2 -1
�ł łł �ł łł �ł łł �ł łł
x3 -1 1 3 -1
b
�ł �ł �ł �ł �ł �ł �ł �ł
X4 = = = .
1
x4 -1 1 2
2 2
Wobec tego otrzymujemy cztery rozwiązania bazowe:
�ł łł �ł łł �ł łł �ł łł
1 1 0 0
�ł śł �ł śł �ł śł �ł śł
�ł śł �ł śł �ł śł �ł śł
�ł śł �ł śł �ł śł �ł śł
1 0 1 0
�ł śł �ł śł �ł śł �ł śł
X1 = , X2 = , X3 = , X4 = ,
�ł śł �ł śł �ł śł �ł śł
�ł śł �ł śł �ł -1
śł �ł -1
śł
0 0
�ł �ł �ł �ł �ł �ł �ł �ł
1 1
0 0
2 2
z których tylko dwa pierwsze są dopuszczalnymi rozwiązaniami bazowymi.
1.4 Znajdowanie rozwiązań bazowych
W praktyce, chcąc znalezć rozwiązanie bazowe układu równań liniowych, sprowadzamy ten
układ do postaci bazowej (zrdukowanej) korzystając z metody eliminacji Gaussa-Jordana.
W trakcie stosowania tej metody decydujemy kolejno, które zmienne będziemy traktować
jako zmienne bazowe. Układ równań, jaki otrzymujemy po zakończeniu procedury elimina-
cji, jest de facto układem postaci (1.7), jednak podczas jego tworzenia nie było konieczne
wyznaczanie macierzy Ab ani macierzy do niej odwrotnej.
5
Przykład 2. Dla układu równań z poprzedniego przykładu macierz tego układu ma postać:
�ł łł
2 1 -2 2 3
�ł �ł
.
1 1 -1 2 2
Po odjęciu wyrazów drugiego wiersza o wyrazów wiersza pierwszego dostajemy:
�ł łł
1 0 -1 0 1
�ł �ł
,
1 1 -1 2 2
a po odjęciu w tej macierzy wyrazów pierwszego wiersza o wyrazów drugiego wiersza do-
stajemy macierz
�ł łł
1 0 -1 0 1
�ł �ł
.
0 1 0 2 1
postaci zredukowanej układu równań:
ńł
�ł
�ł
x1 - x3 = 1,
�ł
ół
x2 + 2x4 = 1.
Zmiennymi bazowymi w tym układzie są x1 i x2 (co wynika z przebiegu procedury elimina-
cji). Podstawiając x3 = 0 i x4 = 0 otrzymujemy (znane już wcześniej) rozwiązanie bazowe:
x1 = 1, x2 = 1, x3 = 0 i x4 = 0.
Jak widać z powyższego przykładu, znalezienie jednego rozwiązania bazowego ukła-
du rownań liniowych jest proste. Istotnym problemem jest jednak znalezienie wszystkich
rozwiązań bazowych lub wszystkich dopuszczalnych rozwiązań bazowych. Jak się okaże,
znajomość takich rozwiązań ma kluczowe znaczenie przy rozwiązywaniu zadań optyma-
lizacji liniowej. Na szczęście, jeżeli znane jest jedno rozwiązanie bazowe, to łatwo można
wyznaczyć pozostałe takie rozwiązania przy wykorzystaniu metody eliminacji. Dotyczy to
również dopuszczalnych rozwiązań bazowych. Procedura stosowana do znajdowania kolej-
nych rozwiązań bazowych nazywana jest metodą jednokrotnej wymiany zmiennych.
Jest to procedura iteracyjna polegająca na tym, że w każdym kroku zastępujemy jedną z
aktualnych zmiennych bazowych nową zmienną wybraną tak, aby nie powtórzył się któ-
ryś z układów zmiennych bazowych znalezionych do tej pory. Realizujemy to postępując
zgodnie z opisaną poniżej procedurą:
Wyznaczanie wszystkich rozwiązań bazowych metodą jednokrotnej wy-
miany zmiennych
1) doprowadzamy wyjściowy układ równań do postaci bazowej i znajdujemy początkowe
rozwiązanie bazowe,
6
2) w tablicy Gaussa zapisujemy wszystkie współczynniki układu równań w postaci ba-
zowej,
3) w otrzymanej tablicy wybieramy kolumnę niebazową (tzn. odpowiadającą zmiennej
niebazowej) i w tej kolumnie wybieramy jeden element niezerowy jako element głów-
ny,
4) stosujemy metodę eliminacji tak, aby wybrana kolumna stała się kolumną jednost-
kową, tzn. kolumną, która ma jedynkę na miejscu elementu głównego i zera na pozo-
stałych pozycjach (w wyniku takiego postępowania zmienną bazową przestaje być ta
zmienna, której odpowiadała kolumna posiadająca jedynkę w wierszu zawierającym
wybrany element główny),
5) odczytujemy nowe rozwiązanie bazowe przypisując zmiennym bazowym wartości znaj-
dujące się w kolumnie wyrazów wolnych, a zmiennym niebazowym wartość zero,
6) sprawdzamy, czy jest możliwe wybranie nowej zmiennej bazowej w taki sposób, aby
nie powtórzył się któryś z wcześniejszych układów zmiennych bazowych; jeśli tak, to
wracamy do punktu 3, jeżeli nie, kończymy postępowanie.
Zilustrujemy teraz etapy takiego postępowania za pomocą przykładu.
Przykład 3. Wróćmy do układu równań liniowych rozważanego w przykładzie 1, dla którego
w przykładzie 2 znależliśmy postać bazową (zredukowaną):
ńł
�ł
�ł
x1 - x3 = 1,
�ł
ół
x2 + 2x4 = 1
o macierzy
�ł łł
1 0 -1 0 1
�ł �ł
.
0 1 0 2 1
Możemy więc przystąpić do wykonania kroku trzeciego z opisanej wyżej procedury. Zmien-
nymi bazowymi są w tym momencie zmienne x1 i x2, a początkowym rozwiazaniem bazo-
wym:
X1 = (1, 1, 0, 0).
Tworzymy więc tablicę Gaussa (litera b w nagłówku oznacza kolumnę wyrazów wolnych):
baza x1 x2 x3 x4 b
,
x1 1 0 -1 0 1
x2 0 1 0 2 1
7
w której wybieramy kolumnę odpowiadającą zmiennej niebazowej x4, a w niej element
równy 2 to będzie element główny w tej kolumnie:
baza x1 x2 x3 x4 b
.
x1 1 0 -1 0 1
x2 0 1 0 2 1
Położenie elementu głównego oznacza, że w kolejnym otrzymanym rozwiązaniu bazowym
zmienna x4 zastąpi w układzie zmiennych bazowych zmienną x2. Z kolumny czwartej mo-
żemy otrzymać kolumnę macierzy jednostkowej, z jedynką na miejscu elementu główne-
go, poprzez podzielenie wyrazów drugiego wiersza przez 2. Ponadto zastępujemy w liście
zmiennych bazowych po lewej stronie tabeli Gaussa zmienną x2 przez zmienną x4:
baza x1 x2 x3 x4 b
.
x1 1 0 -1 0 1
1 1
x4 0 0 1
2 2
W ten sposób wykonaliśmy krok czwarty procedury i w kroku piątym odczytujemy nowe
rozwiązanie bazowe:

1
X2 = 1, 0, 0, .
2
Przechodzimy do kroku szóstego. Widać, że możemy teraz zastąpić zmienną bazową x1
przez zmienną x3. Wobec tego wracamy do kroku trzeciego i stosujemy go do kolumny
odpowiadającej zmiennej x3: znajdujemy w tej kolumnie element główny
baza x1 x2 x3 x4 b
,
x1 1 0 -1 0 1
1 1
x4 0 0 1
2 2
przekształcamy tabelę tak, aby kolumna x3 stała się kolumną jednostkową i wprowadzamy
zmienną x3 do bazy na miejsce zmiennej x1:
baza x1 x2 x3 x4 b
,
x3 -1 0 1 0 -1
1 1
x4 0 0 1
2 2
a następnie odczytujemy kolejne rozwiązanie bazowe:

1
X3 = 0, 0, -1, .
2
Ponownie zauważamy, że można wprowadzić do bazy zmienną x2 na miejsce zmiennej
x4, co prowadzi do ponownego uruchomienia pętli iteracyjnej procedury, w wyniku czego
dostajemy tablicę Gaussa z nowym elementem głównym w kolumnie x2:
8
baza x1 x2 x3 x4 b
x3 -1 0 1 0 -1 ,
1 1
x2 0 0 1
2 2
którą przekształcamy do postaci z jedynką jako elementem głównym:
baza x1 x2 x3 x4 b
.
x3 -1 0 1 0 -1
x2 0 1 0 2 1
Odczytujemy stąd następne rozwiązanie bazowe:
X4 = (0, 1, -1, 0) .
Kontynuowanie tego postępowania nie jest możliwe, bo każda próba wprowadzenia którejś
ze zmiennych do bazy prowadzi do jednego z układów zmiennych bazowych otrzymanych
już wcześniej. Ostatecznie wnioskujemy, że układ równań liniowych 1 ma cztery, powyżej
wymienione, rozwiązania bazowe.
Uwaga 1. Zgodnie z twierdzeniem 1 maksymalna liczba rozwiązań bazowych układu dwóch

4
równań liniowych z czterema niewiadomymi wynosi = 6. Jak widać, rozważany układ
2
ma tylko cztery takie rozwiazania, skąd wynika, że twierdzenie 1 daje tylko oszacowanie z
góry liczby rozwiązań bazowych, a nie ich dokładną liczbę. Ponadto zauważamy, że tylko
dwa spośród otrzymanych rozwiązań są dopuszczalnymi rozwiązaniami bazowymi, czyli
takimi rozwiązaniami bazowymi, które mają wszystkie współrzędne nieujemne.
Uwaga 2. W celu zaoszczędzenia miejsca i nadania przejrzystości prowadzonym przekształ-
ceniom kolejno otrzymywane tablice Gaussa zapisujemy jedna pod drugą zaznaczając tylko
nowo wprowadzane elementy główne. W takiej, ogólnie przyjętej notacji, efekty przepro-
wadzonych rozważań przyjmują postać:
baza x1 x2 x3 x4 b rozwiązanie bazowe
x1 1 0 -1 0 1
x2 0 1 0 2 1 X1 = (1, 1, 0, 0)
x1 1 0 -1 0 1

1 1 1
x4 0 0 1 X2 = 1, 0, 0, ,
2 2 2
x3 -1 0 1 0 -1

1 1 1
x4 0 0 1 X3 = 0, 0, -1,
2 2 2
x3 -1 0 1 0 -1
x2 0 1 0 2 1 X4 = (0, 1, -1, 0)
9
1.5 Wyznaczanie dopuszczalnych rozwiązań bazowych
W rozważanym powyżej przykładzie otrzymaliśmy wszystkie możliwe rozwiązania bazowe,
a nie tylko bazowe rozwiązania dopuszczalne, które pełnią szczególną rolę w rozwiązywaniu
zadań optymalizacji liniowej. W celu wyznaczenia wszystkich bazowch rozwiązań dopusz-
czalnych można więc znalezć wszystkie rozwiązania bazowe i z nich wybrać rozwiązania
dopuszczalne (co jest na ogół dość żmudne) lub zmodyfikować nieco podaną powyżej pro-
cedurę tak, aby kolejno otrzymywane rozwiązania bazowe były dopuszczalne. Modyfikacja
ta musi być przeprowadzona w ten sposób, żeby w każdej iteracji kolumna wyrazów wol-
nych (b)zawierała jedynie wartości dodatnie, a jednocześnie, żeby nie zostala ograniczona
możliwość wyznaczenia wszystkich interesujących nas rozwiązań. Zauważmy ponadto, że w
powyższym przykładzie wybór zmiennej wchodzącej do bazy determinował jednoznacznie
zmienną, którą bazę opuszcza było to konsekwencją faktu, że w wybieranych kolumnach
tylko jedna liczba była różna od zera. W przypadku ogólnym tak być nie musi. Należy więc
również zatroszczyć się o to, aby procedura wskazywała zmienną wychodzącą z bazy.
Wyznaczanie wszystkich dopuszczalnych rozwiązań bazowych metodą
jednokrotnej wymiany zmiennych
1) doprowadzamy wyjściowy układ równań do postaci bazowej z dodatnimi wyrazami
wolnymi bi i znajdujemy początkowe rozwiązanie bazowe,
2) w tablicy Gaussa zapisujemy wszystkie współczynniki układu równań w postaci bazo-
wej i uzupełniamy tablicę dodając jedną kolumnę z prawej strony; liczby znajdujące
się w tej kolumnie nazywać będziemy ilorazami wyjścia,
3) w otrzymanej tablicy wybieramy kolumnę niebazową (tzn. odpowiadającą zmiennej
niebazowej) zawierającą co najmniej jeden wyraz dodatni; przyjmijmy, że kolumna
ta odpowiada zmiennej xj ,
0
4) dla każdego dodatniego elementu aij > 0, i = 1, 2, . . . , m, wybranej kolumny two-
0
rzymy iloraz wyjścia
bi
yij =
0
aij
0
i umieszczamy go w i-tym wierszu ostatniej kolumny tablicy; dla niedodatnich wy-
razów wybranej kolumny ilorazów wyjścia nie tworzymy,
5) na przecięciu wiersza zawierającego najmniejszy z ilorazów wyjścia i wybranej kolum-
ny znajduje się element dodatni, który w danej iteracji staje się elementem głównym,
10
6) stosujemy metodę eliminacji tak, aby wybrana kolumna stała się kolumną jednost-
kową, tzn. kolumną, która ma jedynkę na miejscu elementu głównego i zera na pozo-
stałych pozycjach (w wyniku takiego postępowania zmienną bazową przestaje być ta
zmienna, której odpowiadała kolumna posiadająca jedynkę w wierszu zawierającym
wybrany element główny),
7) odczytujemy nowe rozwiązanie bazowe przypisując zmiennym bazowym wartości znaj-
dujące się w kolumnie wyrazów wolnych, a zmiennym niebazowym wartość zero,
8) sprawdzamy, czy jest możliwe wybranie nowej zmiennej bazowej w taki sposób, aby
nie powtórzył się któryś z wcześniejszych układów zmiennych bazowych i był spełnio-
ny warunek, że dodatni jest przynajmniej jeden wyraz w kolumnie odpowiadającej
wybieranej zmiennej; jeśli tak, to wracamy do punktu 3, jeżeli nie, kończymy postę-
powanie.
Uwaga 3. Poprawność opisanej procedury (prowadzącej do otrzymania rozwiązań bazowych
z nieujemnymi wartościami) wynika z odpowiedniego wyboru zmiennej wchodzącej do ba-
zy, przeprowadzonego w krokach 4. i 5. Uzasadnimy obecnie, że dysponując dopuszczalnym
rozwiązaniem bazowym i zmieniając je w opisany sposób otrzymujemy nowe dopuszczalne
rozwiązanie bazowe. Chcielibyśmy, żeby w nowym rozwiązaniu bazowym wszystkie warto-
ści były nieujemne. W tym celu należy odpowiednio wybrać element główny ai j0. Załóżmy
0
więc, że ai j0 jest dodatnim elementem w ustalonej wcześniej kolumnie o numerze j0 wy-
0
branym tak, aby utworzony dla niego iloraz wyjścia był najmniejszy z możliwych. Oznacza
to, że
bi bi
0
(1.9)
aij ai j0
0 0
dla wszystkich wskazników i = i0, dla których aij > 0. Korzystając z metody eliminacji

0
dostajemy w nowym rozwiązaniu wartość zmiennej bazowej xi równą
bi
0
xi = bi - aij . (1.10)
0
ai j0
0
Z nierówności (1.9) i założenia, że aij > 0 wynika, iż xi 0. Jednocześnie widać, dlaczego
0
operujemy wyłącznie dodoatnimi elementami j-tej kolumny: rozważanie wszystkich ele-
mentów mogłoby nie zapewnić zachodzenie nierówności (1.9) lub uniemożliwić obliczenie
xi ze wzoru (1.10).
Przykład 4. Znajdziemy wszystkie dopuszczalne rozwiązania bazowe dla układu równań
11
liniowych:
ńł
�ł
�ł
�łx1 + x4 - x5 = 2,
�ł
�ł
�ł
x2 - 2x4 + x5 = 1,
�ł
�ł
�ł
�ł
�ł
ół
x3 + x4 - 2x5 = 1.
Jest to układ w postaci bazowej, którego współczynniki należy umieścić w tablicy Gaussa,
a następnie zastosować iteracyjnie opisany wyżej algorytm tak, aby otrzymać wszystkie
dopuszczalne rozwiązania bazowe. W przypadku powyższego układu równań otrzymujemy
następujące trzy tablice Gaussa:
bi
nr baza x1 x2 x3 x4 x5 b rozwiązanie bazowe
aij
x1 1 0 0 1 -1 2 2
1. x2 0 1 0 -2 1 1 - X1 = (2, 1, 1, 0, 0)
x3 0 0 1 1 -2 1 1
x1 1 0 -1 0 1 1 1
.
2. x2 0 1 2 0 -3 3 - X2 = (1, 3, 0, 1, 0)
x4 0 0 1 1 -2 1 -
x5 1 0 -1 0 1 1
3. x2 3 1 -1 0 0 6 X3 = (0, 6, 0, 3, 1)
x4 2 0 -1 1 0 3
Pierwsza tablica zawiera współczynniki danego układu równań. Ponieważ układ dany
jest w postaci bazowej a wartości wyrazów wolnych są dodatnie, pierwsze dopuszczalne roz-
wiązanie X1 dostajemy za darmo . W celu otrzymania drugiego dopuszczalnego rozwiąza-
nia bazowego wybieramy zmienną x4 jako nową zmienną bazową. Gdyby nie interesowało
nas, aby nowe rozwiązanie bazowe było dopuszczalne, moglibyśmy jako element główny
wybrać dowolny z elementów kolumny x4, ale ponieważ chcemy, żeby nowe rozwiązanie
zawierało tylko wartości nieujemne, obliczamy ilorazy wyjścia dzieląc wyrazy wolne przez
dodatnie współczynniki z kolumny x4 i wybieramy najmniejszy z tych ilorazów: znajduje
się on w wierszu trzecim, a więc zmienna x4 zastąpi w bazie zmienną x3. Dlatego jako
element główny wybieramy liczbę 1 stojącą na przecięciu trzeciego wiersza i kolumny x4;
fakt ten zaznaczamy rysując ramkę wokół wybranej liczby. Wiersz trzeci po pomnożeniu
przez odpowiednie liczby dodajemy do wiersza pierwszego oraz drugiego tak, aby w ko-
lumna x4 stała się kolumną macierzy jednostkowej z jedynką w trzecim wierszu i zerami
w wierszach pozostałych. Otrzymujemy w ten sposób drugą z powyższych tablic Gaussa,
z której odczytujemy drugie dopuszczalne rozwiązanie bazowe X2.
Trzecie dopuszczalne rozwiązanie bazowe wyznaczymy wybierając najpierw nową zmien-
ną bazową spośród zmiennych x3 i x5 (pozostałe zmienne są bazowe). Wybór zmiennej x3
12
doprowadziłby do powrotu do rozwiązania X1, a więc decydujemy się na wybór zmiennej
x5. W kolumnie x5 znajduje się tylko jeden element dodatni (w pierwszym wierszu), a
więc można obliczyć tylko jeden iloraz wyjścia i ten dodatni element stanie się nowym ele-
mentem głównym. Wskazuje on, że w następnym rozwiązaniu zmienna x5 zastąpi w bazie
zmienną x1. Po odpowiednim przekształceniu otrzymujemy trzecią tablicę Gaussa i trzecie
dopuszczalne rozwiązanie bazowe X3.
Próba kolejnego wyboru nowej zmiennej bazowej kończy się niepowodzeniem. Istotnie,
można wybierać jedynie spośród zmiennych x1 lub x3. Ale w kolumnie x3 nie ma elemen-
tów dodatnich, co uniemożliwia wybór tej zmiennej, zaś zdecydowanie się na zmienną x1
doprowadziłoby do ponownego otrzymania tablicy drugiej i rozwiązania X2. Wobec tego
należy zakończyć procedurę: jedynymi dopuszczalnymi rozwiązaniami bazowymi są trzy
znalezione rozwiązania X1, X2 i X3.
1.6 Interpretacja geometryczna rozwiązań bazowych
Przy próbie zobaczenia czym są rozwiązania bazowe układu równań liniowych pojawia
się problem wynikający z niedoskonałości naszej wyobrazni i niemożliwości wizualizacji
obiektów o liczbie wymiarów większej niż 3, a przecież rozwiązania układu równań o n
zmiennych są rozmaitościami liniowymi (hiperpłaszczyznami) w przestrzeni n-wymiarowej.
Dlatego posłużymy się dwoma bardzo prostymi przykładami, które można zinterpretować
w przestrzeni R3, i które, niestety, nie uwzględnią wszystkich możliwości, ale pozwolą na
wyrobienie sobie poglądu na sprawę w ogólnej sytuacji.
Przykład 5. Rozważmy układ dwóch równań z trzema niewiadomymi:
ńł
�ł
�ł
x1 + 2x3 = 4,
�ł
ół
x2 - x3 = 1.
Oczywiście, wszystkie rozwiązania tego układu równań można przedstawić w postaci pa-
rametrycznej:
ńł
�ł
�ł
�łx1 = 4 - 2t,
�ł
�ł
�ł
(1.11)
x2 = 1 + t,
�ł
�ł
�ł
�ł
�ł
ół
x3 = t,
gdzie t " R jest dowolną liczbą. Wszystkie rozwiązania bazowe tego układu możemy wy-
znaczyć przyrównując do 0 kolejno x1, x2 i x3, obliczając w każdym przypadku wartość
parametru t, dla której zachodzi ta równość, a następnie wstawiając znalezioną wartość t do
13
wzorów na pozostałe zmienne. Np. równość x1 = 0 zachodzi dla t = 2 i wtedy x2 = 1+2 = 3
oraz x3 = 2. Dostajemy więc pierwsze rozwiązanie bazowe:
X1 = (0, 3, 2).
Podobnie, x2 = 0 dla t = -1 i, w konsekwencji, drugim rozwiązaniem bazowym jest
X2 = (6, 0, -1).
Analogicznie dostajemy trzecie rozwiązanie bazowe
X3 = (4, 1, 0).
Zauważmy, że wśród tych rozwiązań tylko X1 i X3 są dopuszczalnymi rozwiązaniami ba-
zowymi.
Z geometrycznego punktu widzenia, równania (1.11) są równaniami parametrycznymi
pewnej prostej L w R3. Współrzędne każdego punktu na tej prostej tworzą rozwiązanie roz-
ważanego układu równań. Ze sposobu wyznaczania rozwiązań bazowych wynika, że punkty
o współrzędnych danych tymi rozwiązaniami są punktami, w których prosta L przebija
płaszczyzny układu współrzędnych. W pierwszym oktancie przestrzeni R3, tzn. w zbiorze

(x1, x2, x3) " R3 : x1 0 '" x2 0 '" x3 0
leżą tylko dwa spośród tych punktów, a mianowicie te, które odpowiadają rozwiązaniom
X1 i X3. Rozwiązując układ nierówności
ńł
�ł
�ł
�ł4 - 2t 0,
�ł
�ł
�ł
1 + t 0,
�ł
�ł
�ł
�ł
�ł
ół
t 0,
otrzymujemy t " [0, 2], a więc punkty X1 i X3 są końcami odcinka prostej L leżącego
w pierwszym oktancie układu współrzędnych w R3 i określonego równaniami (1.11) dla
t " [0, 2].
Przykład 6. Rozważmy jedno równanie z trzema niewiadomymi:
x1 - 2x2 + 3x3 = 6.
Oczywiście wszystkie wcześniej wprowadzone pojęcia są dobrze określone również dla ta-
kiego układu złożonego z jednego równania.
14
Powyższe równanie jest równaniem płaszczyzny prostopadłej do wektora [1, -2, 3].
Wszystkie rozwiązania bazowe tego równania można otrzymać podstawiając 0 za dwie
spośród trzech zmiennych x1, x2 i x3. Dostajemy więc rozwiązania bazowe:
X1 = (6, 0, 0), X2 = (0, -3, 0), X3 = (0, 0, 2),
z których tylko pierwsze i trzecie są dopuszczalne, a więc leżą w pierwszym oktancie układu
współrzędnych. Część zbioru wszystkich rozwiązań zawarta w pierwszym oktancie układu
współrzędnych jest więc nieograniczonym obszarem leżącym w płaszyznie , który jest
ograniczony odcinkiem o końcach X1 i X3 (leżącym w płaszczyznie Ox1x2) i półprostymi
- -
-- --
o kierunkach wyznaczonych przez wektory X2X3, X2X1, których punktami początkowymi
są X3 oraz X1 odpowiednio (sporządz rysunek!).
Uogólniając powyższe przykłady na przypadek dowolnego skończonego wymiaru można
wysnuć następujący wniosek:
Zbiór S wszystkich rozwiązań układu m równań liniowych z n niewiadomymi,
gdzie n m i m jest rzędem tego układu, jest (n - m)-wymiarową hiperpłasz-
czyzną w przestrzeni n wymiarowej Rn. Część wspólna zbioru S i pierwszego
ortantu układu współrzędnych:
{(x1, x2, . . . , xn) " Rn : "i=1, 2, ..., n xi 0}
jest (n - m)-wymiarowym wielościanem (ograniczonym lub nie), którego wierz-
chołki odpowiadają dopuszczalnym rozwiązaniom bazowym i leżą na m-wymiarowych
hiperpłaszczyznach zawartych w (n - 1)-wymiarowych ścianach tego ortantu.
15

Wyszukiwarka

Podobne podstrony:
uklady rownan liniowych
4 uklady rownan liniowych
t5 uklady rownan liniowych
wykład 11 układy równań liniowych
układy rownań liniowych
110 Układy równań liniowych
7 Układy równań liniowych
Zestaw 12 Macierz odwrotna, układy równań liniowych
lab8 2 uklady rownan liniowych
lab7 uklady rownan liniowych
Zestaw układy równań liniowych(1)
zadania agebra, macierze, wielomiany, układy równań liniowych
zadania agebra, macierze, wielomiany, układy równań liniowych
Układy równań liniowych zadania

więcej podobnych podstron