Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

1

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

0.5

1

1.5

2

2.5

3

0.5

1

1.5

2

2.5

3

4

6

8

10

x

Wykres badanej funkcji

y

Poszukiwanie minimów funkcji wielu zmiennych

Okre lenie zagadnienia

Problem polega na poszukiwaniu minimum funkcji wielu zmiennych. Funkcja mo e by dowolna (tzn. dowolnego rz du,

tak e nieliniowa). Do badania w przykładach wybierzemy nast puj c funkcj (jest to obwód jakiej figury geometrycznej

uzale niony od długo ci dwóch jej boków przy ustalonej warto ci powierzchni całej figury, oznaczymy j przez P(x,y)):

P(x,y)

x

y

1

x y

2

x y

2

x

4

2 x

2

y

2

y

4

4

x y

x

y

Funkcja badana faktycznie ma minimum wynosz ce 2.8284271507 w punkcie x=y=0.7070110163 (s to warto ci

obliczone numerycznie). Podczas ilustrowania działania omawianych dalej metod szukania minimum b d zakłada jako

punkt wyj ciowy punkt o współrz dnych (2.25,3.00).

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

2

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

P(x,y)

x

x y

2

x

4

2 x

2

y

2

y

4

4

x

4

2 x

3

y

2 x y

3

y

4

4

x y

2

x

4

2 x

2

y

2

y

4

4

P(x,y)

y

x y

2

x

4

2 x

2

y

2

y

4

4

x

4

2 x

3

y

2 x y

3

y

4

4

x y

2

x

4

2 x

2

y

2

y

4

4

(czerwona gwiazdka na rysunku oznacza faktyczne poło enie minimum lokalnego).

Znamy analityczne wyra enia na składowe jej gradientu:

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

3

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Jest to do „perfidna” funkcja, wida to dopiero po obejrzeniu jej wykresu dla wi kszego zakresu argumentów — w

zasadzie z faktu, e ma to by obwód figury w funkcji długo ci boków wynika, e x i y musza by dodatnie, jednak podczas

oblicze numerycznych warto ci po rednie zmiennych mog by bardzo ró ne.

Obok przedstawiam wykres tej wła nie funkcji dla wi kszego zakresu zmienno ci argumentów — wida na nim, e

funkcja ma zarówno minimum lokalne jak i maksimum lokalne, ale globalnie minimum d y do – , a maksimum do + .

Metoda połowienia kroku

Metoda jest najprostsz adaptacj metod poznanych dla funkcji jednej zmiennej. Przebieg oblicze jest nast puj cy:

1. Wybieramy punkt startowy (x

o

,y

o

), obliczamy warto P(x

o

,y

o

) i gradient grad(P(x,y)) badanej funkcji w tym punkcie,

2. W kierunku przeciwnym do obliczonego gradientu “wykonujemy krok” o wybranej wcze niej długo ci — obliczamy

nowe współrz dne punktu (x

1

,y

1

) i now warto funkcji P(x

1

,y

1

),

3. Je li nowa warto funkcji jest

mniejsza ni warto z poprzedniego punktu obliczamy jej gradient w tym punkcie

grad(P(x

1

,y

1

)) i wykonujemy nast pny krok (czyli powtarzamy etap 2 powy ej), je li jednak warto funkcji

nie zmalała

to wracamy do poprzedniego punktu, zmniejszamy krok (np. o połow ), i powracamy do etapu 2 — wykonujemy ten

skrócony krok i ponownie sprawdzamy warto funkcji.

Ju na podstawie tego opisu mo emy zauwa y , e je li trafimy wreszcie (by mo e przypadkiem) do minimum to

kolejny krok przeniesie nas dalej — do punktu o wi kszej warto ci funkcji i mo emy powtarza etap 2 w niesko czono

(albo do chwili gdy osi gniemy zadan minimaln długo kroku).

Oto przykładowy przebieg oblicze w metodzie „połowienia kroku”:

cykl 1,

warto funkcji: 6.0912

bł d wzgl.: 1.15357

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

4

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

cykl 2,

warto funkcji: 4.72901

bł d wzgl.: 0.671957

cykl 3,

warto funkcji: 3.69826

bł d wzgl.: 0.307534

w cyklu 4 zmniejszam krok z 1 na 0.5

cykl 4,

warto funkcji: 2.93152

bł d wzgl.: 0.036449

w cyklu 5 zmniejszam krok z 0.5 na 0.25

cykl 5,

warto funkcji: 2.8836

bł d wzgl.: 0.0195064

w cyklu 6 zmniejszam krok z 0.25 na 0.125

cykl 6,

warto funkcji: 2.83676

bł d wzgl.: 0.00294435

w cyklu 7 zmniejszam krok z 0.125 na 0.0625

cykl 7,

warto funkcji: 2.83149

bł d wzgl.: 0.00108422

w cyklu 8 zmniejszam krok z 0.0625 na 0.03125

cykl 8,

warto funkcji: 2.82883

bł d wzgl.: 0.000142345

w cyklu 9 zmniejszam krok z 0.03125 na 0.015625

cykl 9,

warto funkcji: 2.82872

bł d wzgl.: 0.000102758

w cyklu 10 zmniejszam krok z 0.015625 na 0.0078125

