0% ont trouvé ce document utile (0 vote)
7 vues3 pages

Optimisation de la production et A*

L'exercice 1 traite de la maximisation du bénéfice de la fabrication de chaises et de tables sous certaines contraintes de ressources, aboutissant à un bénéfice maximal de 1000 pièces avec 40 chaises et 20 tables. L'exercice 2 utilise l'algorithme A* pour explorer des nœuds et trouver un chemin admissible, tandis que l'exercice 3 évalue l'admissibilité d'une estimation dans un contexte donné, concluant qu'elle n'est pas admissible. Les résultats sont obtenus à l'aide de méthodes graphiques et algorithmiques.

Transféré par

nabihboy
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
7 vues3 pages

Optimisation de la production et A*

L'exercice 1 traite de la maximisation du bénéfice de la fabrication de chaises et de tables sous certaines contraintes de ressources, aboutissant à un bénéfice maximal de 1000 pièces avec 40 chaises et 20 tables. L'exercice 2 utilise l'algorithme A* pour explorer des nœuds et trouver un chemin admissible, tandis que l'exercice 3 évalue l'admissibilité d'une estimation dans un contexte donné, concluant qu'elle n'est pas admissible. Les résultats sont obtenus à l'aide de méthodes graphiques et algorithmiques.

Transféré par

nabihboy
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Exercice 1 :

Objectif : Maximiser B = 15 * x + 20 * y
Variable de {X : le nombre de chaises à fabriquer
Décision {Y : le nombre de tables à fabriquer

Sous – contraintes
Bois : 2 * x + 5 * y <= 180
Métal : 3 * x + 4 * y <= 200
Heures : 1* x + 2 * y <= 80
X , y >= 0

Donc grâce à géogebra, on peut voir avec le point d’intersection de toutes les droites, on trouve :
X = 40 chaises
Y = 20 tables
Soit un bénéfice de B = 1000 pièces au maximal avec le bénéfice optimal

Sinon sur le site phpsimplex

Maintenant avec le nombre d’heures à 75h : B = 1000 avec x = 50 et y = 12.5


B = 825 avec x = 15 et y = 30

Pour la première, nous allons essayer de maximiser la chose sans avoir des nombres décimaux
B = 995 avec x = 49 et y = 13 et B ~= 1000 avec x = 50,66 et y = 12

On recontinue mais cette fois ci avec x


B = 1000 avec x = 51 et y = 11,75 et B = 990 avec x = 50 et y = 12

On continue avec y
B = 1000 avec x = 52 et y = 11
C’est la bonne solution, on cherche dans la zone réduite des différents x et y.

9.
Objectif : Minimiser H = 1 * x + 2 * y
Sous – contraintes
Bois : 2 * x + 5 * y <= 180
Métal : 3 * x + 4 * y <= 200
Bénéfices : 15 * x + 20 * y >= 1000
X , y >= 0

Grâce au python : nous trouvons x = 64 et y = 2 pour faire un Bénéfice de 1000 soit 68h de travail

Exercice 2 :

A*

Nœuds ouverts Nœuds visités


(Lu,244,Vide)
(Tim,111+329=440,Lu) (Meh,70+241=311,Lu) (Lu,___)
(Tim,111+329,Lu) (Dob,70+75+242=387,Meh) (Meh,___)
(Tim,111+329,Lu) (Cra,70+75+120+160=425,Dob) (Dob,___)(Cra,___)
(Tim,111+329,Lu) (Pi,70+75+120+138+100=503,Cra) (Tim,___)
(Rim,70+75+120+146+193=604,Cra)
(Ara,111+118+366=595,Tim) (Pi,___)
(Pi,70+75+120+138+100=503,Cra)
(Rim,70+75+120+146+193=604,Cra)
(Ara,111+118+366=595,Tim)
(Bu,70+75+120+138+101=504 ,Pi)
(Rim,70+75+120+146+193=604,Cra)

La première solution dans un temps raisonnable :


Lu <- Meh <- Dob <- Cra <- Pi <- Bu

3. Oui elle est admissible car l’estimation est plus petite que la valeur réelle.

Exercice 3

La h2 n’est pas admissible car on peut voir que pour le point C, l’estimation est à 8 alors que la réalité
est de 7.

Common questions

Alimenté par l’IA

Revising the production plan when the hours are reduced shifts both production quantities and resource allocation, influencing profit outcomes. As hours decrease from 80 to 75, different production levels become optimal due to adjusted constraints. Revised strategies identify feasible production setups, like using 52 chairs and 11 tables instead of 40 and 20, to preserve maximum profit within reduced labor conditions, effectively adapting operational methods to new constraints without financial loss .

Constraints on materials like wood and metal are integrated by establishing inequality formulas that ensure resource consumption does not exceed availability. For example, 2x + 5y <= 180 for wood and 3x + 4y <= 200 for metal are constraints ensuring that the total use of these resources by x chairs and y tables does not surpass the stock limits. These constraints shape the feasible solution space, within which the optimal profit condition 15x + 20y is sought, keeping the production plan viable and resource-compliant .

The heuristic h2 is considered non-admissible because it overestimates the actual cost for the point C, where the estimation is 8 and the true value is 7 . This overestimation can lead to suboptimal decisions in pathfinding algorithms like A*, where the algorithm might choose a less efficient path thinking it's optimal due to the inflated cost. Non-admissible heuristics can result in the algorithm missing the least cost path, leading to inefficiencies and potentially incorrect solutions .

Python can be used in optimization through libraries like PuLP or SciPy to model and solve linear programming problems. It systematically explores feasible solutions under constraints and identifies the optimal configuration that satisfies all conditions. For instance, Python computing yielded a solution of producing 64 chairs and 2 tables to fulfill the profit constraint of at least 1000 units with 68 hours of labor, demonstrating efficient allocation and usage of resources to meet economic objectives .

Seeking intersection points of constraints plays a crucial role in finding an optimal solution by identifying the point where different resource limits are met simultaneously. These points represent borderline efficiencies - where both material and labor restrictions are maximized without violation, thus determining the possible combinations of production items that can potentially yield maximum profit. In this scenario, identifying the intersection helped in concluding with 40 chairs and 20 tables as an optimal solution under initial conditions .

Geogebra assists in determining the optimal solution by visually representing and allowing intersection calculation of constraint lines on a graph. It shows how different combinations of variables, such as the number of chairs and tables, meet the constraints. By identifying the intersection points and analyzing feasible regions, it helps in pinpointing the production settings that maximize profit, like achieving the intersection at 40 chairs and 20 tables for a maximum profit of 1000 units .

Avoiding decimal production values is important as production quantities are typically required to be whole numbers in manufacturing settings; fractional values are impractical. This is achieved by tweaking the constraints and production variables to find integer solutions that are close to the optimal profit. For example, rounding results like 50.66 chairs to 51 allows maintaining a near-optimal profit within practical manufacturing limits while still adhering to resource constraints .

To ensure that the benefit constraint is satisfied while minimizing hours, strategic adjustments to production variables are made. By maximizing the more profitable item (chairs) given that each requires less of both labor hours and materials compared to tables, a minimum number of hours can still satisfy the constraint of achieving a benefit of at least 1000. The calculation concludes at producing 64 chairs and 2 tables, utilizing 68 hours exactly, thus meticulously allocating resources to balance minimal work time with necessary output .

Adjusting the maximum available hours affects the optimal production mix by changing the feasible region of the constraints. In the given scenario, when the hours are reduced from 80 to 75, the optimal solution shifts. With 80 hours, the optimal solution involves producing 40 chairs and 20 tables, yielding a maximum profit of 1000 units . However, with 75 hours, to maintain maximum profit of 1000 units, the production is adjusted to 52 chairs and 11 tables. This demonstrates that constraint adjustments, like hours, shift the balance of resources, altering the optimal solution without reducing profit .

The first solution obtained using the A* algorithm, Lu <- Meh <- Dob <- Cra <- Pi <- Bu, is feasible and admissible as the estimation provided by the heuristic is less than the actual cost. This means the heuristic does not overestimate the true cost to reach the goal, ensuring that the path found is optimal. The use of an admissible heuristic guarantees that the solution is not only feasible but optimally efficient as per the path and cost calculations provided .

Vous aimerez peut-être aussi