Rozdział 1

Układy równań liniowych

1.1

Pojęcia wstępne

Załóżmy, że dane są liczby rzeczywiste a

ij

, gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n, oraz b

i

,

gdzie i = 1, 2, . . . , m. Rozważmy układ równań liniowych z niewiadomymi x

1

, x

2

, . . ., x

n

:











































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

m1

x

1

+ a

m2

x

2

+ . . . + a

mn

x

n

= b

m

.

(1.1)

Macierz












a

11

a

12

. . . a

1n

b

1

a

21

a

22

. . . a

2n

b

2

..

.

..

.

..

.

..

.

..

.

a

m1

a

m2

. . . a

mn

b

m












(1.2)

będziemy nazywać macierzą układu (1.1), zaś macierze

A =












a

11

a

12

. . . a

1n

a

21

a

22

. . . a

2n

..

.

..

.

..

.

..

.

a

m1

a

m2

. . . a

mn












oraz

B =












b

1

b

2

..

.

b

m












(1.3)

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

X =












x

1

x

2

..

.

x

m












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 wyraźnie 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

znaleźć m kolumn liniowo niezależnych.

Zgodnie z przyjętym założeniem przyjmijmy, że kolumny macierzy A o numerach j

1

, j

2

,

. . ., j

m

, tworzących ciąg rosnący, są liniowo niezależne i oznaczmy:

A

b

=












a

1j

1

a

1j

2

. . . a

1j

m

a

2j

1

a

2j

2

. . . a

2j

m

..

.

..

.

..

.

..

.

a

mj

1

a

mj

2

. . . a

mj

m












,

(1.5)

2

zaś przez A

n

oznaczmy macierz otrzymaną z macierzy A po usunięciu z niej kolumn o

numerach j

1

, j

2

, . . ., j

m

. Dalej przyjmijmy oznaczenie:

X

b

=












x

j

1

x

j

2

..

.

x

j

m












i niech X

n

oznacza wektor otrzymany z wektora X przez usunięcie z niego współrzędnych

o numerach j

1

, j

2

, . . ., j

m

. Przy tych oznaczeniach układ równań liniowych (1.6) AX = B

można zapisać w następującej postaci:

A

b

X

b

+ A

n

X

n

= B

(1.6)

Ponieważ macierz A

b

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 (A

b

)

−1

otrzymujemy

X

b

+ (A

b

)

−1

A

n

X

n

= (A

b

)

−1

B.

