Procédé Gomory. La solution des problèmes de programmation entiers

Les problèmes de poids de l'économie, de la planification et même les questions d'autres sphères de problèmes de la vie humaine associés à des variables liées aux nombres entiers. En raison de leur analyse et la recherche des meilleures façons d'aborder la notion de défis extrêmes. Ses caractéristiques est la fonction ci-dessus prend une valeur entière, et la tâche elle-même est considéré les mathématiques comme la programmation entière.

Les principales utilisations des problèmes avec variables, un nombre entier, est l'optimisation. Un procédé qui utilise un nombre entier de programmation linéaire, également appelée la méthode de coupure.

méthode Gomory a été nommé d'après le mathématicien, d'abord développé en 1957-1958 algorithme est encore largement utilisé pour résoudre des problèmes entiers de programmation linéaire. La forme canonique du problème de programmation entier permet accessible et présente entièrement les avantages de cette méthode.

méthode Gomori appliquée à une programmation linéaire complique grandement la tâche de trouver les valeurs optimales. Après est une exigence intégralité fondamentale, plus tous les paramètres du problème. Il y a des cas où le problème en ayant des plans valides (entier), la présence dans la fonction objective des restrictions sur l'ensemble recevable, la décision a été prise pour atteindre au maximum. Cela est dû à l'absence de celui-ci est des solutions intégrales. Sans les mêmes conditions, en règle générale, sous la forme d'une décision est vecteur approprié.

Pour justifier les algorithmes numériques pour la résolution des problèmes, il est nécessaire d'effectuer des superpositions supplémentaires conditions différentes.

En utilisant la méthode de Gomory, considèrent généralement beaucoup de plans pour le soi-disant problème des solutions de polyèdre limitées. Sur cette base, l'ensemble de tous plan intégral a une valeur finie pour la tâche.

En outre, la fonction intégrale de la garantie supposent que les valeurs des coefficients sont également entiers. Malgré la gravité de ces conditions, les plus faibles qu'ils gèrent quelques-uns.

méthode Gomory implique essentiellement des restrictions de construction, qui coupent des solutions qui ne sont pas non entier. Dans ce cas, il n'y a pas de coupure pas de plan de solutions entières.

L'algorithme pour résoudre le problème consiste à trouver des options appropriées méthode simplex, sans prendre en compte les conditions de l' intégralité. Si toutes les composantes du plan optimal contient les décisions relatives à des nombres entiers, on peut supposer que l'objectif de programmation entier est atteint. Peut-être que l'on trouve insolubilité du problème, donc nous avons la preuve que le problème de la programmation entière n'a pas de solution.

La variante, lorsque les composants de la solution contient nombre non entier. Dans ce cas, une nouvelle restriction est ajouté à toutes les contraintes du problème. Les nouvelles restrictions sont caractérisées par un certain nombre de propriétés. Il convient tout d'abord d'être linéaire, devrait être coupé de l'ensemble trouvé du plan optimal non entier. Ni solution entière ne doit pas être perdu, coupé.

Lors de la construction des restrictions doivent être choisies composante d'un plan optimal avec la plus grande fraction. Il est cette limitation sera ajoutée à la table simplex existante.

Nous trouvons la solution du problème résultant en utilisant une transformation simplex classique. Nous vérifions la solution du problème de l'existence d'un plan optimal entier, si la condition est satisfaite, le problème est résolu. Si le résultat a été obtenu à nouveau avec la présence de solutions non entières, puis on introduit une contrainte supplémentaire, et répétez le processus de calcul.

Après avoir effectué un nombre fini d'itérations, nous obtenons un programme optimal du problème posé devant la programmation entière, ou de prouver l'insolubilité du problème.