Programmation linéaire

Programmation linéaire- une discipline mathématique consacrée à la théorie et aux méthodes de résolution de problèmes extrêmes sur des ensembles d'espaces vectoriels dimensionnels définis par des systèmes équations linéaires et les inégalités.

La programmation linéaire est un cas particulier de programmation convexe, qui à son tour est un cas particulier de programmation mathématique. En même temps, c'est la base de plusieurs méthodes de résolution de problèmes de programmation entière et non linéaire. Une des généralisations programmation linéaire est une programmation linéaire fractionnaire.

De nombreuses propriétés des problèmes de programmation linéaire peuvent également être interprétées comme des propriétés de polyèdres et donc formulées et prouvées géométriquement.

Histoire

La méthode des points intérieurs a été mentionnée pour la première fois par I. I. Dikin en 1967.

Tâches

Le principal problème de programmation linéaire (standard) s'appelle le problème de trouver le minimum d'une fonction objectif linéaire (forme linéaire) de la forme :

sous conditions

, .

Le problème de programmation linéaire aura vue canonique , si dans le problème principal au lieu du premier système d'inégalités il y a un système d'équations :

,

Le problème principal peut être réduit à canonique en introduisant des variables supplémentaires.

Les problèmes de programmation linéaire de la forme la plus générale (problèmes à contraintes mixtes : égalités et inégalités, présence de variables libres de contraintes) peuvent être réduits à des problèmes équivalents (ayant le même ensemble de solutions) en remplaçant les variables et les égalités par une paire de inégalités.

Il est facile de voir que le problème de trouver le maximum peut être remplacé par la tâche de trouver le minimum en prenant des coefficients de signe opposé.

Exemples de problèmes

Correspondance maximale

Considérons le problème d'appariement maximum dans un graphe biparti : il y a plusieurs garçons et filles, et pour chaque garçon et fille, on sait s'ils sont attirants l'un pour l'autre. Nous devons marier le maximum de couples ayant une sympathie mutuelle.

Introduisons des variables qui correspondent à la paire du -garçon et de la -fille et satisfont aux restrictions :

avec fonction objectif. On peut montrer que parmi les solutions optimales à ce problème, il en existe une entière. Les variables égales à 1 correspondront aux couples qui devraient être mariés.

Débit maximal

Soit un graphe (avec des arêtes orientées), dans lequel pour chaque arête son débit. Et deux sommets sont donnés : drain et source. Il est nécessaire d'indiquer pour chaque arête la quantité de liquide qui la traversera (pas plus que sa capacité) afin de maximiser le débit total de la source au drain (le liquide ne peut pas apparaître ou disparaître à tous les sommets sauf le drain et la source).

Prenons comme variables la quantité de liquide circulant à travers la côte. Alors

,

où est la capacité de ce bord. Ces inégalités doivent être complétées par l'égalité des quantités de fluide entrant et sortant pour chaque sommet, à l'exception du drain et de la source. En tant que fonction, il est naturel de prendre la différence entre la quantité de fluide sortant et entrant à la source.

Une généralisation du problème précédent est celle du flux maximum à coût minimum. Dans ce problème, les coûts pour chaque arête sont donnés et vous devez sélectionner le flux avec le coût minimum parmi les flux maximum. Ce problème se résume à deux problèmes de programmation linéaire : il faut d'abord résoudre le problème du débit maximum, puis ajouter à ce problème la contrainte , où est la valeur du débit maximum, et résoudre le problème avec nouvelle fonctionnalité- le coût du flux.

Ces problèmes peuvent être résolus plus rapidement qu'avec des algorithmes généraux de résolution de problèmes de programmation linéaire en raison de la structure particulière des équations et des inégalités.

Tâche de transport

Il existe une certaine cargaison homogène qui doit être transférée des entrepôts aux usines. Pour chaque entrepôt, on connaît la quantité de marchandises qu'il contient, et pour chaque usine, sa demande de marchandises est connue. Le coût du transport est proportionnel à la distance entre l'entrepôt et l'usine (toutes les distances entre l'entrepôt et l'usine sont connues). Il est nécessaire d'élaborer le plan de transport le moins cher.

Les variables décisives dans ce cas sont les quantités de marchandises transportées du ème entrepôt à la ème usine. Ils satisfont aux restrictions :

La fonction objectif a la forme : , qui doit être minimisée.

