Programmation linéaire

[UknownStudent]

Bonjour,

j'aimerais éclaircir quelques zones d'ombre au sujet de la programmation linéaire svp

D'abord, corrigez moi si je me trompe mais j'ai cru comprendre que quand on a des contraintes d'inégalité et des contraintes d'égalité il faut exprimer les contraintes d'égalités en deux contraintes d'inégalités, du coup en ajoutant les variables d'écarts on est sûr de ne pas être en situation favorable b_i>=0 et il faut appliquer la méthode du simplex en deux phases

N'est-ce pas un peu "bête" d'exprimer ainsi une seule contrainte d'égalité par deux contraintes d'inégalités et de finalement revenir à deux contraintes d'égalités avec les variables d'écart ? N'y a-t-il pas moyen de faire autrement ? De faire plus simple ?

Dans la même veine, pourquoi chercher à tout prix, à coup de variables d'écarts et auxiliaires, à avoir la matrice identité Im dans A ? Ne suffit-il pas de trouver une base réalisable quelconque et à partir de laquelle on commence à chercher une solution de base réalisable optimale ?

J'aimerais également savoir s'il y a un nombre maximal de contraintes qu'on peut associer à un problème d'optimisation linéaire (ou autre quelconque) en fonction du nombres de variables initiales du problème.

C'est tout, merci d'avance
-----

[feanorel]

Difficile de vous suivre ici...

Il faut distinguer deux choses : la manière dont un algo (le simplexe apparemment) vous est enseigné, et la manière dont il est implémenté.
Aujourd'hui tous les solveurs ont une phase de preprocessing qui retravaille en profondeur les contraintes, et on ne s'amuse généralement
pas à écrire le problème sous forme canonique. En revanche ça simplifie la vie en cours de se ramener à un cas simple pour que vous puissiez
comprendre le principe de l'algo (concept de bases, de pivot, de coût réduit...)

