Généralement, les problèmes de programmation linéaire n'exigent pas que les coordonnées du plan soient des nombres entiers. Cependant, dans la pratique, on rencontre souvent des problèmes dans lesquels les coordonnées des plans optimaux doivent être des nombres entiers, et de tels problèmes sont appelés problèmes. . Lors de la résolution de problèmes de programmation linéaire à l'aide de la méthode graphique et de la méthode simplexe, rien ne garantit que les coordonnées du plan optimal seront des nombres entiers.

Dans certains cas, les résultats peuvent être arrondis. Par exemple, si le plan optimal stipule que 499 683,3 voitures doivent être produites, il est alors économiquement justifié d'arrondir le résultat à 499 683, voire à 500 000.

Il existe cependant des problèmes dans lesquels un tel arrondi peut créer une erreur importante. Par exemple, si le plan optimal stipule que 0,67 usines doivent être construites, alors un arrondi formel à 0 ou 1 est inacceptable.

Par conséquent, les méthodes de résolution de problèmes de programmation linéaire sont d'une grande importance pratique, à l'aide desquelles vous pouvez trouver le plan optimal dont les coordonnées sont des nombres entiers. Tâches programmation entière sont résolus en utilisant exactement ces méthodes.

Si problème de programmation en nombre entier donné sous forme canonique, il est formulé ainsi :

trouver le maximum de la fonction objectif (forme linéaire)

sous un système de restrictions

Ainsi, la tâche programmation entière et le problème de programmation linéaire correspondant ne diffèrent que dans la condition où les inconnues sont entières.

Comme les problèmes de programmation linéaire, les problèmes de programmation en nombres entiers exigent que le plan optimal maximise la fonction objectif (forme linéaire).

Méthode Gomori pour résoudre des problèmes de programmation en nombres entiers

Méthode Gomori est une méthode universelle pour résoudre des problèmes de programmation en nombres entiers, avec laquelle, après un nombre fini d'itérations, vous pouvez trouver le plan optimal ou vous assurer que le problème n'a pas de solution. Cependant, la valeur pratique de la méthode de Gomori est très limitée, car de nombreuses itérations doivent être effectuées pour résoudre des problèmes.

Lors de la résolution de problèmes de programmation en nombres entiers à l'aide de la méthode Gomori, les sous-ensembles qui ne contiennent pas de plans en nombres entiers sont progressivement supprimés de l'ensemble des plans optimaux pour un problème de programmation linéaire.

Lors de la première itération, vous devez résoudre un problème de programmation linéaire en utilisant la méthode du simplexe. Si les inconnues trouvées satisfont à l’exigence d’entier, alors le problème de programmation en entier est résolu. Si parmi les inconnues trouvées, au moins une est un nombre fractionnaire, alors une condition supplémentaire doit être créée (comment la composer - plus de détails ci-dessous) et attachée au système de contraintes du problème de programmation en nombres entiers. Ainsi, de l'ensemble des plans, le sous-ensemble qui ne contient pas de plans entiers est supprimé. Si le plan optimal du problème ainsi augmenté est entier, alors le problème de programmation en nombres entiers est résolu. Le processus de résolution se poursuit jusqu'à ce qu'à une certaine itération, un plan optimal entier soit trouvé ou qu'il puisse être vérifié que le problème n'a pas de solution.

Parlons maintenant de la façon de créer la condition supplémentaire mentionnée. Elle, condition supplémentaire, est obtenue à partir d'une des équations du système de restrictions à partir des coefficients des inconnues et des inconnues elles-mêmes selon la formule

, où entre accolades se trouvent respectivement les parties fractionnaires du terme libre et les coefficients des inconnues.

Par exemple, à partir d’un tableau simplexe, nous obtenons l’équation suivante :

.

On obtient la partie fractionnaire du terme libre en soustrayant sa partie entière du nombre lui-même comme suit :

De même, on obtient les parties fractionnaires des coefficients pour les inconnues :

