[PDF] Programmation linéaire en nombres entiers

View - Download Programmation linéaire en nombres entiers

Previous PDF

Next PDF

Programmation linéaire

en nombres entiers

Introduction

• Problème de programmation linéaire en nombres entiers (P) •F(P) = domaine réalisable de P• Exemple njxmibxaxc ji n j jijj n j j ,,1entier ,0,,1 àSujet Min 11 entier,0,22010 àSujet 5Min -=xxxxxxxz

Introduction

• Problème de programmation linéaire en nombres entiers (P) •F(P) = domaine réalisable de P• Exemple njxmibxaxc ji n j jijj n j j ,,1entier ,0,,1 àSujet Min 11 entier,0,22010 àSujet 5Min -=xxxxxxxz 2010

21=+xx

2 1= x ( ) 0,0 , 1,0 , 2,0 , 0,1 , 1,1 , 2,1 , 0,2F P=

Introduction

• Problème de programmation linéaire en nombres entiers (P) •F(P) = domaine réalisable de P • dénote le problème (P) où les contraintes d'intégralité sur les variables sont rélaxées.• Exemple njxmibxaxc ji n j jijj n j j ,,1entier ,0,,1 àSujet Min 11 entier,0,22010 àSujet 5Min -=xxxxxxxz ()P 2010

21=+xx

2 1= x ()P

Introduction

• Problème de programmation linéaire en nombres entiers •F(P) = domaine réalisable de P • dénote le problème (P) où les contraintes d'intégralité sur les variables sont rélaxées.• Exemple njxmibxaxc ji n j jijj n j j ,,1entier ,0,,1 àSujet Min 11 entiers,0,22010 àSujet 5Min xxxxxxxz ()P 2010

21=+xx

2 1= x ()PF ()P

Introduction

• Problème de programmation linéaire en nombres entiers (P) • Résolution du problème

Pourquoi pas résoudre le

problème relaxé et arrondir la solution? • Exemple

Solution du problème relaxé:

(2, 9/5) et z = -11

Solution arrondie: (2, 1) et z= -7

njxmibxaxc ji n j jijj n j j ,,1entier ,0,,1 àSujet Min 11 entiers,0,22010 àSujet 5Min xxxxxxxz 2010

21=+xx

2 1= x ()PF

Or (0, 2) est réalisable avec z = -10

Méthodes de résolution

• Principe de base

Générer un ensemble de contraintes

linéaires que nous ajoutons à (P)• Exemple entiers,0,22010 àSujet 5Min xxxxxxxz 2010

21=+xx

2 1= x ()PF 42

21=+xx

Méthodes de résolution

• Principe de base

Générer un ensemble de contraintes

linéaires que nous ajoutons à (P) pour engendrer un nouveau problème (PR) tel que

De plus en résolvant le problème

relaxé , la solution optimale est entière et donc une solution optimale pour (P).• Exemple 2010

21=+xx

2 1= x ()PF 42

21=+xx

entiers,0,4222010 àSujet 5Min xxxxxxxxxz ( ) ( )F PR F PF PR F P PR

Méthode des coupes de Gomory

• Principe des méthodes de coupes Introduire de nouvelles contraintes linéaires au problème pour réduire le domaine réalisable du problème relaxé sans pour autant éliminer de points du domaine réalisable du problème avec les contraintes de nombre entier sur les variables. • La procédure consiste à résoudre une suite de problèmes relaxés jusqu'à ce qu'une solution optimale en nombres entiers soit obtenue. • Un problème de la suite est obtenu du précédent en lui ajoutant une contrainte linéaire (coupe) supplémentaire. n j 1 1

Considérons le problème de programmation

linéaire en nombres entiers suivant: ( ) Min

Sujet à 1, ,

0,entier, 1, ,

j j n ij j i j j P c x a x b i m x j n

Voyons comment construire une coupe de Gomory.

Soit une base optimale de ( ), et la va

riable de base dans la ième ligne du tableau optimal p renant une valeur qui n'est pas entière. k B P x i 1 1 1 2

11 12 1 1 1

1 2 1 var terme base droite

0 1 0 0

1 0 0 0

m m k j j j n jj n k i i ij in i j m m x x x x x x x z x t t t t b x t t t t b x t t-... ... ... ... ... 2 1 2

0 0 1 0

0 0 0 1

mj mn m j nt t b z c c c c z--

Le tableau optimal est de la forme:

La ligne correspondante du tableau optimal est de la forme: 1 où : est l'indice d'une variable hors ba se et n'est pas entier. ik ij j j J i x t x b

J j j b

La ligne correspondante du tableau est d

