View Full Version : Algoritmo del simplesso
punkarre
12-05-2003, 13:39
Salve a tutti
vorrei sapere se qualcuno ha o sa' dove posso trovare codice c, c++ o anche fortran o java sul metodo del Simplesso (programmazione lineare)
grazie in anticipo a tutti per l'aiuto
au revoir
Punkarre
per esempio in:
www.ulib.org/webRoot/Books/Numerical_Recipes/bookfpdf.html
10.8 Linear Programming and the Simplex Method 423
Capitolo 10
Ti servono anche le utility (quelle del c, ma se programmi in c++ sono più affidabili quelle del c++)
http://nr.com/public-domain.html ;)
Mortacci loro,adesso c'è il fortran :mad:
Il capoccia sarà lo zio di a2000 :D
Servirebbe un'anima pia che ci dicesse in privato cosa fare ;)
(non per i sorgenti ma per i pdf)
#define NRANSI
#include "nrutil.h"
#define EPS 1.0e-6
#define FREEALL free_ivector(l3,1,m);free_ivector(l2,1,m);\
free_ivector(l1,1,n+1);
void simplx(float **a, int m, int n, int m1, int m2, int m3, int *icase,
int izrov[], int iposv[])
{
void simp1(float **a, int mm, int ll[], int nll, int iabf, int *kp,
float *bmax);
void simp2(float **a, int n, int l2[], int nl2, int *ip, int kp, float *q1);
void simp3(float **a, int i1, int k1, int ip, int kp);
int i,ip,ir,is,k,kh,kp,m12,nl1,nl2;
int *l1,*l2,*l3;
float q1,bmax;
if (m != (m1+m2+m3)) nrerror("Bad input constraint counts in simplx");
l1=ivector(1,n+1);
l2=ivector(1,m);
l3=ivector(1,m);
nl1=n;
for (k=1;k<=n;k++) l1[k]=izrov[k]=k;
nl2=m;
for (i=1;i<=m;i++) {
if (a[i+1][1] < 0.0) nrerror("Bad input tableau in simplx");
l2[i]=i;
iposv[i]=n+i;
}
for (i=1;i<=m2;i++) l3[i]=1;
ir=0;
if (m2+m3) {
ir=1;
for (k=1;k<=(n+1);k++) {
q1=0.0;
for (i=m1+1;i<=m;i++) q1 += a[i+1][k];
a[m+2][k] = -q1;
}
do {
simp1(a,m+1,l1,nl1,0,&kp,&bmax);
if (bmax <= EPS && a[m+2][1] < -EPS) {
*icase = -1;
FREEALL return;
} else if (bmax <= EPS && a[m+2][1] <= EPS) {
m12=m1+m2+1;
for (ip=m12;ip<=m;ip++) {
if (iposv[ip] == (ip+n)) {
simp1(a,ip,l1,nl1,1,&kp,&bmax);
if (bmax > 0.0)
goto one;
}
}
ir=0;
--m12;
for (i=m1+1;i<=m12;i++)
if (l3[i-m1] == 1)
for (k=1;k<=n+1;k++)
a[i+1][k] = -a[i+1][k];
break;
}
simp2(a,n,l2,nl2,&ip,kp,&q1);
if (ip == 0) {
*icase = -1;
FREEALL return;
}
one: simp3(a,m+1,n,ip,kp);
if (iposv[ip] >= (n+m1+m2+1)) {
for (k=1;k<=nl1;k++)
if (l1[k] == kp) break;
--nl1;
for (is=k;is<=nl1;is++) l1[is]=l1[is+1];
++a[m+2][kp+1];
for (i=1;i<=m+2;i++) a[i][kp+1] = -a[i][kp+1];
} else {
if (iposv[ip] >= (n+m1+1)) {
kh=iposv[ip]-m1-n;
if (l3[kh]) {
l3[kh]=0;
++a[m+2][kp+1];
for (i=1;i<=m+2;i++)
a[i][kp+1] = -a[i][kp+1];
}
}
}
is=izrov[kp];
izrov[kp]=iposv[ip];
iposv[ip]=is;
} while (ir);
}
for (;;) {
simp1(a,0,l1,nl1,0,&kp,&bmax);
if (bmax <= 0.0) {
*icase=0;
FREEALL return;
}
simp2(a,n,l2,nl2,&ip,kp,&q1);
if (ip == 0) {
*icase=1;
FREEALL return;
}
simp3(a,m,n,ip,kp);
is=izrov[kp];
izrov[kp]=iposv[ip];
iposv[ip]=is;
}
}
#undef EPS
#undef FREEALL
#undef NRANSI
Beh,mi piacerebbe anche la versione c++ dei sorgenti :D
;) ;) ;)
http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html
ahoo! me sò confuso!
Però tutto il materiale in c++ mi piacerebbe ancora.
Capisceammè ;)
EDDAI!!! :D
Originally posted by "verloc"
Mortacci loro,adesso c'è il fortran :mad:
...
...
Prima di tutto c'è stato e c'è il , anche e ovviamente per i "Numerical Recipe". :cool:
Come dice la pubblicità del Compaq VisualFortran: compiler technology ... for your PC"[/siz] :cool:
Per il resto, Verluocco, mi sa che cominci a straparlare, va beh che siamo "cosa vuoi di più dalla vita" tutti e due ma, ... e mi contengo, "est modus in rebus" ...
Hai ragione a2000,
l'ho editato subito :)
potrei mai offendere uno che ho invitato? ;)
ps non ho nulla contro il fortran,ma dato che conosco solo il c++
il pensiero che mi avessero levato la migliore fonte di programmazione
scientifica...cmq lo sai che era una battuta(scema,lo so :( e me ne scuso).
A proposito a2000,veniamo alle cose serie ...
fammi un esempio di tipica applicazione del simplex(che non ho mai studiato).
Qualche mese fa incontrai una applicazione del simpex alla stabilità
degli archi murari,ma degli studiosi cmq hanno concluso che nel caso specifico non era affidabile,e che il problema doveva essere risolto con la programmazione non lineare.
per questo dopo la laurea voglio studiarlo e applicarlo agli archi.
Cià Cià :)
Originally posted by "verloc"
Però tutto il materiale in c++ mi piacerebbe ancora.
contrordine!
Dicono che i sorgenti sono praticamente gli stessi con l'uso di una inutile classe interfaccia implementata giusto per vendere un nuovo libro!
Originally posted by "verloc"
A proposito a2000,veniamo alle cose serie ...
fammi un esempio di tipica applicazione del simplex(che non ho mai studiato).
Più programmano in C++ e più non sanno un C++ :D
Il metodo del simplesso nella programmazione lineare determina il minimo/massimo di una funzione di merito lineare vincolata da vincoli lineari. Geometricamente si tratta di determinare il min/max di una funzione obiettivo lineare nel volume delimitato da vincoli lineari (il simplesso).
Si dimostra che il min/max della funzione di merito è su un vertice del simplesso. L'algoritmo percorre quindi solo i vertici del simplesso con un criterio di minimizzazione.
Le applicazioni sono tante quanti sono i problemi di minimizzazione lineare.
Sono tantissime in ricerca operativa, economia ma anche in ingegneria.
Originally posted by "verloc"
Qualche mese fa incontrai una applicazione del simpex alla stabilità
degli archi murari,ma degli studiosi cmq hanno concluso che nel caso specifico non era affidabile,e che il problema doveva essere risolto con la programmazione non lineare.
Infatti esiste un metodo del simplesso per la minimizzazione di funzioni non lineari solo 4 paragrafi più sopra:
10.4 Downhill Simplex Method in Multidimensions 402
Più programmano in C++ e più non leggono un C++ :D
Originally posted by "verloc"
per questo dopo la laurea voglio studiarlo e applicarlo agli archi.
già fatto:
http://www.mechanics.citg.tudelft.nl/~simone/aicap-02.pdf
Più programmano in C++ e più non guardano un C++ :D
Originally posted by "verloc"
Cià Cià :)
"A gatt' è sup'a cers, alla salut' d' tatt"
Più programmano in C++ e più non capiscono un C++ :D
Originally posted by "verloc"
...cmq lo sai che era una battuta ...
... lo sai che noi "cosa vuoi di più dalla vita" siamo mooolto permalosi :mad:
:)
Ma è ovvio che non ho letto la parte su nr,mi spieghi tu quando avrei dovuto farlo?
Se non ho seguito nessun corso dove si insegnasse la prog lineare
E' COLPA MIA?(tra parentesi ho iniziato il c++ da 2 anni)
avrei dovuto seguire 54 corsi? :eek:
Io sapevo c he la programmazione non lineare (nel senso di applicazione software)non era stata ancora applicata alla stabilità degli archi murari.
In altre parole nessuno era stato c++++ di farne un programma.
(non avevo la certezza).
Ti sei preso la briga di verificare se la p.n.l era stata applicata agli archi(murari ribadisco) pur di cogliermi in fallo? :eek:
E poi che ne capisci tu di archi murari? :D
Tu ignori (o subconsciamente preferisci ignorare)che un giorno anche tu sei stato ignorante :D e che non si finisce mai di imparare:
sillogismo per dirti che quindi anche tu sei un ignorante. Tiè :P
Mo,fammi andà a studià che domani devo spiegare l'algoritmo che verifica se un piano sta in piedi o no (sotto u' terramot' ) :)
Io l'algoritmo del simplesso lo implementai su Matlab e sulla calcolatrice...purtroppo non in C++...ma una volta che si conosce l'algoritmo è automatico scrivere il codice... Avevo anche modificato la regola anticiclo...
/\/\@®¢Ø
13-05-2003, 22:01
Originally posted by "verloc"
fammi un esempio di tipica applicazione del simplex(che non ho mai studiato).
Qualsiasi problema del tipo max(x){ cx | Ax<=b } a variabili reali non negative. In pratica i problemi da "manuale" sono quelli di job scheduling , ma se si ammettono anche variabili intere allora la classe di problemi trattabili diventa decisamente ampia, visto che si possono ammettere anche vincoli di tipo diverso (booleani in primis). In questo caso pero' il simplesso diventa parte di un algoritmo piu' ampio, e il numero di vincoli aggiunti diventa abbastanza elevato da sconsigliare un qualsiasi algoritmo fatto in casa. Alcune categorie di problemi su grafi inoltre sono risolvibili tramite PL.
/\/\@®¢Ø
13-05-2003, 22:53
Originally posted by "verloc"
http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html
ahoo! me sò confuso!
Però tutto il materiale in c++ mi piacerebbe ancora.
Capisceammè ;)
EDDAI!!! :D
:confused:
un wget -r -np non basta ? :D :p
Originally posted by "a2000"
già fatto:
http://www.mechanics.citg.tudelft.nl/~simone/aicap-02.pdf
Più programmano in C++ e più non guardano un C++ :D
Che pazienza ci vuole con gli anziani rinc+++++ :rolleyes: :D
Infatti il documento da te citato riguarda una particolare applicazione del cemento armato...
NON GLI ARCHI MURARI!!!
ed in ogni caso non sto parlando di teoria ma di un software applicato e funzionante.
...egli continuava a programmare in FORTRAN mentre il dipinto inesorabilmente invecchiava... :D
[da Il ritratto di Dorian Grey]
Originally posted by "cionci"
Io l'algoritmo del simplesso lo implementai su Matlab e sulla calcolatrice...purtroppo non in C++...ma una volta che si conosce l'algoritmo è automatico scrivere il codice... Avevo anche modificato la regola anticiclo...
giusto.
più complicato è passare dall'algoritmo dell'amplesso a scrivere con l'indice :pig:
modificare la regola diciclo (T = 28 d) poi è quasi impossibile. :cry:
P.S.
Verloc, futt'tinn', pienz' a sta' buon' e miett't u custum' :p
Originally posted by "/\/\@®¢Ø"
Qualsiasi problema del tipo max(x){ cx | Ax<=b } a variabili reali non negative. In pratica i problemi da "manuale" sono quelli di job scheduling , ma se si ammettono anche variabili intere
....
anche quelle reali negative.
perchè i numeri interi non sono numeri reali ?
forse intendevi soluzioni ristrette ai numeri interi.
/\/\@®¢Ø
14-05-2003, 10:38
Originally posted by "a2000"
anche quelle reali negative.
perchè i numeri interi non sono numeri reali ?
forse intendevi soluzioni ristrette ai numeri interi.
Hai ragione non mi sono spiegato bene :p : intendevo dire che si vuole porre la condizione che alcune di queste variabili siano intere!
Originally posted by "verloc"
Ma è ovvio che non ho letto la parte su nr,mi spieghi tu quando avrei dovuto farlo?
Se non ho seguito nessun corso dove si insegnasse la prog lineare
E' COLPA MIA?(tra parentesi ho iniziato il c++ da 2 anni)
"OGNI COSA E' COLPA TUA" da "A bugs life" :)
http://www.pixar.com/featurefilms/abl/images/index_tr.jpg
Originally posted by "verloc"
avrei dovuto seguire 54 corsi? :eek:
Beh, a veterinaria li fanno.
Ci hai mai pensato a veterinaria .... :pig: :pig: :D
Originally posted by "verloc"
Io sapevo c he la programmazione non lineare (nel senso di applicazione software)non era stata ancora applicata alla stabilità degli archi murari.
In altre parole nessuno era stato c++++ di farne un programma.
(non avevo la certezza).
guarda, si dice che da Platone in poi non c'è più niente di nuovo.
ora da Platone forse no, ma in epoche di decadenza come questa caratterizzate da formalismi barocchi (vedi C++, e nun t'ncazza': ) stai tranquillo che non s'inventa un ca++o di nuovo nessuno; a parte, tra un hamburger e un party, applicare algoritmi pensati 100 anni fa per massacrare dei poveri crist.
Originally posted by "verloc"
Ti sei preso la briga di verificare se la p.n.l era stata applicata agli archi(murari ribadisco) pur di cogliermi in fallo? :eek:
ca++o, scusa, è la prima cosa che è venuta su google con "simplex downhill method" :D
Originally posted by "verloc"
E poi che ne capisci tu di archi murari? :D
... lo sai Verloc che posso calcolarti T, D, T (x, t) con un decimo delle tue righe di codice e un quarto del tuo tempo di calcolo puro per tutto il ponte Musmeci .... :cool:
Originally posted by "verloc"
Tu ignori (o subconsciamente preferisci ignorare)che un giorno anche tu sei stato ignorante :D e che non si finisce mai di imparare:
sillogismo per dirti che quindi anche tu sei un ignorante. Tiè :P
nessuno è perfetto. io puro. :p
Originally posted by "verloc"
Mo,fammi andà a studià che domani devo spiegare l'algoritmo che verifica se un piano sta in piedi o no (sotto u' terramot' ) :)
tu u' terramot' u tien n'da cap', fratello mio ![/siz] :D :D :D
Originally posted by "a2000"
... lo sai Verloc che posso calcolarti T, D, T (x, t) con un decimo delle tue righe di codice e un quarto del tuo tempo di calcolo puro per tutto il ponte Musmeci .... :cool:
Ecchessò T, D patat' ?
E poi il ponte Musmeci è in cemento armato,non fatto di archi in pietra!
GNURANT!!! [/siz]
:D
ps mo' bast' se no n' caccn' e tnessr pur' ragion :)
GNURANT !!!![/siz]
non sai che sono T e D ?
e tu il tensore degli sforzi e deformazioni come li chiami all'antica sigma e epsilon ?
poi ci ho messo anche la temperatura T. :cool:
archi in pietra ????
ah figlio mio, tu non sei un personaggio di Conrad, ma dei Flinstones :D :D :D
E va beh che sei dell'entroterra ma non farti riconoscere sempre ! :D
"Wilmo la clava, anzi l'arco in pietra !" :D :D :D
Ma tu pienz' nu picch' ....
Originally posted by "a2000"
GNURANT !!!![/siz]
non sai che sono T e D ?
e tu il tensore degli sforzi e deformazioni come li chiami all'antica sigma e epsilon ?
poi ci ho messo anche la temperatura T. :cool:
:rolleyes:
Se tu fossi un ingegnere civile(e non lo sei) saresti uno di quelli
che al carpentiere gli porta un tabulato di 400 pagine di numeri(Tensori etc)che ovviamente t' sciput' int' a' faccie' :D
Uno dei miei professori è uno dei 3 periti per S.Giuliano e ti assicuro
che di computer ne capisco + io di lui.
Ma io scambierei volentieri la sua conoscenza(1.000.000x) con la mia! :)
Se fosse per te,avremmo usato le macerie riciclate del Foro Romano per farci un bel centro commerciale.
Se non fosse per la passione sull'argomento di quelli come me(la muratura)Il Regno Unito non avrebbe fatto il più colossale investimento di ricerca del dopoguerra sulla ristrutturazione dei loro centenari ponti ferroviari in pietra(alcuni bellissimi).
Cosi come secondo te dovremmo sicuramente abbattere tutto cio che è stato costruito prima del 1950. :D
Sgarbi (che detto fra noi teng' sup u' c.....) ti scorticherebbe vivo. :D
Ricordati che quelli che fanno crollare i palazzi sono quelli che portano 400 pagine di tabulati. ;)
Se cerchi di farmi incazzare è inutile,non ci riuscirai.
ps parli proprio tu che sei di "Dammi la clava" Pert...? :D :D
Questa era buona dai!
Originally posted by "verloc"
:rolleyes:
Se tu fossi un ingegnere civile (e non lo sei) sono molto di più: ingegnere chimico :cool: saresti uno di quelli
che al carpentiere gli porta un tabulato di 400 pagine di numeri(Tensori etc)che ovviamente t' sciput' int' a' faccie' :D
non devi aver bisogno del carpentiere, devi essere anche carpentiere, ingegnere e carpentiere come Leonardo. Libreria e Ferramenta questi sono i due posti che devi frequentare più assiduamente. Ora et Labora.
:cool: :pig:
Uno dei miei professori è uno dei 3 periti per S.Giuliano e ti assicuro
che di computer ne capisco + io di lui.
Ma io scambierei volentieri la sua conoscenza (1.000.000x) con la mia! :)
beh se per questo, anche con quella del carpentiere :D
Se fosse per te,avremmo usato le macerie riciclate del Foro Romano per farci un bel centro commerciale.
Loro (i Romani, quelli antichi ... ) hanno avuto il coraggio, le idee, l'audacia per farci il loro di centro commerciale (Foro Romano). :p
Se non fosse per la passione sull'argomento di quelli come me (la muratura) Il Regno Unito non avrebbe fatto il più colossale investimento di ricerca del dopoguerra sulla ristrutturazione dei loro centenari ponti ferroviari in pietra(alcuni bellissimi).
la muratura, giusto, la muratura ...
Cosi come secondo te dovremmo sicuramente abbattere tutto cio che è stato costruito prima del 1950. :D
anche prima di settembre.
Sgarbi (che detto fra noi teng' sup u' c.....) ti scorticherebbe vivo. :D
Sgarbi sono io in questo scenario :p
Ricordati che quelli che fanno crollare i palazzi sono quelli che portano 400 pagine di tabulati. ;)
Devi essere ingegnere, carpentiere e collaudatore:
la sai la storia del progettista del ponte sul ....
Se cerchi di farmi incazzare è inutile, non ci riuscirai.
siamo sempre fratelli. anche se c'hai l'algoritmo del complesso ... :D
ps parli proprio tu che sei di "Dammi la clava" Pert...? :D :D
ricordati che quando al paese tuo vivevate ancora nelle caverne (senza archi in pietra) a Pert eravamo gia Froci (con archi in roccia) :pig:
http://digilander.libero.it/lucania0/pietrapertosa/fortezza/fortezza4/za1.JPGhttp://digilander.libero.it/lucania0/pietrapertosa/fortezza/fortezza8/za2.JPG
Questa era buona dai!
pure questa :D :D
Salve a tutti,
ho letto l'argomento della discussione e devo dire che mi interessa molto. Io devo implementare l'algoritmo del simplesso col matlab. Conosco come funziona il simplesso, ma non riesco ad implementarlo (non ho molta dimestichezza col matlab). Voi mi sapete dire dove posso trovarlo? O in alternetiva, posso implementarlo col java, fortran o c (preferibilmente java e fortran). Ho visto i vostri siti, ma alcuni li hanno chiusi. Aspetto vostre notizie, spero il più presto possibile, e intanto vi ringrazio anticipatamente.
Io ho trovato il simplesso in C++:
http://www.fizyka.umk.pl/nrbook/c10-4.pdf
Ho dei dubbi però su alcune parti e principalmente non capisco l'input y[i] con i= 1 to mpts cosa rappresenta i vertici? è una copia dalla matrice: y[i] = p[i][j=1..ndim] cioè ogni y[i] è un puntatore ad un array float contenente le coordinate del vertice i-esimo?
e poi se è così come faccio a confrontare le y fra di loro (es: y[1] > y[2])??
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.