J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 1
WSTP
Optymalizacja = wybór najlepszego spośród dopuszczalnych rozwiązao (wariantów).
Rozwiązanie dopuszczalne = rozwiązanie spełniające przyjęte warunki ograniczenia,
Rozwiązanie najlepsze = rozwiązanie, dla którego przyjęte kryterium wyboru funkcja celu ma
ekstremum.
ZADANIE OPTYMALIZACJI
rozwiązywany problem da się opisad w sposób sformalizowany za pomocą tzw. modelu
matematycznego,
cechy problemu, których wartości należy wyznaczyd, są uporządkowad w formie wektora
x1,L,xi,K,xn łT
x =
zmiennych decyzyjnych należącego do przestrzeni stanu, tzn.
ęś
x Rn ,
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 2
możliwe są tylko takie wektory , które należą do zbioru dopuszczalnego x F, okre-
x
ślonego za pomocą układu ograniczeo gj x Ł 0, j = 1,K,m, tzn.
( )
F = x : gj x Ł 0, j = 1,K,m , przy czym F zawiera więcej niż jeden wektor ,
x
( )
{ }
Ć
rozwiązywaniem zadania wektorem optymalnym x jest ten spośród dopuszczalnych
wektorów x F, dla którego funkcja celu kryterium wyboru osiąga ekstremum
Q x ext .
( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 3
MATEMATYCZNY SENS ZADANIA OPTYMALIZACJI
Ć
Q x ma minimum lokalne w x, jeśli
( )
Ć
"x U, Q x Ł Q x , gdzie U Rn jest
( ) ( )
Ć
otoczeniem x.
Ć
Q x ma minimum globalne w x, jeśli
( )
Ć
"x Rn, Q x ŁQ x .
( ) ( )
Q x ma warunkowe minimum globalne w
( )
Ć Ć
x F, jeśli "x F, Q x Ł Q x .
( ) ( )
Wniosek:
Zadanie optymalizacji polega na szukaniu wa-
runkowego globalnego minimum funkcji celu.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 4
SYSTEMATYKA ZADAO OPTYMALIZACJI
Z UWAGI NA WYSTPOWANIE OGRANICZEO
ż zadanie z ograniczeniami w którym zmienne decyzyjne muszą przyjmowad wartości nale-
żące do zbioru dopuszczalnego,
ż zadanie bez ograniczeo w którym zmienne decyzyjne mogą przyjmowad dowolne wartości.
Z UWAGI NA CHARAKTER ZMIENNYCH DECYZYJNYCH
ż zadanie statyczne (parametryczne) które polega na wyznaczeniu wartości zmiennych de-
cyzyjnych, dla których funkcja celu osiąga ekstremum,
ż zadanie dynamiczne w którym zmienne decyzyjne zadania są funkcjami tej samej innej
zmiennej (np. czasu), zatem poszukiwad będziemy ekstremum pewnego funkcjonału.
Z UWAGI NA TYP FUNKCJI CELU ORAZ OGRANICZEO
ż zadanie programowania liniowego (optymalizacji liniowej) w którym zarówno funkcja ce-
lu jak i ograniczenia są liniowymi kombinacjami zmiennych decyzyjnych.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 5
ż zadanie programowania nieliniowego (optymalizacji nieliniowej) w którym przynajmniej
jedna spośród funkcji występujących w zadaniu (ograniczenia, funkcja celu) jest nieliniowa
względem zmiennych decyzyjnych.
Z UWAGI NA WARTOŚCI, JAKIE MOG PRZYJMOWAD ZMIENNE DECYZYJNE
ż programowanie w zbiorach ciągłych kiedy to zmienne decyzyjne mogą przyjmowad do-
wolne wartości należące do zbioru dopuszczalnego (np. zbioru liczb rzeczywistych),
ż programowanie w zbiorach dyskretnych kiedy to zmienne decyzyjne muszą przyjmowad
tylko określone wartości (muszą należed do zbioru dyskretnego).
Z UWAGI NA LICZB FUNKCJI CELU
ż programowanie jednokryterialne w którym optymalizacja przebiega w oparciu o jedną
funkcję celu (kryterium),
ż programowanie wielokryterialne w którym występuje wiele funkcji celu (kryteriów) a
optymalizacja przebiega z uwzględnieniem ich wszystkich jednocześnie.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 6
RÓŻNICE POMIDZY POSZCZEGÓLNYMI RODZAJAMI ZADANIA OPTYMALIZACJI
POWODUJ, IŻ NIE MA JEDNEJ EFEKTYWNEJ METODY ROZWIZYWANIA WSZYSTKICH
JEGO RODZAJÓW. POSZCZEGÓLNE RODZAJE ZADANIA ROZWIZUJE SI ZA POMOC
WYSPECJALIZOWANYCH METOD (ALGORYTMÓW) ODPOWIEDNICH DLA KAŻDEGO
RODZAJU.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 7
PROGRAMOWANIE LINIOWE
WPROWADZENIE DO PROGRAMOWANIA LINIOWEGO
PRZESTRZENIE LINIOWE, ZBIORY WYPUKLE
Elementami tworzącymi
n-wymiarową unormowaną przestrzeo Euklidesową Rn są punkty
(wektory) będące uporządkowanymi zbiorami liczb rzeczywistych (współrzędnych) xi R,
które można przedstawid w formie jednokolumnowej macierzy (wektora):
x1 ł
ę ś
ę ś
M
ę ś
ęx ś
x
x = = K xi Kxn łT x Rn (1.1)
i
ę ś 1
ęś
ę ś
M
ę ś
ęx ś
ę ś
n
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 8
Liniową kombinacją wektorów jest wyrażenie:
k
a1x1 + K+ aixi + K+ akxk = (1.2)
a xi ai R, xi Rn
i
i=1
Hiperpłaszczyzną w przestrzeni Rn nazywamy zbiór punktów x Rn takich, że:
x : aT x = b (1.3)
W przestrzeni dwuwymiarowej równanie (1.3) jest równaniem prostej a1x1 +a2x2 = b,
a w przestrzeni trójwymiarowej równaniem płaszczyzny a1x1 +a2x2 +a3x3 = b.
Zastępując znak równości w wyrażeniu (1.3) znakiem nierówności, otrzymamy półprzestrzeo
domkniętą w przestrzeni Rn :
{ }
x : aTx Ł b (1.4)
lub półprzestrzeo otwartą w przestrzeni Rn :
{x : aTx < b} (1.5)
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 9
Zbiór równao liniowych (1.3) tworzy układ równao:
a11x1 + L +a1ixi + L +a1nxn = b1
MM
aj1x1 + L +ajixi + L +ajnxn = bj
(1.6)
MM
am1x1 + L +amixi + L +amnxn = bm
którego rozwiązaniem jest przecięcie hiperpłaszczyzn:
m
aj1x1 + K+ ajixi + K+ ajnxn = bj dla j = 1Km
jeżeli dla każdego j co najmniej jedna z liczb aji ą 0.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 10
Podobnie zbiór nierówności (1.5) tworzy układ nierówności:
a11x1 + L +a1ixi + L +a1nxn Ł b1
MM
aj1x1 + L +ajixi + L +ajnxn Ł bj
(1.7)
MM
am1x1 + L +amixi + L +amnxn Ł bm
Rozwiązaniem każdej z nierówności aj1x1 +K+ajixi +K+ajnxn Ł bj jest półprze-
strzeo domknięta, jeśli co najmniej jedna z liczb aji ą 0.
a Kaji Kajn ł jest wektorem normalnym do hiperpłaszczyzny
Wektor aT =
j ęś
j1
aj1x1 +K+ajixi +K+ajnxn = bj.
Zbiór rozwiązao układu nierówności (1.7), będący częścią wspólną półprzestrzeni domkniętych
aj1x1 +K+ajixi +K+ajnxn Ł bj tworzy wielościan wypukły FRn .
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 11
a2
a
j
a1
x0
x:aTx0 łbj
j
a3
F
x:aTx0 =bj
j
a4
x:aTx0 Łbj
j
a5
Półprzestrzenie i hiperpłaszczyzna wyznaczo-
Wielościan wypukły część wspólna półprze-
ne przez punkt i wektor normalny
strzeni domkniętych
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 12
Wprowadzając oznaczenia:
aT ł
a11 L a1i L a1n ł b1 ł
1
ę ś
ę ś ę ś
ę ś
ę ś ę ś
M
M M M
ę ś
ę ś ę ś
ęa ęb ś
Ał
L aji L ajn ś ęaT ś
= = b =
ę ś
j1 j
ę ś j
ę ś ę ś
ę ś
ę ś ę ś
M M M
M
ę ś
ę ś ę ś
ęa ęb ś
L ami L amn ś ę ś
ęaT ś
ę m1 ś ę ś
m
m
liniowe układy równao (1.6) i nierówności (1.7) można zapisad w postaci macierzowej:
Ał
x = b (1.8)
ę ś
Ał
x Ł b (1.9)
ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 13
EKSTREMUM WARUNKOWE FUNKCJI LINIOWEJ
Ał
Rozpatrzymy układ nierówności x Ł b, którego zbiorem rozwiązao jest wielościan wypu-
ę ś
kły Ś oraz liniową funkcję:
c1
Q x = cT x gdzie cT = Kci Kcn ł (1.10)
( )
ęś
Funkcja Q x ma ekstremum warunkowe w zbiorze określonym układem nierówności
( )
Ał
F = x : x Ł b w wierzchołkach wielościanu wypukłego F.
{ }
ę ś
To stwierdzenie ma również duże znaczenie praktyczne w rozwiązywaniu zadao programowa-
nia liniowego. Zadanie poszukiwania ekstremum warunkowego w zbiorze rozwiązao F spro-
wadza się bowiem do przeszukania skooczonego zbioru wierzchołków tego zbioru.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 14
POSTAD OGÓLNA, STANDARDOWA I KANONICZNA ZADANIA PROGRAMOWANIA LINIOWEGO
Terminologia i notacja:
aT ł
x1 ł a11 L a1i L a1n ł
1
ę ś
ę ś ę ś
ę ś
ę ś ę ś
M
M M M
ę ś
ę ś ę ś
ęx ś ęa
Ał
L aji L ajn ś ęaT ś
x = = =
ę ś
i j1
ę ś j
ę ś ę ś
ę ś
ę ś ę ś
M M M
M
ę ś
ę ś ę ś
ęx ś ęa
L ami L amn ś ęaT ś
ę ś
ę ś ę ś
n m1
m
wektor zmiennych macierz współczynników
decyzyjnych
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 15
b1 ł c1 ł
ę ś ę ś
Ł
ę ś ę ś
MM
aTx bj ograniczenie
ę ś ę ś
j
ł
ęb ś ęc ś
b = c =
ji
ę ś ę ś
n
ę ś ę ś
MM
Q x = cTx =i
( )
c xi funkcja celu
ę ś ę ś
i=1
ęb ś ęc ś
ę ś ę ś
mn
wektor prawych wektor funkcji
stron ograniczeń celu (kosztów)
Ał
Zbiór F = x : x Ł b,x ł 0 - zbiór dopuszczalny.
{ }
ę ś
*
x*
Punkt x* F, x*T = Kxi* Kxn ł - rozwiązanie dopuszczalne.
1
ęś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 16
Ć Ć
Rozwiązanie dopuszczalne x, dla którego funkcja celu Q x = ext (osiąga wartośd ekstre-
( )
Ć
malną), jest rozwiązaniem optymalnym zadania, a wartośd Q x optymalną wartością zada-
( )
nia.
POSTAD OGÓLNA ZADANIA PROGRAMOWANIA LINIOWEGO
Zadanie:
Q x = cT x min
( )
(1.11)
Ał
x Ł b x ł 0
ę ś
określamy mianem postaci ogólnej zadania programowania liniowego.
Ograniczenie równościowe może byd zastąpione układem ograniczeo nierównościowych:
aT x Ł bj
j
aT x = bj (1.12)
T
j
j
a x ł bj
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 17
Również zadanie poszukiwania maksimum funkcji celu można zastąpid zadaniem poszukiwania
minimum:
Q x = cT x max -Q x = -cT x min (1.13)
( ) ( )
POSTAD STANDARDOWA ZADANIA PROGRAMOWANIA LINIOWEGO
Każdą z nierówności:
aT x Ł bj aj1x1 +L+ajixi + L+ajnxn Ł bj
j
można zastąpid równością:
aT x + xn+1 = bj aj1x1 + L+ajixi + L+ajnxn + xn+1 = bj (1.14)
j
xn+1 ł 0
dodając po lewej stronie zmienną uzupełniającą .
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 18
Jeśli nierównośd ma zwrot przeciwny:
aT x ł bj aj1x1 +L+ajixi + L+ajnxn ł bj
j
zmienną uzupełniająca należy odjąd:
aT x - xn+1 = bj aj1x1 +L+ajixi +L+ajnxn - xn+1 = bj (1.15)
j
Zastępując wszystkie ograniczenia nierównościowe w zadaniu ograniczeniami równościowymi,
można sprowadzid zadanie programowania liniowego do postaci standardowej:
Q x = cT x min
( )
(1.16)
Ał
x = b x ł 0
ę ś
Sprowadzając zadanie programowania liniowego z postaci ogólnej do standardowej, zwiększy-
liśmy wymiar zadania dodając zmiennych uzupełniających.
m
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 19
Postad ogólna:
a11x1 + L +a1ixi + L +a1nxn Ł b1
MM
aj1x1 + L +ajixi + L +ajnxn Ł bj
MM
am1x1 + L +amixi + L +amnxn Ł bm
Postad standardowa:
a11x1 + L +a1ixi + L +a1nxn + xn+1 = b1
M M M
aj1x1 + L +ajixi + L +ajnxn + L +xn+j = bj
M M M
am1x1 + L +amixi + L +amnxn + L L+ xn+m = bm
(1.17)
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 20
lub po wprowadzeniu dodatkowych oznaczeo:
x Kxn+j Kxn+m łT
Ał Nł Ił Bł x1
= = xN = Kxi Kxn łT xB =
ę ś ę ś ę ś ę ś ę ś
n+1
ęś
w postaci macierzowej:
xN ł
ę ś
Nł Bł N,Bł
xN + xB = b = b (1.18)
ę ś ę ś ę ś
ęx ś
B
ę ś
Wtedy funkcja celu przyjmie postad:
xN ł
ę ś
cN ,cB łT
(x)
Q (1.19)
= = cT xN + cT xB
ęś
N B
ęx ś
B
ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 21
POSTAD KANONICZNA ZADANIA PROGRAMOWANIA LINIOWEGO
Przekształcając zadanie programowania liniowego z postaci ogólnej do standardowej, otrzy-
Bł Ił.
muje się macierz =
ę ś ę ś
Ał można wyodrębnid kwadratową n
Zadanie, w którym w macierzy współczynników
ę ś
-wymiarową podmacierz jednostkową, nazywamy kanoniczną postacią zadania programowa-
nia liniowego.
Jeśli jednak ograniczenia w zadaniu mają formę równości, to zastępowanie ich nierównościami
postad ogólna, którą dalej sprowadza się do postaci standardowej, jest niecelowe, bowiem
przez wprowadzanie zmiennych uzupełniających powiększa się wymiar zadania. Układ ograni-
czeo nierównościowych może byd sprowadzony do postaci kanonicznej bezpośrednio, eliminu-
jąc zmienne xi ze wszystkich równao układu (eliminacja Gaussa).
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 22
ROZWIZYWANIE ZADANIA PROGRAMOWANIA LINIOWEGO
Jeżeli rozwiązanie jest jednoznaczne, to leży w jednym z wierzchołków wielościanu wypukłego
(zbioru dopuszczalnego) F. Zatem należy przeszukad skooczony zbioru wierzchołków i wybrad
ten, w którym funkcja celu ma najmniejszą wartośd.
Przykład
Q x1,x2 = x1 + 2x2 max
( )
2x1 - x2 Ł 2
-x1 + 4x2 Ł 6 x1,x2 ł 0
Sprowadzmy zadanie do postaci standardowej:
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 23
-Q x = -x1 - 2x2 min
( )
2x1 - x2 + x3 = 2
-x1 + 4x2 + x4 = 6 x1,x2,x3,x4 ł 0
1 Dla x1 = x2 = 0 x3 = 2 x4 = 6 -Q x1 = 0
( )
przy czym x1,x2,x3,x4 ł 0,
0ł
ę ś
zatem x1 =
ę0ś jest rozwiązaniem dopuszczalnym.
ę ś
x1
Rozwiązanie możemy poprawid wtedy, gdy znajdziemy inne wierzchołki zbioru Ś, w któ-
rych -Q xi < -Q x1 .
( ) ( )
x1 = x3 = 0
2 Dla x2 = -2 x4 = 14
punkt nie jest rozwiązaniem dopuszczalnym, gdyż x2 < 0.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 24
37
3 Dla x1 = x4 = 0 x2 = x3 = -Q x2 = -3
( )
22
przy czym x1,x2,x3,x4 ł 0,
0ł
ę ś
ę3ś
zatem x2 = jest rozwiązaniem dopuszczalnym.
ę ś
ę2ś
4 Dla x2 = x3 = 0 x1 = 1 x4 = 7 -Q x3 = -1
( )
przy czym x1,x2,x3,x4 ł 0,
1ł
ę ś
zatem x3 =
( ) ( )
ę0ś jest rozwiązaniem dopuszczalnym, lecz -Q x3 > -Q x2 .
ę ś
x2 = x4 = 0
5 Dla x1 = -6 x3 = 14
punkt nie jest rozwiązaniem dopuszczalnym, gdyż x1 < 0,
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 25
6 Dla x3 = x4 = 0 x1 = 2 x2 = 2 -Q x4 = -6
( )
przy czym x1,x2,x3,x4 ł 0,
x2
Q x =6
( )
Ć
x4 =x
2ł
2
ę ś
zatem x4 =
ę2ś jest rozwiązaniem opty-
3
ę ś
2
x2
malnym, bo Q x4 = min .
( ) ( )
{Q xi }
1
Ć
Ostatecznie: Q x = Q 2,2 = 6.
( ) ( )
1
2
Wnioski:
x1
x3
0
kolejnośd sprawdzania ma wpływ na to, w
x1
1
3
1
2
2
2
którym kroku uzyskamy rozwiązanie,
Graficzne rozwiązanie przykładu
od wartości współczynników funkcji Q x
( )
zależy, jaki wpływ mają odpowiadające im zmienne na wartośd Q x .
( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 26
ALGORYTM SYMPLEKS
Zrewidowany algorytm sympleks - jedna z odmian podstawowej wersji algorytmu.
Rozwiązaniem zadania jest jeden z wierzchołków zbioru dopuszczalnego F, lecz nie potrafimy
ich wszystkich wyznaczyd.
Rozpatrzymy zadanie:
Q x = cT x min
( )
Ał
x = b x ł 0
ę ś
Rozwiązanie zaczniemy od przekształcenia zadania do postaci kanonicznej:
xN ł
ę ś
Ał Nł Bł N,Bł
x = b xN + xB = b = b (1.20)
ę ś ę ś ę ś ę ś
ęx ś
B
ę ś
Bł jest macierzą jednostkową a o wektorze prawych stron b założymy, że jest nie-
Macierz
ę ś
Bł Ił, b ł 0).
ujemny ( =
ę ś ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 27
ETAP 1: ZNAJDOWANIE BAZOWEGO ROZWIZANIA DOPUSZCZALNEGO
Przyjmijmy: xN = 0
Rozwiązaniami pozostałego układu
Bł
xB = b
ę ś
Bł.
Są wierzchołki zbioru dopuszczalnego opowiadającego bazie
ę ś
Zbiór (obszar) wyznaczony przez te wierzchołki (wielościan wypukły) nazywamy symlpeksem.
Bł-1 b
x0 = xB = (1.21)
ę ś
Bł jest nieosobliwa a rozwiązanie bazowe jest nieujemne xB ł 0, to jest to
1)
Jeżeli macierz
ę ś
bazowe rozwiązanie dopuszczalne.
1)
Macierz kwadratowa n n, której wszystkie wyznaczniki główne (minory) są różne od zera jest macierzą nieosobliwą.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 28
ETAP 2: POPRAWA BAZOWEGO ROZWIZANIA DOPUSZCZALNEGO
Dotychczasowe rozwiązanie xB daje wartośd funkcji celu:
xB ł
ę ś
cB,cN łT
Q x0 = cT x0 = = cT xB (1.22)
( )
ęś
B
ę ś
0
ę ś
n- elementowy zbiór wierzchołków wielościanu wypukłego F, jest liczniejszy niż
n -m-
elementowy zbiór wierzchołków sympleksu, którego wierzchołki są bazowymi rozwiązaniami
dopuszczalnymi.
Pomysł:
Zamiast przeszukiwad kolejne wierzchołki zbioruF, w celu znalezienia tego, w którym funkcja
celu ma minimum, można wybierad po jednym spośród tych , które dotąd nie były wierzchoł-
kami sympleksu i zastępowad nimi dotychczasowe wierzchołki. Przy każda zamiana powinna
poprawiad (zmniejszad) wartośd funkcji celu.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 29
Realizacja:
Trzeba odpowiedzied na dwa pytania:
1którym z wierzchołków wielościanu F powinniśmy z najlepszym skutkiem zastąpid jeden z
dotychczasowych wierzchołków sympleksu?
(inaczej dokonad wyboru zmiennej niebazowej wprowadzanej do bazy),
2 który z wierzchołków sympleksu powinien byd z najlepszym skutkiem zastąpiony przez je-
den z wierzchołków wielościanuF?
(inaczej wybór zmiennej bazowej wyprowadzanej z bazy).
1 WYBÓR ZMIENNEJ NIEBAZOWEJ WPROWADZANEJ DO BAZY
Należy wybrad ten wierzchołek, który najbardziej zmniejsza wartośd funkcji Q x .
( )
Z (1.20) mamy:
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 30
Bł-1 b - Bł-1 Nł
xB = xN
ę ś ę ś ę ś
Bł-1 Nł
Q x = cT xB + cT xN = cT Bł-1 b - xN + cT xN =
( )
{ ę ś ę ś }
ę ś
B N B N
(1.23)
= cT Bł-1 b + cT - cT Bł-1 Nł xN = q + pT xN
}
ę ś { ę ś ę ś
B N B
gdzie: q = cT Bł-1 b
, (1.24)
ę ś
B
pT = cT - cT Bł-1 Nł = cT - T Nł, (1.25)
ę ś ę ś ę ś
N B N
wektor mnożników sympleksowych.
Równanie (1.23) wyraża funkcję celu zależną tylko od zmiennych niebazowych xN . Wartośd
Q x = Q xN zależy zatem od wektora p, bowiem xN ł 0. Rozwiązanie można popra-
( ) ( )
wid (zmniejszyd dotychczasową wartośd funkcji celu), jeżeli wśród składowych wektora p są
składowe ujemne.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 31
I. p > 0,
Wszystkie składowe wektora p są dodatnie, nie można zmniejszyd wartości Q x , do-
( )
Ć
tychczasowe rozwiązanie jest rozwiązaniem optymalnym x = xB.
II. pk = 0,
W wektorze p istnieje zerowa składowa o indeksie k , rozwiązanie jest niejednoznaczne,
)
2
przechodząc do następnego wierzchołka nie zmieniamy wartości Q x .
( )
III. pk < 0,
W wektorze p istnieje co najmniej jedna ujemna składowa pk , można zmniejszyd wartośd
Q x przechodząc do następnego wierzchołka. Jeśli składowych ujemnych jest więcej,
( )
wybieramy najmniejszą z nich.
2)
Istnieje niebezpieczeostwo powstania cyklu polegającego na powrocie do tego samego wierzchołka po pewnej liczbie iteracji.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 32
Nł wybieramy kolumnę ak i wprowa-
Spośród 1 Ł k Ł (n - m) kolumn podmacierzy
ę ś
Bł w następnej iteracji. Jest to równoważne wybraniu jednego z wierz-
dzamy ją do bazy
ę ś
chołków wielościanuF, którym zostanie zastąpiony jeden z dotychczasowych wierzchołków
sympleksu.
2 WYBÓR ZMIENNEJ BAZOWEJ WYPROWADZANEJ Z BAZY
Zamiana wierzchołków powinna przynieśd jak największą poprawę (zmniejszenie) wartości
Q x . Nowe rozwiązanie bazowe powinno byd dopuszczalne xB ł 0.
( )
Bł-1 b - Bł-1 akxk ł 0
xB = (1.26)
ę ś ę ś
N
0
Bł-1 b = xB bieżące rozwiązanie bazowe, Bł-1 ak = d,
Oznaczając:
ę ś ę ś
0
mamy: xB = xB - dxk
N
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 33
Jeżeli d > 0, to zwiększenie xk powoduje zmniejszenie xB , co pociąga zmniejszenie funkcji
N
celu.
Indeks l kolumny wyprowadzanej z bazy to ten, dla którego
x0
(n - m) + 1 Ł l Ł n zachodzi min Bl przy dl > 0.
ż
dl
0
Kolumna bazy odpowiadające zmiennej xBl jest wyprowadzana z bazy do części niebazowej.
W przeciwnym przypadku wartośd funkcji celu może byd pomniejszona do , czyli że zbiór
-Ą
bazowych rozwiązao dopuszczalnych jest nieograniczony .
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 34
PRZYKAAD
Q x1,x2 = -x1 - 2x2 min
( )
2x1 - x2 + x3 = 2
-x1 + 4x2 + x4 = 6 x1,x2,x3,x4 ł 0
Iteracja 1:
x1 x2 x3 x4 x1 x2 x3 x4
2 -1 1 0ł b = 2ł cT =
Ał
ę ę6ś
=
ę ś
ę-1 -2 0 0ł
ś
ę-1 4 0 1ś ę ś
ś
Nł Bł
cT cT
ę ś ę ś NB
0ł
x1
ę ś
ę0ś
2ł
0 0
ę ś
Bł-1 b= Ił-1 b= x1 xB >0 x0 = ę ś x2 Q x0 = -1 0-20=0
xB =
( )
( )
ę ś ę ś
ę2ś
ę6ś
x2 x3
ę ś
ę ś
ę6ś
x4
ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 35
2 -1ł
ęś
Ił
pI = cT -cT Bł-1 Nł = =
N B ę ś ę ś ę ś
ę-1 -2ł-0 0ł
ś ę ś
ę
ę-1 4ś
ś
x1 x2
= k =2
ę-1 -2ł
ś
-1ł -1ł
ę ś ę ś
Bł-1 ak = Ił
dI = =
ę ś ę ś
ę
4ś ę 4ś
ę ś ę ś
x3 x4
2 6 3
ż x2 x4
min dl >0= l =2
2
-1 4
d1 d2
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 36
x1 x4 x3 x2
0łx1
ę ś
1 7
1 ł 2ł ł
xB ę 3ś x4
2 0 1 -1ł x3
-1
2
ę ś
4
ę ś ę ś ę ś
Ał
xI =
xBI =Bł b= =ę 2ś >0
ę śI = ę śI xN ę7 ś x3
13
ę ę0 ś ę6ś ę ś
2
ę ś
4
ę-1 1 0 4ś ę ś ę ś ę
ś
2ś x4
ę0śx2
ę ś
Nł
ę śI Bł
ę śI
x1 x4 x3 x4
3
cT =ś
0 0 -2ł
Q xI = -1 0 - 2 = -3
( ) ( )
I
ę-1
2
cT cT
NI BI
Iteracja 2:
x4
x1
1ł
1
ę ś
1 ł
1
2ł 7ł
2 0ł
ę- ś
dII =ę 4ś ę ś =ę 4ś
pII =-1 0ł- 0 -2ł ę 4ś ęś= 1 1ł k =1
ę
11
ę ś ę ś
ę0 ś ę ś ę ś
1ś ęś ęś
2 2
ę ś
ę-1 1ś 44
ę ś ę-1ś ę- ś
0
ę
4ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 37
x3 x4
7 3
ż
2 2
min dl >0=2 l =1 x1 x3
7 1
-
4 4
d1 d2
x x x1 x2
3 4
4 1ł
ęś
2ł 2ł
1 0 2 -1ł
x1 >0
ę7 7 ś
ę ś ę ś ę ś
Ał
=
ę1 2 ś
ę śII = 0 1 -1 4ś xBII =
ę ę6ś ę2ś
x2
ęś
ę ś ę ś ę ś
ę7 7 ś
Nł
Bł
ę śII
ę śII
2ł
x3
x1x4
x3
x2
xB ę ś x4
ę2ś
ę ś 0
xII = Q xII = -1 2-22=-6 cT = 0 -1 -2ł
( ) ( )
ę0ś II
ęś
ę ś
xN ę0ś x1
cT cT
N B
x2
ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 38
III iteracja:
4 1ł
ęś
ę7 7ś 1 0ł 6 6ł 0
0 0ł
ęś
pIII = -
ę ś ę-1 -2ł ę1 2ś
ś
ę0 1ś = ęś
ę7 7ś >
ęśś
ę7 7ś ę
Wektor p nie ma ujemnych składowych, rozwiązanie otrzymane w II iteracji jest rozwiązaniem
optymalnym:
2ł
ę ś
ĆĆ
x =
( )
ę2ś, Q x = -6.
ę ś
ODWRACANIE MACIERZY W ALGORYTMIE SYMPLEKS
B* ł różni się od macierzy
Bł z poprzedniej
Zauważmy, że w każdej iteracji macierz bazowa
ę ś
ę ś
iteracji tylko jedną kolumną:
B*ł
Bł a1 Kak Kan ł a1
== Kal Kan ł .
ę ś ę ś ę ś
ę ś
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 39
Bł-1 al = y1 Kyk Kyn łT
Jeśli oznaczyd: to można wykazad, że:
ę ś ę ś
B*ł-1
Eł Bł-1
, gdzie
ę ś ę ś
ę ś=
ł
y1
ęś
10
L - L
ęś
yk
ęś
ęś
M O M M
ęś
ęś
1
Eł
ęś
00
LL
=
ę ś
ęś
yk
ęś
ęś
M M O M
ęś
ęś
yn
ęś
01
L - L
ęś
yk
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd 1: PROGRAMOWANIE LINIOWE 40
Dla macierzy z przykładu
1 0ł 1 -1ł -1ł 0ł
ę ś B*ł ę ś, al = ę ś ę ś
Bł
= i ak =
ę ś
ę ś
ę0 1ś i = ę0 ę ę1ś
4ś 4ś
ę ś ę ś ę ś ę ś
ę1 1ł
ś
1 0ł -1ł
T
ę ś ę ś 4ś
Bł-1 al =
= 4ł B*ł-1 ę
ę ś
ę0 1ś ę
=
4ś ę-1 ś ę ś ęś
ę0 1ś
ę ś ę ś
ę
4ś
Wyszukiwarka
Podobne podstrony:
ekonomietria programowanie liniowe (10 stron),programowanie liniowe, zadania6 2 Zadania programowania liniowegoMOO programowanie liniowe(chyba się przyda!!!)Programowanie linioweProgramowanie liniowe 11 (egzamin termin 2 zestaw 3)Programowanie linioweprogramowanie liniowe teoriaprogramowanie liniowe zadania Jodejkoprogramowanie linioweProgramowanie liniowe 11 (egzamin termin 2 zestaw 2)Programowanie liniowe zagadnienia dualneProgramowanie liniowe optymalizacja13 Projektowanie układów sekwencyjnych procesowo–zależnych o programach liniowych na przykładzie uOpracowanie Programowanie liniowe metoda symplekszestawy cwiczen przygotowane na podstawie programu Mistrz Klawia 6więcej podobnych podstron