Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m35ko:ilpbin [2015/05/23 18:22]
velekmar vytvořeno
+++ courses:a4m35ko:ilpbin [2025/01/03 18:29] (aktuální)
@@ Řádek 5: / Řádek 5: @@
 Zde bude nastíněn universální přístup na příkladu ze slajdů, který by měl být podproben kritice, neb není dokázán.
-) Z pravdivostní tabulky vyberte řádek, který má hodnotu 0 a zapište ho jako maxterm. (součtová forma a + b + c). Maxterm je vyjádřen podobně jako u Karn. map. Kde je v proměnné 1, značí negaci proměnné.
+) Z pravdivostní tabulky vyberte řádek, který má hodnotu 0 a zapište ho jako maxterm. (součtová forma a + b + c). Maxterm je vyjádřen podobně jako u Karn. map. Když je v proměnné 1, značí negaci proměnné.
-) 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).
+) 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).
-) 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.
+) 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ů =====
 <code>
 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.
--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-x1+1-x3 >= 1 ===> -x1-x3 >= -1 ===> x1 + x3 <= 1
+) -(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
-(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
+) (x1)+(1-x2) >= 1 ===> x1 - x2 >= 0
--((x1)+(1-x2)) >= 1 => -x1 + x2 >= 2, nelze splnit
+) -((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
 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
-......
+) x4 + x5 >= 1
+) -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
+) (1-x4)+(1-x5) >= 1 ===> -x4 – x5 >= -1 ===> x4 + x5 <= 1
-(1-x1)+(1-x2) + x3 != 0,
+) -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>

courses/a4m35ko/ilpbin.1432398176.txt.gz · Poslední úprava: 2025/01/03 18:25 (upraveno mimo DokuWiki)

Nahoru