El método Gomori es un ejemplo de solución en detalle. Elaboración de una restricción adicional (sección Gomori). Algoritmo para la solución gráfica del problema.

en tareas programación entera a diferencia de las tareas programación lineal Se introduce una restricción adicional sobre las variables: sólo pueden tomar valores enteros.

En algunos problemas, por ejemplo, tipo de transporte, esta condición se cumple automáticamente si los datos de origen (cantidades de bienes enviados y recibidos) se expresan en números enteros. Pero en un problema general de programación lineal, los métodos convencionales para resolver valores enteros no garantizan si las cantidades originales son números enteros o fraccionarios.

EN notación matemática tarea común La programación entera se ve así:

maximizar

bajo condiciones

xj≥ 0, xj - entero.

Objetivos económicos La programación lineal requiere con mayor frecuencia solución entera. Esto se aplica a tareas en las que las variables indican el número de unidades de productos, equipos, trabajadores indivisibles (tareas mejor distribución tareas de producción entre empresas, problemas de optimización del programa de producción de empresas individuales, tareas carga óptima equipos, etcétera). A menudo, estos problemas se resuelven utilizando el método simplex habitual seguido del redondeo de los valores obtenidos. variables a números enteros. Pero en este caso, sólo se puede obtener una cierta aproximación al plan entero verdaderamente óptimo.

En otro grupo de problemas de programación lineal, las cantidades a determinar son las capacidades de producción que satisfacen más eficazmente una necesidad determinada. Dado que los "portadores" de la capacidad de producción son empresas individuales, equipos indivisibles, etc., estos problemas también se reducen a problemas de programación lineal entera.

Los problemas de corte racional de material dimensional (tareas para minimizar el desperdicio) también tienen valores enteros, ya que las variables en ellos, por regla general, indican el número de espacios en blanco iniciales cortados de una forma u otra.

En todos los problemas mencionados se puede encontrar una solución. métodos convencionales programación lineal con posterior ajuste y obtención de un plan de números enteros más o menos cercano al óptimo. Pero hay problemas para los cuales una solución no entera no tiene sentido. Estos incluyen problemas de elección en los que los valores numéricos de las variables sirven sólo para determinar una alternativa (“esto o lo otro”, “sí-no”).

Los modelos de selección de números enteros incluyen algunos problemas de programación operativa, por ejemplo, problemas sobre la secuencia óptima para poner en producción varios productos (piezas). Digamos que necesitas determinar el orden de inicio. norte piezas, cada una de las cuales se procesa secuencialmente en varias máquinas. variables xij igual a uno si la parte j debe ejecutarse después de la parte i y cero, en todos los demás casos. Por cada fijo j , como para todos i , sólo uno de norte Las variables pueden ser iguales a uno, por lo que las restricciones del problema incluyen lo siguiente:

Minimizado tiempo total procesamiento de todas las piezas en máquinas de este grupo. Una solución no entera a tal problema no tiene sentido.

Existen varios métodos para resolver problemas de programación entera. Mejor conocido método gomori, basado en el uso del método simplex.

consideremos conceptos matemáticos: congruencia números, entero Y parte fraccionaria de un número. Número A congruente con el numero b si y sólo si la diferencia a-b es un número entero. La congruencia se indica con tres líneas horizontales ( ≡ ); De este modo, A ≡ b , Si a-b es un número entero.

Por ejemplo: 5 / 3 ≡ 2 / 3 , porque 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , porque - 1 / 3 - 2 / 3 = 1.

Todos los números enteros son congruentes entre sí y congruentes con cero. Los elementos no enteros se pueden representar como la suma de las partes enteras y fraccionarias del número. A = [a ] + {a }. Corchetes significa tomar la parte entera del número contenido en ellos, rizado, tomar la parte fraccionaria del número.

parte entera de un numero A se llama el entero más grande [ a ], sin exceder A .

parte fraccionaria de un numero A se define como el número no negativo más pequeño ( a ), congruente con el número A . parte fraccionaria de un numero A igual a la diferencia entre el número A y toda la parte de ella: ( a }=A - [a ]

Por ejemplo, para A = 2 1 / 3 [a ]= 2 (un) = 1 / 3

para un = - 2 1 / 3 [a ]= -3 (a) = 2 / 3

Propiedades de la congruencia numérica:

1. Si A ≡ b , Eso ( A } = {b }.

2. {A +b } = {A } + {b }.

3. Si norte es un número entero, entonces para cualquier A

na ≡ {n / A } ≡ norte {A }.

Al resolver problemas de programación entera utilizando el método Gomori, la primera etapa coincide con el cálculo habitual de algoritmo simplex. La solución resultante en vista general satisfará todas las condiciones del problema, excepto el requisito del número entero (es posible, por supuesto, que ya se pueda obtener una solución entera en la primera etapa). Si entre los valores de las variables en el plan óptimo (punto A en la Fig. 13) hay fraccionarios, entonces se elabora una restricción adicional, como si se "cortara" parte fraccionaria solución (línea 1 en la Fig. 13), pero dejando vigentes todas las restricciones del problema que debe satisfacer el plan óptimo. Se agrega una restricción adicional a las restricciones originales del problema y se aplica nuevamente el procedimiento simplex al sistema extendido. Si solución óptima resulta ser no entero nuevamente (punto B en la Fig. 13), luego se agrega una restricción adicional más (línea 2 en la Fig. 13) y se repite el proceso de cálculo. El algoritmo nos permite llegar a una solución entera óptima (si existe) en un número finito de pasos (punto C en la Fig. 13).

Arroz. 13. Método de corte de Gomori

Ejemplo Resolver un problema de programación entera. Para la compra de equipamiento para el nuevo centro de producción se destinaron 20 unidades monetarias. El equipo debe colocarse en una superficie no superior a 38 m2. Una empresa puede encargar dos tipos de equipos: máquinas tipo A más potentes que cuestan 5 unidades monetarias, requieren un área de producción de 8 m 2 (incluidos los pasillos) y proporcionan una productividad de 7 mil unidades de producción por turno; Las máquinas menos potentes del tipo B cuestan 2 unidades monetarias, ocupan un área de 4 m 2 y producen 3 mil unidades de producción por turno.

Denotemos por incógnita 1 número de autos comprados A y hasta incógnita 2 - la cantidad de autos B comprados, obtenemos condiciones matemáticas tareas:

maximizar 7x 1 + 3x 2 → máximo

bajo condiciones: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (enteros).

Con la ayuda de variables adicionales x 3 y x 4, las desigualdades originales se transforman en ecuaciones (reducidas a forma canónica):

5x1 + 2x2 + x3 = 20

8x1 + 4x2 + x4 = 38

Si las variables principales x 1 y x 2 son números enteros, de las ecuaciones se deduce inmediatamente que las variables x 3 y x 4 solo pueden tomar valores enteros.

El problema se resuelve primero sin tener en cuenta el requisito de números enteros.

Una tabla simplex tiene siguiente vista:

Base	CON	Plan					θ
X1	x2	X3	x4
X 1 →X 3							20/5=4 minutos
x4							38/8=4,75
f(x) = 0	-7	-3
X1				2/5	1/5		4:2/5=10
X2 →X4				4/5	-8/5		6:4/5=7,5 minutos
f(x) =28		-1/5	7/5
X1						-1/2
x2		7,5			-2	5/4
f(x) =29,5				1/4