w cyklu 10 zmniejszam krok z 0.0078125 na 0.00390625

w cyklu 10 zmniejszam krok z 0.00390625 na 0.00195313

cykl 10,

warto funkcji: 2.82843

bł d wzgl.: 9.56914e –007

Wyniki metody „połowienia kroku”:

współrz dne minimum: x_min=0.708081, y_min=0.708099,

bł dy wzgl. x i y: 0.00151403, 0.00153917

warto funkcji: 2.82843

bł d wzgl.warto ci: 9.56914e-007, warto prawdziwa: 2.82843

warto ci składowych gradientu:

x-owa: 0.00276355,

y-owa: 0.00278872

Ogólnie taka metoda post powania działa do dobrze, jednak je eli mamy pecha i wybierzemy zbyt du warto

pierwszego kroku — mo emy „przeskoczy ” szukane minimum i potem ju tylko oddala si od niego do niesko czono ci

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

5

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

(wybrana funkcja przykładowa ma wła nie tak własno — istnieje dobrze okre lone minimum lokalne , ale w połowie

swej dziedziny funkcja maleje do – ).

Drug wad jest stosunkowo powolna zbie no — je li wybrali my zbyt krótki krok pocz tkowy poszukiwania

minimum mog si bardzo dłu y . Rysunek powy ej pokazuje przebieg poszukiwa minimum t wła nie metod .

Metoda najszybszego spadku (the steepest descent method)

Jest to metoda nieco bardziej skomplikowana — najpierw, jak zwykle, wybieramy punkt startu i obliczamy gradient

badanej funkcji w tym punkcie. Warto ci składowych gradientu okre laj nam lini (maj c kierunek gradientu). Je li

zało ymy, e x i y b d le e na tej wła nie linii to mo emy badan funkcj przekształci do postaci parametrycznej:

x

x

0

P(x,y)

x

t

y

y

0

P(x,y)

y

t

P(x,y)

P x

0

P(x,y)

x

t , y

0

P(x,y)

y

t

Badana funkcja b dzie wtedy funkcj jednej zmiennej i b dziemy mogli zastosowa do niej znane ju nam metody

szukania minimum funkcji jednej zmiennej (jest oczywi cie pewien kłopot — nie b dziemy zna wła ciwych granic

przedziału zmiennej t w jakim powinni my poszukiwa minimum — musimy przyj co „z kapelusza” ). Gdy ju

znajdziemy warto parametru t minimalizuj c badan funkcj to na jej podstawie obliczymy nowe współrz dne x i y.

x

1

x

0

P(x,y)

x

t

min

y

1

y

0

P(x,y)

y

t

min

Operacj t powtarzamy tak długo a zadowol nas warto ci składowych gradientu — w minimum musz oczywi cie

wynosi zero, zatem to na ile ró ni si od zera mo e stanowi pewn „miar odległo ci” od minimum. W metodzie tej nie

zwracamy zbytniej uwagi na zmiany warto ci badanej funkcji — w ka dym cyklu przesuwamy si na inn , trudn do

przewidzenia, odległo .

Przykładowy przebieg oblicze w metodzie „steepest descent”:

cykl: 1,

warto funkcji: 4.51207

bł d wzgl.: 0.595258

cykl: 2,

warto funkcji: 2.97947

bł d wzgl.: 0.0534011

cykl: 3,

warto funkcji: 2.83593

bł d wzgl.: 0.00265193

cykl: 4,

warto funkcji: 2.82944

bł d wzgl.: 0.000357943

cykl: 5,

warto funkcji: 2.82853

bł d wzgl.: 3.72817e –005

cykl: 6,

warto funkcji: 2.82844

bł d wzgl.: 4.22643e –006

cykl: 7,

warto funkcji: 2.82843

bł d wzgl.: 4.57242e –007

cykl: 8,

warto funkcji: 2.82843

bł d wzgl.: 4.26757e –008

cykl: 9,

warto funkcji: 2.82843

bł d wzgl.: –3.42853e –009

cykl: 10,

warto funkcji: 2.82843

bł d wzgl.: –8.53522e –009

Wyniki metody „steepest descent”:

współrz dne: x_min=0.706976, y_min=0.707148,

bł dy wzgl. x i y: –5.01624e –005, 0.000193142,

warto funkcji: 2.82843,

bł d wzgl. warto ci: –3.42853e –009,

warto prawdziwa: 2.82843,

warto ci składowych gradientu:

x-owa: –0.000249537,

y-owa: –6.28107e –006.

Metoda ta mo e by łatwo zaadaptowana do przypadku funkcji o dowolnej liczbie zmiennych — niezale nie od liczby

zmiennych problem zawsze sprowadzamy do poszukiwania minimum funkcji jednej zmiennej (funkcji parametru t).

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

6

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Metoda „rank-one”

Jest to metoda zbli ona do metody najszybszego spadku, jednak oprócz gradientu (czyli pierwszych pochodnych)

wykorzystuje si w niej równie drugie pochodne. Podobnie jak w metodzie najszybszego spadku wybieramy jaki punkt

pocz tkowy i obliczamy w nim warto ci funkcji i jej gradientu. Zakładamy, e istnieje jaki „wła ciwy kierunek”, który