Jeu à somme nulle

Il existe une matrice de taille. Le premier joueur choisit un nombre de 1 à , le second - de 1 à . Ensuite, ils vérifient les numéros et le premier joueur obtient des points, et le second obtient des points (le numéro choisi par le premier joueur obtient le second). Nous devons trouver la stratégie optimale pour le premier joueur.

Supposons que dans une stratégie optimale, par exemple, le premier joueur doive choisir un nombre avec probabilité . Alors la stratégie optimale est une solution au problème de programmation linéaire suivant :

, , (),

dans lequel la fonction doit être maximisée. La valeur de la solution optimale sera l'espérance mathématique du gain du premier joueur dans le pire des cas.

Algorithmes de solutions

La méthode du simplexe est la méthode la plus connue et la plus largement utilisée dans la pratique pour résoudre un problème général de programmation linéaire (LP). Malgré le fait que la méthode du simplexe soit un algorithme assez efficace qui a montré de bons résultats dans la résolution de problèmes LP appliqués, il s'agit d'un algorithme à complexité exponentielle. La raison en est la nature combinatoire de la méthode du simplexe, qui énumère séquentiellement les sommets du polyèdre des solutions réalisables lors de la recherche de la solution optimale.

Le premier algorithme polynomial, la méthode ellipsoïde, a été proposé en 1979 par le mathématicien soviétique L. Khachiyan, résolvant ainsi le problème pendant longtemps restait en suspens. La méthode ellipsoïde a une nature non combinatoire complètement différente de la méthode simplex. Cependant, d’un point de vue informatique, cette méthode s’est avérée peu prometteuse. Néanmoins, le fait même de la complexité polynomiale des problèmes a conduit à la création de toute une classe d'algorithmes LP efficaces - méthodes de points intérieurs, dont le premier était l'algorithme de N. Karmarkar proposé en 1984. Les algorithmes de ce type utilisent une interprétation continue du problème LP, lorsqu'au lieu d'énumérer les sommets du polyèdre pour les solutions du problème LP, une recherche est effectuée le long de trajectoires dans l'espace de variables du problème qui ne passent pas par les sommets de le polyèdre. La méthode des points intérieurs, qui, contrairement à la méthode simplexe, contourne les points de l'intérieur de la région valeurs acceptables, utilise des méthodes de programmation non linéaire à barrière logarithmique développées dans les années 1960 par Fiacco et McCormick.

voir également

• Méthode graphique pour résoudre un problème de programmation linéaire

Remarques

Littérature

• Thomas H. Corman et coll. Chapitre 29. Programmation linéaire // Algorithmes : construction et analyse = INTRODUCTION AUX ALGORITHMES. - 2e éd. - M. : « Williams », 2006. - P. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Chapitre 1. Problèmes de programmation linéaire, Chapitre 2. Tâches spéciales programmation linéaire // Programmation mathématique en exemples et problèmes. - M. : Lycée, 1986. - 319 p. - ISBN5-06-002663-9
• Karmanov V.G. Programmation mathématique. - 3ème édition. - M. : Nauka, 1986. - 288 p.
• Dantzig George Bernard "Souvenirs des débuts de la programmation linéaire"

Liens

• - Package d'optimisation gratuit conçu pour résoudre des problèmes de programmation linéaire, entière et par objectifs.
• Vershik A. M. « À propos de L. V. Kantorovich et de la programmation linéaire »
• Bolshakova I. V., Kuralenko M. V. « Programmation linéaire. Manuel pédagogique et méthodologique du test."
• Barsov A. S. « Qu'est-ce que la programmation linéaire », Conférences populaires sur les mathématiques, Gostekhizdat, 1959.
• M. N. Vyalyi Inégalités linéaires et combinatoire. -MCNMO, 2003.

Fondation Wikimédia. 2010.

• Salten, Félix
• Glagow, Martina

Voyez ce qu'est la « programmation linéaire » dans d'autres dictionnaires :

programmation linéaire- - programmation linéaire Un domaine de programmation mathématique consacré à la théorie et aux méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre ... ... Guide du traducteur technique

Programmation linéaire

Programmation linéaire- un domaine de programmation mathématique consacré à la théorie et aux méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre variables. Dans sa forme la plus générale, le problème de L.p. peut s'écrire ainsi. Sont donnés… … Dictionnaire économique et mathématique