En el plan óptimo, X 1 = 1, X 2 = 7,5; máximo función objetivo es 29,5. Por lo tanto, es necesario comprar una máquina del tipo A y 7 máquinas del tipo B (no hay suficiente dinero ni espacio para 8 máquinas), entonces el volumen de producción será f(x) = 7 × 1 + 3 × 7 = 28 mil unidades de producción.

Encontremos una solución entera usando el método de Gomori. Para la variable X2, que ha recibido un valor no entero en términos de diseño, elaboramos la siguiente ecuación, que se deriva directamente de lo anterior tabla simplex:

7,5 = X 2 – 2X 3 + 1,25X 4.

X2 = 7,5 + 2X3 – 1,25X4.

Esta ecuación, obviamente, también debe ser válida para una solución entera admisible del problema.

Como X 2 es un número entero, la expresión del lado derecho de la ecuación también es un número entero; por lo tanto, el valor del lado derecho de esta ecuación es congruente con cero:

7,5 + 2Х 3 – 1,25Х 4 ≡ 0,

–2Х 3 + 1,25Х 4 ≡ 7,5.

Dadas las propiedades de congruencia anteriores, y también el hecho de que X 3 y X 4 son números enteros, esta expresión se puede transformar en la siguiente:

(-2)X 3 + (1,25)X 4 ≡ {7,5} ;

de aquí obtenemos:

0,25X4 ≡ 0,5.

Como X 4 es un número entero no negativo, tenemos:

0,25X 4 = 0,5, o 1,5, o 2,5, ...;

por eso,

0,25X4 ≥ 0,5.

La desigualdad resultante se convierte en una ecuación y se suma a sistema original restricciones, que ahora contiene las siguientes tres ecuaciones:

5x1 + 2x2 + x3 = 20

8x1 + 4x2 + x4 = 38

0,25x 4 – x 5 = 0,5.

Repitiendo el proceso de solución método simplex en relación al sistema extendido de restricciones, obtenemos un nuevo plan óptimo en el que los valores de las variables incluidas en la base son iguales a: X 1 = 2; X2 = 5; X 4 = 2 (área libre restante).

Así, se ha obtenido una solución entera óptima al problema: bajo estas restricciones, la productividad máxima (29 mil unidades de producción) se asegura comprando 2 máquinas del tipo A y 5 máquinas del tipo B.

LECCIÓN PRÁCTICA

MÉTODO DE RAMIFICACIÓN Y CONTINUACIÓN

Este método se puede aplicar para resolver problemas de programación discreta total y parcialmente entera.

Considere el modelo

bajo restricciones

Supongamos que para cada variable entera es posible establecer límites superior e inferior, dentro de los cuales, por supuesto, está contenida valores optimos

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

Generalmente hj = 0, pero esta condición no es necesaria. El problema se resuelve mediante el método simplex. Si X k toma valores fraccionarios, creemos que la solución óptima al problema satisfará la restricción lineal X k ≤ D k , o restricción lineal X k ≤ D k + 1 , Dónde Dk =[X k ] – el número entero más cercano al valor X k ; rek + 1 – entero más cercano en lado grande de X k . Al mismo tiempo H j ≤ D k ≤ V j – 1 . Luego es necesario resolver un par de problemas de programación lineal utilizando el método simplex:

A.

EN.

Obtenemos un proceso iterativo representado como un árbol, cuya parte superior corresponde a la solución del problema original, y las dos ramas conectadas a él son soluciones a un par de problemas de programación lineal A y B. Los valores resultantes del Las funciones objetivo pueden ser menores o iguales al valor de la función objetivo del problema original. f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Cada uno de los dos nuevos vértices de rama obtenidos puede tener sus propias ramas adicionales.

1) El proceso de bifurcación iterativa continúa hasta que se obtiene una solución entera entre los planes recibidos, y el valor de la función objetivo debe ser mayor o valores iguales funciones de los objetivos de otros vértices ramificados.

2) Si en el siguiente paso de iteración ambos problemas tienen soluciones no enteras, entonces para ramificar aún más el vértice correspondiente al problema con gran valor funciones objetivo. Para una de las variables que ha recibido valores fraccionarios, se elaboran nuevas restricciones para los siguientes problemas de programación lineal.

3) Si en el siguiente paso de iteración uno de los problemas tiene una solución entera, y entre los valores de las variables en el segundo problema hay fraccionarios, entonces el problema que tiene valor más alto funciones objetivo. Si se trata de un problema que ha recibido una solución entera, entonces el proceso finaliza, pero si se trata de un problema con valores fraccionarios de variables, se lleva a cabo un proceso de ramificación adicional.

4) Si en el siguiente paso de iteración uno de los problemas no tiene solución y el segundo problema tiene valores fraccionarios entre los valores de las variables en la solución resultante. Luego, para el primer problema, el proceso de bifurcación se detiene y para una mayor transformación del segundo problema, se selecciona una de las variables no enteras, para lo cual restricciones adicionales Para nueva pareja Problemas de programación lineal.

5) Si en el siguiente paso de iteración uno de los problemas no tiene solución, y para el otro se obtiene una solución entera, y no hay otras opciones con un valor entero grande de la función objetivo y para las cuales se pueda continuar con la ramificación , luego el proceso finaliza y la solución encontrada es la solución entera óptima de las tareas originales.

Si la tarea seleccionada conduce a una pausa (punto muerto) o el valor de la función es menor que en la tarea B.1 f(X) A.4< f(X)­ В,1 ., luego se vuelve a la tarea B.1 y se produce una nueva bifurcación.

Figura 14. Diagrama de flujo del algoritmo de rama y límite

Arroz. 15. Método de ramificación y encuadernación.

Introducción

Una gran clase de problemas de optimización aplicada se reducen a problemas de programación lineal entera. Para resolver estos problemas se utilizan ampliamente métodos de corte, diseñados para resolver un problema entero general, comparándolo con algún problema no entero, cuya solución permite encontrar una solución.

Primeros métodos de solución. problema de enteros Gomori propuso la programación de poda lineal y se denominó algoritmo de Gomori.

1. Planteamiento del problema

El método Gomori está diseñado para resolver problemas de programación lineal entera. Al considerar el método Gomori, resolveremos esta tarea en forma canónica.

1.1 Forma canónica

consideraremos problema canónico programación entera con norte variables y metro condiciones, complementadas por la condición entera:

Dónde c = (c 1 , c 2 , ... , c norte ), x = (x 1 , x 2 , ... , x norte )- vector de dimensión norte, - su producto escalar(), también llamada función objetivo, A- matriz de dimensiones norte´ metro, b- vector de columna de dimensión metro.

La condición de números enteros complica significativamente el problema de programación lineal (1.1), (1.2). Puede suceder que el problema (1.1)-(1.3) tenga planes (enteros) admisibles, la función objetivo esté limitada al conjunto admisible, pero no se alcance su máximo. Por ejemplo en la tarea:

no hay soluciones enteras, mientras que sin esta condición cualquier vector de la forma puede servir como solución

.