(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

X

b

= (A

b

)

−1

(B − A

n

X

n

) .

(1.8)

Zauważmy, że wartości zmiennych x

i

występujące w wektorze X

n

można ustalić dowolnie,

a następnie, za pomocą wzoru (1.8), obliczyć wartości współrzędnych wektora X

b

. 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: x

j

1

, x

j

2

, . . ., x

j

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 A

b

:

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 A

b

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 A

b

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:

Twierdzenie 1. Układ równań liniowych (1.1) może mieć co najwyżej



n

m



rozwiązań

bazowych.

Zauważmy, że rozwiązanie bazowe otrzymujemy podstawiając X

n

= [0 0 . . . 0]

T

we

wzorze (1.8). Wobec tego

X

b

= (A

b

)

−1

B

i, w konsekwencji, w celu wyznaczenia rozwiązania bazowego nie potrzeba używać macierzy

A

n

.

Przykład 1. Rozważmy układ równań liniowych:











2x

1

+ x

2

− 2x

3

+ 2x

4

= 3,

x

1

+ x

2

− x

3

+ 2x

4

= 2.

Z kolumn macierzy głównej tego układu

A =





2 1 −2 2

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:

A

b
1

=





2 1

1 1





,

A

b
2

=





2 2

1 2





,

A

b
3

=





1 −2

1 −1





,

A

b
4

=





−2 2

−1 2





4

i odpowiadają kolejno następującym układom zmiennych bazowych:

(x

1

, x

2

),

(x

1

, x

4

),

(x

2

, x

3

),

(x

3

, x

4

).

Wynika stąd, że rozważany układ równań ma dokładnie cztery rozwiązania bazowe. Aby

je znaleźć należy wyznaczyć wektory zmiennych bazowych korzystając ze wzoru:

X

b

i

= (A

b
i

)

−1

B,

gdzie

B =





3

2





,

i = 1, 2, 3, 4.

Ponieważ



A

b
1



−1

=





1 −1

−1

2





,



A

b
2



−1

=





1 −1

−

1
2

1





,



A

b
3



−1

=





−1 2

−1 1





,



A

b
4



−1

=





−1 1

−

1
2

1





dostajemy kolejno:

X

b

1

=





x

1

x

2





=





1 −1

−1

2









3

2





=





1

1





,

X

b

2

=





x

1

x

4





=





1 −1

−

1
2

1









3

2





=





1

1
2





,

X

b

3

=





x

2

x

3





=





−1 2

−1 1









3

2





=





1

−1





,

X

b

4

=





x

3

x

4





=





−1 1

−

1
2

1









3

2





=





−1

1
2





.

Wobec tego otrzymujemy cztery rozwiązania bazowe:

X

1

=











1

1

0

0











,

X

2

=











1

0

0

1
2











,

X

3

=











0

1

−1

0











,

X

4

=











0

0

−1

1
2











,

z których tylko dwa pierwsze są dopuszczalnymi rozwiązaniami bazowymi.

1.4

Znajdowanie rozwiązań bazowych

W praktyce, chcąc znaleźć 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 A

b

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ń:











x

1

− x

3

= 1,

x

2

+ 2x

4

= 1.

Zmiennymi bazowymi w tym układzie są x

1

i x

2

(co wynika z przebiegu procedury elimina-

cji). Podstawiając x

3

= 0 i x

4

= 0 otrzymujemy (znane już wcześniej) rozwiązanie bazowe:

x

1

= 1, x

2

= 1, x

3

= 0 i x

4

= 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ą):











x

1

− x

3

= 1,

x

2

+ 2x

4

= 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 x

1

i x

2

, a początkowym rozwiazaniem bazo-

wym:

X

1

= (1, 1, 0, 0).

Tworzymy więc tablicę Gaussa (litera b w nagłówku oznacza kolumnę wyrazów wolnych):

baza

x

1

x

2

x

3

x

4

b

x

1

1

0

−1

0

1

x

2

0

1

0

2

1

,

7

w której wybieramy kolumnę odpowiadającą zmiennej niebazowej x

4

, a w niej element

równy 2 — to będzie element główny w tej kolumnie:

baza

x

1

x

2

x

3

x

4

b

x

1

1

0

−1

0

1

x

2

0

1

0

2

1

.

Położenie elementu głównego oznacza, że w kolejnym otrzymanym rozwiązaniu bazowym

zmienna x

4

zastąpi w układzie zmiennych bazowych zmienną x

2

. 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ą x

2

przez zmienną x

4

:

baza

x

1

x

2

x

3

x

4

b

x

1

1

0

−1

0

1

x

4

0

1
2

0

1

1
2

.

W ten sposób wykonaliśmy krok czwarty procedury i w kroku piątym odczytujemy nowe

rozwiązanie bazowe:

X

2

=



1, 0, 0,

1

2



.

Przechodzimy do kroku szóstego. Widać, że możemy teraz zastąpić zmienną bazową x

1

przez zmienną x

3

. Wobec tego wracamy do kroku trzeciego i stosujemy go do kolumny

odpowiadającej zmiennej x

3

: znajdujemy w tej kolumnie element główny

baza

x

1

x

2

x

3

x

4

b

x

1

1

0

−1

0

1

x

4

0

1
2

0

1

1
2

,

przekształcamy tabelę tak, aby kolumna x

3

stała się kolumną jednostkową i wprowadzamy

zmienną x

3

do bazy na miejsce zmiennej x

1

:

baza

x

1

x

2

x

3

x

4

b

x

3

-1

0

1

0

−1

x

4

0

1
2

0

1

1
2

,

a następnie odczytujemy kolejne rozwiązanie bazowe:

X

3

=



0, 0, −1,

1

2



.

Ponownie zauważamy, że można wprowadzić do bazy zmienną x

2

