\documentclass[10pt,a4paper]{article}
\usepackage[height=250mm,width=183mm]{geometry}
\usepackage{preambule}
\usepackage[upright]{fourier}
\graphicspath{{/home/moi/Figures/}}
\entete{Programmation Linéaire}{XCAS au lycée}{}%g,d,b
\usepackage[dvips,colorlinks=true]{hyperref}


\begin{VerbatimOut}{proglin.cxx}
proglin(L,S,X,XS,B):={
n:=nops(L)-1;
D:=NULL;DX:=NULL;
P:=NULL;PX:=NULL;
F:=[];
Le:=NULL;
Intx:=NULL;
Inty:=NULL;
W:=[0,0,0,0];

for(k:=0;k<=n;k++){L[k]:=solve(L[k],y)[0]; if((size(solve(L[k],x))!=0) and (solve(L[k],x)!=[x])){Intx:=Intx,solve(L[k],x)[0]};
                   F:=append(F,unapply(L[k],x));Inty:=Inty,F[k](0)}



W[0]:=-0.1*maxnorm([Intx]); W[1]:=1.2*(max(maxnorm(X),maxnorm([Intx])));
W[2]:=-0.1*maxnorm([Inty]); W[3]:=1.2*maxnorm([Inty]);



if(nops(X)>0){
nx:=nops(X)-1;
for(k:=0;k<=nx;k++){
 Le:=Le,legende(X[k]+i*(k+1)*W[3]/(k+5),"D"+(n+1+k));
 DX:=DX,droite(x=X[k]);
 PX:=PX,if(XS[k]==p){display(polygone(1.2*W[0]+i*6*W[2],1.2*W[0]+1.2*W[3]*i,X[k]+1.2*W[3]*i,X[k]+i*6*W[2]),(k+6+nx)+rempli);}
              else{display(polygone(1.2*W[1]+i*6*W[2],1.2*W[1]+1.2*W[3]*i,X[k]+1.2*W[3]*i,X[k]+i*6*W[2]),(k+6+nx)+rempli);}
  }
}

 for(k:=0;k<=n;k++){
 Le:=Le,legende(((5-k)*W[0]+(k+2)*W[1])/(7)+i*F[k](((5-k)*W[0]+(k+2)*W[1])/(7)),"D"+k);
 D:=D,droite(y=L[k]);
 P:=P,if(S[k]==m){display(polygone(1.2*W[0]+i*F[k](1.2*W[0]),1.2*W[0]+1.2*W[3]*i,1.2*W[1]+1.2*W[3]*i,1.2*W[1]+i*F[k](1.2*W[1])),(k+2)+rempli);}
               else{display(polygone(1.2*W[0]+i*F[k](1.2*W[0]),1.2*W[0]+6*W[2]*i,1.2*W[1]+6*W[2]*i,1.2*W[1]+i*F[k](1.2*W[1])),(k+2)+rempli);}
  }
xyztrange(W[0],W[1],W[2],W[3],-10,10,-1,6,W[0],W[1],W[2],W[3],1);
Be:=unapply(B,x,y):;
Bmax:=Be(maxnorm([Intx]),maxnorm([Inty]));
D:=D,DX;
P,PX,DX,D,display(droite(B=R),line_width_4),Le; 
 
}:;
\end{VerbatimOut}


\begin{VerbatimOut}{proglin.giac}
maple_mode(0);
read("proglin.cxx");
Sortie:=fopen("XCASproglin.tex");
fprint(Sortie,Unquoted,latex(read("proglin.user")));
fclose(Sortie);
\end{VerbatimOut}




\newenvironment{proglin}
{\VerbatimEnvironment\begin{VerbatimOut}{proglin.user}}
{\end{VerbatimOut}
           \immediate\write18{giac  <proglin.giac}
           \begin{center}
             \input{XCASproglin}
           \end{center}
}













\newcommand{\lat}{
\lstset{numbers=none,language=[LaTeX]{TeX},xleftmargin=10pt,%
keywordstyle =\color{0.2white}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily,commentstyle=\normalfont\scriptsize\slshape,
    backgroundcolor=\color{0.8white},breaklines=true}
}

\renewcommand{\xcas}{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
keywordstyle =\color{0.2white}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily,commentstyle=\normalfont\scriptsize\slshape,
    backgroundcolor=\color{0.8white},breaklines=true}
}


\title{\texttt{proglin.xws} \\La machine à résoudre les problèmes de programmation linéaire}

