Source Latex
du cours de mathématiques
\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 - \href{https://xymaths.fr/Informatique-Programmation/Exercices/}{xymaths.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}
Télécharger le fichier source