(à x3 ),

(à x4 ).

Et la règle générale pour trouver des parties fractionnaires est la suivante : par la partie entière d'un nombre réel un Le plus grand entier s’appelle [ un], ne dépassant pas un; partie fractionnaire d'un nombre réel un appelé différence {un} = un - [un] le numéro lui-même un et toute sa partie [ un] .

.

Dans notre exemple, en utilisant la formule ci-dessus, l'équation suivante est obtenue :

.

Exemple 1. Résolvez le problème de programmation en nombres entiers suivant en utilisant la méthode Gomori. Trouver le maximum de la fonction objectif

sous un système de restrictions

Solution. Nous résolvons le problème en utilisant la méthode du simplexe. Puisque nous avons leçon sur la résolution de problèmes de programmation linéaire à l'aide de la méthode du simplexe, la méthode elle-même ne sera pas expliquée ici, mais seuls les tableaux simplex seront donnés.

Inconnues supplémentaires x3 Et x4 Prenons cela comme basique. Exprimons les inconnues de base et la fonction but en termes de variables non fondamentales :

Créons un tableau simplexe à partir des coefficients :

Nous compilons les tableaux suivants jusqu'à obtenir le plan optimal :

Tableau 3
Inconnues de base	Membres gratuits	Inconnues gratuites		Coefficients auxiliaires
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
AVEC	65/7	10/7	1/7	1/2

À partir du tableau 3, nous trouvons le plan optimal . Puisque ce plan optimal ne satisfait pas à la condition entière, nous devons créer une condition supplémentaire. La partie fractionnaire de la coordonnée est le nombre, et la partie fractionnaire de la coordonnée est le nombre.

La première équation basée sur le tableau s'écrira comme suit :

.

Après avoir déterminé les parties fractionnaires des coefficients pour les inconnues et les termes libres, on obtient la condition supplémentaire suivante :

ou, en introduisant une variable supplémentaire,

.

On obtient une nouvelle ligne dans le tableau simplex obtenu à partir du tableau 3 et en ajoutant les coefficients de l'équation qui vient d'être obtenue :

Tableau 4
Inconnues de base	Membres gratuits	Inconnues gratuites		Coefficients auxiliaires
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
AVEC	65/7	10/7	1/7	1/2

Nous terminons l'étape de la méthode simplex et obtenons le tableau :

Tableau 5
Inconnues de base	Membres gratuits	Inconnues gratuites		Coefficients auxiliaires
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
AVEC	55/6	4/3	1/6	-1/7

Nous avons reçu le plan optimal . Ce plan, comme le précédent, ne satisfait pas à la condition entière. Une condition supplémentaire est donc à nouveau requise. Dans ce cas, vous pouvez utiliser la première ou la troisième équation. On obtient la condition supplémentaire suivante :

.

Créons le tableau suivant :

Tableau 6
Inconnues de base	Membres gratuits	Inconnues gratuites		Coefficients auxiliaires
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
AVEC	55/6	4/3	1/6	-1/7

Plan optimal on obtient du tableau final suivant :

Tableau 7
Inconnues de base	Membres gratuits	Inconnues gratuites		Coefficients auxiliaires
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
AVEC	9	6/5	1/5	-1/6

Puisque le plan optimal trouvé satisfait à la condition entière, le problème de programmation en nombre entier est résolu. Coordonnées x5 Et x6 peut être ignoré, puisque les conditions initiales du problème ne contiennent que quatre inconnues. Le plan optimal final s’écrira donc comme suit :

,

et le maximum de la fonction objectif est 9.

Méthode de branchement et de liaison pour résoudre des problèmes de programmation en nombres entiers