En relación con lo anterior, al justificar algoritmos numéricos para resolver problemas del tipo (1.1)-(1.3), es necesario imponer varias condiciones adicionales. Suponemos que el conjunto. incógnita Los planos del problema (1.1), (1.2) (sin la condición de entero) están acotados, es decir, son un poliedro.

De esta condición se deduce que el conjunto INCÓGNITA* todos los planos enteros del problema (1.1)-(1.3) son finitos. Supondremos que todos los coeficientes cj, j=1, 2 , …, norte, las funciones objetivo son números enteros.

De la condición II se deduce que para cualquier plan entero incógnitaÎ incógnita* significado<do, incógnita>maximizable forma lineal- un número entero. En este caso decimos que la integridad de la función objetivo está garantizada.

Aunque las condiciones I y II para los problemas (1.1) - (1.3) son bastante estrictas, es posible debilitarlas sólo ligeramente para obtener los resultados necesarios.

1.2 Reducción a forma canónica

El problema de la programación lineal entera se puede formular de forma algo diferente a como se explicó anteriormente. Entonces, por ejemplo, en lugar de la condición (1.2), puede haber otra forma de restricciones de escritura.

Podemos pasar de dicha notación a (1.2) agregando una nueva variable a cada ecuación, entonces las restricciones tomarán la forma

Las variables agregadas tendrán peso cero en la función objetivo.

Tenga en cuenta que para obtener, dependiendo del tipo de desigualdad, no solo se debe sumar, sino también restar la variable según el signo de la desigualdad, teniendo en cuenta la condición (1.3).

Si en el problema original no es por alguna variable xyo Si no se cumple la condición de positividad, entonces debe reemplazarse por la diferencia de dos nuevas variables positivas.

2. Ideas generales sobre métodos de recorte.

Existe una posibilidad fundamental de reducir la solución del problema (1.1) - (1.3) a encontrar el plan óptimo para algún problema de programación lineal (sin la condición de que las variables sean enteras). Dejar incógnita- un conjunto poliédrico definido por las condiciones (1.1), (1.2). A través de INCÓGNITA* denota el conjunto de todos los vectores enteros incógnita*, acostado incógnita. En otras palabras INCÓGNITA* está dado por las condiciones (1.1)-(1.3), es decir

Por definición INCÓGNITA*Í incógnita. Denotaremos por X z casco convexo del conjunto INCÓGNITA*. Entonces X zÍ incógnita.

Así, hemos asociado al conjunto poliédrico X algún conjunto convexo X zÍ incógnita según la siguiente regla: X z es el conjunto convexo mínimo que contiene todos los vectores enteros de incógnita.

Según el supuesto I, incógnita es un poliedro, de ahí el conjunto INCÓGNITA* Ciertamente. Entonces el conjunto convexo X z también es un poliedro, y por lo tanto tenemos que X z puede especificarse mediante un número finito de desigualdades lineales.

Para resaltar la principal diferencia entre el conjunto. X z de muchos incógnita, demos la siguiente definición.

Definición 1. Un poliedro cuyos puntos extremos son números enteros (es decir, todas sus coordenadas son números enteros) se llama poliedro entero.

Obviamente el poliedro X z- entero, ya que sus puntos extremos son sólo puntos del conjunto INCÓGNITA* planes enteros.

Justificación para estudiar el cumplimiento incógnita® X z es el siguiente hecho simple.

Teorema 1. Cualquier plan de referencia óptimo para un problema de programación lineal es una solución al problema (1.1)-(1.3).

Prueba. vamos` incógnita*- plan de referencia óptimo del problema (2.1), incógnita*- alguna solución al problema original (1.1)-(1.3). ` incógnita*Î X zÍ incógnita, Eso

<do,`incógnita*> £ <do, incógnita*>.

Por otra parte, desde incógnita* es un plan entero, entonces incógnita*Î INCÓGNITA*Í X z, y por lo tanto

<do,`incógnita*> ³ <do, incógnita*>,

dónde

