Diseguaglianza con soluzioni intere
Buongiorno. Sto postando nella sezione di Algebra semplicemente perché questo problema è sorto studiando un argomento di algebra. In ogni caso è probabile che questa discussione stia meglio in Geometria o forse addirittura nella sezione di Ricerca Operativa. Ma veniamo a noi.
Consideriamo su $\NN ^k$ la relazione d'ordine (parziale) definita da:
$\mathbf{n} \leq mathbf{m}$ se e solo se $n_i \leq m_i$ per ogni $i=1 . . . k$.
Consideriamo poi la diseguaglianza seguente:
$\sum c_i n_i \geq G$
dove sia i $c_i$ sia $G$ sono numeri interi positivi.
Bene. Vorrei capire se c'è un modo per trovare soluzioni minimali di questa diseguaglianza, ovvero vettori $\mathbf{n}$ per cui vale la disuguaglianza e per cui, se $\mathbf{m}$ è una soluzione e $\mathbf{m} \leq \mathbf{n}$, allora $\mathbf{m}=\mathbf{n}$.
Viceversa, nel caso in cui la disuguaglianza sia della forma $\sum c_i n_i \leq G$, vorrei trovare soluzioni massimali.
Giusto per semplificare le cose: nei casi che mi vengono proposti $k$ è al massimo 3 o 4, quindi facendo semplicemente i conti a mano le soluzioni si trovano. Tuttavia potrebbe essere interessante avere un modo per risolvere il caso generale.
Al momento l'unica soluzione che mi è venuta in mente è considerare le uguaglianze ($\sum c_i n_i =G$ , $\sum c_i n_i = G+1$ etc. ), e trovare le loro soluzioni minimali studiando le varie equazioni con l'algoritmo per le equazioni diofantee. Tuttavia in questo modo la cosa diventa decisamente lunga e non mi viene in mente niente che possa suggerire quante equazioni prendere in considerazione (ho pensato, così a naso, al m.c.m. dei $c_i$, ma senza dubbio è troppo).
Vorrei quindi qualche suggerimento su come risolvere il problema.
Grazie fin da ora.
Consideriamo su $\NN ^k$ la relazione d'ordine (parziale) definita da:
$\mathbf{n} \leq mathbf{m}$ se e solo se $n_i \leq m_i$ per ogni $i=1 . . . k$.
Consideriamo poi la diseguaglianza seguente:
$\sum c_i n_i \geq G$
dove sia i $c_i$ sia $G$ sono numeri interi positivi.
Bene. Vorrei capire se c'è un modo per trovare soluzioni minimali di questa diseguaglianza, ovvero vettori $\mathbf{n}$ per cui vale la disuguaglianza e per cui, se $\mathbf{m}$ è una soluzione e $\mathbf{m} \leq \mathbf{n}$, allora $\mathbf{m}=\mathbf{n}$.
Viceversa, nel caso in cui la disuguaglianza sia della forma $\sum c_i n_i \leq G$, vorrei trovare soluzioni massimali.
Giusto per semplificare le cose: nei casi che mi vengono proposti $k$ è al massimo 3 o 4, quindi facendo semplicemente i conti a mano le soluzioni si trovano. Tuttavia potrebbe essere interessante avere un modo per risolvere il caso generale.
Al momento l'unica soluzione che mi è venuta in mente è considerare le uguaglianze ($\sum c_i n_i =G$ , $\sum c_i n_i = G+1$ etc. ), e trovare le loro soluzioni minimali studiando le varie equazioni con l'algoritmo per le equazioni diofantee. Tuttavia in questo modo la cosa diventa decisamente lunga e non mi viene in mente niente che possa suggerire quante equazioni prendere in considerazione (ho pensato, così a naso, al m.c.m. dei $c_i$, ma senza dubbio è troppo).
Vorrei quindi qualche suggerimento su come risolvere il problema.
Grazie fin da ora.
Risposte
Puoi vedere che quella somma si assomiglia moltissimo ad una somma integrale, considera questo rapporto $m=G/{sum(c_i)}$ a questo punto scegli un elemento qualsiasi dello spazio prodotto, un indice $j$ intendo, e prendi il numero intero positivo piu' piccolo maggiore di $m$, $m_j = [m]+1$, o $m$ stesso se è intero, lo moltiplichi per il corrispondente coefficiente $c_j$, sottrai il loro prodotto a $G$, $G_1 = G-m_j * c_j$, ripetere il procedimento fino al termine degli indici disponibili, e forse questa trovata è una soluzione minimale, la definzione sopra della funzione è ricorsiva ovviamente, le soluzioni minimali saranno espresse da un fattoriale, non ve n'è una sola ovviamente. Fammi sapere se va bene.
Ho fatto qualche prova. In questo modo in effetti si dovrebbe ottenere una soluzione minimale. Il mio problema, mi accorgo ora che non sono stato chiaro nel primo post, è che devo trovarle tutte (o almeno contarle tutte, cioè sapere quante sono, per poi cercarle a mano con la sicurezza di non lasciarne fuori qualcuna).
Mi sembra siano $k$ ma possono essere non tutte distinte, non sono certo, ma una cosa è sicura, con il procedimento sopra descritto, che porta certamente ad una soluzione minimale, ci sono $k!$ possibili scelte, iniziando cioè dalla scelta del primo indice, e di sicuro quello è un numero che maggiora il numero massimo di soluzioni minimali. La dimostrazione di questo sta nel fatto che quando hai un valore corrispondente ad un indice che è inferiore al valor medio $m$, vuol dire che devi essere partito, nel procedimento ricorsivo sopra descritto, da un altro indice, perche' non e' possibile trovarli tutti inferiori alla media $m$.
Certo...ma con questo procedimento il valore da cui si parte è sempre 'vicino' a quello medio. Invece possono esserci soluzioni minimali che hanno alcuni valori molto più bassi e altri molto più alti.
Ad esempio:
$2a + 3b \geq 10$
$a=5, b=0$ è certamente una soluzione minimale, ma non può essere trovata con il procedimento che suggerisci.
In generale le soluzioni sono molto più di $k$. In questo caso facile dovrebbero essere:
$a=5, b=0$
$a=4, b=1$
$a=2, b=2$
$a=1, b=3$
$a=0, b=4$
Con il metodo che suggerisci si trova solo $a=2,b=2$. Però forse non ho capito bene il tuo metodo.
Ad esempio:
$2a + 3b \geq 10$
$a=5, b=0$ è certamente una soluzione minimale, ma non può essere trovata con il procedimento che suggerisci.
In generale le soluzioni sono molto più di $k$. In questo caso facile dovrebbero essere:
$a=5, b=0$
$a=4, b=1$
$a=2, b=2$
$a=1, b=3$
$a=0, b=4$
Con il metodo che suggerisci si trova solo $a=2,b=2$. Però forse non ho capito bene il tuo metodo.
No, no, è giusto quello che scrivi. Quello sopra è un metodo per trovarne al massimo $k!$, avevo pensato a quanto hai scritto sopra, in effetti il problema di dire quante soluzioni vi siano non è così semplice.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo