método Gomory. La solución de los problemas de programación entera

Los problemas de peso de la economía, planificación e incluso problemas de otros ámbitos de la vida humana problemas asociados a las variables relacionadas con los números enteros. Como resultado de su análisis y la búsqueda de las mejores maneras de abordar la noción de desafíos extremos. Sus características es la característica anterior toma un valor entero, y la tarea en sí se considera la matemática como programación entera.

Los principales usos de los problemas con variables, un número entero, es la optimización. Un método que utiliza un número entero de programación lineal, también llamado el método de corte.

método Gomory se nombró por el matemático, desarrollado por primera vez en 1957 a 1958 algoritmo es todavía ampliamente utilizado para resolver problemas de programación lineal de enteros. La forma canónica del problema de programación entera permite accesible y divulga plenamente las ventajas de este método.

método de Gomori aplicado a una programación lineal complica enormemente la tarea de encontrar los valores óptimos. Después de integralidad es un requisito fundamental, más todos los parámetros del problema. Hay casos en que el problema haciendo que los planes válidos (entero), la presencia en la función objetivo de las restricciones sobre el conjunto admisible, la decisión llega a alcanzar la máxima. Esto se debe a la falta de ella es soluciones integrales. Sin las mismas condiciones, por regla general, en forma de una decisión es vector apropiado.

Para justificar los algoritmos numéricos para la resolución de problemas es necesario para llevar a cabo la superposición adicional de diferentes condiciones.

Utilizando el método de Gomory, por lo general en cuenta muchos planes para el llamado problema de las soluciones poliedro limitados. Sobre esta base, el conjunto de todas Plan integral tiene un valor finito para la tarea.

También, para la función integral de garantía asumen que los valores de los coeficientes también son números enteros. A pesar de la gravedad de estas condiciones, más débil que manejan unos pocos.

método Gomory esencialmente implica restricciones de construcción, que cortan soluciones que no son no integral. En este caso, no hay corte ningún plan soluciones enteras.

El algoritmo para resolver el problema consiste en encontrar opciones adecuadas método simplex, sin tener en cuenta las condiciones de integralidad. Si todos los componentes del plan óptimo contiene las decisiones relacionadas con números enteros, se puede suponer que se logre el objetivo de programación entera. Tal vez que se encuentra la insolubilidad del problema, por lo que tenemos una prueba de que el problema de programación entera no tiene solución.

La variante, cuando los componentes de la solución óptima contiene el número no entero. En este caso, se añade una nueva restricción a todas las restricciones del problema. Las nuevas restricciones se caracterizan por una serie de propiedades. En primer lugar, debe ser lineal, debe ser cortado de la conjunto encontrado de no entero plan óptimo. Ni solución entera no debe perderse, cortado.

Cuando las restricciones de construcción deben ser elegidos los componentes de un plan óptimo con la fracción más alta. Es esta limitación se añadirá a la tabla simplex existente.

Encontramos la solución del problema resultante utilizando la transformación simple convencional. Comprobamos la solución del problema de la existencia de un plan óptimo número entero, si se cumple la condición, entonces el problema está resuelto. Si se obtuvo el resultado de nuevo con la presencia de soluciones no enteros, a continuación, se introduce una restricción adicional, y repetir el proceso de cálculo.

Después de haber llevado a cabo un número finito de iteraciones, alcanzamos un programa óptimo del problema planteado frente a la programación entera, o probar la insolubilidad del problema.