na miejsce zmiennej

x

4

, co prowadzi do ponownego uruchomienia pętli iteracyjnej procedury, w wyniku czego

dostajemy tablicę Gaussa z nowym elementem głównym w kolumnie x

2

:

8

baza

x

1

x

2

x

3

x

4

b

x

3

−1

0

1

0

−1

x

2

0

1
2

0

1

1
2

,

którą przekształcamy do postaci z jedynką jako elementem głównym:

baza

x

1

x

2

x

3

x

4

b

x

3

−1

0

1

0

−1

x

2

0

1

0

2

1

.

Odczytujemy stąd następne rozwiązanie bazowe:

X

4

= (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

równań liniowych z czterema niewiadomymi wynosi



4
2



= 6. Jak widać, rozważany układ

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

x

1

x

2

x

3

x

4

b

rozwiązanie bazowe

x

1

1

0

−1

0

1

x

2

0

1

0

2

1

X

1

= (1, 1, 0, 0)

x

1

1

0

−1

0

1

x

4

0

1
2

0

1

1
2

X

2

=



1, 0, 0,

1
2



x

3

−1

0

1

0

−1

x

4

0

1
2

0

1

1
2

X

3

=



0, 0, −1,

1
2



x

3

−1

0

1

0

−1

x

2

0

1

0

2

1

X

4

= (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 znaleźć 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 b

i

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 x

j

0

,

4) dla każdego dodatniego elementu a

ij

0

> 0, i = 1, 2, . . . , m, wybranej kolumny two-

rzymy iloraz wyjścia

y

ij

0

=

b

i

a

ij

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 a

i

0

j

0

. Załóżmy

więc, że a

i

0

j

0

jest dodatnim elementem w ustalonej wcześniej kolumnie o numerze j

0

wy-

branym tak, aby utworzony dla niego iloraz wyjścia był najmniejszy z możliwych. Oznacza

to, że

b

i

a

ij

0

­

b

i

0

a

i

0

j

0

(1.9)

dla wszystkich wskaźników i 6= i

0

, dla których a

ij

0

> 0. Korzystając z metody eliminacji

dostajemy w nowym rozwiązaniu wartość zmiennej bazowej x

i

równą

x

i

= b

i

−

b

i

0

a

i

0

j

0

a

ij

0

.

(1.10)

Z nierówności (1.9) i założenia, że a

ij

0

> 0 wynika, iż x

i

­ 0. Jednocześnie widać, dlaczego

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

x

i

ze wzoru (1.10).

Przykład 4. Znajdziemy wszystkie dopuszczalne rozwiązania bazowe dla układu równań

11

liniowych:



























x

1

+ x

4

− x

5

= 2,

x

2

− 2x

4

+ x

5

= 1,

x

3

+ x

4

− 2x

5

= 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:

nr

baza

x

1

x

2

x

3

x

4

x

5

b

b

i

a

ij

rozwiązanie bazowe

x

1

1

0

0

1

−1

2

2

1.

x

2

0

1

0

−2

1

1

-

X

1

= (2, 1, 1, 0, 0)

x

3

0

0

1

1

−2

1

1

x

1

1

0

−1

0

1

1

1

2.

x

2

0

1

2

0

−3

3

-

X

2

= (1, 3, 0, 1, 0)

x

4

0

0

1

1

−2

1

-

x

5

1

0

−1

0

1

1

3.

x

2

3

1

−1

0

0

6

X

3

= (0, 6, 0, 3, 1)

x

4

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 X

1

dostajemy „za darmo”. W celu otrzymania drugiego dopuszczalnego rozwiąza-

nia bazowego wybieramy zmienną x

4

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 x

4

, 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 x

4

i wybieramy najmniejszy z tych ilorazów: znajduje

się on w wierszu trzecim, a więc zmienna x

4

zastąpi w bazie zmienną x

3

. Dlatego jako

element główny wybieramy liczbę 1 stojącą na przecięciu trzeciego wiersza i kolumny x

4

;

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 x

4

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 X

2

.

Trzecie dopuszczalne rozwiązanie bazowe wyznaczymy wybierając najpierw nową zmien-

ną bazową spośród zmiennych x

3

i x

5

(pozostałe zmienne są bazowe). Wybór zmiennej x

3

12

doprowadziłby do powrotu do rozwiązania X

1

, a więc decydujemy się na wybór zmiennej

x

5

. W kolumnie x

5

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 x

5

zastąpi w bazie

zmienną x

1

. Po odpowiednim przekształceniu otrzymujemy trzecią tablicę Gaussa i trzecie

dopuszczalne rozwiązanie bazowe X

3

.

Próba kolejnego wyboru nowej zmiennej bazowej kończy się niepowodzeniem. Istotnie,

można wybierać jedynie spośród zmiennych x

1

lub x

3

. Ale w kolumnie x

3

nie ma elemen-

tów dodatnich, co uniemożliwia wybór tej zmiennej, zaś zdecydowanie się na zmienną x

1

doprowadziłoby do ponownego otrzymania tablicy drugiej i rozwiązania X

2

. Wobec tego

należy zakończyć procedurę: jedynymi dopuszczalnymi rozwiązaniami bazowymi są trzy

znalezione rozwiązania X

1

, X

2

i X

3

.

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 wyobraźni 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 R

3

, 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:











x

1

+ 2x

3

= 4,

x

2

− x

3

= 1.

Oczywiście, wszystkie rozwiązania tego układu równań można przedstawić w postaci pa-

rametrycznej:



























x

1

= 4 − 2t,

x

2

= 1 + t,

x

3

= t,

(1.11)

gdzie t ∈ R jest dowolną liczbą. Wszystkie rozwiązania bazowe tego układu możemy wy-

znaczyć przyrównując do 0 kolejno x

1

, x

2

i x

3

, 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ść x

1

= 0 zachodzi dla t = 2 i wtedy x

2

= 1+2 = 3

oraz x

3

= 2. Dostajemy więc pierwsze rozwiązanie bazowe:

X

1

= (0, 3, 2).

Podobnie, x

2

= 0 dla t = −1 i, w konsekwencji, drugim rozwiązaniem bazowym jest

X

2

= (6, 0, −1).

Analogicznie dostajemy trzecie rozwiązanie bazowe

X

3

= (4, 1, 0).

Zauważmy, że wśród tych rozwiązań tylko X

1

i X

3

są dopuszczalnymi rozwiązaniami ba-

zowymi.

Z geometrycznego punktu widzenia, równania (1.11) są równaniami parametrycznymi

pewnej prostej L w R

3

. 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 R

3

, tzn. w zbiorze

n

(x

1

, x

2

, x

3

) ∈ R

3

: x

1

­ 0 ∧ x

2

­ 0 ∧ x

3

­ 0

o

leżą tylko dwa spośród tych punktów, a mianowicie te, które odpowiadają rozwiązaniom

X

1

i X

3

. Rozwiązując układ nierówności



























4 − 2t ­ 0,

1 + t ­ 0,

t ­ 0,

otrzymujemy t ∈ [0, 2], a więc punkty X

1

i X

3

są końcami odcinka prostej L leżącego

w pierwszym oktancie układu współrzędnych w R

3

i określonego równaniami (1.11) dla

t ∈ [0, 2].

Przykład 6. Rozważmy jedno równanie z trzema niewiadomymi:

x

1

− 2x

2

+ 3x

3

= 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 x

1

, x

2

i x

3

. Dostajemy więc rozwiązania bazowe:

X

1

= (6, 0, 0),

X

2

= (0, −3, 0),

X

3

= (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łaszyźnie Π, który jest

ograniczony odcinkiem o końcach X

1

i X

3

(leżącym w płaszczyźnie Ox

1

x

2

) i półprostymi

o kierunkach wyznaczonych przez wektory

−−−→

X

2

X

3

,

−−−→

X

2

X

1

, których punktami początkowymi

są X

3

oraz X

1

odpowiednio (sporządź 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 R

n

. Część wspólna zbioru S i pierwszego

ortantu układu współrzędnych:

{(x

1

, x

2

, . . . , x

n

) ∈ R

n

: ∀

i=1, 2, ..., n

x

i

­ 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