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 :

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. Valeur en solution optimale sera l'espérance mathématique du gain du premier joueur dans le pire des cas.

Algorithmes de solutions

Le plus connu et le plus utilisé en pratique pour résoudre tâche commune La programmation linéaire (LP) est une méthode simplexe. 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

Annotation: Cette conférence couvre un certain nombre de questions consacrées à la programmation linéaire en tant que branche de la programmation mathématique ; formule notamment les principaux types de problèmes de programmation linéaire, révèle les différences entre ces problèmes et les problèmes classiques d'analyse mathématique ; présente Formes variées enregistre ces tâches, les met en place et étudie leur structure. La question de la résolution de problèmes de programmation linéaire à l'aide de la méthode du simplexe est étudiée de manière plus approfondie.

1. Le concept de programmation mathématique

est une discipline mathématique dans laquelle sont développées des méthodes pour trouver les valeurs extrêmes d'une fonction objectif parmi l'ensemble de ses valeurs possibles déterminées par des contraintes.

La présence de restrictions rend les problèmes fondamentalement différents des problèmes classiques d'analyse mathématique consistant à trouver les valeurs extrêmes d'une fonction. Méthodes d'analyse mathématique pour la recherche extremum de la fonction dans les tâches programmation mathématique s'avèrent inadaptés.

Résoudre des problèmes programmation mathématique Des méthodes et théories spéciales ont été développées et sont en cours de développement. Puisque la résolution de ces problèmes nécessite d’effectuer une quantité importante de calculs, lorsque évaluation comparative méthodes grande importance est accordé à l'efficacité et à la commodité de leur mise en œuvre sur un ordinateur.

Il peut être considéré comme un ensemble de sections indépendantes impliquées dans l'étude et le développement de méthodes permettant de résoudre certaines classes de problèmes.

En fonction des propriétés de la fonction objectif et de la fonction de contrainte, tous les problèmes programmation mathématique sont divisés en deux classes principales :

• problèmes de programmation linéaire,
• Tâches programmation non linéaire.

Si la fonction objectif et les fonctions de contrainte sont fonctions linéaires, alors le problème correspondant de trouver un extremum est un problème de programmation linéaire. Si au moins un des fonctions spécifiées est non linéaire, alors le problème correspondant de trouver un extremum est le problème programmation non linéaire.

2. Le concept de programmation linéaire. Types de problèmes de programmation linéaire

Programmation linéaire(LP) – l’une des premières et des sections les plus étudiées programmation mathématique. Exactement programmation linéaireétait la section à partir de laquelle la discipline elle-même a commencé à se développer" programmation mathématique". Le terme « programmation » dans le titre de la discipline n'a rien de commun avec le terme « programmation (c'est-à-dire compilation d'un programme) pour un ordinateur » n'a rien à voir avec la discipline " programmation linéaire" est apparu avant même l'époque où les ordinateurs ont commencé à être largement utilisés pour résoudre des problèmes mathématiques, techniques, économiques et autres.

Le terme " programmation linéaire" est né d'une traduction inexacte de l'anglais « programmation linéaire ». L'une des significations du mot « programmation » est l'élaboration de plans, la planification. Par conséquent, traduction correcte La "programmation linéaire" anglaise ne serait pas " programmation linéaire", et "planification linéaire", qui reflète plus fidèlement le contenu de la discipline. Cependant, les termes programmation linéaire, programmation non linéaire, programmation mathématique etc. sont devenus généralement acceptés dans notre littérature et seront donc préservés.

Donc, programmation linéaire est apparu après la Seconde Guerre mondiale et a commencé à se développer rapidement, attirant l'attention des mathématiciens, des économistes et des ingénieurs en raison de la possibilité d'une large application pratique, ainsi que de l'harmonie mathématique.

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.

Programmation linéaire utilisé pour résoudre des problèmes économiques, dans des tâches telles que la gestion et la planification de la production ; dans les tâches de détermination de l'emplacement optimal des équipements sur les navires et dans les ateliers ; dans les problèmes de détermination plan optimal transport de marchandises (tâche de transport); dans des problèmes de répartition optimale du personnel, etc.

Problème de programmation linéaire(LP), comme cela ressort déjà de ce qui a été dit ci-dessus, consiste à trouver le minimum (ou le maximum) d'une fonction linéaire sous des restrictions linéaires.

