On 2012-09-25 13:22, M.M. wrote:
> 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!
>
>


Popraw mnie, jeżeli się mylę ale czy nie da się przekształcić tego
problemu do serii problemów programowania liniowego? W każdym problemie
zakładasz że jedna z twoich funkcji f jest minimalna (i zabezpieczasz to
założenie odpowiednimi ograniczeniami) po czym dokonujesz jej
maksymalizacji.

Załóżmy, że funkcji f i wektorów z mamy K. Układasz K problemów PL z
których każdy jest postaci (k=1..K):

max f_k

przy ograniczeniach:

(minimalnosc funkcji f_k)
f_k <= f_1
...
f_k <=f_K

(definicje funkcji f)
f_1 = sum(z1 * x)
...
f_K = sum(z_K * x)

(ograniczenia na x)
sum(x) = 1
x>=0

Rozwiązujesz każdy z problemów, uzyskujesz K wyników, wybierasz
najmniejszy.

Plusy są takie, że po pierwsze twoje rozwiązanie jest dokładne, po
drugie odrywasz się od ograniczenia na wartości parametru p. Jeżeli
chodzi o wydajność... to musisz przetestować :) Coś mi umknęło?


--
Pozdrawiam
Kacper Rzepecki

do góry

On 2012-09-25 19:47, Kacper Rzepecki wrote:
>
>
> Rozwiązujesz każdy z problemów, uzyskujesz K wyników, wybierasz
> najmniejszy.

największy

do góry

sorki jak bede chial popisac z nudziarzem to
do ciebie sie odezwe, ale szczerze mowiac to
watpie

do góry

W dniu wtorek, 25 września 2012 19:47:42 UTC+2 użytkownik Kacper Rzepecki napisał:
> Popraw mnie, jeżeli się mylę ale czy nie da się przekształcić tego
> problemu do serii problemów programowania liniowego? W każdym problemie
> zakładasz że jedna z twoich funkcji f jest minimalna (i zabezpieczasz to
> założenie odpowiednimi ograniczeniami) po czym dokonujesz jej
> maksymalizacji.

Nie jestem pewny, ale chyba sie mylisz. Czy takie zadanie miesci sie w ramach
programowania liniowego. Jesli pozostale funkcje przerobimy na warunki, to funkcja
celu stanie sie jakas dziwna: jej wartosc nie bedzie zalezala tylko od
optymalizowanej funkcji, ale takze od warunkow. Jesli ktorys z warunkow spadnie
ponizej optymalizowanej funkcji, to funkcja celu bedzie rowna temu warunkowi. Wlasnie
ulozylem takie zadanie w calcu i uzylem slovera. Ladnie policzyl dla pierwszej
funkcji, ale dla drugiej krzyknal ze zadanie jest nierealistyczne. Nie umial
maksymalizowac drugiej funkcji pod warunkiem ze jest mniejsza od wszystkich
pozostalych funkcji. Moze sie zdarzyc ze jedna z funkcji zawsze bedzie wieksza od
ktorejs z pozostalych dla dowolnych wartosci x.

do góry

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

do góry

ale jaka to bedzie konkretnie odpowiedz bo mi
wydawalo sie ze wynikowe x to moze byc wazona suma z1 z2 z3 tylko nie wiem jakie to
sa wspolczynniki tych wag, chodzi o taki unormowany wektor x gdzie
"dot(x,z1) == dot(x,z2) == dot(x,z3)"

do góry

W dniu 2012-09-25 22:11, bartekltg pisze:

Trochę poprawiłem czytelność.

Zajmujemy się najpierw zmodyfikowanym problemem,
potem pokażemy, że to dokładnie to samo.


Rozwiązujemy następujące zadnienie zmodyfikowane:
[programowanie liniowe]


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

z minimalizowaną funkcją celu sum(x)
(czy jak kto woli x*[1,1,....1] )

Za standardowym warunkiem x_i > 0
****

Rozwiązaniem jest jakiś x1.

Oznaczmy b = 1/sum(x1)



Twierdzimy, że rozwiązaniem oryginalnego problemu jest
wtedy x2 = x1*b = x1 / (sum(x1)) - ten sam wektor
znormalizowany do interesującej nas (hiper)płaszczyzny.


Dlaczego to jest to samo?

sum (x2_i) = 1 // zgadza się z tym, co ma być

x*z1 > = b
x*z2 > = b
x*z3 > = b
...
x*zn > = b

Czyli min (x*z1, ..., x*zn) >=b.
[skądinąd wiemy, ze co najmniej jedną nierówność wysyca]

