Accueil
slides-omp.tex
slides-omp.tex
—
TeX document,
15Kb
Contenu du fichier
\section{Analyse de sensibilit�vec OMP}
\subsection{Mod� OMP}
\begin{verbatim}
******************************
S = Probl� �ile
******************************
MAX
*
X = VARX1 = C $1 > 0
X = VARX2 = C $3 > 0
X = VARU1 = C $0 > 0
X = VARU2 = C $0 > 0
X = VARU3 = C $0 > 0
*
C = CONT1 = VARX1 + VARX2 + VARU1 = 14
C = CONT2 = -2*VARX1 + 3*VARX2 + VARU2 = 12
C = CONT3 = 2*VARX1 - VARX2 + VARU3 = 12
\end{verbatim}
\subsection{Rapports OMP}
\subsubsection{Report : all variables}
\begin{verbatim}
Optimal value
OBJECTIVE 30.00
VARX1 6.00
VARX2 8.00
VARU1 0.00
VARU2 0.00
VARU3 8.00
\end{verbatim}
\subsubsection{Report : variables at lower bound}
\begin{verbatim}
bound reduced cost low lim upp lim
VARU1 0.00 -1.80 -10.00 10.00
VARU2 0.00 -0.40 -30.00 13.33
\end{verbatim}
\newpage
\subsubsection{Report : sensitivity on objective coefficients}
\begin{verbatim}
lower limit present value upper limit
VARX1 -2.00 1.00 3.00
VARX2 1.00 3.00 +Infinity
VARU1 -Infinity 0.00 1.80
VARU2 -Infinity 0.00 0.40
VARU3 -0.66 0.00 2.25
\end{verbatim}
\subsubsection{Report : all constraints}
\begin{verbatim}
left hand side slack/surplus shadow price
CONT1 14.00 0.00 1.80
CONT2 12.00 0.00 0.40
CONT3 12.00 0.00 0.00
\end{verbatim}
\newpage
\subsubsection{Report : sensitivity on R.H.S. coefficients}
\begin{verbatim}
lower limit present value upper limit
CONT1 4.00 14.00 24.00
CONT2 -1.33 12.00 42.00
CONT3 4.00 12.00 +Infinity
\end{verbatim}
\subsection{Termes utilis�
\begin{description}
\item[Reduce cost] d'une variable $x_k$ = coefficient de cette variable dans la ligne objectif du tableau simplexe optimal ($\bar{c}_k$)
\item[Shadow price] d'une contrainte $i$ = valeur optimale de la variable duale associ��ette contrainte ($\pi_i$)
\end{description}
\subsection{Informations donn� par les rapports}
\subsection*{Report : variables at lower/upper bound}
\begin{description}
\item[bound] $\rightarrow$ valeur de la borne atteinte
\item[reduced cost] $\rightarrow$ variation de la valeur optimale de l'objectif pour une augmentation d'une unit�e la borne
\item[lower limit] $\rightarrow$ valeur minimale de ``bound'' jusqu'�aquelle le ``reduced cost'' reste valable
\item[upper limit] $\rightarrow$ valeur maximale de ``bound'' jusqu'�aquelle le ``reduced cost'' reste valable
\end{description}
\subsection*{Report : sensitivity on objective coefficients}
\begin{description}
\item[present value] $\rightarrow$ valeur du coefficient d'une variable dans l'objectif du mod� de d�rt
\item[lower limit] $\rightarrow$ valeur minimale de ``present value'' jusqu'�aquelle la solution optimale reste inchang�\item[upper limit] $\rightarrow$ valeur maximale de ``present value'' jusqu'�aquelle la solution optimale reste inchang�\end{description}
\subsection*{Report : all constraints}
\begin{description}
\item[left hand side] $\rightarrow$ valeur du membre de gauche de la contrainte (dans le mod� explicite) obtenue avec la solution optimale
\item[slack/surplus] $\rightarrow$ diff�nce (en valeur absolue) entre le membre de droite et le membre de gauche de la contrainte
\item[shadow price] $\rightarrow$ variation de la valeur optimale de l'objectif pour une augmentation d'une unit�u membre de droite de la contrainte
\end{description}
\subsection*{Report : sensitivity on R.H.S. coefficients}
\begin{description}
\item[present value] $\rightarrow$ valeur du membre de droite de la contrainte dans le mod� explicite
\item[lower limit] $\rightarrow$ valeur minimale de ``present value'' jusqu'�aquelle la solution optimale reste inchang�(le ``shadow price'' reste valable)
\item[upper limit] $\rightarrow$ valeur maximale de ``present value'' jusqu'�aquelle la solution optimale reste inchang�(le ``shadow price'' reste valable)
\end{description}
\section{Param�isation avec OMP}
R�is�en s�ce.
\newpage
\section{Un probl� de m�nge}
\subsection{Enonc�L'entreprise Steel a re�une commande de cinq tonnes d'acier destin� la fabrication de coques de bateau. Cet acier doit
avoir les caract�stiques particuli�s du tableau \ref{CAC}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l|cc}
El�nt & Pourcentage & Pourcentage\\
chimique & minimal & maximal\\
\hline
Carbone (C) & 2 & 3\\
Cuivre (Cu) & 0,4 & 0,6\\
Mangan� (Mn) & 1,2 & 1,65
\end{tabular}
\caption{\label{CAC}Caract�stiques de l'acier command�\end{center}
\end{table}
\noindent
Pour fabriquer cet acier, Steel dispose de sept mati�s premi�s dont les caract�stiques, les quantit�disponibles et
les co�'achat sont donn�au tableau \ref{CMP}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l|cccccc}
Mati� premi� & C (\%) & Cu (\%) & Mn (\%) & Stocks (kg) & Co�F/kg)\\
\hline
Alliage de fer 1 & 2,5 & 0 & 1,3 & 4000 & 1,20\\
Alliage de fer 2 & 3 & 0 & 0,8 & 3000 & 1,50\\
Alliage de fer 3 & 0 & 0,3 & 0 & 6000 & 0,90\\
Alliage de cuivre 1 & 0 & 90 & 0 & 5000 & 1,30\\
Alliage de cuivre 2 & 0 & 96 & 4 & 2000 & 1,45\\
Alliage d'aluminium 1 & 0 & 0,4 & 1,2 & 3000 & 1,20\\
Alliage d'aluminium 2 & 0 & 0,6 & 0 & 2500 & 1,00
\end{tabular}
\caption{\label{CMP}Caract�stiques des mati�s premi�s}
\end{center}
\end{table}
D�rminer la composition de l'acier �abriquer pour minimiser les co�e production.
\subsection{Formulation}
\subsubsection{Dimensions}
\begin{itemize}
\item $M$ = nombre de mati�s premi�s ($i=1, 2,\ldots,M$)
\item $E$ = nombre d'�ments chimiques ($j=1, 2,\ldots,E$)
\end{itemize}
\subsubsection{Donn�}
\begin{itemize}
\item $D$ = quantit�en kg) d'acier de la commande
\item $P_{ij}$ = pourcentage d'�ment chimique $j$ contenu dans la mati� premi� $i$
\item $S_i$ = stock (en kg) de mati� premi� $i$ disponible
\item $C_i$ = co�n F/kg) de la mati� premi� $i$
\item $PMIN_j$ = pourcentage minimal d'�ment chimique $j$ que doit contenir l'acier command�item $PMAX_j$ = pourcentage maximal d'�ment chimique $j$ que doit contenir l'acier command�end{itemize}
\subsubsection{Variables}
\begin{itemize}
\item $z$ = co�n F) pour satisfaire la commande
\item $x_i$ = quantit�en kg) de mati� premi� $i$ utilis�pour satisfaire la commande
\item $q$ = quantit�en kg) d'acier fabriqu�end{itemize}
\subsubsection{Objectif}
\begin{itemize}
\item $\displaystyle \min z = \sum_{i=1}^{M}C_i*x_i$
\end{itemize}
\subsubsection{Contraintes}
\begin{itemize}
\item $\displaystyle \sum_{i=1}^{M}x_i=q$
\item $q\geq D$
\item $\displaystyle \sum_{i=1}^{M}P_{ij}*x_i\geq PMIN_j*q$ pour $j=1, 2,\ldots,E$
\item $\displaystyle \sum_{i=1}^{M}P_{ij}*x_i\leq PMAX_j*q$ pour $j=1, 2,\ldots,E$
\item $\displaystyle x_i\leq S_i$ pour $i=1, 2,\ldots,M$
\item $\displaystyle x_i\geq 0$ pour $i=1, 2,\ldots,M$ et $q\geq0$
\end{itemize}
\subsection{Mod� OMP}
\begin{itemize}
\item Fichier ``ALLIAGES.mod''
\begin{verbatim}
****************************
S=Fabrication d'alliages
****************************
*
MINimiser les co�e fabrication
*
SET=EC, FICHIER=COMPO.wk1, LIGNE=1
SET=MP, FICHIER=MPCAR.wk1, LIGNE=1
*
X=QU.MP(&)=C $/COUT/ </STOCK/
X=QACIERFAB=C
*
C=QUANTFAB=QU.MP(S&)=QACIERFAB
C=SATDEM=QACIERFAB>/DEMACIER/
C=COMPMIN.EC(&)=/CARACT/*QU.MP(S&)>/PMIN/*QACIERFAB
C=COMPMAX.EC(&)=/CARACT/*QU.MP(S&)</PMAX/*QACIERFAB
*
DATA=DEMACIER : 5000
DATA=COUT, FICHIER=MPS&C.wk1, L=MP(&), C=COUT
DATA=STOCK, FICHIER=MPS&C.wk1, L=MP(&), C=STOCK
DATA=PMIN, FICHIER=COMPO.wk1, L=EC(&), C=PMIN
DATA=PMAX, FICHIER=COMPO.wk1, L=EC(&), C=PMAX
DATA=CARACT, FICHIER=MPCAR.wk1, L=MP(&), C=EC(&)
*
\end{verbatim}
\item Fichier ``COMPO.wk1''
\begin{verbatim}
PMIN PMAX
CARB 2 3
CUIV 0.4 0.6
MANG 1.2 1.65
\end{verbatim}
\twocolumn
\item Fichier ``MPS\&C.wk1''
\begin{verbatim}
STOCK COUT
AFER1 4000 1.2
AFER2 3000 1.5
AFER3 6000 0.9
ACUI1 5000 1.3
ACUI2 2000 1.45
AALU1 3000 1.2
AALU2 2500 1
\end{verbatim}
\pagebreak
\item Fichier ``MPCAR.wk1''
\begin{verbatim}
CARB CUIV MANG
AFER1 2.5 0 1.3
AFER2 3 0 0.8
AFER3 0 0.3 0
ACUI1 0 90 0
ACUI2 0 96 4
AALU1 0 0.4 1.2
AALU2 0 0.6 0
\end{verbatim}
\end{itemize}
\onecolumn
\subsection{Mod� OMP explicite (listing)}
\begin{verbatim}
**********************************************************
* Problem dimensions *
* 8 continuous variables *
* 0 integer variables *
* 0 binary variables *
* Total of 8 variables, *
* of which 0 are fixed *
* 0 are free *
* 7 have an upper bound *
* 0 have a non-zero lower bound *
* 1 equality constraints *
* 3 < constraints *
* 4 > constraints *
* Total of 8 constraints *
* Total of 44 nonzero matrix elements *
**********************************************************
*
SCENARIO=Fabrication d'alliages
*
MINimization
*
X1=QU.AFER1 =C $1.2 <4000.
X2=QU.AFER2 =C $1.5 <3000.
X3=QU.AFER3 =C $0.9 <6000.
X4=QU.ACUI1 =C $1.3 <5000.
X5=QU.ACUI2 =C $1.45 <2000.
X6=QU.AALU1 =C $1.2 <3000.
X7=QU.AALU2 =C $1. <2500.
X8=QACIERFAB=C
*
C1=QUANTFAB
= QU.AFER1 + QU.AFER2 + QU.AFER3 + QU.ACUI1 + QU.ACUI2
+ QU.AALU1 + QU.AALU2 - QACIERFAB = 0
C2=SATDEM
= QACIERFAB > 5000
C3=COMPMIN.CARB
= 2.5 * QU.AFER1 + 3 * QU.AFER2 - 2 * QACIERFAB > 0
C4=COMPMIN.CUIV
= 0.3 * QU.AFER3 + 90 * QU.ACUI1 + 96 * QU.ACUI2
+ 0.4 * QU.AALU1 + 0.6 * QU.AALU2 - 0.4 * QACIERFAB > 0
C5=COMPMIN.MANG
= 1.3 * QU.AFER1 + 0.8 * QU.AFER2 + 4 * QU.ACUI2
+ 1.2 * QU.AALU1 - 1.2 * QACIERFAB > 0
C6=COMPMAX.CARB
= 2.5 * QU.AFER1 + 3 * QU.AFER2 - 3 * QACIERFAB < 0
C7=COMPMAX.CUIV
= 0.3 * QU.AFER3 + 90 * QU.ACUI1 + 96 * QU.ACUI2
+ 0.4 * QU.AALU1 + 0.6 * QU.AALU2 - 0.6 * QACIERFAB < 0
C8=COMPMAX.MANG
= 1.3 * QU.AFER1 + 0.8 * QU.AFER2 + 4 * QU.ACUI2
+ 1.2 * QU.AALU1 - 1.65 * QACIERFAB < 0
\end{verbatim}
\subsection{Rapports OMP}
\subsubsection{Report : all variables}
\begin{verbatim}
Optimal value
OBJECTIVE 5887.57
QU.AFER1 4000.00 QU.ACUI2 27.61
QU.AFER2 0.OO QU.AALU1 574.62
QU.AFER3 397.76 QU.AALU2 0.OO
QU.ACUI1 0.OO QACIERFAB 5000.OO
\end{verbatim}
\subsubsection{Report : variables at lower bound}
\begin{verbatim}
bound reduced cost low lim upp lim
QU.AFER2 0.00 0.40 0.00 845.68
QU.ACUI1 0.00 0.82 -183.28 29.36
QU.AALU2 0.00 0.10 -5561.42 394.86
\end{verbatim}
\subsubsection{Report : variables at upper bound}
\begin{verbatim}
bound reduced cost low lim upp lim
QU.AFER1 4000.00 -0.03 4000.00 4523.53
\end{verbatim}
\subsubsection{Report : sensitivity on objective coefficients}
\begin{verbatim}
lower limit present value upper limit
QU.AFER1 -Infinity 1.20 1.23
QU.AFER2 1.10 1.50 +Infinity
QU.AFER3 -244.14 0.90 1.00
QU.ACUI1 0.48 1.30 +Infinity
QU.ACUI2 -102.17 1.45 1.90
QU.AALU1 1.18 1.20 1.79
QU.AALU2 0.90 1.00 +Infinity
QACIERFAB -1.20 0.00 +Infinity
\end{verbatim}
\subsubsection{Report : all constraints}
\begin{verbatim}
left hand side slack/surplus shadow price
QUANTFAB 0.00 0.00 0.90
SATDEM 5000.00 0.00 1.20
COMPMIN.CARB 0.00 0.00 0.00
COMPMIN.CUIV 1000.00 1000.00 0.00
COMPMIN.MANG 0.00 0.00 0.25
COMPMAX.CARB -5000.00 5000.00 0.00
COMPMAX.CUIV 0.00 0.00 -0.01
COMPMAX.MANG -2250.00 2250.00 0.00
\end{verbatim}
\subsubsection{Report : sensitivity on R.H.S. coefficients}
\begin{verbatim}
lower limit present value upper limit
QUANTFAB -400.70 0.00 5643.66
SATDEM 4421.33 5000.00 5000.00
COMPMIN.CARB -Infinity 0.00 0.00
COMPMIN.CUIV -Infinity 0.00 1000.00
COMPMIN.MANG -687.15 0.00 476.15
COMPMAX.CARB -5000.00 0.00 +Infinity
COMPMAX.CUIV -1000.00 0.00 16440.00
COMPMAX.MANG -2250.00 0.00 +Infinity
\end{verbatim}
\newpage
\subsection{Questions}
\begin{enumerate}
\item Est-ce que la solution optimale donn�par OMP est stable par rapport aux co�es mati�s premi�s ?
\item Quelles modifications des caract�stiques de l'acier command�serait-il int�ssant de n�cier ?
\item Quel serait l'effet sur la fonction objectif si le pourcentage minimal de mangan� dans l'acier command�assait de 1,2
�,1 ?
\item A partir de quel prix serait-il avantageux d'utiliser de l'alliage de fer 2 ?
\item Quelle serait la modification sur les co�i on impose l'utilisation de 20 kg d'alliage de cuivre 1 ? M� question
avec 40 kg ?
\end{enumerate}
\subsection{R�nses}
\begin{enumerate}
\item La solution optimale est sensible �ne augmentation de 2,5\% de AFER1 et une diminution de 1,7\% de AALU1.
\item N�cier une diminution du \% minimal de mangan� et une augmentation du \% maximal de cuivre dans l'acier command�\item Cette modification est �ivalente �ne diminution de 500 unit�du membre de droite de la contrainte COMPMIN.MANG. L'effet sur l'objectif est donc une diminution de 500*0,25=125 de la valeur de l'objectif. (Le shadow price 0,25 est valable pour une diminution allant jusque 687,15 unit�)
\item 1,10 F/kg
\item Pour 20 kg, l'objectif augmente de de 20*0,82=16,4. Pour 40 kg, l'information dont on dispose ne suffit pas (Le reduce cost 0,82 n'est valable que juqu'�9,36 kg).
\end{enumerate}
