Algoritmo del simplesso

[punkarre]

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

[a2000]

per esempio in:

www.ulib.org/webRoot/Books/Numerical_Recipes/bookfpdf.html

10.8 Linear Programming and the Simplex Method 423

[verloc]

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

[verloc]

Mortacci loro,adesso c'è il fortran

Il capoccia sarà lo zio di a2000

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

[verloc]

Beh,mi piacerebbe anche la versione c++ dei sorgenti

[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!!!

[a2000]

Originally posted by "verloc"


Mortacci loro,adesso c'è il fortran
...
...

Prima di tutto c'è stato e c'è il , anche e ovviamente per i "Numerical Recipe".
Come dice la pubblicità del Compaq VisualFortran: compiler technology ... for your PC"[/siz]

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" ...

[verloc]

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).

[verloc]

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à

[verloc]

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!

[a2000]

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++
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++

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++

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++

[a2000]

Originally posted by "verloc"


...cmq lo sai che era una battuta ...

[a2000]

... lo sai che noi "cosa vuoi di più dalla vita" siamo mooolto permalosi

[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)

avrei dovuto seguire 54 corsi?

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?

E poi che ne capisci tu di archi murari?


Tu ignori (o subconsciamente preferisci ignorare)che un giorno anche tu sei stato ignorante 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' )

[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...

[/\/\@®¢Ø]

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.

[/\/\@®¢Ø]

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!!!

un wget -r -np non basta ?

[verloc]

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++

Che pazienza ci vuole con gli anziani rinc+++++

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...

[da Il ritratto di Dorian Grey]

[a2000]

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 ig:
modificare la regola diciclo (T = 28 d) poi è quasi impossibile.


P.S.
Verloc, futt'tinn', pienz' a sta' buon' e miett't u custum'

[a2000]

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.