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.