Forme générale le problème a la forme : trouver dans les conditions

Outre la forme générale, ils sont également largement utilisés canonique Et standard formes. Sous forme canonique et standard

Ceux. toutes les variables de toute solution réalisable au problème doivent prendre des valeurs non négatives (ces variables sont généralement appelées non négatif contrairement à ce qu'on appelle gratuit variables dont la plage de valeurs n'est pas soumise à de telles restrictions). La différence entre ces formes est que dans un cas I 2 = 0 et dans l'autre - I 1 = 0.

Le problème LP sous forme canonique.

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 qui minimisent 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) à n'importe
, ou pour le cas de minimisation - F(X 0 )≤ F(X) à n'importe
.

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 P. 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 P. P. 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 les termes libres du problème de programmation linéaire original, et les termes libres double problème 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 initial (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

	Membres gratuits	Variables libres
		X 1	X 2		X n
oui 1	b 1	un 11	un 12		un 1n
oui 2	b 2	un 21	un 22		un 2n
oui m	b m	un m1	un m2		un minute
Ligne d'index		-c 1	-c 2		-c n

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 sorti à ligne supérieure les tables;

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,

Colonne clé dans nouveau tableau– des zéros, à l'exception de l'élément résolvant,

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. Une décision doit être prise concernant plan optimal production de tricots pendant un mois chez Sviyazh OJSC en utilisant des méthodes 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ée initiale

Ressources ( je)	Type de produit ( j)				Réserve de ressources ( b je)
	Pantalon de sport modèle 7060	Pull homme modèle 55-1	Pull homme modèle 38-0	Modèle de combinaison de sport
	consommation de ressources spécifiques ( un je)
Travail
Matériel
Équipement
	X 1	X 2	X 3	X 4

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ériau 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 devis 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

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

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

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

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

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

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.

Si un problème de programmation linéaire n’a que deux variables, alors il peut être résolu méthode graphique.

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.

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. De plus, 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.
(2)
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).

Trouver l'extremum de la fonction objectif

Nous avons donc une région ombrée de solutions réalisables (ADA). Elle est limitée par une ligne brisée constituée de segments et de rayons appartenant aux droites construites (2). L'ODS est toujours un ensemble convexe. Il peut s'agir d'un ensemble borné ou non borné dans certaines directions.

Nous pouvons maintenant rechercher l'extremum de la fonction objectif
(1.1) .

Pour ce faire, choisissez n'importe quel nombre et construisez une ligne droite
(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), le plus loin 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
.

Il peut également arriver que la ligne droite soit parallèle à l'une des faces de l'ODR. Ensuite, la droite passe par deux sommets du polygone ODR. Nous déterminons les coordonnées de ces sommets. Pour déterminer la valeur maximale (minimale) de la fonction objectif, vous pouvez utiliser les coordonnées de l'un de ces sommets :
.
Le problème a une infinité de solutions. La solution est n'importe quel point situé sur le segment entre les points et , y compris les points et eux-mêmes.

Un exemple de résolution d'un problème de programmation linéaire à l'aide de la méthode graphique

La tâche

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 tissus 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.
.

La solution du 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

Exemple 2

La tâche

Résolvez graphiquement un problème de programmation linéaire.

Solution

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 ; 6) et (6 ; 0).

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

Nous construisons une ligne droite.
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 ombrons la zone le long des limites des lignes construites de sorte que le point (4 ; 1) tombe dans la partie ombrée. On obtient le triangle ABC.

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 , nous traçons une ligne droite, parallèle à la ligne niveau et la distance maximale de celui-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.
.

La solution du problème : ;

Répondre

Exemple de non-solution

La tâche

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 droite 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 la zone est illimitée du côté grandes valeurs et , alors une telle ligne droite ne peut pas être tracée. Quelle que soit la ligne 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.
.
Valeur minimale de la fonction objectif :

Répondre

Il n'y a pas de valeur maximale.
Valeur minimum
.

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 d'équations linéaires et d'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 généralisation de la programmation linéaire est la 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 sa capacité est indiquée. 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 une nouvelle fonction - la 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 un problème longtemps resté sans solution. 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 du simplexe, traverse les points de l'intérieur de la région réalisable, 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. Problèmes spéciaux de 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