Cette méthode est une méthode d'énumération ciblée de solutions de référence à un problème de programmation linéaire. Elle permet, en un nombre fini d'étapes, soit de trouver une solution optimale, soit d'établir qu'il n'existe pas de solution optimale.

Le contenu principal de la méthode simplexe est le suivant :

1. Indiquer une méthode pour trouver la solution de référence optimale
2. Indiquer la méthode de transition d'une solution de référence à une autre, à laquelle la valeur de la fonction objectif sera plus proche de la valeur optimale, c'est-à-dire indiquer un moyen d'améliorer la solution de référence
3. Définissez des critères qui vous permettent d'arrêter rapidement de rechercher des solutions d'assistance à la solution optimale ou de tirer une conclusion sur l'absence de solution optimale.

Algorithme de la méthode simplexe pour résoudre des problèmes de programmation linéaire

Afin de résoudre le problème méthode simplexe vous devez faire ce qui suit :

1. Amener le problème sous forme canonique
2. Trouver la solution de support initiale avec une « base unitaire » (s'il n'y a pas de solution de support, alors le problème n'a pas de solution en raison de l'incompatibilité du système de contraintes)
3. Calculer les estimations des décompositions vectorielles à partir de la solution de référence et remplir le tableau de la méthode simplexe
4. Si le critère d'unicité de la solution optimale est satisfait, alors la solution du problème se termine
5. Si la condition d’existence d’un ensemble de solutions optimales est remplie, alors toutes les solutions optimales sont trouvées par simple énumération

Un exemple de résolution d'un problème en utilisant la méthode du simplexe

Exemple 26.1

Résolvez le problème en utilisant la méthode du simplexe :

Solution:

Nous mettons le problème sous forme canonique.

Pour ce faire, nous introduisons une variable supplémentaire x 6 de coefficient +1 à gauche de la première contrainte d'inégalité. La variable x 6 est incluse dans la fonction objectif avec un coefficient nul (c'est-à-dire qu'elle n'est pas incluse).

On a:

Nous trouvons la solution d’accompagnement initiale. Pour ce faire, nous assimilons les variables libres (non résolues) à zéro x1 = x2 = x3 = 0.

On a Solution de référence X1 = (0,0,0,24,30,6) avec base unitaire B1 = (A4, A5, A6).

Nous calculons estimations des décompositions vectorielles conditions à partir de la solution de référence selon la formule :

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vecteur de coefficients de la fonction objectif pour les variables de base
• X k = (x 1k, x 2k, ..., x mk) - vecteur d'expansion du vecteur correspondant A k selon la base de la solution de référence
• C k est le coefficient de la fonction objectif pour la variable x k.

Les estimations des vecteurs inclus dans la base sont toujours égales à zéro. La solution de référence, les coefficients d'expansion et les estimations des expansions des vecteurs de condition basés sur la solution de référence sont écrits en tableau simplexe:

En haut du tableau, pour faciliter le calcul des estimations, sont inscrits les coefficients de la fonction objectif. Dans la première colonne "B" sont écrits les vecteurs inclus dans la base de la solution de référence. L'ordre dans lequel ces vecteurs sont écrits correspond au nombre d'inconnues autorisées dans les équations de contraintes. Dans la deuxième colonne du tableau « C b » les coefficients de la fonction objectif pour les variables de base sont écrits dans le même ordre. À emplacement correct Les coefficients de la fonction objectif dans la colonne « C b » de l'estimation des vecteurs unitaires inclus dans la base sont toujours égaux à zéro.

Dans la dernière ligne du tableau avec les estimations de Δ k dans la colonne « A 0 » sont écrites les valeurs de la fonction objectif sur la solution de référence Z(X 1).

La solution de support initiale n'est pas optimale, puisque dans le problème du maximum les estimations Δ 1 = -2, Δ 3 = -9 pour les vecteurs A 1 et A 3 sont négatives.

Selon le théorème d'amélioration de la solution support, si dans un problème maximum au moins un vecteur a une estimation négative, alors vous pouvez trouver une nouvelle solution support sur laquelle la valeur de la fonction objectif sera plus grande.

Déterminons lequel des deux vecteurs conduira à un incrément plus important dans la fonction objectif.

L'incrément de la fonction objectif se trouve par la formule : .

