Regardons la programmation linéaire dans Excel en utilisant l'exemple d'un problème précédemment résolu.
Tâche. Nikolai Kuznetsov dirige une petite usine mécanique. Le mois prochain, il prévoit de fabriquer deux produits (A et B), pour lesquels le bénéfice marginal spécifique est estimé respectivement à 2 500 et 3 500 roubles. La fabrication des deux produits nécessite un usinage, des matières premières et des coûts de main-d’œuvre. Chaque unité de produit A nécessite 3 heures d'usinage, 16 unités de matières premières et 6 unités de main-d'œuvre pour être produite. Les exigences unitaires correspondantes pour le produit B sont 10, 4 et 6. Nicholas prédit que le mois prochain, il pourra fournir 330 heures d'usinage, 400 unités de matières premières et 240 unités de main-d'œuvre. Technologie processus de production est tel qu’au moins 12 unités du produit B doivent être produites au cours d’un mois donné. Il faut déterminer le nombre d'unités de produits A et B que Nikolay doit produire au cours du mois suivant pour maximiser la marge de contribution.
Téléchargez la note au format, exemple au format
1. Utilisons le modèle mathématique construit. Voici le modèle :
Maximiser : Z = 2500 * x 1 + 3500 * x 2
À condition que : 3 * x 1 + 10 * x 2 ≤ 330
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
2. Créons un formulaire d'écran et y saisissons les données initiales (Fig. 1).
Riz. 1. Formulaire d'écran de saisie des données de tâche programmation linéaire
Faites attention à la formule dans la cellule C7. C'est la formule fonction objectif. De même, les formules permettant de calculer le côté gauche des restrictions sont saisies dans les cellules C16:C18.
3. Vérifiez si le module complémentaire « Rechercher une solution » est installé (Fig. 2), ignorez ce point.
Riz. 2. Le module complémentaire Recherche de solution est installé ; Onglet Données, groupe Analyse
Si vous ne trouvez pas le complément « Rechercher une solution » sur le ruban Excel, cliquez sur le bouton Microsoft Office, et puis Options Excel(Fig. 3).
Riz. 3. Options Excel
Sélectionnez la ligne Modules complémentaires, puis tout en bas de la fenêtre Gérer les modules complémentaires Microsoft Excel» sélectionnez « Go » (Fig. 4).
Riz. 4. Compléments Excel
Dans la fenêtre « Modules complémentaires », cochez la case « Rechercher une solution » et cliquez sur OK (Fig. 5). (Si Solver n'est pas répertorié dans le champ Modules complémentaires, cliquez sur Parcourir pour rechercher le complément. Si vous recevez un message indiquant que le complément Solver n'est pas installé sur votre ordinateur, cliquez sur Oui pour l'installer.)
Riz. 5. Activation du module complémentaire « Rechercher une solution »
Après avoir chargé le complément de recherche d'une solution, la commande Rechercher une solution devient disponible dans le groupe Analyse de l'onglet Données (Fig. 2).
4. L'étape suivante consiste à remplir la fenêtre Excel « Rechercher une solution » (Fig. 6)
Riz. 6. Remplir la fenêtre « Rechercher une solution »
Dans le champ « Définir la cellule cible », sélectionnez la cellule avec la valeur de la fonction cible – 7 $C$. Nous choisissons de maximiser ou de minimiser la fonction objectif. Dans le champ « Modification des cellules », sélectionnez les cellules avec les valeurs des variables souhaitées $C$4 :$D$4 (à condition qu'elles contiennent des zéros ou soient vides). Dans la zone « Contraintes », à l'aide du bouton « Ajouter », nous plaçons toutes les restrictions de notre modèle. Cliquez sur « Exécuter ». Dans la fenêtre « Résultat de la recherche de solution » qui apparaît, sélectionnez les trois types de rapport (Fig. 7) et cliquez sur OK. Ces rapports sont nécessaires pour analyser la solution résultante. Vous pouvez en savoir plus sur les données présentées dans les rapports.
Riz. 7. Sélection des types de rapports
Les valeurs de la fonction objectif maximisée figuraient sur la feuille principale - 130 000 roubles. et paramètres variables x 1 = 10 et x 2 = 30. Ainsi, pour maximiser le revenu marginal, Nicolas devrait produire 10 unités du produit A et 30 unités du produit B le mois prochain.
Si quelque chose d'autre apparaît à la place de la fenêtre « Résultat de la recherche de solution », Excel n'a pas pu trouver de solution. Vérifiez que la fenêtre « Rechercher une solution » est correctement remplie. Et encore un petit truc. Essayez de réduire la précision de la recherche de solution. Pour cela, dans la fenêtre « Rechercher une solution », cliquez sur Paramètres (Fig. 8.) et augmentez l'erreur de calcul, par exemple, à 0,001. Parfois parce que haute précision Excel n'a pas le temps de trouver une solution en 100 itérations. Vous pouvez en savoir plus sur les paramètres permettant de trouver une solution.
Riz. 8. Augmentation de l'erreur de calcul
Travail de laboratoire "Utilisation du Solution Finder"
Exercice:
Résoudre enExcellertous les problèmes ci-dessous (chacun sur une feuille séparée) et enregistrez les solutions dans un fichierLAB4.xlssur votre disque utilisateur.
Problème 1 1
Résoudre un problème de programmation linéaire à l'aide d'EXCEL. 2
Problème 2 4
Problème de planification de la production de peinture 4
Problème 3 5
Résoudre un problème de transport à l'aide de l'outil Solution Finder 5
Problème 1
Problème d'allocation des ressources.
Si la finance, l'équipement, les matières premières et même les personnes sont considérées comme des ressources, alors un nombre important de problèmes économiques peuvent être considérés comme des problèmes d'allocation des ressources. Très souvent, le modèle mathématique de tels problèmes est un problème de programmation linéaire.
Par exemple:
Il faut déterminer en quelle quantité il faut fabriquer des produits de quatre types Prod1, Prod2, Prod3, Prod4, dont la production nécessite trois types de ressources : main d'œuvre, matières premières, finance. La quantité de chaque type de ressource nécessaire pour produire une unité de production de ce genre, est appelé taux de consommation. Les taux de consommation, ainsi que le bénéfice tiré de la vente d'une unité de chaque type de produit, sont donnés ci-dessous. Créons un modèle mathématique, pour lequel nous introduisons la notation suivante :
Xj- quantité de produits fabriqués jth comme, j=1,4;
bje - quantité de ressource disponible je-ième gentil, je = 1,3;
unje- taux de consommation je-ième ressource pour produire une unité de production jth taper;
cj- bénéfice tiré de la vente d'une unité de production jth taper.
Commençons maintenant à construire le modèle.
Pour produire une unité du Produit 1, 6 unités de matières premières sont nécessaires, ce qui signifie que pour produire tous les produits du Produit 1, 6 sont nécessaires X 1 unités de matières premières, où X 1 - quantité de produits fabriqués Suite1. Compte tenu du fait que pour d'autres types de produits les dépendances sont similaires, la limitation des matières premières ressemblera à :
6x 1 +5x 2 +4x 3
Dans cette contrainte, le membre de gauche est égal à la quantité nécessaire ressource, et celui de droite montre la quantité disponible Ressource. De même, vous pouvez créer des restrictions pour d'autres ressources et écrire une dépendance pour la fonction cible. Le modèle mathématique du problème ressemblera alors à :
F=60x 1 +70x 2 +120x 3 +130x 4 -->maximum
X 1 +x 2 +x 3 +x 4
6x 1 +5x 2 +4x 3 +3x 4
4x 1 +6x 2 +10x 3 +13x 4
Xj>=0 ; j=1,4
Résoudre un problème de programmation linéaire à l'aide d'EXCEL.
1
. Rendre la cellule F6 active.
2. Assistant de fonction Mathématique SOMME PRODUIT sur appuie sur le bouton Plus loin. Boîte de dialogue à l'écran
3. Entrez les dépendances pour les côtés gauches des contraintes.
Travailler dans la boîte de dialogue Rechercher une solution.
1
. Service, Trouver une solution...
2 . Curseur dans le champ Définir la cellule cible et entrez l'adresse F6.
3 . Saisissez la direction de la fonction objectif : Valeur maximum.
4 . Curseur dans le champ Changer de cellule et entrez les adresses B3:E3
5. Cliquez sur le boutonAjouter... EtV saisir les conditions aux limites sur les variables
6. Après avoir entré les restrictions, cliquez sur le boutonExécuter . À la suite des calculs dans les cellules B3 : E3, les valeurs numériques x trouvées seront reflétéesje, et dans la cellule F6 – la valeur de la fonction objectif.
QUE, il est clair que dans solution optimale Cont1=B3=10, Cont2=C3=0, Cont3=D3=6, Cont4=E3=0.
Dans ce cas, le profit maximum sera de F6=1320, la quantité de ressources utilisées sera de travail=F9=16, de matières premières=F10=84, de finance=F11=100.
Utilisation de la boîte de dialogue Le résultat de la recherche d’une solution. Solution trouvée Vous pouvez obtenir trois types de rapports : résultats, durabilité, limites.
Problème 2
Problème de planification de la production de peinture
Pour la production de peinture pour l'extérieur Et travaux intérieurs On utilise deux produits initiaux A et B. Les approvisionnements journaliers maximum possibles de ces produits sont respectivement de 6 et 8 tonnes.
Demande quotidienne de peinture Pour travaux intérieurs ne dépasse jamais la demande de peinture pour usage extérieur plus de 1t.
Demande de peinture pour travaux intérieurs ne dépasse pas 2t. par jour.
Les prix de gros pour une tonne de peintures sont de : 3 000 roubles. pour la peinture pour usage extérieur et 2000 roubles. pour la peinture pour travaux intérieurs .
Quelle quantité de chaque type de peinture faut-il produire pour maximiser les revenus des ventes ?
Dépenses des produits A et B par 1t. sont donnés dans le tableau :
|
produit original |
consommation de matières premières par tonne de peinture |
stock maximum possible |
|
|
pour travaux intérieurs |
pour travaux extérieurs |
||
x 1 - volume de production quotidien de peinture pour travaux intérieurs
x 2 - volume de production quotidien de peinture pour usage extérieur
f - bénéfice quotidien total de la production des deux types de peintures (fonction objectif)
f = 3000x1 +2000x2
Déterminer à quelles valeurs admissibles x 1 et x 2 la valeur de f est le maximum
Restrictions :
Résoudre le problème dans Excel
|
Variables |
|||
|
Fonction objectif : |
3000*A3+2000*B3 |
||
|
Restrictions |
|||
Courir: Service, Recherche d'une solution
Cellule cible C4
Installer: M valeur maximum
Cellules modifiables : A3:B3
Restrictions :
Après avoir saisi les données, cliquez sur le bouton Exécuter
La solution résultante :
|
Variables |
|||
|
Fonction objectif : |
|||
|
Restrictions : |
|||
Conclusion : la production optimale est de 3,3 tonnes de peinture pour les travaux extérieurs et de 1,3 tonnes de peinture pour les travaux intérieurs par jour. Ce volume rapportera un bénéfice de 12,7 mille roubles.
Problème 3
Résoudre un problème de transport à l'aide de l'outil Trouver une solution
L'entreprise dispose de quatre usines : A, B, C, D et de cinq centres de distribution pour ses marchandises : n° 1, n° 2, n° 3, n° 4, n° 5.
Les capacités de production des usines sont respectivement :
A – 200, B – 150, C – 225, D – 175 unités de production par jour.
Les besoins des centres de distribution sont donc :
N° 1 – 100, N° 2 – 200, N° 3 – 50, N° 4 – 250, N° 5 – 150 unités de produit par jour.
Il en coûte 0,75 $ par jour pour stocker une unité de produit dans une usine qui n'est pas livrée à un centre de distribution.
La pénalité de retard de livraison pour un produit commandé par un consommateur dans un centre de distribution mais qui ne s'y trouve pas est de 2,50 $ par jour.
Le coût de transport d'une unité de produit des usines aux points de distribution est présenté dans le tableau :
Planifiez le transport de manière à minimiser les coûts totaux de transport.
Le modèle du problème considéré est équilibré (le volume total des produits fabriqués est égal au volume total des besoins), ce qui signifie qu'il n'est pas nécessaire de prendre en compte les coûts associés à la fois à l'entreposage et aux courtes livraisons de produits. Sinon, vous devez entrer dans le modèle :
En cas de surproduction, un point de distribution fictif, le coût de transport d'une unité de produit, supposé égal au coût d'entreposage, et le volume de transport est égal au volume de stockage des produits excédentaires dans les usines.
En cas de pénurie, une usine fictive, dont le coût de transport d'une unité de produit est supposé être égal au coût des amendes pour déficit de production, et le volume de transport est égal au volume des déficits de produits à points de distribution.
X je– volume de trafic de je-ième usines dans j-ième Centre de distribution.
c je– le coût du transport d’une unité de produit depuis je-ième usines dans j-ième Centre de distribution.
UN je– volume de production par je-ième usine.
V j– la demande en j-m Centre de distribution.
T 
il est nécessaire de minimiser les coûts totaux de transport, c'est-à-dire
Restrictions :
X
je
0 , je
, j
Le mécanisme pour résoudre un problème dans Excel à l'aide de l'outilTrouver une solution
Entrez les frais d'expédition dans les cellules A1:E4.
A6:E9 – attribuer aux valeurs des inconnues (volumes de transport).
Dans les cellules G6:G9, entrez les volumes de production de l'usine.
B A11:E11 – demande de produits aux points de distribution.
Dans la cellule F10 - entrez la fonction objectif
Dans A10:E10 – saisissez les formules qui déterminent le volume de produits importés vers les centres de distribution
En F6 : F9 - formules qui calculent le volume de produits exportés des usines.
|
SOMME(A6:E6) |
|||||||
|
SOMME(A7:E7) |
|||||||
|
SOMME(A8:E8) |
|||||||
|
SOMME(A9:E9) |
|||||||
|
SOMME(A6:A9) |
SOMME(B6:B9) |
SOMME(C6:C9) |
SOMME(D6:D9) |
SOMME(E6:E9) |
SOMME PRODUIT(A1:E4;A6:E9) |
||
Service Trouver une solution
Dans la boîte de dialogue Rechercher une solution :
Définir la cellule cible $F$10
Égal à mi n valeur minimum
Changement de cellule : 6 $A$ : 9$E$
Restrictions :
10$A$ : 10$E$=11$A$:11$E$
$A$6 :$E$9>=0
$F$6 :$F$9=$G$6 :$G$9
Cliquez sur le bouton Possibilités… et cochez la case Modèle linéaire
Cliquez sur le bouton Exécuter
La solution optimale au problème du transport se reflétera dans la gamme A6:E9
Résolvez vous-même le problème de transport en utilisant le mécanisme décrit ci-dessus.
|
Excel requis : ... Problèmes de programmation linéaire. Méthode graphique pour résoudre des problèmes de programmation linéaireSolutionMicrosoft Exceller. Solution Tâches convexe la programmationà aide linéaire approximations. Approximatif solution Tâches mathématique la programmation méthode séparable la programmation. Économique Tâches, résolu avec Avec de l'aide ... Instructions d'utilisation de Microsoft Excel pour résoudre les problèmes LP 5 3 Problèmes LP à index unique 6 > 3 Saisie des données initiales 6 > 3 Résolution du problème 13Instructions1. TRAVAUX DE LABORATOIRE N°1 » SOLUTION TÂCHES LINÉAIRE LA PROGRAMMATION AVEC UTILISER Microsoft Exceller" 1.1. OBJECTIF DU TRAVAIL Acquisition de compétences solutions Tâches linéaire la programmation(LP) dans le tableau... Quelques concepts de programmation linéaireDocumentNous allons apporter solution ce Tâches Avec Avec de l'aide Programmes Tora. regardons la mise en œuvre Tâches linéaire la programmation V.... Tâches Avec Avec de l'aide Microsoft Exceller. 1. Nous entrons les données dans le tableau Exceller(Fig. 1). Riz. 1. Remplir la fiche pour solutions Tâches ... |
Prenons un exemple de problème de programmation linéaire.
Il est nécessaire de déterminer en quelle quantité il est nécessaire de fabriquer des produits de quatre types Prod1, Prod2, Prod3, Prod4, dont la production nécessite trois types de ressources : la main d'œuvre, les matières premières et la finance. La quantité de chaque type de ressource nécessaire pour produire une unité de produit d'un type donné est appelée taux de consommation. Les taux de consommation, ainsi que les bénéfices tirés de la vente d'une unité de chaque type de produit, sont présentés dans la Fig. 1.
| Ressource | Suite1 | Produit2 | Produit3 | Produit4 | Signe | Disponibilité |
| Profit | ||||||
| Travail | ||||||
| Matières premières | ||||||
| Finance |
Image 1.
Modèle mathématique la tâche a la forme :
où x j est la quantité de produits manufacturés du jème type ; F – fonction objectif ; les côtés gauches des expressions de contrainte indiquent les valeurs ressource requise, et les côtés droits montrent la quantité ressource disponible.
Saisir les conditions de la tâche
Pour résoudre le problème avec en utilisant Excel Vous devez créer un formulaire pour saisir les données initiales et les saisir. Le formulaire de saisie est présenté sur la Fig. 2.
Dans la cellule F6, une expression pour la fonction objectif est introduite comme la somme des produits des valeurs de profit provenant de la libération d'une unité de produit de chaque type par le nombre de produits du type correspondant. Pour plus de clarté, sur la Fig. La figure 3 montre le formulaire de saisie des données initiales en mode de sortie de formule.
Les parties gauches des restrictions pour les ressources de chaque type sont saisies dans les cellules F8:F10.
Figure 2.
Figure 3.
Résoudre un problème de programmation linéaire
Pour résoudre des problèmes de programmation linéaire dans Excel, vous utilisez un outil puissant appelé Trouver une solution . L'accès à la Recherche d'une solution s'effectue depuis le menu Service , la boîte de dialogue Rechercher une solution apparaît à l'écran (Fig. 4).
Graphique 4.
Saisir les conditions d'un problème pour trouver sa solution comprend les étapes suivantes :
1 Attribuez une fonction cible en plaçant le curseur dans le champ Définir la cellule cible fenêtre Recherchez une solution et cliquez dans la cellule F6 du formulaire de saisie ;
2 Allumez l'interrupteur pour la valeur de la fonction objectif, c'est-à-dire indique-le Égal à la valeur maximale ;
3 Saisissez les adresses des variables à modifier (x j) : pour cela placez le curseur dans le champ Changer de cellule fenêtre Recherchez une solution, puis sélectionnez la plage de cellules B3:E3 dans le formulaire de saisie ;
4 Appuyez sur le bouton Ajouter Fenêtres de recherche de solutions pour saisir des contraintes pour un problème de programmation linéaire ; une fenêtre apparaît à l'écran Ajouter une contrainte (Fig.5) :
Saisir les conditions aux limites pour les variables x j (x j ³0), pour cela dans le champ Référence de cellule indiquer la cellule B3 correspondant à x 1, sélectionner le signe souhaité (³) dans la liste du champ Limitation indiquer la cellule du formulaire de saisie dans laquelle est stockée la valeur correspondante de la condition aux limites (cellule B4), cliquer sur le bouton Ajouter ; répétez les étapes décrites pour les variables x 2, x 3 et x 4 ;
Saisissez les restrictions pour chaque type de ressource dans le champ Référence de cellule fenêtre Ajouter une contrainte indiquer la cellule F9 du formulaire de saisie, qui contient l'expression du côté gauche de la restriction imposée aux ressources en main d'œuvre dans les champs Limitation indiquez le signe £ et l'adresse H9 à droite de la restriction, appuyez sur le bouton Ajouter ; de même, introduire des restrictions sur d'autres types de ressources ;
Après avoir entré la dernière contrainte, au lieu de Ajouter presse D'ACCORD et revenez à la fenêtre Rechercher une solution.
Graphique 5.
La résolution d'un problème de programmation linéaire commence par la définition des paramètres de recherche :
Dans la fenêtre Trouver une solution appuie sur le bouton Possibilités , une fenêtre apparaît à l'écran Options de recherche de solutions (Fig.6);
Case à cocher Modèle linéaire, qui garantit l'utilisation de la méthode simplexe ;
Spécifiez le nombre maximum d'itérations (la valeur par défaut est 100, ce qui convient à la plupart des problèmes) ;
Case à cocher , si vous devez revoir toutes les étapes de la recherche de la solution optimale ;
Cliquez sur D'ACCORD , retourne à la fenêtre Trouver une solution .
Graphique 6.
Pour résoudre le problème, appuyez sur le bouton Exécuter dans la fenêtre Trouver une solution , il y a une fenêtre sur l'écran Résultats de la recherche de solutions (Fig. 7), qui contient le message La solution a été trouvée. Toutes les restrictions et conditions d’optimalité sont remplies. Si les conditions du problème sont incohérentes, un message s'affiche La recherche ne trouve pas solution adaptée . Si la fonction objectif n'est pas limitée, alors le message apparaît Les valeurs des cellules cibles ne convergent pas.
Graphique 7.
Pour l'exemple considéré, une solution a été trouvée et le résultat de la solution optimale au problème est affiché dans le formulaire de saisie : la valeur de la fonction objectif correspondant au profit maximum et égale à 1320 est indiquée dans la cellule F6 du formulaire de saisie, le plan de production optimal x 1 = 10, x 2 = 0, x 3 = 6, x 4 = 0 est indiqué dans les cellules B3: C3 du formulaire de saisie (Fig. 8).
La quantité de ressources utilisées pour fabriquer des produits est affichée dans les cellules F9:F11 : main d'œuvre - 16, matières premières - 84, finances - 100.
Figure 8.
Si, lors du réglage des paramètres dans la fenêtre Options de recherche de solutions (Fig. 6) la case a été cochée Afficher les résultats de l'itération , toutes les étapes de recherche seront affichées séquentiellement. Une fenêtre apparaîtra à l'écran (Fig. 9). Dans ce cas, les valeurs actuelles des variables et des fonctions cibles seront affichées dans le formulaire de saisie. Ainsi, les résultats de la première itération de recherche d'une solution au problème d'origine sont présentés sous la forme de saisie de la figure 10.
Graphique 9.
Graphique 10.
Pour continuer à chercher une solution, cliquez sur le bouton Continuer dans la fenêtre État actuel de la recherche d'une solution .
Analyse de la solution optimale
Avant de procéder à l’analyse des résultats de la solution, présentons le problème initial sous la forme
en introduisant des variables supplémentaires pour i, représentant les valeurs des ressources inutilisées.
Créons un problème double pour le problème d'origine et introduisons des variables doubles supplémentaires v i .
L'analyse des résultats de la recherche de solution permettra de les relier aux variables de la solution initiale et double problèmes.
Utiliser une fenêtre Résultats de la recherche de solutions Vous pouvez appeler trois types de rapports qui vous permettent d'analyser la solution optimale trouvée :
Résultats,
Durabilité,
Limites.
Pour appeler un état dans un champ Type de rapport surligner le titre le bon type et appuyez sur D'ACCORD .
1 Rapport de résultats(Fig. 11) se compose de trois tableaux :
Le tableau 1 contient des informations sur la fonction objectif ; en colonne Initialement la valeur de la fonction objectif est indiquée avant le début des calculs ;
Le tableau 2 contient les valeurs des variables requises x j obtenues à la suite de la résolution du problème (plan de production optimal) ;
Le tableau 3 montre les résultats de la solution optimale pour les contraintes et pour les conditions aux limites.
Pour Restrictions dans la colonne Formule les dépendances qui ont été saisies lors de la définition des restrictions dans la fenêtre sont affichées Trouver une solution ; dans la colonne Signification les valeurs de la ressource utilisée sont indiquées ; dans la colonne Différence indique la quantité de ressources inutilisées. Si la ressource est entièrement utilisée, alors dans la colonne État le message s'affiche en rapport ; si la ressource n'est pas entièrement utilisée, cette colonne indique pas connecté. Pour Conditions aux limites des valeurs similaires sont données avec la seule différence qu'au lieu d'une ressource inutilisée, la différence entre la valeur de la variable x j dans la solution optimale trouvée et la condition aux limites spécifiée pour celle-ci (x j ³0) est affichée.
C'est dans la colonne Différence vous pouvez voir les valeurs des variables supplémentaires y i du problème d'origine dans la formulation (2). Ici y 1 =y 3 =0, c'est-à-dire la quantité de main-d'œuvre et de ressources financières inutilisées est nulle. Ces ressources sont pleinement utilisées. Dans le même temps, la quantité de ressources inutilisées pour les matières premières y 2 = 26, ce qui signifie qu'il y a un excédent de matières premières.
Graphique 11.
2 Rapport de durabilité(Fig. 12) se compose de deux tableaux.
Le tableau 1 montre les valeurs suivantes :
Le résultat de la résolution du problème (plan de version optimal) ;
- Normir. prix, c'est à dire. des valeurs montrant dans quelle mesure la fonction objectif changera lorsqu'une unité de production du type correspondant sera forcée d'être incluse dans le plan optimal ;
Coefficients de fonction objective ;
Valeurs limites pour l'incrément des coefficients de la fonction objectif auxquelles le plan de production optimal est maintenu.
Le tableau 2 contient des données similaires pour les restrictions :
Quantité de ressources utilisées ;
- Prix fictif, montrant comment la fonction objectif change lorsque la valeur de la ressource correspondante change de un ;
Valeurs valides incréments de ressources auxquels le plan de production optimal est maintenu.
Graphique 12.
Le rapport de durabilité permet une double évaluation.
Comme on le sait, les variables duales z i montrent comment la fonction objectif change lorsque la ressource du i-ième type change de un. Dans un rapport Excel, la double estimation est appelée Prix fictif.
Dans notre exemple, la matière première n'est pas entièrement utilisée et sa ressource y 2 = 26. Évidemment, une augmentation de la quantité de matières premières, par exemple jusqu'à 111, n'entraînera pas une augmentation de la fonction objectif. Par conséquent, pour la deuxième contrainte, la variable duale z 2 =0. Ainsi, si d'après cette ressource il y a une réserve, alors variable supplémentaire sera supérieur à zéro, et double évaluation de cette contrainte est nulle.
Dans l'exemple considéré, les ressources en main-d'œuvre et les finances ont été pleinement utilisées, leurs variables supplémentaires sont donc égales à zéro (y 1 = y 3 = 0). Si une ressource est pleinement utilisée, alors son augmentation ou sa diminution affectera le volume de production, et donc la valeur de la fonction objectif. Les doubles estimations des restrictions sur le travail et les ressources financières sont différentes de zéro, c'est-à-dire z 1 =20, z 3 =10.
Les valeurs des estimations doubles se trouvent dans Rapport de durabilité, dans le tableau 2, dans la colonne Prix fictif.
Avec une augmentation (diminution) des ressources en main-d'œuvre d'une unité, la fonction objectif augmentera (diminuera) de 20 unités et sera égale à
F=1320+20×1=1340 (avec grossissement).
De même, lorsque le volume des finances augmente d’une unité, la fonction objectif sera
F=1320+10×1=1330.
Ici, dans les graphiques Augmentation autorisée Et Réduction admissible Le tableau 2 montre les limites autorisées pour modifier la quantité de ressources du jème type. Par exemple, lorsque l'augmentation de la valeur des ressources en travail passe de –6 à 3,55, comme le montre le tableau, la structure de la solution optimale est préservée, c'est-à-dire le plus grand profit est fourni par la production de Prod1 et Prod3, mais dans quantités différentes.
Des variables doubles supplémentaires sont également reflétées dans Rapport de durabilité dans la colonne Normir. prix Tableau 1.
Si les principales variables ne sont pas incluses dans la solution optimale, c'est-à-dire sont égaux à zéro (dans l'exemple x 2 =x 4 =0), alors les variables supplémentaires correspondantes ont des valeurs positives (v 2 =10, v 4 =20). Si les variables principales sont incluses dans la solution optimale (x 1 =10, x 3 =6), alors leurs variables doubles supplémentaires sont égales à zéro (v 1 =0, v 3 =0).
Ces valeurs montrent de combien la fonction objectif va diminuer (donc le signe moins dans les valeurs des variables v 2 et v 4) avec la libération forcée d'une unité de ce produit. Par conséquent, si l’on veut libérer de force une unité de produit de type Prod3, alors la fonction objectif diminuera de 10 unités et sera égale à 1320 -10×1 = 1310.
Notons Dс j la variation des coefficients de la fonction objectif dans le modèle original (1). Ces coefficients déterminent le bénéfice tiré de la vente d'une unité de produit du jème type.
Dans les graphiques Augmentation autorisée Et Réduction autorisée Tableau 1 Rapport de durabilité les limites de changement Dс j sont indiquées auxquelles la structure est préservée plan optimal, c'est à dire. Il sera rentable de continuer à fabriquer des produits de type Prodj. Par exemple, si Dc 1 évolue entre -12 £ Dc 1 et 40 £, comme indiqué dans le rapport, il sera toujours rentable de fabriquer des produits du type Prod1. Dans ce cas, la valeur de la fonction objectif sera F=1320+x 1 ×Dс j =1320+10×Dс j .
3 Rapport de limite montré sur la fig. 13. Il montre dans quelles limites les valeurs x j incluses dans la solution optimale peuvent changer tout en conservant la structure de la solution optimale. De plus, pour chaque type de produit, les valeurs de la fonction objectif sont données, obtenues en substituant dans la solution optimale la valeur de la limite inférieure de production de produits du type correspondant par des valeurs constantes de production d'autres les types. Par exemple, si pour la solution optimale x 1 =10, x 2 =0, x 3 =6, x 4 =0 on met x 1 =0 (limite inférieure) avec x 2, x 3 et x 4 inchangés, alors la la valeur de la fonction objectif sera égale à 60×0+70×0+120×6+130×0=720.
La saisie des conditions de tâche comprend les étapes principales suivantes :
Création d'un formulaire pour saisir les conditions des tâches.
Saisie des données initiales.
Saisie des dépendances à partir d'un modèle mathématique.
Finalité de la fonction objectif.
introduction de restrictions et de conditions limites.
Progrès dans la résolution du problème :
Formulaire de saisie des conditions de tâche :
|
Variables |
||||||
|
Signification |
||||||
|
Coefficient dans la fonction objectif |
(formule) |
|||||
|
Restrictions |
||||||
|
Coefficients de restrictions |
Côté droit de la contrainte |
|||||
Un par un, les coefficients de la fonction objectif, les contraintes, leurs signes, les formules de description de la fonction objectif et les contraintes présentées dans le modèle mathématique du problème sont saisis dans le formulaire présenté.
La boîte de dialogue Assistant de fonction est utilisée pour décrire la formule et les contraintes de la fonction objectif ; catégorie de fonctions – mathématiques ; Fonction SOMMEPRODUIT (dans la boîte de dialogue du tableau 1 l'intervalle de cellules de la valeur variable B3:C3 est indiqué, dans le tableau 2 - les coefficients de ces variables. Dans la fonction il s'agit de l'intervalle de cellules B4:C4, en contraintes - B8 : C8, B9:C9, etc.)
La solution au problème s'effectue à l'aide des commandes Service, Rechercher une solution...
Dans la boîte de dialogue Rechercher une solution, remplissez les lignes indiquant les adresses des cellules :
Fonction objectif : E4
Égal : max (min)
Changement de cellule : l'emplacement des variables est indiqué (B3:C3)
Restrictions : à l'aide de la touche Ajouter, on écrit les adresses des cellules indiquant les conditions de restrictions (par exemple : D8>= F8, etc.). Il est obligatoire de saisir une contrainte de solution entière.
Si, lors de la saisie d'une tâche, il est nécessaire de modifier ou de supprimer les restrictions ou conditions limites saisies, cela se fait à l'aide des commandes Changer.., Supprimer.
Pour obtenir une solution optimale à un problème de programmation linéaire dans la Recherche de solution, utilisez la touche Options... :
Temps maximum : 100 secondes
Nombre limite d'itérations : 100
Erreur relative 0,000001
Tolérance : 5%
Cochez la case Modèle linéaire, qui garantit l'utilisation de la méthode simplexe.
Dans la fenêtre Rechercher une solution qui apparaît, exécutez la commande Exécuter.
Une solution a été trouvée, le résultat de la solution optimale est donné dans le tableau original.
Résoudre des problèmes de programmation linéaire dans Excel
En utilisant les données du double problème direct, résolvez-le dans Excel à l'aide des tableaux suivants
Variables
Restrictions
|
Type de ressource |
Coefficients de restrictions |
Côté gauche de la contrainte (formule) |
Partie droite restrictions |
||
Il est nécessaire de déterminer en quelle quantité il est nécessaire de fabriquer des produits de quatre types Prod1, Prod2, Prod3, Prod4, dont la production nécessite trois types de ressources : la main d'œuvre, les matières premières et la finance. La quantité de chaque type de ressource nécessaire pour produire une unité de produit d'un type donné est appelée taux de consommation. Les taux de consommation, ainsi que les bénéfices tirés de la vente d'une unité de chaque type de produit, sont présentés dans la Fig. 1.
| Ressource | Suite1 | Produit2 | Produit3 | Produit4 | Signe | Disponibilité |
| Profit | ||||||
| Travail | ||||||
| Matières premières | ||||||
| Finance |
Image 1.
Le modèle mathématique du problème a la forme :
où x j est la quantité de produits manufacturés du jème type ; F – fonction objectif ; les côtés gauches des expressions de contrainte indiquent les valeurs ressource requise, et les côtés droits montrent la quantité ressource disponible.
Saisir les conditions de la tâche
Pour résoudre le problème avec Excel, vous devez créer un formulaire de saisie des données initiales et le saisir. Le formulaire de saisie est présenté sur la Fig. 2.
Dans la cellule F6, une expression pour la fonction objectif est introduite comme la somme des produits des valeurs de profit provenant de la libération d'une unité de produit de chaque type par le nombre de produits du type correspondant. Pour plus de clarté, sur la Fig. La figure 3 montre le formulaire de saisie des données initiales en mode de sortie de formule.
Les parties gauches des restrictions pour les ressources de chaque type sont saisies dans les cellules F8:F10.
Figure 2.
Figure 3.
Résoudre un problème de programmation linéaire
Pour résoudre des problèmes de programmation linéaire dans Excel, vous utilisez un outil puissant appelé Trouver une solution . L'accès à la Recherche d'une solution s'effectue depuis le menu Service , la boîte de dialogue Rechercher une solution apparaît à l'écran (Fig. 4).
Graphique 4.
Saisir les conditions d'un problème pour trouver sa solution comprend les étapes suivantes :
1 Attribuez une fonction cible en plaçant le curseur dans le champ Définir la cellule cible fenêtre Recherchez une solution et cliquez dans la cellule F6 du formulaire de saisie ;
2 Allumez l'interrupteur pour la valeur de la fonction objectif, c'est-à-dire indique-le Égal à la valeur maximale ;
3 Saisissez les adresses des variables à modifier (x j) : pour cela placez le curseur dans le champ Changer de cellule fenêtre Recherchez une solution, puis sélectionnez la plage de cellules B3:E3 dans le formulaire de saisie ;
4 Appuyez sur le bouton Ajouter Fenêtres de recherche de solutions pour saisir des contraintes pour un problème de programmation linéaire ; une fenêtre apparaît à l'écran Ajouter une contrainte (Fig.5) :
Saisir les conditions aux limites pour les variables x j (x j ³0), pour cela dans le champ Référence de cellule indiquer la cellule B3 correspondant à x 1, sélectionner le signe souhaité (³) dans la liste du champ Limitation indiquer la cellule du formulaire de saisie dans laquelle est stockée la valeur correspondante de la condition aux limites (cellule B4), cliquer sur le bouton Ajouter ; répétez les étapes décrites pour les variables x 2, x 3 et x 4 ;
Saisissez les restrictions pour chaque type de ressource dans le champ Référence de cellule fenêtre Ajouter une contrainte indiquer la cellule F9 du formulaire de saisie, qui contient l'expression du côté gauche de la restriction imposée aux ressources en main d'œuvre dans les champs Limitation indiquez le signe £ et l'adresse H9 à droite de la restriction, appuyez sur le bouton Ajouter ; de même, introduire des restrictions sur d'autres types de ressources ;
Après avoir entré la dernière contrainte, au lieu de Ajouter presse D'ACCORD et revenez à la fenêtre Rechercher une solution.
Graphique 5.
La résolution d'un problème de programmation linéaire commence par la définition des paramètres de recherche :
Dans la fenêtre Trouver une solution appuie sur le bouton Possibilités , une fenêtre apparaît à l'écran Options de recherche de solutions (Fig.6);
Case à cocher Modèle linéaire, qui garantit l'utilisation de la méthode simplexe ;
Spécifiez le nombre maximum d'itérations (la valeur par défaut est 100, ce qui convient à la plupart des problèmes) ;
Case à cocher , si vous devez revoir toutes les étapes de la recherche de la solution optimale ;
Cliquez sur D'ACCORD , retourne à la fenêtre Trouver une solution .
Graphique 6.
Pour résoudre le problème, appuyez sur le bouton Exécuter dans la fenêtre Trouver une solution , il y a une fenêtre sur l'écran Résultats de la recherche de solutions (Fig. 7), qui contient le message La solution a été trouvée. Toutes les restrictions et conditions d’optimalité sont remplies. Si les conditions du problème sont incohérentes, un message s'affiche La recherche ne parvient pas à trouver une solution appropriée. Si la fonction objectif n'est pas limitée, alors le message apparaît Les valeurs des cellules cibles ne convergent pas.
Graphique 7.
Pour l'exemple considéré, une solution a été trouvée et le résultat de la solution optimale au problème est affiché dans le formulaire de saisie : la valeur de la fonction objectif correspondant au profit maximum et égale à 1320 est indiquée dans la cellule F6 du formulaire de saisie, le plan de production optimal x 1 = 10, x 2 = 0, x 3 = 6, x 4 = 0 est indiqué dans les cellules B3: C3 du formulaire de saisie (Fig. 8).
La quantité de ressources utilisées pour fabriquer des produits est affichée dans les cellules F9:F11 : main d'œuvre - 16, matières premières - 84, finances - 100.
Figure 8.
Si, lors du réglage des paramètres dans la fenêtre Options de recherche de solutions (Fig. 6) la case a été cochée Afficher les résultats de l'itération , toutes les étapes de recherche seront affichées séquentiellement. Une fenêtre apparaîtra à l'écran (Fig. 9). Dans ce cas, les valeurs actuelles des variables et des fonctions cibles seront affichées dans le formulaire de saisie. Ainsi, les résultats de la première itération de recherche d'une solution au problème d'origine sont présentés sous la forme de saisie de la figure 10.
Graphique 9.
Graphique 10.
Pour continuer à chercher une solution, cliquez sur le bouton Continuer dans la fenêtre État actuel de la recherche d'une solution .
Analyse de la solution optimale
Avant de procéder à l’analyse des résultats de la solution, présentons le problème initial sous la forme
en introduisant des variables supplémentaires pour i, représentant les valeurs des ressources inutilisées.
Créons un problème double pour le problème d'origine et introduisons des variables doubles supplémentaires v i .
L'analyse des résultats de la recherche de solution permettra de les relier aux variables du problème initial et duel.
Utiliser une fenêtre Résultats de la recherche de solutions Vous pouvez appeler trois types de rapports qui vous permettent d'analyser la solution optimale trouvée :
Résultats,
Durabilité,
Limites.
Pour appeler un état dans un champ Type de rapport mettez en surbrillance le nom du type souhaité et appuyez sur D'ACCORD .
1 Rapport de résultats(Fig. 11) se compose de trois tableaux :
Le tableau 1 contient des informations sur la fonction objectif ; en colonne Initialement la valeur de la fonction objectif est indiquée avant le début des calculs ;
Le tableau 2 contient les valeurs des variables requises x j obtenues à la suite de la résolution du problème (plan de production optimal) ;
Le tableau 3 montre les résultats de la solution optimale pour les contraintes et pour les conditions aux limites.
Pour Restrictions dans la colonne Formule les dépendances qui ont été saisies lors de la définition des restrictions dans la fenêtre sont affichées Trouver une solution ; dans la colonne Signification les valeurs de la ressource utilisée sont indiquées ; dans la colonne Différence indique la quantité de ressources inutilisées. Si la ressource est entièrement utilisée, alors dans la colonne État le message s'affiche en rapport ; si la ressource n'est pas entièrement utilisée, cette colonne indique pas connecté. Pour Conditions aux limites des valeurs similaires sont données avec la seule différence qu'au lieu d'une ressource inutilisée, la différence entre la valeur de la variable x j dans la solution optimale trouvée et la condition aux limites spécifiée pour celle-ci (x j ³0) est affichée.
C'est dans la colonne Différence vous pouvez voir les valeurs des variables supplémentaires y i du problème d'origine dans la formulation (2). Ici y 1 =y 3 =0, c'est-à-dire la quantité de main-d'œuvre et de ressources financières inutilisées est nulle. Ces ressources sont pleinement utilisées. Dans le même temps, la quantité de ressources inutilisées pour les matières premières y 2 = 26, ce qui signifie qu'il y a un excédent de matières premières.
Graphique 11.
2 Rapport de durabilité(Fig. 12) se compose de deux tableaux.
Le tableau 1 montre les valeurs suivantes :
Le résultat de la résolution du problème (plan de version optimal) ;
- Normir. prix, c'est à dire. des valeurs montrant dans quelle mesure la fonction objectif changera lorsqu'une unité de production du type correspondant sera forcée d'être incluse dans le plan optimal ;
Coefficients de fonction objective ;
Valeurs limites pour l'incrément des coefficients de la fonction objectif auxquelles le plan de production optimal est maintenu.
Le tableau 2 contient des données similaires pour les restrictions :
Quantité de ressources utilisées ;
- Prix fictif, montrant comment la fonction objectif change lorsque la valeur de la ressource correspondante change de un ;
Valeurs acceptables des incréments de ressources auxquelles le plan de production optimal est maintenu.
Graphique 12.
Le rapport de durabilité permet une double évaluation.
Comme on le sait, les variables duales z i montrent comment la fonction objectif change lorsque la ressource du i-ième type change de un. Dans un rapport Excel, la double estimation est appelée Prix fictif.
Dans notre exemple, la matière première n'est pas entièrement utilisée et sa ressource y 2 = 26. Évidemment, une augmentation de la quantité de matières premières, par exemple jusqu'à 111, n'entraînera pas une augmentation de la fonction objectif. Par conséquent, pour la deuxième contrainte, la variable duale z 2 =0. Ainsi, s'il existe une réserve pour cette ressource, alors variable supplémentaire sera supérieur à zéro, et double évaluation de cette contrainte est nulle.
Dans l'exemple considéré, les ressources en main-d'œuvre et les finances ont été pleinement utilisées, leurs variables supplémentaires sont donc égales à zéro (y 1 = y 3 = 0). Si une ressource est pleinement utilisée, alors son augmentation ou sa diminution affectera le volume de production, et donc la valeur de la fonction objectif. Les doubles estimations des restrictions sur le travail et les ressources financières sont différentes de zéro, c'est-à-dire z 1 =20, z 3 =10.
Les valeurs des estimations doubles se trouvent dans Rapport de durabilité, dans le tableau 2, dans la colonne Prix fictif.
Avec une augmentation (diminution) des ressources en main-d'œuvre d'une unité, la fonction objectif augmentera (diminuera) de 20 unités et sera égale à
F=1320+20×1=1340 (avec grossissement).
De même, lorsque le volume des finances augmente d’une unité, la fonction objectif sera
F=1320+10×1=1330.
Ici, dans les graphiques Augmentation autorisée Et Réduction admissible Le tableau 2 montre les limites autorisées pour modifier la quantité de ressources du jème type. Par exemple, lorsque l'augmentation de la valeur des ressources en travail passe de –6 à 3,55, comme le montre le tableau, la structure de la solution optimale est préservée, c'est-à-dire le plus grand profit est fourni par la production de Prod1 et Prod3, mais dans quantités différentes.
Des variables doubles supplémentaires sont également reflétées dans Rapport de durabilité dans la colonne Normir. prix Tableau 1.
Si les principales variables ne sont pas incluses dans la solution optimale, c'est-à-dire sont égaux à zéro (dans l'exemple x 2 =x 4 =0), alors les variables supplémentaires correspondantes ont des valeurs positives (v 2 =10, v 4 =20). Si les variables principales sont incluses dans la solution optimale (x 1 =10, x 3 =6), alors leurs variables doubles supplémentaires sont égales à zéro (v 1 =0, v 3 =0).
Ces valeurs montrent de combien la fonction objectif va diminuer (donc le signe moins dans les valeurs des variables v 2 et v 4) avec la libération forcée d'une unité de ce produit. Par conséquent, si l’on veut libérer de force une unité de produit de type Prod3, alors la fonction objectif diminuera de 10 unités et sera égale à 1320 -10×1 = 1310.
Notons Dс j la variation des coefficients de la fonction objectif dans le modèle original (1). Ces coefficients déterminent le bénéfice tiré de la vente d'une unité de produit du jème type.
Dans les graphiques Augmentation autorisée Et Réduction autorisée Tableau 1 Rapport de durabilité les limites de changement de Dc j sont indiquées auxquelles la structure du plan optimal est préservée, c'est-à-dire Il sera rentable de continuer à fabriquer des produits de type Prodj. Par exemple, si Dc 1 évolue entre -12 £ Dc 1 et 40 £, comme indiqué dans le rapport, il sera toujours rentable de fabriquer des produits du type Prod1. Dans ce cas, la valeur de la fonction objectif sera F=1320+x 1 ×Dс j =1320+10×Dс j .
3 Rapport de limite montré sur la fig. 13. Il montre dans quelles limites les valeurs x j incluses dans la solution optimale peuvent changer tout en conservant la structure de la solution optimale. De plus, pour chaque type de produit, les valeurs de la fonction objectif sont données, obtenues en substituant dans la solution optimale la valeur de la limite inférieure de production de produits du type correspondant par des valeurs constantes de production d'autres les types. Par exemple, si pour la solution optimale x 1 =10, x 2 =0, x 3 =6, x 4 =0 on met x 1 =0 (limite inférieure) avec x 2, x 3 et x 4 inchangés, alors la la valeur de la fonction objectif sera égale à 60×0+70×0+120×6+130×0=720.