begin process at 2012 02 12 10:17:03
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > PROGRAMMATION LINEAIRE

PROGRAMMATION LINEAIRE


 Information sur la source

Note :
Aucune note
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é :15 532 / 801
Auteur : JCDjcd

Ecrire un message privé
Ce membre participe au partage de revenus publicitaires
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

Les Membres Club peuvent 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.

 Sources du même auteur

Source avec Zip Source avec une capture COLORATION SYNTAXIQUE
Source avec Zip Source avec une capture ORBITES DES SATELLITES GPS
Source avec Zip Source avec une capture DESSIN D'ARBRES
Source avec Zip EXTENSION DE CORPS (MATH)
Source avec Zip Source avec une capture CACUL (RAPIDE) DE PGCD
Toutes les sources de JCDjcd

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

PIVOT DE GAUSS par Jbs106
ALGO RÉSOLUTION DE SUDOKU. par mamsk00
[PSP]HELLO WORLD par Mario1095
Source avec Zip Source avec une capture JEU EN SDL "LANGAGE C" par thechef
Source avec Zip Source avec une capture TRAITEMENT IMAGE: MODIFICATION NON LINÉAIRE DES COULEURS (CM... par Pistol_Pete

Commentaires et avis

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... ^^

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 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...

Comparez les prix


Mio - Moov V735 - GPS Europe - Ecran 7"
Entre 305€ et 375€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Beautiful woman in a bikini meditating on the beachPhoto Happy Bright Landscape WIth Butterflies
Photo Pêche au Carrelet, la Barre-de-Monts, vendée (85), Pays de loire 

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

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,326 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)