Pozostaje pytanie, czy nie da się lepiej niż b.

Niech x_3 będzie takim lepszym rozwiązaniem oryginalnego
zagadnienia.

sum (x3_i) = 1

x*z1 > = c
x*z2 > = c
x*z3 > = c
...
x*zn > = c

Gdzie c > b.

Wtedy x4 = x3/c spełnia

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

oraz sum (x_4) = 1/c

Ale to to samo, co funkcja celu w zagadnieniu zmodyfikowanym.
a 1/c < 1/b.

Jest to sprzeczne z tym, że x2 jest optymalne dla tego
zmodyfikowanego problemu (prog lin).

Więc x2 = x1 / sum(x1) jest rozwiązaniem oryginalnego problemu.



pzdr
bartekltg

do góry

W dniu 2012-09-25 22:25, kenobi pisze:
> ale jaka to bedzie konkretnie

Konkretnie:

Piszemy zagadnienie programowania liniowego w postaci:

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

x_i > 0

Funkcja celu = [1,1...1]*x , minimalizowana.

Rozwiązujemy. Np algorytmem simplex.
Dostajemy y.

Ostatecznym wzorkiem na nasze rozwiązanie jest
z = y / (sum (y_i))

Czyli y przeskalowane tak, by jego pierwsza norma była =1.


Niestety, nie wszystkie zagadnienia da się rozwiązać
wzorkiem. Ten problem jest równoważny problemowi programowania
liniowego, więc jesteśmy niemal pewni, że wzorkiem nie da się
go rozwiązać.
Ale często, jak nie ma wzorku, to jest algorytm.

Na rozwiązanie układu równań też nie ma rozsądnego wzorku,
a jest algorytm.

> odpowiedz bo mi
> wydawalo sie ze wynikowe x to moze byc wazona suma z1 z2 z3 tylko
> nie wiem jakie to sa wspolczynniki tych wag, chodzi o taki unormowany
> wektor x gdzie
> "dot(x,z1) == dot(x,z2) == dot(x,z3)"

Nie, nie zawsze rozwiązanie będzie kombinacją liniową z1,z2,z3.

Nie, nie zawsze rozwiązanie będzie spełniać
dot(x,z1) == dot(x,z2) == dot(x,z3)

To ostatnie łatwo pokazać.

z1 = [2,1,1,1,1,1,1,1]
z2 = [5,5,5,5,5,5,5,5]
z3 = [8,9,7,5,6,9,8,7]

Optymalne x wynosi tam x=[1,0,0,0,0,0,0,0].

_Ani jedna_ równość z trójki
dot(x,z1) == dot(x,z2) == dot(x,z3)
nie zachodzi.

pzdr
bartekltg

do góry

On 2012-09-25 21:16, M.M. wrote:
> W dniu wtorek, 25 września 2012 19:47:42 UTC+2 użytkownik Kacper Rzepecki napisał:
>> Popraw mnie, jeżeli się mylę ale czy nie da się przekształcić tego
>> problemu do serii problemów programowania liniowego? W każdym problemie
>> zakładasz że jedna z twoich funkcji f jest minimalna (i zabezpieczasz to
>> założenie odpowiednimi ograniczeniami) po czym dokonujesz jej
>> maksymalizacji.
>
> Nie jestem pewny, ale chyba sie mylisz. Czy takie zadanie miesci sie w ramach
programowania liniowego. Jesli pozostale funkcje przerobimy na warunki, to funkcja
celu stanie sie jakas dziwna: jej wartosc nie bedzie zalezala tylko od
optymalizowanej funkcji, ale takze od warunkow. Jesli ktorys z warunkow spadnie
ponizej optymalizowanej funkcji, to funkcja celu bedzie rowna temu warunkowi. Wlasnie
ulozylem takie zadanie w calcu i uzylem slovera. Ladnie policzyl dla pierwszej
funkcji, ale dla drugiej krzyknal ze zadanie jest nierealistyczne. Nie umial
maksymalizowac drugiej funkcji pod warunkiem ze jest mniejsza od wszystkich
pozostalych funkcji. Moze sie zdarzyc ze jedna z funkcji zawsze bedzie wieksza od
ktorejs z pozostalych dla dowolnych wartosci x.
>

Chyba sie jednak nie myle, dlaczego to nie mialby byc problem PL?
Wszystkie ograniczenia i funkcja celu sa w postaci liniowej.

