Optimisation lineaire

[Zlato]

Bonjour, j'ai un devoir d’optimisation linéaire dont je ne trouve pas la solution. Je voudrais savoir si des personnes pouvaient m'aider ou ont des pistes. Merci

[fatal_error]

hi

une modelisation parmi d'autres, je l'ai pas réfléchi outre mesure:
tu poses x_i le plat i variable booléenne
tu minimises la somme des x_i

tu imposes des contraintes sur les x_i:
x_1 + x_8 = 1 // une entrée
x_2 + x_6 + x_7 = 1 // un dessert
guess what pour plat
guess what pour kcal

[Zlato]

Merci pour ta réponse, pourrait tu m'expliquer pourquoi tu as mis =1 pour les contraintes?
C'est pour dire par exemple qu'il faut qu'un seul plat ?
Par la même occasion pour les contraintes sur les Kcal j'ai du mal à voir comment faire instinctivement j'aurai fais x_1+x_4+x_2<= 1250. Mais on sait déjà que c'est le cas.
Je n'arrive pas à déterminer une inéquation generale pour la contraintes des Kcal

[fatal_error]

re,
> C'est pour dire par exemple qu'il faut qu'un seul plat
oui

> x_1+x_4+x_2<= 1250
non

tu manipules des cal donc sommer des variables qui valent 0 ou 1 et comparer à 1250 (des cal) n'a pas de sens
par ailleurs tu peux effectivement ecrire
x_1 * 180 + x_4 * 660 + x_2 * 240 <= 1250
mais faudrait ecrire les inéquations pour toutes les solutions possibles du coup bon...
on peut être plus bourrin (en remarquant qu'il y a pas de cal négative):
1000 <= x_1 * 180 + x_2 * 240 + ... + x_9 * 750 <= 1250

[Zlato]

Super, merci beaucoup pour ton aide je pense avoir bien compris
Il faudrait pas minimiser la somme des prix des plats en faisant min 7*x_1+...+15*x_9 ?
avec x_i=1 ou x_i=0
Car on cherche le menu le plus bon marché (si je comprend le moins cher)
Même si ce n'est pas très important

[fatal_error]

oui tu as raison, nieme brain fart de ma part

[Sylviel]

Et il manque la contrainte 2&9 pas en simultané. Je te laisse faire une proposition.

P.S: ce n'est pas de l'optimisation linéaire par contre, mais linéaire en nombre entier .

[Zlato]

Oui, c'est vrai j'aurai dis x_2+x_9<=1.
Comme ça il y'a soit l'un soit l'autre ou aucun
peut être rajouter x_2+x_9>0 mais je ne pense pas que ce soit nécessaire car les x_i sont soit 0 soit 1.

P.S: En effet . Comme je ne savais pas comment commencer je ne savais pas que ça allait être que des entiers

[Sylviel]

Il ne faut certainement pas ajouter x2 + x9> 0, car, étant entier, cela entrainerait qu'il faut choisir exactement l'un des deux.

[Zlato]

Ah oui c'est vrai je voulais mettre >=0. Mais dans tout les cas il n'est pas nécessaire car on aura jamais de valeur <0.

En tout cas merci beaucoup pour votre aide à vous deux.