<do,`incógnita*> = <do, incógnita*>.

La demostración del teorema está completa.

Destacamos que el Teorema 1 establece sólo la posibilidad fundamental de reducir la solución de un problema de programación lineal entera a la búsqueda de planos de referencia de un problema de programación lineal de la forma (2.1). La principal dificultad al utilizar esta característica es la definición explícita del poliedro. X z sistema de desigualdades lineales para luego aplicarlo a la resolución del problema (2.1) métodos numéricos programación lineal. Es probable que este problema sea computacionalmente tan difícil como problema original buscando el plan entero óptimo.

Pese a ello, la idea de “estrechar” el conjunto incógnita resultó útil y condujo a la creación de varios algoritmos para resolver problemas de programación lineal entera, llamados "métodos de corte".

Presentemos la idea de los métodos de poda. Supongamos que logramos construir la secuencia ( lr}, r = 0, 1 , 2 , ..., problemas de programación lineal, cada uno de los cuales está determinado por su propio poliedro x r y una función objetivo para todos<do, incógnita>:

Además, esta secuencia de tareas tiene las siguientes propiedades:

) X 0 =X, es decir. como X0 tome el conjunto de planos para el problema (1.1), (1.2);

) Xrz = Xz, r=1,2,…;

) si al resolver un problema lr el vector óptimo resultante x r * no satisface la condición de número entero, entonces no es un plan de tareas L r+1, es decir. x r *Ï X r+1.

Tenga en cuenta que si en algún paso r vector x r *- resolución de problemas lr- resultó ser un número entero, entonces es una solución al problema original (1.1)-(1.3) debido a la propiedad 2) de la secuencia lr.

Está intuitivamente claro que la construcción secuencial de tareas lr, r=1,2,..., da en cierto sentido una aproximación del conjunto X z con la ayuda de muchos x r.

Métodos para construir una secuencia ( lr), aseguran la finitud del proceso de resolución del problema (1.1)-(1.3), fueron propuestos por primera vez por Gomori.

3. Descripción del método Gomori

Consideremos ahora el algoritmo de Gomori para resolver problemas de programación lineal entera. Este método pertenece a los métodos de corte e implementa las ideas descritas en el párrafo anterior.

3.1 El concepto de corte correcto y la forma más sencilla su construcción

Programación lineal del algoritmo de Homero.

Introduzcamos el límite correcto, que subyace a muchos métodos numéricos para resolver problemas de programación lineal entera.

Definición 2. Sea x* el plan óptimo para el problema (1.1), (1.2), que no es un número entero. Desigualdad

donde g = (g 1 , gramo 2 , …, gramo norte), se denomina corte correcto si cumple los requisitos:

a) para un vector incógnita* la desigualdad no se cumple, es decir incógnita*> > g 0 (condición de corte).

b) si incógnita es el plan entero del problema (1.1), (1.2) (es decir, el plan del problema (1.1)-(1.3)), entonces incógnita- satisface (3.1) (condición de corrección).

Está claro que agregar la desigualdad (3.1) a las condiciones (1.1), (1.2) reduce el conjunto admisible incógnita, conservando todos sus puntos enteros. De este modo aplicación consistente Esta técnica proporciona una especie de aproximación en varias etapas del poliedro. X z utilizando restricciones lineales.

Hay dos problemas con el concepto de recorte adecuado. El primero de ellos es formular algoritmo general cortes para un problema de programación lineal entera arbitraria. El segundo problema es construir un límite correcto de tal manera que asegure la solución del problema (1.1)-(1.3) en un número finito de pasos, es decir para que de la multitud incógnita cada vez se cortaron áreas suficientemente grandes.

Tenga en cuenta que el segundo requisito es bastante sutil. Como confirmación, consideremos el método de construcción de un límite correcto propuesto por Danzig.

Dejar incógnita*- apoyar el plan óptimo del problema (1.1), (1.2), s y w - listas de números de variables básicas y no básicas, respectivamente, correspondientes a alguna base del plan incógnita*. Entonces xj*= 0 en j Ay. Teniendo en cuenta esta propiedad, no es difícil construir un punto de corte correcto para el diseño x* si no es un número entero: la desigualdad puede servir como tal:

De hecho, la condición de corte se cumple trivialmente, ya que . La condición de corrección también se cumple, ya que si x = (x1,x2 , …,xn) es el plan entero del problema (1.1), (1.2), luego el valor teniendo en cuenta las condiciones xj ³ 0, jÎ w, puede ser menor que la unidad sólo en el caso de que xj= 0 para todos jÎ w. Pero en ese caso el plan incógnita- referencia, y la base del plan se puede tomar como base incógnita*. El plan de referencia está determinado únicamente por su base, de la cual obtenemos que la desigualdad implica x=x *. Esto último, sin embargo, es imposible, ya que incógnita es un vector entero, y incógnita* No lo es.

Este método de construir un corte correcto, a pesar de su simplicidad, resultó ineficaz, ya que la finitud del proceso de solución está garantizada solo para una clase estrecha de problemas de programación lineal entera.

Describamos el método para construir un límite correcto propuesto por Gomori. Para un número arbitrario a, a través de [ a] denotaremos su parte completa, es decir [ a] es el número entero más grande k número no excedente a.

Parte fraccionaria ( a) números a llamó al número ( a} = a - [a]. Observemos la propiedad obvia de la parte fraccionaria de un número arbitrario: 0 £ ( a}<1, причем {a) = 0 si y sólo si a - un número entero.

Dejar incógnita*- solución de referencia del problema (1.1), (1.2), que no es entera, - su base y B- la tabla simplex correspondiente en forma de coordenadas.

Consideremos el sistema reducido de ecuaciones correspondiente a esta base (y la tabla B) plan

incógnita*:

Desde xj*= 0 en jÎw, entonces sólo las cantidades pueden ser no enteras x0* = <do, incógnita*>, x yo *, i Es.

Dejar s- tal índice (0 £ s £ norte) que el número xs*- no completo. consideremos sª fila en una tabla simplex B (s aésima ecuación en el sistema (3.2), (3.3)) y componer la expresión

Teorema 2. Si incógnitaÎ INCÓGNITA* es el plan entero del problema (1.1), (1.2), entonces

Prueba. Usando la relación

asj = [asj] + {asj }, j = 0, 1, 2, … , norte, de (3.3) con i= s obtenemos

dónde

El lado izquierdo de esta desigualdad contiene un número entero, por lo tanto el número

también entero. De que xj ³ 0, jÎw, usando la propiedad de la parte fraccionaria, obtenemos

aquellos. - zs(incógnita) < 1, или zs(incógnita) > -1. considerando que zs(incógnita) - número entero, finalmente aceptaremos zs(incógnita) ³ 0.

Consecuencia. Si xs*(= as0) - número no entero y conjunto INCÓGNITA* los planos del problema de enteros (1.1)-(1.3) no están vacíos, entonces entre los números ( asj}, j=1, 2, …, norte, los hay positivos.

De hecho, todos los números ( asj), son obviamente no negativos. Supongamos que ( asj} = 0, j = 1, 2, …, norte.

Si INCÓGNITA* no vacío y incógnita* Î INCÓGNITA*, Eso zs(incógnita*)= - {as0), eso zs(incógnita*) es un número entero, desde 0< {as0} < 1.

Comentario. En la demostración del Teorema 2, utilizamos el Supuesto II de que se garantiza que la función objetivo es entera. Válido en caso s= valor 0

es un número entero (siempre que incógnitaÎ INCÓGNITA*) sólo cuando el número x0 = < do, incógnita> - entero.

De esto se desprende

Teorema 3. si el numero xs*- no es un número entero, entonces la desigualdad

es el límite correcto.

Prueba. Comprobemos la condición de corte en la Definición 2. Dado que xs* = as0, entonces del hecho de que xs*- no es un número entero, obtenemos la desigualdad ( as0) > 0. Desde xj*= 0 en jО w, entonces

y por lo tanto el vector incógnita* no satisface la desigualdad (3.5). La condición de corrección se deriva de la declaración. zs(incógnita) ³ 0 en el teorema 2.

3.3 El primer algoritmo de Gomory

Pasemos a la presentación del primer algoritmo de Gomori.

Denotemos el problema (1.1), (1.2) por l 0. Gomori propuso encontrar el máximo lexicográfico del problema en la primera etapa de su algoritmo. l 0. Denotaremos por

incógnita(0) = (incógnita 0 (0), incógnita 1 (0), …, incógnita norte(0))

(n+1)-vector dimensional tal que ( incógnita 1 (0), incógnita 2 (0), …, incógnita n (0)) - solución al problema lexicográfico l 0 , un incógnita 0 (0) = - valor de forma lineal. En los casos en que esto no cause malentendidos, llamaremos incógnita(0) - plan optimo tarea lexicográfica l 0 (aunque según la terminología generalmente aceptada, un plan es un vector compuesto por el último norte coordenadas vectoriales incógnita(0)).

Tenga en cuenta también que incógnita(0) será plan de referencia, así como un pseudoplan del problema estrictamente admisible l 0 .

Si x(0) es un vector entero, entonces obviamente es una solución al problema (1.1) - (1.3).

De lo contrario, encontramos el índice mínimo s, 0 £ s £ n, para el cual el valor xs(0) no es un número entero. Dejar B(0) - tabla simplex en forma de coordenadas correspondiente al vector incógnita(0). Usando coeficientes s En la fila de esta tabla (es decir, los coeficientes del sistema reducido (3.2), (3.3)), utilizando la técnica descrita anteriormente, se construye el límite correcto.

Se introduce una variable auxiliar. xn+1 y la tarea es considerada. l 1:

La siguiente etapa es encontrar el máximo lexicográfico del problema. l 1. Una ventaja importante del algoritmo de Gomori es el hecho de que el pseudoplan estricto inicial admisible para su aplicación simplex dual-método a la tarea l 1 se encuentra sin dificultad. De hecho, es fácil ver que como pseudoplan podemos tomar el vector

De hecho, es obvio que y(1) satisface (junto con vectorform incógnita(0)) restricciones (3.6), (3.7) problemas l 1, y solo se viola una de las restricciones (3.8): xn+1 (0)= - (un s 0 } < 0. Кроме того, y(1) es la referencia para el sistema de ecuaciones (3.6), (3.7), porque si - base del plan incógnita(0) entonces el sistema

es linealmente independiente y sirve como base para y(1). demostremos que y(1) es un pseudoplan estrictamente admisible. Para ello, construiremos una tabla simplex correspondiente a la base vectorial especificada. y(1). Para hacer esto, solo necesita agregar a continuación a la tabla B(0) línea

Donde w = ( j 1 , j 2 , …, jn -metro) - lista de números de variables no básicas correspondientes a la tabla B(0) plan de referencia incógnita(0). Desde incógnita(0) es un pseudoplan estrictamente admisible, entonces cada columna b j, jÎw, mesas B(0) lexicográficamente positivo: b j > 0, j Ay. De esto se deduce que en la tabla simplex en forma de coordenadas correspondiente al vector de soporte y(1), cada columna (excepto la primera, coincidiendo con y(1)) es lexicográficamente positivo:

Así, tener a nuestra disposición una solución incógnita(0) tarea lexicográfica l 0 y la tabla simplex correspondiente en forma de coordenadas B(0), sin ningún cálculo adicional encontramos el pseudoplan inicial estrictamente admisible y(1) para la tarea l 1 y construya la tabla simplex correspondiente en forma de coordenadas.

Puede suceder que la tarea lexicográfica l 1 no tiene solución. En este caso, la solución al problema de números enteros (1.1) - (1.3) debe detenerse ya que

Teorema 4. si en el problema l 1 no existe un máximo lexicográfico, entonces el conjunto incógnita* los puntos enteros del problema (1.1) - (1.3) están vacíos.

Prueba. ya que muchos incógnita vectores que satisfacen las condiciones Hacha = b, incógnita³ 0, según el supuesto I está acotado, entonces el conjunto de planes para el problema también está acotado l 1. Por tanto, la única razón por la que este problema puede no tener un mínimo lexicográfico es que su conjunto de planos está vacío. Demostremos que en este caso el conjunto incógnita* también vacío.

Supongamos lo contrario, es decir. Qué incógnita* ¹ Æ, y deja incógnita* = (incógnita 1 * , incógnita 2 * , …, xn*) О X*. Por el teorema 2 encontramos que la cantidad

no negativo. Pero esto significa que vector = ( incógnita 1 * , incógnita 2 * , …, xn * , xn+1 *) es el plan de tareas l 1, en contradicción con lo anterior. El teorema está demostrado.

Dejar incógnita(1) = (incógnita 0 (1), incógnita 1 (1), …, xn(1), xn+1 (1)) - solución al problema lexicográfico l 1. Partiendo de la tarea l 1 y vector incógnita(1), los problemas se construyen de manera similar lr, r= 2, 3,…, y soluciones incógnita(r) Î Â norte +1+r tareas lexicográficas correspondientes.

Tenga en cuenta que el algoritmo de Gomori determina de forma única la secuencia incógnita(r), r= 0, 1, 2, …, que se deriva de la unicidad de la elección s. Prestemos también atención al hecho de que el índice s siempre no supera n: 0 s n. De hecho, si todo xj(r) en j= 0, 1, 2,…, n son números enteros, entonces se deduce del Teorema 2 que xn +1 (r), xn +2 (r), … - también números enteros.

Si en algún paso r vector

incógnita(r) = (incógnita 0 (r), incógnita 1 (r), …, xn(r), …, xn +r (r))

resulta ser un número entero, entonces el vector ( incógnita 0 (r), incógnita 1 (r), …, xn(r)) es una solución al problema (1.1) - (1.3). La prueba de esta afirmación es obvia.

Transición del vector incógnita(r) al vector incógnita(r+1) el uso del algoritmo Gomori descrito se denomina iteración grande, en contraste con las iteraciones intermedias del método simplex dual, que se denominan pequeñas.

La pregunta principal relacionada con el primer algoritmo de Gomori es: ¿es siempre posible obtener un vector entero en un número finito de iteraciones grandes? incógnita(r).

Demostremos la finitud del primer algoritmo de Gomory. Usaremos la siguiente notación:

incógnita(0) = (incógnita 0 (0), incógnita 1 (0), …, xn(0));

Dónde ( incógnita 1 (0), …, xn(0)) es la solución al problema lexicográfico L0, y incógnita(0) = - el valor correspondiente de la forma lineal (función objetivo).

y(1) = (incógnita 0 (0), incógnita 1 (0), …, xn(0), xn +1),

el vector y(1) sirve como pseudoplan inicial estrictamente admisible al resolver el problema L1 usando el método simplex dual en forma de coordenadas: ` y(1) = (`y 0 (1), `y 1 (1), …, `y norte(1), `y norte+1 (1)) es el vector resultante de y(1) como resultado de la primera (pequeña) iteración del método simplex dual en forma de coordenadas.

