@ccueil Colles

Source LaTeX icone Optimisation-Programmation-lineaire



Fichier
Type: Cours
File type: Latex, tex (source)
Télécharger le document pdf compilé pdficon
Description
Algorithme et programmation: problèmes d'optimisation, progammation linéaire
Niveau
-
Mots clé
optimisation discrète, programmation linéaire, optimisation sous contraintes, algorithme, programmation
Voir aussi:

Documentation sur LaTeX
pdficon
Source LaTex icone
Télécharger le fichier source pdficon

\documentclass[12pt]{article}
\usepackage{amsfonts}\usepackage{amssymb}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{calc}
\usepackage{enumerate}
\usepackage{array}
\usepackage{pst-all}
\usepackage{pstricks-add}

\usepackage{hyperref}
\hypersetup{
    pdfauthor={Yoann Morel},
    pdfsubject={Algorithmique et programmation - Programmation linéaire},
    pdftitle={Algorithmique et programmation - Programmation linéaire},
    pdfkeywords={Mathématiques, algorithmique, programmation, 
      Programmation linéaire, optimisation, python}
}
\hypersetup{
    colorlinks = true,
    linkcolor = red,
    anchorcolor = red,
    citecolor = blue,
    filecolor = red,
    urlcolor = red
}
\voffset=-1.cm
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\ct}{\centerline}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgen}{\begin{enumerate}}\nwc{\enen}{\end{enumerate}}

\nwc{\la}{\left\{}\nwc{\ra}{\right\}}
\nwc{\lp}{\left(}\nwc{\rp}{\right)}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}

