Algoritmus pre riešenie systémov lineárnych nerovností - lineárna algebra

Mám k lineárne nerovnosti v n premenných (0 <k <n). Nevadí mi to, čo je to riešenie, chcem len otestovať, či je alebo nie je prázdny - t akýkoľvek priradenie k mojim n premenným vyhovuje systému. Každý, kto vie, ako to vyriešiť?

Vďaka!

odpovede:

Môžete to urobiť pomocou tlačidla a lineárne programovanie s konštantnou objektívnou funkciou. To je len kontrola uskutočniteľnosť programu.

Použite SMT riešiteľ pre teóriu lineárnejaritmetika (Yices, Z3, ...). Tieto programy sú určené na vyhľadanie modelov pre zadaný vstup. Existujúce algoritmy môžete samozrejme využívať aj inými spôsobmi.

Na riešenie systému nerovností môžete použiť Fourier-Motzkinovu elimináciu. Budete musieť poznať základné algebry pochopiť riešenie hoci.

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Stačí len pretiahnuť rozsahy. Tu je návod, ako v pseudokóde:

// An array that has the ranges (inequalities) to test:
fromToArray = [[0, 10], [5, 20], [-5, Infinity]]

currentRange = [-Infinity, Infinity];
for each pair myRange in fromToArray
if currentRange[0] < myRange[0]
then currentRange[0] = myRange[0]
if currentRange[1] > myRange[1]
then currentRange[1] = myRange[1]
if currentRange[0] >= currentRange[1]    // from greater than to, so set is empty.
then return "NO SOLUTION"
end for each

return "Solution is: " + currentRange

Vypočítajte determinant príslušnej matice; ak je nenulové, existuje jedinečné riešenie, ak je nula, existuje buď nekonečne veľa riešení alebo žiadne - http://en.wikipedia.org/wiki/System_of_linear_equations

Alebo použite Gaussovu elimináciu - http://en.wikipedia.org/wiki/Gaussian_elimination