Método de Homori. Resolver problemas de programación enteiros

A masa de problemas de natureza económica, problemas de planificación e ata a solución de preguntas de outras esferas da actividade da vida humana está relacionada coas variables que se refiren a números enteiros. Como resultado da súa análise e da busca de métodos óptimos de solución, aparecía o concepto de problema extremal. As súas características son a característica anterior para ter un valor enteiro, eo problema en si é tratado en matemáticas como programación enteira.

A dirección principal do uso de tarefas con variables que toman valores enteiros é a optimización. Un método que usa programación lineal enteira tamén se denomina método de recorte.

O método de Homori conseguiu o seu nome polo nome de matemático, que desenvolveu por primeira vez en 1957-1958 o algoritmo, que aínda se utiliza ampliamente para resolver problemas de programación lineal enteiros. A forma canónica do problema de programación enteira fai posible descubrir completamente as vantaxes deste método.

O método Gomori para a programación lineal complica significativamente o problema de atopar valores óptimos. Ao final, o enteiro é a condición principal, ademais de todos os parámetros do problema. Non é raro un problema, ao ter un plan (enteiro) viable, se a función obxectivo ten restricións sobre un conxunto admisible, a solución non chega ao máximo. Isto é debido á ausencia de solucións enteiras. Sen esta mesma condición, como norma, un vector axeitado está en forma de solución.

Para acreditar algoritmos numéricos na resolución de problemas, faise necesario superponer varias condicións adicionais.

Usando o método de Gomori, o conxunto de plans de problemas xeralmente considérase un límite chamado polytope de solucións. A partir disto segue que o conxunto de todos os plans integrais para o problema en cuestión ten un valor finito.

Ademais, para garantir a integridade dunha función, suponse que os valores do coeficiente tamén son enteiros. A pesar da gravidade de tales condicións, poden ser enviados un pouco.

O método de Homori, de feito, implica a construción de restricións que cortan decisións que non son enteiras. Neste caso, non hai ningún corte de ningunha solución para o plan de valor enteiro.

O algoritmo para resolver o problema implica atopar as variantes apropiadas polo método simplex, sen ter en conta as condicións enteiras. Se en todos os compoñentes do plan óptimo existen solucións relacionadas cos enteiros, podemos supoñer que se logra o obxectivo de programación enteira. É posible que se revele unha indeterminación do problema, así que obtemos unha proba de que o problema de programación enteiro non ten solución.

Unha variante é posible cando hai números non enteiros nos compoñentes da solución ideal. Neste caso, engádese unha nova restrición a todas as restricións da tarefa. Unha nova limitación caracterízase pola presenza dunha serie de propiedades. Primeiro de todo, debe ser lineal, debe cortar o plan non enteiro a partir do conxunto ideal atopado. Non se debe perder ningunha solución de número enteiro, cortada.

Cando se constrúe a restrición, debe escoller o compoñente do plan ideal coa maior parte fraccionada. É esta restrición que se engadirá á táboa simplex existente.

Atopamos a solución do problema obtido mediante transformacións simples normais. Comprobamos a solución do problema para a presenza dun plan óptimo de enteiro, se a condición está satisfeita, entón o problema está resolto. Se de novo o resultado obtívose coa presenza de solucións non enteiras, introducimos unha restrición adicional e repetimos o proceso de cálculo.

Tras realizar un número finito de iteracións, obtemos un plan ideal para o problema plantexado antes da programación enteira, ou demostrar a falta de resolución do problema.