Programmation linéaire avec sélection d'une grandeur spécifique. Le concept de programmation linéaire. types de problèmes de programmation linéaire

La programmation linéaire est une branche des mathématiques qui étudie les méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre des variables et un critère d'optimalité linéaire.

Quelques mots sur le terme programmation linéaire lui-même. Cela nécessite une compréhension correcte. Dans ce cas, la programmation n’est bien entendu pas la compilation de programmes informatiques. Ici, la programmation doit être interprétée comme la planification, l'élaboration de plans, l'élaboration d'un programme d'action.

Les problèmes mathématiques de programmation linéaire comprennent des études de situations de production et économiques spécifiques, qui, sous une forme ou une autre, sont interprétées comme des problèmes d'utilisation optimale de ressources limitées.

L'éventail des problèmes résolus à l'aide des méthodes de programmation linéaire est assez large. C'est par exemple :

· le problème de l'utilisation optimale des ressources dans la planification de la production ;

· problème de mélange (planification de la composition du produit) ;

· le problème de trouver la combinaison optimale de différents types de produits à stocker dans les entrepôts (gestion des stocks ou « problème du sac à dos ») ;

· tâches de transport (analyse de la localisation de l'entreprise, mouvement des marchandises).

La programmation linéaire est la section la plus développée et la plus utilisée de la programmation mathématique (elle comprend en outre : la programmation entière, dynamique, non linéaire et paramétrique). Ceci s'explique comme suit :

· les modèles mathématiques d'un grand nombre de problèmes économiques sont linéaires par rapport aux variables requises ;

· ce type de problème est actuellement le plus étudié. Des méthodes spéciales ont été développées à cet effet, à l'aide desquelles ces problèmes sont résolus, ainsi que des programmes informatiques correspondants ;

· de nombreux problèmes de programmation linéaire, après avoir été résolus, ont trouvé de nombreuses applications ;

· certains problèmes qui, dans la formulation originale, ne sont pas linéaires, après un certain nombre de restrictions et d'hypothèses supplémentaires, peuvent devenir linéaires ou être réduits à une forme telle qu'ils peuvent être résolus par des méthodes de programmation linéaire.

Le modèle économique et mathématique de tout problème de programmation linéaire comprend : une fonction objectif dont il faut trouver la valeur optimale (maximale ou minimale) ; restrictions sous la forme d'un système d'équations linéaires ou d'inégalités ; exigence de non-négativité des variables.

En général, le modèle s'écrit comme suit :

fonction objectif :

F = c1x1 + c2x2 + ... + cnxn → max(min);

restrictions :

a11x1 + a12x2 + ... + a1nxn (≤ = ≥) b1,

a21x1 + a22x2 + ... + a2nxn (≤ = ≥) b2,

am1x1 + am2x2 + ... + amnxn (≤ = ≥) bm;

exigence de non-négativité :

Le problème est de trouver la valeur optimale de la fonction tout en satisfaisant les contraintes.

Donc, La programmation linéaire est une branche de la programmation mathématique qui étudie les méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre des variables et un critère linéaire.

Une condition nécessaire pour poser un problème de programmation linéaire sont les restrictions sur la disponibilité des ressources, le montant de la demande, la capacité de production de l'entreprise et d'autres facteurs de production.

L'essence de la programmation linéaire est de trouver les points de la plus grande ou de la plus petite valeur d'une certaine fonction sous un certain ensemble de restrictions imposées aux arguments et formant un système de restrictions qui, en règle générale, a un nombre infini de solutions. Chaque ensemble de valeurs de variables (arguments de la fonction F) qui satisfont le système de contraintes est appelé plan admissible du problème de programmation linéaire. La fonction F dont le maximum ou le minimum est déterminé est appelée fonction objectif du problème. Un plan admissible sur lequel le maximum ou le minimum de la fonction F est atteint est appelé plan optimal du problème.

Le système de restrictions qui détermine de nombreux plans est dicté par les conditions de production. La tâche de la programmation linéaire (LP) est de sélectionner le plan le plus rentable (optimal) parmi un ensemble de plans réalisables.

Méthode simplexe est le principal dans programmation linéaire . La résolution du problème commence par la considération de l'un des sommets du polyèdre des conditions. Si le sommet étudié ne correspond pas au maximum (minimum), alors ils se déplacent vers le voisin, augmentant la valeur de la fonction objectif lors de la résolution du problème pour le maximum et la diminuant lors de la résolution du problème pour le minimum. Ainsi, passer d’un sommet à un autre améliore la valeur de la fonction objectif. Étant donné que le nombre de sommets du polyèdre est limité, en un nombre fini d'étapes, il est garanti de trouver la valeur optimale ou d'établir le fait que le problème est insoluble.

Cette méthode est universelle, applicable à tout problème de programmation linéaire dans forme canonique. Le système de contraintes est ici un système d'équations linéaires dans lequel le nombre d'inconnues est supérieur au nombre d'équations. Si le rang du système est r , alors nous pouvons choisir r inconnues, que nous exprimerons à travers les inconnues restantes. Pour plus de précision, nous supposons que les premières inconnues consécutives sont sélectionnées X 1 , X 2 , ..., Xr . Alors notre système d’équations peut s’écrire

Il peut être amené à cette forme tout système commun , par exemple, par la méthode gaussienne. Certes, il n'est pas toujours possible de l'exprimer en termes des premières r inconnues restantes (nous l'avons fait pour la précision de la notation). Cependant, un tel r il y aura certainement des inconnues. Ces inconnues (variables) sont dites basiques, le reste est libre.

En attribuant certaines valeurs aux variables libres et en calculant les valeurs des variables de base (exprimées en termes de variables libres), nous obtiendrons différentes solutions à notre système de contraintes. Ainsi, n’importe quelle solution peut être obtenue. Nous nous intéresserons aux solutions particulières obtenues dans le cas où les variables libres sont égales à zéro. De telles solutions sont appelées basique, il y en a autant qu'il existe de différents types fondamentaux d'un système de restrictions donné. La solution de base s'appelle solution de base admissible ou solution de référence, si les valeurs des variables qu'il contient ne sont pas négatives. Si les variables sont considérées comme fondamentales X 1 , X 2 , ..., Xr , alors la solution (b 1 , b 2 ,..., b r , 0, ..., 0) apportera son soutien à condition que b 1 , b 2 ,..., b r ≥ 0 .

La méthode du simplexe est basée sur un théorème appelé théorème fondamental de la méthode du simplexe. Parmi les plans optimaux d’un problème de programmation linéaire sous forme canonique il existe nécessairement une solution de référence à son système de contraintes. Si le plan optimal du problème est unique, alors il coïncide avec une solution de référence. Il existe un nombre fini de solutions différentes de support au système de contraintes. Ainsi, une solution au problème sous forme canonique pourrait être recherchée en énumérant les solutions de référence et en choisissant parmi elles celle pour laquelle la valeur F le plus grand. Mais, premièrement, toutes les solutions de référence sont inconnues et doivent être trouvées, et, deuxièmement, dans les problèmes réels, il existe un grand nombre de ces solutions et une recherche directe est difficilement possible. La méthode simplexe est une certaine procédure d'énumération dirigée des solutions de support. Sur la base d'une certaine solution de référence trouvée à l'avance à l'aide d'un certain algorithme de la méthode simplexe, nous calculons une nouvelle solution de référence sur laquelle la valeur de la fonction objectif F pas moins que l'ancien. Après une série d’étapes, nous arrivons à une solution de référence, qui est le plan optimal.

Ainsi, la méthode du simplexe introduit un certain ordre à la fois lors de la recherche de la première solution de base (initiale) et lors du passage à d'autres solutions de base. Son idée est la suivante.

Ayant système de restrictions , réduit à une forme générale, c'est-à-dire à un système de m équations linéaires avec n variables (m< n) , trouver n'importe quelle solution de base ce système, en ne se souciant que de le trouver le plus simplement possible.

Si la première solution de base trouvée s'avérait être acceptable , puis vérifie-le optimalité. Si c'est pas optimal , alors un passage à un autre s'effectue, nécessairement solution de base admissible .

La méthode du simplexe garantit qu'avec cette nouvelle solution la forme linéaire, si elle n'atteint pas l'optimum, s'en rapprochera. Ils font de même avec la nouvelle solution de base réalisable jusqu’à ce qu’ils trouvent une solution optimale.

Si la première solution de base trouvée s'avère être inacceptable , alors en utilisant la méthode du simplexe, il est possible de transition vers d'autres solutions de base, qui nous rapprochent de la région des solutions admissibles, jusqu'à ce qu'à une étape de décision soit la solution de base s'avère admissible et l'algorithme de la méthode simplex lui soit appliqué, soit nous sommes convaincus de l'incohérence du système de restrictions.

Ainsi, l'application de la méthode du simplexe se divise en deux étapes : trouver une solution fondamentale admissible au système de contraintes ou établir le fait de son incompatibilité ; trouver la solution optimale.
De plus, chaque étape peut comprendre plusieurs étapes correspondant à l'une ou l'autre solution de base. Mais comme le nombre de solutions de base est toujours limité, le nombre d’étapes de la méthode du simplexe est également limité.

Le schéma donné de la méthode simplex exprime clairement sa nature algorithmique (la nature d'une instruction claire sur l'exécution d'opérations séquentielles), ce qui permet de programmer et de mettre en œuvre avec succès cette méthode sur un ordinateur. Les problèmes avec un petit nombre de variables et de contraintes peuvent être résolus manuellement à l'aide de la méthode du simplexe.

Sans nous attarder plus en détail sur l'essence de l'algorithme, nous décrirons son côté informatique. Calculs utilisant la méthode simplexe sont organisés sous la forme tableaux simplexes, qui sont une représentation abrégée du problème de programmation linéaire sous forme canonique. Avant de compiler tableaux simplexes la tâche devrait être converti , système de restrictions réduit à forme de base acceptable, à l'aide duquel les variables de base doivent être exclues de la fonction cible. Nous examinerons ci-dessous la question de ces transformations préliminaires. Nous supposerons maintenant qu'ils ont déjà été terminés et que la tâche a la forme suivante.

La programmation linéaire est considérée comme une réalisation révolutionnaire qui a donné à l'homme la capacité de formuler des objectifs généraux et de trouver, grâce à la méthode du simplexe, des solutions optimales à une large classe de problèmes pratiques de prise de décision d'une grande complexité.

Programmation linéaire– une discipline mathématique consacrée à la théorie et aux méthodes de résolution de problèmes sur les extrema des fonctions linéaires sur les ensembles n-espace vectoriel dimensionnel défini par des systèmes d'équations linéaires et d'inégalités.

On peut dire que programmation linéaire applicable à la résolution de modèles mathématiques de ces processus et systèmes qui peuvent être basés sur l'hypothèse d'une représentation linéaire du monde réel.

Problème de programmation linéaire(LP), consiste à trouver le minimum (ou maximum) d'une fonction linéaire sous contraintes linéaires.

La programmation linéaire est utilisée pour résoudre les problèmes économiques suivants :

1. Le problème de la gestion et de la planification de la production.

2. Problèmes de détermination du placement optimal des équipements sur les navires et dans les ateliers.

3. Le problème de la détermination du plan optimal de transport de marchandises (problème de transport).

4. Le problème de la répartition optimale du personnel.

5. Problèmes de mélanges, d’alimentation (planification de la composition des produits), etc.

3. MODÈLE DE PROGRAMMATION LINÉAIRE, SA REPRÉSENTATION DANS LES TABLEAUX ÉLECTRONIQUES MS EXCEL.

Traditionnellement, les sciences de gestion font référence à la construction de modèles détaillés, à la suite de l'analyse desquels sont prises les décisions de gestion. Aujourd'hui, des millions de managers utilisent des feuilles de calcul pour analyser les problèmes de leur entreprise. Les feuilles de calcul modernes disposent de nombreux outils puissants qui peuvent être utilisés pour analyser les modèles avec plus de précision, ce qui permet de prendre de meilleures décisions, plus proches de l'optimum. Avec l'utilisation croissante des feuilles de calcul dans le processus de gestion, les futurs professionnels doivent posséder des compétences en développement de modèles professionnels - comment « planifier » une feuille de travail vierge afin d'obtenir un modèle utile et pratique d'une situation commerciale sans se plonger dans les subtilités algorithmiques et mathématiques. des calculs.

Les principales étapes pour créer un modèle de programmation linéaire dans Excel :

1. Ecrire et tester un modèle de programmation linéaire symbolique. Le modèle est écrit sur papier sous forme mathématique.

2. Création et débogage d'un modèle de programmation linéaire tabulaire. A partir du modèle symbolique du produit médicamenteux, sa représentation est créée dans Excel .

3. Une tentative d'optimisation du modèle à l'aide du module complémentaire SOLUTION SEARCH.

4. UTILISER LE ADD-ON À LA RECHERCHE D'UNE SOLUTION.

À l'aide de feuilles de calcul, vous pouvez simuler des situations réelles et évaluer les résultats. En d'autres termes, à l'aide de feuilles de calcul, vous pouvez analyser les résultats des opérations et prédire les perspectives futures de l'entreprise. Ces tâches dans l'environnement MS Excel permet de résoudre avec le complément Rechercher une solution.

Trouver une solution – Il s'agit d'un module complémentaire conçu pour optimiser les modèles en présence de contraintes. Il se compose de deux composants logiciels : un programme écrit en Visual Basic, qui traduit les informations présentées sur la lettre de travail pour une représentation interne, qui est utilisée par un autre programme. Le deuxième programme se trouve dans la mémoire de l'ordinateur en tant que module logiciel distinct. Il effectue l'optimisation et renvoie la solution trouvée au premier programme, qui reprend les données de la feuille de calcul. En l'utilisant, vous pouvez trouver la valeur optimale de la formule, qui est stockée dans la cellule cible. Cette procédure fonctionne sur un groupe de cellules directement liées à une formule dans la cellule cible. Pour obtenir un résultat de formule dans une cellule cible, la procédure modifie la valeur dans les cellules qui affectent la recherche. Afin de réduire la pluralité de valeurs utilisées dans le modèle de problème, une contrainte est appliquée. Ces contraintes peuvent contenir une référence à d'autres cellules qui affectent la recherche.

Algorithme général pour travailler avec le complément Trouver une solution.

1. Au menu Service sélectionner une équipe Trouver une solution.
2. Dans le champ Définit la cellule cible Saisissez l'adresse de la cellule contenant la formule pour optimiser le modèle.
3. Pour maximiser la valeur d'une cellule cible en modifiant les valeurs des cellules d'influence, réglez le commutateur sur Valeur maximale. Pour minimiser la valeur de la cellule cible en modifiant les valeurs des cellules d'influence, réglez le commutateur sur Valeur minimale. Pour que la cellule cible acquière la valeur d'un nombre spécifique, placez le commutateur sur la position Signification et entrez le numéro approprié.
4. Dans le champ Changer de cellule Saisissez les adresses des cellules dont les valeurs changent, en les séparant par des virgules. Les cellules modifiées doivent être directement ou indirectement liées à la cellule cible. Jusqu'à 200 cellules variables peuvent être installées.
5. Dans le champ Restrictions saisissez toutes les restrictions imposées à la recherche d'une solution.
6. Cliquez sur le bouton Exécuter.
7. Pour enregistrer la solution trouvée, sélectionnez le commutateur dans la boîte de dialogue Résultats de la recherche de solutions positionner Enregistrez la solution trouvée. Pour reprendre les données saisies, réglez le commutateur sur Restaurer les valeurs d'origine.
8. Pour interrompre la recherche d'une solution, appuyez sur la touche Esс. MS Excel recalculera la feuille en tenant compte des valeurs de cellules trouvées qui affectent le résultat.

Algorithme robotique avec Nadbudova Trouver une solution.

5. RÉSOLUTION D'UN PROBLÈME DE PROGRAMMATION LINÉAIRE À L'AIDE D'UN PROGRAMME MS EXCEL.

Exemple. Confiserie pour réaliser trois types de caramel A, B, C utilise trois principaux types de matières premières : le sucre, la mélasse et la purée de fruits. Consommation standard de sucre pour la production de 1 kg de caramel de chaque type, respectivement, niveaux : 0,8 kg ; 0,5 kg ; 0,6 kg ; mélasse – 04 kg ; 0,4kg ; 0,3kg ; purée de fruits – 0 kg ; 0,1kg ; 0,1 kg. Les confiseries peuvent être produites en toutes quantités (les ventes sont garanties), mais l'approvisionnement en matières premières est limité : réserves de sucre - 80 kg, mélasse - 60 kg, purée de fruits - 12 kg. Bénéfice de la vente de 1 kg de caramel UN est de 10 UAH, tapez DANS – 11 UAH, tapez AVEC – 12 UAH.

Tableau 1

Déterminez un plan de production de caramel qui garantit un profit maximal des activités de la confiserie.

Si un problème de programmation linéaire ne comporte que deux variables, il peut alors être résolu graphiquement.

Considérons un problème de programmation linéaire à deux variables et :
(1.1) ;
(1.2)
Ici, il y a des nombres arbitraires. La tâche peut consister soit à trouver le maximum (max), soit à trouver le minimum (min). Le système de restrictions peut contenir à la fois des signes et des signes.

Construction du domaine des solutions réalisables

La méthode graphique pour résoudre le problème (1) est la suivante.
Tout d’abord, nous dessinons les axes de coordonnées et sélectionnons l’échelle. Chacune des inégalités du système de contraintes (1.2) définit un demi-plan délimité par la droite correspondante.

Donc la première inégalité
(1.2.1)
définit un demi-plan délimité par une droite.

D'un côté de cette ligne droite, et de l'autre côté.

Sur la ligne très droite.

Pour savoir de quel côté l’inégalité (1.2.1) est vraie, nous choisissons un point arbitraire qui ne se trouve pas sur la droite. Ensuite, nous substituons les coordonnées de ce point dans (1.2.1). Si l'inégalité est vraie, alors le demi-plan contient le point sélectionné. Si l'inégalité n'est pas vérifiée, alors le demi-plan est situé de l'autre côté (ne contient pas le point sélectionné). Ombrez le demi-plan pour lequel l’inégalité (1.2.1) est valable.
(2)
Nous faisons de même pour les inégalités restantes du système (1.2). De cette façon, nous obtenons des demi-plans ombrés. Les points de la région des solutions réalisables satisfont toutes les inégalités (1.2). Par conséquent, graphiquement, la région des solutions réalisables (ADA) est l’intersection de tous les demi-plans construits. Ombrage de l'ODR. C'est un polygone convexe dont les faces appartiennent aux droites construites. Aussi, un ODF peut être une figure convexe illimitée, un segment, un rayon ou une ligne droite.

Il peut également arriver que les demi-plans ne contiennent pas de points communs. Alors le domaine des solutions réalisables est l’ensemble vide. Ce problème n'a pas de solutions.

La méthode peut être simplifiée. Vous n’êtes pas obligé d’ombrer chaque demi-plan, mais construisez d’abord toutes les lignes droites.

Ensuite, sélectionnez un point arbitraire qui n’appartient à aucune de ces lignes. Remplacez les coordonnées de ce point dans le système d’inégalités (1.2). Si toutes les inégalités sont satisfaites, alors la région des solutions réalisables est limitée par les droites construites et inclut le point sélectionné. Nous ombrons la région des solutions réalisables le long des limites des lignes afin qu'elle inclue le point sélectionné.

Si au moins une inégalité n’est pas satisfaite, choisissez un autre point. Et ainsi de suite jusqu'à ce qu'un point soit trouvé dont les coordonnées satisfont au système (1.2).
(1.1) .

Trouver l'extremum de la fonction objectif
(3) .
Pour faciliter la présentation, nous supposons que cette droite passe par l’ODR. Sur cette ligne la fonction objectif est constante et égale à .
.
une telle ligne droite est appelée ligne de niveau de fonction.
.
Cette droite divise le plan en deux demi-plans. Sur un demi-plan

Sur un autre demi-avion

Autrement dit, d’un côté de la droite (3), la fonction objectif augmente. Et plus on éloigne le point de la droite (3), plus la valeur sera grande.

De l’autre côté de la droite (3), la fonction objectif diminue. Et plus nous déplaçons le point de la droite (3) vers l’autre côté, plus la valeur sera petite.
.
Si nous traçons une droite parallèle à la droite (3), alors la nouvelle droite sera également une droite de niveau de la fonction objectif, mais avec une valeur différente.
.

Ainsi, pour trouver la valeur maximale de la fonction objectif, il faut tracer une droite parallèle à la droite (3), aussi loin que possible de celle-ci dans le sens des valeurs croissantes, et passant par au moins un point de l'ODD. Pour trouver la valeur minimale de la fonction objectif, il faut tracer une droite parallèle à la droite (3) et aussi éloignée que possible de celle-ci dans le sens des valeurs décroissantes, et passant par au moins un point de l'ODD.
.
Si l'ODR est illimité, il peut alors arriver qu'une telle ligne directe ne puisse pas être tracée. Autrement dit, quelle que soit la manière dont nous supprimons la ligne droite de la ligne de niveau (3) dans le sens croissant (décroissant), la ligne droite passera toujours par l'ODR. Dans ce cas, il peut être arbitrairement grand (petit). Il n’y a donc pas de valeur maximale (minimale). Le problème n'a pas de solutions.

Considérons le cas où la ligne extrême parallèle à une ligne arbitraire de la forme (3) passe par un sommet du polygone ODR. A partir du graphique, nous déterminons les coordonnées de ce sommet. Ensuite, la valeur maximale (minimale) de la fonction objectif est déterminée par la formule :

La solution au problème est

L'entreprise produit des robes de deux modèles A et B. Trois types de tissus sont utilisés. Pour réaliser une robe du modèle A, il faut 2 m de tissu du premier type, 1 m de tissu du deuxième type, 2 m de tissu du troisième type. Pour réaliser une robe du modèle B, il faut 3 m de tissu du premier type, 1 m de tissu du deuxième type, 2 m de tissu du troisième type. Les stocks de tissu du premier type sont de 21 m, du deuxième type - 10 m, du troisième type - 16 m. La sortie d'un produit de type A rapporte un revenu de 400 deniers. unités, un produit de type B - 300 den. unités

Élaborer un plan de production qui procure à l'entreprise les revenus les plus élevés. Résolvez le problème graphiquement.

Solution

Soit les variables et désignant le nombre de robes produites, modèles A et B, respectivement. Alors la quantité de tissu du premier type consommée sera :
(m)
La quantité de tissu du deuxième type consommée sera :
(m)
La quantité de tissu du troisième type consommée sera :
(m)
Puisque le nombre de robes produites ne peut pas être négatif, alors
Et .
Les revenus des robes produites seront de :
(den. unités)

Alors le modèle économico-mathématique du problème a la forme :

Nous le résolvons graphiquement.
Nous dessinons les axes de coordonnées et .

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (0 ; 7) et (10,5 ; 0).

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (0 ; 10) et (10 ; 0).

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (0 ; 8) et (8 ; 0).

Nous ombrons la zone pour que le point (2 ; 2) tombe dans la partie ombrée. On obtient le quadrilatère OABC.

(A1.1) .
À .
À .
Tracez une ligne droite passant par les points (0 ; 4) et (3 ; 0).

On remarque en outre que les coefficients de et de la fonction objectif étant positifs (400 et 300), celle-ci augmente au fur et à mesure.
.

On trace une droite parallèle à la droite (A1.1), aussi éloignée que possible de celle-ci dans le sens croissant, et passant par au moins un point du quadrilatère OABC. Une telle ligne passe par le point C. A partir de la construction nous déterminons ses coordonnées.

Solution au problème : ;

.
Répondre

Autrement dit, pour obtenir le revenu le plus élevé, il faut confectionner 8 robes du modèle A. Le revenu sera de 3200 den. unités

La solution au problème est

Exemple 2

Solution

Nous le résolvons graphiquement.
Nous dessinons les axes de coordonnées et .

Nous construisons une ligne droite.
À .
À .
Résolvez graphiquement un problème de programmation linéaire.

Nous construisons une ligne droite.
Tracez une ligne droite passant par les points (0 ; 6) et (6 ; 0).
À .
À .
D'ici.

Nous construisons une ligne droite.
Tracez une ligne droite passant par les points (3 ; 0) et (7 ; 2).

Nous construisons une ligne droite (axe des abscisses).

La région des solutions admissibles (ADA) est limitée par les lignes droites construites. Pour savoir de quel côté, on remarque que le point appartient à l'ODR, puisqu'il satisfait le système d'inégalités :

Nous construisons une ligne arbitraire du niveau de la fonction objectif, par exemple,
.
À .
À .
Tracez une ligne droite de niveau passant par les points (0 ; 6) et (4 ; 0).
Puisque la fonction objectif augmente avec l'augmentation de et , on trace une droite parallèle à la ligne de niveau et aussi éloignée que possible de celle-ci dans le sens croissant , et passant par au moins un point du triangle ABC. Une telle ligne passe par le point C. A partir de la construction nous déterminons ses coordonnées.
.

On trace une droite parallèle à la droite (A1.1), aussi éloignée que possible de celle-ci dans le sens croissant, et passant par au moins un point du quadrilatère OABC. Une telle ligne passe par le point C. A partir de la construction nous déterminons ses coordonnées.

Solution au problème : ;

Exemple de non-solution

La solution au problème est

Résolvez graphiquement un problème de programmation linéaire. Trouvez la valeur maximale et minimale de la fonction objectif.

Solution

Nous résolvons le problème graphiquement.
Nous dessinons les axes de coordonnées et .

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (0 ; 8) et (2,667 ; 0).

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (0 ; 3) et (6 ; 0).

Nous construisons une ligne droite.
À .
À .
Tracez une ligne droite passant par les points (3 ; 0) et (6 ; 3).

Les lignes droites sont les axes de coordonnées.

La région des solutions admissibles (ADA) est limitée par les lignes droites et les axes de coordonnées construits. Pour savoir de quel côté, on remarque que le point appartient à l'ODR, puisqu'il satisfait le système d'inégalités :

Nous ombrons la zone pour que le point (3 ; 3) tombe dans la partie ombrée. On obtient une aire illimitée délimitée par la ligne brisée ABCDE.

Nous construisons une ligne arbitraire du niveau de la fonction objectif, par exemple,
(A3.1) .
À .
À .
Tracez une ligne droite passant par les points (0 ; 7) et (7 ; 0).
Puisque les coefficients de et sont positifs, il augmente avec l'augmentation de et .

Pour trouver le maximum, il faut tracer une ligne parallèle la plus éloignée possible dans le sens croissant et passant par au moins un point de la région ABCDE. Cependant, comme l'aire est illimitée du côté des grandes valeurs de et , une telle ligne droite ne peut pas être tracée. Quelle que soit la ligne droite que nous traçons, il y aura toujours des points dans la région qui sont plus éloignés dans le sens croissant et .

Il n’y a donc pas de maximum. vous pouvez le rendre aussi grand que vous le souhaitez.
.
Nous recherchons le minimum. On trace une droite parallèle à la droite (A3.1) et aussi éloignée que possible de celle-ci dans le sens décroissant, et passant par au moins un point de la région ABCDE. Une telle ligne passe par le point C. A partir de la construction nous déterminons ses coordonnées.

Solution au problème : ;

Valeur minimale de la fonction objectif :
Il n'y a pas de valeur maximale.
.

Valeur minimale

15. Méthodes analytiques. Méthodes de programmation linéaire.

Tout au long de son évolution, l'homme, lorsqu'il accomplissait certaines actions, a cherché à se comporter de telle manière que le résultat obtenu à la suite d'une action se révèle, dans un certain sens, le meilleur. En se déplaçant d'un point à un autre, il cherchait à trouver le chemin le plus court possible. Lors de la construction d'une habitation, il recherchait une géométrie qui offrirait des conditions de vie acceptables avec la moindre consommation de carburant. En construisant des navires, il essayait de leur donner une forme dans laquelle l'eau offrirait le moins de résistance. La liste d’exemples similaires peut facilement être poursuivie.

Les meilleures solutions aux problèmes dans un certain sens sont généralement appelées optimal. Actuellement, aucun problème plus ou moins complexe ne peut être résolu sans l'utilisation de principes d'optimisation. Lors de la définition et de la résolution de problèmes d'optimisation, deux questions se posent : quoi et comment optimiser ?

La réponse à la première question est obtenue grâce à une étude approfondie du problème à résoudre. Le paramètre qui détermine le degré de perfection de la solution au problème posé est identifié. Ce paramètre est généralement appelé fonction cible ou critère de qualité. Ensuite, un ensemble de quantités est établi qui détermine la fonction objectif. Enfin, toutes les contraintes qui doivent être prises en compte lors de la résolution du problème sont formulées. Après cela, un modèle mathématique est construit, qui consiste à établir la dépendance analytique de la fonction objectif à l'égard de tous les arguments et la formulation analytique des contraintes associées au problème. Ensuite, nous commençons à chercher une réponse à la deuxième question.

Ainsi, à la suite de la formalisation du problème appliqué, il est établi que la fonction objectif est , où l'ensemble X est une généralisation de restrictions, on l'appelle l'ensemble des solutions réalisables. L'essence du problème d'optimisation est de rechercher une telle solution sur l'ensemble X - l'ensemble des solutions réalisables
, auquel la fonction cible f atteint sa valeur minimale ou maximale.

La programmation linéaire fait partie intégrante des méthodes d'optimisation.

15.2. Concepts de base de la programmation linéaire

La première mention (1938) des méthodes mathématiques de gestion efficace de la production appartient au mathématicien soviétique L. V. Kantorovich. Un an plus tard, en 1939, L. V. Kantorovitch publie l'ouvrage « Méthodes mathématiques d'organisation et de planification de la production » et applique dans la pratique les résultats obtenus. Le terme « programmation linéaire » a été introduit par les mathématiciens américains J. Danzig et T. Koopmans à la fin des années 40. J. Dantzig a développé l'appareil mathématique de la méthode simplex pour résoudre des problèmes de programmation linéaire (1951). La méthode du simplexe est utilisée pour résoudre un large éventail de problèmes de programmation linéaire et reste l’une des méthodes principales.

La programmation linéaire est une branche des mathématiques axée sur la recherche d'un extremum (maximum ou minimum) dans des problèmes décrits par des équations linéaires. De plus, les équations linéaires décrivent à la fois la fonction objectif elle-même et les paramètres d'entrée (variables) ainsi que les conditions de restrictions sur les paramètres d'entrée. Une condition nécessaire aux problèmes de programmation linéaire est la présence obligatoire de restrictions sur les ressources (matières premières, matériaux, financement, demande de produits manufacturés, etc.). Une autre condition importante pour résoudre le problème est le choix du critère d'arrêt de l'algorithme, c'est-à-dire la fonction objectif doit être optimale dans un certain sens. L'optimalité de la fonction objectif doit être exprimée quantitativement. Si la fonction cible est représentée par une ou deux équations, de tels problèmes peuvent en pratique être résolus assez facilement. Le critère d’arrêt de l’algorithme (ou critère d’optimalité) doit satisfaire aux exigences suivantes :

être le seul pour une tâche donnée ;

mesuré en unités de quantité ;

dépendent linéairement des paramètres d’entrée.

Sur la base de ce qui précède, nous pouvons formuler le problème de programmation linéaire sous forme générale :

trouver l'extremum de la fonction objectif

sous restrictions sous forme d’égalités :

(2.2)

soumis à des restrictions sous forme d’inégalités :

(2.3)

et conditions de non négativité des paramètres d'entrée :

En bref, le problème de programmation linéaire peut s’écrire comme suit :

(2.5)

étant donné que

Où
- variables d'entrée ;

Les nombres sont positifs, négatifs et égaux à zéro.

Sous forme matricielle, ce problème peut s’écrire comme suit :

Les problèmes de programmation linéaire peuvent être résolus de manière analytique et graphique.

15.3. Problème de programmation linéaire canonique

, je=1,…,m,

, j=1,…,n.

Les principales méthodes informatiques permettant de résoudre des problèmes de programmation linéaire ont été développées spécifiquement pour le problème canonique.

15.4. Problème général de programmation linéaire

Il faut maximiser (minimiser) une fonction linéaire de n variables.

sous restrictions

, je=1,…, k,

, je=1+ k,…, m,

, …,

Ici k≤ m, r≤ n. Le problème standard est obtenu comme un cas particulier du problème général avec k= m, r= n; canonique – à k=0, r= n.

Exemple.

L'usine de confiserie produit plusieurs types de bonbons. Appelons-les « A », « B » et « C ». On sait que la vente de dix kilogrammes de bonbons "A" rapporte un bénéfice de 90 roubles, "B" - 100 roubles et "C" - 160 roubles. Les bonbons peuvent être produits en n'importe quelle quantité (les ventes sont garanties), mais les approvisionnements en matières premières sont limités. Il est nécessaire de déterminer quel type de bonbons et combien de dizaines de kilogrammes doivent être produits pour maximiser le bénéfice total des ventes. Les taux de consommation de matières premières pour la production de 10 kg de bonbons de chaque type sont indiqués dans le tableau 1.

Tableau 1. Taux de consommation de matières premières

pour la production

La formulation économique et mathématique du problème a la forme

Trouver de telles valeurs de variables X=(x1, x2, x3), à

fonction objectif

sous conditions-restrictions :

Un grand nombre de problèmes économiques sont réduits à des modèles mathématiques linéaires. Traditionnellement, on les appelle modèles de programmation linéaire. La programmation linéaire signifie une planification linéaire, c'est-à-dire obtenir un plan de solution optimal dans des problèmes à structure linéaire. Il est généralement utilisé par les spécialistes des unités du siège pour résoudre les difficultés de production. Des exemples typiques d'applications du modèle de programmation linéaire sont les suivants :

planification intégrée de la production (établissement de calendriers de production minimisant les coûts totaux dus aux variations des taux d'intérêt) ;

planifier la gamme de produits (déterminer la structure optimale de la production alimentaire pour l'homme) ;

acheminement de la production d'un produit (détermination de l'itinéraire technologique optimal pour fabriquer un produit) ;

régulation des stocks (détermination de la combinaison optimale de produits dans l'entrepôt) ;

planification de la production (établissement de plannings minimisant les coûts, prenant en compte les coûts de maintien des stocks, le paiement des heures supplémentaires et des commandes externes) ;

planification de la distribution des produits, etc.

Dans sa forme la plus générale, la programmation linéaire se réduit à un problème d'optimisation et s'écrit sous la forme suivante :

Pour résoudre un problème d'optimisation, il suffit de trouver sa solution optimale, c'est-à-dire indiquer
tel que f(X 0 )≥ f(X) à tout moment
, ou pour le cas de minimisation - f(X 0 )≤ f(X) à tout moment
.

Un problème d’optimisation n’est pas résolu s’il n’a pas de solution optimale. En particulier, le problème de maximisation ne sera pas résolu si la fonction objectif f(X) n'est pas borné par le haut sur l'ensemble admissible W.

Les méthodes de résolution des problèmes d'optimisation dépendent à la fois du type de fonction objectif f(X) , et de la structure de l'ensemble admissible W. Si la fonction cible du problème est une fonction n variables, alors les méthodes de résolution sont appelées méthodes de programmation mathématique.

Un problème de programmation linéaire est un problème de recherche opérationnelle dont le modèle mathématique a la forme :

Dans ce cas, le système d'équations linéaires (2) et d'inégalités (3), (4), qui détermine l'ensemble admissible de solutions au problème W, est appelé le système de contraintes d'un problème de programmation linéaire, et la fonction linéaire f(X) appelée fonction objectif, ou critère d'optimalité.

Si le modèle mathématique d’un problème de programmation linéaire a la forme :

alors ils disent que le problème est présenté sous forme canonique.

Tout problème de programmation linéaire peut être réduit à un problème de programmation linéaire sous forme canonique en déplaçant la maximisation vers la minimisation, des contraintes d'inégalité aux contraintes d'égalité, et en remplaçant les variables qui n'obéissent pas à la condition de non-négativité. Maximiser une certaine fonction équivaut à minimiser la même fonction prise avec le signe opposé et vice versa.

La règle pour amener un problème de programmation linéaire sous forme canonique est la suivante :

1) si dans le problème initial il est nécessaire de déterminer le maximum d'une fonction linéaire, alors vous devez changer le signe et rechercher le minimum de cette fonction ;

2) si le côté droit des restrictions est négatif, alors cette restriction doit être multipliée par (-1) ;

3) s'il existe des inégalités entre les restrictions, alors en introduisant des variables supplémentaires non négatives, elles sont transformées en égalités ;

4) si une variable x k n'a pas de restrictions de signe, alors il est remplacé (dans la fonction objectif et dans toutes les restrictions) par la différence entre deux nouvelles variables non négatives : x k = x’ k - x 1 , où 1 est un indice libre, x’ k ≥ 0, x 1 ≥ 0.

En résumant ce qui précède, nous pouvons tirer les conclusions suivantes :

1. Les contraintes dans les problèmes de programmation linéaire peuvent être exprimées à la fois par des égalités et des inégalités.

2. Une fonction linéaire peut tendre vers un maximum et un minimum.

3. Les variables du modèle sont toujours non négatives.

4. À partir de n'importe quel problème de programmation linéaire, vous pouvez passer au problème de programmation linéaire canonique (principal).

Chaque problème de programmation linéaire peut être comparé à un autre problème de programmation linéaire qui est double du problème d'origine (direct).

Considérons un problème de programmation linéaire de la forme suivante :

Le problème nécessite de maximiser la fonction objectif ; toutes les contraintes sont des inégalités de signe ≤, toutes les variables X 1 ,X 2 ,…,X n n variables de contrôle et m restrictions. Coefficients des variables dans la fonction objectif : c 1 , c 2 ,…, c n; membres gratuits : b 1 , b 2 ,…, b m .

Le problème de programmation dual linéaire a la forme :

Dans un problème dual, il faut trouver le minimum de la fonction objectif, les contraintes - inégalités de signe ≥, les variables de contrôle oui 1 , oui 2 ,…, oui m non négatif. La tâche contient m variables de contrôle et n restrictions. Coefficients de la fonction objective du problème b 1 , b 2 ,…, b m sont des termes libres du problème de programmation linéaire original et des termes libres du problème dual c 1 , c 2 ,…, c n – coefficients de la fonction objectif du problème de programmation linéaire original. La matrice des coefficients du problème dual est transposée, c'est-à-dire Les lignes sont remplacées par des colonnes et les colonnes sont remplacées par des lignes.

Les problèmes (9) – (10) et (11) – (12) forment une paire de problèmes, appelée double paire en programmation linéaire.

Le problème dual par rapport au problème original se compose selon les règles suivantes :

1. La fonction objective du problème initial est fixée au maximum et la fonction objective du problème double est fixée au minimum.

2. Matrice UN(13)

composé de coefficients pour les inconnues dans le système de contraintes (10) du problème original (9) – (10) et d'une matrice similaire dans le problème dual (11) – (12) sont obtenus l'un de l'autre par transposition.

3. Le nombre de variables dans le problème dual (11) – (12) est égal au nombre de restrictions dans le système (10) du problème d'origine et au nombre de restrictions dans le système (12) du problème dual est égal au nombre de variables du problème d’origine.

4. Les coefficients des inconnues dans la fonction objectif (11) du problème dual sont les termes libres dans le système (10) du problème d'origine, et les membres droits dans les contraintes du système (12) du problème le problème dual sont les coefficients des inconnues dans la fonction objectif (9) du problème original.

5. Si la variable x j du problème original (9) – (10) ne peut prendre que des valeurs non négatives, alors j- La contrainte dans le système (12) du problème dual est une inégalité de la forme ≥. Si la variable x j peut prendre des valeurs à la fois positives et négatives, alors j- La contrainte dans le système (12) est l'équation. Des connexions similaires ont lieu entre les contraintes (10) du problème initial et les variables du problème dual. Si je- Si la contrainte dans le système (10) du problème initial est une inégalité, alors je- Je suis la variable du double problème oui je ≥ 0. Si je- Si la contrainte est une équation, alors la variable oui je peut prendre des valeurs positives et négatives.

L'idée d'une amélioration séquentielle de la solution a constitué la base d'une méthode universelle pour résoudre des problèmes de programmation linéaire - la méthode simplex. La signification géométrique de cette méthode consiste en une transition séquentielle d'un sommet du polyèdre de contrainte (appelé initial) au voisin, dans lequel la fonction linéaire prend la meilleure (du moins pas la pire) valeur (par rapport à l'objectif du problème) jusqu'à ce qu'elle soit trouvée. La solution optimale est le sommet où la valeur optimale de la fonction but est atteinte (si le problème a un optimum final). Les idées de la méthode ont été publiées par le scientifique russe L.V. Kantorovitch en 1939

Pour appliquer la méthode du simplexe, des variables supplémentaires sont introduites dans les contraintes du problème oui 1 , oui 2 ,…, oui je et la condition du problème initial prend la forme :

Cet énoncé peut être présenté sous la forme d'un tableau - le premier tableau de la méthode simplex (tableau 1.1).

Tableau 1.1.

Premier tableau simplexe

Pour compiler un tableau simplexe, vous pouvez appliquer certaines règles.

1. Pour le premier tableau :

a) écrivez dans la première colonne oui m– les variables de base qui sont dans les équations de gauche ;

b) variables libres un minute placé dans la rangée supérieure du tableau ;

