ro-lihd-examen-2004-juin.tex

Contenu du fichier

\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\addtolength{\voffset}{-3.5cm}
\addtolength{\textheight}{5.5cm}
\addtolength{\hoffset}{-2cm}
\addtolength{\textwidth}{4cm}
\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� LIHD\\}
{\Large Examen d'exercices du 2 juin 2004}
\end{center}

\section{(8 pts)}
Avant de partir en vacances, vous souhaitez faire des sauvegardes sur
disquettes de fichiers im\-portants. 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{(4 pts)}
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{(8 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� gra\-phique.

\end{document}