Pourquoi les nombres entiers compliquent-ils tout ?
Un programme en nombres entiers est un programme linéaire dont certaines variables doivent être entières. Par exemple, on prend un colis ou on ne le prend pas.
Ce détail le rend bien plus difficile à résoudre. Vous saurez pourquoi arrondir ne marche pas, puis vous résoudrez un sac à dos par programmation dynamique.
À la fin de cette leçon
Remarque
Je peux expliquer pourquoi arrondir ne résout pas un problème en nombres entiers.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Variable entière | une variable qui ne peut prendre que des valeurs entières | 0 ou 1 |
| Sac à dos | un problème : choisir des objets de valeur maximale sans dépasser une charge | |
| Relâchement | le même problème où les fractions sont permises | |
| Programmation dynamique | résoudre de petits cas d’abord et s’en servir pour les grands | |
| Glouton | une méthode qui choisit le meilleur coup du moment, sans revenir en arrière |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On ne coupe pas un colis
Une camionnette de livraison porte au plus 10 kg. Quatre colis attendent : on les prend entiers ou pas du tout.
Le tableau donne le poids et la valeur de chacun. Il faut choisir les colis de plus grande valeur totale sans dépasser 10 kg. C’est un problème de sac à dos.
Exemple travaillé : les quatre colis
| Colis | Poids en kg | Valeur en euros | Valeur par kilo |
|---|---|---|---|
| 1 | 6 | 30 | 5 |
| 2 | 3 | 14 | 4,67 |
| 3 | 4 | 16 | 4 |
| 4 | 2 | 9 | 4,5 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Choisir d’abord le meilleur rapport ne suffit pas
Une idée naturelle : prendre d’abord les colis qui valent le plus par kilo. Le colis 1 (5 euros par kilo) entre, puis le colis 2. Il reste 1 kg : plus rien n’entre.
Le total est 30 + 14 = 44 euros. Pourtant les colis 1 et 3 pèsent 10 kg et valent 46 euros. La méthode gloutonne s’est trompée.
Résoudre le sac à dos avec des fractions
docker exec jupyter python3 -c "from scipy.optimize import linprog; res = linprog([-30, -14, -16, -9], A_ub=[[6, 3, 4, 2]], b_ub=[10], bounds=(0, 1)); print([round(v, 2) for v in res.x], round(-res.fun, 2))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le relâchement permet des morceaux de colis
La commande autorise des fractions entre 0 et 1 pour chaque colis. Elle affiche [1.0, 1.0, 0.0, 0.5] 48.5 : on prend les colis 1 et 2 en entier et la moitié du colis 4.
Ce plan vaut 48,5 euros, plus que le vrai meilleur de 46. Mais on ne coupe pas un colis : le relâchement donne seulement une borne.
Exiger des colis entiers
docker exec jupyter python3 -c "from scipy.optimize import linprog; res = linprog([-30, -14, -16, -9], A_ub=[[6, 3, 4, 2]], b_ub=[10], bounds=(0, 1), integrality=[1, 1, 1, 1]); print([round(v) for v in res.x], round(-res.fun))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
La programmation dynamique remplit un tableau
Au lieu d’essayer tous les choix, on note la meilleure valeur pour chaque charge de 0 à 10 kg. On ajoute les colis un par un.
Prenons un colis de poids p et de valeur v. Pour la charge c, on garde le plus grand de deux nombres. Le premier est l’ancienne valeur. Le second est la valeur de la charge c moins p, plus v.
Exemple travaillé : le tableau après chaque colis
| Charge | Après colis 1 | Après colis 2 | Après colis 3 | Après colis 4 |
|---|---|---|---|---|
| 2 kg | 0 | 0 | 0 | 9 |
| 3 kg | 0 | 14 | 14 | 14 |
| 5 kg | 0 | 14 | 16 | 23 |
| 6 kg | 30 | 30 | 30 | 30 |
| 8 kg | 30 | 30 | 30 | 39 |
| 9 kg | 30 | 44 | 44 | 44 |
| 10 kg | 30 | 44 | 46 | 46 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Remplir le tableau avec Python
# Le meilleur chargement par programmation dynamique.
poids = [6, 3, 4, 2]
valeurs = [30, 14, 16, 9]
capacite = 10
# meilleur[c] : la meilleure valeur avec une capacité de c kilos.
meilleur = [0] * (capacite + 1)
for i in range(len(poids)):
# On descend pour ne prendre chaque colis qu'une fois.
for c in range(capacite, poids[i] - 1, -1):
avec = meilleur[c - poids[i]] + valeurs[i]
if avec > meilleur[c]:
meilleur[c] = avec
print("après le colis", i + 1, meilleur)
print("meilleure valeur", meilleur[capacite])
Compter les choix possibles
docker exec jupyter python3 -c "print(2 ** 10, 2 ** 20, 2 ** 40)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pourquoi les problèmes entiers restent durs
Avec n colis, il y a 2 puissance n façons de choisir. La commande donne 1 024 pour 10 colis, plus d’un million pour 20 et plus de mille milliards pour 40.
Le tableau, lui, a seulement n fois la charge cases. Mais si la charge elle-même est énorme, le tableau l’est aussi.
Une erreur fréquente
Attention
Beaucoup pensent qu’il suffit de résoudre avec des fractions, puis d’arrondir. Ici, arrondir donne 44 euros, alors que le meilleur plan entier vaut 46. Un arrondi peut même dépasser la charge ou rater le meilleur plan.
Pour aller plus loin
Dans votre carnet, changez la charge de la camionnette de 10 à 9 kg dans le code du tableau. Lisez la nouvelle meilleure valeur.
Dites quels colis sont pris et si le relâchement aurait donné le même plan.