Newsgroup: it.comp.lang.visual-basic
Titolo: Come risolvereste questo problema?

1 - Fisso un insieme di numeri interi (per esempio 40,41,42,43)
2 - Dico che A è composto da 1 numero 40, da 2 numeri 41, da 2 numeri 
42, da 1 numero 43
2 - Dico che B è composto da 1 numero 40, da 2 numeri 41, da 1 numero 42
2 - Dico che C è composto da 1 numero 41, da 2 numeri 42, da 1 numero 43
In altri termini ho:
   40  41  42  43
A  1   2   2   1
B  1   2   1
C      1   2   1
A questo punto immaginiamo di avere a disposizione 5 numeri 40, 8 numeri 
  41, 8 numeri 42 e 5 numeri 43 (una specie di termine noto)
Ossia:
40 41 42 43
  5  8  8  5
Il problema è trovare quanti A, B e C posso avere tali per cui siano 
MINIMI i numeri che rimangono fuori dalla selezione. Per esempio se 
scelgo 1 di A, 1 di B ed 1 di C avrò che:
              40 41 42 43                40 41 42 43
  A +  B +  C  2  5  5  2 e mi rimangono  3  3  3  3 = 12 numeri fuori
2A +  B +  C  3  7  7  3 e mi rimangono  2  1  1  2 =  6 numeri fuori
  A + 2B +  C  3  7  6  2 e mi rimangono  2  1  2  3 =  8 numeri fuori
  A +  B + 2C  2  6  7  3 e mi rimangono  3  2  1  2 =  8 numeri fuori
  A +  B + 2C  2  6  7  3 e mi rimangono  3  2  1  2 =  8 numeri fuori
...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...
4A + 0B + 0C  4  8  8  4 e mi rimangono  1  0  0  1 =  2 numeri fuori
eccetera
Per un caso così semplice la soluzione migliore sembra essere 4A perchè 
mi lascia fuori dagli iniziali 5 8 8 5 solo 1 numero 40 ed un numero 43.
Ma per casi più complessi come si può fare? A prima vista sembrerebbe un 
caso di un sistema di eq. lin. con numero di incognite maggiore del 
numero di equazioni. Voi che approccio seguireste?
Giovanni.

 numero di equazioni. Voi che approccio seguireste?
Questo è un problema di programmazione lineare intera, mi sembra che si debba
applicare l'algoritmo del simplesso (per trovare una soluzione ottima, ma nel
"continuo") + il cosiddetto "branch and bound" per ottenere (enumerativamente)
l'ottimo nel campo discreto.
Almeno queste sono le mie reminiscenze dal corso di ricerca operativa... google
(e forse un buon testo) possono poi aiutarti ulteriormente.
Bye
Raf
-----------------------------------------------------
Funk: cooler than the other side of the pillow.

 ha scritto nel messaggio 
news:461f5...@x-privat.org...


Hai ragione g.
Ho dimenticato di precisare che non sono ammessi valori negativi per le 
numerate A, B e C ossia posso avere al massimo 4A+B+C che è comunque 
peggiorativa rispetto a 4A
g ha scritto:


 ha scritto nel messaggio 
news:461fed5f$1...@x-privat.org...


Ho iniziato a cercare qualcosa sul metodo del simplesso ma è davvero 
difficile trovare qualcosa di buono e soprattutto fruibile senza molte 
difficoltà. Hai per caso a portata di mano qualche buon link o libro 
ecc. da suggerirmi?
Grazie in anticipo,
Giovanni.
Rafunk ha scritto:


 Giovanni.
Le difficoltà aumentano poi se non hai dimestichezza con l'algebra matriciale.
Non essendo più dentro a questi argomenti da ormai parecchio tempo, posso solo
indirizzarti verso qualche link che a mia volta ho trovato con google.
Ad esempio
http://digilander.libero.it/robicox/dispense/ricercaoperativa/mainricercaoperativa.pdf
Questo programma (con sorgenti e documentazione) di F. Languasco può essere una
buona base di partenza.
http://www.flanguasco.org/VisualBasic/ProgLin.ZIP
Tieni presente che nel tuo caso si tratta di un problema di programmazione
lineare *intera*, quindi il solo metodo del simplesso (che può restituirti una
soluzione ottima *reale*) potrebbe non essere sufficiente.
Ad esempio nel problema che hai esposto la soluzione ottimale (ottenuta col
programma di cui sopra) è effettivamente (4, 0, 0), ossia 4 "A" 0 "B" e 0 "C",
ma metti solo che i "termini noti" fossero diversi, ad es. 5 6 7 8, la soluzione
ottimale del simplesso sarebbe (2.5, 0, 1), che però non è accettabile in quanto
non intera.
In ogni caso quella costituisce un punto di partenza per applicare un successivo
algoritmo come il cosiddetto "Branch and Bound" o altro algoritmo decisionale.