oznaczymy jako (s

1

,s

2

) i wzdłu niego b dziemy zmienia warto ci x i y (w metodzie najszybszego spadku kierunek ten

jednoznacznie wyznaczał nam gradient funkcji):

x

a

t s

1

y

b

t s

2

Zakładamy, e wła nie takie równania parametryczne mo na podstawi do wyra enia na badan funkcj P(x,y) (pomimo

faktu, e kierunków tych na razie nie znamy) po czym rozwijamy j w szereg Taylora (dwuwymiarowy) wokół punktu o

współrz dnych (a,b):

f (x,y)

f (a s

1

t,b s

2

t)

f (a,b)

t s

1

f

x

s

2

f

y

t

2

2

s

2

1

2

f

x

2

2s

1

s

2

2

f

x y

s

2

2

2

f

y

2

Wszystkie pochodne w powy szym wzorze obliczane s w punkcie (a,b). Je li za s

1

i s

2

przyjmiemy warto ci spełniaj ce

nast puj cy układ równa :

s

1

2

f

x

2

s

2

2

f

x y

f

x

s

1

2

f

x y

s

2

2

f

y

2

f

y

to dostaniemy:

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

7

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

f (x,y)

f (a,b)

1
2

t 1

2

1 s

1

2

f

x

2

2s

1

s

2

2

f

x y

s

2

2

2

f

y

2

B dzie zatem zachodzi :

J e

li

|t| < 1

i

s

2

1

2

f

x

2

2s

1

s

2

2

f

x y

s

2

2

2

f

y

2

> 0

to

f(x,y) < f(a,b)

Spełnienie tych warunków jest do łatwe je eli tylko szukaj c kolejnego nie oddalimy si zbytnio od poprzedniego

przybli enia.

Przykładowy przebieg oblicze w metodzie „rank-one”:

cykl: 1,

warto ci: funkcji: -32.0051

bł d wzgl.: –12.3155,

t_min: 0.499999,

cykl: 2,

warto ci: funkcji: -3.21376

bł d wzgl.: –1.13624,

t_min: 0.235521

cykl: 3,

warto ci: funkcji: 2.82844

bł d wzgl.: 6.21862e –006,

t_min: 0.196386

cykl: 4,

warto ci: funkcji: 2.82843

bł d wzgl.: 3.20727e –007,

t_min: 0.230203

cykl: 5,

warto ci: funkcji: 2.82843

bł d wzgl.: 1.00811e –009,

t_min: 0.280505

cykl: 6,

warto ci: funkcji: 2.82843

bł d wzgl.: –9.05838e –009, t_min: 0.362769

Wyniki metody „rank-one”:

współrz dne: x_min=0.714811, y_min=0.714811,

bł dy wzgl. x i y: 0.0110318, 0.0110318,

warto funkcji: 2.82859,

bł d wzgl. warto ci: 5.87003e –005,

warto prawdziwa: 2.82843,

warto ci składowych gradientu:

x-owa: 0.0214388,

y-owa: 0.0214388.

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

8

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Adaptacja metody „rank-one” do wi kszej liczby wymiarów.

Zmiana polega na zast pieniu układu dwóch równa słu cych w przypadku dwuwymiarowym do wyznaczenia

składowych kierunku poszukiwa (s

1

,s

2

) układem odpowiedniej (wi kszej) liczby równa :

G s

f

w przypadku dwóch wymiarów układ ten wygl da tak:

2

f

x

2

2

f

x y

2

f

x y

2

f

y

2

s

1

s

2

f

x

f

y

dla trzech i wi cej:

2

f

x

2

2

f

x y

2

f

x z

2

f

x y

2

f

y

2

2

f

y z

2

f

x z

2

f

y z

2

f

z

2

s

1

s

2

s

3

f

x

f

y

f

z

(mo e to by całkiem spory układ równa ).

Wszystkie pochodne byłyby oczywi cie obliczane w aktualnym punkcie. Rozwi zanie tego układu powinno da nam

wektor składowych kierunku poszukiwania nast pnego punktu (i tak wła nie post powali my w przypadku zagadnienia

dwuwymiarowego). Jednak w przypadku wi kszej liczby wymiarów zamiast rozwi zywa dokładnie du y układ równa

posłu ymy si przybli eniem:

s

H f

w którym macierz H ma zbiega si do odwrotno ci G w miar zbli ania si do lokalnego minimum, którego poszukujemy.

Na pocz tek przyjmiemy, e jest to macierz jednostkowa (zawieraj ca jedynki na głównej przek tnej), w miar post pu

oblicze b dziemy j modyfikowa — modyfikacja b dzie polega na dodawaniu poprawki E:

E

u u

T

Poprawk t b dziemy wyznacza nast puj co. Najpierw zauwa amy, e (je li drugie pochodne obliczamy numerycznie)

mo liwy jest zapis:

G s

f

G x

f

Wówczas, je li dodatkowo zało ymy (o czym była mowa ju wcze niej), e kolejne poprawki E zbli aj macierz H do

odwrotno ci macierzy G otrzymamy:

H E

f

x

H

uu

T

f

x

które to równanie b dzie spełnione je li zajdzie równocze nie:

u

x H f

i

u

T

f

1