Non il n'y a pas de nombres maximal de contraintes que l'on peut associer à un problème d'optim. On peut même avoir un nombre infini de
contraintes (voir l'optim robuste). Après pour avoir un algo qui le résolve il faut généralement se ramener à un problème avec un nombre fini
de contraintes. Et le nombre de contraintes peut gêner la résolution d'un problème. Il y a d'ailleurs des méthodes spécifiques pour les cas où
le nombre de contraintes (ou de variables) est trop important (voir méthode de décomposition de Benders par exemple).

[UknownStudent]

Oui toutes mes questions sauf la dernière concernent (en particulier) la méthode du Simplexe

Je sais pas quoi répondre d'autres franchement et je ne confonds rien du tout, ma question est simple, on peut la décomposer en deux cas : Cas du simplexe et cas général/algorithme quelconque ...

[feanorel]

Ben il me semble avoir répondu :
on ne fait ces manipulations que pour simplifier l'exposé en cours.
D'un cours à l'autre on trouve des présentations différentes.

Dans les vraies implémentations les reformulations sont faites de manière plus fines,
puisque l'on commence pas une importante phase de preprocessing.

[A voir en vidéo sur Futura]

[UknownStudent]

Bonjour,

je m'excuse du long retard :/

Euh je ne sais pas si ca répond à ma question mais en tout cas ca ne m'avance pas tellement :/ ...

Je vais reformuler ma demande, si vous le permettez, et la préciser avec des "yes or no" question

- Est ce que je peux arriver au résultat correct en procédant comme je l'ai dit, c'est à dire en ayant des contraintes d'inégalités et d'égalités, je mets le tout sous forme canonique c'est à dire en écrivant les contraintes d'égalité en deux contraintes d'inégalités, à la main, avec la méthode "traditionnelle" du simplexe, comme décrite dans les cours, avec les tableaux et les variables d'écarts ? Oui ou non ?

- Si on procède de cette manière, en tout cas dans les cours d'introduction disons à l'optimisation linéaire, c'est bien-sûr pour avoir la fameuse matrice identité, maintenant est ce que je peux, est ce que "j'ai le droit", de chercher la solution optimale du problème à partir d'une SBR quelconque sans nécessairement passer une matrice Id ? Oui ou non ?

merci

[feanorel]

Ah, la question était pour résoudre un problème linéaire à la main ? (c'est tellement ncongru que ça ne m'est même pas venu à l'idée).

Pour la première question : oui on peut faire cette transformation. Je suppose qu'il y a plusieurs manières de faire les tableaux du simplexe et je ne
l'ai plus fait depuis longtemps du coup je ne sais pas si c'est la méthode la plus efficice, mais en tout cas c'est juste.

Je ne comprends pas vraiment la deuxième question (SBR ?).

Encore une fois, je n'ai manipulé les tableaux du simplexe à la main qu'une fois il y a fort longtemps.
En revanche j'enseigne régulièrement l'optim linéaire...

[UknownStudent]

Oui je demande pour le cas où on doit le faire à la main car c'est tout ce que je connais, je ne sais pas comment font les programmes informatiques dont vous parlez pour résoudre le problème

En fait cela soulève pour moi deux questions, premièrement si ce qu'on voit en cours d'optimisation linéaire n'est apparemment pas grand chose d'après ce que vous dites, c'est quand qu'on est censé maitriser l'optimisation ? Linéaire ou pas. Deuxièmement si les solveurs font tout à notre place et qu'il n'y a même pas besoin de traiter les contraintes préalablement ca se fait automatiquement, on étudie et optimise quoi finalement en optimisation ? Les programmes eux memes peut etre pour qu'ils soient plus rapide, une optimisation de l'optimisation, optimisation² ?

En fait je n'ai pas étudié l'optim linéaire spécifiquement, j'ai étudié RO d'un coté et optimisation et analyse convexe de l'autre, je sais pas si ca revient au même parce que la RO c'était de l'optimisation linéaire en fait, mise à par le coté modélisation

Pour la deuxième question, SBR c'est solution de base réalisable

Vous ne donnez pas des cours d'optim linéaire sur le net par hasard ?

[feanorel]

Bonjour,

il y a plein de choses à voir en optimisation Essayons de donner quelques grandes classes :
- la modélisation
- les reformulations
- les algorithmes

La modélisation consiste à prendre un problème "réel" et à l'écrire sous forme mathématique.
La reformulation consiste à transformer un problème "mathématique" sous une forme acceptable par un solveur / algo
(typiquement les réécritures que tu proposes, mais aussi des astuces de type "big M", etc.)
Les algorithmes sont ceux qui sont effectivement implémenté pour résoudre un problème.

Pour un problème "générique", dont tu n'exploites pas les particularités, il ne faut surtout pas essayer d'implémenter
un algo par soi même (sauf à fin pédagogiques) car les codes qui le font prennent en compte beaucoup de cas particuliers.
C'est particulièrement le cas pour l'optimisation linéaire, où coder un algo du simplexe ou des points intérieur n'a d'intérêt
que pour comprendre mieux le principe.

En revanche, même en optim linéaire, il existe tout plein de méthodes qui exploite des particularités du problème, typiquement
les méthodes de décompositions, génération de colonnes etc... On peut aussi voir que des formulations équivalentes mathématiquement
ne se résolve pas aussi vite par le solveur, et donc savoir trouver des formulations alternatives peut permettre de résoudre un même problème
en un temps beaucoup moindre.

Donc dans des cours d'intro à l'optim on apprends :
- le principe des algorithmes (pour en comprendre les avantages et inconvénients, conditions de convergence, vitesse, etc)
- des méthodes de modélisation de problèmes
- des méthodes pour reformuler des problème

Les cours d'intro à la RO sont très souvent des cours d'optim linéaire (éventuellement avec nombres entier).

Voilà, j'espère que c'est plus clair.

[Tete marcel]

Je vais préciser ma question sur cet exercice; comment modéliser cet exercice de programmation linéaire ? c'est a dire écrire sous forme des inéquations mathématiques ou encore, faire ressortir des contraintes. c'est ça la clef de la résolution. Énoncé du problème:

Une usine peut produire 5 types de produits en utilisant deux procédés de fabrication: meulage et forage, après déduction de cout, des intrants, chaque unité de chaque produit donne les contributions suivantes:
PROD 1 PROD 2 PROD 3 PROD 4 PROD 5
500 $ 600 $ 350 $ 400 $ 200 $

Chaque unité requiert un certain temps de production sur chaque procédé, temps donné en heure dans le tableau ci-après :
PROD 1 PROD 2 PROD 3 PROD 4 PROD 5
MEULAGE 12 20 - 25 15
FORAGE 10 8 16 - -

L’assemblage de chaque produit nécessite 2O heures de travail de la part d’un employé. l’usine dispose de trois machines de meulage et de deux machines de forage, l’usine travaille 6 jours par semaine avec deux équipes de 8 heures par jour, 8 personnes travaillant à l’assemblage, chacune travaillant dans une équipe par jour.
Déterminer l’assortiment optimal qui maximise le profit total.