Partage d'un trésor (Prog linéaire)
Partage d'un trésor (Prog linéaire)
Bonsoir, dans un exo de programmation linéaire(modélisation) dont je vous joins l'énoncé .
On nous demande de modéliser le problème du pirate ayant choisi le remplissage des deux sacs.
Pour la modélisation, j'ai bien compris que l'on veut maximiser le profit et on a comme contrainte le respect de la capacité mais quelle serait la contrainte liée au deuxième pirate : celui qui remplira les deux sacs et cherchera à maximiser le profit de sa part de butin (d'après l'énoncé) ?
Merci de votre aide
On nous demande de modéliser le problème du pirate ayant choisi le remplissage des deux sacs.
Pour la modélisation, j'ai bien compris que l'on veut maximiser le profit et on a comme contrainte le respect de la capacité mais quelle serait la contrainte liée au deuxième pirate : celui qui remplira les deux sacs et cherchera à maximiser le profit de sa part de butin (d'après l'énoncé) ?
Merci de votre aide
Dernière modification par GaussX le 24 juin 2019 00:45, modifié 1 fois.
Re: Partage d'un trésor (Prog linéaire)
Je ne vois pas l’énoncé.
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait)
Re: Partage d'un trésor (Prog linéaire)
j'ai un probleme pour joindre l'énoncé, je l'écris alors: deux pirates trouvent un trésor et pr le partager équitablement ils s'accordent sur une procédure: le premier choisit un remplissage du sac et le second choisit un sac.
Les deux sacs ont une capacité C , les pirates peuvent choisir entre n objets. Chaque objet a un poids ci et un profit pi.
On suppose que chacun des pirates veut maximiser le profit de sa part de butin
Les deux sacs ont une capacité C , les pirates peuvent choisir entre n objets. Chaque objet a un poids ci et un profit pi.
On suppose que chacun des pirates veut maximiser le profit de sa part de butin
Re: Partage d'un trésor (Prog linéaire)
Il faut programmer en quel langage ?
Ça se modélise comment un « remplissage » ?
Celui qui remplit a intérêt à maximiser son gain à lui (correspondant au 2e gain)
Il y a peut-être un autre critère à gérer ?
Le poids total ? La différence entre les 2 gains ??
(s’il s’estime trop lésé ...)
A priori, pour la différence : l’énoncé parle d’ équitabilité. La solution la plus équitable peut ne pas être celle qui maximise...
Le poids total, ou plutôt : la capacité totale, c’est la valeur C.
Ça se modélise comment un « remplissage » ?
Celui qui remplit a intérêt à maximiser son gain à lui (correspondant au 2e gain)
Il y a peut-être un autre critère à gérer ?
Le poids total ? La différence entre les 2 gains ??
(s’il s’estime trop lésé ...)
A priori, pour la différence : l’énoncé parle d’ équitabilité. La solution la plus équitable peut ne pas être celle qui maximise...
Le poids total, ou plutôt : la capacité totale, c’est la valeur C.
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait)
Re: Partage d'un trésor (Prog linéaire)
Chaipas de loin comme ça je dirais que pour le premier pirate (celui qui fait le partage) le problème s'écrit
$$ \min_{p | p \cup {p}^{\mathsf{c}} = T} \bigg\{ \max \Big\{ \sum_{t \in p} t , \sum_{t \in {p}^{\mathsf{c}}} t \Big\} \bigg\} $$
avec p et p^c qui forment une partition du trésor T. Ta question est un peu curieuse, la seule contrainte du deuxième pirate consiste à choisir parmi les deux sous-ensembles qu'on lui propose (d'où le max).
$$ \min_{p | p \cup {p}^{\mathsf{c}} = T} \bigg\{ \max \Big\{ \sum_{t \in p} t , \sum_{t \in {p}^{\mathsf{c}}} t \Big\} \bigg\} $$
avec p et p^c qui forment une partition du trésor T. Ta question est un peu curieuse, la seule contrainte du deuxième pirate consiste à choisir parmi les deux sous-ensembles qu'on lui propose (d'où le max).
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or
Re: programmation linéaire ?
Je ne connaissais pas le terme,
pour la raison suivante :
Optimisation linéaire :
- L’optimisation linéaire (OL) est également désignée par le nom de programmation linéaire
mais cette appellation tend à être abandonnée,
à cause de la confusion possible avec la notion de programmation informatique.
https://fr.wikipedia.org/wiki/Optimisat ... %C3%A9aire
pour la raison suivante :
Optimisation linéaire :
- L’optimisation linéaire (OL) est également désignée par le nom de programmation linéaire
mais cette appellation tend à être abandonnée,
à cause de la confusion possible avec la notion de programmation informatique.
https://fr.wikipedia.org/wiki/Optimisat ... %C3%A9aire
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait)
Re: programmation linéaire ?
.U46406 a écrit : ↑24 juin 2019 22:27Je ne connaissais pas le terme,
pour la raison suivante :
Optimisation linéaire :
- L’optimisation linéaire (OL) est également désignée par le nom de programmation linéaire
mais cette appellation tend à être abandonnée,
à cause de la confusion possible avec la notion de programmation informatique.
https://fr.wikipedia.org/wiki/Optimisat ... %C3%A9aire
Re: Partage d'un trésor (Prog linéaire)
Bonjour,
J'imagine que tu as aussi une contrainte sur le poids maximum autorisé dans un sac donné. De toute façon, dans ces cas là, tu devrais plutôt te tourner vers de la programmation linéaire en nombres entiers (plus dur que la programmation linéaire standard).
J'imagine que tu as aussi une contrainte sur le poids maximum autorisé dans un sac donné. De toute façon, dans ces cas là, tu devrais plutôt te tourner vers de la programmation linéaire en nombres entiers (plus dur que la programmation linéaire standard).
Re: Partage d'un trésor (Prog linéaire)
Les sacs sont de capacité C et chaque objet i a un poids ci, il faut juste ajouter la contrainte sur les poids des objets dans chaque sacDer RHDJ a écrit : ↑24 juin 2019 14:09Chaipas de loin comme ça je dirais que pour le premier pirate (celui qui fait le partage) le problème s'écrit
$$ \min_{p | p \cup {p}^{\mathsf{c}} = T} \bigg\{ \max \Big\{ \sum_{t \in p} t , \sum_{t \in {p}^{\mathsf{c}}} t \Big\} \bigg\} $$
avec p et p^c qui forment une partition du trésor T. Ta question est un peu curieuse, la seule contrainte du deuxième pirate consiste à choisir parmi les deux sous-ensembles qu'on lui propose (d'où le max).
The Axiom of Choice is obviously true, the Well-Ordering Principle is obviously false, and nobody knows about Zorn's Lemma. - Jerry Bona