La méthode branch andbound est pratique pour résoudre des problèmes de programmation en nombres entiers dans lesquels le nombre d'inconnues est faible ou dans lesquels les exigences relatives aux nombres entiers ne s'appliquent pas à toutes les inconnues. L'essence de la méthode branch andbound est que pour les inconnues auxquelles s'applique l'exigence d'un nombre entier, il est nécessaire de déterminer les limites dans lesquelles les valeurs de ces inconnues peuvent se situer. Ensuite, les problèmes de programmation linéaire correspondants sont résolus.

Spécifier les limites dans lesquelles les valeurs des inconnues doivent se situer dans un problème de programmation en nombres entiers peut s'écrire comme suit :

En pratique, dans de nombreux cas, les limites des valeurs inconnues sont déjà incluses dans le système de contraintes du problème de programmation en nombres entiers, ou elles peuvent être déterminées en fonction du contenu économique du problème. Sinon, nous pouvons supposer que la limite inférieure est , et la limite supérieure est , où M.- un nombre positif assez important.

Comment la méthode branch-and-bound aide-t-elle à clarifier les limites des valeurs acceptables des inconnues ?

Premièrement, un problème de programmation linéaire correspondant à un problème de programmation en nombres entiers est résolu, par exemple, en utilisant la méthode du simplexe. Supposons que le plan optimal dans ce problème soit trouvé et que la valeur de l'une de ses coordonnées soit un nombre fractionnaire. Ensuite, vous devrez créer deux nouveaux problèmes de programmation linéaire. Comment faire cela ?

Notons la partie entière de la coordonnée par . Dans l'un des nouveaux problèmes de programmation linéaire, la limite inférieure de la valeur des coordonnées sera le nombre , c'est-à-dire la partie entière de la valeur des coordonnées augmentée de un. Il s'écrira ainsi :

.

Dans un autre nouveau problème de programmation linéaire, la limite supérieure de la valeur de coordonnée sera la partie entière de la valeur de coordonnée elle-même. Il s'écrira ainsi :

Ainsi, deux nouveaux problèmes « ont dérivé » du premier problème de programmation linéaire, dans lequel les limites des valeurs admissibles d'une inconnue ont changé. Lors de la résolution de chacun de ces problèmes, trois cas sont possibles :

• le plan optimal n'est pas un entier,
• le plan optimal est entier,
• le problème n'a pas de solutions.

Ce n'est que dans le premier cas qu'il est possible de « ramifier » de nouvelles tâches de la manière indiquée ci-dessus. Dans les deuxième et troisième cas, le « ramification » s'arrête.

A chaque itération de résolution d’un problème de programmation en nombres entiers, un problème est résolu. Introduisons le concept : une liste de problèmes de programmation linéaire à résoudre. Dans la liste, sélectionnez le problème à résoudre à l'itération correspondante. Lors d'itérations ultérieures, la liste change, car les problèmes résolus n'y sont plus inclus et, à leur place, de nouvelles tâches « dérivées » des tâches précédentes sont incluses dans la liste.

Afin de limiter le « branchement », c'est-à-dire de réduire le nombre de problèmes à résoudre, il est nécessaire de déterminer à chaque itération la limite inférieure de la valeur maximale de la fonction objectif. Cela se fait comme suit :

D'après l'algorithme de résolution d'un problème de programmation en nombres entiers à l'aide de la méthode branch-and-bound, sur chaque p La ième itération nécessite 4 étapes.

Exemple 2. Résolvez le problème de programmation d’entiers suivant à l’aide de la méthode branch andbound. Trouver le maximum de la fonction objectif

sous un système de restrictions

Solution. Supposons que les limites suivantes des valeurs optimales des inconnues soient données ou déterminées :

.

Puisque le problème est donné sous forme normale, il a un plan entier et une borne inférieure sur la valeur maximale de la fonction objectif.

La liste des tâches à résoudre comprend la 1ère tâche :

Itération 1.

Étape 1. En utilisant méthode simplexe la solution au 1er problème a été obtenue :

Puisque le plan trouvé n’est pas un nombre entier, l’étape 4 suit.