c) les coefficients devant les variables libres sont écrits dans les colonnes restantes.

2. Pour les tableaux suivants :

a) le plus petit élément négatif dans la ligne d'index est sélectionné lors de la recherche du maximum, mais le plus grand élément positif est sélectionné lors de la recherche du minimum, à l'exclusion du vecteur de termes libres ;

b) cet élément définit le vecteur colonne clé et il est entré dans la base ;

c) les composantes du vecteur de termes libres sont divisées par les éléments positifs de la colonne clé ;

d) le plus petit est sélectionné parmi les rapports obtenus ;

e) un vecteur ligne contenant le plus petit quotient positif est le vecteur clé et est dérivé de la base ;

f) à l'intersection des lignes clés et de la colonne se trouve un élément permissif ;

g) transformation matricielle :

Chaque élément de chaîne clé est divisé en un élément d'activation. Les quotients résultants sont les éléments de ligne clés du tableau suivant,

La colonne clé du nouveau tableau est constituée de zéros, à l'exception de l'élément d'activation,

Les éléments restants du nouveau tableau sont calculés selon le schéma suivant :

Nouvel élément = Ancien élément –

- Élément de ligne clé*Élément de colonne clé

Élément permissif

Si la ligne (colonne) nulle contient zéro, alors la colonne correspondante (ligne 0 dans la nouvelle table ne changera pas.

3. Les points « a » - « g » sont répétés jusqu'à ce qu'il ne reste plus un seul élément négatif dans la ligne d'index lors de la recherche du maximum (mais pas un seul élément positif lors de la recherche du minimum).

Exemple 1.1. Il est nécessaire de prendre une décision sur le plan optimal pour la production de tricots pendant un mois chez Sviyazh OJSC en utilisant la méthode simplex.

Déterminons un plan de production de modèles de tricots pour hommes afin d'obtenir un profit maximum avec des ressources données en construisant un modèle mathématique. Les données initiales sont présentées dans le tableau 1.2.

Tableau 1.2.

Données initiales

Les données initiales sur la consommation spécifique de ressources matérielles et de main-d'œuvre sont présentées dans le tableau. 1.2 conformément à la documentation réglementaire et technologique en vigueur dans l'organisation. La ligne « Ressources matérielles » enregistre le taux de consommation du type de matériaux le plus rare (limité0) - le fil de laine. Ce matériau a le taux de consommation et le coût les plus élevés.

La ligne « Équipement » montre l'intensité de travail récapitulative de la fabrication d'une unité de produit en heures standard comme total pour toutes les opérations partielles. D'autres types de ressources sont également pris en unités naturelles : ressources en main-d'œuvre - en heures ; matériel - en dm 2.

La ligne « Bénéfice » reflète le bénéfice de la vente d'une unité de produit, tiré du coût estimé prévu pour une unité de produit.

À travers x 1 , x 2 , x 3 , x 4 indiqué la quantité de produits fabriqués pour chaque type d'assortiment.

Selon la règle de construction d’un problème de programmation linéaire standard, créons un modèle mathématique :

Dans les contraintes du problème, nous introduisons des variables supplémentaires oui 1 , oui 2 , oui 3 et réécrivez la condition problématique sous la forme d’une équation :

La dernière déclaration peut être présentée sous la forme du tableau 1.3 - le premier tableau de la méthode du simplexe, que nous utiliserons pour résoudre le problème de programmation linéaire.

Tableau 1.3.

Premier tableau simplexe

La première colonne contient oui je – les variables de base sont celles à gauche de l'équation, et les variables libres x j placé dans la première rangée du tableau. Les colonnes restantes contiennent les coefficients des variables libres. La ligne d'index est le résultat de la soustraction des coefficients devant les variables libres de zéro.

Pour construire le tableau suivant, le plus petit élément négatif de la ligne d'index est sélectionné (c'est 222). Cet élément définit le vecteur colonne clé et il est introduit dans la base. Les composantes du vecteur de termes libres sont divisées par les éléments positifs de la colonne clé et le plus petit est sélectionné parmi les ratios résultants. Le vecteur ligne contenant le plus petit quotient positif est le vecteur clé et est dérivé de la base ( oui 2 ). À l'intersection des lignes clés et de la colonne se trouve un élément d'activation (c'est 55,50).

Chaque élément de chaîne clé est ensuite divisé en un élément d'activation. Les quotients résultants sont les éléments de la ligne clé du tableau suivant. En conséquence, le deuxième tableau simplex a été obtenu (tableau 1.4).

Tableau 1.4.

Deuxième table simplex

Puisqu'un élément négatif est apparu dans la ligne d'index, toutes les étapes similaires doivent être répétées et un troisième tableau simplex doit être construit.

Le résultat est un tableau. 1.5.

Tableau 1.5.

Table simplexe finale

Sur la base du tableau 1.5, nous pouvons tirer des conclusions : dans la colonne des termes libres, tous les éléments sont positifs (cela signifie que la solution résultante est admissible) ; dans la ligne d'index, tous les éléments sont également positifs (cela signifie que la solution résultante est optimale, c'est-à-dire qu'elle maximise la fonction objectif) ; le plan optimal serait les valeurs suivantes :
(c'est-à-dire qu'ils sont basiques) ;
(puisqu'ils sont gratuits) ; fonction objectif L= 4 201 195.

Il résulte également du tableau 1.5 que la variable de base oui 3 =9716, et variables libres oui 1 = oui 2 = 0, c'est-à-dire dans le plan optimal, les réserves de main-d'œuvre et de ressources matérielles sont égales à zéro, puisqu'elles sont pleinement utilisées. Une réserve de ressources matérielles oui 2 = 9716, ce qui indique son excédent.

Ainsi, suite à l'application de la méthode de programmation linéaire, il a été décidé de produire des pulls pour hommes du modèle sélectionné à hauteur de 3981 pièces, des pulls pour hommes modèle 55-1 à hauteur de 29 875 pièces.