Beaucoup de tâches à caractère économique, problèmesla planification et même la résolution de problèmes d'autres sphères de la vie humaine sont associées à des variables liées aux nombres entiers. À la suite de leur analyse et de la recherche de solutions optimales, la notion de problème extrême est apparue. Sa particularité est la fonction ci-dessus de prendre une valeur entière, et le problème lui-même est considéré en mathématiques comme une programmation entière.
Comme principal sens d'utilisationles problèmes avec les variables prenant des valeurs entières sont l'optimisation. Et la méthode utilisant la programmation linéaire en nombres entiers est également appelée méthode de découpage.
La méthode Gomori tire son nom du nommathématicien, qui a développé pour la première fois en 1957-1958 un algorithme encore largement utilisé pour résoudre des problèmes de programmation linéaire en nombres entiers. La forme canonique du problème de programmation d'entiers vous permet de révéler facilement et pleinement les avantages de cette méthode.
Méthode de Gomori appliquée au linéairela programmation complique considérablement le problème de la recherche de valeurs optimales. Après tout, l'entier est la condition principale, en plus de tous les paramètres du problème. Il n'est pas rare pour un problème, ayant des conceptions (entiers) réalisables, et si les fonctions objectives ont des contraintes sur l'ensemble des possibles, la solution n'atteint pas son maximum. Cela est dû à l'absence de solutions exactement entières. Sans cette condition, en règle générale, un vecteur approprié est trouvé sous la forme d'une solution.
Pour justifier les algorithmes numériques dans la résolution de problèmes, il devient nécessaire d'imposer diverses conditions supplémentaires.
En utilisant la méthode Gomori, on considère généralement l'ensembledes plans du problème par le polyèdre dit solution borné. Sur cette base, il s'ensuit que l'ensemble de tous les plans entiers pour la tâche en cours a une valeur finie.
Aussi, pour s'assurer qu'ils sont entiers, les fonctions supposent que les coefficients des valeurs sont également des entiers. Malgré la gravité de ces conditions, il est possible de les affaiblir un peu.
La méthode Gomori, en fait, implique la construction de contraintes qui coupent des solutions qui ne sont pas non entières. Dans ce cas, pas une seule solution du plan entier n'est coupée.
L'algorithme de résolution du problème comprendtrouver des options appropriées en utilisant la méthode du simplexe, sans tenir compte des conditions entières. Si tous les composants du plan optimal contiennent des solutions entières, alors l'objectif de programmation d'entiers peut être considéré comme atteint. Il est possible que le problème soit indécidable, nous obtenons donc une preuve que le problème de programmation d'entiers n'a pas de solution.
Une option est possible lorsque les composantsla solution optimale contient des nombres non entiers. Dans ce cas, une nouvelle contrainte est ajoutée à toutes les contraintes de la tâche. La nouvelle limitation est caractérisée par un certain nombre de propriétés. Tout d'abord, il doit être linéaire, il doit couper un plan non entier de l'ensemble optimal trouvé. Aucune solution entière ne doit être perdue, tronquée.
Lors de la construction de la contrainte, il faut choisir le composant du plan optimal avec la plus grande partie fractionnaire. C'est cette restriction qui sera ajoutée à la table simplex existante.
Nous trouvons une solution au problème obtenu en utilisanttransformations simplex ordinaires. Nous vérifions la solution du problème pour la présence d'un plan optimal entier, si la condition est remplie, alors le problème est résolu. Si à nouveau le résultat a été obtenu avec la présence de solutions non entières, alors nous introduisons une contrainte supplémentaire et répétons le processus de calcul.
Après avoir effectué un nombre fini d'itérations, on obtient un plan optimal pour le problème posé à la programmation entière, ou on démontre l'indécidabilité du problème.
