Le problème du régime 181
1945
Stigler résout le problème
du régime selon une
méthode heuristique.
1947
Dantzig formule la méthode
du simplexe et résout
le problème du régime
par la technique de la
programmation linéaire.
1984
Karmarkar conçoit
un nouvel algorithme pour
résoudre les problèmes
de programmation linéaire.
2 × 30 + 3 × 5 = 75 mg de vitamines. Elle procède de même pour les minéraux et
trouve 10 × 30 + 50 × 5 = 550 mg de minéraux.
Puisque son entraîneur a exigé qu’elle prenne au moins 120 mg de vitamines et
880 mg de minéraux, il lui faut remplir son caddie de davantage de boîtes et de
briques. Le problème pour Tanya est de se débrouiller pour calculer les bonnes quantités des deux produits de manière à couvrir ses besoins en vitamines et minéraux.
Elle revient dans le rayon des produits diététiques et ajoute des boîtes et des briques
dans son caddie. Elle a maintenant 40 boîtes et 15 briques. C’est sûrement assez ?
Elle refait ses calculs : elle a 2 × 40 + 3 × 15 = 125 mg de vitamines et 10 × 40 + 50
× 15 = 1 150 mg de minéraux. Tanya respecte maintenant les recommandations de
son entraîneur et a même dépassé les quantités nécessaires.
Des solutions réalisables Cette combinaison (40, 15) de produits diététiques permettra à Tanya de respecter son régime. C’est ce que l’on appelle une
combinaison possible, ou une solution « réalisable ». Nous avons déjà vu que (30, 5)
n’est pas une solution réalisable et il faut donc distinguer entre les deux types de
combinaisons, à savoir, des solutions réalisables où le régime est respecté, et des
solutions non réalisables où il ne l’est pas.
Tanya a beaucoup d’autres possibilités. Elle pourrait remplir son caddie de Solido
uniquement. Dans ce cas, il lui faudrait en acheter au moins 88 boîtes. L’achat (88,
0) respecte les deux exigences, parce que cette combinaison contient 2 × 88 + 3 × 0
= 176 mg de vitamines et 10 × 88 + 50 × 0 = 880 mg de minéraux. Si elle n’achetait
que du Liquex, elle aurait besoin de 40 briques au moins, et la solution réalisable (0,
40) respecte à la fois ses besoins en vitamines et en minéraux, parce que 2 × 0 + 3
× 40 = 120 mg de vitamines et 10 × 0 + 50 × 40 = 2 000 mg de minéraux. On peut
remarquer que la prise de vitamines et de minéraux ne correspond pas exactement
à ce qui est recommandé quelle que soit la combinaison retenue parmi toutes ces
possibilités, mais l’entraîneur aura malgré tout la conviction que Tanya en absorbe
suffisamment.
Solutions optimales L’argent entre maintenant en ligne de compte. Lorsque
Tanya arrive à la caisse, elle doit régler ses achats. Elle remarque que les boîtes et
les briques coûtent 5 € l’unité. Avec les combinaisons réalisables que nous avons
trouvées jusque-là (40, 15), (88, 0) et (0, 40), il lui faudrait respectivement payer
275 €, 440 € et 200 €, et la meilleure solution est par conséquent de ne pas acheter
de Solido mais 40 briques de Liquex. C’est l’achat le moins coûteux qui respecte
ses besoins nutritionnels. Mais la quantité de produits à acheter a été déterminée
de manière hasardeuse. Tanya a essayé instinctivement diverses combinaisons de
Solido et de Liquex, puis elle a calculé le prix de ces seuls cas. Peut-elle mieux faire ?
1945
Stigler résout le problème
du régime selon une
méthode heuristique.
1947
Dantzig formule la méthode
du simplexe et résout
le problème du régime
par la technique de la
programmation linéaire.
1984
Karmarkar conçoit
un nouvel algorithme pour
résoudre les problèmes
de programmation linéaire.
2 × 30 + 3 × 5 = 75 mg de vitamines. Elle procède de même pour les minéraux et
trouve 10 × 30 + 50 × 5 = 550 mg de minéraux.
Puisque son entraîneur a exigé qu’elle prenne au moins 120 mg de vitamines et
880 mg de minéraux, il lui faut remplir son caddie de davantage de boîtes et de
briques. Le problème pour Tanya est de se débrouiller pour calculer les bonnes quantités des deux produits de manière à couvrir ses besoins en vitamines et minéraux.
Elle revient dans le rayon des produits diététiques et ajoute des boîtes et des briques
dans son caddie. Elle a maintenant 40 boîtes et 15 briques. C’est sûrement assez ?
Elle refait ses calculs : elle a 2 × 40 + 3 × 15 = 125 mg de vitamines et 10 × 40 + 50
× 15 = 1 150 mg de minéraux. Tanya respecte maintenant les recommandations de
son entraîneur et a même dépassé les quantités nécessaires.
Des solutions réalisables Cette combinaison (40, 15) de produits diététiques permettra à Tanya de respecter son régime. C’est ce que l’on appelle une
combinaison possible, ou une solution « réalisable ». Nous avons déjà vu que (30, 5)
n’est pas une solution réalisable et il faut donc distinguer entre les deux types de
combinaisons, à savoir, des solutions réalisables où le régime est respecté, et des
solutions non réalisables où il ne l’est pas.
Tanya a beaucoup d’autres possibilités. Elle pourrait remplir son caddie de Solido
uniquement. Dans ce cas, il lui faudrait en acheter au moins 88 boîtes. L’achat (88,
0) respecte les deux exigences, parce que cette combinaison contient 2 × 88 + 3 × 0
= 176 mg de vitamines et 10 × 88 + 50 × 0 = 880 mg de minéraux. Si elle n’achetait
que du Liquex, elle aurait besoin de 40 briques au moins, et la solution réalisable (0,
40) respecte à la fois ses besoins en vitamines et en minéraux, parce que 2 × 0 + 3
× 40 = 120 mg de vitamines et 10 × 0 + 50 × 40 = 2 000 mg de minéraux. On peut
remarquer que la prise de vitamines et de minéraux ne correspond pas exactement
à ce qui est recommandé quelle que soit la combinaison retenue parmi toutes ces
possibilités, mais l’entraîneur aura malgré tout la conviction que Tanya en absorbe
suffisamment.
Solutions optimales L’argent entre maintenant en ligne de compte. Lorsque
Tanya arrive à la caisse, elle doit régler ses achats. Elle remarque que les boîtes et
les briques coûtent 5 € l’unité. Avec les combinaisons réalisables que nous avons
trouvées jusque-là (40, 15), (88, 0) et (0, 40), il lui faudrait respectivement payer
275 €, 440 € et 200 €, et la meilleure solution est par conséquent de ne pas acheter
de Solido mais 40 briques de Liquex. C’est l’achat le moins coûteux qui respecte
ses besoins nutritionnels. Mais la quantité de produits à acheter a été déterminée
de manière hasardeuse. Tanya a essayé instinctivement diverses combinaisons de
Solido et de Liquex, puis elle a calculé le prix de ces seuls cas. Peut-elle mieux faire ?