\def\N{{\rm I\kern-.1567em N}}
\def\R{{\rm I\kern-.1567em R}}
\def\C{{\rm C\kern-4.7pt 
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Z{{\sf Z\kern-4.5pt Z}}


\nwc{\tm}{\times}
\nwc{\V}[1]{\overrightarrow{#1}}

\nwc{\zb}{\mbox{$0\hspace{-0.67em}\mid$}}
\nwc{\db}{\mbox{$\hspace{0.1em}|\hspace{-0.67em}\mid$}}

\nwc{\ul}[1]{\underline{#1}}

\newcounter{nex}%[section]
\setcounter{nex}{0}
\newenvironment{EX}{%
\stepcounter{nex}
\bigskip{\noindent {\bf Exercice }\arabic{nex}}\hspace{0.2cm}
}{}

\nwc{\bgex}{\begin{EX}}\nwc{\enex}{\end{EX}}

\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}

\headheight=0cm
\textheight=26.2cm
\topmargin=-1.8cm
\footskip=0.8cm
\textwidth=18.6cm
\oddsidemargin=-1.3cm
\parindent=0.2cm

% Concernant la mise en page des algo:
\definecolor{grayp}{gray}{0.8}
\definecolor{graypc}{gray}{0.65}
\newlength{\ProgIndent}
\setlength{\ProgIndent}{0.6cm}

\nwc{\PI}{\hspace*{\ProgIndent}}
\nwc{\DPI}{\hspace*{2\ProgIndent}}
\nwc{\TPI}{\hspace*{3\ProgIndent}}
\nwc{\QPI}{\hspace*{4\ProgIndent}}

\newlength{\lgcoin}\setlength{\lgcoin}{3ex}
\newlength{\lgshadow}\setlength{\lgshadow}{0.5ex}
\newlength{\phgn}\newlength{\phgnp}
\newlength{\phgng}
\newlength{\plgn}\newlength{\plgng}
\newlength{\phgtq}\newlength{\phgtqg}
\newlength{\plgtq}\newlength{\plgtqg}
\newlength{\plgcoin}\setlength{\plgcoin}{3ex}
\newlength{\plgshadow}\setlength{\plgshadow}{0.5ex}
\nwc{\Prog}[3]{%
  %\par\vspd%
  \bgmp[t]{#2+0.5cm}%\linewidth}
  \hspace*{-0.3pt}\hspace*{-\parindent}\hspace*{-1ex}%
  \psframebox[fillstyle=solid,fillcolor=graypc]{
    \emph{\textcolor{white}{\!\!#1}}} \\
  \vspace*{-0.5ex}\\
  \bgmp{#2}
  %\setlength{\fboxrule}{0.1pt}
  \settototalheight{\phgn}{\phantom{\bgmp{#2}#3\enmp}}
  \setlength{\phgn}{\phgn-2ex}
  \setlength{\plgn}{\linewidth}
  \setlength{\phgtq}{-\phgn}%\addtolength{\hgtq}{-3ex}
  \setlength{\phgtqg}{\phgtq}\addtolength{\phgtqg}{-\lgshadow}
  \setlength{\plgng}{\plgn}\addtolength{\plgng}{\lgshadow}
  \setlength{\plgtq}{\plgn}\addtolength{\plgtq}{-\lgcoin}
  \setlength{\plgtqg}{\plgtq}\addtolength{\plgtqg}{\lgshadow}
  \setlength{\phgnp}{\phgn}\addtolength{\phgnp}{\lgcoin}
  \setlength{\phgng}{\phgnp}\addtolength{\phgng}{\lgshadow}
  \pspolygon[linecolor=white,fillstyle=solid,fillcolor=grayp]%
  (-1ex,-\phgnp)(-1ex,1ex)(\plgn,1ex)(\plgng,0)%
  (\plgng,\phgtqg)(\plgtqg,-\phgng)(-0.5ex,-\phgng)
  \pspolygon[linewidth=0.6pt,linecolor=graypc,fillstyle=solid,fillcolor=graypc]%
  (\plgn,\phgtq)(\plgtq,\phgtq)(\plgtq,-\phgnp)
  \pspolygon[fillstyle=solid,fillcolor=white]%
  (-1ex,-\phgnp)(-1ex,1ex)(\plgn,1ex)%
  (\plgn,\phgtq)(\plgtq,\phgtq)(\plgtq,-\phgnp)
  \par
  \bgmp{\linewidth}#3\enmp
  \enmp\enmp%
}

% et pour les progs casio:
\nwc{\return}{
  \psset{unit=1cm,arrowsize=4pt}
  \psline{<-}(0,0.1)(0.3,0.1)(0.3,0.25)}
\nwc{\disp}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(0.2,0)(0.2,0.15)}



% Bandeau en bas de page
\newcommand{\TITLE}{Algorithmique et programmation}
\author{Y. Morel}
\date{}

\usepackage{fancyhdr}

\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}

\lfoot{Y. Morel - \url{xymaths.free.fr}}
\rfoot{Problèmes d'optimisation - \thepage/\pageref{LastPage}}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\vspace*{-0.4cm}

\renewcommand{\thesection}{\Roman{section} -\hspace{-.6em}}
\ct{\LARGE\bf \TITLE}
\medskip
\ct{\Large\bf Exemples de problèmes d'optimisation}
\bigskip

\bgex{\bf Un constructeur et concessionnaire automobile}

Un constructeur automobile propose deux mod\`eles à la vente,
des grosses voitures et des petites voitures. 
Les voitures de ce fabriquant sont tellement
à la mode qu'il est certain de vendre tout ce qu'il parvient à produire, 
au moins au prix catalogue actuel de 16\,000 euros pour les grosses voitures, 
et 10\,000 euros pour les petites voitures. 

Son problème vient de l’approvisionnement limité en deux matières premières, 
le caoutchouc et l'acier. 

\bgen
\item La construction d’une petite voiture nécessite l’emploi d’une unité
  de caoutchouc et d'une unité d’acier;  
\item la construction d'une grosse voiture nécessite une
  unité de caoutchouc et deux unités d'acier. 
\enen

Ses stocks sont limités: 
il dispose de 40 unités de caoutchouc et de 60 unités 
d'acier. 

L'objectif est de déterminer les nombres de petites et de
grosses voitures que le constructeur doit produire afin de maximiser 
son chiffre d’affaire. 


\bgen
\item On suppose qu'il construit et vend 10 grosses voitures et 12 petites. 

  Donner le nombre d'unités de caoutchouc et d'acier nécessaires. 
  Quel est le chiffre d'affaire correspondant ?

\item On suppose qu'il veut construire 35 grosses voitures et 25 petites. 
  Quel serait son chiffre d'affaire ? 
  
  Est-ce possible compte tenu des ressources en matières premières ? 

\item On note maintenant $x$ le nombre de grosses voitures produites, 
  $y$ le nombre de petites voitures produites, 
  et $z$ le chiffre d'affaire résultant. 


  \bgen[a)]
  \item Donner l'expression du chiffre d’affaire $z$ en fonction de $x$ et $y$. 
  \item Combien peut-on fabriquer au plus de petites voitures (si on ne fabrique que celles là) ? 
    de grosses voitures ? 

    Traduire ces contraintes par des inégalités sur $x$ et $y$. 

  \item Combien d'unités de caoutchouc nécessitent la production 
    de $x$ grosses voitures et $y$ petites ? 
    Combien d'unités d'acier ? 

    Traduire alors les contraintes d'approvisionnement en acier 
    et caoutchouc du constructeur. 
  \enen
\item \'Ecrire un algorithme, puis un programme, 
  qui permet de calculer le chiffre d'affaire 
  pour toutes les possibilités des nombres $x$ et $y$ 
  satisfaisant les contraintes exprimées précédemment, 
  et donnant enfin sa valeur maximale. 
\enen
\enex

\noindent
\bgmp{14cm}
\bgex {\bf Des yaourts à la fraise}

Un fabriquant produit 2 types de yaourts 
à la fraise A et B à partir
de Fraise, de Lait et de Sucre. 
Chaque yaourt doit respecter les
proportions ci-contre de mati\`eres premi\`eres.

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de
sucre.
La vente de 1 Kg de yaourts A et B rapporte respectivement 4 euros et
5 euros.

\medskip
Quelle quantité de yaourts A et B faut-il (et peut-on) fabriquer 
pour obtenir un profit maximal ?
\enex
\enmp\hfill
\bgmp{4cm}
\[\begin{tabular}{c|c|c|}\cline{2-3}
\rule[-1em]{0cm}{2.2em}&A & B \\\hline
\multicolumn{1}{|c|}{\rule[-1em]{0cm}{2.2em}Fraise} & 2 & 1 \\\hline
\multicolumn{1}{|c|}{\rule[-1em]{0cm}{2.2em}Lait} & 1 & 2 \\\hline
\multicolumn{1}{|c|}{\rule[-1em]{0cm}{2.2em}Sucre} & 0 & 1\\\hline
\end{tabular}\]
\enmp


\label{LastPage}
\end{document}
\bigskip
Nous appellerons 
Le problème se traduit alors sous la forme:  
maximiser $z = 16000x + 10000y$
en respectant les contraintes 
\[\bgar{ll}
x + y \leqslant 400 \\
2x + y \leqslant 600 \\
x \geqslant 0, y \geqslant 0.
\enar\]

\end{document}

Haut de la page Haut de la page