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. Suma argumentow x zawsze musi byc rowna zero z
dokladnoscia przynajmniej czterech miejsc po przecinku (najlepiej szesciu). Ponadto
kazdy argument x musi byc wiekszy lub rowny zero.

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 )).

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?
Pozdrawiam!

do góry

W dniu 2012-09-25 13:22, M.M. pisze:
> 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. Suma argumentow x zawsze musi byc rowna zero z
dokladnoscia przynajmniej czterech miejsc po przecinku (najlepiej szesciu). Ponadto
kazdy argument x musi byc wiekszy lub rowny zero.
>
> 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 )).

Ten zapis jest bez sensu.
Rozumiem, że chodzi o max_{zi} (min(f1,f2,f3))

czyli tak dobrać zi (a włąściwie p) aby minimum z trzech
funkcji było największe?

>
> 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?

Tak. zi[j] =1 jeśli x[j]>0, zi[j]=0 w przeciwnym przypadku.

Napisz to jeszcze raz wyraźniej (co jeds daną, co zmienną,
ekstrema względem których zmiennych etc) bo chyba nie o to chodziło;)

pzdr
bartekltg

do góry

> mniejsze od 10. Suma argumentow x zawsze musi
> byc rowna zero z dokladnoscia przynajmniej
> czterech miejsc po przecinku (najlepiej
> szesciu). Ponadto kazdy argument x musi byc
> wiekszy lub rowny zero.

nie wiem czy wogole trzeba cos liczyc bo jesli
kazdy x >=0 i suma x = 0 to znaczy ze kazdy
x = 0

:O

do góry

W dniu wtorek, 25 września 2012 13:30:44 UTC+2 użytkownik bartekltg napisał:
> Ten zapis jest bez sensu.
> Rozumiem, że chodzi o max_{zi} (min(f1,f2,f3))

Trzeba zmaksymalizowac funkcje ff zmieniajac wartosci x.
http://pastebin.com/papzUzaL
Wartosci w p[j] sa losowe z przedzialu od 1 do P. Wartosci w z[i][j]
sa rowne albo zero, albo jeden, albo p[j]. Suma wartosci x[i]
msui byc rowna 1, ponadto kazdy x[i] >= 0.

Pozdrawiam.

do góry

W dniu wtorek, 25 września 2012 14:14:17 UTC+2 użytkownik kenobi napisał:
> nie wiem czy wogole trzeba cos liczyc bo jesli
> kazdy x >=0 i suma x = 0 to znaczy ze kazdy
Ups :)
Suma rowna 1 :)
Pozdrawiam

do góry

jesli zaane p sa stale i zadane z
sa stale, oraz zwiazek miedzy p i z
jest staly to chyba lepiej mowic tylko
o poszukiwaniu spraw zwiazanych z
maximum/ minimum z[]*x[] ? bez wtracania
w to p

a jak konkretne postac z[] ma pomoc to podaj
ja dokladnie a nie kawałek :O

do góry

W dniu wtorek, 25 września 2012 14:26:41 UTC+2 użytkownik kenobi napisał:
> jesli zaane p sa stale i zadane z
>
> sa stale, oraz zwiazek miedzy p i z
>
> jest staly to chyba lepiej mowic tylko
>
> o poszukiwaniu spraw zwiazanych z
>
> maximum/ minimum z[]*x[] ? bez wtracania
>
> w to p
>
>
rozumiem to jako "tak dobrac w przestrzeni
wektor x aby najmniejszy z jego iloczynow
skalarnych z z1, z2, z3 byl jak najwiekszy
(co prawdopodobnie znaczy ze beda sobie rowne
- nie da sie tego normalnie rozwiazac ?
wydaje sie chyba prostym problemem z matematyki

do góry

W dniu wtorek, 25 września 2012 14:37:27 UTC+2 użytkownik kenobi napisał:
> W dniu wtorek, 25 września 2012 14:26:41 UTC+2 użytkownik kenobi napisał:
>
> > jesli zaane p sa stale i zadane z
>
> >
>
> > sa stale, oraz zwiazek miedzy p i z
>
> >
>
> > jest staly to chyba lepiej mowic tylko
>
> >
>
> > o poszukiwaniu spraw zwiazanych z
>
> >
>
> > maximum/ minimum z[]*x[] ? bez wtracania
>
> >
>
> > w to p
>
> >
>
> >
>
> rozumiem to jako "tak dobrac w przestrzeni
>
> wektor x aby najmniejszy z jego iloczynow
>
> skalarnych z z1, z2, z3 byl jak najwiekszy
>
> (co prawdopodobnie znaczy ze beda sobie rowne
>
> - nie da sie tego normalnie rozwiazac ?
>
> wydaje sie chyba prostym problemem z matematyki

moze nawet z geometrii cos w stylu - x
na przekatnej bryly zbudowanej na z1 z2 z3
- czy sos w tym stylu

do góry

> Dostosowalem do tego zdania symulowane wyzarzanie.

co to takiego?

do góry

W dniu wtorek, 25 września 2012 14:26:41 UTC+2 użytkownik kenobi napisał:
> jesli zaane p sa stale i zadane z
> sa stale, oraz zwiazek miedzy p i z
> jest staly to chyba lepiej mowic tylko
> o poszukiwaniu spraw zwiazanych z
> maximum/ minimum z[]*x[] ? bez wtracania
> w to p
Moze jednak warto wtracac w to p?
W kazdej kolumnie z[][] moze byc tylko jedna z
'trzech' wartosci: 0, 1, p[i]. Mniej mozliwosci,
to zadanie prostsze do optymalizacji?
Pozdrawiam

do góry