Encuentre el valor máximo de la función objetivo usando el método de gomory. Método de Gomori para resolver problemas de programación entera. Ejemplos de resolución de problemas económicos. Ideas generales para los métodos de poda
La esencia de los métodos de corte es que el problema se resuelve primero sin la condición de número entero. Si el plan resultante es entero, el problema está resuelto. De lo contrario, se agrega una nueva restricción con las siguientes propiedades a las restricciones de la tarea:
Debe ser lineal;
Debería cortar el plan no entero óptimo encontrado;
No debe truncar ningún plan entero.
Una restricción adicional que tiene estas propiedades se llama corte propio.
Geométricamente, agregar cada restricción lineal corresponde a dibujar una línea recta (hiperplano) que corta una parte del polígono solución (poliedro) junto con el punto óptimo con coordenadas no enteras, pero no afecta ninguno de los puntos enteros de este poliedro. . Como resultado, el nuevo poliedro de decisión contiene todos los puntos enteros contenidos en el poliedro de decisión original y, en consecuencia, la solución óptima obtenida con este poliedro será entera (Fig. 8.1).
principales variables *1, *2, nuevas variables Xm+1, Xm+2, ..., Xm+1, soluciones
xm a través de neox- x„ óptimo
| (8.5) |
componente no entero. En este caso, se puede demostrar que la desigualdad
(P, ) - (a," m+\)xm+1 ■ -~(am)Xn ^ 0, (* )
formado de acuerdo con la ecuación /-ésima del sistema (8.5), tiene todas las propiedades del corte correcto.
Para resolver el problema de programación lineal entera (8.1)-(8.4) por el método de Gomory, se utiliza el siguiente algoritmo:
1. Utilice el método símplex para resolver el problema (8.1)-(8.3) sin tener en cuenta la condición de integralidad. Si todos los componentes del plan óptimo son enteros, entonces también es óptimo para el problema de programación entera (8.1)-(8.4). Si la primera tarea (8.1) es
(8.3) es irresoluble (es decir, no tiene un óptimo finito o sus condiciones son contradictorias), entonces el segundo problema (8.1)-(8.4) también es irresoluble.
2. Si hay componentes no enteros entre los componentes de la solución óptima, elija el componente con la parte integral más grande y, usando la ecuación correspondiente del sistema (8.5), forme el corte correcto (8.6).
3. La desigualdad (8.6) al introducir una variable entera no negativa adicional se transforma en una ecuación equivalente
(P() - |a/ m+1)*m+1- ■-(a|"l)xn + xn+1 > (®*^)
e incluirlo en el sistema de restricciones (8.2).
4. Resuelva el problema extendido resultante usando el método símplex. Si el plan óptimo encontrado es entero,
entonces se resuelve el problema de programación entera (8.1)-(8.4). De lo contrario, regrese al paso 2 del algoritmo.
Si el problema se puede resolver en números enteros, luego de un número finito de pasos (iteraciones) se encontrará el plan entero óptimo.
Si en el proceso de resolución aparece una ecuación (expresando la variable principal en términos de no básicos) con un término libre no entero y otros coeficientes enteros, entonces la ecuación correspondiente no tiene solución en números enteros. En este caso, este problema tampoco tiene una solución óptima entera.
^ 8.1. Para comprar equipos para clasificar granos, el agricultor asigna 34 den. unidades El equipo debe colocarse en un área que no exceda los 60 metros cuadrados. M. Un agricultor puede pedir dos tipos de equipos: menos potentes máquinas de tipo A por valor de 3 den. unidades que requieren un área de producción de 3 m2. m (incluidas las pasadas) y proporcionando una productividad por turno de 2 toneladas de grano, y máquinas tipo B más potentes que cuestan 4 den. Unidades que ocupan un área de 5 m2. m y proporcionando una productividad por turno de 3 toneladas de grano de alta calidad.
Se requiere elaborar un plan óptimo para la compra de equipos que asegure la máxima productividad general, siempre que el agricultor no pueda comprar más de 8 máquinas del tipo B.
Solución. Denotemos por x\, x2 el número de máquinas de tipo A y B, respectivamente, y por Z - la productividad total. Entonces el modelo matemático del problema tomará la forma:
En la fig. 8.2 OKM: el área de soluciones admisibles del problema (8.1") - (8.3"), delimitada por líneas rectas (1), (2), (3) y ejes de coordenadas; />(2/3; 8) - punto de solución óptima, pero no entera, del problema (8.1") - (8.3"); (4) es una línea recta que corta esta solución no entera; 0№M - área de soluciones factibles del problema extendido (8.1') - (8.3'), (8.61); M2; 7) - el punto de la solución entera óptima.
Doy un paso. Principales variables x3, x4, *5; variables menores X\, X2.
| x3 | = 60 - | ¡Zx! - 5x2, |
| x4 | = 34 - | Zx) - 4x2, |
| x5 | = 8 | - *2> |
| Z = 2x) | + Zx2. |
La primera solución básica X\ = (0; 0; 60; 34; 8) es admisible. El valor correspondiente de la función lineal = 0.
Traducimos a las principales variables la variable XI, que se incluye en la expresión de una función lineal con el mayor coeficiente positivo. Encontramos el valor máximo posible de la variable хі, que “permite” aceptar el sistema de restricciones, a partir de la condición del mínimo de las proporciones correspondientes:
Хг = 1ШП | t; t; T | = 8,
aquellos. la tercera ecuación se está resolviendo (resaltada). Con *2 = 8 en esta ecuación, X5 = 0, y la variable X5 pasa a las no básicas.
II paso. Principales variables x2, x3, x*; variables menores Xx X5.
| { |
| (8.6) |
Introduciendo una variable entera adicional x6 > 0, obtenemos una ecuación equivalente a la desigualdad (8.6")
~1*5+Xb\u003d°"^8"7^
La ecuación (8.7") debe incluirse en el sistema de restricciones (8.5") del problema canónico original, luego de lo cual se debe repetir el proceso de resolución del problema por el método símplex en relación con el problema extendido. En este caso, para reducir el número de pasos (iteraciones), se recomienda introducir una ecuación adicional (8.7") en el sistema obtenido en el último paso de resolución del problema (sin la condición de integralidad).
IV paso. Variables básicas X), *2, xs> *b‘> variables no básicas *1, *2-
X1 \u003d s - 3 * 4 +
x3 = 18 + x4 +___ x5,
x6 - + ^x4 + z "x5-
La solución básica X4 = (y; 8; 18; 0; 0; -y) no es válida. (Tenga en cuenta que después de la inclusión de una ecuación adicional correspondiente al corte correcto en el sistema de restricciones, siempre se obtendrá una solución básica no válida).
Para obtener una solución básica aceptable, es necesario convertir en la variable principal que entra en la ecuación con coeficiente positivo, en la que el término negativo es más libre, es decir *1 o x$ (en esta etapa no consideramos la función lineal). Traducimos a los principales, por ejemplo, la variable X5.
Paso V. Principales variables X\, X2, X3, X5; variables no básicas R], X£
Obtenemos después de las transformaciones:
LG| \u003d 2 - x4 + 2x6,
*2 = 7 + 2x* ~ 2x("
x3 = 19 + -x4 + -x6,
*5 = 1 - 2x* + 2x6’
2 = 25-|x4--|x6.
^5 =(2; 7; 19; 0; 1;0);^ = 25.
Dado que no existen variables principales con coeficientes positivos en la expresión de una función lineal, X5 es la solución óptima.
Entonces, 2max = 25 para la solución entera óptima X* - X$ =(2; 7; 19; 0; 1; 0), es decir la productividad máxima de 25 toneladas de grano de alta calidad por turno se puede obtener comprando 2 máquinas de tipo A y 7 máquinas de tipo B\, mientras que el área desocupada del local será de 19 metros cuadrados. m, el saldo de fondos de la asignación es 0, en la reserva para la compra: 1 automóvil de tipo B (el sexto componente no tiene un significado significativo).
Comentario. Para una interpretación geométrica sobre el plano Ox\Xr (ver Fig. 8.2) del corte (8.6"), es necesario expresar las variables x4 y x$ incluidas en él a través de las variables XI y x2. Obtenemos (ver el 2ª y 3ª ecuaciones del sistema de restricciones (8.5")):
y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 o x, + 2x2 £ 16.
(ver corte de la línea recta (4) en la Fig. 8.2)>
^ 8.2. Hay una cantidad bastante grande de troncos de 3 m de largo, los troncos deben cortarse en dos tipos de espacios en blanco: 1,2 m de largo y 0,9 m de largo, y se deben obtener al menos 50 piezas de cada tipo. y 81 uds. respectivamente. Cada tronco se puede aserrar en los espacios en blanco indicados de varias maneras: 1) en 2 espacios en blanco de 1,2 m; 2) para 1 formato de 1,2 m y 2 formatos de 0,9 m; 3) para 3 espacios en blanco de 0,9 m cada uno Encuentre el número de troncos,
serrado por cada método, de modo que se pueda obtener una pieza de cualquier tipo del menor número de troncos.
Solución. Denote por x\, xi, xm, la cantidad de troncos aserrados, respectivamente, 1, "2 y 3 formas. De ellos puede obtener 2xi + *2 espacios en blanco de 1.2 m y 2n\ + Zx2 espacios en blanco de 0.9 m Denote el número total de registros por I. Entonces el modelo matemático del problema tomará la forma:
I 2x, + x2 - x4 = 50, sin exceder el dado.
Bajo parte fraccional
algún número A se entiende como el número no negativo más pequeño 
tal que la diferencia entre ella y A Hay [ a] - la 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 en las variables i- ésima línea del sistema de restricciones 
(línea de producción).
Denotar 
Y 
partes enteras de numeros 
Y 
. valores fraccionarios 
Y 
(
) se definen de la siguiente manera
Para hacer esto, se escribe una ecuación usando la fila generadora de la tabla símplex, suponiendo que la primera metro las variables son básicas para un plan óptimo dado
o 
Transferimos todas las partes enteras de los coeficientes en un sentido, dejando todas las partes fraccionarias en el otro:
Porque 
<1,
то заменяя в правой части 
, obtenemos una desigualdad estricta
Dado que el lado izquierdo de la desigualdad debe tomar valores enteros, la condición necesaria para su valor entero se puede escribir solo de la siguiente forma:
La desigualdad se convierte en una ecuación mediante la introducción de una variable no negativa adicional y se incluye en la tabla símplex óptima.
Resolvemos el problema usando el método simplex dual. Si el nuevo plan óptimo para el problema extendido es entero, entonces el problema está resuelto. Si la solución no es entera, entonces se debe repetir el algoritmo del método de Gomori hasta obtener una solución entera.
Ejemplo.
Utilizando el método de Gomory, encontrar una solución al problema de programación entera, que consiste en determinar el valor máximo de la función 
dado que
Solución. Nivelación de desigualdades con variables auxiliares X 3 , X 4, obtenemos un problema de programación lineal en forma canónica:
Resolvemos el problema de programación lineal por el método símplex, usando una transición paso a paso de una base a otra. El curso de 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 X 2 es igual a un número fraccionario. Encuentra su parte fraccionaria y las partes fraccionarias de todos los elementos de la cadena que contiene la variable X 2, a saber:
Ahora componemos la desigualdad de Gomory para los valores encontrados de las partes fraccionarias:
.
X 5, trasladamos el término libre de la ecuación al 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 dual simplex, ya que ahora la tabla contiene un pseudoplan.
|
| |||||||
|
|
|
| |||||
|
|
|
| |||||
|
∆ j =Z j –CON j |
|
|
| ||||
|
CON B |
CON 2 =11 | ||||||
|
|
|
|
|||||
|
|
|
||||||
|
∆ j =Z j –CON j |
|
|
|||||
La solución óptima obtenida del problema extendido contiene un valor no entero de la variable X 1, por lo que 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: 
Igualando la desigualdad de Gomory con la ayuda de una nueva variable auxiliar X 6, trasladamos el término libre de la ecuación al lado derecho y obtenemos una nueva restricción: 
.
Lo añadimos al problema a resolver, lo alineamos con 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 del problema de programación entera: Z máximo=11 a las 
.
Observaciones :
Si en el proceso de resolución de una ecuación con componente no entero aparece en la tabla simplex 
y coeficientes enteros en la línea correspondiente del sistema de restricciones 
, entonces este problema no tiene solución entera.
Interpretación económica y geométrica del problema de la programación entera. Un problema extremo cuyas variables toman solo valores enteros se llama problema de programación entera.
En el modelo matemático del problema de los números enteros programación tanto la función objetivo como las funciones del sistema de restricciones pueden ser lineales, no lineales y mixtas. Nos restringimos al caso en que la función objetivo y el sistema de restricciones del problema son lineales.
Ejemplo 20.
En el taller de la empresa, se decidió instalar equipos adicionales, para lo cual se asignó espacio. Una empresa puede gastar 10 mil rublos en la compra de equipos, mientras que puede comprar dos tipos de equipos. Un conjunto de equipos de tipo I cuesta 1000 rublos y de tipo II - 3000 rublos. La compra de un conjunto de equipos de tipo I le permite aumentar la producción por turno en 2 unidades, y un conjunto de equipos de tipo II, en 4 unidades. Sabiendo que la instalación de un conjunto de equipos de tipo I requiere 2 m 2 de área y equipos de tipo II - 1 m 2 de área para determinar dicho conjunto de equipos adicionales, lo que permite maximizar la producción
Solución. Hagamos un modelo matemático del problema. Suponga que la empresa comprará x 1 conjuntos de equipos de tipo I y conjuntos de equipos de tipo II. Entonces las variables x 1 y deben satisfacer las siguientes desigualdades:
Si la empresa adquiere la cantidad especificada de equipo, el aumento total de la producción será
Según su contenido económico, las variables x 1 y sólo pueden tomar valores enteros no negativos, es decir
x 1 , son números enteros. (73)
Así, llegamos al siguiente problema matemático: encontrar el valor máximo de la función lineal (71) bajo las condiciones (70), (72) y (73). Dado que las incógnitas solo pueden tomar valores enteros, el problema (70) - (73) es un problema de programación de enteros. Dado que el número de incógnitas en el problema es dos, la solución a este problema se puede encontrar utilizando su interpretación geométrica. Para ello, en primer lugar, construimos un polígono de soluciones al problema, que consiste en determinar el valor máximo de la función lineal (71) en las condiciones (70) y (72) (Fig. 11). Coordenadas de todos los puntos del polígono solución construido OAEMU satisfacer el sistema de desigualdades lineales (70) y la condición no negatividad variables (72). Al mismo tiempo, la condición (73), es decir, la condición enteros Las variables satisfacen las coordenadas de solo 12 puntos marcados en la Fig. 11. Para encontrar un punto cuyas coordenadas determinen la solución del problema original, reemplazamos el polígono OABC polígono OKEMNF, que contiene todos los puntos válidos con coordenadas enteras y tal que las coordenadas de cada uno de los vértices son números enteros. Por lo tanto, si encontramos el punto máximo de la función (71) en el polígono OKEMNF, entonces las coordenadas de este punto determinarán el plan óptimo del problema.
Para hacer esto, también construimos una línea recta que pasa por el polígono solución OKEMNF(el número 12 se toma arbitrariamente). Movemos la línea construida en la dirección del vector hasta que pasa por su último punto común con el polígono dado. Las coordenadas de este punto determinan el plan óptimo y el valor de la función objetivo en él es el máximo.
En este caso, el punto deseado es mi(1; 3), en el que la función objetivo toma el valor máximo С Por lo tanto, las coordenadas del punto mi determinar el plan óptimo del problema (70) - (73). De acuerdo con este plan, la empresa debe comprar un juego de equipos de tipo 1 y tres juegos de equipos de tipo II. Esto proporcionará a la empresa con sus restricciones existentes en el espacio de producción y efectivo, el aumento máximo en la producción, igual a 14 unidades. en turno
Ejemplo 21.
se puede usar para trabajar PAG mecanismos. Actuación i-th mecanismo al realizar j – el trabajo es igual a . Suponiendo que cada máquina solo se puede usar en un trabajo y que cada trabajo solo puede ser realizado por una máquina, determine la asignación de máquinas a los trabajos que asegure la máxima productividad. Construya un modelo matemático del problema.
Solución. Introduzcamos una variable x ij , cuyo valor sea igual a 1, si durante la ejecución i-ésimo trabajo usado j – th mecanismo, y es 0 en caso contrario. Entonces las condiciones para usar cada mecanismo en un solo trabajo están expresadas por las igualdades
(74)
y las condiciones para la realización del trabajo por un solo mecanismo: igualdades
(75)
Así, el problema es determinar tales valores de las incógnitas 
satisfaciendo los sistemas de ecuaciones (74) y (75) y la condición (76), bajo los cuales el valor máximo de la función
El problema formulado es un problema de programación entera.
Determinación del plan óptimo para el problema de programación entera. Considere problemas de programación de enteros en los que tanto la función objetivo como las funciones en el sistema de restricciones son lineales. En este sentido, formulamos el problema principal de la programación lineal, en el que las variables solo pueden tomar valores enteros. En términos generales, este problema se puede escribir de la siguiente manera: encuentre el máximo de la función
bajo condiciones
(79)
– entero (81)
Si se encuentra una solución al problema (78) - (81) por el método símplex, entonces puede resultar ser un número entero o no (un ejemplo en el que la solución siempre es un número entero es el problema de transporte). En el caso general, para determinar el plan óptimo para el problema (78) - (81), se requieren métodos especiales. Actualmente, existen varios métodos de este tipo, de los cuales el más famoso es metodo de gomory, que se basa en el método simplex descrito anteriormente.
método Gomory. Encontrar una solución al problema de programación entera por el método de Gomory comienza con determinar el plan óptimo del problema (78) - (80) por el método símplex sin tener en cuenta enteros variables Después de encontrar este plan, se visualizan sus componentes. Si no hay números fraccionarios entre los componentes, entonces el plan encontrado es el plan óptimo para el problema de programación entera (78) - (81). Si, en el plan óptimo del problema (78) - (80), la variable toma un valor fraccionario, entonces la desigualdad se suma al sistema de ecuaciones (79)
(82)
y encuentre una solución al problema (78) – (80), (82).
En la desigualdad (82) y – cantidades iniciales transformadas y cuyos valores se toman de la última tabla símplex, y – partes fraccionarias de números (la parte fraccionaria de algún número a se entiende como el número no negativo más pequeño b tal que la diferencia entre A Y b es un número entero). Si en el plan óptimo del problema (78) - (80) los valores fraccionarios toman varias variables, entonces se determina la desigualdad adicional (82) mayor fraccionario parte.
Si en el plan del problema encontrado (78) - (80), (82) las variables toman valores fraccionarios, entonces se agrega una restricción adicional nuevamente y se repite el proceso de cálculo. Realizando un número finito de iteraciones, o bien se obtiene el plan óptimo del problema de programación entera (78) - (81), o bien se establece su insolubilidad.
Si el requisito enteros(81) se aplica solo a algunas variables, entonces tales problemas se llaman parcialmente entero. Su solución también se encuentra mediante una solución secuencial de problemas, cada uno de los cuales se obtiene a partir del anterior introduciendo una restricción adicional. En este caso, esta restricción tiene la forma
donde se determinan a partir de las siguientes relaciones:
1) para , que puede tomar valores no enteros,
(84)
2) para , que solo puede tomar valores enteros,
(85)
De lo anterior se deduce que el proceso de determinación del plan óptimo para un problema de programación entera por el método de Gomory incluye lo siguiente escenarios principales:
1. Usando el método simplex, encuentre una solución al problema (78) - (80) sin tener en cuenta el requisito enteros variables
2. Componga una restricción adicional para una variable que, en el plan óptimo del problema (78) - (80), tiene fraccionario maximo valor, y en el plan óptimo del problema (78) - (81) debe ser entero.
3. Usando el dual, encuentre una solución al problema obtenido del problema (78) - (80) como resultado de agregar una restricción adicional.
4. Si es necesario, invente una restricción adicional y continúe el proceso iterativo hasta que se obtenga un plan óptimo para el problema (78) - (81) o se establezca su irresolubilidad.
Ejemplo 22.
Usando el método de Gomori para encontrar el valor máximo de la función
dado que
(87)
– entero (89)
Solución. Para determinar el plan óptimo para el problema (86) - (89), primero encontramos el plan óptimo para el problema (86) - (88) (Tabla 22).
Tabla 22
|
cb |
R 0 |
|||||||
Como puede verse en la Tabla. 22, encontró el plan óptimo 
problema (86) - (88) no es un plan óptimo para el problema (86) - (89), ya que los dos componentes y tienen valores no enteros. En este caso, las partes fraccionarias de estos números son iguales entre sí. Por lo tanto, se hace una restricción adicional para una de estas variables. Compongamos, por ejemplo, tal restricción para la variable De la última tabla simplex (Tabla 22) tenemos
Así, al sistema de restricciones del problema (86) – (89) le sumamos la desigualdad
o
Tabla 23
|
cb |
R 0 |
||||||||
Ahora encontramos el valor máximo de la función (86) bajo las condiciones (87), (88) y (90) (Tabla 23).
La tabla 23 muestra que el problema original de programación entera tiene un plan óptimo
PAG En este plan, el valor de la función objetivo es igual a . Demos una interpretación geométrica de la solución del problema. El dominio de soluciones factibles al problema (86) - (88) es un polígono OABCD(Figura 12). De la fig. 12 muestra que la función objetivo toma el valor máximo en el punto CON(19/2; 7/2), tomo e. Qué X =(19/2; 7/2; 0; 0; 34) es el plan óptimo. Esto es directamente evidente en la Tabla 22. Dado que X= (19/2; 7/2; 0; 0; 34) no es un plan óptimo para el problema (86) - (89) (los números y son fraccionarios), entonces se introduce una restricción adicional. Excluyéndolo y sustituyendo en su lugar los valores correspondientes de las ecuaciones del sistema de restricciones (87), obtenemos el corte del polígono OABCD triángulo EFC.
Como puede verse en la fig. 12, el área de soluciones factibles del problema obtenido 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. Como las coordenadas del punto mi son números enteros e incógnitas, y toman valores enteros cuando los valores y se sustituyen en la ecuación (87), entonces 
es el plan óptimo para el problema (86) – (89). Esto se deduce de la tabla 23.
Ejemplo 23.
Usando el método de Gomory, encuentre una solución al problema, que consiste en determinar el valor máximo de la función
bajo condiciones
- entero. (94)
Dar una interpretación geométrica de la solución del problema.
Solución. Reescribimos el problema formulado de la siguiente manera: encuentre el valor máximo de la función
bajo condiciones
(96)
- entero. (98)
El problema (95) - (98) es parcialmente entero, ya que las variables y pueden tomar valores no enteros.
Encontramos por el método simplex la solución de las tareas (95) - (97) (tabla 24).
Tabla 24
|
cb |
R 0 |
|||||||
|
cb |
R 0 |
|||||||
|
–1/3 no es un plan de tareas (95) – (98), ya que la variable |
Encuentre la solución del problema de PL: . Solución L i será un número entero si
aquellos. 
. (β i ) - parte fraccionaria de la solución óptima no entera x i , (d i ) - parte fraccionaria de variables no básicas. Esta relación determina (ver figura). Asignación de servicios. La calculadora en línea se utiliza para resolver problemas de programación lineal entera utilizando el método de corte. Durante la solución se utilizan tablas símplex. (ver ejemplo).
Instrucción. Seleccione el número de variables y el número de filas (número de restricciones), haga clic en Siguiente. La solución resultante se guarda en un archivo de Word (ver un ejemplo de la solución por el método Gomori). Además, se crea una plantilla de solución en formato Excel.
En este caso, las restricciones del tipo x yo ≥ 0 no tener en cuentaTipos de algoritmo de Gomory
- El primer algoritmo de Gomory para resolver problemas completamente enteros.
- Segundo algoritmo de Gomory para problemas de programación lineal parcialmente entera.
algoritmo de gomori para problemas completamente enteros incluye los siguientes pasos:
- El problema de la programación lineal se resuelve sin tener en cuenta los números enteros.
- Entre los números fraccionarios, se selecciona el elemento con la mayor parte fraccionaria y se hace una restricción adicional.
- La desigualdad se convierte en una ecuación introduciendo una variable no negativa adicional.
- El problema resultante se resuelve por el método simplex dual.
Ejemplo. La Asociación de Investigación y Producción "Strela" se dedica a la fabricación de componentes para empresas del complejo militar-industrial. En la fabricación de productos de tipo A y tipo B, se utilizan acero y metales no ferrosos. El proceso tecnológico también incluye el procesamiento de productos en tornos y fresadoras. De acuerdo con los estándares tecnológicos, la producción de un producto de tipo A y un producto de tipo B requiere una cierta cantidad de materias primas y una cierta cantidad de horas de máquina para el procesamiento en máquinas en el taller. Los datos tecnológicos del proceso de producción se dan en la tabla.
Durante el mes del taller, NPO Strela tiene recursos limitados en cuanto a materias primas y tiempo dedicado a los talleres de producción (ver tabla). El beneficio de la venta de un producto de tipo A es de 100 rublos, y de una unidad de producto de tipo B - 250 rublos.
| Materia prima | Trabajo en el taller, hora-máquina | Beneficio de las ventas, frotar. | |||
| Metales no ferrosos | Acero | Trabajos de torneado | trabajo de fresado | ||
| Producto A | 10 | 25 | 41 | 90 | 100 |
| Producto B | 30 | 25 | 90 | 50 | 250 |
| Recursos | 4500 | 6250 | 14100 | 18000 | |
Encuentre el plan de producción óptimo para NPO "Strela" (la cantidad de productos de tipo A y tipo B - números enteros), que brinda la mayor ganancia.
Solución.
Modelo económico-matemático del problema.
x 1 - plan de producción para productos tipo A, x 2 - plan de producción para productos tipo B,
x 1, x 2 son números enteros.
Límites de recursos
10x1 + 30x2 ≤ 4500
25x1 + 25x2 ≤ 6250
41x1 + 90x2 ≤ 14100
90x1 + 50x2 ≤ 18000
función objetiva
100x1 + 250x2 → máx.
Resolvamos el problema directo de programación lineal por el método símplex. Como resultado, obtenemos el siguiente plan óptimo:
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x2 | 1450 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 |
| x4 | 17500 / 11 | 0 | 0 | 245 / 66 | 1 | -50 / 33 | 0 |
| x1 | 600 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 |
| x6 | 6500 | 0 | 0 | 55 / 3 | 0 | -20 / 3 | 1 |
| F(X3) | 422500 / 11 | 0 | 0 | 125 / 33 | 0 | 50 / 33 | 0 |
x 1 \u003d 54 6 / 11, x 2 \u003d 131 9 / 11
F(X) = 250 131 9/11 + 100 54 6/11 = 38409 1/11
El plan óptimo resultante no es un número entero, por lo que usamos metodo de gomory. La parte fraccionaria más grande está en la segunda ecuación para la variable x 4 (10 / 11). Creamos una restricción adicional:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 \u003d b 2 - \u003d 1590 10 / 11 - 1590 \u003d 10 / 11
q 2 1 = un 2 1 - = 0 - 0 = 0
q 2 2 = un 2 2 - = 0 - 0 = 0
q 2 3 \u003d a 2 3 - \u003d 3 47 / 66 - 3 \u003d 47 / 66
q 2 4 = un 2 4 - = 1 - 1 = 0
q 2 5 \u003d a 2 5 - \u003d -1 17 / 33 + 2 \u003d 16 / 33
q 2 6 = un 2 6 - = 0 - 0 = 0
10/11 - 47/66x3 - 16/33x5 ≤ 0
10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0
Como se usa el método simplex dual para encontrar el mínimo de la función objetivo, hacemos la transformación F(x) = -F(X).
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x2 | 1450 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 | 0 |
| x4 | 17500 / 11 | 0 | 0 | 245 / 66 | 1 | -50 / 33 | 0 | 0 |
| x1 | 600 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 | 0 |
| x6 | 6500 | 0 | 0 | 55 / 3 | 0 | -20 / 3 | 1 | 0 |
| x7 | -10 / 11 | 0 | 0 | -47 / 66 | 0 | -16 / 33 | 0 | 1 |
| F(X0) | -422500 / 11 | 0 | 0 | -125 / 33 | 0 | -50 / 33 | 0 | 0 |
Primera iteración de Gomory. 1. Comprobación del criterio de optimalidad. El plan en la tabla símplex es un pseudoplan, por lo que definimos la fila y la columna principales.
2. Definición de una nueva variable libre. Entre los valores negativos de las variables básicas, elegimos el módulo más grande. La quinta línea será la inicial, y la variable x 7 debe eliminarse de la base.
3. Definición de una nueva variable básica. El valor mínimo de θ corresponde a la quinta columna, es decir la variable x 5 debe ingresarse en la base. En la intersección de la fila y la columna principales, hay un elemento de resolución (RE) igual a (-16 / 33).
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x2 | 131 9 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 | 0 |
| x4 | 1590 10 / 11 | 0 | 0 | 3 47 / 66 | 1 | -1 17 / 33 | 0 | 0 |
| x1 | 54 6 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 | 0 |
| x6 | 6500 | 0 | 0 | 18 1 / 3 | 0 | -6 2 / 3 | 1 | 0 |
| x7 | -10 / 11 | 0 | 0 | -47 / 66 | 0 | -16 / 33 | 0 | 1 |
| F(X0) | -38409 1 / 11 | 0 | 0 | -3 26 / 33 | 0 | -1 17 / 33 | 0 | 0 |
| θ | - | - | -3 26 / 33: (-47 / 66) = 5 15 / 47 | - | -1 17 / 33: (-16 / 33) = 3 1 / 8 | - | - |
4. Recalculamos la tabla símplex usando el método de Jordan-Gauss.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x2 | 1055 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 |
| x4 | 6375 / 4 | 0 | 0 | 95 / 16 | 1 | 0 | 0 | -25 / 8 |
| x1 | 435 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 |
| x6 | 13025 / 2 | 0 | 0 | 225 / 8 | 0 | 0 | 1 | -55 / 4 |
| x5 | 15 / 8 | 0 | 0 | 47 / 32 | 0 | 1 | 0 | -33 / 16 |
| F(X0) | -153625 / 4 | 0 | 0 | -25 / 16 | 0 | 0 | 0 | -25 / 8 |
En el plan óptimo resultante, hay números fraccionarios. De acuerdo con la primera ecuación con la variable x 2 , que recibió un valor no entero en el plan óptimo con la mayor parte fraccionaria 7 / 8 , creamos una restricción adicional:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 \u003d b 1 - \u003d 131 7/8 - 131 \u003d 7/8
q 1 3 \u003d a 1 3 - \u003d 27 / 160 - 0 \u003d 27 / 160
q 1 7 \u003d a 1 7 - \u003d -1 / 16 + 1 \u003d 15 / 16
Una restricción adicional se parece a:
7/8 - 27/160x3 - 15/16x7 ≤ 0
Transformamos la desigualdad resultante en una ecuación:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
cuyos coeficientes se introducirán como una línea adicional en la tabla símplex óptima.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 |
| x2 | 1055 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 | 0 |
| x4 | 6375 / 4 | 0 | 0 | 95 / 16 | 1 | 0 | 0 | -25 / 8 | 0 |
| x1 | 435 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 | 0 |
| x6 | 13025 / 2 | 0 | 0 | 225 / 8 | 0 | 0 | 1 | -55 / 4 | 0 |
| x5 | 15 / 8 | 0 | 0 | 47 / 32 | 0 | 1 | 0 | -33 / 16 | 0 |
| x 8 | -7 / 8 | 0 | 0 | -27 / 160 | 0 | 0 | 0 | -15 / 16 | 1 |
| F(X0) | -153625 / 4 | 0 | 0 | -25 / 16 | 0 | 0 | 0 | -25 / 8 | 0 |
Segunda iteración de Gomroy. 1. Comprobación del criterio de optimalidad. El plan en la tabla símplex es un pseudoplan, por lo que definimos la fila y la columna principales.
2. Definición de una nueva variable libre. Entre los valores negativos de las variables básicas, el de mayor módulo es la variable x 8. Debe sacarse de la base.
3. El valor mínimo de θ corresponde a la séptima columna, es decir la variable x 7 debe ingresarse en la base.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 |
| x2 | 131 7 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 | 0 |
| x4 | 1593 3 / 4 | 0 | 0 | 5 15 / 16 | 1 | 0 | 0 | -3 1 / 8 | 0 |
| x1 | 54 3 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 | 0 |
| x6 | 6512 1 / 2 | 0 | 0 | 28 1 / 8 | 0 | 0 | 1 | -13 3 / 4 | 0 |
| x5 | 1 7 / 8 | 0 | 0 | 1 15 / 32 | 0 | 1 | 0 | -2 1 / 16 | 0 |
| x 8 | -7 / 8 | 0 | 0 | -27 / 160 | 0 | 0 | 0 | -15 / 16 | 1 |
| F(X0) | -38406 1 / 4 | 0 | 0 | -1 9 / 16 | 0 | 0 | 0 | -3 1 / 8 | 0 |
| θ | - | - | -1 9 / 16: (-27 / 160) = 9 7 / 27 | - | - | - | -3 1 / 8: (-15 / 16) = 3 1 / 3 | - |
4. Transformando los cortes de New Gomory.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 |
| x2 | 1979 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 |
| x4 | 4790 / 3 | 0 | 0 | 13 / 2 | 1 | 0 | 0 | 0 | -10 / 3 |
| x1 | 271 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 |
| x6 | 19576 / 3 | 0 | 0 | 153 / 5 | 0 | 0 | 1 | 0 | -44 / 3 |
| x5 | 19 / 5 | 0 | 0 | 46 / 25 | 0 | 1 | 0 | 0 | -11 / 5 |
| x7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -16 / 15 |
| F(X0) | -115210 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -10 / 3 |
En el plan óptimo, hay números fraccionarios. La mayor parte fraccionaria de la variable x 2 (14/15). Hacemos una restricción adicional: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 \u003d b 1 - \u003d 131 14 / 15 - 131 \u003d 14 / 15
q 1 1 = un 1 1 - = 0 - 0 = 0
q 1 2 = un 1 2 - = 1 - 1 = 0
q 1 3 \u003d a 1 3 - \u003d 9 / 50 - 0 \u003d 9 / 50
q 1 4 = un 1 4 - = 0 - 0 = 0
q 1 5 = un 1 5 - = 0 - 0 = 0
q 1 6 = un 1 6 - = 0 - 0 = 0
q 1 7 = un 1 7 - = 0 - 0 = 0
q 1 8 \u003d a 1 8 - \u003d -1 / 15 + 1 \u003d 14 / 15
Una restricción adicional se parece a:
14/15 - 9/50x3 - 14/15x8 ≤ 0
Transformamos la desigualdad resultante en una ecuación:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
cuyos coeficientes se introducirán como una línea adicional en la tabla símplex óptima.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 | x9 |
| x2 | 1979 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 | 0 |
| x4 | 4790 / 3 | 0 | 0 | 13 / 2 | 1 | 0 | 0 | 0 | -10 / 3 | 0 |
| x1 | 271 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 | 0 |
| x6 | 19576 / 3 | 0 | 0 | 153 / 5 | 0 | 0 | 1 | 0 | -44 / 3 | 0 |
| x5 | 19 / 5 | 0 | 0 | 46 / 25 | 0 | 1 | 0 | 0 | -11 / 5 | 0 |
| x7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -16 / 15 | 0 |
| x9 | -14 / 15 | 0 | 0 | -9 / 50 | 0 | 0 | 0 | 0 | -14 / 15 | 1 |
| F(X0) | -115210 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -10 / 3 | 0 |
Tercera iteración por el método de Gomory. La variable x 9 se debe sacar de la base. El valor mínimo de θ corresponde a la octava columna, es decir la variable x 8 debe ingresarse en la base.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 | x9 |
| x2 | 131 14 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 | 0 |
| x4 | 1596 2 / 3 | 0 | 0 | 6 1 / 2 | 1 | 0 | 0 | 0 | -3 1 / 3 | 0 |
| x1 | 54 1 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 | 0 |
| x6 | 6525 1 / 3 | 0 | 0 | 30 3 / 5 | 0 | 0 | 1 | 0 | -14 2 / 3 | 0 |
| x5 | 3 4 / 5 | 0 | 0 | 1 21 / 25 | 0 | 1 | 0 | 0 | -2 1 / 5 | 0 |
| x7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -1 1 / 15 | 0 |
| x9 | -14 / 15 | 0 | 0 | -9 / 50 | 0 | 0 | 0 | 0 | -14 / 15 | 1 |
| F(X0) | -38403 1 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -3 1 / 3 | 0 |
| θ | - | - | -1: (-9 / 50) = 5 5 / 9 | - | - | - | - | -3 1 / 3: (-14 / 15) = 3 4 / 7 | - |
4. Realice la transformación.
| Base | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x 8 | x9 |
| x2 | 132 | 0 | 1 | 27 / 140 | 0 | 0 | 0 | 0 | 0 | -1 / 14 |
| x4 | 1600 | 0 | 0 | 50 / 7 | 1 | 0 | 0 | 0 | 0 | -25 / 7 |
| x1 | 54 | 1 | 0 | -67 / 140 | 0 | 0 | 0 | 0 | 0 | 3 / 14 |
| x6 | 6540 | 0 | 0 | 234 / 7 | 0 | 0 | 1 | 0 | 0 | -110 / 7 |
| x5 | 6 | 0 | 0 | 317 / 140 | 0 | 1 | 0 | 0 | 0 | -33 / 14 |
| x7 | 2 | 0 | 0 | 27 / 70 | 0 | 0 | 0 | 1 | 0 | -8 / 7 |
| x 8 | 1 | 0 | 0 | 27 / 140 | 0 | 0 | 0 | 0 | 1 | -15 / 14 |
| F(X0) | -38400 | 0 | 0 | -5 / 14 | 0 | 0 | 0 | 0 | 0 | -25 / 7 |
La solución resultó ser entera. El plan entero óptimo se puede escribir de la siguiente manera: x 1 \u003d 54, x 2 \u003d 132. F (X) \u003d 38400
