[optimisation] prix dégressifs!

Bonjour à toutes et à tous,

j'ai un petit problème d'optimisation à vous soumettre, qui parait simple, mais pour lequel je sens des complications...

Dans une ferme au japon on vend des choux soit à l'unité soit par caisse de 10 choux.

- à l'unité les choux coutent un prix C1
- la première caisse de 10 coute un prix C2
- et les caisses de 10 suivantes coutent un prix C3

un client arrive et souhaite acheter une quantité d'au minimum N choux, pour le prix total le moins cher possible!

soit Q1 la quantité de choux à l'unité qu'il faut
soit Q10 la quantité de caisses de 10 qu'il faut

je cherche les valeurs de Q1 et Q10 qui minimisent le cout total en fonction de N.

voici un exemple d'application numérique pour bien situer les niveaux des prix C1 C2 et C3 pour mon problème.

les choux à l'unité coutent C1 = 155 yen
la première caisse de choux est facturée C2 = 940 yen
les caisses de choux suivantes sont facturées C3 = 800 yen

en essayant "à la main" de trouver le meilleur choix, on trouve:

si N = 0, Q1 = 0, Q10 = 0, cout= 0
si N = 1, Q1 = 1, Q10 = 0, cout= 155 (155*1)
si N = 2, Q1 = 2, Q10 = 0, cout= 310 (155*2)
si N = 3, Q1 = 3, Q10 = 0, cout= 465 (155*3)
si N = 4, Q1 = 4, Q10 = 0, cout= 620 (155*4)
si N = 5, Q1 = 5, Q10 = 0, cout= 775 (155*5)
si N = 6, Q1 = 6, Q10 = 0, cout= 930 (155*6)
si N = 7, Q1 = 0, Q10 = 1, cout= 940 (155*0 + 940*1) ici une caisse est mieux
si N = 8, Q1 = 0, Q10 = 1, cout= 940 (155*0 + 940*1) et comme c'est la 1ere
si N = 9, Q1 = 0, Q10 = 1, cout= 940 (155*0 + 940*1) on la paye le prix fort
si N = 10, Q1 = 0, Q10 = 1, cout= 940 (155*0 + 940*1)
si N = 11, Q1 = 1, Q10 = 1, cout= 1095 (155*1 + 940*1)
si N = 12, Q1 = 2, Q10 = 1, cout= 1250 (155*2 + 940*1)
si N = 13, Q1 = 3, Q10 = 1, cout= 1405 (155*3 + 940*1)
si N = 14, Q1 = 4, Q10 = 1, cout= 1560 (155*4 + 940*1)
si N = 15, Q1 = 5, Q10 = 1, cout= 1715 (155*5 + 940*1)
si N = 16, Q1 = 0, Q10 = 2, cout= 1740 (155*0 + 940*1 + 800*1)
si N = 17, Q1 = 0, Q10 = 2, cout= 1740 (155*0 + 940*1 + 800*1)
si N = 18, Q1 = 0, Q10 = 2, cout= 1740 (155*0 + 940*1 + 800*1)
si N = 19, Q1 = 0, Q10 = 2, cout= 1740 (155*0 + 940*1 + 800*1)
si N = 20, Q1 = 0, Q10 = 2, cout= 1740 (155*0 + 940*1 + 800*1)
...
si N = 80, Q1 = 0, Q10 = 8, cout= 6540 (155*0 + 940*1 + 800*7)

etc...

j'essaye de programmer ce comportement en C,
j'ai tout d'abord essayé d'utiliser une résolution à l'aide d'un algo LP en cherchant la combinaison de quantités (à l'unité, la 1ere caisse, les caisses suivantes) qui minimise le cout et qui respecte la contrainte de quantité minimum, mais ça ne fonctionne pas car il y a un lien entre les caisses! en effet on ne peut commander de caisse moins chère que si on a déjà commandé la 1ere caisse chère! bref ça sent l'impossible.

cela dit en regardant les données j'ai identifié deux solutions, celles de la forme Q1*155 et celles de la forme Q1*155 + 940 + (Q10-1)*800
je pourrais calculer les deux et faire un simple min, mais c'est pas top..
j'essaye de voir où cela peut mener...

Toujours est t'il que ce problème doit bien avoir une solution simple et élégante, valable quelle que soient les prix et les quantités dans les caisses, une belle modélisation quoi :-)

Merci d'avance si vous avez des suggestions ^_^

PS: il y avait une erreur j'ai remplacé 115 par 155, merci de me l'avoir signalé. petite dyslexie temporaire ^_^