On calcule les valeurs du paramètre θ 01 pour les première et troisième colonnes à l'aide de la formule :

On obtient θ 01 = 6 pour l = 1, θ 03 = 3 pour l = 1 (tableau 26.1).

On retrouve l'incrément de la fonction objectif en introduisant dans la base le premier vecteur ΔZ 1 = - 6*(- 2) = 12, et le troisième vecteur ΔZ 3 = - 3*(- 9) = 27.

Par conséquent, pour une approche plus rapide de la solution optimale, il est nécessaire d'introduire le vecteur A3 dans la base de la solution de référence au lieu du premier vecteur de la base A6, puisque le minimum du paramètre θ 03 est atteint dans la première ligne ( l = 1).

On effectue la transformation de Jordan avec l'élément X13 = 2, on obtient la deuxième solution de référence X2 = (0,0,3,21,42,0) avec la base B2 = (A3, A4, A5). (Tableau 26.2)

Cette solution n'est pas optimale, puisque le vecteur A2 a une estimation négative Δ2 = - 6. Pour améliorer la solution, il faut introduire le vecteur A2 dans la base de la solution de référence.

Nous déterminons le numéro du vecteur dérivé de la base. Pour ce faire, on calcule le paramètre θ 02 pour la deuxième colonne, il est égal à 7 pour l = 2. Par conséquent, on dérive le deuxième vecteur de base A4 de la base. On effectue la transformation de Jordan avec l'élément x 22 = 3, on obtient la troisième solution de référence X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tableau 26.3).

Cette solution est la seule optimale, puisque pour tous les vecteurs non inclus dans la base les estimations sont positives

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Répondre: max Z(X) = 201 à X = (0,7,10,0,63).

Méthode de programmation linéaire en analyse économique

Méthode de programmation linéaire permet de justifier la solution économique la plus optimale dans des conditions de restrictions sévères liées aux ressources utilisées dans la production (immobilisations, matériaux, ressources en main d'œuvre). L'utilisation de cette méthode en analyse économique permet de résoudre des problèmes liés principalement à la planification des activités d'une organisation. Cette méthode permet de déterminer les niveaux de sortie optimaux, ainsi que les directions pour le plus utilisation efficace ressources de production dont dispose l’organisation.

Grâce à cette méthode, on résout les problèmes dits extrêmes, qui consistent à trouver des valeurs extrêmes, c'est-à-dire le maximum et le minimum des fonctions de quantités variables.

Cette période repose sur la résolution d'un système d'équations linéaires dans les cas où les phénomènes économiques analysés sont liés par une dépendance linéaire et strictement fonctionnelle. La méthode de programmation linéaire est utilisée pour analyser des variables en présence de certains facteurs limitants.

Il est très courant de résoudre le problème dit de transport en utilisant la méthode de programmation linéaire. Le contenu de cette tâche est de minimiser les coûts encourus dans le cadre de l'opération Véhicule dans le cadre des restrictions existantes concernant le nombre de véhicules, leur capacité de transport, la durée de leur exploitation et s'il existe un besoin d'entretien quantité maximale clients.

En plus, cette méthode est largement utilisé pour résoudre les problèmes de planification. Cette tâche consiste en une telle répartition du temps de fonctionnement pour le personnel d'une organisation donnée qui serait la plus acceptable tant pour les membres de ce personnel que pour les clients de l'organisation.

Cette tâche consiste à maximiser le nombre de clients servis dans des conditions de limitation du nombre de membres du personnel disponibles, ainsi que du fonds de temps de travail.

Ainsi, la méthode de programmation linéaire est assez courante dans l’analyse de placement et d’utilisation. divers types ressources, ainsi que dans le processus de planification et de prévision des activités des organisations.

Néanmoins, la programmation mathématique peut également être appliquée aux phénomènes économiques dont la relation n’est pas linéaire. A cet effet, des méthodes de programmation non linéaires, dynamiques et convexes peuvent être utilisées.

La programmation non linéaire repose sur la nature non linéaire de la fonction objectif ou des contraintes, ou des deux. Les formes de la fonction objectif et des contraintes d'inégalité dans ces conditions peuvent être différentes.

La programmation non linéaire est utilisée en analyse économique, notamment pour établir la relation entre des indicateurs exprimant l'efficacité des activités d'une organisation et le volume de cette activité, la structure des coûts de production, les conditions du marché, etc.

La programmation dynamique repose sur la construction d'un arbre de décision. Chaque niveau de cet arbre sert d'étape pour déterminer les conséquences décision précédente et d'éliminer les options inefficaces pour cette solution. Ainsi, programmation dynamique a une nature en plusieurs étapes et en plusieurs étapes. Ce type de programmation est utilisé en analyse économique pour trouver options optimales développement de l'organisation, aujourd'hui et à l'avenir.

La programmation convexe est un type de programmation non linéaire. Ce type de programmation exprime le caractère non linéaire de la relation entre les résultats des activités d’une organisation et ses coûts. La programmation convexe (alias concave) analyse les fonctions objectives convexes et les systèmes de contraintes convexes (points de faisabilité). La programmation convexe est utilisée dans l'analyse des activités économiques dans le but de minimiser les coûts, et la programmation concave dans le but de maximiser les revenus dans le cadre des restrictions existantes sur l'action des facteurs qui influencent les indicateurs analysés de manière opposée. Par conséquent, avec les types de programmation considérés, les fonctions objectives convexes sont minimisées et les fonctions objectives concaves sont maximisées.

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 le maximum) fonction linéaire sous restrictions 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 de l'équipement sur navires de mer, 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 aboutit à des modèles plus équilibrés et plus proches de l'ajustement. solutions optimales. Compte tenu de l'utilisation de plus en plus répandue feuilles de calcul Dans le processus de gestion, les futurs spécialistes doivent avoir des compétences professionnelles en matière de développement de modèles - 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 dossier distinct. module logiciel. 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 le résultat de la formule dans la 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. Sur le terrain 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 maximum. Pour minimiser la valeur de la cellule cible en modifiant les valeurs des cellules d'influence, réglez le commutateur sur Valeur minimum . 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. Sur le terrain 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. Sur le terrain 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,6kg ; 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.