Jeżeli chodzi o to że funkcja celu zależy od warunków: Twój podproblem
PL szuka maksymalnej wartości funkcji f_k przy założeniu że jest ona
mniejsza równa od pozostałych (czyli minimalna). W ujęciu formalnym ona
nie zależy od warunków. Warunki zabezpieczają to, że to akurat f_k jest
funkcją minimalną. Nie ma w tym niczego dziwnego - to typowe przy PL.

Jeżeli jeden z problemów jest niespełnialny to znaczy ze dana funkcja
celu nigdy nie bedzie mniejsza równa od pozostałych, stad też nie moze
byc rozwiazaniem twojego problemu - to jest ok, spojrz chociazby na taki
przyklad:

z1 = {0},
z2 ={1},
f_1 = 0 * x
f_2 = 1 * x

W takim przypadku f_2 nigdy nie bedzie minimalna. Stad twoj "podproblem"
dla k=2 nie ma rozwiazania dopuszczalnego. Co nie zmienia faktu ze
calosc dziala.

Wydaje mi się,że możesz nawet ułożyc jeden problem PL który zagreguje
wybór najlepszego rozwiązania spośród twoich "podproblemow".
Prawdopodobnie musialbys zastosowac zmienne sztuczne.

do góry

W dniu wtorek, 25 września 2012 22:11:49 UTC+2 użytkownik bartekltg napisał:
> Trochę gdybania i gorszych metod. Jak Ci się spieszy,
> leć od razu do 'rozwiązanie właściwe'
Ok, po mału, bo nie ogarniam :)

> Super. x1+.. +x8 = 0
To moja pomyłka, przepraszam.
> Dalej zakładam, że miało być x1+x2+...+x8 = 1
Tak, o to chodzilo.
> Zamiast jeden można podstawić sobie epsylon.
Tak.
> 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.
Tak.


> Minimum jest z tych 3 funkcji, a po czym jest maksimum?
Maksimum jest po x. Wektor p i sposob budowania macierzy z
ktos nam narzuca. Mozemy operowac tylko na x.

> Nie wyzarzaniem;) Już zwykłe MC będzie lepsze:)
Zgadza się. Moja wersja procedury optymalizacyjnej
jest dość odlegla od wyzarzania, jednak nie wiem jak
jak nazwac i mowie "odmiana wyzarzania".

> 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] )
Chyba tak.

> W dodatku wypukła/wklęsła.
Raczej niewypukla/niewklesla. Ma dużo plaskich miejsc. Glupia procedura
optymalizacyjna nie wie gdzie skoczyc gdy jest na plaskim miejscu.

> Im prostsza, tym lepsza. Matalbowskiego fminsearch trzeba nieco
> podpuscić, aby to dobrze rozwiązywał.
Gdy moja podpuszczalem przez rozne modyfikacje funkcji celu, to
dzialalo ciut gorzej. Moze zle to robilem.

> Ale nadal, to funkcje liniowe. Gdzie będzie rozwiązanie?
> Na rogach, na przecięciu f1=f2=f3 i brzegu kostki/warunków
Nie jest az tak prosto. Czasami dla zadnych x nie zachodzi f1=f2=f3.
Wtedy rozwiazanie jest np. gdy f1=f2, a f3>f1.

> sumowania, albo brzego i równości dwóch.
> W rzeczywistości obstawiam równość wszystkich trzech (mają
> dodatnie współczynniki...)
Sprawdzalem, to zwodzi. Czesto jest f1=f2 i f3>f1 dla dowolnych x.




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


> Wybieramy jakiś wektor x z tej płaszczyzny, rzutujemy
> na wektorki z1,z2,z3 i bierzemy najmniejszy rzut.
> Bierzemy największy.
Hmmm nie kumam.

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

> Wyjdą z tego trzy hiperpłaszczyzny. One nas
> ograniczają. Jednocześnie próbujemy dostać
> się jak najbliżej centrum.
Dlaczego jak najblizej centrum?
> Powstanie nam fragment wielościanu wypukłego.
> [Ciach mętna interpretacja geometryczna]
Bylo ciekawie :)

> 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
W oryginalne bylo zi*x >= 0. zi[j] może zawierac {0,1,p[j]}. Rozumiem
ze zmieniasz w okreslonym celu.

> x>0 (w znaczeniu x[i] > 0)
W oryginale x[i]>=0, ale ok.

> 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.
Nie wiem co oznacza ten zapis [1,1,1...1]*x.

> 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.
Na razie nic nie zrozumialem. Jutro sprobuje jeszcze raz
przeczytac :)

Pozdrawiam
P.S.
Solver liniowy w arkuszu nie rozwiazuje tego :/

do góry