Partage

Programmation linéaire

Le 29 juin 2009 à 8:57:36

Bonjour,

Avant de poser cette question ici, j'ai déjà regardé sur Wikipédia la définition!
Et je ne comprenais pas encore plus, ce n'est pas un mode de programmation mais de la mathématique?

Des tutos que j'ai trouvés sur le net aussi ne montraient que comment les résoudre sous le solveur d'Excel

Mais pourquoi apprend-on cela en études en informatique? Comment donc les résoudre, si quelqu'un peut me montrer un tuto??? Merci d'avance
Publicité
Le 29 juin 2009 à 8:57:36
Le 29 juin 2009 à 9:36:08

Alors déjà sache qu'il y a la programmation linéaire d'une part, et la programmation mathématique d'autre part. Les deux sont des "ensembles d'algos" pour résoudre des systèmes sous contraintes.

La programmation linéaire est comme son nom l'indique linéaire.
exemple de système :
max 5x+3y
sc x < 2
y+2y < 8
y+x>5
x,y > 0

Pour le résoudre, l'algorithme sur lequel tu peux te renseigner est l'algorithme du Simplex. Sachant que j'ai donné un système au pif, mais je pense qu'il est résolvable sans (juste avec un système d'équation).
L'avantage du simplex, c'est que tu peux l'utiliser avec une infinité de contraintes (sc = sous contrainte)
(je donne pas de tuto, google t'aidera avec le mot Simplex, un autre mot qui peut t'aider dans tes recherches est "dualité").

La programmation mathématique, c'est la même chose, mais en pas linéaire
exemple :
max 2xy + y
sc xy+ 8<4
y²+2 < 5
x+2y-z < 8
x,z >0 , z C R

Le simplex n'est plus utilisable. Généralement on cherche à faire une approximation de la solution, en utilisant des méthodes en plusieurs itérations. En 2D, les plus simples sont la méthode de newton, la méthode dichtomique ou encore la méthode de la sécante.
Par contre en 3D, c'est tout de suite plus compliqué et rébarbatif. Tu trouveras la méthode de la plus forte pente (accélérée ou non) ou encore la méthode de newton multidimensionnelle. Pas de la tarte.

Enfin pourquoi on apprend ça en info ... c'est parce qu'il te faudra surement un jour savoir résoudre ces équations, et écrire vite fait leurs algorithmes (bon pour le simplex tu recoderas pas, beaucoup l'ont déjà fait). Tu en auras besoin par exemple en IA ou autres matière étant assez proche des mathématiques.

Voilà, bonne journée.
Le 30 juin 2009 à 13:27:27

Merci pour cette explication, j'en avais besoin

Mais je suis vraiment à la recherche de tuto comme on fait sur site des zéros pour tourner l'algo de simplexe!! Dès que je cherche je tombe sur des complications dont je n'y comprends rien: résolution algébrique, BIG M, dualité et dégénerescence

C'est quoi DUALITÉ?
Le 23 juin 2013 à 19:16:59

svp es que vous n'auriez pas de bons cours a me passé en programmmation linaire!!!!!

Le 23 juin 2013 à 21:28:15

Pour ceux qui cherche une facon "simple" de faire un simplex... Cette petite vidéo resume pas trop mal les choses a mon gout

https://www.youtube.com/watch?v=fgX_7QaFzE4

Le 24 juin 2013 à 9:29:18

(rien à voir mais je tenais à souligner la performance de 4 ans de déterrage... bravo :) )
Le 24 juin 2013 à 9:38:29

Eskimon a écrit:

(rien à voir mais je tenais à souligner la performance de 4 ans de déterrage... bravo :) )


Merde... J'avais lu 30 juin... Pas 30 juin 2009...
Le 24 juin 2013 à 18:28:48

Le message qui suit est une réponse automatique activée par un membre de l'équipe. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention plus facilement.
Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé.

Déterrage

Bonjour,

Tu as répondu à un sujet ancien dont il est peu probable que l'auteur ait encore de l'intérêt à le lire (ou que le problème existe encore). Il n'est pas recommandé de remonter un sujet ancien pour poser une question ou pour apporter une réponse au problème.

Je ferme donc ce sujet (et t'invite à ouvrir un sujet propre à ta demande s'il s'agissait d'une question). :)

NB: Les règles du site exigent par ailleurs de faire un minimum de recherche avant de poster une question.

Merci de ta compréhension.

Arius.

[Développement JV] Ressources utiles et FAQ - Ex-Newser/Manager - Aussi sur Zeste de Savoir ♥