programmation linéaire

invite769a1844 · 01/04/2009, 20h45

Bonjour,

les premières définitions de mon cours me posent quelques problèmes.

On dit que $\text{[math]}$ est solution de base de $\text{[math]}$ où $\text{[math]}$ , la matrice $\text{[math]}$ ( $\text{[math]}$ ) étant de rang $\text{[math]}$ , s'il peut être construit de la façon suivante:
on choisit un ensemble d'indices $\text{[math]}$ tel que les vecteurs colonnes extraits de $\text{[math]}$ dont les indices sont dans $\text{[math]}$
$\text{[math]}$ soient linéairement indépendants donc forment une matrice carrée $\text{[math]}$ inversible $\text{[math]}$ extraite de $\text{[math]}$ ;

ensuite on résout $\text{[math]}$ où $\text{[math]}$ ; la solution $\text{[math]}$ est alors définie par $\text{[math]}$

On dit que $\text{[math]}$ est solution de base admissible de $\text{[math]}$ si c'est une solution de base de $\text{[math]}$ tel que $\text{[math]}$ (ie toutes ses composantes sont $\text{[math]}$ ).

Il est dit qu'il est possible que les solutions de base admissibles de $\text{[math]}$ sont les points extrémaux du polyèdre convexe $\text{[math]}$ .

Pour essayer de montrer ce résultat, on prend $\text{[math]}$ tel que $\text{[math]}$ contienne une base admissible $\text{[math]}$ et on essaie de montrer que $\text{[math]}$ ou $\text{[math]}$ .

Or il est dit qu'il suffit de remarquer le fait que $\text{[math]}$ pour $\text{[math]}$ implique forcément que $\text{[math]}$ pour $\text{[math]}$ .

Je suis d'accord avec cette remarque mais en quoi c'est suffisant pour montrer que $\text{[math]}$ est un point extrémal? Il doit y avoir quelque chose qui m'échappe

Merci pour votre aide.

**acx01b** · 02/04/2009, 14h52

salut

xj = a.yj + (1-a).zj
avec a.yj >= 0 et (1-a).zj >= 0 (a coefficient d'interpolation, et y,z appartiennent à P)

donc pour chaque j, si xj = 0 alors
- soit yj et zj sont nuls,
- soit a et zj sont nuls
- soit 1-a et yj sont nuls

- si pour tout les j où xj est nul, yj et zj sont nuls, alors y = z car la matrice est de rang m, et donc x = y = z
- sinon on a 'a' ou '1-a' qui est nul et donc x = y ou x = z

programmation linéaire