Ho fatto a mano.
In effetti dovrebbero esistere metodi di ottimizzazione "teoricamente"
esatti.
Però, come dicevo, sono tutti NP e richiedono un numero enorme di
calcoli se il numero di elementi da ordinare supera un certo livello.
Quindi, normalmente non vengono implementati su un foglio di calcolo.
Non ho dati precisi sulla complessità computazionale di questi metodi.
Per farti un'idea puoi però pensare alla soluzione di un sistema di N
equazioni lineari. Se usi il metodo di eliminazione di Gauss il numero
di moltiplicazioni è dell'ordine di N al cubo (algoritmo polinomiale).
Se usi il metodo di Cramer, teoricamente bellissimo, senza usare N+1
volte il metodo di Gauss per calcolare i determinanti, le
moltiplicazioni diventano (N+1)! (algoritmo NON polinomiale). Su un
esempio concreto, un sistema di 20 equazioni in 20 incognite richiede
circa 10.000 moltiplicazioni con Gauss e circa 21! moltiplicazioni con
Cramer, quindi un calcolatore che esegue un milione di operazioni al
secondo impiegherebbe meno di un secondo con il primo metodo e circa
1.620.083 anni con il secondo. Meglio lasciar perdere ;-)
Non so se esistano algoritmi iterativi possono essere arrestati dopo
un numero prefissato di operazioni anche se non sono ancora pervenuti
alla soluzione esatta, ma solo ad una sua "buona" approssimazione. In
fin dei conti è quello che stavamo facendo a mano. Si parte dal metodo
ABCCBAABC... e poi si incominciano a spostare delle fatture da un
gruppo all'altro . Se la soluzione migliora, si riparte da questa e
così via.
Quale è il sistema per cercare di migliorare la suddivisione? Se
provassi spostando tutte le N fatture, dovrei fare N!/(N/3)!
tentativi. Devo trovarmi un metodo più smart! Quale? Non saprei.
Andrea
Il giorno 12 gennaio 2018 15:34, Giuseppe Imbesi
<giuseppe.imbesi68@gmail.com <mailto:giuseppe.imbesi68@gmail.com>> ha
scritto:
Grazie Andrea Celli,
si, ovviamente sembra tutto più equilibrato.
Hai "aggiustato a mano" o utilizzato un algoritmo diverso da
quello che ho applicato io?
E, nella seconda ipotesi, è implementabile su un foglio di calcolo?
Più in generale, esistono altri metodi, più raffinati e precisi,
ma egualmente utiilzzabili con calc,
per risolvere il problema? Pur non essendo un matematico, la cosa
mi intriga?
Il giorno 12 gennaio 2018 15:21, Andrea Celli
<a.celli.casa@gmail.com <mailto:a.celli.casa@gmail.com>> ha scritto:
Così, salvo errori, mi sembra che si riequilibri un po' tutto:
1 € 7.486,83 € 7.486,83
2 € 7.260,90 € 7.260,90
3 € 5.584,24 € 5.584,24
4 € 437,74 € 437,74
5 € 364,78 € 364,78
6 € 364,78 € 217,50
7 € 108,75 € 217,50
8 € 21.608,02 € 108,75
9
€ 108,75
€ 21.786,99
1 € 10.560,53 € 10.560,53
2 € 2.188,68 € 2.188,68
3 € 2.188,68 € 2.188,68
4 € 2.141,10 € 2.141,10
5 € 1.800,00 € 1.800,00
6 € 1.459,12 € 1.459,12
7 € 692,03 € 692,03
8 € 510,69 € 510,69
9 € 217,50 € 217,50
€ 217,50
€ 21.975,83 € 21.758,33
1 € 4.517,65 € 4.517,65
2 € 3.995,07 € 3.995,07
3 € 3.647,80 € 3.647,80
4 € 3.144,69 € 3.144,69
5 € 2.918,24 € 2.918,24
6 € 2.188,68 € 2.188,68
7 € 345,81 € 345,81
8 € 291,82 € 291,82
9 € 217,50 € 217,50
10 € 217,50 € 364,78
€ 108,75
€ 21.593,51 € 21.632,04
Un po' alla volta mi tornano in mente altri particolari sul
lavoro matematico che avevo visto una trentina di anni fa.
Passa il tempo e la memoria :-((
Se ben ricordo esistono algoritmi per risolvere esattamente il
problema, ma quelli noti sono tutti NP, Non Polinomiali. Ossia
il numero di operazioni richieste cresce in modo esponenziale
con il numero degli elementi da riorganizzare e quindi sono
utilizzabili solo su insiemi molto piccoli.
Andrea
Il giorno 12 gennaio 2018 00:52, Giuseppe Imbesi
<giuseppe.imbesi68@gmail.com
<mailto:giuseppe.imbesi68@gmail.com>> ha scritto:
Ringrazio tutti per l'interessamento.
Nello specifico, i valori sono i seguenti (già ordinati)
€ 10.560,53
€ 7.486,83
€ 7.260,90
€ 5.584,24
€ 4.517,65
€ 3.995,07
€ 3.647,80
€ 3.144,69
€ 2.918,24
€ 2.188,68
€ 2.188,68
€ 2.188,68
€ 2.141,10
€ 1.800,00
€ 1.459,12
€ 692,03
€ 510,69
€ 437,74
€ 364,78
€ 364,78
€ 345,81
€ 291,82
€ 217,50
€ 217,50
€ 217,50
€ 217,50
€ 108,75
€ 108,75
Utilizzando il metodo di Mario Graziani, ottengo la
seguente suddivisione:
Gruppo A, 9 elementi
€ 10.560,53 A
€ 3.995,07 A
€ 3.647,80 A
€ 2.188,68 A
€ 2.141,10 A
€ 437,74 A
€ 364,78 A
€ 217,50 A
€ 217,50 A
Totale € 23.770,70
Gruppo B, 9 elementi
€ 7.486,83 B
€ 4.517,65 B
€ 3.144,69 B
€ 2.188,68 B
€ 1.800,00 B
€ 510,69 B
€ 364,78 B
€ 217,50 B
€ 217,50 B
Totale € 20.448,32
Gruppo C, 10 elementi
€ 7.260,90 C
€ 5.584,24 C
€ 2.918,24 C
€ 2.188,68 C
€ 1.459,12 C
€ 692,03 C
€ 345,81 C
€ 291,82 C
€ 108,75 C
€ 108,75 C
Totale € 20.958,34
-----------------------------------------------------------------------------------
Con aggiustamenti "a mano" (ed un bel pò di perdita di
tempo) ho ottenuto questo risultato
(ossia somma dei valori di ciascun gruppo più vicini tra
loro ma numero di pratiche per gruppo non omogeneo)
€ 7.486,83
€ 7.260,90
€ 5.584,24
€ 437,74
€ 364,78
€ 364,78
€ 108,75
Tot.€ 21.608,02 (7 pratiche)
€ 10.560,53
€ 2.188,68
€ 2.188,68
€ 2.141,10
€ 1.800,00
€ 1.459,12
€ 692,03
€ 510,69
€ 217,50
€ 217,50
Tot € 21.975,83 (10 pratiche)
€ 4.517,65
€ 3.995,07
€ 3.647,80
€ 3.144,69
€ 2.918,24
€ 2.188,68
€ 345,81
€ 291,82
€ 217,50
€ 217,50
€ 108,75
Tot. € 21.593,51 (11 pratiche)
Mi pare di capire che le due condizioni (eguaglianza della
somma dei valori di ciascun gruppo e del numero di
pratiche per gruppo) non possano essere contemporaneamente
soddisfatte: il rispetto dell'una esclude l'altra..
<https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
Mail priva di virus. www.avast.com
<https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
Il giorno 11 gennaio 2018 19:23, Andrea Celli
<a.celli.casa@gmail.com <mailto:a.celli.casa@gmail.com>>
ha scritto:
Grosso modo è il metodo con cui si formano le squadre
di calcio a scuola o
tra amici: ogni capitano sceglie a turno un giocatore.
Il primo sceglie il
più forte, il secondo e poi il terzo scelgono i
migliori tra i rimanenti.
Il metodo migliora se ad ogni tornata si inverte
l'ordine di scelta. Ossia,
se chiamo A, B e C i capitani, l'ordine di scelta è
ABCCBAABCCBA...
Ricordo di aver visto su una rivista di matematica un
articolo in cui si
dimostrava che la soluzione così ottenuta non si
discosta troppo dalla
soluzione ottima, squadre il più possibile equivalenti.
Per capire che questa non è la soluzione ottima basta
pensare che tra i
giocatori ci siano Messi e tanti ragazzi bravi ma non
bravissimi. Per
compensare un po' il vantaggio del capitano A (che
ovviamente sceglie
Messi) questo deve stare fermo nei turni successivi
per poi prendere i
giocatori lasciati liberi dagli altri.
Andrea
Il giorno 11 gennaio 2018 13:03, Carlo Magistrelli
<carlo@magistrelli.it <mailto:carlo@magistrelli.it>>
ha scritto:
> Sì, concordo con le giuste osservazioni di Mario
Graziani
>
> Ciao
>
> Carlo
>
> Il giorno 11 gennaio 2018 12:33, Mario Graziani
<mario@graziani.net <mailto:mario@graziani.net>> ha
> scritto:
>
> > Ciao
> >
> > meglio sarebbe nel caso di tre gruppi assegnare
> > al gruppo A il primo e poi il sesto della lista
> > al gruppo B il secondo e poi il quinto della lista
> > al gruppo C il terzo e poi il quarto della lista
> > e poi i successivi con la solita sequenza:
> > gruppo A 1,6,7,12 etc
> >
> > per farlo basta creare una colonna gruppo e dopo
aver ordinato per valore
> > inserire per i primi sei valori uno per riga
> > A B C C B A
> > e poi copiare fino alla fine dei valori
> >
> > altrimenti il gruppo A sarà sempre maggiore di B e
B sarà maggiore di C
> > il tutto funziona abbastanza se i valori sono
tanti e non ci sono salti
> > improvvisi
> > e se il totale non deve risultare essere
necessariamente esattamente
> > uguale per i tre gruppi
> >
> > un saluto
> >
> > --
> >
> > M a r i o G r a z i a n i
> >
> > GRAZIANI srl
> >
> > Z.Ind.Pian di Laura
> > 56043 LORENZANA (PI)
> > ITALIA
> >
> > [ t ] +39 0586 421421 <tel:%2B39%200586%20421421>
> > [ f ] +39 0586 069609 <tel:%2B39%200586%20069609>
> > [ w ] www.graziani.net <http://www.graziani.net>
> > [ @ ] mario@graziani.net <mailto:mario@graziani.net>
> >
> >
> > Il 11/01/2018 09:24, Carlo Magistrelli ha scritto:
> >
> >> Ciao.
> >>
> >> Se i valori delle controversie sono abbastanza
numerosi e variati, forse
> >> si
> >> può ragionare così:
> >> a) Ordinare in senso crescente (o decrescente) i
record per valore della
> >> controversia
> >> b) (caso due gruppi) Assegnare al gruppo 1 tutte
le controversie di
> ordine
> >> dispari (1° 3° ecc.) e al gruppo 2 tutte quelle
di ordine pari (2° 4°
> >> ecc.)
> >> c) (caso tre gruppi) Assegnare al gruppo 1 tutte
le controversie 1+nx3
> (1°
> >> 4° 7° ecc), al gruppo 2 le ctr. 2+nx3 (2° 5° 8°
ecc), al gruppo 3 le
> ctr.
> >> 3+nx3 (3° 6° 9° ecc).
> >> d) Raggruppare in base al codice di gruppo
assegnato al passo
> precedente.
> >>
> >> Ciao
> >>
> >> Carlo
> >>
> >>
> >>
> >> Il giorno 10 gennaio 2018 21:17, Giuseppe Imbesi <
> >> giuseppe.imbesi68@gmail.com
<mailto:giuseppe.imbesi68@gmail.com>> ha scritto:
> >>
> >> Salve a tutti.
> >>> E' il mio primo messaggio, perdonate eventuali
off-topic.
> >>>
> >>> Premetto che ho urgenza di trovare una soluzione
e non sono
> assolutamente
> >>> esperto né di programmazione né di statistica
(laurea in legge)
> >>>
> >>> Ho un foglio di calc contenente una serie di
record con i seguenti
> campi:
> >>> nome controparte, sintesi fatti di causa,
importo controversia.
> >>>
> >>> L'importo della controversia è ovviamente
variabile, si va dai 10mila
> >>> euro
> >>> ai 100.
> >>>
> >>> Devo suddividere i record in gruppi omogenei (2
o 3, ancora non ho
> >>> deciso).
> >>>
> >>> Nello specifico:
> >>>
> >>> 1) la somma degli importi delle controversie
di ciascun gruppo deve
> >>> dare
> >>> lo stesso totale (o valori che siano i più
vicini possibile)
> >>> 2) ciascun gruppo deve contenere lo stesso
numero di record
> >>>
> >>> E' possibile far si che calc suddivida in
automatico i record nei tre
> >>> gruppi, indicando per ciascun gruppo il totale
degli importi ed il
> numero
> >>> dei record?
> >>>
> >>> Grazie in anticipo.
> >>>
> >>> --
> >>> Come cancellarsi: E-mail
users+unsubscribe@it.libreoffice.org
<mailto:users%2Bunsubscribe@it.libreoffice.org>
> >>> Problemi?
https://it.libreoffice.org/supporto/mailing-lists/come-
<https://it.libreoffice.org/supporto/mailing-lists/come->
> >>> cancellarsi/
> >>> Linee guida per postare + altro: https://wiki.
> >>> documentfoundation.org/Local_Mailing_Lists/it
<http://documentfoundation.org/Local_Mailing_Lists/it>
> >>> Archivio della lista:
https://listarchives.libreoffice.org/it/users/
<https://listarchives.libreoffice.org/it/users/>
> >>> Tutti i messaggi inviati a questa lista vengono
archiviati
> pubblicamente
> >>> e
> >>> non sono eliminabili
> >>>
> >>>
> >
> > --
> > Come cancellarsi: E-mail
users+unsubscribe@it.libreoffice.org
<mailto:users%2Bunsubscribe@it.libreoffice.org>
> > Problemi?
https://it.libreoffice.org/supporto/mailing-lists/come-cance
<https://it.libreoffice.org/supporto/mailing-lists/come-cance>
> > llarsi/
> > Linee guida per postare + altro:
https://wiki.documentfoundatio
> > n.org/Local_Mailing_Lists/it
<http://n.org/Local_Mailing_Lists/it>
> > Archivio della lista:
https://listarchives.libreoffice.org/it/users/
<https://listarchives.libreoffice.org/it/users/>
> > Tutti i messaggi inviati a questa lista vengono
archiviati pubblicamente
> e
> > non sono eliminabili
> >
>
> --
> Come cancellarsi: E-mail
users+unsubscribe@it.libreoffice.org
<mailto:users%2Bunsubscribe@it.libreoffice.org>
> Problemi?
https://it.libreoffice.org/supporto/mailing-lists/come-
<https://it.libreoffice.org/supporto/mailing-lists/come->
> cancellarsi/
> Linee guida per postare + altro: https://wiki.
> documentfoundation.org/Local_Mailing_Lists/it
<http://documentfoundation.org/Local_Mailing_Lists/it>
> Archivio della lista:
https://listarchives.libreoffice.org/it/users/
<https://listarchives.libreoffice.org/it/users/>
> Tutti i messaggi inviati a questa lista vengono
archiviati pubblicamente e
> non sono eliminabili
>
--
Come cancellarsi: E-mail
users+unsubscribe@it.libreoffice.org
<mailto:users%2Bunsubscribe@it.libreoffice.org>
Problemi?
https://it.libreoffice.org/supporto/mailing-lists/come-cancellarsi/
<https://it.libreoffice.org/supporto/mailing-lists/come-cancellarsi/>
Linee guida per postare + altro:
https://wiki.documentfoundation.org/Local_Mailing_Lists/it
<https://wiki.documentfoundation.org/Local_Mailing_Lists/it>
Archivio della lista:
https://listarchives.libreoffice.org/it/users/
<https://listarchives.libreoffice.org/it/users/>
Tutti i messaggi inviati a questa lista vengono
archiviati pubblicamente e non sono eliminabili