ro-examen-2004-juin.tex

Contenu du fichier

\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\addtolength{\voffset}{-3cm}
\addtolength{\textheight}{5cm}
\addtolength{\hoffset}{-2cm}
\addtolength{\textwidth}{3cm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{epsfig}
\newcommand{\pts}[1]{\hspace{-15mm}\makebox[15mm][l]{\fbox{#1 pts}}}
\renewcommand{\thesection}{Question \arabic{section}}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{\theenumii.}
\renewcommand{\tablename}{Tableau}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \begin{tabular}{ll}
 NOM & :\\
 PRENOM & :
\end{tabular} \end{flushleft}

\begin{center}
{\LARGE \bf Recherche op�tionnelle}\\
\bigskip
{\Large FUNDP : 2� licence et ma�ise en Informatique\\}
{\Large Examen d'exercices du 21 avril 2004}
\end{center}

\section{(4 pts)}
Avant de partir en vacances, vous souhaitez faire des sauvegardes sur
disquettes de fichiers importants. Vous avez \`{a} votre disposition une bo� de vingt 
disquettes vierges de capacit\'{e} 1,4 Mo. Voici la taille des seize fichiers que
vous souhaitez sauve\-gar\-der : 26 Ko, 35 Ko, 52 Ko, 77 Ko, 88 Ko, 94 Ko, 137 Ko,
164 Ko, 253 Ko, 364 Ko, 372 Ko, 388 Ko, 406 Ko, 432 Ko, 461 Ko et 851 Ko.\\

\noindent
En supposant que vous ne disposez pas de programme permettant de compresser les
donn\'{e}es et que l'enti�t�'un fichier doit �e sauv�ur la m� disquette, comment r\'{e}partir ces fichiers sur les disquettes de fa\c{c}on \`{a}
minimiser le nombre de disquettes utilis\'{e}es?\\

\noindent
Formulez ce probl� sous la forme d'un mod� \textbf{lin�re}.

\section{(4pts) }
En Australie, la r�lte de canne �ucre est hautement m�nis� Les cannes fra�ement coup� sont achemin� directement
vers une sucrerie dans des wagons qui empruntent un r�au de petites voies ferr�. La teneur en sucre des cannes d'un wagon
d�nd du champ de r�lte et de la maturit�es cannes. Apr�r�lte, cette teneur diminue rapidement par fermentation, au
point que le contenu du wagon devient sans valeur apr�un certain temps. A l'instant $t$, onze wagons pleins, de m� charge,
sont arriv��a sucrerie. Des examens ont permis de d�rminer les pertes en sucre de chaque wagon (en kg/h) et la dur�de
vie des lots (en h �artir de $t$), indiqu� au tableau \ref{CLC}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l|ccccccccccc}
Lot & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\
\hline
Perte (kg/h) & 43 & 26 & 37 & 28 & 13 & 54 & 62 & 49 & 19 & 28 & 30\\
Dur�de vie (h) & 4 & 4 & 1 & 4 & 2 & 4 & 4 & 4 & 3 & 4 & 4\\
\end{tabular}
\caption{\label{CLC}Caract�stiques des lots de canne}
\end{center}
\end{table}

\noindent
Chaque lot peut passer au choix sur une des \textbf{trois} lignes de traitement disponibles, compl�ment �ivalentes. Il n�ssite
\textbf{une} heure de traitement continu. La fin de traitement doit survenir au plus tard �a date de fin de vie du lot.\\

\noindent
Donner un mod� \textbf{lin�re} pour l'ordonnancement de traitement des lots �artir de l'instant $t$, de fa� �inimiser la
perte totale de sucre.

\section{(2pts)}
Donner le probl� dual du probl� lin�re suivant~:
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max z & = \begin{array}{rcrcr} 8 \xi_1 & - & \xi_2 & + &5\xi_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
3\xi_1 & - &\xi_2 & + & \xi_3 & \leq & 3\\
 \xi_1 & + & 2\xi_2 & - &\xi_3 & = & -4\\
\xi_1 & + & \xi_2 & - &\xi_3 & \geq & 2\\
\xi_1 &  &     & & & \geq &  0\\
  &  & \xi_2     & & & \leq & 0\\ 
  &  &      & & \xi_3 &\in &  \mathbb{R} \\   
\end{array}\right.
\end{array}
 }
$$

\section{(4 pts) }
Soit
$$
{\renewcommand{\arraystretch}{1.2}
\renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max  & z = \frac{59}{7}-\frac{4}{7}x_3 -\frac{1}{7}x_4     \\
\mbox{s.c.q.} & \left\{ \begin{array}{rcrcrcrcrcr}
                x_1 &&     & + & \frac{1}{7}x_3 & + & \frac{2}{7}x_4& & &=& \frac{20}{7}  \\
                 & &  x_2  & & &+&x_4 &  & &=& 3  \\
                 & &    & &-\frac{2}{7}x_3 & + & \frac{10}{7}x_4 & + & x_5&=& \frac{23}{7}  \\
                \multicolumn{9}{r}{x_1  ,  x_2   ,  x_3 ,  x_4 , x_5}&>=&0
\end{array} \right.
\end{array}}
$$
un probl� lin�re sous sa forme �ivalente optimale.\\
On ajoute �e probl� la contrainte $x_1\le2$ et on vous demande, en utilisant l'algorithme dual simplexe, de calculer la solution
optimale du probl� modifi�


\section{(6 pts)}
Soit le probl� lin�re
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max z & = \begin{array}{rcr} 2x_1 & + & \theta x_2 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcl}
 -x_1 & + &  x_2 &\leq & 4\\
x_1 & + & 2x_2 &\leq & 20\\
x_1 &  &  &\leq & 8\\
\multicolumn{3}{r}{x_1  ,  x_2} &\geq & 0\\
\end{array}\right.
\end{array}
 }
$$
o�heta$ est un param�e r�.
\begin{enumerate}
\item Discutez la solution optimale de ce probl� en fonction de la valeur de $\theta$. C'est-�ire, pour chaque valeur de $\theta$ comprise entre $-\infty$ et $+\infty$, donnez les valeurs optimales de $x_1$, $x_2$ et $z$.
 \item Donnez un graphique de $z$ en fonction de $\theta$.
 \end{enumerate}
\paragraph{Remarque :} Cette programmation  param�ique peut �e enti�ment r�is�de mani� graphique.

\end{document}