Étape 4. Puisque le plan optimal a une coordonnée fractionnaire de 1,2, alors . En appliquant les bornes des valeurs inconnues du 1er problème, on obtient de nouveaux problèmes. Dans le 2ème problème, la limite inférieure de est , et dans le 3ème problème, la limite supérieure de est .

6 réponses

Suivez cet exemple : supposons que les équations soient :

7 = x + 3a + 4z + 9s 12 = 4x + 2a + 3z + 7s

Il y a 2 équations et 4 inconnues. Vous pouvez définir 2 des inconnues comme paramètres, de sorte que le système aura autant d'équations qu'il y a d'inconnues :

7 - (4z + 9w) = x + 3a 12 - (3z + 7w) = 4x + 2a

Nous utiliserons x et y comme inconnues. Il peut être résolu et laisser w et z comme paramètres dans la solution linéaire :

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

Vous devez maintenant rendre les numérateurs divisibles par 10, le dénominateur. S'il existe une solution, vous pouvez vérifier tous les paramètres de 1 à 10.

En général, vous faites ceci :

• Choisissez les paramètres de manière à ce qu'il y ait autant d'inconnues que d'équations. Essayez de laisser les inconnues qui génèrent la plus petite valeur absolue pour le déterminant (dans l'exemple, c'était 10, mais il serait préférable de choisir y et z car ce serait |det|=3)
• Résoudre un système linéaire et créer une réponse en fonction des paramètres
• Vérifiez les valeurs des paramètres de 1 à la valeur absolue det (s'il existe une solution, vous la trouverez à ce stade) jusqu'à ce qu'il y ait une solution entière pour toutes les inconnues (c'est pourquoi vous choisissez la plus petite valeur déterminante avant) et vérifiez s'il est positif (ce n'est pas le cas comme illustré dans l'exemple).

Désolé s'il s'agit d'une force brute lors de la dernière étape, mais il existe au moins une option pour minimiser la plage de test. Peut-être existe-t-il une meilleure façon de résoudre le système final d'équations diophantiennes, mais je ne connais aucune méthode.

MODIFIER1

Il existe une méthode pour éviter de forcer brutalement la dernière partie. Encore une fois, dans l'exemple, vous devez faire :

22 = 3w + z (congru, mod 10) 16 = 29w + 13z (congru, mod 10)

Application du module :

2 = 3w + z (congru, mod 10) 6 = 9w + 3z (congru, mod 10)

Vous pouvez rendre le système de congruence triangulaire (élimination gaussienne) en multipliant la congruence avec son inverse modulo 10 et en additionnant les autres. L'inverse de 9 modulo 10 est -1, on multiplie donc la dernière congruence :

2 = 3w + z (congru, mod 10) -6 = -9w + -3z (congru, mod 10)

Équivalent:

2 = 3w + z (congru, mod 10) 4 = w + 7z (congru, mod 10)

Multipliez ensuite par -3 et ajoutez au premier :

2 - 3*4 = 3w + z -3w - 21z (congru, mod 10) 4 = w + 7z (congru, mod 10)

Équivalent:

10 = -20z (congru, mod 10) 4 = w + 7z (congru, mod 10)

Ensuite, vous résolvez de haut en bas (cet exemple semble être vrai pour toute valeur de z). Il peut y avoir un certain degré de liberté si vous avez plus de paramètres que de congruences, mais ils sont équivalents et vous pouvez définir les paramètres redondants sur n'importe quelle valeur, de préférence la plus petite valeur de 1.

Faites-moi savoir s'il y a autre chose qui n'est pas clair !

Si je comprends bien le problème, vous avez plusieurs colis, chacun avec des frais de port différents. Vous souhaitez payer ces frais de port à partir du pool de timbres dont vous disposez. Vous pouvez résoudre le problème avec toute la programmation. La solution ci-dessous résout tous les packages à la fois. Vous aurez un nombre de variables égal à numPackages * numStampDenominations (probablement gênant pour un grand nombre de packages).

