ro-lihd-examen-2003-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� LIHD\\}
{\Large Examen d'exercices du 7 juin 2003}
\end{center}

\section{(10pts)}
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$ .
 \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.

\section{(10pts)}
Soit le probl� en nombres entiers
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max z & = \begin{array}{rcr} x_1 & + & 5x_2 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcr}
-4x_1 & + &  3x_2 &\leq & 6\\
3x_1 & + & 2x_2 &\leq & 18\\
\multicolumn{3}{r}{x_1  ,  x_2} &\in &  \mathbb{N}\\
\end{array}\right.
\end{array}
 }
$$
Donnez, pour ce probl�, un arbre de r�lution par la m�ode du Branch and Bound (r�lution graphique). Identifiez clairement les sous-probl�s associ�aux noeuds de votre arbre ainsi que les solutions de ces sous-probl�s. Si vous pouvez choisir $x_1$ ou $x_2$ pour la s�ration, choisissez $x_1$. 

\end{document}