Kamil Bęczyński

Kamil Bęczyński R, SAS, analizy

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Cześć, czy znacie jakiś algorytm który rozwiązuje układ równań liniowych o tylko binarnych zmiennych ? Przy czym układ równań może nie być pełny, ale nie jest sprzeczny. Wydaje mi się, że problem jest bardziej skomplikowany, niż modyfikacja algorytmy eliminacji gaussowskiej polegająca na dodaniu rozbijania danego równania układu na k równań w przypadku, gdy równanie to ma k zmiennych i ich suma wynosi k.
Pozdrawiam
Filip Gurgul

Filip Gurgul Analityk i
Wykładowca

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Może nie palnę głupotę ale wydaje mi sie że taki układ można rozwiązać za pomocą algorytmu programowania całkowitego.
Kamil Bęczyński

Kamil Bęczyński R, SAS, analizy

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Niestety nie jest to problem maksymalizacji/minimalizacji. Można go w takowy zamienić, jednak pozostanie problem zmiennych nieidentyfikowalnych. Być może jakieś implementacji programowania całkowitego, identyfikują takowe zmienne, więc to dobry trop. Pozdrawiam
Filip Gurgul

Filip Gurgul Analityk i
Wykładowca

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Chodziło mi o samo postępowanie. W programowaniu całkowitym postępujemy tak: liczymy zwyczajnym simpleksem zadanie. Potem ustalamy jeden parametr na całkowity, liczymy jeszcze raz (z ustalonym już jednym parametrem), ustalamy nastepny parametr itd. Może można podobnie postąpić z rozwiązywaniem równań.
Grzegorz Melniczak

Grzegorz Melniczak Have you tried
turning it off and
on again?

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Wydaje mi się, że algorytm genetyczny powinien sobie z tym poradzić.

konto usunięte

Temat: Jaki algorytm rozwiązuje układ równań liniowych o...

Kamil Bęczyński:
Cześć, czy znacie jakiś algorytm który rozwiązuje układ równań liniowych o tylko binarnych zmiennych ? Przy czym układ
Z tego co pisałeś to rozumiem, że wynik ma być całkowito-liczbowy.
równań może nie być pełny, ale nie jest sprzeczny. Wydaje mi
Jak ustaliłeś, że nie jest sprzeczny?
się, że problem jest bardziej skomplikowany, niż modyfikacja algorytmy eliminacji gaussowskiej polegająca na dodaniu rozbijania danego równania układu na k równań w przypadku, gdy równanie to ma k zmiennych i ich suma wynosi k.
Każdy solver do problemu programowania całkowito-liczbowego jest w stanie poradzić sobie z takim zadaniem. Przynajmniej teoretycznie.
To czego szukasz to rozwiązania dopuszczalnego. Aby to uzyskać w funkcji celu wystarczy wpisać 0.

Spójrz też na to: http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_e...

Jeśli są to zmienne o wartościach ze zbioru {0,1} to być może podejście oparte na programowaniu w logice z więzami byłoby dobre.

Co do proponowanego algorytmu genetycznego to nie widzę sensu stosowania do takiego problemu. Co więcej za mało wiadomo o problemie bo może być tak, że klasyczny AG może kompletnie nie poradzić sobie, np. jak obszar dopuszczalny nie jest jednospójny.

Następna dyskusja:

układ równań




Wyślij zaproszenie do