PIPS
|
#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"
Go to the source code of this file.
Macros | |
#define | MALLOC(s, t, f) malloc(s) |
package plint More... | |
Functions | |
Psommet | plint_pas (Psommet sys1, Psommet fonct, Pvecteur *lvbase, int *nb_som, int *nbvars, Pbase *b) |
Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur * lvbase, int * nb_som, int * nbvars, Pbase *b): Algorithme des congruences decroissantes (Michel Minoux - Programmation mathematique - theorie et algorithmes- tome 2. More... | |
bool | plint_degen (Psommet *sys, Psommet fonct, int *nb_som, Pvecteur *lvbase, int *nbvars, Pbase *b) |
void plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur * lvbase, int nbvars, Pbase * b): Cas de degenerescence au cours de l'algorithme des congruences decroissantes More... | |
Psysteme | plint (Psysteme first_sys, Psommet fonct, Psolution *sol_fin) |
Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin): resolution d'un systeme lineaire en nombres entiers positifs par l'algorithme general des congruences decroissantes (c.f. More... | |
Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin): resolution d'un systeme lineaire en nombres entiers positifs par l'algorithme general des congruences decroissantes (c.f.
Programmation Mathematique - tome 2. M.MINOUX (83))
resultat retourne par la fonction :
Psysteme : systeme lineaire donnant la solution de base du systeme ,si celui ci est realisable. Dans ce cas, son cout optimal vaut la valeur (avec le signe - ) de la constante de la fonction economique et la solution de base est exprimee sous la forme d'une Psolution.
NULL : si le systeme initial n'est pas realisable.
Les parametres de la fonction :
Psysteme first_syst : systeme lineaire initial Psommet fonct : fonction economique du programme lineaire
ajout des variables d'ecart
Definition at line 430 of file plint.c.
References Ssysteme::base, base_dup(), BASE_NULLE, Ssolution::denominateur, typ_som::denominateur, Ssysteme::dimension, eq_in_ineq(), noms_var(), plint_pas(), primal_pivot(), printf(), sc_dup(), sc_normalize(), sc_rm(), sol_finale(), sommets_rm(), Ssolution::succ, syst_smith(), TCST, Ssolution::val, Ssolution::var, var_ecart_sup(), vect_coeff(), vect_rm(), and typ_som::vecteur.
Referenced by find_eg(), and sys_int_fais().
bool plint_degen | ( | Psommet * | sys, |
Psommet | fonct, | ||
int * | nb_som, | ||
Pvecteur * | lvbase, | ||
int * | nbvars, | ||
Pbase * | b | ||
) |
void plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur * lvbase, int nbvars, Pbase * b): Cas de degenerescence au cours de l'algorithme des congruences decroissantes
resultat retourne par la fonction :
Le systeme initial est modifie. S'il est vide, c'est que le systeme est non faisable. Sinon on ajoute une contrainte supplementaire permettant la non degenerescence du programme lineaire.
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
construction de la liste des variables hors base de cout non nul
construction d'une nouvelle fonction economique pour le systeme dont on a elimine les variables h.base de cout non nul
recherche d'une solution entiere pour ce nouveau systeme
le systeme n'admet aucune solution entiere
ajout inegalite permettant la non-degenerescence du programme lineaire
on recherche la variable pivot et on effectue le pivot
Definition at line 288 of file plint.c.
References typ_som::denominateur, typ_som::eq_sat, lvbase_add(), lvbase_ote_no_ligne(), MALLOC, oter_lvbase(), pivoter(), plint_pas(), printf(), SOMMET, sommet_add(), sommets_dupc(), sommets_rm(), typ_som::succ, Svecteur::succ, TCST, VALUE_MONE, VALUE_ONE, VALUE_ZERO, Svecteur::var, var_ecart_sup(), var_pivotd(), vect_add_elem(), vect_chg_coeff(), vect_dup(), vect_new(), vect_rm(), typ_som::vecteur, VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.
Referenced by plint_pas().
Psommet plint_pas | ( | Psommet | sys1, |
Psommet | fonct, | ||
Pvecteur * | lvbase, | ||
int * | nb_som, | ||
int * | nbvars, | ||
Pbase * | b | ||
) |
Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur * lvbase, int * nb_som, int * nbvars, Pbase *b): Algorithme des congruences decroissantes (Michel Minoux - Programmation mathematique - theorie et algorithmes- tome 2.
Dunod. p22. )
resultat retourne par la fonction :
Psommet : systeme lineaire modifie
Les parametres de la fonction :
Psommet sys1 : 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
test de degenerescence
recherche d'une variable de base non entiere, puis ajout d'une coupe de Gomory
il n'y a plus de variable non entiere
on effectue un pas de l'algorithme dual du simplexe
ajout des variables d'ecart
la solution est entiere mais pas positive
on a une solution positive
cas de degenerescence
on a une sol. entiere et positive a la fin de
l'execution de l'algorithme dual du simplexe
on a une solution entiere et positive a la fin
de l'execution de l'algorithme primal du simplexe
Definition at line 73 of file plint.c.
References const_negative(), cout_nul(), typ_som::denominateur, dual_pivot_pas(), false, gomory_eq(), gomory_trait_eq(), ligne_pivot(), noms_var(), plint_degen(), primal_pivot(), printf(), sc_fprint(), sol_entiere(), sol_positive(), sommet_add(), sommets_rm(), TCST, value_div, VALUE_TO_DOUBLE, value_uminus, VALUE_ZERO, value_zero_p, var_ecart_sup(), vect_coeff(), and typ_som::vecteur.
Referenced by plint(), and plint_degen().