\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,numprint}
\usepackage[dvips]{color}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage{tikz}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
\textwidth 19,5cm \textheight 27cm \hoffset 
-1,7cm \voffset -4cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{red}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}.\arabic{subsubsection}}} 
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}
\title{\fbox{\textcolor{blue}{\textbf{Optimisation linéaire}}}}
\date{}
\begin{document}
\maketitle

\subsection*{\textcolor{red}{Activité préparatoire page 49}}

\begin{enumerate}
\item $\mathscr{D}_{1}$ passe par les points $A(2~;~6)$ et $B(4~;~3)$.\\
Le coefficient directeur vaut $a_{1}=-\dfrac{3}{2}$. L'équation réduite est : $y=a_{1}x+b_{1}$ donc $y=-\dfrac{3}{2}x+b_{1}$.\\
Pour $x=2$, n doit avoir $y=6$ donc $6=-\dfrac{3}{2}\times 2+b_{1}$ : $b_{1}=9$.\\
L'équation est : $y=-\dfrac{3}{2}x+9$.\\
On obtient également : $2y=-3x+18$ d'où $3x+2y=18$.

\item Soit $\mathscr{D}_{2}$ la droite passant par A et parallèle à l'axe des ordonnées : son équation est $x=2$.

\item $\mathscr{D}_{3}$ passe par B et est parallèle à l'axe des abscisses : son équation est $y=3$.

\item C est le point d'abscisses 1 de $\mathscr{D}_{2}$ : C$(1~;~2)$.

\item Soit $\mathscr{D}_{4}$ la droite d'équation $x-y=1$. Cela équivaut à $y=x-1$.
\end{enumerate}
\begin{center}
\psset{yunit=0.5,algebraic=true}
\begin{pspicture}(-1,-4)(8,10)
\psgrid[subgriddiv=1,gridlabels=0,gridwidth=0.3pt](-1,-4)(8,10)%grille
\psline[linewidth=0.8pt]{->}(-1,0)(8,0)%axe horizontal
\psline[linewidth=0.8pt]{->}(0,-4)(0,10)%axe vertical
%repère
\uput[dl](0,0){$O$}
\psline{->}(0,0)(1,0)
\psline{->}(0,0)(0,1)
\uput[d](0.7,0){$\overrightarrow{i}$}
\uput[l](0,0.5){$\overrightarrow{j}$}
\psplot{0}{8}{-1.5*x+9}
\psline[linecolor=blue](2,-4)(2,10)
\psline[linecolor=red](-1,3)(8,3)
\psplot{0}{8}{x-1}
\uput[u](0,9){$\mathscr{D}_{1}$}\uput[r](2,-1){$\mathscr{D}_{2}$}\uput[u](1,3){$\mathscr{D}_{3}$}\uput[u](7,6){$\mathscr{D}_{4}$}
\psdots(2,6)(4,3)(2,3)(2,1)
\uput[l](2,6){A}
\uput[l](4,3){B}
\uput[l](2,3){D}
\uput[l](2,1){C}
\end{pspicture}
\end{center}
2) On s'intéresse au système : $\left\{\begin{array}{l}3x+2y\leqslant 18\\x\geqslant 2\\y\leqslant 3\\x-y\leqslant 1\end{array}\right.$.
\begin{enumerate}
\item Avec le point $(0,0)$, on obtient l'inégalité $0\leqslant 18$ sui est vraie. Le demi-plan solution est le demi-plan de frontière $\mathscr{D}_{1}$ et contenant (0~;~0).\\
On hachure le demi-plan qui ne convient pas.

\item 

\item 

\item 
\end{enumerate}
Finalement, l'ensemble des solutions est l'intérieur du triangle BCD, bords compris

\newpage
\subsection*{\textcolor{red}{Activité préparatoire \no 2 page 51}}

\subsection{}


\begin{enumerate}
\item Soient les droites $\mathscr{D}_{1}$ et $\mathscr{D}_{2}$ d'équations $2x+y=2$ et $-x+y=2$.\\
\begin{center}
\psset{algebraic=true}
\begin{pspicture}(-1,-1)(4,4)
\psgrid[subgriddiv=10,gridlabels=0,gridwidth=0.3pt](-1,-1)(4,4)%grille
\psline[linewidth=0.8pt]{->}(-1,0)(4,0)%axe horizontal
\psline[linewidth=0.8pt]{->}(0,-1)(0,4)%axe vertical
%repère
\uput[dl](0,0){$O$}
\psline{->}(0,0)(1,0)
\psline{->}(0,0)(0,1)
\uput[d](0.7,0){$\overrightarrow{i}$}
\uput[l](0,0.5){$\overrightarrow{j}$}
\psplot{-1}{1.5}{2-2*x}
\psplot{-1}{2}{2+x}
\psline[linewidth=2pt,linecolor=red](1.5,-1)(1.5,4)
\psline[linewidth=2pt,linecolor=blue](-1,1)(4,1)
\uput[l](-0.5,3){$\mathscr{D}_{1}$}\uput[d](2,4){$\mathscr{D}_{2}$}\uput[r](1.5,0.5){$\mathscr{D}_{3}$}\uput[u](3,1){$\mathscr{D}_{4}$}
\psdots(0,2)(0.5,1)(1.5,1)(1.5,3.5)
\uput[l](0,2){A}\uput[l](0.5,1){B}\uput[ul](1.5,1){C}\uput[l](1.5,3.5){A}
\end{pspicture}

