Trouver le moins disant dans un appel d’offre

Maaloum · March 2021

Bonjour à tous,

Une institution a lancé un appel d’offre de construction de 7 Bâtiments, 13 soumissionnaires ont été participés à chaque lot (Chaque construction d’un Bâtiment).

L’institution a envisagé une liste des Règles de choix :
Règle de choix 1 : Le lot doit être attribué au moins disant.
Règle de choix 2 : un soumissionnaire n’est peut pas gagner plus d’un lot.
Règle de choix : les lots doivent être distribués d’une manière que l’institution investie le minimum d’argent possible.
Note : si un soumissionnaire est moins disant sur deux lots ou plus, on va luis donner qu’un seul lot d’une manière que l’institution dépense le minimum d’argent.
Y a-t-il une manière (formule) à appliquer pour trouver les moins disant sans qu’un soumissionnaire gagne deux lots avec le minimum des dépenses ?

Merci.

Fin de partie · March 2021

Chaque postulant peut faire qu'une seule proposition ou doit-il faire une proposition pour chaque lot?

Maaloum · March 2021

il peut bien faire à chaque lot une proposition

lourrran · March 2021

Les postulants ont fait une proposition pour chaque lot. On a lancé les appels d'offre, et on a reçu les 7*13 offres.

Il faut faire de la combinatoire. Analyser toutes les combinaisons.
13*12*11*10*9*8*7 combinaisons à analyser, si on ne fait aucune optimisation.
7*7*7*7*7*7*7 combinaisons à analyser, après une optimisation assez basique.
En vrai, il y a des solutions beaucoup plus efficaces. Et on devrait souvent trouver la meilleure solution en comparant une centaine de solutions.
Bel exercice d'algorithmique.

gerard0 · March 2021

Bonjour.

A priori, c'est assez simple : On trie les propositions par montant, et on choisit les moins disant. Si deux lots sont attribués au même soumissionnaire, on considère les moins-disant suivants, et on calcule les deux totaux sur l'ensemble des deux lots.
Par exemple Lot 1 / S1: 1000, S2 : 1050; Lot 2 / S1:2000, S3 (*) :2200; 1000+2200>1050+2000, donc on choisit S2 pour le lot 1 et S1 pour le lot 2.
Idem si le même soumissionnaire est le moins disant des trois lots.

Ce genre de choses est à la portée d'un employé de la comptabilité.

Cordialement.

(*) qui peut être S2.

lourrran · March 2021

A la main, ça peut être très fastidieux.

La demande est de bâtir un cheminement pour que l'employé de la comptabilité trouve la solution, sans erreur, en un temps raisonnable.
Mais dès que les données sont bien alambiquées (sur tous les lots, S1 est le moins cher, S2 arrive en 2ème, S3 arrive en 3ème etc etc. ), ou si on passe à 10 lots au lieu de 7, l'employé de la comptabilité aura vite besoin d'un algorithme.

Etape 1 : Pour chaque lot, on recherche le moins-disant, on a le prix correspondant, et on remplace le prix demandé par chaque soumissionnaire par le surcoût entre ce prix et le prix optimal. Ca permettra plus facilement de calculer un surcoût entre un scénario X et un scénario idéal.

Etape 2 : chercher une combinaison valide, pas forcément optimale.
Je prends le moins disant sur le lot 1 , le moins disant sur le lot 2 ( en excluant le prestataire retenu pour le lot 1 ) ... etc. J'obtiens une solution valide, relativement efficace en principe. Je calcule le sûrcout correspondant à cette solution (la somme des surcouts des différents lots). Si ce montant est 0, c'est qu'il n'y avait aucun challenge ; le moins disant de chaque lot donnait une solution valide.

Etape 3 : Je peux explorer tout l'arbre de toutes les possibilités, en coupant toutes les branches, dès que le surcoût atteint ou dépasse le surcoût qu'on a trouvé. J'ai ainsi l'assurance de trouver la solution la moins chère.

Fin de partie · March 2021

Une méthode:

On commence par déterminer un minorant $m$ du coût.
On prend pour chaque immeuble le minimum des prix proposés par chaque postulant et on additionne ces nombres.
On ne se préoccupe pas à cette étape de savoir si un postulant a postulé plus de deux fois.
Le coût à retenir est supérieur ou égal à ce minorant $m$.
Et après on regarde si pour chaque coût $m,m+1,....,M$ il y a une configuration qui est possible.
(on a aussi un majorant $M$)

PS:
Le pas de +1 peut être remplacé me semble-t-il par la différence (en valeur absolue) entre les deux plus petits prix proposés.

gerard0 · March 2021

Effectivement, j'avais mal lu (j'ai lu 3 lots, pourquoi ???). Avec 7 lots, ça peut être effectivement plus pénible.

A noter : la règle 2 est interdite pour les appels d'offre d'institutions publiques en France. Et le non choix du "mieux disant" doit être fortement justifié.

Maaloum · March 2021

Bonjour à tous et merci,

Je veux essayer d’appliquer la réponse de Mr. gerard0, malgré qu’elle est plus pénible, mais comme je veux créer un programme en Visual Basic, il va occuper de la charge des traitements.

Mais j’ai souci encore, j’explique :

En appliquant la réponse de Mr. gerard0

Par exemple Lot 1 / S1: 1000, S2 : 1050; Lot 2 / S1:2000, S3 (*) :2200; 1000+2200>1050+2000, donc on choisit S2 pour le lot 1 et S1 pour le lot 2.

Si j’arrive à donner à S1 le lot2, je retire le S1 et le lot2 entièrement de la base de donnée puis je recommence par la même manière avec les autres Lots et Soumissionnaires jusqu’à qu’il ne reste plus rien. (Est-ce que c’est exact)

soleil_vert · March 2021

Est-ce que tous les lots sont équivalent?
Je veux dire en terrassement, en quantité de béton, en main-d’œuvre...
Si ce n'est pas le cas tu peux commencer par classer les lots par ceux qui couteront le plus cher a priori il y aura moins d'entreprises candidates puis répartir les derniers lots aux entreprises restantes.

Règle de choix 2 : un soumissionnaire n’est peut pas gagner plus d’un lot.

Et que se passe-t-il si une seule entreprisse peut faire deux lots car il faut des compétences spéciales?

Maaloum · March 2021

Malheureusement on juge les offres sur un seul critère (moins disant), oublier toutes les autres paramètres

lourrran · March 2021

Je pense que Maaloum a un travail de programmation à faire et qu'il demande de l'aide pour cet exercice.
Il n'y a pas de vrais cas concrets avec du béton et de la main d'oeuvre derrière toute cette histoire.
Et ce sujet n'a rien à faire dans un sous-forum 'maths et société'.

Maaloum · March 2021

Je suis juste comme vous, j’ai un frère qui m’a posé cette question et comme je suis un programmeur j’essaye de l'aider en lui faisant un programme pas plus que ça.

lourrran · March 2021

Oui, pas de problème Maaloum.
C'est bien comme cela que je l'avais compris.
C'est un problème de programmation, c'est déjà ce que je disais hier, quand je parlais d'algorithme.
Et c'est pour cette raison que j'ai proposé une réponse sous forme d'algorithme.

Maaloum · March 2021

Effectivement Lourrran, mais avant qu’on passe à l’algorithme on devait avoir la solution mathématique.

Rassurer vous que je n'ai rien à cacher, et dès que je termine ce petit programme je vous l’envoie pour faire un test vous-même.