La contrainte d'égalité ressemble à Aeqx = beq. La matrice Aeq pour deux packages avec quatre marques (numVarsnumPackages) ressemble à ceci :

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

La première ligne contient les coefficients de contrainte (valeurs de tampon) pour le lot 1. Les coefficients non nuls sont les valeurs de tampon. La variable null associée aux autres packages n'est pas prise en charge.

Le deuxième ensemble de contraintes (inégalités) concerne le pool de marques dont je dispose. La contrainte d'inégalité ressemble à A * x = b. La matrice A pour 4 tampons et 8 variables (numPackages * numStampDenominations) ressemble à ceci :

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

La fonction de coût est f"*x, qui représente le nombre total de dés. Ses coefficients sont simplement des unités, spécifiées sous forme de vecteur colonne.

Un script est exécuté dans Matlab qui résout le problème de la manière décrite. Il sera probablement formulé de la même manière dans les octaves proposées par GNU, à la manière de Matlab. Matlab ou Octave ne sont peut-être pas la bonne solution pour vous, mais ils vous indiquent au moins ce qui fonctionne et vous donnent un bac à sable pour développer une solution.

% La valeur de chaque tampon disponible sous forme de matrice 4x1 sv = [.21; 0,68 ; .47 ; .01]; % Le nombre de chaque timbre disponible sous forme de matrice 4x1 sq = ; % Nombre de démonstrations m = size(sv, 1); % L'affranchissement requis pour chaque colis sous forme de matrice 4x1 % -- probablement lu à partir d'un fichier affranchissement = [.89;.50;1.01;.47;.47]; % Nombre de colis -- juste le nombre de lignes d'affranchissement packageCount = size(postage, 1); % Le nombre de variables est m*packageCount numVar = m*packageCount; % limite inférieure -- zéros d'une dénomination donnée lb = zéros(numVar,1); % limite supérieure -- utiliser des contraintes pour la limite supérieure ub = ; % La fonction de coût -- minimiser le nombre de timbres utilisés % min(f"*x) f = ones(numVar,1); % contraintes entières intcon = 1:numVar; % Construire une matrice de contraintes d'affranchissement Aeq = zeros(numVar, packageCount ); for i = 1:packageCount first = i*m - 3; last = first + 3; ) ); pour r = 1:m pour j = 1:m c = (j-1)*m + 1; A(c,r) = 1; fin fin x = intlinprog(f, intcon, A", b, Aeq ", beq, lb, ub)

J'essaierais l'approche suivante (notez que je n'ai jamais eu à faire face à ce problème, alors prenez cette réponse comme une tentative de résoudre le problème avec vous plutôt que comme une véritable réponse analytique).

Vous trouvez simplement des solutions comme s'il s'agissait d'un système normal, vous pouvez donc trouver une infinité de solutions :

Exemple:

Y=x+3

alors la vraie paire de nombres (2,5) est une solution réelle possible pour ce système, une fois que vous avez une infinité de solutions, vous limitez simplement le sous-ensemble de solutions produites par des nombres entiers.

Bien sûr, vous avez des limites, dans notre cas la solution n'a qu'une seule variable libre, nous pouvons donc écrire toutes les solutions comme ceci :

(x,x+3)

Étonnement:

S’il y a un nombre irrationnel quelque part, il n’y a pas de solutions entières :

(x, x+pi) => ni le 1er ni le 2ème nombre ici ne peuvent être entiers en même temps

Vous pouvez donc trouver des solutions entières si et seulement si votre « infinité de solutions » se limite à des nombres entiers ou rationnels.

Disons que vous avez le vecteur suivant :

(3x, (2/5)y, y, x, x+y)

Alors toute la solution pourrait être :

X=3 y=10/2

Si vous estimez que la réponse ne vous convient pas, dites simplement : je la supprimerai pour ne pas recevoir de points bonus.

Introduction

2.2 Un exemple de résolution d'un problème de programmation en nombres entiers

3. Programmation paramétrique

3.1 Problème avec un paramètre dans la fonction objectif

3.2 Problème avec un paramètre dans les termes libres du système de contraintes

3.3 Problème dont la fonction objectif et le membre de droite des contraintes contiennent un paramètre

4. Programmation paramétrique entière

4.1 Un exemple de résolution d'un problème de programmation en nombres entiers avec un paramètre dans la fonction objectif

4.2 Un exemple de résolution d'un problème de programmation en nombres entiers avec un paramètre dans les termes libres du système de contraintes

Conclusion

Références

Introduction

La programmation mathématique est une discipline mathématique qui traite de l'étude de problèmes extrêmes et du développement de méthodes pour les résoudre.

De manière générale, la formulation mathématique du problème extrême consiste à déterminer la plus grande ou la plus petite valeur de la fonction objectif

dans les conditions , où et reçoivent des fonctions, et sont des nombres réels.

En fonction des propriétés des fonctions

et la programmation mathématique peut être considérée comme un certain nombre de disciplines indépendantes impliquées dans l'étude et le développement de méthodes permettant de résoudre certaines classes de problèmes.

Tout d’abord, les problèmes de programmation mathématique sont divisés en problèmes de programmation linéaire et non linéaire. De plus, si toutes les fonctions

et linéaire, alors le problème correspondant est un problème de programmation linéaire. Si au moins une de ces fonctions est non linéaire, alors le problème correspondant est un problème de programmation non linéaire.

La branche la plus étudiée de la programmation mathématique est la programmation linéaire. Un certain nombre de méthodes, d'algorithmes et de programmes efficaces ont été développés pour résoudre les problèmes de programmation linéaire.

Des classes distinctes de problèmes de programmation mathématique sont les problèmes de programmation linéaire entière, paramétrique et fractionnaire.

Le premier chapitre de ce travail aborde les concepts de base de la programmation linéaire.

Dans le deuxième chapitre, un problème de programmation en nombres entiers est formulé et des méthodes pour le résoudre sont considérées. Un exemple de résolution d'un problème de programmation en nombres entiers est donné.

Le troisième chapitre traite des problèmes de programmation paramétrique et montre des exemples de méthodes pour résoudre divers problèmes de ce type.

Dans le quatrième chapitre, des problèmes de programmation paramétrique entière sont formulés et étudiés. Le problème de la programmation paramétrique entière avec un paramètre dans la fonction objectif a été résolu indépendamment de deux manières. Sur la base de la solution à ce problème, une méthode permettant de résoudre des problèmes de ce type est déterminée. Un problème de programmation en nombres entiers avec un paramètre dans les termes libres du système de contraintes a également été résolu.

Lors de la rédaction du diplôme, la littérature de référence suivante a été utilisée : Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Programmation mathématique, Ashmanov S.A. Programmation linéaire. Certains exemples sont tirés des livres de V.I. Kopylov. Conférences et cours pratiques sur la programmation mathématique, Akulich I.L. Programmation mathématique en exemples et problèmes. Les algorithmes pour les méthodes de résolution de problèmes de programmation entière et paramétrique, à mon avis, sont les plus accessibles et les plus complets dans le livre d'I.L.

1. Concepts de base de la programmation linéaire

Il existe trois formes principales de problèmes de programmation linéaire en fonction de différents types de contraintes.

Tâche standard

(1.1) (1.2)

Sous forme matricielle, le problème (1.1) - (1.2) a la forme :

- matrice de coefficients. Un vecteur est appelé vecteur de coefficients de forme linéaire, un vecteur est appelé vecteur de contraintes.

Problème canonique la programmation linéaire a la forme :

ou, sous forme matricielle :

Tâche générale programmation linéaire - certaines contraintes sont exprimées sous forme d'inégalités, d'autres - sous forme d'équations. De plus, la condition de non-négativité ne s’applique pas à toutes les variables :

Théorème. Les problèmes de programmation linéaire standard, canonique et générale sont équivalents.

Commentaire. Le cas où dans un problème standard il est nécessaire de minimiser une forme linéaire peut facilement être réduit à un problème pour le maximum - nous devrions considérer le problème pour le maximum de la fonction

sous les mêmes restrictions sur les variables que dans le problème d’origine.

2. Programmation entière

Une partie importante des problèmes économiques liés aux problèmes de programmation linéaire nécessite une solution entière. Il s'agit notamment de tâches dans lesquelles les variables désignent le nombre d'unités de produits indivisibles, par exemple la répartition des tâches de production entre les entreprises, la découpe des matériaux, les équipements de chargement, la répartition des navires le long des lignes, des avions entre les vols, ainsi que les tâches pour le production de produits indivisibles. Si une unité constitue une petite partie du volume total de production, alors la solution optimale est trouvée en utilisant la méthode simplex habituelle, en l'arrondissant à des unités entières, en fonction de la signification du problème. Sinon, l’arrondi peut donner une solution loin de la solution entière optimale.

2.1 Énoncé du problème et méthodes de solution

Un problème de programmation en nombres entiers est formulé de la même manière qu'un problème de programmation linéaire, mais inclut l'exigence supplémentaire selon laquelle les valeurs des variables qui composent la solution optimale doivent être des entiers non négatifs.

Vous devez trouver la valeur minimale d'une fonction linéaire

(2.1.1)

sous restrictions

(2.1.2) (2.1.3)
- entier. (2.1.4)

Supposons que le problème de programmation linéaire ait un polyèdre de solutions illustré à la Fig. 2.1. Si nous imposons l’exigence d’un nombre entier, alors l’ensemble admissible de solutions à un tel problème est une collection de points entiers isolés et non

est convexe. Si nous ajoutons de nouvelles contraintes reliant des points entiers externes, puis utilisons l'ensemble convexe entier délimité par les axes de coordonnées et un nouveau contour comme polyèdre solution, nous obtenons un nouveau problème de programmation linéaire avec les propriétés suivantes :

1) le nouveau polyèdre solution contient tous les points entiers contenus dans le polyèdre solution d'origine ; l'un de ses points d'angle est entier ;

2) puisque la fonction linéaire atteint son optimum au coin du polyèdre solution, la construction d'un tel polyèdre assure l'intégrité de la solution optimale.

