Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Programmation linéaire

Posté par
jackobenco
09-02-18 à 20:57

Bonsoir à la communauté ,

je suis un débutant (pour ne pas dire pire) en optimisation , je suis en train de voir la programmation linéaire et l'on m'indique une proposition :
Soit f une fonction linéaire tel que f : C -> oú C est un polyèdre convexe fermé et inf f (sur C) -oo alors xC tel que f(x) = inf f (sur C).

J'ai essayé : aucune idée et intuitions ( ça nécessite surement un certain niveau) .

Quelqu'un pourrait-il m'aider s'il vous plaît ?

Merci d'avance à la communauté.

Posté par
jackobenco
re : Programmation linéaire 09-02-18 à 21:51

Quelqu'un aurait-il une idée ?

Posté par
jsvdb
re : Programmation linéaire 09-02-18 à 22:27

Bonsoir jackobenco.
Je peux toujours t'indiquer les étapes de démonstration, tu pourras essayer de la faire. C'est plus long que compliqué.
Tout d'abord, on va préciser que C est un convexe fermé pris dans un \R^n; si c'est autre chose, tu voudras bien préciser.

Préliminaire : on pose m = \underset{v\in C}{\inf} f(v). Comme f est linéaire, alors \exists v_0 \in C, f(v_0) \neq +\infty et donc m \neq +\infty.

1ère étape : construction d'une suite minimisante (v_n)_n c'est-à-dire f(v_n) \rightarrow m.

Comme m est fini (puisque \underset{v\in C}{\inf} f \neq -\infty), alors \forall \varepsilon > 0, \exists v \in C, m \leq f(v) < m+ \varepsilon.
En prenant \varepsilon = 1/n, il existe une suite (v_n)_n \in C^{\N^*} telle que f(v_n) \rightarrow m

2ème : montrer que (v_n)_n est bornée. Se fait par l'absurde.

3ème étape : extraire de (v_n)_n une sous-suite convergente.

4ème étape : passer à la limite.

Dans le cas où f n'est pas linéaire mais strictement convexe, il y a une 5ème étape : l'unicité de la limite.

Posté par
jackobenco
re : Programmation linéaire 09-02-18 à 23:44

Ah d'accord merci , cependant je comprends pas pourquoi le fait que f soit linéaire sur C ça implique qu'il existe vo tel que f(vo) +oo.

Posté par
jsvdb
re : Programmation linéaire 10-02-18 à 00:08

Il me semble que tu as écrit f : C -> donc non seulement il existe, mais en plus c'est \forall v \in C, f(v) \neq +\infty
(Le fait que f soit linéaire n'entre en fait pas en ligne de compte)

Posté par
jackobenco
re : Programmation linéaire 10-02-18 à 00:32

Pour l'étape 2 , l'idée est d'arriver sur une absurdité telle que f(Xno)= +oo  ou (-oo) ?
Je n'attends pas la correction lol .

Posté par
jsvdb
re : Programmation linéaire 10-02-18 à 00:39

oui, disons au moins pour une sous-suite ...

Posté par
jackobenco
re : Programmation linéaire 10-02-18 à 00:47

bon je t'avoue effectivement , j'ai pas le niveau pour faire ces questions j'ai beau essayé , impossible

Posté par
jsvdb
re : Programmation linéaire 11-02-18 à 00:10

Pour la 2ème étape, si (v_n)_n n'est pas bornée, alors il y a une sous-suite (v_{\varphi(n)})_n telle que ||v_{\varphi(n)}|| \rightarrow \infty.

Comme f et linéaire alors ||f(v_{\varphi(n)})|| \rightarrow \infty, ce qui contredit f(v_n) \rightarrow m.

Évidemment, si le convexe est déjà borné, on zappe cette étape.

Les étapes 3 et 4 sont triviales. Pour la 4, évidemment, il faut dire que f est continue pour conclure (ce qui présuppose qu'on est en dimension finie pour pouvoir affirmer sans ambages la continuité de f, sinon, il fallait avoir supposé dans l'énoncé que f était continue : c'est pour cela que je t'ai demandé de préciser au début)

Posté par
jackobenco
re : Programmation linéaire 11-02-18 à 00:20

Ok merci beaucoup

Posté par
jackobenco
re : Programmation linéaire 13-02-18 à 23:25

bonsoir malgré tout , qu'est-ce qui nous garantit que la suite Vn converge , on a juste une suite extraite qui converge dans C. ça nous indique rien sur Vn

Posté par
jackobenco
re : Programmation linéaire 13-02-18 à 23:51

oups désolé

Posté par
jackobenco
re : Programmation linéaire 14-02-18 à 00:07

quoique après réflexion je n'y arrive toujours pas

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1344 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !