AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

  • C / C++ / C++.NET CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2009 07 05 06:59:34
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

PROGRAMMATION LINEAIRE


Information sur la source

Catégorie :Maths & Algorithmes Classé sous : lineaire, simplex, pivot, programmation, polytope Niveau : Débutant Date de création : 15/01/2008 Date de mise à jour : 15/01/2008 20:25:23 Vu / téléchargé: 8 784 / 482
Auteur : JCDjcd Ecrire un message privé
Ce membre participe au partage de revenus publicitaires
Note :
Aucune note
Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale
Voici un programme que j'ai concu il y a quelques mois.
Il resout le probleme de la programmation lineaire par
l'algorithme du simplexe. Tout est tres bien explique
dans numerical recipes au chapitre 10, vous expliquez
serait seulement de la paraphrase...

L'atout majeur du programme est l'apercu graphique du
probleme, ce qui permet d'avoir une bonne visualisation
du deroulement de l'algorithme, et en meme permet de
justifer la validite de l'implementation (pas ou moins
de bug)

La visualisation se fait en toute dimension, alors ames
sensibles s'abstenir pour ceux qui pensent qu'il n'est
pas possible d'afficher un espace N dimensions sur un
ecran 2 dimensions. Les axes sont marques en bas a droite,
la rotation des axes s'effectue avec les touches 'P' et 'M',
et le choix des deux axes par les nombres 1,2,3...
et SHIFT+1,2,3... au dessus du clavier (pas le pave numerique)
La touche espace pour faire une etape de l'algorithme, les
aretes visitees se colorient au fur et a mesure en violet
(ou orange), et le polytope est en vers.
En haut a gauche il y a le tableau de l'algorithme similaire
a celui decrit dans le numerical recipes (LA reference...)

On possede n hyperplans et il y a p variables (on vit
donc dans un espace de dimension p)
Le calcul du polytope est simple et bourrin : on calcule tous
les sommets (on calcule les intersections de p hyperplans
choisis parmi n, ce qui en fait C(p,n), ce qui est grand,
l'intersection se calcule en inversant une matrice...
pour ce faire l'algorithme du pivot de Gauss est le
bien-venu)
Ensuite il suffit de calculer les aretes a partir de
l'ensemble des sommets : deux sommets qui differs qu'un
hyperplan sont les sommets d'une aretes du polytope,
c'est logique ! facile.

L'exemple du polytope de gauche est un hypercube en 4D.
L'exemple du polytope de droite est genere aleatoirement.


En pratique l'algorithme du simplexe est polynomial,
mais en theorie il est exponentiel (voir contre-exemple
de Klee-Minty)

