W dniu 2012-09-25 13:22, M.M. pisze:

Trochę gdybania i gorszych metod. Jak Ci się spieszy,
leć od razu do 'rozwiązanie właściwe'

> Jest N-elementowy ciag parametrow p[1..N] i N-elementowy ciag argumentow x[1..N]. W
moim problemie obecnie N jest rowne 8,
>ale potem bedzie wieksze. Zarowno parametry jak i argumenty to liczby rzeczywiste.
Parametry p sa z przedzialu 1 <= p <= P,
>gdzie P z reguly jest mniejsze od 10.


Warunek A:
>Suma argumentow x zawsze musi byc rowna zero

Super. x1+.. +x8 = 0

Warunek b
> Ponadto kazdy argument x musi byc wiekszy lub rowny zero.

ok.
x1>=0
x2>=0
...
x8>=0

Z drugiej storny A mówi, że
x1+.. +x8 = 0
-x1 = x2+...+x8
Ale B! x2>=0, x8>=0, więc
-x1 = x2+...+x8 >= 0

x1<=0

Tak samo z pozostałymi. Z Twoich warunków x=0 i tyle.

Dalej zakładam, że miało być x1+x2+...+x8 = 1

Zamiast jeden można podstawić sobie epsylon.
Pamiętaj, że wynik będzie najzwyczajniej w świecie
proporcjonalny do tego epsylona. To liniowe jest.
100 razy dalej od sum x_i =0, sto razy większy wynik.


> Jest kilka funkcji liniowych (obecnie mam trzy, ale bedzie wiecej):
> f1(p,x) = suma od 1 do N z1[j] * x[j];
> f2(p,x) = suma od 1 do N z2[j] * x[j];
> f3(p,x) = suma od 1 do N z3[j] * x[j];
> gdzie zi[j] moze przyjmowac wartosc zero, jeden, albo p[j].
>
> Ciagi p i z sa danymi w zadaniu. Szukamy takiego ciagu x ktory zmaksymalizuje
minimum:
> max( min( f1, f2 , f3 )).

Minimum jest z tych 3 funkcji, a po czym jest maksimum?
Matematyczna precyzacja nigdy nie szkodzi, a zmniejsza
liczbę niepotrzebnych postów:)
max_{x}( min( f1, f2 , f3 )). :)

> Dostosowalem do tego zdania symulowane wyzarzanie. Znajduje rozwiazanie po okolo
50mln iteracji,
> co zajmuje na procesorze i3 okolo 4-5 sekund. Niestety dopuszczalny czas to 0.03s.

> Da sie to jakos szybciej policzyc?

Nie wyzarzaniem;) Już zwykłe MC będzie lepsze:)
[Na serio, sprawdza się kiepsko, 100000 losowych daje
wynik dość odległy o optymalnego. Dla losowych zi optymalnie
bylo coś rzedu 7.3, a max z CMC (czyt chamskie MC) dawało 6.7]


Jakakolwiek 'numeryczna' metoda minimalizacji sprawdzi się
znacznie lepiej. W końcu to tylko kawałkami liniowe funkcje
na 7 (N-1) wymiarowej przestrzeni (a właściwie kostki).

F = min( sum z1[j] * x[j],sum z2[j] * x[j], sum z3[j] * x[j] )

W dodatku wypukła/wklęsła.

Im prostsza, tym lepsza. Matalbowskiego fminsearch trzeba nieco
podpuscić, aby to dobrze rozwiązywał.


Ale nadal, to funkcje liniowe. Gdzie będzie rozwiązanie?
Na rogach, na przecięciu f1=f2=f3 i brzegu kostki/warunków
sumowania, albo brzego i równości dwóch.
W rzeczywistości obstawiam równość wszystkich trzech (mają
dodatnie współczynniki...)

Tyle, że to tez strzelanie z armaty do wrócla, i to
zupełnie nie tą amunicją co trzeba.


Idzmy dalej. Popatrz na to geometrycznie.
z1 z2 z3 to takie wektorki sterczące w ściśle dodatnią
'ćwiartkę' przestrzeni. Warunek sum xi = 1 to wybór
pewnej hiperpłaszczyzny.
Wybieramy jakiś wektor x z tej płaszczyzny, rzutujemy
na wektorki z1,z2,z3 i bierzemy najmniejszy rzut.
Bierzemy największy.


x (po prostu z R^N)
popatrzmy na 'hipsometry'. Płaszczyzna stałęj wartośći.
Weźmy jakąś wartość. b.
Wyrysujmy
z1*x==b
z2*x==b
z3*x==b
...

Wyjdą z tego trzy hiperpłaszczyzny. One nas
ograniczają. Jednocześnie próbujemy dostać
się jak najbliżej centrum.
Powstanie nam fragment wielościanu wypukłego.

[Ciach mętna interpretacja geometryczna]

********ROZWIĄZANIE WŁAŚCIWE*****************
Mamy tutaj zwyczajne zagadnienie programowania liniowego z warunkami:

Najpierw je zdefiniujemy, a potem pokażemy, że to to samo.


z1*x >= 1
z2*x >= 1
z3*x >= 1

x>0 (w znaczeniu x[i] > 0)

oraz funkcją celu [1,1,1,1, 1,1,1,1] *x i chcemy ją _minimalizować_


Z algorytmu simplex czy jakiejkolwiek innej metody uzyskujesz
rozwiązanie x_1 spełniające te warunki i maksymalizujące
funkcję celu.

Rozwiązaniem oryginalnego problemu jest x_2 = x_1/(suma(x_1)).


Dlaczego? No to szkic dowodu:

Niech b = 1/suma(x1).

Po przeskalowaniu x-ów przez b mamy

suma(x_2)=1 i spełnia

z1*x_2 >= b
z2*x_2 >= b
z3*x_2 >= b
czyli min (fi,f2,f3)>=b;) Wiemy, że równe.



Niech inny x3, taki , ze suma(x3)=1
jest lepszym 'maksimum z minimum'
z1*x_3 >= c
z2*x_3 >= c
z3*x_3 >= c

c > b

Wtedy

x3/c spełnia nierówności z programowania liniowego
(zi * (x_3/c)) <= 1 oraz
sum (x_3/c) = 1/c < 1/b, czyli jest lepszym minimum
funkcji celul z programowania liniowego. To jest
sprzeczne z tym, że x2 jest rozwiązaniem programowania
liniowego.

[koniec]


W 0.03 s to kilogramy takich zagadnień oblecisz.

pzdr
bartekltg