Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Faculté Ordinateurs, Informatique et Microélectronique Filière Francophone Info

Faculté Ordinateurs, Informatique et Microélectronique Filière Francophone Informatique Vasile MORARU Recherche opérationnelle Eléments de cours Chişinău U.T.M. 2012 UNIVERSITE TECHNIQUE DE MOLDOVA AGENCE UNIVERSITAIRE DE LA FRANCOPHONIE Digitally signed by Library TUM Reason: I attest to the accuracy and integrity of this document 2 În lucrare este tratată metoda simplex în vederea utilizării acesteia în determinarea soluţiilor optime a problemelor de programare liniară, de programare în numere întregi, de programare liniar-fracţionară. Se prezintă problema de transport şi se abordează dualitatea în programarea liniară. Lucrarea reprezintă o iniţiere în cursul de Cercetări operaţionale, conţinînd exemple şi exerciţii care să faciliteze studiul individual şi este destinată studenţilor din anul doi de la Facultatea Calculatoare, Informatică şi Microelectronică, Filiera francofonă Informatica. Autor: conf. univ., dr. Vasile Moraru Responsabil pentru ediţie: conf. univ. Liviu Carcea Recenzenţi: conf.univ., dr. Mihail Perebinos lector superior Daniela Istrati  U.T.M., 2012 3 Avant- Propos Dans l‟industrie, le commerce, l‟administration, l‟économie, la chimie, l‟énergie, le transport, les réseaux, dans presque tous les domaines de l‟activité humaine apparaissent des problèmes qui conduisent au choix une situation donnée et ce choix doit être fait d‟une telle manière qu‟il soit assurée la réalisation d‟un but bien déterminé. Les problèmes de ce type sont nommés problèmes de décision. Un rôle important dans les problèmes de décision le joue les problèmes d’optimisation qui consistent dans le calcul du maximum ou du minimum d‟une fonction donnée de plusieurs variables liées entre elles par d‟une d‟entre toutes les possibilités d‟action dans des différentes relations. Un cas particulier des problèmes d‟optimisation est la programmation linéaire qui inclue un système d‟équations et (ou) inéquations linéaires, nommées restrictions du problème, aussi qu‟une fonction linéaire qui représente le but désiré, le but désiré par la valeur maximale ou minimale de celle-ci. Le problème de programmation linéaire a été formulé pour la première fois en 1939 par Kantorovitch L.V. En 1947 Dantzig George a élaboré la méthode simplex de résolution des problèmes de programmation linéaire. La méthode simplex consiste dans le parcours des sommets du polyèdre des solutions admissibles, en 4 s‟approchant de la solution optimale, jusqu‟au moment de sa atteinte dans un des sommets du polyèdre. Dans l‟ouvrage on étudie la méthode simplex pour son utilisation pour la détermination des solutions optimales des problèmes de programmation linéaire, de programmation des nombres entiers, de programmation linéaire fractionnaire. On présente le problème de transport et on aborde la dualité dans la programmation linéaire. On discute la sensibilité de la solution et on indique les possibilités d‟utilisation du produit informatique QM pour la résolution des problèmes à l‟aide de l‟ordinateur. Les méthodes d‟optimisation linéaire sont inclues dans les programmes d‟enseignement universitaire comme objet séparé ou les compartiments des cours de Recherche Opérationnelle ou de Programmation Mathématique. Les cours respectives sont lues aux étudiants des institutions d‟enseignement supérieur avec un profil technique et économique. C‟est à eux que cet ouvrage est adressé aussi comme aux autres hommes qui veulent s‟initier dans l‟optimisation linéaire. 5 Liste des notations R l‟ensemble de nombres réels. n R l‟espace linéaire n–dimensionnel. k x suite des vecteurs: k x . x* la solution du problème: n R x* . ||x|| la norme du vecteur n R x . Un indice peut préciser la nature de cette norme. T A la transposée de la matrice A. 1 A l‟inverse de la matrice A. I la matrice unité. y x, le produit scalaire des vecteurs n R y x, P x l‟ensemble des éléments x avec la propriété P. x f le gradient de la fonction f(x). x f 2 la matrice Hesse de la fonction f(x). x . 0 si 0 x x x 6 1. NOTIONS CONCERNANT LES ENSEMBLES ET LES FONCTIONS CONVEXES 1.1. Ensembles convexes Un ensemble M, MRn, est appelé ensemble convexe si pour tous deux points M x x 2 1, , appartenant à cet ensemble, le segment de droite qui les unit appartient de même à cet ensemble. Autrement dit, pour tout M x x 2 1, a lieu M x x z 2 1 1 pour tout réel, 1 0 (fig.1.1). En particulier, l‟ensemble vide, l‟ensemble formé d‟un seul élément et tout l‟espace n dimensionnel Rn, sont des ensembles convexes. Dans la fig. 1.2 sont donnés des exemples d‟ensembles 2 R qui ne sont pas convexes. On constate facilement que l‟intersection d‟une famille d‟ensembles convexes est un ensemble convexe. Soit R b a R x a n , 0 , , . L‟ensemble x1 5 x() M M M Fig. 1.1. Ensemble convexe Fig. 1.2. Exemples d‟ensembles qui ne sont pas convexes 7 n i i i T b x a x b x a x 1 forme un hyperplan de Rn. Les demi-espaces déterminés par l‟hyperplan sont , b x a x S T . b x a x S T Evidemment, S S . Les ensembles S , et S sont convexes. Soit A une matrice de dimensions n m , n R x et m R b . L‟ensemble n j i j ij m i b x a x b Ax x T 1 , 2 , 1 ,  est appelé tronçon. Le tronçon représente l‟intersection d‟un nombre fini de demi espaces , , , 2 , 1 1 m i b x a x S n j i j ij i  et, donc, est un ensemble convexe. Un tronçon borné est appelé polyèdre convexe ou polytope. Un polyèdre planaire est un polygone. La combinaison linéaire des éléments m i R x n i , , 2 , 1 ,  de forme m mx x x  2 2 1 1 où , 0 i m i , , 2 , 1  et 1 2 1 m  s‟appelle combinaison convexe des éléments m x x x , , , 2 1  . Théorème1.1. Un ensemble convexe contient toute combinaison convexe construite de ses éléments. Démonstration (par induction). Soit M un ensemble convexe, n R M . Il en résulte que toute combinaison convexe, construite de deux éléments de M appartient à M. Supposons que M contient toute combinaison de maximum 3 , 1 m m , éléments de M. Considérons la combinaison convexe 8 m mx x x z  2 2 1 1 , m i M xi , , 2 , 1 ,  telle que 1 2 1 m  . Evidemment, au moins pur un des indices 1 : i i . On peut considérer que 1 1 . Alors m mx x x y  3 3 2 2 , où m i i i  , 3 , 2 , 1 1 , est une combinaison convexe des éléments m x x x ,..., 3 2 , car  i0 et 1 3 2 m  . Conformément à l‟hypothèse inductive que M y . Comme y x z 1 1 1 1 et M est un ensemble convexe, il résulte que zM, fait qui démontre le théorème. Soit n R M un ensemble non vide et convexe. On dit que xM est un point d‟extremum de l‟ensemble M si‟l n‟existe aucun z y M z y , 1 , 0 , , tels que: z y x 1 . Autrement dit, le point d‟extremum x ne peut pas appartenir à l‟intervalle (y,z) pour tous M z y, . Nous montrons ici deux exemples de points d‟extremum des ensembles convexes en 2 R . On note par E l‟ensemble des points d‟extremum de l‟ensemble M. 1. 1 , 1 2 2 2 1 2 2 2 1 x x x E x x x M . 2. , 0 0 , 5 , 4 2 2 1 2 1 2 1 , x x x x x x x M T T T T E 2 , 3 , 0 , 2 , 5 , 0 , 0 , 0 . Dans la fig.1.3 sont présentés ces deux ensembles pour lesquels est évidentié l‟ensemble des points d‟extremum E. Un hyperplan ou un demi-espace n‟a pas de points d‟extremum. Un ensemble fermé et borné en n R s‟appelle compacte. Tout ensemble convexe compact en n R possède des points d‟extremum. Si M est un ensemble convexe compacte en n R et à un nombre fini de points d‟extremum, alors tout élément de 9 l‟ensemble M peut être exprimé comme une combinaison convexe de ses points d‟extremum. Soit le tronçon b Ax x T , où n R x , A est une matrice de dimension m R b n m n m , , . Notons par A une sous matrice d‟ordre n n de A. Supposons que 0 det A . En ce cas, le système d‟équations b x A , où b contient des éléments de b, après une éventuelle rémunération, admet une solution unique x . Si T x alors x s‟appelle sommet du tronçon T. On vérifie immédiatement que le tronçon T a au plus ! ! / ! n m n m Cn m uploads/Science et Technologie/ recherche-operationnelle-elements-cours-ds.pdf