Petit rappel :
La programmation lineaire consiste a maximiser une fonction
linaire (gradient constant) des variables x1,x2...xp sous
contraintes lineaires de la forme "dans un demi-espace"
(i.e. a1.x1+a2.x2+...ap.xp<=A).
Ce probleme ce rencontre dans les problemes de flots
maximals, ou dans des problemes d'optimisations de productions
en economie... les applications ne manquent pas.
L'ensemble des solutions de ce probleme est un polytope
(parti convexe dont la frontiere est des bouts d'hyperplans)
L'idee du simplexe est d'abord de dire que la solution
optimale est forcement sur un sommet, ensuite de dire que
l'on part initialement d'un sommet et qu'a chaque iteration
de l'algorithme on change de sommet en se deplacant suivant
(ou "le long de") d'une arete, et en se deplacant ainsi,
on a augmente la fonction objective (celle que l'on cherche
a maximiser). Le choix de l'arete est bien explique dans
numerial recipes.
... arretons-la la paraphrase.


N'hesite pas a poser des questions !

NB: le code qui suit, et l'algorithme sur une etape,
il gere seulement un seul pivot. Il est imcomprehensible
sans la connaissance de numerical recipes...basic vars
et slack vars...
 

Source

  • //-------------------------------------------------
  • BOOL oneStep(P_DATA_WINDOW data)
  • {
  • int i,j;
  • double deltaZj,deltaRVj;
  • double deltaZMax,deltaRVjMax;
  • int jMax,iLimjMax;
  • deltaZMax = 0.;
  • for(j=1;j<=data->nBasicVar;j++)
  • {
  • int iLim;
  • double deltaMax;
  • iLim = 0;
  • for(i=1;i<=data->nSlackVar;i++)
  • {
  • double C,beta;
  • C = GetItemMatrix(data->mat,i,0);
  • beta = GetItemMatrix(data->mat,i,j);
  • if(beta < 0)
  • {
  • double delta;
  • delta = - C / beta;
  • if(0 == iLim || delta < deltaMax)
  • {
  • iLim = i;
  • deltaMax = delta;
  • }
  • }
  • }
  • ErrorIf((0 == iLim,"le polytope n'est pas borné !!"));
  • deltaRVj = deltaMax;
  • deltaZj = GetItemMatrix(data->mat,0,j) * deltaRVj;
  • if(deltaZj > deltaZMax)
  • {
  • deltaZMax = deltaZj;
  • deltaRVjMax = deltaRVj;
  • jMax = j;
  • iLimjMax = iLim;
  • }
  • }
  • if(deltaZMax <= 0.)
  • {
  • //message(("\n\nFIN DE L'ALGORITHME DU SIMPLEXE\n\n"));
  • return FALSE;
  • }
  • // on echange les deux variables
  • {
  • int i0,j0;
  • double betai0j0;
  • i0 = iLimjMax;
  • j0 = jMax;
  • betai0j0 = GetItemMatrix(data->mat,i0,j0);
  • for(i=0;i<=data->nSlackVar;i++)
  • {
  • if(i != i0)
  • {
  • SetItemMatrix(data->matTmp,i,0,
  • GetItemMatrix(data->mat,i,0)
  • -
  • GetItemMatrix(data->mat,i,j0)*GetItemMatrix(data->mat,i0,0)/betai0j0
  • );
  • for(j=1;j<=data->nBasicVar;j++)
  • {
  • if(j != j0)
  • {
  • SetItemMatrix(data->matTmp,i,j,
  • GetItemMatrix(data->mat,i,j)
  • -
  • GetItemMatrix(data->mat,i0,j)*GetItemMatrix(data->mat,i,j0)/betai0j0
  • );
  • }
  • else
  • {
  • SetItemMatrix(data->matTmp,i,j,
  • GetItemMatrix(data->mat,i,j0)/betai0j0
  • );
  • }
  • }
  • }
  • else // i == i0
  • {
  • SetItemMatrix(data->matTmp,i,0,
  • -
  • GetItemMatrix(data->mat,i0,0)/betai0j0
  • );
  • for(j=1;j<=data->nBasicVar;j++)
  • {
  • if(j != j0)
  • {
  • SetItemMatrix(data->matTmp,i,j,
  • -
  • GetItemMatrix(data->mat,i0,j)/betai0j0
  • );
  • }
  • else
  • {
  • SetItemMatrix(data->matTmp,i,j,
  • 1./betai0j0
  • );
  • }
  • }
  • }
  • }
  • }
  • SwapPointer(&data->mat,&data->matTmp);
  • SwapPointer(&data->RVar[jMax-1],&data->LVar[iLimjMax-1]);
  • // on attribue les valeurs
  • for(i=0;i<data->nSlackVar;i++)
  • {
  • data->LVar[i]->val = GetItemMatrix(data->mat,1+i,0);
  • }
  • for(j=0;j<data->nBasicVar;j++)
  • {
  • data->RVar[j]->val = 0.;
  • }
  • return TRUE;
  • } // oneStep()
//-------------------------------------------------
BOOL oneStep(P_DATA_WINDOW data)
{
int       i,j;
double    deltaZj,deltaRVj;
double    deltaZMax,deltaRVjMax;
int       jMax,iLimjMax;

deltaZMax = 0.;
for(j=1;j<=data->nBasicVar;j++)
  {
  int     iLim;
  double  deltaMax;

  iLim  = 0;
  for(i=1;i<=data->nSlackVar;i++)
    {
    double C,beta;
    C    = GetItemMatrix(data->mat,i,0);
    beta = GetItemMatrix(data->mat,i,j);
    if(beta < 0)
      {
      double delta;
      delta = - C / beta;
      if(0 == iLim || delta < deltaMax)
        {
        iLim      = i;
        deltaMax  = delta;
        }
      }
    }

  ErrorIf((0 == iLim,"le polytope n'est pas borné !!"));

  deltaRVj = deltaMax;
  deltaZj  = GetItemMatrix(data->mat,0,j) * deltaRVj;

  if(deltaZj > deltaZMax)
    {
    deltaZMax     = deltaZj;
    deltaRVjMax   = deltaRVj;
    jMax          = j;
    iLimjMax      = iLim;
    }
  }

if(deltaZMax <= 0.)
  {
  //message(("\n\nFIN DE L'ALGORITHME DU SIMPLEXE\n\n"));
  return FALSE;
  }

// on echange les deux variables
  {
  int     i0,j0;
  double  betai0j0;

  i0        = iLimjMax;
  j0        = jMax;
  betai0j0  = GetItemMatrix(data->mat,i0,j0);

  for(i=0;i<=data->nSlackVar;i++)
    {
    if(i != i0)
      {
      SetItemMatrix(data->matTmp,i,0,
          GetItemMatrix(data->mat,i,0)
            -
          GetItemMatrix(data->mat,i,j0)*GetItemMatrix(data->mat,i0,0)/betai0j0
          );
      for(j=1;j<=data->nBasicVar;j++)
        {
        if(j != j0)
          {
          SetItemMatrix(data->matTmp,i,j,
              GetItemMatrix(data->mat,i,j)
                -
              GetItemMatrix(data->mat,i0,j)*GetItemMatrix(data->mat,i,j0)/betai0j0
              );
          }
        else
          {
          SetItemMatrix(data->matTmp,i,j,
              GetItemMatrix(data->mat,i,j0)/betai0j0
              );
          }
        }
      }
    else // i == i0
      {
      SetItemMatrix(data->matTmp,i,0,
            -
          GetItemMatrix(data->mat,i0,0)/betai0j0
          );
      for(j=1;j<=data->nBasicVar;j++)
        {
        if(j != j0)
          {
          SetItemMatrix(data->matTmp,i,j,
                -
              GetItemMatrix(data->mat,i0,j)/betai0j0
              );
          }
        else
          {
          SetItemMatrix(data->matTmp,i,j,
              1./betai0j0
              );
          }
        }
      }
    }
  }

SwapPointer(&data->mat,&data->matTmp);
SwapPointer(&data->RVar[jMax-1],&data->LVar[iLimjMax-1]);

// on attribue les valeurs
for(i=0;i<data->nSlackVar;i++)
  {
  data->LVar[i]->val = GetItemMatrix(data->mat,1+i,0);
  }
for(j=0;j<data->nBasicVar;j++)
  {
  data->RVar[j]->val = 0.;
  }

return TRUE;
} // oneStep()

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

15 janvier 2008 20:25:23 :
erreur de manip.

Commentaires et avis

signaler à un administrateur
Commentaire de coco3095 le 21/01/2008 00:33:53

Bonjour,
Assez chaud pour comprendre la bête...

Ce simplex a-t-il une garantie de convergence? (Méthode de bruitage pour les cas dégénérés)

Par contre, géniale l'idée de représenter graphiquement du multi-dimentionnel. Mais c'est tout de même assez hard à lire...

A quand le B&B... ^^

signaler à un administrateur
Commentaire de neomac le 29/04/2009 00:16:16

Bonjour,

Je n'arrive pas à le faire fonctionner, est-ce qu'il faut effectuer des configurations (au niveau du classpath, par exemple) ?

Merci

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

programmation lineaire [ par ranyita ] salut,je suis une nouvelle condidature de code source et je vous informe que votre site est trés interessants pour tout  les gens précisement les etud Windows et MIDI [ par mezzan ] Bonjour à tous,Je dois développer une application WINDOWS pour piloter un appareil MIDI externe.  J'ai fouillé sur le site de Microsoft, mais je n'ai programmation - les flottants [ par seyna ] Salut à tous!là j'ai besoin d'aide. je suis débutante en programmation et ça m'interresse vraiment. là je suis sur la programmation de la calculat programmation des expression réguliere en C ou C++ [ par omaraitsalah82 ] Slt les amies je cherche un programme qui permet générer un fichier XML ou text a partire  une expression réguliere et merci beaucoup pour votre aide le simplexe programatio lineaire [ par SaoudAyoub ] comment realise  le siplexe programation lénéaire en c ou Exel'je code source' aide pour le choix du stage d'été [ par safoo86 ] salut,je suis charfeddineje vous sollicite un aide pour choisir le sujet de mon stage d'été en programmation:il y a beaucoup de sujets tel la programm programmation [ par fouad59 ] voila je suis débutant en C++ je voulais savoir en combien de temps je pourrai maitriser ce langage et quesqu'on peut faire avec le C++ ? aide à la programmation [ par sosocha ] bonjour à tous et toutes,je suios un étudiant en aéronautique, je vais terminer mes études cette année: ingeniorat en aéronautique, option installatio programmation Qt [ par Topnotch ] BonjourJe voudrais changer la couleur d'un bouton sous Qt. Également, je voudrais créer une fenêtre ouvrir. J'ai cherché dans la documentation Qt de t gerer par programmation deux ecrans avec une seule unité centrale [ par juguinfo ] actuellement je veux developper une application qui peu contrôler deux écrans branchés à une seule unité centrale à l'aide d'une carte graphique.si vo


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version


LG KP501
Entre 9€ et 159€


Visiter le guide achat

Photothèque Nouveau !

Photo sitges beachPhoto friends
Photo cascades de plitvicePhoto chambre pleine d'amour

Visiter la photothèque


Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés
Temps d'éxécution de la page : 0,452 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.