La notación se introduce de manera similar.

incógnita(r), y(r + 1), `y(r + 1), r = 1, 2, …

De las propiedades del método simplex dual en forma de coordenadas se deduce

y(r) >`y(r) ³ incógnita(r).

Lema 1. Dejar s- el índice mínimo para el cual el número xs(0) no es un número entero. Entonces

Prueba. Dado que de (3.9) se sigue y(1) >`y(1), entonces son posibles dos casos:

En el caso 1, el enunciado del lema se satisface trivialmente con la definición de orden lexicográfico.

Considere el caso 2. De acuerdo con las reglas del método simplex dual, en la primera (pequeña) iteración de resolución del problema l 1 variable está sujeta a derivación de entre las básicas xn+1 porque en el vector y(1) xj(0) ³ 0, j Oh w, xn +1 < 0. Пусть kО w es un índice tal que

Para cualquiera jО w, si -(a sj} < 0. По правилам симплексного метода в число базисных вводится переменная x k.

El caso 2 sólo es posible bajo la condición b yo = 0, i = 0, 1, 2, …, s- 1. Porque incógnita(0) - pseudoplan de tarea estrictamente admisible l 0 , entonces todas sus columnas b j, jО w, tabla simplex B(0) lexicográficamente positivo; en particular b k> 0 . Por lo tanto, la coordenada b sk de esta columna debe ser no negativo. Tenga en cuenta que b sk=un sk(es decir, 0 £ s £ norte Y sО w), por la condición (3.10) el número a sk- no cero. Es por eso

a sk> 0 y un sk³ (un sk}

Según la fórmula de transformación de tablas simplex, tenemos

Recordando que xs(0) = as0, obtenemos:

.

Teniendo en cuenta (3.11), obtenemos la siguiente estimación:

El lema está probado.

Comentario. Si el problema original (1.1) - (1.3) es admisible, entonces, según el corolario del Teorema 2, existe el índice k que satisface la condición (3.10).

Consecuencia. Relación justa

Válido en r= 1, esta desigualdad se deriva del lema y de la segunda desigualdad (3.9). Para obtener esta declaración de forma arbitraria r, hay que aprovechar el hecho de que y j(r) = xj(r) a 0 £ j £ norte y la desigualdad y(r) ³ incógnita(r) en (3.9).

Teorema 5. Si se cumplen los supuestos I y II, entonces el primer algoritmo de Gomori requiere sólo un número finito de iteraciones grandes.

Para verificar la verdad del teorema, es necesario demostrar que para algunos r vector incógnita(r) = (incógnita 0 (r), incógnita 1 (r), …, xn +r (r)) - número entero. Para ello, a su vez, basta con demostrar la naturaleza entera del vector ( incógnita 0 (r), incógnita 1 (r), …, xn(r)), ya que del Teorema 2 se sigue que todos los números xn +1 (r), xn +2 (r), …, xn +r (r) también están enteros. Recordemos también que el índice mínimo s para el cual el número xs(r) no es entero no siempre excede de n: 0 £ s £ n. Antes de pasar a la prueba principal, demostramos el siguiente lema:

Lema 2. Para cualquiera j, 0 £ j £ norte, existe tal número Rj, que en r ³ Rj todos los numeros xj(r) - números enteros e iguales al mismo número entero xj(Rj).

Prueba. Dejar s, 0 £ s £ norte, - el índice mínimo para el cual no se cumple el enunciado del Lema. denotemos

En el caso cuando s= 0, pongamos R = 0.

Dejar r, yo- tales índices que R £ r£ l, y números xs(r), xs(yo) - no completo. Demostremos que entonces [ xs(r)] > [xs(yo)]. Válido por definición s tenemos

en ese caso s- el índice mínimo para el cual el número xs(r) - número entero. Por corolario del Lema 1 tenemos [ xs(r)] ³ xs(yo).

considerando que xs(yo) no es un número entero, tenemos xs(yo) > [xs(yo)], de donde obtenemos la declaración deseada. ya que muchos incógnita Los planes del problema (1.1) - (1.3) son limitados, entonces cualquier valor es limitado. xs(r), 0 £ s £ norte, r= 1, 2,…. Por tanto, una cadena infinita de desigualdades de la forma [ xs(r)] > [xs(yo)] > ... no puede existir y, por lo tanto, en la secuencia xs(r), r= 0, 1,…, no puede haber una cantidad infinita de números no enteros. De manera similar, se demuestra que esta secuencia no puede contener infinitos números enteros diferentes.

El lema está probado.

Volvamos a la demostración del teorema. Dejar

donde estan los numeros Rj aparecen en la formulación del Lema 2. Entonces, de acuerdo con este lema, todos los números xj(R), 0 £ j £ norte, - entero. Del Teorema 2 obtenemos que el vector incógnita(R) - número entero. Por lo tanto, el algoritmo de Gomory no requiere más que R iteraciones.

El teorema está demostrado.

3.5 Notas sobre la implementación práctica del primer algoritmo de Gomori

En implementación práctica En el primer algoritmo de Gomori, un problema importante es el aumento en el número de restricciones, lo que conduce a un aumento en el tamaño de las tablas simplex. Gomori propuso una forma de eliminar este inconveniente del algoritmo, que es la siguiente.

) Durante la solución del problema lr Usando el método simplex dual, en cada pequeña iteración, debe usar una regla de inferencia refinada a partir del número de vectores base para resolver problemas de programación lineal usando el método simplex: si la primera columna de la tabla simplex tiene varios elementos negativos b i 0 (= xyo), i =1, 2, …, norte, …, norte + r, entonces la variable con el número mínimo debe eliminarse de entre las básicas.

) Si durante la próxima pequeña iteración al implementar la tarea lr todas las variables principales incógnita 1 , incógnita 2 , …, xn resultó no negativo, entonces se siguió aplicando el método simplex dual al problema lr debería detenerse, a pesar de que es posible que aún no se haya alcanzado su máximo lexicográfico. Si todas las variables xj, j = 1, 2, …, norte, resultó ser un número entero, luego, según el teorema 2, todas las variables auxiliares xn +k , k = 1, 2, …, r, son números enteros y no negativos. Esto significa, como ya se sabe, que el vector ( incógnita 0 , incógnita 1 , incógnita 2 , … , xn) es una solución al problema entero original. De lo contrario, pasamos a una nueva iteración grande.

) Fila de la tabla simplex correspondiente a la variable auxiliar xn +r, se elimina tan pronto como la variable xn +r se declara no básico. Recordemos que esto sucede en la primera pequeña iteración de resolución del problema. lr.

) Si en el curso de la resolución del problema lr variable xn +r nuevamente cae en el número de los básicos, entonces la fila correspondiente no se restaura.

Está claro que cuando se siguen las reglas 3), 4), las dimensiones de la tabla simplex en el primer algoritmo de Gomori no aumentan: cada tabla contiene norte+ 2 líneas correspondientes a las variables principales incógnita 0 , incógnita 1 , … , xn y la variable auxiliar actual xn +r en el momento de su introducción) y norte - metro+1 columnas (desde el número norte - metro las variables no básicas no cambian).

) En la primera pequeña iteración de la resolución del problema. lr Se elige +1 como la variable derivada de la base. xn +r+1, a pesar de que los valores de otras variables auxiliares en este momento también pueden ser negativos.

Tenga en cuenta que la regla 5) es en realidad redundante, ya que cuando se cumplen las reglas 3) y 4), no sabemos nada sobre el valor de las variables restantes. xn +1 , …, xn +r en el momento de la transición a la tarea lr +1 . esta regla resaltado solo para resaltar la diferencia entre los algoritmos bajo consideración.

Tenga en cuenta que cuando se utiliza la regla 2) la secuencia resultante incógnita ’ (r) puede no ser el máximo lexicográfico del problema lr, ya que los valores de algunas de las variables auxiliares pueden ser negativos.

Sin embargo, por coherencia incógnita ’ (r), r= 0, 1, 2,…, obtenido usando las reglas 1) y 2), se conserva una propiedad importante: esta secuencia es única.

Sólo queda demostrar que cuando se utilizan las reglas 1) - 4), el algoritmo de Gomori sigue siendo finito, ya que su finitud significará que conduce al objetivo: encontrar una solución entera al problema (1.1) - (1.3). De hecho, la finitud del número R iteraciones grandes significan que el vector incógnita ’ (R) número entero.

Observemos, en primer lugar, que cuando utilizamos la regla 2) el número de pequeñas iteraciones para resolver el problema lr por supuesto, no más de lo necesario para encontrar su máximo lexicográfico.

Teorema 6. La secuencia x’(r) que surge en el proceso de aplicación del algoritmo de Gomori, la regla refinada 1) - 4), es finita.

Prueba. Tenga en cuenta que en la demostración del teorema 5 sobre la finitud de la secuencia x(r), solo se utilizaron dos circunstancias que regulan la aparición de esta secuencia: el método para construir el corte correcto y el hecho de que en cualquier tabla simplex actual todas las columnas b j, jÎw, son lexicográficamente positivos. Así, eliminar la línea correspondiente a la variable auxiliar sólo puede afectar a esta última circunstancia. Sin embargo, esto no puede ser así, como se muestra en el siguiente lema.

Lema 3. En cualquier tabla simplex que surja durante el algoritmo de Gomori, refinada por las reglas 1) - 4), para cualquier columna

hay desigualdad

Prueba. Supongamos que el enunciado del lema no es válido para algunos kО w. Desde b k, entonces esta suposición significa que

Por la definición de una tabla simplex en forma de coordenadas, tenemos

Para cualquiera incógnita Î Rn +1+r, si se viola el enunciado del lema durante la solución del problema lr. La fórmula (3.13) teniendo en cuenta (3.12) significa que un cambio en el valor de la variable x k no afecta el valor xyo, i = 0, 1, 2, …, norte. En otras palabras, para el mismo conjunto de valores xyo, 0£ i£ norte, variable x k puede tomar un valor arbitrario. De ello se deduce, en primer lugar, que k ³ norte+ 1, y en segundo lugar, que el supuesto aceptado (3.13) es incorrecto, ya que desde el valor de cualquier variable auxiliar x k, k ³ norte+ 1, como se desprende de (3.7), está determinado únicamente por los valores de las variables principales.

Porque eliminar filas correspondientes a variables auxiliares no afecta la propiedad de las b columnas j, jÎ w, sea lexicográficamente positivo, entonces estas líneas no son necesarias en absoluto. De hecho, teniendo en cuenta las reglas 1) - 2) variable xn +r, convirtiéndose en uno de los básicos, sigue siendo básico hasta el final de los cálculos, y su línea no es necesaria para determinar la variable introducida en la base según las reglas del método simplex.

Así, los elementos de fila correspondientes a la variable xn +r, no participe en las fórmulas del método simplex dual para calcular los valores de todas las demás variables.

Dado que, como se señaló, el índice s regular la formación del corte correcto no excede norte, 0 £ s £ norte, entonces no se requieren variables auxiliares para estos fines.

4. Implementación informática

en esto proyecto del curso El programa está diseñado para encontrar una solución a un problema de programación lineal entera utilizando el método Gomori.

El módulo de software utiliza el algoritmo descrito en la parte teórica, teniendo en cuenta los comentarios sobre aplicación práctica Método elaborado por Gomori.

La entrada de datos en el módulo del programa se realiza a partir de un archivo. Los resultados del programa se pueden enviar a un archivo, a una pantalla o a una impresora. Formato de archivo de entrada:

…

…

…

…

Dónde norte- número de variables, metro- número de restricciones, do 1 , do 2 , … , c norte- coeficientes de la forma lineal maximizada, un ij- elementos de la matriz A, bj- componentes vectoriales b. A, b - caracterizar restricciones [ver. (1.2)].

Archivo de entrada de ejemplo:

2 5 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

Referencias:

1. Abramov L.A., Kapustin V.F. Programación matemática. - L.: Editorial de la Universidad Estatal de Leningrado, 1981. -328 p.

Belousova G.S. Programación lineal. Guía de estudio. -Krasnoyarsk: Ciencia, 1975. -107 p.

Kuznetsov Yu.N. y otros. Programación matemática: libro de texto. - 2ª ed., revisada. y adicional -M.: Escuela Superior, 1980. -300 p.

Ashmanov S.A., Programación lineal. M.: Ciencia. 1969. -240 s

Gabásov R.I. Kirillova F.M., Métodos de programación lineal. Minsk: ciencia. 1977. -174 s

El método de Gomori para resolver problemas de programación entera es método de corte .

La esencia del método es construir restricciones que eliminen las soluciones no enteras de un problema de programación lineal, pero no eliminen ningún plan entero. Para hacer esto, primero decida tarea debilitada Programación lineal sin tener en cuenta la condición de las variables enteras.

Si la solución resultante a un problema de programación lineal es entera, entonces el problema de programación entera también está resuelto y la solución encontrada es óptima para el mismo. Si en la solución encontrada a un problema de programación lineal una o más variables no son enteras, entonces para encontrar una solución entera al problema, se agrega una nueva restricción lineal que elimina las soluciones no enteras. Continuando con la resolución del problema extendido mediante el método simplex dual, teniendo en cuenta esta restricción se obtiene un plan entero.

Para encontrar una solución entera al problema utilizando el método Gomori, se utiliza el siguiente algoritmo.

Debería ser lineal;

Se debe cortar el plan no entero óptimo encontrado;

No debe truncarse ningún plan de números enteros.

Si hay varias variables de base no enteras, entonces para crear una restricción seleccionamos un componente del plan óptimo. con la mayor parte fraccionaria (si hay varias de estas variables, seleccione cualquiera).

Esta variable corresponde a una fila de la tabla simplex llamada línea que realiza el corte (línea generadora ).

Para presentar el método, introducimos los siguientes conceptos. Dejar a– número real.

Bajo parte entera algún número A se entiende como el entero máximo [ a], sin exceder esto.

Bajo parte fraccionaria algún número A significa el número más pequeño no negativo
tal que la diferencia entre éste y A Hay [ a] – parte entera del número).

Para la variable base seleccionada con la mayor parte fraccionaria encontrar la parte fraccionaria
esta variable y las partes fraccionarias de todos los coeficientes de las variables iª línea del sistema de restricciones
(línea de producción).

denotemos
Y
partes enteras de números Y . Valores fraccionarios
Y
(
) se definen de la siguiente manera

Para hacer esto, se escribe una ecuación a partir de la fila generadora de la tabla simplex, suponiendo que la primera metro Las variables son básicas para un plan óptimo dado.

o

Movemos todas las partes enteras de los coeficientes en una dirección, dejando todas las partes fraccionarias en la otra:

Porque
<1, то заменяя в правой части
, obtenemos la desigualdad estricta

Dado que el lado izquierdo de la desigualdad debe tomar valores enteros, la condición necesaria para su integridad solo se puede escribir de la siguiente forma:

La desigualdad se convierte en una ecuación introduciendo una variable adicional no negativa y se incluye en la tabla simplex óptima.

Resolvemos el problema utilizando el método dual simplex. Si el nuevo plan óptimo para el problema extendido es un número entero, entonces el problema está resuelto. Si la solución no es un número entero, entonces es necesario repetir el algoritmo del método Gomori hasta obtener una solución entera.

Ejemplo. Utilizando el método Gomori, encuentre una solución a un problema de programación entera consistente en determinar el valor máximo de una función
dado que

Solución. Nivelación de desigualdades mediante variables auxiliares incógnita 3 , incógnita 4, obtenemos el problema de programación lineal en forma canónica:

Resolvemos el problema de programación lineal mediante el método simplex, utilizando una transición paso a paso de una base a otra. El progreso de la resolución del problema y la solución óptima resultante se presentan en las tablas.

	CON B			CON 2 =11
∆ j =Z j -CON j

	CON B			CON 2 =11
∆ j =Z j -CON j

En el plan óptimo encontrado, el valor de la variable incógnita 2 es igual a un número fraccionario. Encontramos su parte fraccionaria y las partes fraccionarias de todos los elementos de la recta que contiene la variable incógnita 2, a saber:

Ahora componemos la desigualdad de Gomori para los valores encontrados de las partes fraccionarias:

.

incógnita 5, movemos el término libre de la ecuación hacia el lado derecho y obtenemos una nueva restricción:

.

Agregamos una fila que contiene una nueva restricción y una columna que contiene una nueva variable a la tabla simplex y continuamos resolviendo el problema usando el método simplex dual, ya que el pseudoplan ahora está escrito en la tabla.

∆ j =z j –CON j

	CON B			CON 2 =11
∆ j =z j –CON j

La solución óptima resultante al problema extendido contiene un valor no entero de la variable incógnita 1, entonces encontramos para esta línea las partes fraccionarias de todos los números no enteros, a saber:

y la nueva desigualdad de Gomory tiene la forma:

Igualamos la desigualdad de Gomori usando una nueva variable auxiliar incógnita 6, movemos el término libre de la ecuación hacia el lado derecho y obtenemos una nueva restricción:
.

Lo agregamos al problema a resolver, lo alineamos usando una variable auxiliar y resolvemos el problema extendido

	CON B			CON 2 =11
∆ j =z j –CON j

	CON B			CON 2 =11
∆ j =z j –CON j

Así, se ha encontrado la solución óptima al problema de programación entera: z máximo=11 en
.

Notas :

Si, durante el proceso de solución, aparece una ecuación con un componente no entero en la tabla simplex y coeficientes enteros en la línea correspondiente del sistema de restricciones
, entonces este problema no tiene solución entera.

Sea el plan óptimo obtenido por el método simplex para el problema (5.1)-(5.3) el siguiente: y obtenido sobre la base
Entonces la última tabla simplex tiene la siguiente forma:

Tabla 5.1

Tabla simplex de base reducida para un problema de programación entera

Supongamos que
fraccionario; entonces algunos
también fraccionario (de lo contrario el problema no tiene solución entera). Denotemos por
Y
partes enteras de números Y , es decir. enteros más grandes que no excedan los números Y . Entonces los valores de las partes fraccionarias. Y números Y se definen como las diferencias:

Dónde Y

Por ejemplo,

.

Ya que por condición
son números enteros no negativos, entonces la diferencia también es un número entero no negativo.

Transformar esta desigualdad en una ecuación restando de su lado izquierdo la variable adicional entera no negativa
multiplicamos la ecuación por –1, la sumamos a la última tabla simplex y, usando el método simplex (preferiblemente dual), encontramos un nuevo plan. Si no es un número entero, creamos una nueva restricción adicional utilizando la última tabla simplex.

Si en el plan óptimo del problema (5.1)-(5.3) hay varios fraccionarios
entonces la restricción adicional es formax . Esto acelera el proceso de obtención de la solución entera óptima.

Consideremos el significado geométrico de introducir una restricción adicional (ver Fig. 5.2). dejar en el punto A poliedro solución q función z alcanza el valor máximo z(A)=max, pero las coordenadas del punto A– fraccionario. Luego las restricciones introducidas sobre la integridad de I y II. de la región q cortar el área con punto de esquina
, cuyas coordenadas son enteras y en las que la función lineal alcanza su valor máximo.

Fig.5.2. Significado geométrico de la restricción de Gomori

Consideremos el método Gomori usando el siguiente problema como ejemplo.

Ejemplo 5.1. Encuentra el valor máximo de una función.

bajo condiciones

Da una interpretación geométrica de la solución del problema.

Solución. Para determinar el plan óptimo para el problema (5.5)-(5.8), primero encontramos el plan óptimo para el problema (5.5)-(5.7):

Tabla 5.2

base
plan
– subóptimo,
.

Tabla 5.3

Tabla simplex reducida a base

,
– base subóptima
,
.

Tabla 5.4

Tabla simplex reducida a base

plan optimo
, base
. Este plan óptimo no es el plan óptimo para el problema (5.5)-(5.8), ya que dos componentes Y tener un valor no entero. Además, las partes fraccionarias de estos números.
son iguales entre sí. Por lo tanto, se crea una restricción adicional para una de estas variables. Creemos, por ejemplo, una restricción para la variable (la mayoría de las veces toman la primera línea). De la última tabla simplex tenemos:

.

Así, al sistema de restricciones del problema (5.5)-(5.7) le sumamos la desigualdad

Ahora encontramos el valor máximo de la función (5.5) cuando se cumplen las condiciones (5.6), (5.7) y (5.9). En la condición (5.9) introducimos una variable adicional:

Tabla 5.5

Ingresar una variable adicional en una tabla simplex

elijamos .
base.

Tabla 5.6

Reducir una tabla simplex a una base

Base
.
.

Anotemos el plan óptimo para el problema original:
Con este plan, el valor de la función objetivo es igual a
.

Interpretación geométrica de la solución del problema.

Fig.5.3. Interpretación geométrica de la solución al problema.

La región de soluciones factibles del problema (5.5)-(5.7) es un polígono OABCD(Figura 5.3). La figura muestra que la función objetivo toma su valor máximo en el punto
aquellos.
es el plan óptimo. Dado que este plan no es el plan óptimo para el problema (5.5)-(5.8) (números Y – fraccional), luego se introduce una restricción adicional

Excluyendo de esta desigualdad Y Sustituyendo en cambio los valores correspondientes de las ecuaciones del sistema de restricciones (5.6), obtenemos
.

.

Esta desigualdad corresponde al semiplano delimitado por la recta
polígono de recorte OABCD triángulo CEF.

Como puede verse en la figura, la región de soluciones factibles del problema resultante es un polígono OABEFD. en el punto mi(9;4) de este polígono, la función objetivo de este problema toma el valor máximo. Dado que las coordenadas del punto mi– números enteros e incógnitas
Y tomar valores enteros al sustituir los valores en las ecuaciones (5.6)
Y
Eso
es el plan óptimo para el problema (5.5)-(5.8). Esto también se desprende de la tabla del método simplex.

Una nota sobre el uso del método Gomori: si la base inicial del problema incluía vectores artificiales, entonces al elaborar una restricción adicional, se deben omitir las variables artificiales.

Preguntas de autoevaluación

Áreas de aplicación de la programación entera.

Planteamiento del problema de programación entera.

Un método gráfico para resolver un problema de programación entera.

Algoritmo del método Gomori.

La regla para elaborar una restricción adicional (sección Gomori).

El significado geométrico de introducir la sección Gomori.

El método se basa en el método simplex, que se utiliza para encontrar la solución óptima sin tener en cuenta condiciones enteras. Si el plan resultante contiene al menos un componente fraccionario, se impone una restricción adicional y los cálculos continúan nuevamente utilizando el método simplex.

El proceso continúa hasta que todos los componentes del plan sean números enteros o se demuestre que el problema no tiene una solución entera.

Sea X* = (x1, x2,…, xm,…, xn) el plan óptimo encontrado mediante el método simplex, donde la base son los vectores A1, A2,…, Am. Sea xi un número fraccionario (el número de la columna B en la i-ésima fila). Entonces es posible que en la i-ésima línea:

1. todos los xij son números enteros, esto significa que el problema no tiene solución entera

2. algunos xij son fraccionarios

Sean [xi] y [xij] partes enteras de los números xi y хij, y (xi) y (хij) partes fraccionarias.

Denotemos qi = (хi) y qij = (хij) y componamos las diferencias.

(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0

Transformemos la desigualdad en una ecuación multiplicándola por (-1) y agregando una nueva variable Xn+1 y agregando una nueva fila a la tabla simplex (y por lo tanto una columna). Además, resolvemos utilizando el método simplex dual; si el plan encontrado no es un número entero, repetimos el proceso de agregar una nueva variable, fila y columna a la tabla simplex.

Si el plan óptimo tiene varios componentes no enteros, entonces creamos una restricción adicional para el qi máximo.

También puede encontrar la información que le interesa en el buscador científico Otvety.Online. Utilice el formulario de búsqueda:

Más sobre el tema 47 Método Gomori: ideas principales y breve descripción del algoritmo. El sentido económico de introducir una restricción adicional:

1. 25.Métodos de gestión económica, su finalidad prevista. Tipos y contenido principal de métodos de influencia económica. Breve descripción y características de la aplicación de métodos económicos.