Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
max f (x)= cT x
x"X
przy ograniczeniach:
Ax d" b
x e" 0
dim x=n, dim c=n, dim A =[m x n], dim b1=m1,
Postać kanoniczna zadania PL
max x0 = cT x
x"X
X = {x : Ax = b, x e" 0}
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Równowa\
ność zadań programowania matematycznego
I Ograniczenie równościowe mo\
na
gi (x) d" 0
Å„Å‚
zastąpić dwoma ograniczeniami nierów-
gi (x) = 0 Ò!
òÅ‚g (x) e" 0Ò! -gi (x)
ściowymi
i
ół
II Ograniczenie nierównościowe mo\
na
zastąpić ograniczeniem równościowym ,
gi(x) Ä… xn+ j = 0
wprowadzając zmienną uzupełniającą
xn+ j e" 0
III ZmiennÄ… wolnÄ… mo\
na przedstawić
xi " R
jako ró\
nicę dwóch zmiennych nieujemnych
xi = xi+ - xi-
xi+ e" 0, xi- e" 0
gdzie:
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Przykład zadania programowania liniowego
x1 + x2 d" 5
Å„Å‚ üÅ‚
ôÅ‚x
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
max x0 = 2x1 +1x2
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
" Liczba zmiennych n=2,
" Liczba ograniczeń m=3.
Postać kanoniczna zadania PL  wprowadzenie zmiennych uzupełniających dla układu m równań
liniowych.
max x0 = 2x1 +1x2 + 0x3 + 0x4 + 0x5
x"X
x1 + x2 + x3 + 0 + 0 = 5
Å„Å‚ üÅ‚
ôÅ‚x ôÅ‚
X = : - x1 + x2 + 0 + x4 + 0 = 0
òÅ‚ żł
ôÅ‚
6x1 + 2x2 + 0 + 0 + x5 = 21ôÅ‚
ół þÅ‚
Kolumny odpowiadajÄ…ce jednostkowej macierzy bazowej B
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Postać kanoniczna macierzowa zadania PL
x1 + x2 d" 5
Å„Å‚ üÅ‚
ôÅ‚x
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
max x0 = 2x1 +1x2
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
" Liczba zmiennych n=5,
" Liczba ograniczeń m=3.
xT =[x1,x2,x3,x4,x5]T
cT =[c1,c2,c3,c4,c5]T =[2,1, 0, 0, 0]
max x0 = cT x
x"X
X = {x : Ax = b, x e" 0}
x1
îÅ‚ Å‚Å‚
ïÅ‚x śł
5
îÅ‚ Å‚Å‚
1 1 1 0 0
îÅ‚ Å‚Å‚ 2
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚-1 1 0 1 0śł
ïÅ‚ śł
b = 0 x = x3 e" 0
A =
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚
4
ïÅ‚x śł
ïÅ‚ śł
ûÅ‚
6 2 0 0 1ûÅ‚ ðÅ‚21śł
ðÅ‚
ïÅ‚x5 śł
ðÅ‚ ûÅ‚
x1 x2 x3 x4 x5
Kolumny odpowiadajÄ…ce jednostkowej macierzy bazowej B x3, x4, x5
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Podstawowe definicje
Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[Ar]=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 aj
macierzy A.
Definicja 4.2 rozwiÄ…zania bazowego
Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor
xb=B-1b utworzony ze zmiennych odpowiadajÄ…cych kolumnom aj macierzy bazowej B.
Składowe wektora bazowego xb są to zmienne bazowe.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
RozwiÄ…zania bazowe
B- macierz bazowa nieosobliwa
A = [B, N]
det B `" 0, dim B = m
N- macierz niebazowa
xB - wektor zmiennych bazowych odpowiadajÄ…cych kolumnom macierz B
x = [xB , xN ]
xN - wektor zmiennych niebazowych odpowiadajÄ…cych kolumnom macierz N
Definicja 4.3
RozwiÄ…zanie bazowe jest rozwiÄ…zaniem bazowym dopuszczalnym zadania programowania
liniowego PL
xB e" 0
jeśli wektor xB jest nieujemny tzn.
Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej ni\
m dodatnich xi.
x = [xB ,0] xB = B-1b xN = 0
Definicja 4.4
Niezdegenerowanym rozwiÄ…zaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe xi
są większe od zera.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL
Definicja 4.5
X ‚" Rn
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.
Twierdzenie 4.1
Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.
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.:
x = [xB,0]T
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL cd.
Twierdzenie 4.3
f : X R1
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
X ‚" Rn
punkcie ekstremalnym (bÄ…dz
punktach) zbioru X.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL cd.
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.
'" '" '"
p
Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.
x1, x2 .....x
Zbiór rozwiązań optymalnych przyjmuje postać:
p p
'"
'"
X = xi , i e" 0,i =1,..., p
i i
" " =1
i=1 i=1
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic