pldual.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sommet.h"
#include "ray_dte.h"
#include "polyedre.h"
#include "matrix.h"
#include "plint.h"

Include dependency graph for pldual.c:

Go to the source code of this file.

Macros
#define	MALLOC(s, t, f)   malloc(s)
	package plint More...

Functions
Psommet	ligne_pivot (Psommet sys, int nb_som, no_som)
	Psommet ligne_pivot(Psommet sys, int nb_som, int * no_som): recherche de la ligne pivot dans l'algorithme dual du simplexe. More...
Variable	var_pivotd (Psommet eq, Psommet fonct)
	int var_pivotd(Psommet eq, Psommet fonct): recherche de la nouvelle variable pivot entrant dans la base au cours de l'execution de l'algorithme dual du simplexe More...
bool	dual_pivot_pas (Psommet *sys, Pvecteur *lvbase, int nb_som, Psommet fonct, int *nbvars, Pbase *b)
	bool dual_pivot_pas(Psommet * sys, Pvecteur * lvbase, int nb_som, Psommet fonct, int * nbvars, Pbase * b): execution d'un pas de l'algorithme dual du simplexe i.e. More...
bool	dual_pivot (Psysteme sys, Psysteme *syst_result, Psommet *fonct, int *nb_som, Pvecteur *lvbase)
	bool dual_pivot(Psysteme sys, Psysteme * syst_result, Psommet * fonct, int * nb_som, Pvecteur * lvbase): Algorithme dual du simplexe (c.f. More...
Psysteme	dual (Psysteme sys, Psommet fonct)
	Psysteme dual(Psysteme ps, Psommet fonct): Algorithme dual du simplexe avec initialisation des parametres. More...
Psysteme	dual_positive (Psysteme sys, Psommet fonct)

Macro Definition Documentation

MALLOC

#define MALLOC	(		s,
			t,
			f
	)		malloc(s)

package plint

pour recuperer les declarations des fonctions de conversion de sc en liste de sommets et reciproquement, bien que ca casse le DAG des types de donnees

Definition at line 52 of file pldual.c.

Function Documentation

dual()

Psysteme dual	(	Psysteme	sys,
		Psommet	fonct
	)

Psysteme dual(Psysteme ps, Psommet fonct): Algorithme dual du simplexe avec initialisation des parametres.

resultat retourne par la fonction :

Psysteme : systeme final dont on peut deduire la valeur des differentes variables du systeme.

NULL : si le systeme initial est non faisable.

Les parametres de la fonction :

! Psysteme sys : systeme lineaire ! Psommet fonct : fonction economique du programme lineaire

Definition at line 351 of file pldual.c.

{
 
    Psysteme syst_result = NULL;
    Pvecteur lvbase = NULL;
    int nb_som = 0;
 
    dual_pivot(sys,&syst_result,&fonct,&nb_som,&lvbase);
    vect_rm(lvbase);
    return(syst_result);
}

References dual_pivot(), and vect_rm().

Referenced by chernikova().

Here is the call graph for this function:

Here is the caller graph for this function:

dual_pivot()

bool dual_pivot	(	Psysteme	sys,
		Psysteme *	syst_result,
		Psommet *	fonct,
		int *	nb_som,
		Pvecteur *	lvbase
	)

bool dual_pivot(Psysteme sys, Psysteme * syst_result, Psommet * fonct, int * nb_som, Pvecteur * lvbase): Algorithme dual du simplexe (c.f.

Programmation mathematique - tome 1 . M.MINOUX (83) )

resultat retourne par la fonction :

bool : == true si le systeme a une solution == false sinon

Le parametre SYST_RESULT est le systeme final (dont on peut deduire la valeur des differentes variables du systeme) . S'il est vide, c'est que le systeme initial est non faisable.

Les parametres de la fonction :

! Psysteme sys : systeme lineaire Psysteme syst_result: systeme lineaire resultant de l'execution ! Psommet fonct : fonction economique du programme lineaire ! Pvecteur lvbase : liste des variables de base du systeme ! int nb_som : nombre de contraintes du systeme

Definition at line 297 of file pldual.c.

{
    Psommet som = (Psommet) NULL;
    int nbvars = 0;
    Pbase b = BASE_NULLE;
#ifdef TRACE
    printf(" ** algorithme dual du simplexe \n");
#endif
    if (sys != (Psysteme) NULL) {
        nbvars = sys->dimension;
        b = base_dup(sys->base);
        som = sys_som_conv(sys,nb_som);
 
        som = eq_in_ineq(&som,nb_som,lvbase);
        som = var_ecart_sup(som,*nb_som,lvbase,&nbvars,&b);
 
        while( (som != (Psommet) NULL) && 
               (dual_pivot_pas(&som,lvbase,*nb_som,*fonct,&(sys->dimension),
                               &(sys->base))    == true) );
 
        *syst_result = som_sys_conv(som);
        if (*syst_result) {
            (*syst_result)->dimension = sys->dimension;
            (*syst_result)->base = base_dup(sys->base);
        }
    }
    if(som == (Psommet) NULL);
    else  sommets_rm(som);
  
    return((boolean) (som != (Psommet) NULL));
}

References base_dup(), BASE_NULLE, dual_pivot_pas(), eq_in_ineq(), printf(), sommets_rm(), and var_ecart_sup().

Referenced by dual(), and dual_positive().

Here is the call graph for this function:

Here is the caller graph for this function:

dual_pivot_pas()

bool dual_pivot_pas	(	Psommet *	sys,
		Pvecteur *	lvbase,
		int	nb_som,
		Psommet	fonct,
		int *	nbvars,
		Pbase *	b
	)

bool dual_pivot_pas(Psommet * sys, Pvecteur * lvbase, int nb_som, Psommet fonct, int * nbvars, Pbase * b): execution d'un pas de l'algorithme dual du simplexe i.e.

• ajout des variables d'ecart
• recherche d'un pivot

• on effectue le pivot

  resultat retourne par la fonction :

  bool : == false si l'on n'a pas pu effectuer un pas de l'algorithme dual == true si l'on a pu effectuer un pas de l'algorithme

  le systeme est modifie. Si le systeme retourne est NULL, c'est que le systeme est non borne.

  Les parametres de la fonction :

  Psommet sys : systeme lineaire Psommet fonct : fonction economique du programme lineaire Pvecteur lvbase: liste des variables de base du systeme int nb_som : nombre de contraintes du systeme. int nbvars : nombre de variables du systeme. Pbase * b : liste des variables du systeme

recherche de la ligne pivot

recherche de la variable pivot

operation PIVOT

Definition at line 213 of file pldual.c.

{
 
    Psommet ligne_entrant =NULL;
    Psommet *ps=NULL;
    int no_som = 0;
    bool result = true;
 
#ifdef TRACE
    printf(" *** alg. dual -  un pas de l'algorithme \n");
#endif
    ps = sys;
 
    *ps = var_ecart_sup(*ps,nb_som,lvbase,nbvars,b);
 
    /* recherche de la ligne pivot      */
    ligne_entrant = ligne_pivot(*ps,nb_som,&no_som);
    if ((ligne_entrant != NULL))
    {
        Variable var_entrant = NULL;
        /* recherche de la variable pivot       */
        var_entrant = var_pivotd(ligne_entrant,fonct);
 
        if (VARIABLE_DEFINED_P(var_entrant))
        {
            /* operation PIVOT  */
            pivoter(*ps,ligne_entrant,var_entrant,fonct);
            lvbase_ote_no_ligne(no_som,lvbase);
            lvbase_add(var_entrant,no_som,lvbase);
        }
        else {
            if (VARIABLE_UNDEFINED_P(var_entrant))
            {
                sommets_rm(*sys);
                *sys = NULL;
                result = false;
#ifdef TRACE
                printf (" --- alg. dual - le probleme n'est pas borne \n");
#endif
            }
        }
    }
    else 
    {
        result = false;
#ifdef TRACE
        printf (" --- alg. dual - plus de ligne pivot possible \n");
#endif
    }
 
    return (result);
 
}

References ligne_pivot(), lvbase_add(), lvbase_ote_no_ligne(), pivoter(), printf(), sommets_rm(), var_ecart_sup(), var_pivotd(), VARIABLE_DEFINED_P, and VARIABLE_UNDEFINED_P.

Referenced by dual_pivot(), plint_pas(), and plreal().

Here is the call graph for this function:

Here is the caller graph for this function:

dual_positive()

Psysteme dual_positive	(	Psysteme	sys,
		Psommet	fonct
	)

Parameters

fonct

Psommet ???

Definition at line 365 of file pldual.c.

{
 
    Psysteme syst_result = NULL;
    Pvecteur lvbase = NULL;
    int nb_som = 0;
 
    dual_pivot(sys,&syst_result,&fonct,&nb_som,&lvbase);
    if (!sol_positive(sys,lvbase,nb_som)) { 
        sc_rm(syst_result);
        syst_result=NULL;}
 
    vect_rm(lvbase);
    return(syst_result);
}

References dual_pivot(), sc_rm(), sol_positive(), and vect_rm().

Here is the call graph for this function:

ligne_pivot()

Psommet ligne_pivot	(	Psommet	sys,
		int	nb_som,
		no_som
	)

Psommet ligne_pivot(Psommet sys, int nb_som, int * no_som): recherche de la ligne pivot dans l'algorithme dual du simplexe.

resultat retourne par la fonction : Psommet : prochaine contrainte "pivot"

Les parametres de la fonction :

Psommet sys : systeme lineaire int nb_som : nombre de contraintes du systeme int no_som : place de la contrainte dans le systeme (no de la ligne)

initialisation du minimum

Definition at line 66 of file pldual.c.

