Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
przy ograniczeniach
:
( )
x
c
x
T
X
x
f
=
∈
max
0
≥
≤
x
b
x
A
dim x=n, dim c=n, dim A =[m x n], dim b
1
=m
1
,
Postać kanoniczna zadania PL
x
c
T
X
x
x =
∈
0
max
{
}
0
,
:
≥
=
=
x
b
Ax
x
X
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
RównowaŜność zadań programowania matematycznego
I Ograniczenie równościowe moŜna
zastąpić dwoma ograniczeniami nierów-
ściowymi
0
)
(
=
±
+ j
n
i
x
x
g
II Ograniczenie nierównościowe moŜna
zastąpić ograniczeniem równościowym ,
wprowadzając zmienną uzupełniającą
III Zmienną wolną moŜna przedstawić
jako róŜnicę dwóch zmiennych nieujemnych
−
⇒
≥
≤
⇒
=
)
(
0
)
(
0
)
(
0
)
(
x
g
x
g
x
g
x
g
i
i
i
i
0
≥
+ j
n
x
R
x
i
∈
−
+
−
=
i
i
i
x
x
x
gdzie:
0
,
0
≥
≥
−
+
i
i
x
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Przykład zadania programowania liniowego
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
5
4
3
2
1
0
0
0
0
1
2
max
x
x
x
x
x
X
x
+
+
+
+
=
∈
x
Postać kanoniczna zadania PL – wprowadzenie zmiennych uzupełniających dla układu m równań
liniowych.
•Liczba zmiennych n=2,
•Liczba ograniczeń m=3.
=
+
+
+
+
=
+
+
+
+
−
=
+
+
+
+
=
21
0
0
2
6
0
0
0
5
0
0
:
5
2
1
4
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
X
Kolumny odpowiadające jednostkowej macierzy bazowej B
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Postać kanoniczna macierzowa zadania PL
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
{
}
0
,
:
≥
=
=
x
b
Ax
x
X
•Liczba zmiennych n=5,
•Liczba ograniczeń m=3.
Kolumny odpowiadające jednostkowej macierzy bazowej B x
3
, x
4
, x
5
x
c
T
X
x
x =
∈
0
max
]
0
,
0
,
0
,
1
,
2
[
]
,
,
,
,
[
5
4
3
2
1
=
=
T
T
c
c
c
c
c
c
T
T
x
x
x
x
x
x
]
,
,
,
,
[
5
4
3
2
1
=
−
=
1
0
0
2
6
0
1
0
1
1
0
0
1
1
1
A
=
21
0
5
b
0
5
4
3
2
1
≥
=
x
x
x
x
x
x
5
4
3
2
1
x
x
x
x
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Podstawowe definicje
Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[A
r
]=rz[A]
to mogą zaistnieć trzy następujące przypadki:
1.
rz[A] = m = n istnieje jedno rozwiązanie układu Ax=b.
2.
rz[A] = n < m istnieje jedno rozwiązanie układu równań, lecz przy tym
(m - n) równań jest zbędnych.
3. rz[A] = m < n istnieje nieskończenie wiele rozwiązań układu Ax=b , jest to
układ nieoznaczony.
Definicja 4.1 macierzy bazowej B
Macierzą bazową B układu równań Ax = b rz[A] = m, n>m nazywamy nieosobliwą
macierz kwadratową o wymiarach (m*m) utworzoną z liniowo-niezaleŜnych kolumn a
j
macierzy A.
Definicja 4.2 rozwiązania bazowego
Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor
x
b
=B
-1
b utworzony ze zmiennych odpowiadających kolumnom a
j
macierzy bazowej B.
Składowe wektora bazowego x
b
są to zmienne bazowe.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Rozwiązania bazowe
]
,
[
N
B
A =
m
B
B
=
≠
dim
,
0
det
]
,
[
N
B
x
x
x =
Definicja 4.3
Rozwiązanie bazowe jest rozwiązaniem bazowym dopuszczalnym zadania programowania
liniowego PL
jeśli wektor x
B
jest nieujemny tzn.
Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej niŜ m dodatnich x
i
.
Definicja 4.4
Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe x
i
są większe od zera.
0
≥
B
x
B- macierz bazowa nieosobliwa
N- macierz niebazowa
- wektor zmiennych bazowych odpowiadających kolumnom macierz B
- wektor zmiennych niebazowych odpowiadających kolumnom macierz N
N
B
x
x
0
]
0
,
[
1
=
=
=
−
N
B
B
x
b
B
x
x
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Extremum zadania programowania liniowego PL
Twierdzenie 4.1
Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.
Definicja 4.5
Punkt x naleŜący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X, jeśli nie moŜe być wyraŜony jako kombinacja liniowa innych punktów zbioru X.
n
R
X ⊂
Twierdzenie 4.2
Rozwiązanie dopuszczalne x zadania programowania liniowego PL jest punktem
wierzchołkowym zbioru rozwiązań dopuszczalnych X wtedy i tylko wtedy gdy
odpowiada mu bazowe rozwiązanie dopuszczalne tzn.:
T
B
x
x
]
0
,
[
=
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Extremum zadania programowania liniowego PL cd.
1
:
R
X
f
→
Twierdzenie 4.3
JeŜeli funkcja , określona na domkniętym i ograniczonym wypukłym
zbiorze , jest ciągła i wypukła, to globalne maximum funkcji f(x) występuje w
punkcie ekstremalnym (bądź punktach) zbioru X.
n
R
X ⊂
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Extremum zadania programowania liniowego PL
cd.
∧
∧
∧
p
x
x
x
.....
,
2
1
Twierdzenie 4.4
1.
Funkcja celu zadania PL przyjmuje wartość maksymalną w punkcie
wierzchołkowym zbioru rozwiązań dopuszczalnych zadania PL.
2. Jeśli funkcja celu zadania PL przyjmuje wartość maksymalną w więcej niŜ jednym
punkcie wierzchołkowym, to ma tą samą wartość dla kaŜdej kombinacji wypukłej
tych punktów.
Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.
Zbiór rozwiązań optymalnych przyjmuje postać:
1
,...,
1
,
0
,
1
1
=
=
≥
=
∑
∑
=
=
∧
∧
p
i
i
i
p
i
i
i
p
i
x
X
λ
λ
λ