Programmation dynamique linéaire multi-période avec différentes dépendances et changements dans la période
Je ne sais pas si je formule cela correctement, mais en un mot, mon problème est:
Je modélise les actions potentielles qu'un propriétaire de bateau peut faire à son bateau. Disons qu'il veut savoir sur la durée de vie de 50 ans du bateau, quelle est la manière la moins chère d'entretenir la peinture extérieure.
Il a trois options:
Option 1: première peinture au coût de 1 M $ / bateau. Dans le cadre de cette option, il est suggéré (pas obligatoire) de refaire la peinture dans les 5 ans suivant le travail de peinture précédent pour le reste de la vie du bateau.
Option 2: Si le bateau n'a pas été peint au cours des 7 dernières années, il se détériore à un point tel qu'il nécessite des réparations plus importantes à 1,4 M $. Cela comprendra les réparations et la peinture sans frais supplémentaires.
Option 3: si le bateau n'a pas été peint pendant plus de 10 ans consécutifs, certains éléments devraient être remplacés pour un coût total de \ 1,6 M $ / bateau. Dans le cadre de cette option, il doit également peindre un an après la réparation de l'option 3 au même coût additionnel de 1 M $ / bateau.
Par souci d'argumentation et plus de contraintes:
- La superficie du bateau est de 400 m2. (Les coûts doivent être divisés par ce nombre pour obtenir le coût par m2)
- Le bateau a été entièrement peint il y a 2 ans, donc aucune peinture n'est requise sur le bateau jusqu'à la période> = 3.
- Surface de réparation minimale = 25 m2
Avec un budget maximum de \$200K/year for the first 6 years and a max budget of \$300K / an après, combien devrait-il faire à partir des options 1, 2 et 3 pour maximiser la condition (zone peinte)?
Notez que je voudrais exécuter cela à la fois comme une minimisation du coût et une maximisation des modèles séparés de condition.
J'ai du mal à créer les contraintes de ce modèle, en particulier la variable d'interaction sur la façon de construire les multiples contraintes / variables et de les résumer en résultats.
MODIFIER :
La solution doit pouvoir s'adapter quelque peu aux nbateaux, aux ioptions et aux mpropriétaires.
MODIFIER :
Au départ, je n'ai pas inclus la courbe de détérioration, mais il y en a une. Je pense que par souci de simplicité, nous pouvons supposer que la détérioration se produit à un taux constant de 3% par an et l'une des contraintes est de s'assurer que pas plus de 10% sont en état de détérioration.
De plus, à l'option 1, renvoie la section réparée à un taux de condition de 90%, l'option 2 à 95% et l'option 3 à 100%.
Réponses
Avertissement: il s'agit plus d'un indice qu'une réponse complète.
Vous pouvez utiliser le modèle suivant comme point de départ pour créer votre propre modèle. J'ignore deux éléments:
- Contrainte de l'option 3:
Dans le cadre de cette option, il doit également peindre un an après la réparation de l'option 3 au même coût additionnel de 1 M $ / bateau.
- Contraintes de surface
Vous devrez modifier ce qui suit pour prendre en compte les contraintes ci-dessus.
Cette relaxation de votre problème peut être résolue comme un problème de chemin le plus court dans le graphe acyclique dirigé suivant:
Définissez un nœud par an, de 0 $ à 50 $ . Ensuite, définissez une arête de $ i $ à $ j $ , $ i <j $ , s'il est possible pour le propriétaire de faire un peu de maintenance les années $ i $ et $ j $ , et rien les années $ i + 1, i +2, ..., j-1 $ .
La fonction de coût sur ces arêtes est définie selon les options $ 3 $ . Ainsi par exemple, entre les nœuds $ i $ et $ i + 1, i + 2, i + 3, i + 4, i + 5 $ , le coût est de 1 $ M dollars (option 1). Entre les nœuds $ i $ et $ i + 7, i + 8, i + 9 $ , c'est 1,4 M $ de dollars (option 2). Et entre les nœuds $ i $ et $ i + 10 $ , c'est 1,6 $ M $ (option 3).
Si le budget maximum n'est pas satisfait, ne créez pas les arêtes correspondantes.
Le chemin le plus court entre le nœud 1 $ et 50 $ détermine la stratégie de maintenance la moins chère pour le propriétaire du bateau.
MODIFIER N ° 1
Le fait que ce qui précède soit le problème du chemin le plus court indique que le problème pourrait probablement être résolu avec la programmation dynamique. Quoi qu'il en soit, une façon de résoudre le problème est de considérer les «états». Un état $ (t, s) $ est défini par deux paramètres: $ t \ in \ {1, ..., 50 \} $ et $ s \ in \ {0,1,2, ..., 400 \ } $ . $ t $ désigne l'année et $ s $ la surface non peinte de l'année $ t $ . Dans la réponse ci-dessus, les surfaces partielles ont été ignorées, donc tous les sommets correspondent aux états $ (t, 0) $ .
Une fois que vous avez défini ces états, créez une grille où les nœuds représentent tous les états possibles. Et créez une arête (orientée) $ (i, j) $ entre deux sommets $ i = (t_i, s_i) $ , $ j = (t_j, s_j) $ si ce qui suit est vrai :
- $ t_j> t_i $ ,
- $ (i, j) $ est une transition faisable en termes de budget,
- $ (i, j) $ est une transition possible en termes de stratégie de peinture
Créez également un nœud source et liez-le à tous les sommets (si possible) et à un nœud récepteur, auquel tous les sommets sont liés (si possible). Une fois que vous avez tous les bords, ajoutez le coût correspondant. Par exemple, sur le bord $ (i, j) $ , si $ s_j> s_i $ , cela signifie que vous ne faites rien, et donc le coût est de 0 $ . Si $ s_j \ le s_i $ , cela signifie que vous peignez $ s_i - s_j - A_ {ij} $ $ m ^ 2 $ , où $ A_ {ij} $ désigne la surface détériorée entre $ t_j $ et $ t_i $ , à un coût qui dépend de l'option ( 1,2,3 $ ) que vous utilisez (et ainsi de la longueur du bord $ (i, j) $ ).
Une fois que vous avez défini un tel graphe orienté. Un chemin du nœud source au nœud récepteur définit une stratégie de maintenance et le chemin le plus court définit la meilleure stratégie (la moins chère).
La contrainte de l'option 3:
Dans le cadre de cette option, il doit également peindre un an après la réparation de l'option 3 au même coût additionnel de 1 M $ / bateau.
doit être adressé (je pense) avec la programmation entière. Vous devrez formuler le problème de chemin le plus court comme un MIP (facile), et ajouter des contraintes et des variables supplémentaires pour prendre en compte le fait que si vous utilisez une arête correspondant à un$10$ transition d'année, alors vous devez utiliser une arête correspondant à un $1$ transition d’année l’année suivante.