Metoda eliminacji Gaussa-Jordana -
zadanie optymalizacji liniowej w postaci standardowej Równania liniowe
I.
x1 + 2 x2 +
x3 = 4
II.
2 x1 −
x2 + 3 x3 = 3
III.
x1 +
x2 −
x3 = 3
• KROK 1. Używamy równania I dla wyelimi-nowania x1 z II i III.
x1 + 2 x2 +
x3 =
4
− 5 x2 +
x3 = −5
−
x2 − 2 x3 = −1
• KROK 2. Dzielimy równanie II przez -5 żeby wspó lczynnik przy x2 by l równy 1
x1 + 2 x2 +
x3 =
4
x2 − 1 x
5
3
=
1
−
x2 − 2 x3 = −1
• KROK 3. Używamy równania II do wylimi-nowania x2 z I i III
x1
+
7
x
5
3
= 2
x2 − 1 x
5
3
= 1
− 11 x
5
3
= 0
• KROK 3. Używamy równania III dla wyelim-inowania x3 z I i II
x1
= 2
x2
= 1
x3 = 0
1
Przyk lad 2 Uk lad nie ma rozwiazań
,
I.
x1 + 2 x2 +
x3 = 4
II.
x1 +
x2 + 2 x3 = 1
III. 2 x1 + 3 x2 + 3 x3 = 2
• KROK 1. Eliminujemy x1 z równań II i III I.
x1 + 2 x2 +
x3 =
4
II.
−
x2 +
x3 = −3
III.
−
x2 +
x3 = −6
• KROK 2. Eliminujemy x2 z równań I i III I.
x1
+ 3 x3 = −2
II.
x2 −
x3 =
3
III.
0
= −3
Przyk lad 3 Uk lad ma nieskończenie wiele rozwiazań
,
I.
x1 + 2 x2 +
x3 = 4
II.
x1 +
x2 + 2 x3 = 1
III. 2 x1 + 3 x2 + 3 x3 = 5
• KROK 1. Eliminujemy x1 z równań II i III I.
x1 + 2 x2 +
x3 =
4
II.
−
x2 +
x3 = −3
III.
−
x2 +
x3 = −3
• KROK 2. Eliminujemy x2 z równań I i III I.
x1
+ 3 x3 = −2
II.
x2 −
x3 =
3
III.
0
=
0
x1
= −2 − 3x3
x2
=
3 + x3
2
Uk lad m równań liniowych z n niewiadomymi a11x1 + a12x2 + ... + a1nxn = b1
...
...
...
...
= ...
am1x1 + an2x2 + ... + amnxn = bm
w postaci macierzowej
a
11
... a1n
x1
b1
...
...
...
.
.
...
...
... . = .
...
...
... .
.
am1 ... amn
xn
bm
Ax = b gdzie A macierz m × n, b wektor m × 1, x wektor n × 1
LUB
a
11
a1n
b1
.
.
.
.
x1 + ... +
.
xn =
.
.
.
.
am1
amn
bm
szukamy wspó lczynników x1, ..., xn takich, że wektor b jest kombinacja liniowa kolumn macierzy A
,
,
3
,
Przyk lad. Rzemieślnik produkuje skórzane paski
’zwyk le’ i ’luksusowe’. Pasek ’luksusowy’ wymaga paska skóry i 2 godzin pracy.
Pasek ’zwyk ly’
wymaga paska skóry i 1 godziny pracy. Dostepnych
,
jest 40 pasków skóry i 60 godzin pracy. Jak wiele pasków kaźdego rodzaju mo że być wyprodukowanych?
w zadaniu wystepuja cztery rodzaje aktywności:
,
,
• x1 - ilość wyprodukowanych pasków ’luksu-sowych’
• x2 - ilość wyprodukowanych pasków ’zwyk lych’
• s1 - ilość pozostawienych pasków skóry w mag-azynie
• s2 - ilość godzin pracy bez wykorzystania Cel:
wyznaczyć wszystkie mo żliwe kombinacje tych czterech rodzajów aktywności tak by otrzymać 40 pasków i 60 godzin:
1
1
1
0
40
x1
+ x
+ s
+ s
=
2
2
1
1
0
2
1
60
Eliminacja Gaussa-Jordana
x1 = 20 + s1 − s2
x2 = 20 − 2s1 + s2
x1, x2 - zmienne bazowe
Czy inne zmienne moga być bazowe - tak, o ile
,
odpowiednie kolumny sa liniowo niezale żne
,
4
Max z = c1x1 + c2x2 + ....cnxn
przy ograniczeniach
a11x1 + a12x2 + .... + a1nxn = b1
.......................
am1x1 + am2x2 + .... + am1xn = bm x1 ≥ 0, x2 ≥ 0, ....xn ≥ 0
• jeśli problem jest min z to zapisujemy max −z
• jeśli wystepuje warunek a
,
1x1 +ai2x2 +...+ainxn ≤
bi to dodajemy nieujemna zmienna os labiajaca
,
,
,
,
si i otrzymujemy a1x1 +ai2x2 +...+ainxn +si = bi, si ≥ 0
• jeśli wystepuje warunek a
,
1x1 +ai2x2 +...+ainxn ≥
bi to dodajemy nieujemna zmienna os labiajaca
,
,
,
,
si i otrzymujemy a1x1 +ai2x2 +...+ainxn −si = bi, si ≥ 0
• jeśli niektóre zmienne nie maja ograniczenia
,
na znak to zastepujemy je wszedzie sformu lowaniem
,
,
x0 − x00 gdzie x0 ≥ 0 i x00 ≥ 0
j
j
j
j
5
,
,
Przyk lad Rozwiazać zadanie
,
max
z = x1 + x2
2x1 + x2 ≤ 4
x1 + 2x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
• KROK 1. Sprowadzenie do postaci standardowej
max
x1
+
x2
2
x1
+
x2
+
x3
= 4
x1
+
2
x2
+
+ x4 = 3
x1 ≥ 0,
x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
• niech z oznacza funkcje celu: z = x
,
1 + x2 lub
równowa żnie z − x1 − x2 = 0
• otrzymujemy:
z −
x1 −
x2
= 0 wiersz 0
2 x1 +
x2 +
x3
= 4
wiersz I
x1 + 2 x2
+ x4 = 3 wiersz II
• Chcemy maksymalizować z tak by spe lnione by ly powy ższe ograniczenia oraz x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
• z wierszy I i II: zmienne bazowe x3 i x4
• KROK 2: rozwiazanie bazowe: k ladziemy zmi-
,
enne niebazowe równe 0 i otrzymujemy x1 = x2 = 0, x3 = 4, x4 = 3, z = 0
6
x1 = x2 = 0, x3 = 4, x4 = 3, z = 0
jest rozwiazaniem optymalnym? Czy mo żemy
,
zwiekszyć z zwiekszajac x
,
,
,
1i x2?
• tak, bo te zmienne maja ujemne wspó lczynniki
,
w wierszu 0. Gdyby wszystkie wspó lczynniki w wierszu zerowym by ly nieujemne to otrzy-mane rozwiazanie by loby optymalne, bo nie
,
moglibyśmy zwiekszyć z zachowujac nieujemność
,
,
zmiennych
• Regu la 1: Jeśli wszystkie zmienne maja nieu-
,
jemne wspó lczynniki w wierszu 0 to otrzy-mane rozwiazanie jest optymalne. W przeci-
,
wnym przypadku wybierz zmienna x
,
j z ujem-
nym wspó lczynnikiem w wierszu 0
• wybrana zmienna nosi nazwe zmiennej wchodzacej
,
,
• KROK 3:wybierzmy x1 jako zmienna wchodzaca
,
,
,
(mo żna te ż wybrać x2)
• Mamy teraz dwie możliwości wyboru elementu g lównego: Wiersz I lub wiersz II. Sprawdźmy obie mo żliwości: Wiersz I
z −
x1 −
x2
= 0 wiersz 0
2 x1 +
x2 +
x3
= 4
wiersz I
x1 + 2 x2
+ x4 = 3 wiersz II
z
− 1 x
x
2
2
+ 12
3
= 2 wiersz 0
x1 + 1 x
x
2
2
+ 12
3
= 2
wiersz I
3
x
x
2
2
− 12
3
+ x4 = 1 wiersz II
7
• otrzymujemy rozwiazanie bazowe: x
,
2 = x3 = 0,
x1 = 2, x4 = 1, z = 2
• druga możliwość: wiersz II
z −
x1 −
x2
= 0 wiersz 0
2 x1 +
x2 +
x3
= 4
wiersz I
x1 + 2 x2
+ x4 = 3 wiersz II
z
+ x2
+
x4
= 3
wiersz 0
− 3 x2 +
x3 − 2 x4 = −2 wiersz I
x1 + 2 x2
+
x4
= 3
wiersz II
• rozwiazanie bazowe: x
,
2 = x4 = 0, x1 = 3, x3 =
−2, z = 0, Niedopuszczalne
• jak można z góry przewidzieć który wiersz wybrać jako g ló wny?
• trzeba porównywać ilorazy:
prawa strona
wspó lczynnik zmiennej wchodzacej
,
• w pierwszym przypadku: 4, w drugim: 3
2
1
• jeśli wybierzemy wiersz z
minimalnym ilo-
razem to otrzymamy zawsze rozwiazanie do-
,
puszczalne
• Regu la 2: Dla każdego wiersza i, i ≥ 1 gdzie jest ściśle dodatni wspó lczynnik przy zmiennej wchodzacej obliczamy ilorazy
,
prawa strona
wspó lczynnik zmiennej wchodzacej
,
i wybieramy MINIMALNY
8
• w naszym przyk ladzie - wybierajac wiersz pier-
,
wszy otrzymaliśmy uk lad
z
− 1 x
x
2
2
+ 12
3
= 2 wiersz 0
x1 + 1 x
x
2
2
+ 12
3
= 2
wiersz I
3
x
x
2
2
− 12
3
+ x4 = 1 wiersz II
z rozwiazaniem bazowym: x
,
3 = x4 = 0, x1 = 2,
x4 = 1, z = 2
• Czy to jest rozwiazanie optymalne? NIE, Regu la
,
1 mówi, że musimy wybrać x2 jako zmienna, wchodzaca
,
,
• obliczamy ilorazy: dla wiersza I: 2 = 4
1/2
• dla wiersza II: 1 = 2
3/2
3
• wybieramy wiersz II i robimy eliminacje,
• mnożymy wiersz II przez 23
z
− 1 x
x
2
2
+ 12
3
= 2 wiersz 0
x1 + 1 x
x
2
2
+ 12
3
= 2
wiersz I
x2 − 1 x
x
wiersz II
3
3
+ 23 4 = 23
z
+ 1 x
x
wiersz 0
3
3
+ 13
4 = 7
3
x1
+ 2 x
x
wiersz I
3
3
− 13
4 = 5
3
x2 − 1 x
x
wiersz II
3
3
+ 23
4 = 2
3
• rozwiazanie bazowe: x
, x
,
,
3 = x4 = 0, x1 = 5
3
2 = 2
3
z = 73
• Regu la 1 mówi, że to jest rozwiazanie opty-
,
malne
9