Home

 Logithèque

TI80

Mini-solution du problème du simplexe (cas simple)


Code

Programme SMPLXIN : (465 octets)

Lbl 9:ClrHome:Disp "%Simplexe%"

Disp "1-Input"

Disp "2-Disp"

Disp "3-Calc"

Disp "4-Result"

Input A

If A=1:Goto 1

If A=2:Goto 2

If A=3:Goto 3

If A=4:Goto 4

Return

Lbl 1

Disp "Max(Ax+By)":Input "A=",A

Input "B=",B

{A,B}->L5:0->N

Lbl 8:ClrHome

Disp "Contrainte",N

Disp "Ax+By<=C"

Disp "{0}=End"

Input "{A,B,C}=",L6

If 1=Dim L6: Goto 9

N+1->N

L6(1)->L5(3N):L6(2)->L5(3N+1):L6(3)->L5(3N+2)

Goto 8

Lbl 2

Disp "Fct a Max",{L5(1),L5(2)}

(Dim L5-2)/3->N

Disp "Contraintes",N

For (I,1,N)

Disp {L5(3I),L5(3I+1),L5(3I+2)}

End

Input I:Goto 9

Lbl 3

Disp "Computing..."

Prgm_Simplex

Lbl 4

If 2>Dim L6

Then: Disp "Pas de Sol":Else

Disp "Max=",A

If 5>Dim L6

Then:Disp "Point:"

Else:Disp "Droite:":End

Disp L6:End

Input I: Goto 9

 

Programme SIMPLEX : (315 octets)

-1e90->A:{0}->L6:(Dim L5-2)/3->N

For (I,I,N-1)

3I->U

For (J,I+1,N)

3J->V

L5(U)*L5(V+1)-L5(U+1)*L5(V)->C

If C<>0:Then

(L5(U+2)*L5(V+1)-L5(V+2)*L5(U+1))/C->X

(L5(V+2)*L5(U)-L5(U+2)*L5(V))/C->Y

Max(Seq(L5(3K)X+L5(3K+1)Y-L5(3K+2),K,1,N,1))->D

IF 0>=D:Then

X*L5(1)+Y*L5(2)->D:Disp {I,J,D}

If D=A:Then

Dim L6->C

I->L6(C+1):J->L6(C+2):X->L6(C+3):Y->L6(C+4)

End

If D>A:Then

D->A:{I,J,X,Y}->L6:End

End:End

End:End

 


Mode d'emploi

Lancer le programme SMPLXIN, qui est l'interface de saisie des paramètres.


Mathématiques à l'oeuvre

On sait que le maximum est le point se trouvant à l'intersection de deux droites de contraintes, ou bien c'est la droite d'une des contraintes. On calcule donc la valeur de la fonction à maximiser aux intersections, et on retient la plus élevée ou les deux plus élevées.


Fonctionnement du programme

Voici l'utilisation des variables du programme SIMPLXIN :

A Numéro d'option dans le menu, input
N Nombre de contraintes
I Indice de boucle d'affichage
L5 Voir le programme SIMPLEX
L6 Entrée des contraintes, et résultats

Les paramètres envoyés à SIMPLEX sont N et L6, et les résultats sont récupérés dans L6.

Voici l'utilisation des variables du progamme SIMPLEX :

A Valeur maximale atteinte

C

Déterminant et buffer

D

Valeur contrainte et fct à maximiser
N Nombre de contraintes
I Indice de boucle n°1
J Indice de boucle n°2
U Pointeur sur la contrainte I

V

Pointeur sur la contrainte J

X et Y

Coordonnées de l'intersection I, J

L5

(Voir ci-dessous)

L6

Points des maxima

Partout I et J sont utilisés comme indices de deux des contraintes que l'on traite à un certain moment : 0<I<=N et de même pour Y.

Le format des listes L5 et L6 est le suivant :

L5 : ses deux premiers éléments sont la fonction à maximiser (coefficient de X puis de Y), ensuite les triplets des contraintes.

L6 : contient un ou des quadruplets donnant les indices des deux contraintes, puis leur point d'intersection (X puis Y), soit le format {Ii, Ji, Xi, Yi, ... }