{
    Psommet som1,som2;
    Psommet lpivot= NULL;
    double min;
    double coeff;
    int nb_som1 = nb_som;
    Value den;
    double dden;
 
#ifdef TRACE
    printf(" **** alg. dual - recherche de la ligne pivot \n");
#endif
 
 
    if (sys) den = sys->denominateur;
    /*  initialisation du minimum    */
 
    for (som2 = sys;som2 != NULL  
         && value_posz_p(vect_coeff(TCST,som2->vecteur)) ;
         som2 = som2->succ,nb_som1 --);
    den = som2->denominateur;
    dden = VALUE_TO_DOUBLE(den);
 
    min = -VALUE_TO_DOUBLE(vect_coeff(TCST,som2->vecteur))/dden;
    lpivot = som2;
    *no_som = nb_som1;
    nb_som1 --;
    for (som1 = som2->succ;som1 != NULL;som1 = som1->succ)
    {
        den = som1->denominateur;
        if ((coeff = -VALUE_TO_DOUBLE(vect_coeff(TCST,som1->vecteur))/dden) < 0
            && coeff < min)
        {
            min = coeff;
            lpivot = som1;
            *no_som = nb_som1;
 
        }  nb_som1--;
    }
    return(lpivot);
}

References typ_som::denominateur, min, printf(), typ_som::succ, TCST, value_posz_p, VALUE_TO_DOUBLE, vect_coeff(), and typ_som::vecteur.

Referenced by dual_pivot_pas(), and plint_pas().

Here is the call graph for this function:

Here is the caller graph for this function:

var_pivotd()

Variable var_pivotd	(	Psommet	eq,
		Psommet	fonct
	)

int var_pivotd(Psommet eq, Psommet fonct): recherche de la nouvelle variable pivot entrant dans la base au cours de l'execution de l'algorithme dual du simplexe

resultat retourne par la fonction : int : variable "pivot" entrant dans la base

Les parametres de la fonction :

Psommet eq : contrainte du systeme Psommet fonct : fonction economique du programme lineaire

initialisation du minimum

pv = vect_tri(eq->vecteur, is_inferior_variable);

Definition at line 125 of file pldual.c.

{
    Pvecteur pv= VECTEUR_NUL;
    double min=0, min2;
    Variable no_lpivot = NULL;
    Value cf2 = VALUE_ZERO;
    bool trouve = false;
 
#ifdef TRACE
    printf(" **** alg. dual - recherche de la variable pivot \n");
#endif
 
    if (eq && fonct)
    {
        /* initialisation du minimum   */
        Value cst = vect_coeff(TCST,eq->vecteur);
        Pvecteur pv3;
        vect_chg_coeff(&(eq->vecteur),TCST,0);
        pv = vect_sort(eq->vecteur, vect_compare);
        /* pv = vect_tri(eq->vecteur, is_inferior_variable); */
        for(pv3 =pv; pv3->succ!=NULL;pv3=pv3->succ);
        pv3->succ = vect_new(TCST,cst);
    
        for (; pv!= NULL && !trouve; pv = pv->succ) {
            if ((var_of(pv) != NULL) && (value_neg_p(val_of(pv))) && 
                (value_posz_p(cf2 = vect_coeff(var_of(pv),fonct->vecteur))))
            {
                double d1,d2 = 0;
                d1 = VALUE_TO_DOUBLE(pv->val) * 
                    VALUE_TO_DOUBLE(fonct->denominateur);
                d2 = VALUE_TO_DOUBLE(cf2) * 
                    VALUE_TO_DOUBLE(eq->denominateur) ;
                min = - d2/d1;
                trouve = true;
                no_lpivot = var_of(pv);
            }
        }
        if (pv != VECTEUR_NUL) {
            for (; pv!= NULL && trouve ;pv= pv->succ) {
                if ((var_of(pv) != NULL) && value_neg_p(val_of(pv)) &&
                    value_posz_p(cf2 = vect_coeff(var_of(pv),fonct->vecteur)))
                {
                    double d1,d2 = 0;
                    d1 = VALUE_TO_DOUBLE(cf2) *
                        VALUE_TO_DOUBLE(eq->denominateur);
                    d2 = VALUE_TO_DOUBLE(pv->val) * 
                        VALUE_TO_DOUBLE(fonct->denominateur);
                    min2 = -d1/d2;
                    if (min2 < min) {
                        min = min2;
                        no_lpivot = var_of(pv);
                    }
                }
            }
        }
    }
    vect_rm(pv);
 
    return (no_lpivot);
}

References eq, min, printf(), Svecteur::succ, TCST, Svecteur::val, val_of, value_neg_p, value_posz_p, VALUE_TO_DOUBLE, VALUE_ZERO, var_of, vect_chg_coeff(), vect_coeff(), vect_compare(), vect_new(), vect_rm(), vect_sort(), Scontrainte::vecteur, and VECTEUR_NUL.

Referenced by dual_pivot_pas(), and plint_degen().

Here is the call graph for this function:

Here is the caller graph for this function: