Résoudre des problèmes de programmation linéaire dans Excel - Résumé. Résoudre des problèmes de programmation linéaire à l'aide d'Excel

Usage Microsoft Excel Résoudre des problèmes programmation linéaire .

Dans Excel 2007, pour activer le package d'analyse, vous devez cliquer sur Aller pour bloquer Options Excel en appuyant sur le bouton à gauche coin supérieur, puis le bouton Options Excel"en bas de la fenêtre :

Ensuite, dans la liste qui s'ouvre, vous devez sélectionner Modules complémentaires, puis placez le curseur sur l'élément Trouver une solution, appuie sur le bouton Aller et dans la fenêtre suivante, activez le package d'analyse.

Afin de résoudre le problème LP dans un tableau Processeur Microsoft Excel, vous devez procéder comme suit :

1. Entrez la condition du problème :

un)créer un formulaire d'écran pour saisir les conditions de la tâche :

· variables,

· fonction objectif(CF),

· restrictions,

· conditions aux limites;

b) saisir les données initiales dans le formulaire d'écran :

· Coefficients TF,

· coefficients pour les variables dans les restrictions,

· côtés droits des restrictions ;

c) introduire des dépendances de modèle mathématique pour filtrer le formulaire :

formule de calcul du CF,

· formules de calcul des valeurs des côtés gauches des restrictions ;

d) définir TF (dans la fenêtre "Trouver une solution"):

cellule cible

· direction de l'optimisation des FC ;

e) introduire des restrictions et des conditions aux limites (dans la fenêtre "Trouver une solution"):

· cellules à valeurs variables,

· conditions aux limites pour valeurs acceptables variables

· ratios entre les côtés droit et gauche des contraintes.

2. Résolvez le problème :

un) définir les paramètres pour résoudre le problème (dans la fenêtre "Trouver une solution");

b) exécuter un problème à résoudre (dans la fenêtre "Trouver une solution") ;

c) sélectionner le format de sortie de la solution (dans la fenêtre "Résultats de la recherche de solutions").

Examinons en détail l'utilisation de MS Excel en utilisant l'exemple de résolution du problème suivant.

Tâche.

L'usine « GRM pic » produit deux types de céréales pour petit-déjeuner : « Crunchy » et « Chewy ». Les ingrédients utilisés pour fabriquer les deux produits sont essentiellement les mêmes et ne sont généralement pas rares. La principale limitation imposée au volume de production est la disponibilité d'heures de travail dans chacun des trois ateliers de l'usine.

La responsable de production Joy Deason doit élaborer un plan de production mensuel. Le tableau ci-dessous montre le temps de travail total et le nombre d'heures-homme nécessaires pour produire 1 tonne de produit.

*Boutique*	*Fonds de temps de travail requis* *personne-h/t*		*Fonds général du temps de travail* *heure-personne par mois*
*Boutique*	*"Croquant"*	*"Moelleux"*
A. Production	10	4	1000
B. Ajout d'assaisonnements	3	2	360
C. Emballage	2	5	600

Le revenu de la production de 1 tonne de « Crunchy » est de 150 livres. Art., et de la production de "Chewy" - 75 f., art. Sur actuellement il n'y a aucune restriction sur les volumes de ventes possibles. Il est possible de vendre tous les produits fabriqués.

Requis:

a) Formuler un modèle de programmation linéaire qui maximise le revenu mensuel total de l'usine.

b) Résolvez-le en utilisant MS Excel.

La formulation formelle de ce problème est de la forme :

(1)
Saisie des données initiales
Création d'un écran et saisie des données initiales

Le formulaire d’écran de la solution dans MS Excel est présenté dans la figure 1.

Image 1.

Dans le formulaire d'écran de la figure 1, chaque variable et chaque coefficient du problème se voit attribuer une cellule spécifique sur feuille de calcul Excel. Le nom de la cellule est constitué d'une lettre désignant une colonne et d'un nombre désignant une ligne, à l'intersection de laquelle se trouve l'objet du problème LP. Ainsi, par exemple, les variables de la tâche 1 correspondent aux cellules B4 (), C4(), les coefficients CF correspondent aux cellules B6 (150), C6(75), les membres de droite des restrictions correspondent aux cellulesD18 (1000), D19 (360), D20 (600), etc.
Saisie des dépendances d'un énoncé formel du problème dans un formulaire d'écran

Pour saisir des dépendances qui définissent l'expression de la fonction cible et des restrictions, utilisez la fonction MS Excel SOMME PRODUIT, qui calcule la somme des produits par paires de deux tableaux ou plus.

Un des plus des moyens simples définir des fonctions dans MS Excel consiste à utiliser le mode "Insérer des fonctions" , qui peut être appelé depuis le menu "Insérer" ou en appuyant sur un bouton "

Figure 2

Ainsi, par exemple, l'expression de la fonction objectif du problème 1 est définie comme suit :

· curseur dans le champ D6;

· en appuyant sur un bouton "

· dans la fenêtre "Fonction" sélectionner une fonction SOMME PRODUIT(Fig.3) ;

figure 3

dans la fenêtre qui apparaît "SOMMEPRODUIT"à la ligne "Tableau 1" saisir une expression B$4: C$4 , et à la ligne "Tableau 2"- expression B6: C6 (Fig.4);

Figure 4

Les membres de gauche des contraintes du problème (1) sont somme de produits chacune des cellules allouées pour les valeurs des variables de tâche ( B3, C3 ), à la cellule correspondante réservée aux coefficients d'une limitation spécifique ( B13, C13 - 1ère limitation ; B14, C14- 2ème limitation et B15, C15- 3ème limitation). Les formules correspondant aux côtés gauches des restrictions sont présentées dans le tableau 1.

Tableau 1.
Formules décrivant les limites du modèle (1)

Côté gauche de la contrainte	FormuleExceller
	=SOMMEPRODUIT(B4: C4; B13: C13))
	=SOMMEPRODUIT(B4: C4; B14: C14))
	=SOMMEPRODUIT(B4: C4; B15: C15)

Tâche DF

D'autres actions sont effectuées dans la fenêtre "Trouver une solution", qui est appelé depuis le menu "Service"(Fig.5) :

· placez le curseur dans le champ "Définir la cellule cible";

· entrez l'adresse de la cellule cible $ D$6 ou faites un clic avec le bouton gauche de la souris sur la cellule cible dans le formulaire à l'écran ¾ cela équivaudra à saisir l'adresse au clavier ;

· entrez la direction de l'optimisation CF en cliquant une fois avec le bouton gauche de la souris sur le bouton de sélection "valeur maximum".

Figure 5
Saisie de contraintes et de conditions aux limites
Définition de cellules variables

Par la fenêtre "Trouver une solution" dans le champ "Changer de cellule" saisir les adresses $ B4 $ : $С$4. Les adresses requises peuvent être saisies dans le champ "Changer de cellule" et automatiquement en sélectionnant les cellules variables correspondantes avec la souris directement dans le masque.
Définition de conditions limites pour des valeurs de variable acceptables

Dans notre cas, seule la condition aux limites de non-négativité est imposée aux valeurs des variables, c'est-à-dire que leur limite inférieure doit être égale à zéro (voir Fig. 1).

· Cliquez sur le bouton "Ajouter", après quoi une fenêtre apparaîtra "Ajouter une contrainte"(Fig.6).

· Sur le terrain "Référence de cellule" saisir des adresses de cellules variables $ B4 $ : $С$4. Cela peut être fait soit à partir du clavier, soit en sélectionnant toutes les cellules variables directement dans le masque avec la souris.

· Dans le champ Panneau, ouvrez la liste des panneaux suggérés et sélectionnez .

· Sur le terrain "Limitation" entrez 0.

Fig.6 - Ajout d'une condition de non-négativité des variables du problème (1)
Spécification des panneaux de restriction , , =

· Cliquez sur le bouton "Ajouter" dans la fenêtre "Ajouter une contrainte".

· Sur le terrain "Référence de cellule" entrez l'adresse de cellule du côté gauche d'une contrainte particulière, par exemple $ B$18 . Cela peut être fait soit à partir du clavier, soit en sélectionnant la cellule souhaitée directement dans le masque avec la souris.

· Conformément aux conditions de la tâche (1), sélectionnez le signe requis dans le champ signe, par exemple, .

· Sur le terrain "Limitation" saisissez l'adresse de la cellule du côté droit de la contrainte en question, par exemple $ D$18 .

· Saisissez les restrictions de la même manière : $ B$19<=$ D$19 , $ B$20<=$ D$20 .

· Confirmez la saisie de toutes les conditions ci-dessus en appuyant sur le bouton D'ACCORD.

Fenêtre "Trouver une solution" après avoir saisi toutes les données nécessaires, la tâche (1) est illustrée à la Fig. 5.

Si, lors de la saisie d'une condition de tâche, il s'avère nécessaire de modifier ou de supprimer les restrictions ou les conditions limites saisies, cela peut être fait en cliquant sur les boutons "Changement" ou "Supprimer"(voir fig. 5) .
La solution du problème
Définition des paramètres pour résoudre un problème

La tâche commence à être résolue dans la fenêtre "Trouver une solution." Mais d'abord, pour définir des paramètres spécifiques permettant de résoudre les problèmes d'optimisation d'une certaine classe, vous devez appuyer sur le bouton "Options" et remplissez certains champs de la fenêtre "Options de recherche de solutions"(Fig.7).

Riz. 7 - Paramètres de recherche de solutions adaptés à la plupart des problèmes LP

Paramètre "Durée maximale" sert à attribuer le temps (en secondes) alloué pour résoudre un problème. Vous pouvez saisir dans ce champ une durée qui ne dépasse pas 32 767 secondes (plus de 9 heures).

Paramètre "Nombre limite itérations" sert à contrôler le temps nécessaire pour résoudre un problème en limitant le nombre de calculs intermédiaires. Dans le champ, vous pouvez saisir le nombre d'itérations ne dépassant pas 32 767.

Paramètre "Erreur relative" sert à spécifier la précision avec laquelle la conformité de la cellule à la valeur cible ou son rapprochement des limites spécifiées est déterminée. Le champ doit contenir un nombre de 0 à 1. Ensuite moins le nombre de décimales dans le nombre saisi, le ci-dessous précision. Une précision élevée augmentera le temps nécessaire à la convergence du processus d’optimisation.

Paramètre "Tolérance" sert à définir la tolérance pour l’écart par rapport à la solution optimale dans les problèmes entiers. En spécifiant une tolérance plus grande, la recherche d'une solution se termine plus rapidement.

Paramètre "Convergence" s'applique uniquement lors de la résolution de problèmes non linéaires. Cochez la case "Modèle linéaire" permet d'accélérer la recherche d'une solution à un problème linéaire grâce à l'utilisation de la méthode du simplexe.

Confirmez les paramètres en appuyant sur le bouton " D'ACCORD" .
Commencer un problème à résoudre

La tâche de solution est lancée depuis la fenêtre "Trouver une solution" en appuyant sur un bouton "Courir".

Après avoir commencé à résoudre le problème LP, une fenêtre apparaît à l'écran "Résultats de la recherche de solutions" avec un message sur la solution réussie du problème présenté sur la Fig. 8.

Riz. 8 -. Message sur la solution réussie de la tâche

L'apparition d'un message différent n'indique pas la nature de la solution optimale au problème, mais plutôt que des erreurs ont été commises lors de la saisie des conditions du problème dans Excel. les erreurs, empêchant Excel de trouver la solution optimale qui existe réellement.

Si, en remplissant les champs de la fenêtre "Trouver une solution" des erreurs ont été commises qui n'ont pas permis à Excel d'appliquer la méthode simplex pour résoudre le problème ou compléter sa solution, puis après avoir lancé la tâche de solution, un message correspondant s'affichera à l'écran indiquant la raison pour laquelle la solution n'a pas été trouvée. Parfois, la valeur du paramètre est trop petite "Erreur relative" ne nous permet pas de trouver la solution optimale. Pour corriger cette situation, augmentez l'erreur petit à petit, par exemple de 0,000001 à 0,00001, etc.

Dans la fenêtre "Résultats de la recherche de solutions" Les noms de trois types de rapports sont présentés : "Résultats", "Durabilité", "Limites". Ils sont nécessaires lors de l’analyse de la sensibilité de la solution résultante. Pour recevoir la réponse (valeurs des variables, fonctions numériques et parties gauches des restrictions) directement sur l'écran, appuyez simplement sur le bouton " D'ACCORD". Après cela, la solution optimale au problème apparaît à l'écran (Fig. 9).

Fig.9 - Écran du problème (1) après obtention de la solution

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.

La programmation linéaire est la section à partir de laquelle la discipline de la « programmation mathématique » a commencé à se développer. Le terme « programmation » dans le nom de la discipline n'a rien de commun avec le terme « programmation (c'est-à-dire compilation de programmes) pour un ordinateur », puisque la discipline « programmation linéaire » est née avant même l'époque où les ordinateurs ont commencé à être largement utilisés. dans la résolution de problèmes mathématiques et d'ingénierie, de problèmes économiques et autres. Le terme « programmation linéaire » est né d'une traduction inexacte de l'anglais « programmation linéaire ». L’une des significations du mot « programmation » est de faire des plans, de planifier. Par conséquent, la traduction correcte de « programmation linéaire » ne serait pas « programmation linéaire », mais « planification linéaire », qui reflète plus fidèlement le contenu de la discipline. Cependant, les termes programmation linéaire, programmation non linéaire, etc. sont devenues généralement acceptées dans notre littérature. Les problèmes de programmation linéaire constituent un modèle mathématique pratique pour un grand nombre de problèmes économiques (planification de la production, consommation de matières, transport, etc.). L'utilisation de la méthode de programmation linéaire est importante et précieuse - l'option optimale est sélectionnée parmi un nombre assez important d'options alternatives. De plus, tous les problèmes économiques résolus à l'aide de la programmation linéaire se distinguent par des solutions alternatives et certaines conditions limites. Dans les feuilles de calcul Excel, à l'aide de la fonction de recherche de solutions, vous pouvez rechercher une valeur dans la cellule cible et modifier la valeur des variables. Dans ce cas, pour chaque variable, vous pouvez définir des restrictions, par exemple une limite supérieure. Avant de commencer la recherche d'une solution, il est nécessaire de formuler clairement le problème à résoudre dans le modèle, c'est-à-dire déterminer les conditions à respecter lors de l’optimisation. Le point de départ pour trouver la solution optimale est le modèle de calcul créé dans la feuille de calcul. Le programme de recherche de solutions nécessite les données suivantes. 1. Une cellule cible est une cellule d'un modèle de calcul dont les valeurs doivent être maximisées, minimisées ou égales à une valeur spécifiée spécifique. Il doit contenir une formule faisant directement ou indirectement référence aux cellules en cours de modification, ou il doit être lui-même modifié. 2. Les valeurs dans les cellules en cours de modification seront modifiées séquentiellement (par itération) jusqu'à ce que la valeur souhaitée soit obtenue dans la cellule cible. Ces cellules doivent donc influencer directement ou indirectement la valeur de la cellule cible. 3. Vous pouvez définir des restrictions et des conditions limites pour les cellules cible et modifiées. Vous pouvez également définir des restrictions pour d'autres cellules. Directement ou indirectement présent dans le modèle. Le programme offre la possibilité de définir des paramètres spéciaux qui déterminent le processus de recherche d'une solution. Après avoir défini tous les paramètres nécessaires, vous pouvez commencer à chercher une solution. La fonction de recherche de solutions créera trois rapports basés sur les résultats de son travail, qui pourront être marqués dans le classeur. Les contraintes sont les conditions qui doivent être remplies par l'outil de recherche de solutions lors de l'optimisation du modèle.

Une étude de la littérature a montré que :

1. La programmation linéaire est l’une des premières sections de la programmation mathématique et l’une des plus étudiées en profondeur. C’est la programmation linéaire qui est la section à partir de laquelle la discipline de la « programmation mathématique » elle-même a commencé à se développer.

La programmation linéaire est la méthode d'optimisation la plus couramment utilisée. Les problèmes de programmation linéaire sont les suivants :

· utilisation rationnelle des matières premières et des fournitures ; problèmes d'optimisation de coupe ;
· optimisation du programme de production des entreprises ;
· placement et concentration optimaux de la production ;
· l'élaboration d'un plan de transport et d'une opération de transport optimaux ;
· gestion de l'inventaire;
· et bien d'autres appartenant au domaine de la planification optimale.
2. La méthode graphique est assez simple et intuitive pour résoudre des problèmes de programmation linéaire à deux variables. Il est basé sur la représentation géométrique des solutions réalisables et des TF du problème.

L'essence de la méthode graphique est la suivante. Dans la direction (contre la direction) du vecteur dans l'ODR, le point optimal est recherché. Le point optimal est le point par lequel passe la ligne de niveau, correspondant à la plus grande (la plus petite) valeur de la fonction. La solution optimale est toujours située sur la limite de l'ODD, par exemple, au dernier sommet du polygone ODD par lequel passera la ligne cible, ou sur tout son côté.

Prenons un exemple de problème de programmation linéaire.

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 :

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.

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

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 ;

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.

Graphique 7.

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.

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.

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) ;

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.

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.

Des variables doubles supplémentaires sont également reflétées dans Rapport de durabilité dans la colonne Normir. prix Tableau 1.

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.

Un exemple de résolution d'un problème de programmation linéaire à l'aide de MS Exceller

La ferme est spécialisée dans l'agriculture en plein champ pour la production de céréales, de betteraves sucrières et de tournesols. En agriculture L'entreprise dispose de 3 200 hectares de terres arables, de ressources en main d'œuvre d'un montant de 7 000 jours-homme et d'engrais minéraux d'un montant de 15 000 c.d.w. Il est nécessaire de trouver une combinaison de superficies qui garantirait un profit maximum.

Il faut également tenir compte du fait que

- la superficie ensemencée en cultures industrielles (betteraves sucrières et tournesols) ne doit pas dépasser 25 % de la superficie totale des terres arables ;

- La ferme a conclu un contrat de vente de céréales d'un montant de 65 000 c.

Pour développer un modèle économique et mathématique, il est nécessaire de préparer les informations d'entrée (tableau 1).

Tableau 1

Indicateurs	Les cultures agricoles
Indicateurs	céréales	Betterave à sucre	tournesol
Productivité, c/ha
Prix de vente de 1 centième de produits, rub./c.
Coût des produits commercialisables pour 1 ha, en milliers de roubles.	5,59	20,62	6,73
Coûts par 1 ha : MDS, mille roubles.		12,7
travail, jours-homme
engrais minéraux, c.d.v.
Bénéficiez de 1 ha, frottez.	2,89	7,93	3,63

Comme inconnues, nous prendrons la superficie cultivée par type :

X 1 - cultures céréalières

X 2 - betteraves sucrières

X 3 - tournesol

Pour construire un modèle économique et mathématique du problème, il faut prendre en compte toutes les conditions. Dans ce cas, selon ces conditions, cinq restrictions peuvent être établies :

- la somme des superficies ensemencées en cultures agricoles ne doit pas dépasser la superficie disponible sur l'exploitation (3 200 hectares). Les coefficients des inconnues dans cette limitation caractérisent la consommation de terres arables pour 1 hectare de chaque culture. Dans ce cas, les coefficients techniques et économiques des inconnues seront égaux à un. La superficie totale des terres arables est enregistrée sur le côté droit.

1) X1+X2+X3<=3200

- la somme des superficies ensemencées en cultures industrielles ne doit pas dépasser la superficie pouvant être allouée à cet effet (3200 * 0,25 = 800 hectares). Les coefficients des inconnues de cette limitation caractérisent la consommation de terres arables allouées aux semis de cultures industrielles pour 1 hectare de chaque culture agricole industrielle. Dans ce cas, les coefficients techniques et économiques pour les inconnues X2 et X3 seront égaux à un, et pour les cultures agricoles non techniques (X3) - zéro. Sur le côté droit est inscrite la superficie maximale de terres arables pouvant être allouée à la plantation de cultures industrielles.

2) X2+X3<=800

- les troisième et quatrième restrictions garantissent que l'utilisation des ressources en main-d'œuvre et des engrais minéraux ne dépasse pas leur disponibilité sur l'exploitation. En d'autres termes, la somme des produits des taux de consommation des ressources par hectare sur la superficie ensemencée avec les cultures agricoles correspondantes ne doit pas dépasser le volume des ressources disponibles dans l'agriculture. entreprise. Les coefficients des inconnues de ces contraintes seront les taux de consommation des ressources (dans la troisième contrainte - les ressources en main d'œuvre, dans la quatrième - les engrais minéraux) pour 1 hectare de surface cultivée. Dans ce cas, les coefficients techniques et économiques sont tirés du tableau 1. La disponibilité de ces ressources sur l'exploitation est enregistrée sur le côté droit.

3) 1,5Х1+4,5Х2+1,5Х3<=7000

4) 2Х1+15Х2+2,3Х3<=15000

- la cinquième contrainte garantit la production du volume de céréales prévu. Les coefficients des variables sont le rendement en grains par hectare de superficie agricole. cultures Lorsque X1 est inconnu, il s'agit du rendement en grains (tableau 1). Pour les variables X2 et X3, ce coefficient est nul. Sur le côté droit se trouve le plan de production céréalière.

5) 26Х1>=65000

En conséquence, un système de cinq inégalités linéaires à trois inconnues est obtenu. Il est nécessaire de trouver de telles valeurs non négatives de ces inconnues X1>=0 ; X2>=0 ; X3>=0, ce qui satisferait ce système d’inégalités et assurerait un profit maximum à l’industrie de production végétale dans son ensemble :

Z max = 2,89Х1+7,93Х2+3,53Х3

Les coefficients des inconnues dans la fonction objectif sont le bénéfice tiré de 1 hectare de superficie cultivée. Ces coefficients sont calculés sur la base des données du tableau 1.

Puisque ce problème est résolu avec MS Exceller , il est alors conseillé de préparer toutes les informations d'entrée pour construire un modèle économique et mathématique à l'aide de ce tableur (Figure 1). Cela facilite non seulement les calculs de coefficients techniques et économiques et d'autres données, mais permet également à l'avenir de mettre à jour automatiquement les informations dans le modèle économique et mathématique.

Image 1

Toutes les informations développées sont résumées dans un modèle économique et mathématique détaillé et saisies dans la feuille de calcul MS. Exceller. (Fig.2.)

Figure 2

Il est recommandé de saisir les données dans le modèle sous la forme de liens vers des cellules contenant des informations pertinentes dans des feuilles de calcul ou des feuilles de calcul contenant des informations initiales. La figure 3 montre comment dans une cellule F9 des informations sont fournies sur le taux de consommation d'engrais pour 1 hectare de semis de tournesol.

figure 3

Aux colonnes UN («№»), DANS("Restrictions"), AVEC(« Unités ») etH(« Type de contrainte »), les données correspondantes sont saisies directement dans le modèle (Fig. 1). Ils ne sont pas utilisés dans les calculs et servent à des fins d'information et pour faciliter la compréhension du contenu du modèle. Vers la colonne je(« Portée des restrictions »), des liens sont saisis vers des cellules contenant des informations correspondant au nom de la colonne (les valeurs des membres droits des inégalités construites précédemment).

Pour les valeurs souhaitées des variables X1, X2, X3 nous avons laissé des cellules vides - en conséquence J5, E5, F5. Programme de cellules initialement vides MS Excel perçoit comme des cellules dont la valeur est nulle. Colonne g, appelé par nous " Somme des produits", est destiné à déterminer la somme des produits des valeurs des inconnues inconnues (cellules J5, E5, F5) et les coefficients techniques et économiques selon les restrictions correspondantes (lignes 6 à 10) et la fonction objectif (ligne 11). Ainsi, dans la colonne g défini :

- - quantité de ressources utilisées (cellule G6– superficie totale des terres arables ; G7– des terres arables pouvant être utilisées pour la plantation de cultures industrielles ; G8– les ressources en main d'œuvre ; G9– engrais minéraux) ;

- - quantité de céréales produites (cellule G10);

- - montant du bénéfice (cellule G11).

La figure 2 montre comment dans une cellule G11 l'enregistrement de la somme des produits des valeurs des variables est mis en œuvre (superficies ensemencées en cultures agricoles - cellules J5, E5, F5) pour les bénéfices correspondants de 1 hectare de leurs cultures (cellules J11, E11, F11)en utilisant la fonction MS Exceller « SOMME PRODUIT" Depuis lors de l'écriture de cette formule, l'adressage absolu aux cellules de J5 avantF5,cette formule peut être copiée vers d'autres cellules à partir deG6 avant G10.

Ainsi, un plan de référence a été construit (Fig. 2) et la première solution réalisable a été obtenue. Valeurs des inconnues X1, X2, X3 sont égaux à zéro (cellules J5, E5, F5 -cellules vides), cellules de colonne g La « somme des produits » pour toutes les contraintes (lignes 6 à 10) et la ligne cible (ligne 11) ont également des valeurs nulles.

L'interprétation économique du premier plan de base est la suivante : l'exploitation dispose de ressources, tous les coefficients techniques et économiques ont été calculés, mais le processus de production n'a pas encore commencé ; les ressources n’ont pas été utilisées et, par conséquent, il n’y a eu aucun profit.

Pour optimiser le plan existant, nous utiliserons l'outil Trouver une solution qui est dans le menu Service. S'il n'y a pas de commande de ce type dans le menu Service, requis au point Superstructure coche la case Trouver une solution. Après cela, cette procédure deviendra disponible dans le menu Service.

Après avoir sélectionné cette commande, une boîte de dialogue apparaîtra (Fig. 4).

Figure 4

Puisque nous avons choisi la maximisation du profit comme critère d'optimisation, dans le domaine Définir la cellule cible Entrez un lien vers la cellule contenant la formule de calcul du profit. Dans notre cas c'est la cellule $G$11. Maximiser la valeur de la cellule finale en modifiant les valeurs des cellules d'influence (les cellules d'influence, dans ce cas ce sont les cellules changeantes, sont les cellules qui sont conçues pour stocker les valeurs des inconnues inconnues), placez l'interrupteur sur la position valeur maximum;

Sur le terrain Changer de cellule entrez les références aux cellules à modifier, en les séparant par des virgules ; ou, si les cellules sont adjacentes, en indiquant la première et la dernière cellule, en les séparant par deux points ( $ D$5 : $F$5).

Sur le terrain Restrictions saisir toutes les restrictions imposées à la recherche d'une solution. Considérons l'ajout d'une contrainte en utilisant l'exemple de l'ajout de la première contrainte sur la superficie totale des terres arables.

Au chapitre Restrictions boite de dialogue Trouver une solution cliquez sur le bouton Ajouter. La boîte de dialogue suivante apparaîtra (Fig. 5)

Figure 5

Sur le terrain Référence de cellule Entrez l'adresse de la cellule dont la valeur est contrainte. Dans notre cas, c'est la cellule $ 6$G, où est la formule de calcul des terres arables utilisée dans le plan actuel.

Sélectionnez une instruction conditionnelle dans la liste déroulante <= , qui doit être situé entre le lien et la contrainte.

Sur le terrain Limitation Entrez un lien vers la cellule qui contient la valeur de la disponibilité des terres arables sur l'exploitation, ou un lien vers cette valeur. Dans notre cas, c'est la cellule $ je 6$

En conséquence, la boîte de dialogue prendra la forme suivante (Fig. 6).

Figure 6

Pour accepter la restriction et commencer à en saisir une nouvelle, cliquez sur le bouton Ajouter. D'autres restrictions sont introduites de la même manière. Pour revenir à la boîte de dialogue Trouver une solution, appuie sur le bouton D'ACCORD.

Après avoir suivi les instructions ci-dessus, la boîte de dialogueTrouver une solutionaura la forme suivante (Fig. 7).

Figure 7

Pour modifier ou supprimer des restrictions dans la liste Restrictions boite de dialogue Trouver une solution spécifiez la restriction que vous souhaitez modifier ou supprimer. Sélectionnez une équipe Changement et apportez des modifications ou cliquez sur le bouton Supprimer.

Case à cocher Modèle linéaire dans la boîte de dialogue Possibilités Trouver une solution(Fig. 8) vous permet de définir n'importe quel nombre de restrictions. Case à cocher Valeurs non négatives nous permettra de respecter la condition de non-négativité des variables (lors de la résolution de notre problème, cela est obligatoire). Vous pouvez laisser les paramètres restants inchangés ou définir les paramètres dont vous avez besoin, en utilisant l'aide si nécessaire.

Figure 8

Pour démarrer la tâche de solution, cliquez sur le bouton Exécuter et effectuez l'une des opérations suivantes :

- pour restaurer les données d'origine, sélectionnez l'option Restaurer les valeurs d'origine.

Figure 9

Pour arrêter la recherche d'une solution, appuyez sur la touche ÉCHAP.

La feuille Microsoft Excel sera recalculée en tenant compte des valeurs trouvées des cellules d'influence. Suite à la résolution et à l'enregistrement des résultats de la recherche sur la feuille, le modèle prendra la forme suivante (tableau 10).

Figure 10

Dans les cellules J5-F5 les valeurs des inconnues requises sont obtenues (la superficie cultivée est égale à : céréales - 2500 ha, betterave sucrière - 661 ha, tournesol - 39 ha), en cellules G6-G9 les volumes de ressources utilisées ont été déterminés (superficie totale des terres arables - 3200 hectares ; superficie des terres arables pouvant être utilisées pour semer des cultures industrielles - 700 hectares ; main d'œuvre - 6781,9 jours-homme ; engrais minéraux - 15000 c.d.v.) , en cellule G10 la quantité de céréales produites a été établie (65 000 centièmes). Avec toutes ces valeurs, le bénéfice atteint 12 603,5 mille roubles. (cellule G11).

Si la recherche n'a pas trouvé de solution satisfaisant aux conditions spécifiées, dans la boîte de dialogue Résultats de la recherche de solutions un message correspondant apparaîtra (Fig. 11).

Figure 11

L'une des raisons les plus courantes de l'impossibilité de trouver une solution optimale est la situation dans laquelle, à la suite de la résolution d'un problème, il s'avère qu'il existe des restrictions qui ne sont pas respectées. Après avoir enregistré la solution trouvée sur la feuille, vous devez comparer ligne par ligne les valeurs obtenues des colonnes « Somme des produits » et « Volume des contraintes » et vérifier si la relation entre elles satisfait la contrainte dans le « Type de Colonne Contraintes ». Ayant ainsi constaté des restrictions non respectées, il faut rechercher et éliminer les raisons qui rendent impossible le respect de cette condition spécifique (cela peut être par exemple des volumes de restrictions trop importants ou, à l'inverse, très faibles, prévus, etc.).

S'il y a beaucoup de restrictions dans le modèle, il est alors visuellement assez difficile de comparer et de vérifier l'exactitude de chaque ligne. Pour faciliter les choses, il est recommandé d'ajouter une autre colonne « Validation » au modèle, où l'utilisation des fonctions MS Exceller « SI" Et " ROND» vous pouvez organiser un contrôle automatique (Fig. 12).

Figure 12

Site sur l'informatique

Saisir les conditions de la tâche

Résoudre un problème de programmation linéaire

Analyse de la solution optimale

Créons un problème double pour le problème d'origine et introduisons des variables doubles supplémentaires v i .

Saisir les conditions de la tâche

Résoudre un problème de programmation linéaire

Analyse de la solution optimale

Créons un problème double pour le problème d'origine et introduisons des variables doubles supplémentaires v i .

ARTICLES LIÉS