Si vous trouvez une solution au problème (2.1.1)-(2.1.4) en utilisant la méthode du simplexe, alors elle peut s'avérer être un nombre entier ou non (un exemple de problème de programmation linéaire dont la solution est toujours un nombre entier , c'est le problème du transport). Dans le cas général, pour déterminer le plan optimal pour les problèmes (2.1.1)-(2.1.4), des méthodes spéciales sont nécessaires. Actuellement, il existe plusieurs méthodes de ce type, dont la plus célèbre est la méthode Gomori.

Méthode Gomori. La méthode de résolution du problème proposée par Gomori est basée sur la méthode du simplexe et comprend les éléments suivants. La méthode du simplexe est utilisée pour trouver le plan optimal pour le problème sans tenir compte de la condition entière. Si le plan optimal est entier, alors les calculs sont terminés, mais si le plan optimal contient au moins une composante fractionnaire

, alors une contrainte supplémentaire est imposée qui prend en compte la nature entière des composantes du plan, et les calculs utilisant la méthode du simplexe sont poursuivis jusqu'à ce qu'un nouveau plan optimal soit obtenu. S'il est également non entier, alors la contrainte suivante est faite, en tenant compte de l'intégrité. Le processus d'ajout de contraintes supplémentaires est répété jusqu'à ce qu'un plan optimal entier soit trouvé ou qu'il soit prouvé que le problème n'a pas de plans entiers. Cela se produit si, pour une fraction, tout ce qui se trouve dans cette ligne s'avère être des nombres entiers.