Objet de la prestation. Le calculateur en ligne est conçu pour résoudre des problèmes de programmation linéaire en utilisant la méthode du simplexe en accédant à KZLP Et SZLP. Dans ce cas, le problème de trouver le minimum de la fonction objectif se réduit au problème de trouver le maximum par la transformation de la fonction objectif F*(X) = -F(X) . Il est également possible de créer un double problème.

La solution se déroule en trois étapes :

1. Transition vers KZLP. Tout LLP de la forme ax ≤ b , ax ≥ b , ax = b (F(X) → extr) se réduit à la forme ax = b , F(X) → max ;
2. Transition vers le SZLP. Un CLLP de la forme ax = b se réduit à la forme ax ≤ b , F(X) → max ;
3. Solution utilisant la méthode du simplexe ;

Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word.

Nombre de variables 2 3 4 5 6 7 8 9 10
Nombre de lignes (nombre de restrictions) 1 2 3 4 5 6 7 8 9 10

Transition du problème de minimisation de la fonction objectif au problème de maximisation

Le problème de minimiser la fonction objectif F(X) peut facilement être réduit au problème de maximiser la fonction F*(X) sous les mêmes restrictions en introduisant la fonction : F*(X) = -F(X) . Les deux problèmes ont la même solution X*, et en même temps min(F(X)) = -max(F*(X)) .
Illustrons ce fait graphiquement :

F(x) → min

F(x) → maximum

Pour optimiser la fonction objectif, nous utilisons les concepts et méthodes suivants.
Forfait de base– un plan avec des variables de base définies via libres.
Forfait de base– plan de référence avec zéro variable de base.
Forfait optimal– un plan de base qui satisfait fonction optimale buts (FC).

Élément principal (résolvant) est le coefficient de l'inconnue libre, qui devient le coefficient de base, et le coefficient lui-même est converti en unité.
Ligne directrice– la ligne de l'élément leader, dans laquelle se situe l'inconnue de base avec un coefficient unitaire, exclue lors de la transformation (ligne avec le coefficient limite minimum, voir ci-dessous).
Colonne de guidage– la colonne de l'élément leader dont l'inconnue libre est convertie en celle de base (la colonne avec le bénéfice maximum, voir ci-dessous).

