navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m35ko:ilpbin [2015/05/24 18:12] velekmar [ILP Vyjádření logických formulí] |
courses:a4m35ko:ilpbin [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 9: | Řádek 9: | ||
| 2) Výsledný maxterm nám říká; tato kombinace se rovná nepřípustné vlastnosti. Položíme nerovnost a negace proměnných nahradíme výrazem (1 - x). | 2) Výsledný maxterm nám říká; tato kombinace se rovná nepřípustné vlastnosti. Položíme nerovnost a negace proměnných nahradíme výrazem (1 - x). | ||
| - | 3) Rozepíšeme rovnici na formu vhodnou do ILP. Podmínka x != y je ekvivaletní |x - y| >= 1. Vzhledem k nulovosti y se podmínka redukuje na |x| >= 1. Vypočteme dva případy, -(x) >= 1 a (x) >= 1. Pokud některá z rovnic je nesplnitelná (za x lze dosazovat pouze 0 nebo 1), případně splnitelná vždy, neuvažujeme ji. | + | 3) Rozepíšeme rovnici na formu vhodnou do ILP. Podmínka x != y je ekvivaletní |x - y| >= 1 (možné jsou pouze celočíslené proměnné). Vzhledem k nulovosti y se podmínka redukuje na |x| >= 1. Vypočteme dva případy, -(x) >= 1 a (x) >= 1. Pokud některá z rovnic je nesplnitelná (za x lze dosazovat pouze 0 nebo 1), případně splnitelná vždy, neuvažujeme ji. |
| ===== Příklad ze slajdů ===== | ===== Příklad ze slajdů ===== | ||
| <code> | <code> | ||
| + | |||
| a) jestliže je dům 1 vybrán, potom není vybrán dům 3 | a) jestliže je dům 1 vybrán, potom není vybrán dům 3 | ||
| - | Tabulka má 0 v řádká x1 = 1, x3 = 1. Vytvoříme maxterm (1-x1)+(1-x3) != 0, (1-x1)+(1-x3) > 0 nebo (1-x1)+(1-x3) < 0. | + | Tabulka má 0 v řádká x1 = 1, x3 = 1. |
| - | 1-x1+1-x3 >= 1 => -x1-x3 >= -1 => x1 + x3 <= 1 | + | Vytvoříme maxterm (1-x1)+(1-x3) != 0, |
| - | -(1-x1+1-x3) >= 1 => -2 + x1 + x3 >= 1 ===> x1 + x3 >= 3, nelze splnit | + | |(1-x1)+(1-x3)| >= 1 |
| + | 1) 1-x1+1-x3 >= 1 ===> -x1-x3 >= -1 ===> x1 + x3 <= 1 | ||
| + | 2) -(1-x1+1-x3) >= 1 ===> -2 + x1 + x3 >= 1 ===> x1 + x3 >= 3, nelze splnit | ||
| + | Řešení 1) | ||
| b)jestliže je dům 2 vybrán, potom musí být vybrán i dům 1 | b)jestliže je dům 2 vybrán, potom musí být vybrán i dům 1 | ||
| - | (x1)+(1-x2) != 0, (x1)+(1-x2) > 0 nebo (x1)+(1-x2) < 0 | + | (x1)+(1-x2) != 0 ===> |(x1)+(1-x2)| >= 1 |
| - | (x1)+(1-x2) >= 1 => x1 - x2 >= 0 | + | 1) (x1)+(1-x2) >= 1 ===> x1 - x2 >= 0 |
| - | -((x1)+(1-x2)) >= 1 => -x1 + x2 >= 2, nelze splnit | + | 2) -((x1)+(1-x2)) >= 1 ===> -x1 + x2 >= 2, nelze splnit |
| + | Řešení 1) | ||
| c) buď je vybrán dům 4 nebo dům 5, ale ne oba | c) buď je vybrán dům 4 nebo dům 5, ale ne oba | ||
| Zde jsou dvě možnosti, budou čtyři výsledné nerovnice | Zde jsou dvě možnosti, budou čtyři výsledné nerovnice | ||
| - | (x4)+(x5) != 0, (x4)+(x5) > 0 nebo (x4)+(x5) < 0 | + | (x4)+(x5) != 0 ===> |(x4)+(x5)| >= 1 |
| - | (1-x4)+(1-x5) != 0, (1-x4)+(1-x5) > 0 nebo (1-x4)+(1-x5) < 0 | + | (1-x4)+(1-x5) != 0 ===> |(1-x4)+(1-x5)| >= 1 |
| - | ...... | + | 1) x4 + x5 >= 1 |
| - | + | 2) -x4 -x5 >= 1, nelze splnit | |
| - | d) pokud jsou vybrány domy 1 a 2 zároveň, pak musí být vybrán i dům 3 | + | 3) (1-x4)+(1-x5) >= 1 ===> -x4 – x5 >= -1 ===> x4 + x5 <= 1 |
| - | (1-x1)+(1-x2) + x3 != 0, | + | 4) -1+ x4 – 1 + x5 >= 1 ===> x4 + x5 >= 3, nelze splnit |
| - | (1-x1)+(1-x2) + x3 > 0 nebo | + | z 1) a 3) vyplývá x4 + x5 = 1 |
| - | (1-x1)+(1-x2) + x3 < 0 | + | |
| - | + | ||
| - | + | ||
| - | (1-x1)+(1-x2) + x3 >= 1 => x1 + x2 - x3 <= 1 | + | |
| - | -((1-x1)+(1-x2) + x3) >= 1 => x1 + x2 - x3 >= 3, nelze splnit | + | |
| </code> | </code> | ||