Tryb post powania podczas poszukiwania minimum t metod b dzie nast puj cy:

1 Wybieramy punkt pocz tkowy ,

a

2 Obliczamy wektor pochodnych cz stkowych

(je li trzeba numerycznie).

f a

3 Poszukujemy minimum funkcji jednej zmiennej t (parametru): f t

f a tH f a

4 Zast pujemy przez

a

a t

min

f a

5 Koniec oblicze nast puje gdy uznamy, e zmiany s wystarczaj co małe

a

6 Wyznaczamy now macierz H:

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

9

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

6.1

wektor u

x

H f

a

1

a

0

H f a

1

f a

0

6.2

współczynnik wyznaczamy z równania: u

T

f

1

6.3

cała poprawka: E

uu

T

6.4

i nowa macierz: H

1

H

0

uu

T

Programowanie liniowe

Okre lenie zagadnienia

Zagadnienia programowania liniowego polegaj na znalezieniu maksimum zadanej liniowej funkcji wielu zmiennych

przy uwzgl dnieniu wielu dodatkowych warunków narzuconych na te zmienne.

Metoda znana jako „programowanie liniowe” zacz ła by powszechnie stosowana podczas II Wojny wiatowej do

rozwi zywania zagadnie logistycznych (w armiach angielskiej i ameryk skiej). Nazwa ta jest uzasadniona co najwy ej

historycznie, bo w swej oryginalnej postaci metoda ta nie miała nic wspólnego z programowaniem komputerów.

Przykład sformułowania problemu

Załó my, e mamy fabryk produkuj c dwa typy płaszczy: zwykłe przeciwdeszczowe i luksusowe. Cały proces

produkcji obejmuje trzy procesy cz stkowe: krojenie materiałów, szycie i pakowanie. Płaszcze produkuje si partiami (po

ile tam sztuk) — jednak ze wzgl du na uwarunkowania lokalne (dost pno wykwalifikowanego personelu itp.) liczba

godzin, które mo na przeznaczy na ka dy z procesów jest ograniczona. Konkretnie: na ci cie mo na przeznaczy 42

godziny (roboczogodziny), na szycie — 60 godzin i na pakowanie — 32 godziny. Ilo czasu jak trzeba przeznaczy na

ka d z czynno ci jest inna dla ka dego typu płaszcza. Wycinanie materiału na płaszcz przeciwdeszczowy zajmuje 8 godzin,

podczas gdy wycinanie płaszczy luksusowych zajmuje 5 godzin. Szycie płaszcza zwykłego zajmuje 3 godziny, a

luksusowego 16. Pakowanie: 5 godzin dla partii płaszczy zwykłych i 6 godzin dla luksusowych. Na ka dej partii płaszczy

zwykłych zarabiamy 500 zł, a na ka dej partii płaszczy luksusowych — 400 zł.

