Matematické Fórum

Akcope · 19. 03. 2016 19:43

Zdravím, ve formulaci ILP jsem narazil na následující problém:

Mám 2 matice 1*n proměnných $s_i,x_i$

Chtěl bych vytvořit matici nových proměnných (rozměru n*k, kde k je libovolné celé číslo). Tyto proměnné by měly mít následující vlastnost:

$z_{ij} = \begin{cases} 1 & \text{pokud } j \geq s_i \text{a } j \leq x_i\\ 0 & \text{jinak} \\ \end{cases}$

Např:

$s_i = 4 \\ x_i = 8 \\ z_{i5} = 1$

Chtěl bych se zeptat, jak bych skrz omezení úlohy ILP obecně formuloval $z_{ij}$ ?

Akcope · 20. 03. 2016 20:50

Napadá mě, že otázka by šla přeformulovat do srozumitelnější formy:

$f(x,y,z)= \begin{cases} 1 & \text{pokud } z \geq x \text{a } z \leq y\\ 0 & \text{jinak} \\ \end{cases}$

$x,y,z \in \mathbb{N}$

Ale potřebuji tuto funkci definovat s použitím pouze sčítání, odečítání, násobení a dělení.

Můžu si zadefinovat tolik nových proměnných, funkcí a rovnicí kolik chci, a v rovnicích používat relace rovná se, a neostré nerovná se.

Funkci f můžu dekomponovat takhle:

$f(x,y,z)= g(x,z)h(y,z)$

kde

$g(x,z) = \begin{cases} 1 & \text {pokud } z \geq x \\ \text{0} & \text{jinak} \\ \end{cases}$

$h(y,z) = \begin{cases} 1 & \text {pokud } z \leq y\\ \text{0} & \text{jinak} \\ \end{cases}$

Takže stačí vyřešit jak zadefinovat g a h.

Dostal jsem se dost daleko:

$g(x,z) = \frac{x- \left| x - z \right| -z }{2x - 2z}$

Vim že jsem řekl že můžeme používat jen základní aritmetické operace, ale vím na 100%, že absolutní hodnota může být vytvořena za pomocí pravidel, která jsem výše uvedl. Pro jednoduchost ji uvádím v klasické notaci.

Tato rovnice funguje dobře, až na případy kde x = z . V tom momentě nejen že čitatel nekorektně uvádí nulu, ale dokonce i nulou dělíme.

Mohl by mi prosím někdo poradit jak funkci zobecnit tak, aby fungovala i pro tento případ, popřípadě nastínit důkaz proč je nemožné toto vyřešit (jelikož o tom mám pochyby..). Předem děkuji.

Matematické Fórum

#1 19. 03. 2016 19:43

Celočíselné lineární programování - pomocná binární rozsahová proměnná

#2 20. 03. 2016 20:50

Re: Celočíselné lineární programování - pomocná binární rozsahová proměnná

Zápatí