@DATABASE PULITO @VER$ PULITO© v0.9beta @WIDTH 72 @HEIGHT 200 @NODE MAIN "PULITO© v1.0 beta" PPPPP U U L IIIII TTTTT OOO P P U U L I T O O P P U U L I T O O PPPPP U U L I T O O P U U L I T O O P U U L L I T O O P UUUUU LLLLLL IIIII T OOO PULITO© v1.0 beta (25-7-1996) by Stefano Avanzo (huels@dei.unipd.it) @{" Che cos'e` " LINK Cosa} @{" Requisiti " LINK Requisiti} @{" Come si usa " LINK Comesiusa} @{" Copyrights " LINK Copyrights} @{" Ringraziamenti " LINK Ringraziamenti} @{" Saluti " LINK Saluti} @{" Musica? " LINK Musica} @ENDNODE @NODE Cosa E` un programma per risolvere problemi di programmazione lineare e lineare intera con l'algoritmo del simplesso in forma tableau. Sebbene sia stato creato appositamente per aiutare gli studenti di un corso di Ricerca Operativa, puo` essere utile anche per risolvere qualsiasi problema di ottimizzazione. Il programma risolve infatti problemi generali del tipo: / | min cX / \ AX=b | \ X>=0 (Interi o non) dove c e` un vettore di coefficienti, X e` il vettore rappresentante le variabili del problema in esame, A e` una matrice m x n di coefficienti, X e` lo stesso vettore di prima e b e` un vettore di termini noti. Il programma cioe` risolve un problema nel quale si deve trovare il minimo di una certa espressione al variare delle variabili( X ), e contemporaneamente, il valore della soluzione deve soddisfare al sistema di vincoli AX=b. Esempio: Un'azienda deve affittare alcuni Amiga secondo i fabbisogni mensili di seguito illustrati: ----------------------------------------------------------- mese | gen | feb | mar | apr | mag | giu | ----------------------------------------------------------- quantita`| 9 | 5 | 7 | 9 | 10 | 5 | ----------------------------------------------------------- I costi variano a seconda della durata del periodo di affitto(KL=1000Lire) ---------------------------------- durata |1 mese |2 mesi |3 mesi | ---------------------------------- costo | 400KL | 700KL | 900KL | ---------------------------------- Si vuole decidere la politica che minimizza il costo complessvo. Siano: - gen1,gen2,gen3 = n° di Amiga affittati a gennaio per 1,2,3 mesi - feb1,feb2,feb3 = n° di Amiga affittati a febbraio per 1,2,3 mesi - mar1,mar2,mar3 = n° di Amiga affittati a marzo per 1,2,3 mesi . . . . . . . . - giu1,giu2,giu3 =n° di Amiga affittati a giugno per 1,2,3 mesi le variabili del problema. Un possibile modello matematico e` allora: min 400(gen1+feb1+mar1+apr1+mag1+giu1)+700(gen2+feb2+mar2+apr2+mag2+giu2)+ 900(gen3+feb3+mar3+apr3+mag3+giu3) gen1+gen2+gen3 - X1 =9 (Amiga a gennaio) feb1+feb2+feb3+gen2+gen3 - X2 =5 (Amiga a febbraio) mar1+mar2+mar3+feb2+feb3+gen3 - X3 =7 (Amiga a marzo) apr1+apr2+apr3+mar2+mar3+feb3 - X4 =9 (Amiga a aprile) mag1+mag2+mag3+apr2+apr3+mar3 - X5 =10 (Amiga a maggio) giu1+giu2+giu3+mag2+mag3+apr3 - X6 =5 (Amiga a giugno) gen1,gen2,.......giu2,giu3 >=0 interi dove sono state aggiunte nel modello delle variabili X1,...,X6 dette variabili surplus, perche` il modello originale avrebbe avuto al posto degli "=" dei ">=". ecco, inserendo i coefficienti di ognuna delle variabili del modello, PULITO calcolera` la soluzione ottima intera. (Si noti che le variabili non presenti nella soluzione ottima devono essere considerate poste a zero). (In questo preciso esempio si dovra` usare l'algoritmo di tipo primale il metodo delle due fasi e i tagli di Gomory) @ENDNODE @NODE Comesiusa Come nell' @{"esempio" LINK Cosa} visto in precedenza, si devono inserire i vari coefficienti della funzione obiettivo(in forma di minimo) e del sistema di vincoli. L' effettiva utilita` del programma e` quella di mostrare tutti i passaggi derivati dall'applicazione del metodo del simplesso in forma tableau. Questi passaggi infatti sono in genere richiesti per un esame scritto di Ricerca Operativa, e per esempio per essere sicuri della correttezza degli esercizi svolti, si puo` usare PULITO. I tableau mostrati sono nella forma: ---------------------------------------- | | | | | | <--coefficienti della funzione ---------------------------------------- obiettivo(a partire dalla | | | | | | seconda colonna, infatti ---------------------------------------- il termine nella prima /-> | | | | | |<--\ riga e prima colonna, e` | ---------------------------------------- | il valore della funzione nella prima colonna / obiettivo corrente cambiato ci sono i termini noti / di segno. (a parte il primo elemento) / dopo la prima riga ci sono i coefficienti dei vincoli Per usare l'algoritmo duale bisogna specificare le variabili in base corrispondenti all'ordine di immissione dei coefficienti dei vincoli. Per la soluzione ottima intera e` necessario rispondere affermativamente alla domanda dei tagli di Gomory, e, nel qual caso verranno visualizzati i vincoli aggiunti al tableau originale. Pulito elabora tableau fino a dimensioni massime di 100 x 100. Pulito B&B e` una versione che implementa un Branch and Bound limitato a 10 sottoproblemi. @ENDNODE @NODE Copyrights PULITO è Freeware ma tutti i diritti sono riservati. Potete copiarlo finché volete, basta che non ne ricaviate un profitto e che l'archivio rimanga intatto. La distribuzione su CD-Rom è concessa a patto che il CD e l'eventuale rivista che lo accompagni siano venduti a meno di 35.000 lire! In nessun caso l'autore si assume responsabilità per il cattivo uso del software. Non si da' alcuna garanzia di nessun tipo, né implicita, né esplicita lo ripeto, usando questo software ti assumi tutti i rischi che ne potrebbero derivare. @ENDNODE @NODE Ringraziamenti @{fg highlight}@{b}L'autore ringrazia:@{ub}@{fg text} @{fg highlight}Chris Hülsbeck (o Huelsbeck),@{fg text} per le sue stupende creazioni musicali. @{fg highlight}Aminet,@{fg text} per i continui rifornimenti di software PD. @{fg highlight}Commodore,@{fg text} per aver finanziato i produttori originali di Amiga e per aver creato il C-16, il C-64 ed il C-128. Peccato che sia finita così... @{fg highlight}Escom AG,@{fg text} per aver ridato nuova vita ad Amiga @{fg highlight}Tutti i programmatori Amiga:@{fg text} grazie per il vostro supporto per questa splendida macchina. @ENDNODE @NODE Saluti @{fg highlight}@{b}Voglio salutare:@{ub}@{fg text} @{fg highlight}De Marchi Marina, Marco Zuliani@{fg text}, miei compagni di corso. @{fg highlight}Sergio Serena,@{fg text} programmatore Assembly. Possiede un A4000/30. @{fg highlight}Stefano Osti,@{fg text} programmatore in Amos. Possiede un A500+. @{fg highlight}Ilario Moretto,@{fg text} appassionato di Manga & Anime, consulente di MAG®, appassionato di musica. Attualmente possiede un A1200 ed un C64. Presto sentirete alcuni dei suoi moduli su Aminet. @{fg highlight}Sandro Destro,@{fg text} Kenshir-maniaco di 27° livello, Guyver-maniaco di 35° livello, A500ista. Pazzo. :) @{fg highlight}Luca Giolo,@{fg text} programmatore in Amos,appassionato di Manga, studia lingue orientali. Possiede un A1200/30/881. @{fg highlight}@{b}E tutti quelli che mi conoscono.@{ub}@{fg text} @ENDNODE @NODE Requisiti Per il sistema operativo penso basti anche l'1.3 mentre per la memoria e il resto : PULITO |--> 200Kb RAM libera, 68020/30/40 con 68881/82 PULITOB&B |--> 900Kb RAM libera, 68020/30/40 con 68881/82 PULITO68000 |--> 250Kb RAM libera, 68000(!?) PULITOB&B68000 |--> 950Kb RAM libera, 68000 @ENDNODE @NODE Musica Dello stesso autore, su Aminet ci sono le seguenti musiche: mods/dream/DaitarnIII.lha mods/dream/Glodrake.lha mods/dream/Mazinga.lha @ENDNODE