\end{center}
\item En résolvant le système $\left\{\begin{array}{l}2x+y=2\\-x+y=2\end{array}\right.$, on trouve $(x~;~y)=(0,2)$.\\
Les deux droites se coupent au point de coordonnées $(0~;~2)$.

\item Les équations réduites sont : $y=-2x+2$ et $y=x+2$.

\item $\mathscr{D}_{3}$ a pour équation $x=1,5$ et $\mathscr{D}_{4}$ $y=1$.

\item voir figure
\end{enumerate}




\subsection{}


\begin{enumerate}
\item Les inégalités seront larges.

\item Demi-plan de frontière $\mathscr{D}_{1}$, contenant ABCD : $2x+y\geqslant 2$.

\item Demi-plan de frontière $\mathscr{D}_{2}$, contenant ABCD : $-x+y\leqslant 2$.

\item Demi-plan situé à gauche de $\mathscr{D}_{3}$ : $x\leqslant 1,5$

\item Demi-plan situé au-dessus de $\mathscr{D}_{4}$ : $y\geqslant 1$.

\item ABCD est l'ensemble des points de coordonnées $(x~;~y)$ vérifiant le système :$\left\{\begin{array}{l}2x+y\geqslant 2\\-x+y\leqslant 2\\x\leqslant 1,5\\y\geqslant 1\end{array}\right.$.
\end{enumerate}

\setcounter{subsection}{0}
\subsection{\textcolor{red}{\textcolor{red}{Régionnement du plan}}}

Le plan est muni d'un repère.\\
$a$, $b$ et $c$ sont trois nombres ; $a$ et $b$ ne sont pas simultanément nuls.

\subsubsection{\textcolor{blue}{Droite d'équation $ax+by=c$}}
On a vu en seconde que l'ensemble des points de coordonnées $(x~;~y)$ vérifiant une relation du type $ax+by=c$ est une droite et réciproquement, pour une droite donnée, il existe trois nombres $a$, $b$ et $c$, $a$ et $b$ non nuls simultanément caractérisée par une équation $ax+by=c$.\\
Si $b\neq 0$, on peut se ramener à une équation réduite : $y=-\dfrac{a}{b}c+\dfrac{c}{b}$.\\
Si $b=0$, alors $a\neq 0$ et $x=\dfrac{c}{a}$.\\\\

\newpage
\textbf{\textcolor{blue}{Exemples : }}
\begin{enumerate}
\item $2x+3y=7$ se transforme en $3y=-2x+7$ puis $y=\dfrac{-2}{3}x+\dfrac{7}{3}$ (droite de coefficient directeur $-\dfrac{2}{3}$)

\item $5x=7$ se transforme en $x=\dfrac{7}{5}$ (droite parallèle à l'axe des ordonnées)
\end{enumerate}

\subsubsection{\textcolor{blue}{Demi-plan et frontières}}
La droite $\mathscr{D}$ d'équation $ax+by=c$ partage le plan en deux demi-plans, de frontière $\mathscr{D}$.
\begin{enumerate}[$\bullet$]
\item L'un est caractérisé par la relation $ax+by< c$ (frontière $\mathscr{D}$ exclue)

\item L'autre est caractérisé par la relation $ax+by> c$ (frontière $\mathscr{D}$ exclue)
\end{enumerate}
Pour savoir quelle inéquation, on peut tester sur les coordonnées d'un point connu ou raisonner sur les inéquations réduites.\\\\
\textbf{\textcolor{red}{Exemples :}}
\begin{enumerate}
\item \text{ }\\
\parbox{8cm}{Soit l'inéquation $2x+3y\leqslant 7$ ; elle es transforme en $3y\leqslant -2x+7$ puis $y\leqslant -\dfrac{2}{3}x+\dfrac{7}{3}$.\\
$y=-\dfrac{2}{3}x+\dfrac{7}{3}$ est l'équation d'une droite. Pour une valeur $x$ donnée, le point de coordonnées $(x~;~y)$ avec $y=-\dfrac{2}{3}x+\dfrac{7}{3}$ appartient à cette droite.\\
Les points de même abscisses $x$, mais avec $y<-\dfrac{2}{3}x+\dfrac{7}{3}$ sont en dessous de ce point.}\hfill
\parbox{10cm}{\begin{center}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-5,-2)(4,5)
\psaxes[xAxis=true,yAxis=true,Dx=1,Dy=1,ticksize=-2pt 0,subticks=2]{->}(0,0)(-2,-2)(4,5)
\psgrid[subgriddiv=1,gridlabels=0,gridwidth=0.3pt](-2,-2)(4,5)%grille
\psline[linewidth=0.8pt]{->}(-2,0)(4,0)%axe horizontal
\psline[linewidth=0.8pt]{->}(0,-2)(0,5)%axe vertical
%repère
\uput[dl](0,0){$O$}
\psplot[plotpoints=200,linecolor=red,linewidth=1pt]{-2.0}{4.0}{-2*x/3+7/3}
\uput[l](-2,3.5){$y= -\dfrac{2}{3}x+\dfrac{7}{3}$}
\uput[l](3,-1.5){\textcolor{red}{$y\leqslant  -\dfrac{2}{3}x+\dfrac{7}{3}$}}
\uput[l](3,3){\textcolor{blue}{$y\geqslant  -\dfrac{2}{3}x+\dfrac{7}{3}$}}
\end{pspicture*}
\end{center}}

\item \text{ }\\
 \parbox{8cm}{Soit l'inéquation $3x-5y\geqslant 1$ ; elle se transforme en $-5y\geqslant -3x+1$ puis $y\leqslant \dfrac{3}{5}x-\dfrac{1}{5}$.\\
$y=\dfrac{3}{5}x-\dfrac{1}{5}$ est l'équation d'une droite. Pour une valeur $x$ donnée, le point de coordonnées $(x~;~y)$ avec $y=\dfrac{3}{5}x-\dfrac{1}{5}$ appartient à cette droite.\\
Les points de même abscisses $x$, mais avec $y<\dfrac{3}{5}x-\dfrac{1}{5}$ sont en dessous de ce point.}\hfill
\parbox{10cm}{\begin{center}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-5,-2)(4,5)
\psaxes[xAxis=true,yAxis=true,Dx=1,Dy=1,ticksize=-2pt 0,subticks=2]{->}(0,0)(-2,-2)(4,5)
\psgrid[subgriddiv=1,gridlabels=0,gridwidth=0.3pt](-2,-2)(4,5)%grille
\psline[linewidth=0.8pt]{->}(-2,0)(4,0)%axe horizontal
\psline[linewidth=0.8pt]{->}(0,-2)(0,5)%axe vertical
%repère
\uput[dl](0,0){$O$}
\psplot[plotpoints=200,linecolor=red,linewidth=1pt]{-2.0}{4.0}{3*x/5-1/5}
\uput[u](2,1){$y=\dfrac{3}{5}x-\dfrac{1}{5}$}
\uput[u](2,4){\textcolor{red}{$y>\dfrac{3}{5}x-\dfrac{1}{5}$}}
\uput[u](2,-2){\textcolor{blue}{$y<\dfrac{3}{5}x-\dfrac{1}{5}$}}
\end{pspicture*}
\end{center}}
\end{enumerate}


\subsubsection{\textcolor{blue}{Résolution graphique d'un système}}
Résoudre graphiquement un système d'équations linéaires à deux inconnues $x$ et $y$ revient à déterminer la région du plan telle qu l'ensemble des points de coordonnées $(x~;~y)$ vérifient simultanément chaque inéquation.\\
Cette région est l'intersection de chaque demi-plan, solution de chacune des inéquations.

\newpage
\subsection{\textcolor{red}{Programmation linéaire}}


\subsubsection*{\textcolor{blue}{Activité 3 pages 64-65}}
\textbf{1.)}\\
\begin{enumerate}
\item $x$ et $y$ sont des nombres d'objets, donc des nombres entiers naturels.

\item En traduisant les données, on obtient le système : $\left\{\begin{array}{l}x\leqslant 10\\y\leqslant 8\\x+y\leqslant 12\end{array}\right.$.

\item Soit $p$ le profit : $p=120x+160y$.

\item Il faut donc maximiser l'expression $120x+160y$ avec les contraintes $\left\{\begin{array}{l}x\leqslant 10\\y\leqslant 8\\x+y\leqslant 12\end{array}\right.$..
\end{enumerate}
\textbf{2).}\\

\begin{enumerate}
\item \textbf{\textcolor{red}{Tracés}} :\\
\begin{center}
\psset{unit=0.5,algebraic=true}
\begin{pspicture}(-2,-2)(18,18)
\psaxes[xAxis=true,yAxis=true,Dx=1,Dy=1,ticksize=-2pt 0,subticks=2]{->}(0,0)(-2,-2)(18,18)
\psgrid[subgriddiv=1,gridlabels=0,gridwidth=0.3pt](0,0)(10,8)%grille
\psline(10,0)(10,18)
\psline(0,8)(18,8)
\pspolygon[fillstyle=vlines](0,12)(12,12)(12,0)
\pspolygon[fillstyle=hlines](10,17)(16,17)(16,0)(10,0)
\pspolygon[fillstyle=crosshatch](0,8)(0,17)(15,17)(15,8)
\psdots(0,8)(4,8)(10,2)(10,0)
\uput[d](0,8){A}
\uput[d](4,8){B}
\uput[d](10,2){C}
\uput[d](10,0){D}
\psplot[linecolor=red]{0}{6}{(15-3*x)/4}
\psplot[linecolor=blue]{0}{7}{(20-3*x)/4}
\psplot[linewidth=2pt]{-1}{13}{(44-3*x)/4}
\uput[u](13,2){$\Delta_{p_{m}}$}
\end{pspicture}
\end{center}
La partie du plan solution du système de contraintes est le polygone ABCD.
\item \textbf{\textcolor{red}{Optimisation}}\\
Tra\c cons la droite $\Delta_{1}$ d'équation : $120x+160y=600$ qui se simplifie en $3x+4y=15$ d'où $y=-\dfrac{3}{4}x+\dfrac{15}{4}$.\\
On regarde alors les intersubsections de cette droite avec les n\oe uds du quadrillage, pour tourver des points à coordonnées entières.\\
On trouve plusieurs couples solutions (1~;~3) et {5~;~0}.\\\\
Tra\c cons la droite $\Delta_{2}$ d'équation $120x+160y=800$. Cela correspond à $3x+4y=20$ d'où $y=\dfrac{-3x+20}{4}$.\\
La droite $\Delta_{m}$ qui correspondra à un profit maximal $p_{m}$ a pour équation : $120x+160y=p_{m}$ ou $y=\dfrac{p_{m}-120x}{160}$.\\
$\Delta_{m}$ est parallèle à $\Delta_{1}$ ou $\Delta_{2}$.\\
L'ordonnée à l'origine est $\dfrac{p_{m}}{160}$ ; plus $p_{m}$ est grand, plus cette ordonnée à l'origine est grande.\\
On est donc amené à tracer la droite parallèle à $\Delta_{1}$, d'ordonnée à l'origine la plus grande possible et qui a une intersubsection avec la portion du plan solution du système de contraintes.\\
C'est la droite qui passe par B(4~;~8).\\

Le profit est alors de $4\times 120+8\times 160=\numprint{1760}\text{ \euro}$.
\end{enumerate}

\subsubsection*{\textcolor{red}{Programmation linéaire}}

\begin{enumerate}
\item \textbf{\textcolor{blue}{Principe}}\\
La programmation linéaire consiste à optimiser graphiquement une expression linéaire $ax + by$, pour les points de coordonnées $(x~;~y)$ d'une région du plan caractérisée par un système d'inéquations linéaires correspondant à des contraintes.\\
Optimiser une expression signifie la minimiser s'il s'agit d'un coût ou la maximiser s'il s'agit d'un profit.\\
Les variables $x$ et $y$ désignent généralement les quantités de deux produits ou services achetés ou vendus par une entreprise ou un particulier.\\
Les contraintes représentent des limites liées à l'entreprise (ou au particulier) ou à son environnement.\\
L'expression à optimiser, qui dépend de deux variables $x$ et $y$, représente pour l'entreprise (ou le particulier) soit un coût que l'on cherche à minimiser, soit un profit que l'on cherche à maximiser.\\
Le but de la programmation linéaire est ainsi de déterminer graphiquement un programme optimal, c'est-à-dire de trouver les valeurs de $x$ et de $y$ permettant soit de minimiser les coûts, soit de maximiser les profits. 

\item \textbf{\textcolor{blue}{Étapes de résolution d'un programme linéaire}}\\
La résolution d'un programme linéaire se déroule en deux temps :
\begin{enumerate}
\item  Traduction algébrique des données du problème sous forme de programme linéaire : 
\begin{itemize}
\item  choix des variables $x$ et $y$ ;

\item mise en inéquation des contraintes ; 

\item détermination de l'expression linéaire $ax + by$ à optimiser. 
\end{itemize}

\item Résolution graphique du programme linéaire : 
\begin{itemize}
\item détermination du programme réalisable par la résolution graphique d'un système d'inéquations linéaires précédemment déterminé ; 

\item  détermination du programme optimal par l'optimisation graphique de l'expression linéaire \\
$ax + by$. 
\end{itemize}
\end{enumerate}

\end{enumerate}

`

\label{fin}
\end{document}
