UKŁADY RÓWNAŃ I NIERÓWNOŚCI LINIOWYCH

UKŁADY RÓWNAN LINIOWYCH

Układ m równań liniowych o n niewiadomych
ma następująca postać:

Macierz A nazywamy macierzą współczynników przy niewiadomych lub macierzą układu równań liniowych; wektor x nazywamy wektorem niewiadomych, a wektor b wektorem wyrazów wolnych.

Postać macierzowa układu równań liniowych :

Jeżeli n=m to detA nazywamy wyznacznikiem układu równań liniowych.

Rozwiązaniem układu równań liniowych Ax=b jest każdy wektor
, którego współrzędne spełniają wszystkie równania tego układu.

Podział układów ze względu na postać wektora b:

1. układy jednorodne, czyli takie, w których wszystkie elementy wektora b są równe 0

2. układy niejednorodne, czyli takie, w których przynajmniej jeden element wektora b jest różny od 0

Rozwiązanie zerowe układu równań dla układu jednorodnego nazwane jest rozwiązaniem trywialnym.

Podział ze względu na liczbę rozwiązań:

1. układy oznaczone - posiadające jedno rozwiązanie

2. układy nieoznaczone - posiadające nieskończenie wiele rozwiązań

3. układy sprzeczne - nie posiadające żadnego rozwiązania

Dwa układy równań liniowych nazywamy układami równoważnymi, jeżeli każde rozwiązanie jednego układu jest jednocześnie rozwiązaniem drugiego układu i odwrotnie.

METODY ROZWIĄZYWANIA

I. Układ Cramera

Układ równań liniowych Ax=b nazywamy układem Cramera wtedy i tylko wtedy gdy:

1. ilość równań w układzie jest równa ilości niewiadomych

2. macierz A tego układu jest macierzą nieosobliwą

1. metoda za pomocą macierzy odwrotnej : Ax=b

2. wzory Cramera

Twierdzenie: jeżeli układ równań liniowych jest układem Cramera to posiada rozwiązanie wyrażone wzorami nazywanymi wzorami Cramera

,
, ...,

(j=1,2,...,n) - jest wyznacznikiem macierzy powstałej z macierzy A w wyniku zastąpienia jej j-tej kolumny kolumną wyrazów wolnych

II. Z twierdzenia Kroneckera Capellego

Macierz uzupełniona powstaje przez dołączenie do macierzy A kolumny wyrazów wolnych b

Twierdzenie Kroneckera - Capellego

Układ równań liniowych Ax=b nie jest układem sprzecznym wtedy i tylko wtedy gdy rzA=rzU ; przy czym jeżeli rzA=rzU=n to układ jest układem oznaczonym, a jeżeli rzA=rzU<n to układ jest układem nieoznaczonym.

Wniosek: jeżeli
to układ jest układem sprzecznym.

Układ Ax=b jest rzA=r=rzU. W macierzy A istnieje więc macierz A' stopnia r, której wyznacznik jest różny od zera:

• 
  zredukowany układ równań :
  , który można rozwiązać wzorami Cramera

• 
  przenosimy wszystkie wyrazy, zawierające niewiadome, których współczynniki nie występują w macierzy A' na prawą stronę równania. Otzrymujemy układ
  , gdzie:

Ponieważ
, zatem i ten układ możemy rozwiązać, stosując wzory Cramera i wyznaczyć niewiadome
jako funkcje liniowe niewiadomych
, które nazywamy zmiennymi swobodnymi, gdyż mogą przyjmować dowolne wartości rzeczywiste. Natomiast zmienne
nazywamy zmiennymi bazowymi. Jeżeli zmienne swobodne przyjmują wartości równe zero, to rozwiązanie układu nazywamy rozwiązaniem bazowym. (nieskończenie wiele rozwiązań)

Rozwiązanie bazowe układu równań to rozwiązanie szczególne, które powstaje z ogólnego przez podstawienie pod zmienne niebazowe zer.

III. Metoda Gaussa - Jordana (metoda operacji elementarnych)

Operacje elementarne na macierzy uzupełnionej układu równań:

• pomnożenie dowolnego wiersza macierzy przez dowolną liczbę R różna od 0

• zamienienie kolejnością dwóch dowolnych wierszy

• dodanie do dowolnego wiersza innego wiersza pomnożonego przez dowolną liczbę rzeczywistą

• zamiana kolejnością kolumn ale tylko w obrębie kolumny A (nie ruszać kolumny wyrazów wolnych)

Metoda Gaussa-Jordana rozwiązywania układów równań liniowych polega na:

1. zapisaniu macierzy uzupełnionej układu

2. przeprowadzeniu operacji elementarnych na U w celu sprowadzenia jej do postaci bazowej

3. odczytaniu rozwiązań

