Newsgroup: it.comp.ia
Titolo: Ho un problema di ottimizzazione

e sto cercando un algoritmo per risolverlo.
Spiego brevemente il problema, riguarda la produzione di certi "articoli"
tramite l'unione di componenti, faccio un esempio:
Devo produrre 10 pezzi dell'articolo A
l'articolo A è composto dalle parti A1, A2, A3
Le parti A1 vengono prodotte alla bisogna in blocchi di 10
Le parti A2 vengono prodotte alla bisogna in blocchi di 10
Le parti A3 vengono prodotte alla bisogna in blocchi di 5
Quindi dovrò per produrre 10 A dovrò prevedere 1 blocco A1, 1 blocco A2, 2
blocchi A3.
E fin qui è facile...
Il problema sono le ottimizzazioni, quando devo produrre più articoli che
hanno componenti comuni.
Il fulcro dell'ottimizzazione è che non devono esserci disavanzi nei
componenti degli articoli.
Es:
devo produrre 10 K e 25 F
l'articolo K è composto dalle parti K1, K2, K3
l'articolo F è composto dalle parti K1, K2, F3
Le parti K1 vengono prodotte alla bisogna in blocchi di 20
Le parti K2 vengono prodotte alla bisogna in blocchi di 20
Le parti K3 vengono prodotte alla bisogna in blocchi di 10
Le parti F3 vengono prodotte alla bisogna in blocchi di 10
Cosa devo produrre?
In teoria (uso le virgole per poter fare le ottimizzazioni):
K--> K1*0,5      K2* 0,5         K3*1
F--> K1*1,25    K2*1,25        F3*2,5
Quindi in totale devo produrre
K1--> 0,5+1,25=1,75
K2--> 0,5+1,25=1,75
K3--> 1
F3--> 2,5
(#### Punto X ####, vedi sotto) Arrotondo all'intero superiore, perche posso
produrre solo "blocchi" interi delle componenti, quindi produrrò
K1--> 1,75 --> 2
K2--> 1,75 --> 2
K3--> 1 ------> 1
F3--> 2,5 ----> 3
E così produco i 10 K ed i 25 F.... però mi avanzano dei pezzi,
nella fattispecie mi avanzano:
5 componenti K1
5 componenti K2
5 componenti F3
E cosa me ne faccio?
Facile, io sono intelligente... ci posso costruire altri 5 articolo F, e
cosi non avanzo nulla!
Facile, per me... ma come faccio a farlo fare ad un PC?
Inoltre questo è un caso volutamente particolare in cui ottimizzando ho
disavanzi in numero preciso...
ma se ho numeri strani? devo comunque non avere disavanzi; ok, allora si
lavora di minimi comui multipli e cose simili... il tutto è facile su un
singolo articolo, ma non riesco ad uscirne dovendo applicare l'idea ad un
set di articoli da ottimizzare tutti assieme.
Metodicamente arrivo al "Punto X"(vedi sopra), ma da qui in poi non so come
fare.
Esiste un qualche algoritmo per risolvere problemi di questo tipo?
Grazie a tutti, Max

 altra teoria ancora.
Ho provato a cercare un po in rete e sto scaricando un po di roba... ma
credo che la maggior parte siano appunti di corsi universitari.
E come al solito ci mettono vagonate di cavolate teoriche e poche
applicazioni pratiche, oddio certi tipi di professori... :-)
Quel poco che cia aveva fatto il nostro proff di ricerca operativa almeno
era piuttosto "pratico", ma quell'algoritmo non lo ricordo, anche se in
effetti č passato qualche anno.
Andrņ a vedere se ho qualcosa negli appunti :-)
Grassie, Max

 altra teoria ancora.
In effetti guardando un po di documentazione che ho scaricato capisco che la
soluzione č da quelle parti :-)
Perņ prima di avventurarmi nella lettura di centinaia di pagine molto
teoriche ti chiedo:
L'algoritmo del simplesso e la programmazione lineare trattano problemi  su
numeri interi? in quanto io dovrņ ragionare su quelli per le soluzioni
finali (mentre nei passaggi intermedi ragionerņ su numeri Reali)
Inoltre da alcune FAQ che ho letto pare che la programmazione lineare sui
numeri interi sia una cosa estremamente ostica, dici che ho delle speranze
di uscirne con una soluzione?
Grazie, Max

 e sto cercando un algoritmo per risolverlo.
8<
Mai sentito parlare del "simplesso"?
Ti conviene usare l'MPL della Maximal Software, e' un risolutore che usa il
simplesso su un file di input in cui metti le disequazioni del problema. Io
l'ho usato per il mio corso di Ricerca Operativa. Ha la possibilita' anche
di trattare problemi di PLI e credo anche convessa.
Ciao,
     Stefano
--
In questo post c'e' sicuramente un errore.

 finali (mentre nei passaggi intermedi ragionerò su numeri Reali)
C'e' un intero corso di Ricerca Operativa che ti attende, da cui uscirai con
mille fantastici algoritmi e varianti, per i numeri interi, razionali e
irrazionali, per grafi e sottografi, ottimi e euristici, e chi piu' ne ha
piu' ne metta. Prenditi un libro di ricerca operativa ( Colorni, Ricerca
Operativa, per dirne uno, ma ce ne sono centinaia) e studiatelo.
E' una delle basi della programmazione, non e' tempo sprecato.
Stefano

Ciao,
In linea di massima non e' necessario che ti addentri a fondo nella 
teoria della Programmazione Matematica. In effetti la cosa che forse ti 
converrebbe fare e' quella di utilizzare dei tools gia' esistenti ( ce 
ne sono anche di gratuiti ), e limitarti a imparare a scriverti delle 
'formulazioni' ( ovvero impostare il problema in modo che il tool lo 
capisca e lo risolva ). Di solito si tratta di impostare il problema 
sotto forma di disequazioni lineare . Una volta imparati i "trucchi del 
mestiere" il piu' e' fatto. Dovresti trovare documentazione anche su di 
questo in rete.
Ma a questo punto forse conviene spostarsi su di un NG piu' adatto.
Marco

 che hanno componenti comuni.
In generale, ci sono vari approcci per risolvere problemi di
ottimizzazione: di programmazione matematica (algoritmi di ricerca
operativa, oppure metodi basati su statistiche); soft-computing,
tipicamente con algoritmi genetici (ma anche reti neurali e logica
fuzzy); di simulazione. 
Il tuo problema suona (non ho letto i dettagli) come un problema di
composizione, risolto spesso con varie tecniche di programmazione intera;
quale esattamente, e soprattutto come ricondurre la tua definizione del
problema ad una delle definizione canoniche per cui esiste la soluzione,
st a te. 
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun

 Esiste un qualche algoritmo per risolvere problemi di questo tipo?
Knapsack.
http://www.cs.sunysb.edu/~algorith/files/knapsack.shtml
(ad esempio)
-- 
Inviato il ven 18 gen 2002 17:46:24 CET da 
fw01-e31.inferentia.net
[217.29.160.1]
http://www.neuromante.net/