Les variables x 1, …, x m, incluses avec des coefficients unitaires dans une seule équation du système, avec des coefficients nuls dans le reste, sont appelées basique ou dépendant. Dans le système canonique, chaque équation correspond exactement à une variable de base. La transition est réalisée selon la méthode de Gauss-Jordan. L'idée principale de cette méthode est de réduire un système de m équations à n inconnues à une forme canonique à l'aide d'opérations élémentaires sur des chaînes.
Repos n-m variables(x m +1 ,…, x n) sont appelés non basique ou variables indépendantes.

Solution basique appelé solution de base admissible, si les valeurs des variables de base qu'il contient x j ≥0, ce qui équivaut à la condition de non-négativité b j ≥0.
Une solution de base réalisable est coin ensemble admissible S d'un problème de programmation linéaire et est parfois appelé plan de référence.
Si parmi les nombres non négatifs b j il y en a égaux à zéro, alors la solution de base admissible est appelée dégénérer(point de coin dégénéré) et le problème de programmation linéaire correspondant est appelé dégénérer.

Exemple n°1. Réduisez le problème de programmation linéaire à un ZLP standard.
F(X) = x 1 + 2x 2 - 2x 3 → min avec restrictions :
4x 1 + 3x 2 - x 3 ≤10
- 2x2 + 5x3 ≥3
x1 + 2x3 =9
Pour amener le PAP à Forme canonique nécessaire:
1. Changez le signe de la fonction objectif. Réduisons le problème F(X) → min au problème F(X) → max. Pour ce faire, multipliez F(X) par (-1). Dans la première inégalité de sens (≤), on introduit la variable de base x 4 ; dans la deuxième inégalité de sens (≥), on introduit la variable de base x 5 avec un signe moins.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Transition vers le SZLP.
Matrice étendue du système de contraintes d'égalité pour ce problème :

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Réduisons le système à la matrice identité en utilisant la méthode de transformation de Jordan.
1. Vous pouvez choisir x 4 comme variable de base.
2. Nous choisissons x 2 comme variable de base.
Élément de résolution RE=-2. La droite correspondant à la variable x 2 est obtenue en divisant tous les éléments de la droite x 2 par l'élément résolvant RE = -2. À la place de l'élément de résolution, nous obtenons 1. Dans les cellules restantes de la colonne x 2, nous écrivons des zéros. Tous les autres éléments sont déterminés par la règle du rectangle. Présentons le calcul de chaque élément sous forme de tableau :

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

On a nouvelle matrice:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. Nous choisissons x 3 comme variable de base.
Élément de résolution RE=2. La droite correspondant à la variable x 3 est obtenue en divisant tous les éléments de la droite x 3 par l'élément résolvant RE = 2. À la place de l'élément de résolution, nous obtenons 1. Dans les cellules restantes de la colonne x 3, nous écrivons des zéros. Tous les autres éléments sont déterminés par la règle du rectangle. Présentons le calcul de chaque élément sous forme de tableau :

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

On obtient une nouvelle matrice :

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Puisque le système a une matrice d'identité, nous prenons X = (4,2,3) comme variables de base.
Les équations correspondantes sont :
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
Exprimons les variables de base en fonction du reste :
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1 / 2 x 1 +4 1 / 2
Remplaçons-les dans la fonction cible :
F(X) = - x 1 - 2 (- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2 (- 1 / 2 x 1 +4 1 / 2)
ou

Système d'inégalités :
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 × 1 +4 1/2 ≥ 0
On réduit le système d’inégalités à la forme suivante :
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 5 ≤ 9 3/4
1/2 × 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Simplifions le système.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 2 ≤ 9 3/4
1/2 × 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Exemple n°2. Trouver d'abord méthode graphique, puis en utilisant la méthode simplexe pour résoudre le problème
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) avec restrictions :
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

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.

À Problèmes mathématiques La programmation linéaire comprend des études sur des situations de production et économiques spécifiques, qui, sous une forme ou une autre, sont interprétées comme des problèmes concernant utilisation optimale 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 : les nombres entiers, dynamiques, non linéaires, programmation paramétrique). Ceci s'explique comme suit :

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

· ce type les problèmes sont actuellement les plus étudiés. 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 considérer 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 plus de quantitéé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 diverses solutions notre système de restrictions. 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 plan optimal le 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 ça pas optimal , alors un passage à un autre s'effectue, nécessairement solution de base admissible .

La méthode simplexe garantit qu'avec cette nouvelle solution forme linéaire, même s’il n’atteint pas l’optimum, il 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.