Accueil
slides-problemes.tex
slides-problemes.tex
—
TeX document,
21Kb
Contenu du fichier
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Probl�s lin�res et r�lution graphique}
\newpage
\minitoc
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Un probl� lin�re continu}
\subsection{Enonc�Un chocolatier-confisseur confectionne des assortiments de chocolats. Dans ceux-ci, il a convenu d'y placer 3 sortes de chocolats, d�t�chocolats 1,2 et 3, dont chaque kg lui co�espectivement 4\$, 1,45\$ et 2,40\$. Chaque assortiment doit peser un kg et se vendra 8\$.\par
Le chocolat 1 doit repr�nter entre 10\% et 20\% du poids d'un assortiment. Les chocolats 1 et 2 pr�nts dans un assortiment ne doivent pas peser plus de 800g. Au moins la moiti�u poids d'un assortiment doit provenir des chocolats 1 et 3.\par
Quelle proportion de chaque sorte de chocolats, le chocolatier-confisseur doit-il utiliser pour maximiser les revenus nets qu'il tirera de la vente de ses assortiments ?
\subsection{Formulation}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = profit de la vente d'un assortiment (en \$)
\item $q_1$ = quantit�u chocolat 1 dans un assortiment (en kg)
\item $q_2$ = quantit�u chocolat 2 dans un assortiment (en kg)
\item $q_3$ = quantit�u chocolat 3 dans un assortiment (en kg)
\end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\max z = 8(q_1+q_2+q_3)-(4q_1+1,45q_2+2,40q_3)$
\end{itemize}
\newpage
\subsubsection{Contraintes}
\begin{itemize}
\item $q_1+q_2+q_3=1,000$
\item $q_1 \geq 0,100$
\item $q_1 \leq 0,200$
\item $q_1+q_2 \leq 0,800$
\item $q_1+q_3 \geq 0,500$
\item $q_1,q_2,q_3 \geq 0$
\end{itemize}
\subsection{Solution}
$z=5,915$ avec $q_1=0,100$, $q_2=0,500$ et $q_3=0,400$.
\newpage
\section{Un probl� lin�re en nombres entiers}
\subsection{Enonc\'e}
Un atelier de m�nique cherche \`a recruter des m\'ecaniciens-monteurs pour d\'emarrer la production d'un nouveau moteur de motocyclette.\par
Une petite annonce dans les
quotidiens a permis de susciter la candidature de 2 m\'ecaniciens-monteurs experts (cat\'egorie C1), de 6 m\'ecaniciens-monteurs confirm\'es (cat\'egorie C2) et
de 9 apprentis (cat\'egorie C3). Les informations concernant ces candidats sont donn\'ees par le tableau \ref{ICC}.
\begin{table}[h]
\begin{center}
\begin{tabular}{cccc}
\hline
Cat\'egorie&Nombre de moteurs&Salaire quotidien&Nombre minimal\\
&par jour&(en \$)&d'ann\'ees d'exp\'er.\\
\hline
C1 & 20 & 200 & 10\\
C2 & 15 & 155 & 6\\
C3 & 8 & 90 & 2\\
\hline
\end{tabular}
\caption {\label{ICC} Informations concernant les candidats}
\end{center}
\end{table}
\noindent
L'atelier fonctionne 5 jours par semaine. La direction souhaite fabriquer le plus de moteurs possible tout en ne d\'eboursant pas plus de 8.000 \$
hebdomadairement en salaires. De plus, elle exige que le nombre total des ann\'ees d'exp\'erience de cette nouvelle main-d'oeuvre soit d'au moins 60 ans.\\
Comment doit-elle s'y prendre ?
\subsection{Formulation}
\subsubsection{Dimensions}
\begin{itemize}
\item $N$ = nombre de cat\'egories de m\'ecaniciens-monteurs ($i=1,\ldots,N$)
\end{itemize}
\subsubsection{Donn\'ees}
\begin{itemize}
\item $C_i$ = nombre de candidats m\'ecaniciens-monteurs dans la cat\'egorie i
\item $M_i$ = nombre de moteurs mont\'es par jour par les m\'ecaniciens-monteurs de la cat\'egorie i (en unit�
\item $S_i$ = salaire quotidien des m\'ecaniciens-monteurs\\
de la cat\'egorie i (en \$)
\item $E_i$ = nombre minimal d'ann\'ees d'exp\'erience des m\'ecaniciens-monteurs de la cat\'egorie i (en ann�)
\item $CSM$ = co\^ut salarial hebdomadaire maximum (en \$)
\item $AEM$ = nombre minimum d'ann\'ees d'exp\'erience de l'ensemble des m\'ecaniciens-monteurs engag\'es (en ann�)
\item $NJS$ = nombre de jours de travail par semaine (en jours)
\end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = nombre de moteurs fabriqu\'es par jour
\item $x_i$ = nombre de m\'ecaniciens-monteurs de la cat\'egorie i engag\'es
\end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\max z = \sum_{i=1}^{N}M_i*x_i$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $NJS*\sum_{i=1}^{N}S_i*x_i \leq CSM$
\item $\sum_{i=1}^{N}E_i*x_i \geq AEM$
\item $\displaystyle x_i \leq C_i$ pour $i=1,\ldots,N$
\item $\displaystyle x_i \geq 0$ et entiers pour $i=1,\ldots,N$
\end{itemize}
\subsection{Solution}
$z=154$ avec $x_1=2$, $x_2=6$, $x_3=3$.
\newpage
\section{Un probl� lin�re binaire}
\subsection{Enonc�Un jeu t�vis�ropose �haque concurrent 3 s�es de 7 nombres choisis au hasard entre 1 et 60. Le concurrent doit choisir
une des 3 s�es, puis certains ou tous les nombres composant cette s�e, de fa� �e que la somme des nombres retenus
s'approche le plus pr�possible de 100 mais sans l'exc�r. Voici les 3 jeux de nombres que vient de tirer un concurrent.
\begin{center}
\begin{tabular}{cc}
\begin{tabular}{c|ccc}
\hline
& S1 & S2 & S3 \\
\hline
N1 & 11 & 9 & 3 \\
N2 & 13 & 11 & 23 \\
N3 & 16 & 18 & 31 \\
N4 & 41 & 37 & 53 \\
N5 & 7 & 13 & 11 \\
N6 & 17 & 18 & 17 \\
N7 & 21 & 46 & 21\\
\hline
\end{tabular}
&
\begin{minipage}{5cm}
Quelle s�e le concurrent doit-il choisir et quels sont, dans cette s�e, les nombres �etenir dont la somme s'approche le
plus de 100 ?
\end{minipage}
\end{tabular}
\end{center}
%%%
\subsection{Formulation}
\subsubsection{Dimensions}
\begin{itemize}
\item $S$ = nombre de s�es ($i=1,\ldots,S$)
\item $N$ = nombre de nombres dans chaque s�e ($j=1,\ldots,N$)
\end{itemize}
\subsubsection{Donn�}
\begin{itemize}
\item $V_{ij}$ = valeur du nombre $j$ de la s�e $i$
\item $BS$ = borne sup�eure pour la somme des nombres
\end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = somme des nombres choisis
\item $y_i$ = 1 si la s�e $i$ est choisie
\item $x_{ij}$ = 1 si le nombre $j$ de la s�e $i$ est choisi
\end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\displaystyle \max z = \sum_{i=1}^{S}\sum_{j=1}^{N}V_{ij}*x_{ij}$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\displaystyle \sum_{i=1}^{S}y_i=1$
\item $\displaystyle \sum_{j=1}^{N}V_{ij}*x_{ij}\leq BS *y_i$ pour $i=1,2,\ldots,S$
\item $y_i,x_{ij}\in\{0,1\}$ pour $i=1,2,\ldots,S$ et $j=1,2,\ldots,N$
\end{itemize}
\subsection{Solution}
$z=100$ avec $y_3=1$ et $x_{31}=1$, $x_{32}=1$, $x_{34}=1$, $x_{37}=1$.
\newpage
\section{Un probl� lin�re mixte}
\subsection{Enonc\'{e}}
Il y a dans un atelier 5 al\'{e}seuses qui diff\`{e}rent par la taille et l'\^{a}ge. On doit al\'{e}ser dans la journ\'{e}e 1500 pi\`{e}ces identiques.
Les co\^{u}ts de mise en route des diff\'{e}rentes all\'{e}seuses, leur capacit\'{e}
quotidienne de production et leur co\^{u}t unitaire d'al\'{e}sage se retrouvent dans le
tableau suivant.
\begin{table} [h] \centering
\begin{tabular}{cccc}
\hline & Co\^{u}t de & Co\^{u}t unitaire \\
Al\'{e}seuse & mise en route & d'al\'{e}sage & Capacit\'{e}\\
\hline
A1 & 1000 \$ & 2,00 \$ & 600\\
A2 & 500 \$ & 4,00 \$ & 400\\
A3 & 400 \$ & 5,00 \$ & 500\\
A4 & 600 \$ & 2,50 \$ & 500\\
A5 & 300 \$ & 5,50 \$ & 400\\
\hline
\end{tabular}
\end{table}
Quelle al\'{e}seuses doit-on mettre en route et combien de pi\`{e}ces doit-on al\'{e}ser
sur chacune pour minimiser les co\^{u}ts d'usinage des 1500 pi\`{e}ces ?
\subsection{Formulation}
{\samepage
\vspace{-1mm}
\subsubsection{Dimensions}
\begin{itemize}
\item $NA$ = nombre d'al\'{e}seuses ($i=1,\ldots,NA$)
\end{itemize}
\vspace{-4mm}
\subsubsection{Donn\'{e}es}
\begin{itemize}
\item $CD_i$ = co\^{u}t de d\'{e}marrage de l'al�use $i$ en \$
\item $CU_i$ = co\^{u}t unitaire d'al�ge pour l'al�use $i$ en \$
\item $PM_i$ = production maximale de l'al�use $i$ en pi�s
\item $DEM$ = nombre de pi�s demand�
\end{itemize}
\vspace{-4mm}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = co� production en \$
\item $y_i$ = 1 si l'al\'{e}seuse $i$ est mise en route
\item $x_i$ = nombre de pi\`{e}ces al\'{e}s\'{e}es par jour sur l'al\'{e}seuse $i$
\end{itemize}
}
\subsubsection{Objectif}
\begin{itemize}
\item $\displaystyle\min z = \sum_{i=1}^{NA}(CD_i*y_i + CU_i*x_i)$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\sum_{i = 1}^{NA} x_i \geq DEM$\\
\item $x_i \leq PM_i*y_i$ pour $i=1 \ldots NA$\\
\item $x_i \geq 0$ et $y_i \in \{0,1\}$ pour $i=1 \ldots NA$\\
\end{itemize}
\subsection{Solution}
$z=6150$ avec $y_1=1$, $y_2=1$,$y_4=1$ et $x_1=600$, $x_2=400$, $x_4=500$.
\section{Un probl� de m�nge}
\subsection{Enonc\'e}
L'entreprise Steel a re�une commande de cinq tonnes d'acier destin� la fabrication de coques de bateau. Cet acier doit
avoir les caract�stiques particuli�s du tableau \ref{CAC}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l|cc}
El�nt & Pourcentage & Pourcentage\\
chimique & minimal & maximal\\
\hline
Carbone (C) & 2 & 3\\
Cuivre (Cu) & 0,4 & 0,6\\
Mangan� (Mn) & 1,2 & 1,65
\end{tabular}
\caption{\label{CAC}Caract�stiques de l'acier command�\end{center}
\end{table}
\noindent
Pour fabriquer cet acier, Steel dispose de sept mati�s premi�s dont les caract�stiques, les quantit�disponibles et
les co�'achat sont donn�au tableau \ref{CMP}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l|cccccc}
Mati� premi� & C (\%) & Cu (\%) & Mn (\%) & Stocks (kg) & Co�F/kg)\\
\hline
Alliage de fer 1 & 2,5 & 0 & 1,3 & 4000 & 1,20\\
Alliage de fer 2 & 3 & 0 & 0,8 & 3000 & 1,50\\
Alliage de fer 3 & 0 & 0,3 & 0 & 6000 & 0,90\\
Alliage de cuivre 1 & 0 & 90 & 0 & 5000 & 1,30\\
Alliage de cuivre 2 & 0 & 96 & 4 & 2000 & 1,45\\
Alliage d'aluminium 1 & 0 & 0,4 & 1,2 & 3000 & 1,20\\
Alliage d'aluminium 2 & 0 & 0,6 & 0 & 2500 & 1,00
\end{tabular}
\caption{\label{CMP}Caract�stiques des mati�s premi�s}
\end{center}
\end{table}
D�rminer la composition de l'acier �abriquer pour minimiser les co�e production.
\subsection{Formulation}
\subsubsection{Dimensions}
\begin{itemize}
\item $M$ = nombre de mati�s premi�s ($i=1, 2,\ldots,M$)
\item $E$ = nombre d'�ments chimiques ($j=1, 2,\ldots,E$)
\end{itemize}
\subsubsection{Donn�}
\begin{itemize}
\item $D$ = quantit�en kg) d'acier de la commande
\item $P_{ij}$ = pourcentage d'�ment chimique $j$ contenu dans la mati� premi� $i$
\item $S_i$ = stock (en kg) de mati� premi� $i$ disponible
\item $C_i$ = co�n F/kg) de la mati� premi� $i$
\item $PMIN_j$ = pourcentage minimal d'�ment chimique $j$ que doit contenir l'acier command�item $PMAX_j$ = pourcentage maximal d'�ment chimique $j$ que doit contenir l'acier command�end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = co�n F) pour satisfaire la commande
\item $x_i$ = quantit�en kg) de mati� premi� $i$ utilis�pour satisfaire la commande
\item $q$ = quantit�en kg) d'acier fabriqu�end{itemize}
\subsection{Objectif}
\begin{itemize}
\item $\displaystyle \min z = \sum_{i=1}^{M}C_i*x_i$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\sum_{i=1}^{M}x_i=q$
\item $q\geq D$
\item $\sum_{i=1}^{M}P_{ij}*x_i\geq PMIN_j*q$ pour $j=1, 2,\ldots,E$
\item $\sum_{i=1}^{M}P_{ij}*x_i\leq PMAX_j*q$ pour $j=1, 2,\ldots,E$
\item $x_i\leq S_i$ pour $i=1, 2,\ldots,M$
\item $x_i\geq 0$ pour $i=1, 2,\ldots,M$ et $q\geq0$
\end{itemize}
\subsection{Solution}
$$
\begin{array}{lr|lr|lr}
z &5888.57& x_{AFER2} & 0.00& x_{ACUI2} & 27.61\\
q &5000.00& x_{AFER3} &397.76& x_{AALU1} &574.62\\
x_{AFER1}&4000.00& x_{ACUI1} & 0.00& x_{AALU2} & 0.00\\
\end{array}
$$
\newpage
\section{Un probl� d'affectation}
\subsection{Enonc\'e}
Chacune des six machines d'un atelier doit recevoir un op\'erateur. Six personnes ont \'et\'e pr\'es\'electionn\'ees. Chacune d'elles a subi un test
de productivit\'e sur chaque machine. Le tableau ci-dessous donne les productivit\'es obtenues, en pi\`eces par heure. Les machines sont en
parall\`ele, c'est-\`a-dire que la productivit\'e totale de l'atelier est la somme des productivit\'es des personnes affect\'ees aux
machines.
\begin{center}
\begin{tabular}{cc}
{%\renewcommand{\arraystretch}{0.9}
\begin{tabular}{c|cccccc}
& M1 & M2 & M3 & M4 & M5 & M6 \\
\hline
P1 & 13 & 24 & 31 & 19 & 40 & 29\\
P2 & 18 & 25 & 30 & 15 & 43 & 22\\
P3 & 20 & 20 & 27 & 25 & 34 & 33\\
P4 & 23 & 26 & 28 & 18 & 37 & 30\\
P5 & 28 & 33 & 34 & 17 & 38 & 20\\
P6 & 19 & 36 & 25 & 27 & 45 & 24\\
\end{tabular}}
&
\begin{minipage}{5.5cm}
L'objectif est de d\'eterminer une affectation des personnes aux
machines permettant de maximiser la productivit\'e totale.
\end{minipage}
\end{tabular}
\end{center}
\subsection{Formulation}
\subsubsection{Dimensions}
\begin{itemize}
\item $P$ = nombre de personnes s�ctionn� ($i=1,\ldots,P$)
\item $M$ = nombre de machines ($j=1,\ldots,M$)
\end{itemize}
\subsubsection{Donn\'ees}
\begin{itemize}
\item $PROD_{ij}$ = productivit\'e de la personne $i$ sur la machine $j$ (en pi�s par heure)
\end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = nombre de pi�s fabriqu� par heure
\item $x_{ij}$ = 1 si la personne $i$ est affect�\`a la machine $j$
\end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\displaystyle \max z = \sum_{i=1}^{P} \sum_{j=1}^{M} PROD_{ij}x_{ij}$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\sum_{i=1}^{P}x_{ij}\le1$ pour $j=1,\ldots,M$
\item $\sum_{j=1}^{M}x_{ij}\le1$ pour $i=1,\ldots,P$
\item $x_{ij}\in\{ 0,1\}$ pour $i=1,\ldots,P$ et $j=1,\ldots,M$
\end{itemize}
\subsection{Solution}
$z=193$ avec\\
$x_{13}=1$, $x_{25}=1$, $x_{34}=1$, $x_{46}=1$, $x_{51}=1$, $x_{62}=1$.
\newpage
\section{Un probl� de ravitaillement}
\subsection{Enonc�Un pays de l'asie du Sud-Est vient de subir des inondations d'une rare ampleur. Le gouvernement d�de de mettre en place un syst� de ravitaillement par avion. Malheureusement, il ne peut s'appuyer que sur sept pistes d'atterrissage encore en bon �t pour assurer des livraisons de vivres et de m�caments de premi� urgence.\\
\begin{tabular}{cc}
\begin{tabular}{c|ccccccc}
&A2&A3&A4&A5&A6&A7\\
\hline
A1 & 786 & 549 & 657 & 331 & 559 & 250 \\
A2 & - & 668 & 979 & 593 & 224 & 905\\
A3 & - & - & 316 & 607 & 472 & 467 \\
A4 & - & - & - & 890 & 769 & 400\\
A5 & - & - & - & - & 386 & 559\\
A6 & - & - & - & - & - & 681\\
\end{tabular}
&
\begin{minipage}{5.5cm}
Le gouvernement d�de de faire partir des avions de la capitale pour qu'ils visitent les six autres a�ports et reviennent en fin de parcours �a capitale. Le tableau ci-contre donne les distances (en km) entre a�ports.
\end{minipage}\\
\end{tabular}
Sachant que A1 est l'a�port de la capitale, quel devra �e l'ordre de visite des autres a�ports pour parcourir une distance minimale~?
\subsection{Formulation}
\subsubsection{Dimension}
\begin{itemize}
\item $N$ = nombre d'a�ports
\end{itemize}
\subsubsection{Donn�}
\begin{itemize}
\item $D_{ij}$ = distance de l'a�port $i$ �'a�port $j$ (en km)
\end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = longueur du parcours
\item $x_{ij}$ = 1 si les avions circulent de l'a�port $i$ �'a�port $j$ ($i\neq j$)
\end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\displaystyle \min z = \sum_{i=1}^{N} \sum_{j=1}^{N} D_{ij}x_{ij}$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\displaystyle \sum_{i=1,i\neq j}^{N}x_{ij}=1$ pour $j=1,\ldots,N$
\item $\displaystyle \sum_{j=1,i\neq j}^{N}x_{ij}=1$ pour $i=1,\ldots,N$
\item $\displaystyle \sum_{i\in S} \sum_{j\in S}x_{ij}\leq |S|-1$ pour $S\subseteq \{1,2\ldots,N\}$ et $2\leq|S|\leq N-1$
\item $x_{ij}\in\{ 0,1\}$ pour $i=1,\ldots,N$, $j=1,\ldots,N$ et $i\neq j$
\end{itemize}
\subsection{Solution}
$z=2575$ avec\\
$x_{17}=1$, $x_{74}=1$, $x_{43}=1$, $x_{32}=1$, $x_{26}=1$, $x_{65}=1$, $x_{51}=1$.
\newpage
\section{R�lution graphique d'un probl� lin�re continu}
\begin{tabular}[c]{c}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& x_{1} &+& x_{2} &\le& 14\\
-& 2x_{1} &+& 3x_{2} &\le& 12\\
& 2x_{1} &-& x_{2} &\le& 12\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\\
\\
$(x_1,x_2)^*=(6,8)$\\
$z^*=30$
\end{tabular}
\hspace{5mm} {
% PARAMETRES
\psset{unit=0.35cm}
%\psset{arrowsize=4pt 3}
\psset{arrowinset=0}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-3,-3)(13,13)
% AXES
%,labels=none
\psaxes[Dx=2,Dy=2,tickstyle=top]{->}(0,0)(-3,-3)(12,12)
\rput(13,0){$x_1$}\rput(0,13){$x_2$}
% CONTRAINTES
\psline(4,10)(10,4) \psline(-2,2.66)(9,10) \psline(5,-2)(10,8)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,4)(6,8)(8.66,5.33)(6,0)
% OBJECTIF
\psline[linestyle=dashed](0,6)(9,3)
\psline{->}(1,6)(1.25,6.75)
% \psdots*[dotstyle=*,dotscale=1.5](6,8)
\end{pspicture}
}
\newpage
\paragraph{Exercices}
\begin{enumerate}
\item Modifier l'objectif du probl� pour que la solution optimale soit un autre sommet du polygone des solutions r�isables.
\item Modifier le probl� pour que celui-ci poss� plusieurs solutions optimales.
\item Modifier le probl� pour qu'il soit non born�\item Modifier le probl� pour qu'il ne poss� aucune solution r�isable.
\end{enumerate}
\newpage
\section{R�lution graphique d'un probl� non lin�re}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\mbox{max } & z = (6-x_1) x_1 + (8-x_2) x_2\\ [5mm]
\mbox{s.c.q. } & \left\{ \begin{array}{rcrcr}
6 x_1 &+& 5 x_2 &\le& 60\\
x_1 &+& 2 x_2 &\le& 15\\
x_1 & & &\le& 8\\
\multicolumn{3}{r}{x_{1}, x_{2}} &\ge& 0
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (3,4)$$
$$z^* = 25$$
\end{minipage}
&
\begin{minipage}{5cm}
% PARAMETRES
\psset{unit=0.45cm}
\psset{arrowinset=0}
%\psset{arrowsize=3pt 3}
%\psset{arrowinset=0} \fontsize{7}{1}\selectfont
\begin{pspicture}(-1,-1)(10,10)
% AXES
%,labels=none
\psaxes[Dx=3,Dy=3,tickstyle=full]{->}(0,0)(-1,-1)(9,9)
\rput(9.5,0){$x_1$}\rput(0,9.5){$x_2$}
% CONTRAINTES
\psline(8,-0.5)(8,3)\psline(9,1.2)(6,4.8)\psline(7,4)(-1,8)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,7.5)(6.43,4.29)(8,2.4)(8,0)
% SOLUTION
\pscircle(3,4){1}\pscircle(3,4){2}\pscircle(3,4){3}\pscircle(3,4){4}
\psdots*[dotstyle=*,dotscale=1.5](3,4)
\end{pspicture}
%\BoxedEPSF{FUNDP_AD_SLIDES.eps/nonlin.eps scaled 800}
\begin{center}
Les courbes $z=k$ sont des cercles, de rayon $\sqrt{25-k}$,
centr\'es en $(3,4)$.
\end{center}
\end{minipage}
\end{tabular}
\section{R�lution graphique d'un probl� lin�re en nombres entiers}
\subsection{Formulation 1}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$ {\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\mbox{max } & z = x_1 + x_2,\\ [5mm]
\mbox{s.c.q. } & \left\{ \begin{array}{rcrcr}
2 x_1 &+& 2 x_2 &\ge& 3, \\
2 x_1 &-& 2 x_2 &\le& 3, \\
2 x_1 &+& 4 x_2 &\le& 19,\\
\multicolumn{5}{r}{x_1 , x_2 \ge 0 \mbox{ et entiers.}}
\end{array}\right.
\end{array}}
$$
$$(x_1,x_2)^* = (3,3)$$
$$z^* = 6$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=0.7cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-1.5,-1.5)(6,6)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-1.5,-0.5)(5.5,5.5)
\rput(6,0){$x_1$}\rput(0,6){$x_2$}
% CONTRAINTES
\psline(-0.5,2)(2,-0.5) \psline(1,-0.5)(5,3.5) \psline(-0.5,5)(5,2.25)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,1.5)(0,4.75)(4.17,2.67)(1.5,0)
% OBJECTIF
\psline[linestyle=dashed](-0.5,4)(3,0.5)
\psline{->}(1.7,2)(2.1,2.4)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,2)\psdots(0,3)\psdots(0,4)
\psdots(1,1)\psdots(1,2)\psdots(1,3)\psdots(1,4)
\psdots(2,1)\psdots(2,2)\psdots(2,3)
\psdots(3,2)\psdots(3,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(-1,0)\psdots(-1,1)\psdots(-1,2)\psdots(-1,3)\psdots(-1,4)\psdots(-1,5)
\psdots(0,0)\psdots(0,1)\psdots(0,5)
\psdots(1,0)\psdots(1,5)
\psdots(2,0)\psdots(2,4)\psdots(2,5)
\psdots(3,0)\psdots(3,1)\psdots(3,4)\psdots(3,5)
\psdots(4,0)\psdots(4,1)\psdots(4,2)\psdots(4,3)\psdots(4,4)\psdots(4,5)
\end{pspicture}
}
\end{tabular}
\paragraph{N.B. : } La solution optimale du probl� continu est $(x_1,x_2)=(4\frac{1}{6},2\frac{2}{3})$.
\subsection{Formulation 2}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.1}
\begin{array}{ll}
\mbox{max } & z = x_1 + x_2,\\ [5mm]
\mbox{s.c.q. } & \left\{ \begin{array}{rcrcr}
x_1 &+& x_2 &\ge& 2, \\
&& x_2 &\ge& 1, \\
x_1 &-& x_2 &\le& 1, \\
x_1 & & &\le& 3, \\
x_1 &+& 2 x_2 &\le& 9,\\
& & x_2 &\le& 4, \\
x_1 & & &\ge& 0, \\
\multicolumn{5}{r}{x_1 , x_2 \mbox{ entiers.}}
\end{array}\right.
\end{array}}
$$
\end{minipage}
&
\begin{minipage}{5cm}
{
% PARAMETRES
\psset{unit=0.7cm} \psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-1.5,-1.5)(6,6)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-1.5,-0.5)(5.5,5.5)
\rput(6,0){$x_1$}\rput(0,6){$x_2$}
% CONTRAINTES
\psline(-0.25,2.25)(1.25,0.75) \psline(0.75,1)(2.25,1)
\psline(1.75,0.75)(3.25,2.25)
\psline(3,1.75)(3,3.25)\psline(3.25,2.875)(0.75,4.125)\psline(-0.25,4)(1.25,4)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](1,1)(2,1)(3,2)(3,3)(1,4)(0,4)(0,2)
% OBJECTIF
\psline[linestyle=dashed](-0.5,4)(3,0.5) \psline{->}(1.7,2)(2.1,2.4)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,2)\psdots(0,3)\psdots(0,4)
\psdots(1,1)\psdots(1,2)\psdots(1,3)\psdots(1,4)
\psdots(2,1)\psdots(2,2)\psdots(2,3) \psdots(3,2)\psdots(3,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(-1,0)\psdots(-1,1)\psdots(-1,2)\psdots(-1,3)\psdots(-1,4)\psdots(-1,5)
\psdots(0,0)\psdots(0,1)\psdots(0,5) \psdots(1,0)\psdots(1,5)
\psdots(2,0)\psdots(2,4)\psdots(2,5)
\psdots(3,0)\psdots(3,1)\psdots(3,4)\psdots(3,5)
\psdots(4,0)\psdots(4,1)\psdots(4,2)\psdots(4,3)\psdots(4,4)\psdots(4,5)
\end{pspicture}
}
$$(x_1,x_2)^* = (3,3)$$
$$z^* = 6$$
\end{minipage}
\end{tabular}
\paragraph{N.B. : } La solution optimale du probl� continu est $(x_1,x_2)=(3,3)$.
%\newpage
%\mbox{ }