Dodatkowo zakładamy, e wszyscy pracownicy otrzymuj takie samo wynagrodzenie (niezale nie od tego czy pracuj

czy nie, e materiały („substraty”) i (ewentualne) narzuty kosztuj tyle samo (niezale nie od procesu) oraz e fabryka mo e

sprzeda wszystko co wyprodukuje. Chcemy wiedzie w jaki sposób zmaksymalizowa zysk.

Dane:

zwykły

przeciwdeszczowy

luksusowy

dost pny

czas pracy

ci cie

8

5

42

szycie

3

16

60

pakowanie

5

6

32

zysk

500

400

Wprowad my oznaczenia: x

1

— liczba partii zwykłych płaszczy przeciwdeszczowych, jakie fabryka mo e

wyprodukowa w ci gu dnia, x

2

— analogiczna liczba dla płaszczy luksusowych.

Tzw.

„funkcj celu” (któr chcemy zmaksymalizowa ) b dzie zysk: z = 500x

1

+ 400x

2

. Mamy te ograniczenia

(dotycz ce czasu pracy):

8x

1

+ 5x

2

42

(ci cie)

3x

1

+ 16x

2

60

(szycie)

5x

1

+ 6x

2

32

(pakowanie)

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

10

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Ddatkowo dodamy jeszcze ograniczenia oczywiste (zwane trywialnymi):

x

1

0 i x

2

0

W przypadku tak prostych problemów (pod wzgl dem liczby zmiennych) mo na pozwoli sobie na zastosowanie

metody graficznej. Posłu y ona jako ilustracja i umo liwi pó niejsze wprowadzenie metody numerycznej.

Metoda graficzna

Najpierw wykre lamy nasz „obszar zainteresowania” — tzn. obszar, w którym warto ci obu zmiennych spełniaj

narzucone na nie warunki.

Na tym samym wykresie mo emy te zaznaczy linie odpowiadaj ce kilku wybranym warto ciom zysku — w ten sposób

mo emy szybko zorientowa si uzyskanie jakich zysków w ogóle wchodzi w gr , a jakie warto ci s niemo liwe do

uzyskania. Na koniec, równie z rysunku, łatwo jest zorientowa si , któr dy b dzie przebiega linia zysku odpowiadaj ca

warto ci maksymalnej — je li ju okre limy przez który „naro nik” obszaru ma przechodzi zauwa ymy, przez punkt

wspólny których dwóch warunków musi przechodzi linia zysku i wyznaczymy warto ci x

1

i x

2

odpowiadaj ce

maksymalnemy zyskowi, a potem i sam zysk. W naszym przykładzie maksymalizuj zysk warto ci x

1

=4 i x

2

=2, a odpowiada

im zysk wynosz cy 2800.

Przypadek ogólniejszy

Jak łatwo zauwa y parametry zostały „r cznie” tak dobrane aby otrzyma wynik wyra aj cy si liczbami całkowitymi

— gdyby wynikiem nie były liczby całkowite mogliby my mie spory problem — np. ze wzgl dów technicznych nie byłoby

mo liwe wykonywanie tylko cz ci partii towaru (przykładem mo e by cho by i huta i (niemo liwa do uzyskania)

„ułamkowa cz

wytopu” z wielkiego pieca).

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

11

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Wracaj c do naszego przykładu — był on bardzo prymitywny: ró ni pracownicy otrzymuj ró ne wynagrodzenia, do

wytworzenia jednego wyrobu potrzeba wielu ró nych materiałów (o ró nych cenach), mo e doj jeszcze zu ycie energii,

koszty utylizacji odpadków itd., itp.. W rzeczywisto ci problem nigdy nie b dzie tylko dwuwymiarowy — liczba wymiarów

b dzie o wiele wi ksza — zatem metody graficznej nie da si zastosowa . Jednak prawdziwy pozostanie fakt, e

rozwi zaniem b dzie wierzchołek wielowymiarowej bryły (b d cej naszym obszarem zainteresowania), który b dzie

styczny do „linii zysku” (albo cie lej do czego „o jeden mniej wymiarowego” ni nasz obszar zainteresowania).

„Na oko” wydaje si , e rozwi zanie mo na by znale badaj c warto ci zysku odpowiadaj ce wszystkim „naro nikom”

— jednak okazuje si , e w przypadku np. 16 zmiennych i 20 warunków (tych „nietrywialnych”, tzn. pomijaj c oczywiste

warunki głosz ce, e dana zmienna ma by wi ksza od zera) otrzymujemy ok. 7 milionów naro ników (a jest to problem,

wg standardów programowania liniowego, bardzo mały). Potrzebne jest wi c inne podej cie.

Nosi ono nazw metody „simplex”, a jej zasad działania mo na zilustrowa za pomoc adaptacji do przypadku

wielowymiarowego metody, któr posłu yli my si w (dwuwymiarowym) przypadku rozwi zywanym graficznie.

W najwi kszym skrócie i uproszczeniu metoda ta działa nast puj co: wybieramy jaki wierzchołek (cho by i ten dla

wszystkich zmiennych wynosz cych zero), sprawdzamy jaka jest w nim warto naszej funkcji celu (zysku), nast pnie

spo ród s siednich wierzchołków wybierzemy ten, dla przej cia do którego przyrost funkcji celu b dzie maksymalny,

przejdziemy do niego i z kolei w ród jego s siadów b dziemy szuka wierzchołka daj cego maksymalny przyrost funkcji

celu. Operacje takie b dziemy powtarza a do znalezienia si w wierzchołku, którego wszyscy s siedzi daj ujemny

przyrost funkcji celu — uznamy wówczas problem za rozwi zany.

Oczywi cie aby operacj t mógł samodzielnie przeprowdzi komputer musimy odpowiednio przygotowa dane i

sformułowa algorytm rozwi zywania takich problemów dla dowolnej liczby zmiennych i dowolnej liczby ogranicze .

Posta kanoniczna problemu

Najpierw okre lmy

posta standardow zagadnienia — odpowiada ona uporz dkowaniu wszystkich nierówno ci

opisuj cych zagadnienie:

z

c

1

x

1

c

2

x

2

c

n

x

n

c

11

x

1

c

12

x

2

c

1

x

n

b

1

c

21

x

1

c

22

x

2

c

2

x

n

b

2

c

m1

x

1

c

m2

x

2

c

mn

x

n

b

m

x

1

,x

2

, ,x

n

0

Warto zauwa y , e w postaci standardowej wszystkie warunki „nietrywialne” zapisane s w postaci

„mniejszy lub

równy” — zatem podczas przepisywania zagadnienia do postaci standardowej mo e by konieczne odwrócenie niektórych

nierówno ci (pomno enie przez –1, z czym b dzie si wi za zmiana znaków współczynników na przeciwne). Natomiast

wszystkie warunki trywialne maj posta

„wi kszy lub równy” (to zazwyczaj nie b dzie ulega zmianie).

W postaci kanonicznej zawsze mówimy o maksymalizacji funkcji, a warunki nietrywialne musz mie posta

równo ci — co mo na uzyska przez wprowadzenie zmiennych dodatkowych.

Rozwa my to na nast puj cym przykładzie — mamy zminimalizowa funkcj z:

z

x

1

3x

2

4x

3

2x

1

4x

3

4

x

1

x

2

5x

3

4

2x

2

x

3

2

x

1

,x

2

,x

3

0

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

12

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

W postaci standardowej zagadnienie to przybierze posta :

z

x

1

3x

2

4x

3

2x

1

4x

3

4

x

1

x

2

5x

3

4

2x

2

x

3

2

x

1

,x

2

,x

3

0

Znak funkcji z został zmieniony aby my mogli mówi o maksymalizacji. Aby zamieni t posta na kanoniczn musimy

sprowadzi nierówno ci b d ce warunkami (ograniczeniami) nietrywialnymi do równo ci — zrobimy to wprowadzaj c

dodatkowe zmienne:

2x

1

4x

3

4

2x

1

4x

3

x

4

4

x

4

0

Je li przeprowadzimy tak operacj dla wszystkich warunków otrzymamy:

z

x

1

3x

2

4x

3

2x

1

4x

3

x

4

4

x

1

x

2

5x

3

x

5

4

2x

2

x

3

x

6

2

x

1

,x

2

,x

3

,x

4

,x

5

,x

6

0

co jest wła nie postaci kanoniczn naszego zagadnienia.

Przykład realizacji metody simplex

Rozpatrzmy działanie takiej metody na poprzednim przykładzie (produkcja płaszczy). Problem maksymalizacji zysku

z produkcji płaszczy ma, w postaci kanonicznej, nast puj c posta :

z

500x

1

400x

2

8x

1

5x

2

x

3

42

3x

1

16x

2

x

4

60

5x

1

6x

2

x

5

32

x

1

,x

2

,x

3

,x

4

,x

5

0

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

13

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Na rysunku powy ej widzimy nasz “obszar zainteresowania” przedstawiony jako obszar ograniczony prostymi o

równaniach postaci x

i

= 0. Istotne dla nas wierzchołki, w których b dziemy bada zmiany funkcji celu oznaczone s na

rysunku wielkimi literami A...E, natomiast wierzchołki, które wprawdzie równie stanowi punkty przeci cia par prostych

x

i

= 0, ale jako nie nale ce do kraw dzi interesuj cego nas obszaru s z naszego punktu widzenia nieistotne, oznaczone

s jako X, Y, Z (s jeszcze dwa takie wierzchołki, ale znalazły si poza wykresem).

Mo na zauwa y , e w ka dym z wierzchołków pokazanych na wykresie powy ej

dwie zmienne maj warto zero,

a

trzy pozostałe nie.

W ogólnym przypadku, je li problem był okre lony przez n zmiennych, do których dodali my jeszcze m zmiennych

dodatkowych (mamy ich wi c w sumie n+m) to w ka dym z wierzchołków n spo ród zmiennych przyjmuje warto zero.

Zmienne, które w danym wierzchołku maj warto ci niezerowe okre lamy jako podstawowe (w danym wierzchołku), a

pozostałe jako niepodstawowe (w tym e wierzchołku). Zbiór warto ci wszystkich zmiennych (podstawowych i

niepodstawowych) w danym wierzchołku okre lamy jako rozwi zanie odpowiadaj ce temu wierzchołkowi. W tabeli

pokazano, które zmienne s podstawowe, a które nie, w poszczególnych wierzchołkach w naszym przykładzie:

wierzchołek

zmienne

podstawowe

zmienne

niepodstawowe

A

B

C

D

E

x

1

, x

2

, x

4

x

1

, x

4

, x

5

x

3

, x

4

, x

5

x

2

, x

3

, x

5

x

1

, x

2

, x

3

x

3

, x

5

x

2

, x

3

x

1

, x

2

x

1

, x

4

x

4

, x

5

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

14

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Mo na zauwa y , e przemieszczaj c si od wierzchołka do wierzchołka po obwodzie interesuj cego nas obszaru za

ka dym razem zmieniamy jedn ze zmiennych podstawowych na niepodstawow i odwrotnie: A B x

2

x

5

, B C

x

1

x

3

, C D x

2

x

4

, D E x

1

x

5

, E A x

3

x

4

.

Rozwi zanie metod simplex rozpoczynamy od nadania wszystkim zmiennym wyst puj cym w oryginalnym problemie

warto ci zerowych. Je li wierzchołek ten nale y do kraw dzi obszaru zainteresowania to wszystkie warto ci zerowe s

dopuszczalnym rozwi zaniem naszego problemu (zazwyczaj tak jest) i mo emy rozpocz obliczenia — je li nie —

b dziemy musieli znale inny wierzchołek, od którego rozpoczniemy (o tym jak to zrobi — pó niej).

W przykładowym problemie rozwi zaniem pocz tkowym b dzie x

1

=0 i x

2

=0 (jak wida na rysunku takie rozwi zanie

jest dopuszczalne — jest to punkt C). W przypadku gdy nie mamy rysunku (np. problem jest wielowymiarowy)

podstawiamy zało one warto ci zerowe do warunków problemu (sformułowanego w postaci kanonicznej — a wi c ju z

wprowadzonymi zmiennymi dodatkowymi) i sprawdzamy czy warunki te nie s sprzeczne. Je li nie s — rozwi zanie jest

dopuszczalne. Łatwo zauwa y (patrz c na funkcj celu z), e zwi kszanie x

1

(od warto ci zerowej) spowoduje wi kszy

przyrost funkcji celu (zysku — z) ni analogiczne zwi kszanie warto ci x

2

— poszukamy wi c zmiennej niepodstawowej,

która ma najwi kszy współczynnik w (maksymalizowanej przez nas) funkcji celu (w wierzchołku od którego rozpocz li my

zmiennymi niepodstawowymi były wła nie x

1

i x

2

). Zdecydowawszy si na x

1

pozwalamy jej przyj warto niezerow (a

wi c sta si zmienn podstawow ) — musimy okre li , która z dotychczasowych zmiennych podstawowych ma sta si

niepodstawow . W tym celu równania okre laj ce warunki przepiszemy w nast puj cej postaci:

x

3

42

8x

1

5x

2

x

4

60

3x

1

16x

2

x

5

32

5x

1

6x

2

Sprawdzamy teraz, która z pozostałych zmiennych pierwsza osi gnie zero gdy warto zmiennej x

1

b dzie wzrasta

ponad zero — w tym celu wystarczy podzieli wolny wyraz w ka dym z równa przez współczynnik stoj cy przy x

1

—

otrzymamy: 42/8 (5.25) dla x

3

, 60/3 (20) dla x

4

i 32/5 (6.4) dla x

5

— najszybciej spadnie do zera zmienna x

3

i t te zmienn

wybieramy jako „zamiennik” dla x

1

. Z naszej tabeli wynika, e przeniesiemy si do wierzchołka B.

W wierzchołku B powtarzamy cał procedur — sprawdzamy, która ze zmiennych niepodstawowych staj c si

podstawow b dzie mie najwi kszy wpływ na wzrost funkcji celu z. W wierzchołku tym (B) zmiennymi niepodstawowymi

s x

2

i x

3

— funkcj celu przepiszemy wi c z ich wykorzystaniem:

x

1

42

5x

2

x

3

8

z

500

42

5x

2

x

3

8

400x

2

2625

87.5x

2

62.5x

3

Wynika st d, e je li zmienna x

2

stanie si podstawow to b dzie to mie wi kszy wpływ na wzrost z ni taka zmiana

w przypadku x

3

(wła ciwie, poniewa współczynnik przy zmiennej x

3

jest ujemny, mogliby my wył czy j z tych rozwa a

— tylko jej warto ci ujemne mogłyby wpływa na wzrost z, a te s „z definicji” wykluczone). Warunki przepiszemy w

nast puj cej postaci (pami taj c, e x

3

ma pozosta niepodstawow — czyli wynosz c zero):

x

1

42

5x

2

8

3x

1

x

4

60

16x

2

5x

1

x

5

32

6x

2

Jak wida pierwszego z warunków nie trzeba ju przekształca (odpowiedni form uzyskał gdy wyznaczali my warto

zmiennej x

1

), pozostałe dwa przekształcamy (wykorzystuj c wyra enie na x

1)

:

x

1

42

5x

2

8

x

4

354

113x

2

8

x

5

46

23x

2

8

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

15

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Ponownie sprawdzamy współczynniki (wolny wyraz podzielony przez współczynnik stoj cy przy x

2

) — najmniejszym

jest 46/23 (odpowiadaj cy zmiennej x

5

) — czyli to zmienna x

5

pierwsza osi gnie zero gdy x

2

b dzie wzrasta od zera. Zatem

zmienna x

5

stanie si niepodstawow , za zmienna x

2

stanie si podstawow — „przenosi” nas to z wierzchołka B do

wierzchołka A.

Znan ju procedur powtarzamy w wierzchołku A. Znowu przekształcamy funkcj celu tak aby wyra ona była przez

zmienne niepodstawowe (w tym przypadku/wierzchołku s to x

3

i x

5

). Wychodz c od ostatnio zmodyfikowanej postaci

funkcji celu otrzymujemy i przekształcaj c ostatnie z powy szych równa (wi

ce x

5

z x

2

):

z

2625

87.5x

2

62.5x

3

2625

87.5

8x

5

46

23

62.5x

3

2800

62.5x

3

700

23

x

5

Jak wida doszli my do momentu, gdy nie jeste my w stanie zwi kszy warto ci funkcji celu z poniewa obie

wyst puj ce we wzorze zmienne podstawowe maj ujemne współczynniki. Stwierdzamy wi c, e znale li my rozwi zanie

optymalne — konkretnie z = 2800. Podstawienie x

3

=0 i x

5

=0 we wzorach na warunki zagadnienia daje:

8

x

1

5x

2

42

5x

1

6x

2

32

Sk d łatwo otrzymujemy x

1

=4 i x

2

=2 (czyli ten sam wynik, który otrzymali my metod graficzn ).

Warto zwróci tu uwag , e w bardziej skomplikowanych przypadkach mo liwe jest „zap tlenie” rozwi zania (gdy

proces zacznie przebiega sekwencj wierzchołków nie zwi kszaj c warto ci funkcji celu).

Pocz tkowe przybli enie rozwi zania

Problem znajdowania pocz tkowego przybli enia rozwi zania zilustrujemy na nieco zmodyfikowanym przykładzie

fabryki płaszczy. Dodamy jeszcze jeden warunek — fabryka musi produkowa przynajmniej jedn parti płaszczy

przeciwdeszczowych dziennie.

Po uwzgl dnieniu tego dodatkowego warunku posta kanoniczna problemu jest nast puj ca:

z

500x

1

400x

2

8x

1

5x

2

x

3

42

3x

1

16x

2

x

4

60

5x

1

6x

2

x

5

32

x

1

x

6

1

x

1

,x

2

,x

3

,x

4

,x

5

,x

6

0

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

16

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

A przedstawienie graficzne wygl da tak jak na rysunku obok. Jak wida zastosowane wcze niej rozwi zanie

pocz tkowe, w którym obie zmienne wyst puj ce w oryginalnym sformułowaniu problamu wynosz zero nie jest

dopuszczalne — dotychczasowy punkt C nie znajduje si ju na kraw dzi obszaru zainteresowania — zało enie x

1

=0 łamie

warunek x

6

0.

Aby rozpocz jednak w jaki sposób obliczenia zaczynamy od

funkcji pseudocelu z . Funkcj t wprowadzamy maj c

na celu zwi kszenie warto ci zmiennej x

6

i doprowadzenia jaj do warto ci dodatniej. Przeprowadzimy w tym celu jeden

cykl metody simplex dla celu danego równaniem:

z’ = x

6

= x

1

– 1

i z pozostałymi warunkami oryginalnymi. Zgodnie z zasadami stwierdzamy, e zmiana x

1

b dzie mie wi kszy wpływ na

z ni zmiana x

2

. Wobec tego zmienna x

1

staje si zmienn podstawow — zmiennymi podstawowymi s wi c obecnie x

3

,

x

4

, x

5

i x

6

, zatem utrzymuj c dla x

2

warto zero mamy:

x

3

42

8x

1

x

4

60

3x

1

x

5

32

5x

1

x

6

1

x

1

Wida , e przy wzro cie x

1

ponad zero x

6

b dzie pierwsz zmienn , która osi gnie zero i wła nie x

6

stanie si

niepodstawow . Mamy teraz x

2

=0 i x

6

=0, sk d wynika, e x

1

=1, x

3

=34, x

4

=57 i x

5

=27.

To jest wła nie wyj ciowe przybli enie rozwi zania i od niego mo na rozpocz dalsze rozwi zywanie zagadnienia

metod simplex.

Przeprowadzony jeden cykl z funkcj pseudocelu “przeniósł” nas z punktu C do punktu Y (zaznaczonego na rysunku

powy ej).

Gdyby uzyskany punkt nie był dopuszczalnym rozwi zaniem musieliby my wybra inn funkcj pseudocelu — mogłaby

to by np. suma wszystkich zmiennych niedodatnich.

Metody Numeryczne w Fizyce 1

Minima funkcji wielu zmiennych

17

© Andrzej Brozi, Instytut Fizyki Politechniki Łódzkiej

Problemy z rozwi zaniami b d cymi liczbami całkowitymi

W rozwi zanym przykładzie otrzymali my wynik wyra ony liczbami całkowitymi — bardzo nas to satysfakcjonuje. W

wielu przypadkach rozwi zania b d ce liczbami całkowitymi s jedynymi dopuszczalnymi — nie sposób sobie wyobrazi

wyprodukowania ułamka zawarto ci wielkiego pieca stali czy „gruszki” betonu — istniej procesy produkcyjne, w których

nie mo na zostawi cz ci produkcji „na jutro”.

Znajdowanie rozwi za całkowitych mo e znakomicie utrudni rozwi zywania takich zagadnie . Mo na sobie z tym

jednak poradzi stosuj c nast puj ce podej cie:

Na pocz tku rozwi zujemy zagadnienie tak samo jak w przedstawionych przykładach — czyli tak jaby zadowalało nas

znalezienie rozwi za ułamkowych. Gdy znajdziemy ju rozwi zanie optymalne sprawdzamy czy wyra a si ono liczbami

całkowitymi — je li tak „mamy problem z głowy”. Je li nie — wybieramy t zmienn , która w rozwi zaniu nie jest

całkowita (je li jest ich kilka to wybieramy któr kolwiek) i zaczynamy rozwi zywa

dwa problemy — w ka dym z nich

do oryginalnego zestawu warunków dodajemy jeden dodatkowy ograniczaj cy zmienno tej wła nie zmiennej —

uniemo liwiaj cy jej przyj cie tej wła nie warto ci ułamkowej.

Gdyby na przykład zmienna x

1

w obliczonym rozwi zaniu przyjmowała warto 3.3 przyst piliby my do rozwi zywania

dwóch „nowych” zagadnie — jedno z nich zostałoby „wzbogacone” o warunek

x

1

3, a drugie o warunek x

1

4. Procedur

tak powtarzaliby my (zapisuj c otrzymywane rozwi zania całkowite — o ile oczywi cie takie by my „po drodze”

uzyskiwali) tak długo a wyczerpaliby my wszystkie mo liwo ci. Nast pnie spo ród zanotowanych rozwi za całkowitych

wybraliby my najlepsze (maksymalizuj ce funkcj celu).

Nale y zwróci uwag , e dodanie warunków do nowych „podproblemów” ogranicza „obszar zainteresowania” dla

danego podproblemu — je li podczas rozwi zywania którego z podproblemów znale li my rozwi zanie optymalne dla

danego „podobszaru” to rozwi zywanie kolejnych podproblemów dotycz cych tego samego podobszaru mija si z celem

— umo liwia bowiem co najwy ej powtórne znalezienie tego samego rozwi zania.