W dniu 2012-09-26 10:32, M.M. pisze:
> W dniu wtorek, 25 września 2012 22:35:35 UTC+2 użytkownik bartekltg napisał:
>> W dniu 2012-09-25 22:11, bartekltg pisze:
>> 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
>
> Tego potrzebowalem zeby zrozumiec :)

:)

> A co do dowodu poprawnosci. Czy nie wystarczy ze:
> 1) jest to poprawnie zefiniowane zadanie z programowania,
> 2) podczas odtworzenia warunku suma x_i = 1 funkcje skaluja
> sie liniowo (bo sa liniowe), a wiec wszystkie inne warunki
> liniowe nadal beda obowiazywaly?

No, musisz jeszcze pokazać, że to nadal najlepsze rozwiązanie.
Tak, to oczywiste;), ale wolałem dopisać dowód (zresztą, dowodząc
tego znalazłem błąd w pierwszej wersji).


Sprawdziłem przerobioną wersję na oo calc. Nie tylko
znalazł rozwiązanie, ale i okazało się, że fminsearch
zaplątał się i był gorszy o parę %.


Wpadłem rano, jak w miarę prosto 'algebraicznie'
rozwiązywać pierwotny problem, ale algorytm
jest dość podobny, w pewnym momencie radośnie sobie
rzutujemy na jądro pewnej macierzy ograniczeń;)
a do simpleksu jeśli nawet nie masz juz biblioteki,
to łatwiej znaleźć gotowca czy materiały.


W każdym razie szłoby to tak (szkic i nieprzetestowane):

Mamy jakąś propozycję dla x.

Uaktualniamy ją. Nawet o gradeint g = pi, gdzie
pi odpowiada najmniejszej funkcji w x. Tylko teraz
wrzucamy ograniczenia. Pierwszym jest
równość g[1] +.. +g[8] = 0 - to gwarantuje
pozostanie na naszej płaszczyźnie.
Jeśli mamy pi*x == pj*x i jest to najmniejsza
wartość ze wzyctkich pk*x, dodajemy równania
pi[1]*g[1] +.. +pi[8]*g[8]==0
pj[1]*g[1] +.. +pj[8]*g[8]==0

Rzutujemy nasz gradient na jądro mcierzy opisującej
te warunki (kod wygląda lepiej niż to brzmi:).
Dzięki temu nie uciekamy z płaszczyzny oraz nie
zmnijeszamy fi kosztem innych równych co do wartości fj.

Dalej, dla każdej współrzędnej x[i]==0
i g (już ten nowy gradient) g[i]<0
dodajemy warunek g[i]==0.

Powiększamy naszą macierz warunków i powtarzamy operację.

Teraz gorsza część.

patrzymy na wetkro x'=x + t*g. t to skalr.
Rozwiązujemy wszystkie kolizje ze ściankami,
oraz potójne równości pi*x' == pj*x' == pk*x'

Wybieramy najmniejsze dodatnie t, podstawiamy
x< x+t*g
goto start:)


Da się. Jest upierdliwe. Nadal polecam przepisać
simplex z wiki;)


pzdr
bartekltg