\author{Guillaume \textsc{Connan} \\ \href{http://gconnan.free.fr}{http://gconnan.free.fr}}

\date{7 février 2008 - Version 1.1}

\begin{document}

\maketitle

\section{Ça sert à quoi~?}

Les exercices  de programmation  linéaire au  lycée sont assez  standardisés, que  ce soit  dans les
sections  STG ou ES.  Ce petit  programme \Prog{XCAS}  permet d'obtenir  rapidement le  polygone des
contraintes  et la  droite  qui va  permettre  de lire  le «~bénéfice~»  maximum  ou la  «~dépense~»
minimum  avec une  mise à  l'échelle automatisée.  On se  contentera de  «~faire bouger~»  la droite
d'optimisation à l'aide d'un curseur et d'obtenir les coordonnées du point optimum.


\section{Comment ça marche~?}

\subsection{Principe général}

On entre une série d'instructions correspondant au système de contraintes~:


\begin{center}
  

$\bsyc

a_1x+b_1y+c_1&> \text{ ou }<&0\\
a_2x+b_2y+c_2&> \text{ ou }<&0\\
\cdots & & \\
x & > \text{ ou } < & k_1\\
x&> \text{ ou }<& k_2\\

\esyc$



\end{center}

avec  les  coefficients  $b_i$ positifs,  ainsi  que  l'expression  donnant  le «~bénéfice~»  ou  la
«~dépense~» en fonction de $x$ et $y$. On entre alors~:

\xcas

\begin{lstlisting}
proglin([a1x+b1y+c1,a2x+b2y+c2,...],[p,m,...],[k1,k2,...],[p,m,...],A*x+B*y)
\end{lstlisting}


avec \texttt{p} pour $>0$ et \texttt{m} pour $<0$.

\subsection{Comment l'utiliser~?}




On ouvre une fenêtre de géométrie en tapant \Alt+\keystroke{G}.

On crée d'abord un curseur représentant le «~bénéfice~» ou la «~dépense~»~:

\begin{lstlisting}
R:=element(0 .. Bmax)
\end{lstlisting}

\texttt{Bmax} étant la valeur maximum du curseur automatiquement calculée.

On entre ensuite les données~:

\begin{lstlisting}
proglin([a1x+b1y+c1,a2x+b2y+c2,...],[p,m,...],[k1,k2,...],[p,m,...],A*x+B*y)
\end{lstlisting}


On utilise le  curseur pour faire «~bouger~»  la droite d'optimisation. On détermine  ainsi le point
optimum. S'il s'agit de l'intersection de $D_1$  et $D_3$ par exemple, on obtient ses coordonnées en
tapant~:

\begin{lstlisting}
I:=inter(D[1],D[3])
\end{lstlisting}

Si  \Prog{XCAS} répond  par exemple  $(1200,300)$, pour  avoir la  valeur du  «~bénéfice~» ou  de la
«~dépense~»~ on entre~:

\begin{lstlisting}
Be(1200,300)
\end{lstlisting}



\section{Un exemple}


{\slshape Une usine syldave produit des androïdes de deux sortes~:~des soldats et des ouvriers, à partir de
microprocesseurs. Elle dispose au plus de $60\,000$ microprocesseurs par jour.

Il faut  30 microprocesseurs  pour le  cerveau d'un soldat  et 80  microprocesseurs pour  un cerveau
d'ouvrier.

Il faut une heure de travail pour produire 20 soldats et 2 heures pour produire 20 ouvriers.

L'usine emploie 9 techniciens travaillant 10 heures par jour.

Il ne faut pas produire  plus de 500 ouvriers par jour, sinon ils se  regroupent dans un syndicat et
ça devient ingérable.

Un soldat rapporte un bénéfice de 8\texteuro{} et un ouvrier 20 \texteuro{}.

Comment répartir la production quotidienne pour obtenir le bénéfice maximum~?}



Ce problème classique amène au système~:

\begin{center}

$\bsyc
x & \se & 0\\
y & \se & 0\\
30x+80y-60\,000 & \ie & 0\\
y-500 & \ie & 0\\
0,05x+0,1y-90 & \ie & 0\\
\esyc$

\end{center}

De plus, le bénéfice est donné par $B=8x+20y$.

On entre~:

\begin{lstlisting}
R:=element(0 .. Bmax)
\end{lstlisting}

\begin{lstlisting}
proglin([y,30*x+80*y-60000,y-500,0.05*x+0.1*y-90],[p,m,m,m],[0],[p],8*x+20*y)
\end{lstlisting}



On obtient~:

\begin{center}
  \includegraphics[width=.75\textwidth]{proglin.eps}
\end{center}



On  fait varier  la «~droite-bénéfice~»  avec le  curseur et  on lit  que le  maximum sera  obtenu à
l'intersection des droites $D_3$ et $D_1$.

On obtient ses coordonnées en entrant~:

\begin{lstlisting}
I:=inter(D[1],D[3])
\end{lstlisting}

qui renvoie~:

\begin{figure}
  \begin{BoxedVerbatim}
    $\mathtt{[point(1200.0,300.0)]}$
 \end{BoxedVerbatim}
\end{figure}

On obtient le bénéfice correspondant en entrant~:

\begin{lstlisting}
Be(1200,300)
\end{lstlisting}

et on obtient~:

\begin{figure}
  \begin{BoxedVerbatim}
    $\mathtt{15\,600}$
 \end{BoxedVerbatim}
\end{figure}

\section{Insertion dans un document \LaTeX{}}

On  peut bien  sûr fabriquer  un  environnement \texttt{proglin}  ainsi~:~on commence  par créer  un
fichier qui sera interprété par \Prog{giac/XCAS}~:

\lat

\begin{lstlisting}
\begin{VerbatimOut}{proglin.cxx}
proglin(L,S,X,XS,B):={
n:=nops(L)-1;
D:=NULL;DX:=NULL;
P:=NULL;PX:=NULL;
F:=[];
Le:=NULL;
Intx:=NULL;
Inty:=NULL;
W:=[0,0,0,0];

for(k:=0;k<=n;k++){L[k]:=solve(L[k],y)[0]; if((size(solve(L[k],x))!=0) and (solve(L[k],x)!=[x])){Intx:=Intx,solve(L[k],x)[0]};
                   F:=append(F,unapply(L[k],x));Inty:=Inty,F[k](0)}

W[0]:=-0.1*maxnorm([Intx]); W[1]:=1.2*(max(maxnorm(X),maxnorm([Intx])));
W[2]:=-0.1*maxnorm([Inty]); W[3]:=1.2*maxnorm([Inty]);

if(nops(X)>0){
nx:=nops(X)-1;
for(k:=0;k<=nx;k++){
 Le:=Le,legende(X[k]+i*(k+1)*W[3]/(k+5),"D"+(n+1+k));
 DX:=DX,droite(x=X[k]);
 PX:=PX,if(XS[k]==p){display(polygone(1.2*W[0]+i*6*W[2],1.2*W[0]+1.2*W[3]*i,X[k]+1.2*W[3]*i,X[k]+i*6*W[2]),(k+5+nx)+rempli);}
              else{display(polygone(1.2*W[1]+i*6*W[2],1.2*W[1]+1.2*W[3]*i,X[k]+1.2*W[3]*i,X[k]+i*6*W[2]),(k+5+nx)+rempli);}
  }
}
 for(k:=0;k<=n;k++){
 Le:=Le,legende(((5-k)*W[0]+(k+2)*W[1])/(7)+i*F[k](((5-k)*W[0]+(k+2)*W[1])/(7)),"D"+k);
 D:=D,droite(y=L[k]);
 P:=P,if(S[k]==m){display(polygone(1.2*W[0]+i*F[k](1.2*W[0]),1.2*W[0]+1.2*W[3]*i,1.2*W[1]+1.2*W[3]*i,1.2*W[1]+i*F[k](1.2*W[1])),(k+2)+rempli);}
               else{display(polygone(1.2*W[0]+i*F[k](1.2*W[0]),1.2*W[0]+6*W[2]*i,1.2*W[1]+6*W[2]*i,1.2*W[1]+i*F[k](1.2*W[1])),(k+2)+rempli);}
  }
xyztrange(W[0],W[1],W[2],W[3],-10,10,-1,6,W[0],W[1],W[2],W[3],1);
Be:=unapply(B,x,y):;
//fB:=unapply(solve(B,y)[0],x);return(fB);
Bmax:=Be(maxnorm([Intx]),maxnorm([Inty]));
D:=D,DX;
P,PX,DX,D,display(droite(B=R),line_width_4),Le;  
}:;
\end{VerbatimOut}
\end{lstlisting}


Puis  on donne  quelques  instructions à  \Prog{XCAS/giac}  pour savoir  trouver  et interpréter  ce
fichier~:


\begin{lstlisting}
\begin{VerbatimOut}{proglin.giac}
maple_mode(0);
read("proglin.cxx");
Sortie:=fopen("XCASproglin.tex");
Resultat:=read("proglin.user");
Resultat:=latex(Resultat);
fprint(Sortie,Unquoted,Resultat);
fclose(Sortie);
\end{VerbatimOut}
\end{lstlisting}

On  fabrique  enfin  un  environnement  \LaTeX{}   qui  lira  nos  instructions  et  les  enverra  à
\Prog{XCAS/giac}  qui  rendra  la  politesse  à  \LaTeX{}  en  lui  envoyant  la  figure  au  format
\texttt{PSTricks}~:


\begin{lstlisting}
\newenvironment{proglin}
{\VerbatimEnvironment\begin{VerbatimOut}{proglin.user}}
{\end{VerbatimOut}
           \immediate\write18{giac  <proglin.giac}
           \begin{center}
             \input{XCASproglin}
           \end{center}
}
\end{lstlisting}

Ainsi, en reprenant l'exemple étudié~:

\begin{lstlisting}
\begin{proglin}
proglin([y,30*x+80*y-60000,y-500,0.05*x+0.1*y-90],[p,m,m,m],[0],[p],8*x+20*y)
\end{proglin}
\end{lstlisting}

donne~:

\begin{proglin}
proglin([y,30*x+80*y-60000,y-500,0.05*x+0.1*y-90],[p,m,m,m],[0],[p],8*x+20*y)
\end{proglin}

\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