e la forme:1 où : est l'indice d'une variable hors ba se et n'est pas entier. ik ij j j J i x t x b J j j b

Dénotons le plus grand entier (plancher)

Puisque 0 , alors

et par conséquent . (2) j ij j ij j j J j J i k ij j k ij j j J j Jd d x j t x t x x t x x t x b entier. pasest n' bet base hors variableuned' indicel'est :où 1 forme la de est du tableau ante correspond ligne La ii

Jjjijk

jjJbxtx

? ?(3).satisfait )( desolution touteAinsi)3(.que (2) de découle il , variablesdeséintégralitd' contrainte la sconsidéron nous Si

P bxtxx ij

Jjijkj

)2(.conséquentpar et alors ,0 Puisque.(plancher)entier grand plus le sDéfinisson ij

JjijkJjjijj

Jjijjbxtxxtxtjxdd

0et 0 que Notons4:(1)et (3) entre différence lefaisant en obtenuerelation la maintenant sConsidéron

i ijiji j

Jjijij

bbttbbxtt ii

).( desolution aucune éliminen' )( danson introductison et (4),satisfait elle alors (3),et (1)satisfait )( desolution toutePuisque

PPP

0et 0 que Notons4:(1)et (3) entre différence lefaisant en

obtenue relation la maintenant s

Considéron

i ijiji j

Jjijij

bbttbbxtt ii

).( desolution aucune éliminen' )( danson introductison et (4),satisfait elle alors (3),et (1)satisfait )( desolution toutePuisque

PPP

).( relaxé problèmedu réalisable domaine leréduit on introductison et (4) passatisfait ne 0où )( relaxé problèmedu actuellesolution la contre,Par

P JjxP j Pour poursuivre la résolution, il suffit d'introduire la contrainte où est une variable d'écart avec coût nul, au dernier tableau du simplex ii iiij ij jij ij j j Jj J t t x b b t t x x b b x e pour générer une solution de base au nouveau problème en considérant comme la variable de base d ans la nouvelle ligne du tableau. Cette solution de base n'est pas réalisable puisque 0. i i x x b bτ Il suffit de poursuivre la résolution avec l'algorithme dual du simplexe. 1 1 1 2

11 12 1 1 1

1 2 var terme base droite

0 1 0 0 0

1 0 0 0 0

m m k j j j n jj n k i i ij in i j x x x x x x x x z x t t t t b x t t t t b x t 1 2

1 1 2 2

1 2

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

i m m mj mn m i i i i i ij ij in in j n t t t b x t t t t t t t t b bz c c c c zτ Pour poursuivre la résolution, il suffit d'introduire la contrainte où est une variable d'écart avec coût nul, au dernier tableau du simplex ii iiij ij jij ij j j Jj J t t x b b t t x x b b x e pour générer une solution de base au nouveau problème en considérant comme la variable de base d ans la nouvelle ligne du tableau. Cette solution de base n'est pas réalisable puisque 0. i i x x b bτ Il suffit de poursuivre la résolution avec l'algorithme dual du simplexe. Notes:1) Si (i.e., est entier) , et si n'est pas entier, alors 1 indique que ( ) n'est pas réalisable p uisque le terme de gauche prend une valeur entière iij ij ij i k ij j j J t t t j J b x t x b P pour toute solution réalisable de ( ) alo rs que le terme de droite n'est pas entier.

2) Une dérivation similaire s'applique à toutes les itérations.P

1 2 1 2 3 1 2 3

Considérons le problème suivantMin 21 11

Sujet à 7 4 13

, , 0, entiersx x x x x x x x- - 1 2 3

2 3 4Itération 1:Solution de base optimal de ( )

4 1 13

7 7 7valeur opt. 39

Nouvelle contrainte:

4 4 1 1 13 137 7 7 7 7 7

P x x x x x x+ + =

1647134Ainsi .4713Or .6476

71

74:egéométriqution Interpréta

xxxxxxxxxxx ii ij ij j i ij ij j i j Jj Jt t x b b t t x x b b 1 2 1 2 3 1 2 3

Min 21 11Sujet à 7 4 13

, , 0, entiers x x x x x x x x entiers ,0,,,76 71

741347 àSujet 1121Min de relaxé problème le Résoudre:2Itération

432143232121≥-=+--=++--

xxxxxxxxxxxx2137opt.valeur 23 47
411
obtenonsquotesdbs_dbs35.pdfusesText_40

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie

[PDF] fonction de cobb douglas pdf

[PDF] revenu d'équilibre et revenu de plein emploi

[PDF] fonction cobb douglas ses