Rozwiązuje się układ równań liniowych sprowadzając macierz uzupełnioną do postaci kanonicznej.

UKŁADY NIERÓWNOŚCI LINIOWYCH

Układ m nierówności liniowych o n niewiadomych ma postać:

Możemy zapisać :

Rozwiązaniem układu nierówności jest każdy punkt przestrzeni
(wektor i n współrzędnych), którego współrzędne spełniają jednocześnie wszystkie nierówności tego układu. Zbiór takich punktów (wektorów) nazywamy zbiorem rozwiązań układu nierówności liniowych.

Układ nierówności liniowych nazywamy sprzecznym, jeżeli zbiór rozwiązań tego układu jest zbiorem pustym, w przeciwnym wypadku układ nazywamy układem nieoznaczonym.

Każdemu rozwiązaniu
układu nierówności odpowiada określone rozwiązanie
układu równań, przy czym wszystkie z
0.

Układ równań :

Postaci bazowe:

,
,

Twierdzenie 1:

Jeżeli macierz uzupełnioną układu równań, która odpowiada układowi nierówności sprowadzimy do postaci bazowej 1 to układ nierówności nie będzie sprzeczny.

Twierdzenie 2:

Jeżeli macierz uzupełniona układu równań, który odpowiada układowi nierówności sprowadzimy do postaci bazowej 2 lub 3 to układ nierówności nie będzie układem sprzecznym wtedy i tylko wtedy, gdy układ równań o macierzy uzupełnionej
będzie posiadał przynajmniej jedno nieujemne rozwiązanie bazowe.

PRZYKŁADY ZASTOSOWAŃ UKŁADÓW DO ROZWIĄZYWANIA ZAGADNIEŃ EKONOMICZNYCH

Zagadnienie żywienia

- macierz składników odżywczych

- ile i-tego składnika odżywczego znajduje się w jednostce j-tego artykułu żywnościowego

x - ile jednostek danego artykułu spożywczego spożywamy,
, rozwiązanie / dieta dopuszczalna

- ile dostarczyliśmy organizmowi składników odżywczych przy diecie x

b - ile jednostek produktu powinna spożywać osoba

c - ceny jednostek produktów żywieniowych

- koszt całkowity przy diecie x

cx - min przy

- dieta dopuszczalna powinna spełniać ten warunek

- dieta, dla której to wyrażenie jest najmniejsze jest dietą optymalną

Programowanie liniowe

Jeśli zagadnienia programowania liniowego zapisane są jako układ nierówności to jest to postać standardowa. Jeśli warunki ograniczające są w postaci równań to postać kanoniczna.

Decyzja optymalną nazywamy decyzję gospodarczą, która zapewnia uzyskanie maksymalnego efektu.

Twierdzenie:

Jeżeli zagadnienie programowania liniowego w postaci kanonicznej ma rozwiązanie optymalne, to jest ono osiągane dla co najmniej jednego nieujemnego rozwiązania bazowego układu równań algebraicznych.

Twierdzenie to wyznacza procedurę szukania rozwiązań optymalnych:

1. wyznaczamy rozwiązanie ogólne układu równań algebraicznych

2. poszukujemy wszystkich rozwiązań bazowych tego układu

3. wybieramy wszystkie nieujemne rozwiązania bazowe

4. dla każdego nieujemnego rozwiązania bazowego obliczamy wartość funkcji celu i wybieramy z nich największą (lub najmniejszą)

Model przepływów międzygałęziowych Leontiefa

• cała gospodarka podzielona na n gałęzi

• w każdej gałęzi wytwarzany tylko 1 produkt

• 
  - wielkość produkcji i-tej gałęzi

• 
  - część produkcji, która trafia na rynek

• 
  - wielkość produkcji i-tej gałęzi przekazywana do gałęzi j-tej

• 
  - wielkość, która pozostaje w tym dziale

• Bilans gospodarki narodowej :

• techniczny współczynnik produkcji
  określa ile jednostek produktu i-tego działu należy zużyć w j-tym dziale, aby można było wyprodukować jedną jednostkę produktu w tym dziale.

• 
  - współczynnik wewnętrznego zużycia produkcji

• 
  

• macierz technicznych współczynników produkcji:

-
- produkcja globalna i-tego działu - równanie bilansowe produkcji

• równanie bilansowe można więc zapisać:
  układ ten jest warunkiem koniecznym wewnętrznej zgodności planu produkcji. Jeżeli jest on sprzeczny, to plan produkcji jest niewykonalny, czyli gospodarka nie jest samowystarczalna.. Przyjmując:

Układ można zapisać

• 
  - macierz Leontiefa

• 
  - model Leontiefa (układ warunków bilansowych)

• jeżeli macierz Leontiefa nieosobliwa i dane są wielkości produktów końcowych, to wektor produktów globalnych można wyznaczyć :
  

6

---