hogar › Ajustes › Transición a la forma canónica de la trama en línea. Reducir el problema general del LP a forma canónica. Características generales y principales etapas del método simplex.

Transición a la forma canónica de la trama en línea. Reducir el problema general del LP a forma canónica. Características generales y principales etapas del método simplex.

tareas programación lineal

2.1. Definición y formas de grabación.

En el caso en que todas las restricciones son ecuaciones y todas las variables satisfacen la condición de no negatividad, el problema de programación lineal se llama canónico. Puede presentarse en forma de notación de coordenadas, vector o matriz.

a) el problema canónico de LP en forma de coordenadas tiene la forma:

,
.

Este problema se puede escribir usando el signo de suma:

,
,
.

b) el problema canónico de LP en forma vectorial tiene la forma: ,

Dónde
;
;

,
;;
.

c) el problema canónico de LP en forma matricial tiene la forma:

,
,

Dónde
,,.

2.2. Reducción del problema lineal general.

programación en forma canónica

Al compilar modelos matemáticos de problemas económicos, las restricciones se forman principalmente en sistemas de desigualdades. Por tanto, es necesario poder pasar de ellos a sistemas de ecuaciones. Por ejemplo, considere la desigualdad lineal

y agregar a su lado izquierdo un cierto valor
tal que la desigualdad se convierte en igualdad.

Variable no negativa
llamada variable adicional. El siguiente teorema proporciona la base para la posibilidad de tal transformación.

Teorema 2.2.1. Cada decisión
la desigualdad (2.2.1) corresponde a una solución única de la ecuación (2.2.2) y la desigualdad
, y, a la inversa, a cada solución de la ecuación (2.2.2)c
corresponde a la solución
desigualdades (2.2.1).

Prueba. Dejar
solución de la desigualdad (2.2.1). Entonces. tomemos un numero
. Está claro que
. Sustituyendo en la ecuación (2.2.2), obtenemos

La primera parte del teorema ha sido demostrada.

Sea ahora un vector satisface la ecuación (2.2.2) con
, es decir, descartar el valor no negativo en el lado izquierdo de la última igualdad
, recibimos, etc.

Por lo tanto, el teorema probado en realidad establece la posibilidad de reducir cualquier problema de PL a forma canónica. Para ello, basta con introducir en cada restricción que tenga la forma de desigualdad su propia variable adicional no negativa. Además, en desigualdades de la forma (1.2.1) estas variables aparecerán con el signo “+”, y en desigualdades de la forma (1.2.2) – con el signo “–”. Se introducen variables adicionales función objetivo con coeficientes cero y por tanto no afecta su valor.

Comentario. En el futuro presentaremos el método simplex para el problema canónico de LP al estudiar la función objetivo para un mínimo. En aquellos problemas donde necesitas encontrar el máximo.
, basta considerar la función
, Encuéntrala valor mínimo, y luego, cambiando el signo al contrario, determine el requerido valor máximo
.

3. Método gráfico para la resolución de problemas.

programación lineal

3.1. Conceptos generales, ejemplos.

En los casos en los que sólo hay dos variables en el problema LP, puedes utilizar método gráfico. Sea necesario encontrar el valor máximo (mínimo) de la función.
bajo restricciones

(3.1.1)

Este método se basa en la posibilidad de representar gráficamente la región de soluciones factibles a un problema, es decir satisfacer el sistema (3.1.1) y encontrar la solución óptima entre ellos. La región de soluciones factibles del problema se construye como la intersección (parte común) de las regiones de solución de cada una de las restricciones dadas (3.1.1). Cada uno de ellos define un semiplano con límite.
,
. Para determinar cuál de los dos semiplanos es el dominio de solución, basta con sustituir en la desigualdad las coordenadas de cualquier punto que no se encuentre en la recta: si se cumple, entonces el dominio de solución es el semiplano que contiene este punto, si no se satisface la desigualdad, entonces el dominio de la solución es un semiplano que no contiene el punto dado.

La intersección de estos semiplanos forma un área determinada llamada polígono solución, que es un conjunto convexo. (Supongamos que el sistema de restricciones es consistente y el polígono de sus soluciones es limitado). Para encontrar la óptima entre las soluciones factibles, se utilizan líneas de nivel y líneas rectas de referencia.

línea de nivel se llama línea recta en la que la función objetivo toma un valor constante. La ecuación de la línea de nivel tiene la forma

, Dónde
. Todas las líneas de nivel son paralelas entre sí. su normalidad
.

Linea de referencia Se llama línea de nivel que tiene al menos un punto común con la región de soluciones factibles, en relación con la cual esta región se ubica en uno de los semiplanos (Fig. 1).

Valores
aumento en la dirección del vector
. Por lo tanto, es necesario mover la línea de nivel.
en la dirección de este vector paralelo a sí mismo a la línea de referencia l 1 en la tarea máxima y en la dirección opuesta - en la tarea mínima (hasta la línea de referencia l 2).

Demos la solución al ejemplo 1.1. Recuerde que necesitamos encontrar el máximo de la función.
bajo restricciones

Solución. Construimos una región de soluciones factibles. Numeramos las restricciones del problema. En un sistema de coordenadas cartesiano rectangular (Fig.2), construimos una línea recta

, correspondiente a la restricción (1). Encontramos cuál de los semiplanos en los que esta recta divide todo el plano coordenado es el dominio de las soluciones a la desigualdad (1).

Para hacer esto, basta con sustituir en la desigualdad las coordenadas de cualquier punto que no se encuentre en la recta. ya que es recto no pasa por el origen, sustituye
a la primera limitación. Obtenemos una desigualdad estricta.
. Por lo tanto, el punto
se encuentra en el semiplano de soluciones. De manera similar, construimos una línea recta

y el dominio de solución de la restricción (2). Encontramos la parte común de los semiplanos de soluciones, teniendo en cuenta las restricciones (3). Resaltamos la región resultante de soluciones factibles en color oscuro en la Fig. 2.

Construyendo una línea de nivel
y vector
, que indica la dirección de aumento de la función y perpendicular a la recta

. línea de nivel
moverse paralelo a sí mismo en la dirección
a la línea de referencia. Encontramos que la función objetivo alcanza su máximo en el punto
punto de intersección de líneas Y . Resolver un sistema de ecuaciones de estas rectas.
, obtenemos las coordenadas del punto
. Por lo tanto, un
,
solucion optima.

Ejemplo 3.1. Encuentra el mínimo de una función.
bajo un sistema de restricciones

Solución. Construimos la región de soluciones factibles (ver Fig. 3), vector
y una de las líneas de nivel
. Mueva la línea de nivel en la dirección opuesta.
, ya que se está resolviendo el problema de encontrar el mínimo de una función. La línea de referencia en este caso pasa por el punto A (Fig.3), cuyas coordenadas se encontrarán a partir de la solución del sistema.

Entonces,
. Calculemos.

Comentario. De hecho, depende del tipo de dominio de soluciones factibles y de la función objetivo.
Un problema de PL puede tener una única solución, un número infinito de soluciones o ninguna solución.

Ejemplo 3.2. Encuentra el mínimo de una función.
bajo restricciones

Solución. Construyendo la región de soluciones factibles, la normal de las líneas de nivel.
y una de las líneas de nivel , que tiene puntos comunes con esta zona. Moviendo la línea de nivel en dirección opuesta a la normal , ya que se está resolviendo el problema de encontrar el mínimo de una función. Normal de líneas de nivel.
y la normal de la línea límite , en la dirección en la que se mueven las líneas de nivel, son paralelas, ya que sus coordenadas son proporcionales
. Por tanto, la línea de referencia coincide con la línea límite. región de soluciones factibles y pasa por dos puntos de esquina de esta región Y (Figura 4).

El problema tiene un número infinito de soluciones óptimas, que son puntos del segmento.
. Estos puntos
,
encontramos resolviendo los correspondientes sistemas de ecuaciones:

;
;

,
;
,
;

;
.

Calculemos.

Respuesta:
en
,
.

Ejemplo 3.3. Resolver un problema de programación lineal.

Solución. Construimos la región de soluciones factibles, la normal.
y una de las líneas de nivel. En este problema es necesario encontrar el máximo de la función objetivo, por lo que la línea de nivel moverse en la dirección de la normalidad. Debido a que en esta dirección la gama de soluciones factibles no está limitada, la línea de nivel llega al infinito (Fig. 5).

El problema no tiene solución debido a que la función objetivo es ilimitada.

Respuesta:
.

Página 1

Forma canónica El problema se caracteriza por las siguientes tres características: 1) sistema homogéneo restricciones en forma de sistema de ecuaciones; 2) condiciones homogéneas de no negatividad que se aplican a todas las variables involucradas en el problema, y 3) maximización, función lineal. En este problema, se violan estas tres características.

La forma canónica del problema se caracteriza por las siguientes tres características: 1) un sistema homogéneo de restricciones en forma de sistema de ecuaciones; 2) condiciones homogéneas de no negatividad que se aplican a todas las variables involucradas en el problema, y 3) maximización de una función lineal. En este problema, se violan estas tres características.

La forma canónica del problema de programación lineal es conveniente porque el vértice inicial es fácil de encontrar. área válida.

Consideremos la forma canónica del problema de programación lineal y el método de eliminación de Jordan-Gauss.

La forma canónica de un problema de programación lineal suele resultar conveniente.

Al transformar un sistema de restricciones a la forma canónica de un problema de programación lineal, las desigualdades (12) y (13) deben reemplazarse por igualdades. Para ello, se introducen variables adicionales no negativas.

Demuestre que las matrices reales que conmutan por pares se reducen simultáneamente a la forma canónica del problema 1128 mediante una transformación de similitud utilizando una matriz ortogonal.

Esencialmente (4) - (5) puede considerarse como la forma canónica del problema de programación no lineal, ya que los métodos descritos en el Cap. Por lo general, en los problemas de programación no lineal no es necesario que las variables sean enteras.

Tipos de restricciones y métodos para su transformación.

La forma canónica del problema se caracteriza por la homogeneidad del sistema de restricciones en forma de sistema de ecuaciones; maximizar la función objetivo; la condición de no negatividad de todas las variables involucradas en el problema.

Ninguno características adicionales la forma canónica de los problemas no aporta nada al esquema computacional bajo consideración.

Consideremos primero la segunda forma canónica del problema mínimo.

El algoritmo simplex-mete se puede dividir en dos etapas. En la primera etapa, se encuentra una solución básica eliminando variables. Si se encuentra, entonces tenemos la forma canónica del problema para pasar a la segunda etapa. El segundo paso es comprobar si existe un óptimo acotado. Si existe, se determinan las soluciones básicas admisibles y de entre ellas se selecciona la óptima.

Si el problema se resuelve en forma canónica, sólo se utiliza parte de las operaciones introducidas en el segundo párrafo. Así, para el problema del mínimo canónico, solo se realiza el caso del párrafo 3.4.1, y solo se necesitan las operaciones de reordenamiento cíclico de columnas, pasando la columna a través de la zona del borde vertical, corrigiendo violaciones estructurales y parte de la operación de truncamiento. Simétricamente, al resolver el problema del máximo canónico, solo se realiza el caso del párrafo 3.4.2, y se realizan las operaciones de reordenamiento cíclico de cuerdas, paso de una cuerda a través de la zona del borde horizontal, corrección de violaciones estructurales y otra parte de la operación de truncamiento. necesario. Por lo demás, la forma canónica del problema no añade ninguna especificidad adicional.

El primer párrafo de la introducción mostró cómo un problema general de programación lineal se puede reducir a una de las formas canónicas. Para problemas canónicos, la descripción del método de mejora secuencial se simplifica formalmente, ya que no es necesario considerar dos opciones para violar las condiciones de optimización y dos opciones para alcanzar el siguiente vértice. Sin embargo, esto aumenta el tamaño de la matriz base A [. /, J ], que determina principalmente la complejidad. Sin embargo, en muchos casos resulta preferible la aplicación del método a las formas canónicas del problema, y en esta sección nos detendremos en las variantes del método obtenidas para lineales particulares. problemas de programación.

Páginas: 1

Un método analítico para resolver un problema de programación lineal es método simplex. Para aplicarlo, los problemas de PL presentados de diferentes maneras deben reducirse a forma canónica. El problema de programación lineal, escrito en la forma (2.1.1)-(2.1.3), es una forma ampliada de escribir el problema de programación lineal general (GLP).

Llamaremos al siguiente problema un problema de programación lineal canónica (CLPT):

bajo restricciones que tienen la forma de igualdades,

Si para un problema de la forma (2.3.1)-(2.3.4) se cumple la condición t = norte, entonces su solución se reduce a resolver el sistema de ecuaciones

(2.3.2) . En este caso, el problema no tendrá solución si la condición
(2.3.3) no se cumple o el sistema de ecuaciones no tiene solución.

condición t

1. para ir del problema de maximización función objetivo (2.3.1) a problema de minimización suficiente tomar todos los coeficientes Cj función objetiva con signos inversos y resolver al máximo el problema resultante. Luego de encontrar el máximo, se debe tomar el valor de la función objetivo con el signo opuesto. La solución óptima seguirá siendo la misma.
2. para ir desde menor o igual a la restricción de igualdad es necesario con un signo más:

3. Para ir de una restricción “mayor o igual a” a la igualdad es necesario introducir una variable adicional no negativa con signo menos:

En este caso, cada desigualdad introduce su propia (n +/)-ésima variable adicional.

4. Todo las igualdades que tienen términos libres negativos se dividen en-1, para que se cumpla la condición (2.3.4).
5. Si en alguna variable Xj no se impone la condición de no negatividad, Eso realizar un cambio de variables Xj=x".- X" x"j> 0, x"> 0. En el problema transformado todas las variables no son negativas.

Hay una afirmación de que cualquier ZLP se puede reducir a una forma canónica.

Ejemplo 2.3.1. Transformemos el problema dado en el Ejemplo 2.2.2 a forma canónica. La función objetivo y el sistema de restricciones se ven así:

Introduzcamos una variable adicional jc 3 > 0 con un signo más en la primera desigualdad y en la segunda x4> 0 con signo menos y en el tercero x5> 0 también con un signo más. Como resultado, obtenemos un sistema de restricciones de problemas en forma canónica:

Dadas estas restricciones, necesitas encontrar el valor máximo de la función:

Consideremos sentido económico variables adicionales en el problema canónico del uso óptimo de los recursos.

Ejemplo 2.3.2. Problema de utilización óptima de recursos (problema de alfombra)[17J.

La fábrica tiene a su disposición Una cierta cantidad de recursos de tres tipos: mano de obra (80 días-hombre), materias primas (480 kg) y equipos (130 horas-máquina). La fábrica puede producir cuatro tipos de alfombras. En el cuadro se proporciona información sobre el número de unidades de cada recurso necesarias para producir una alfombra de cada tipo y sobre los ingresos que recibe la empresa por una unidad de cada tipo de producto. 2.3.1.

Se requiere encontrar un plan de producción en el que su costo total sea máximo.

Modelo económico y matemático del problema. variables: x x, x 2, x 3, x 4 - Número de alfombras de cada tipo. Función objetiva - es el costo total de producción que debe maximizarse:

Límites de recursos:

Llevemos el problema a su forma canónica introduciendo variables adicionales x 5, x6 Y x7:

A continuación se mostrará que el plan de producción óptimo es el vector X* =(0; 30; 10; 0), el valor de la función objetivo es 150, es decir para maximizar coste total Para producir productos es necesario producir 30 alfombras del segundo tipo y 10 alfombras del tercer tipo. sustituyamos valores optimos vector X en restricciones de KZLP:

Obtenemos que los recursos “mano de obra” y “equipo” se utilizan en su totalidad, el recurso “materias primas” está disponible en abundancia:

En este caso x en muestra que quedan 200 kg de materia prima.

Entonces las variables principales x v x 2, x 3, x l significa el número de alfombras de cada tipo y variables adicionales x 5, x 6 sus 7 - volumen de recursos subutilizados.

Respuesta. Plan de producción óptimo X* = (0; 30;

10; 0).

Plan, o solución aceptable , KZLP se llama vector X=(jcp X 2 ,..., xn), cumpliendo las condiciones (2.3.2)-(2.3.4).

Si todos los componentes de la solución básica del sistema de restricciones CLLP no son negativos, entonces dicha solución se llama solución de referencia o plano de referencia. El número de componentes positivos del plan de referencia no puede exceder T.

El plan de referencia se llama no degenerado, si contiene t componentes positivos, de lo contrario se llama degenerar.

plan optimo o solucion optima Un plan se denomina plan que entrega el valor más grande (más pequeño) de la función lineal (2.3.1).

El conjunto de todos los planes del PPP (si existen) es poliedro convexo. Cada punto de esquina (extremo) del poliedro solución corresponde a plan de referencia (soluciones básicas no negativas del sistema de ecuaciones KZLP). Cada plan de referencia está determinado por el sistema. t vectores linealmente independientes contenidos en un sistema dado de PAG vectores D, D,..., Una pág. Si hay un plan óptimo, entonces hay un punto angular del poliedro de decisión en el que la función lineal alcanza su valor mayor (menor).

Encontrar plan optimo Basta examinar únicamente los planos de referencia. El límite superior en el número de planes de referencia contenidos en un problema está determinado por el número de combinaciones. S t p (ver párrafo 1.4).

Ejemplo 2.3.3. Obtenga una solución al problema sobre uso optimo recursos limitados(resuelva ZL P):

Solución. Llevemos el problema a su forma canónica introduciendo variables adicionales. x 3, x4 y x5:

Encontremos todos los planes de apoyo del sistema de restricciones de este KZLP (l? - 5; /77 - 3); su número no supera los 10:

Utilizando el método de Jordan-Gauss (ver párrafo 1.4), escribimos todas las soluciones básicas del sistema de ecuaciones (Tabla 2.3.2).

Número base no vayas soluciones	Base	Plan

entre diez soluciones basicas cinco soportes:

Los planos de referencia indicados en la Fig. 2.3.1 corresponden respectivamente a los siguientes puntos de las esquinas y los valores del CF en ellos:

Arroz. 2.3.1.

Según la teoría La solución óptima de LP está contenida entre los planes de referencia.

Así, el valor máximo igual a 2300 lo alcanza la función objetivo en el punto EN en el plan de referencia X5 = (70; 80; 0; 60; 0).

Respuesta. Plan de tareas óptimo: x( = 70, x2 = 80, valor de la función objetivo f(xvx2) = 2300.

Tareas MP

Papanicolaou general llamado <,=,>=)bi (i=1,n) (2) sujeto a xj>

Simétrico < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Canónico mezclado.

mín f(x) = -máx(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Interpretación geométrica función objetivo y restricciones del PLP. Formulación geométrica de la ZLP.

Sea el problema f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

soy1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

El plano del problema (x1,x2) es un punto del plano. Cada desigualdad tiene 2 representaciones. es un semiplano. Un semiplano es un conjunto convexo. Convexo Se llama conjunto en el que los puntos del segmento que conecta (x1 y x2) pertenecientes a este conjunto también pertenecen al conjunto. C-ma 2 representa la intersección de semiplanos. Al cruzar puedes conseguir:

1) área cerrada poligonal convexa.

2) área poligonal abierta convexa

3) punto único

4) conjunto vacío

5) rayo y segmento

Interpretación geométrica de la función objetivo: La función 1 es una familia de rectas paralelas, que se denominan líneas de nivel (líneas de valor constante de la función objetivo). Las derivadas parciales de la función con respecto a x1 y x2 muestran la tasa de aumento de la función objetivo a lo largo de las coordenadas de los ejes. Vector degradado muestra la dirección del aumento más rápido en la función objetivo Para el problema 1-3, el vector gradiente = (c1; c2) sale del punto (0,0) y se dirige al punto con coordenadas (c1; c2). El vector de gradiente es perpendicular a las líneas de nivel. La intersección de semiplanos se suele llamar área de soluciones admisibles (AÑADIR).

El teorema principal de LP. Diagrama esquemático solución del ZLP, que se sigue de este teorema.

Si el ZLP tiene solución, entonces la función objetivo alcanza un valor extremo en al menos uno de los puntos extremos del poliedro plan. Si la función objetivo alcanza un valor extremo en más de un punto extremo, entonces alcanza un mismo valor, que es una combinación lineal convexa de ellos, en cualquier punto. En decisión del PP Es conveniente utilizar una entrada de tabla manualmente.

PA		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
F	abucheo	bo1 bo2 bon-m

Algoritmo del método simplex.

1. llevar el modelo del problema a su forma canónica;

2. encontrar el plan de referencia inicial;

3. Escribe el problema en forma sencilla. mesa;

5. pasar a un nuevo plan de referencia, a un nuevo síntoma. mesa. Para pasar a un nuevo plan de referencia, basta con sustituir una variable básica por una gratuita. La variable incluida en la base y la columna de resolución correspondiente están determinadas por el elemento negativo absoluto más grande de la fila f. La variable que excluye de la base y la línea de resolución correspondiente están determinadas por la relación simplex más pequeña, es decir la relación de los elementos de la columna de unidades con el elemento correspondiente de la columna de resolución. La relación simplex es una cantidad no negativa. En la intersección de la fila de resolución y la columna de resolución hay un elemento de resolución, con respecto al cual la transformación simplex se realiza de la siguiente manera. regla: 1. los elementos de la cadena permitida se dividen en el elemento permitido; 2. los elementos de la columna de resolución se dividen en el elemento de resolución y cambian su signo al contrario; 3. Los elementos restantes de la tabla se reorganizan según la regla del rectángulo:

bij Bis bkj=(bkj*bis-bij*bks)/bi

El segundo teorema de la dualidad.

si uno de los problemas duales tiene un plan óptimo, entonces el otro también tiene solución, es decir Tiene un plan óptico. En este caso, los valores extremos de las funciones objetivo coinciden (j=de 1 a n) Σcjxj*= (i=de 1 a m)Σbiyi* si está en el original. problema, la función objetivo es ilimitada en el conjunto de planes, entonces en problema dual el sistema de restricciones es inconsistente.

Teorema sobre el rango de la matriz TK.

El rango de la matriz A del problema de transporte es uno menos que el número de ecuaciones: r(A)=m+n-1.

39. Algoritmo para la construcción del plan de referencia inicial de la ZLP.

Para encontrar el plano de referencia inicial, podemos sugerir lo siguiente algoritmo:

1. Escriba el problema en forma de tabla de Jordan de modo que todos los elementos de la columna de términos libres sean no negativos, es decir, se cumplió la desigualdad aio>=0 (i=1,m). Aquellas ecuaciones en las que los términos libres son negativos se multiplican primero por -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1…..amn
f=		-c1…. -cn

Transforma la tabla usando los pasos de eliminación de Jordan, reemplazando los ceros en la columna de la izquierda con la x correspondiente. Al mismo tiempo, a cada paso. se puede seleccionar permisivo cualquier columna que contenga al menos un elemento positivo. La fila de resolución está determinada por la menor de las proporciones de los términos libres con respecto a los elementos positivos correspondientes de la columna de resolución. Si se encuentra una cadena 0 durante el proceso de excepción, todos los elementos que son ceros, y el término libre es diferente de cero, entonces el sistema no tiene soluciones para las ecuaciones restrictivas. Si nos encontramos con una cadena 0 en la que, además del término libre, no hay otros elementos positivos no, entonces el sistema de ecuaciones restrictivas no tiene soluciones no negativas Si el sistema de ecuaciones restrictivas articulación, luego de un cierto número de pasos todos los ceros en la columna de la izquierda serán reemplazados por x y así se obtendrá una cierta base y, en consecuencia, el plan de referencia correspondiente.

40. Algoritmo para construir el plan de referencia óptimo de la ZLP.

Se examina la optimización del plan de apoyo inicial de Ho.

Si no hay elementos negativos en la fila f (sin contar el término libre), el plan es óptimo. Si tampoco hay elementos cero en la fila f, entonces solo hay un plan óptimo; si entre los elementos hay al menos un cero, entonces hay un número infinito de planes óptimos. Si hay al menos un elemento negativo en la fila f y no hay elementos positivos en la columna correspondiente, entonces la función objetivo no está limitada en la región factible. El problema no tiene solución. Si hay al menos un elemento negativo en la fila f, y en cada columna con dicho elemento hay al menos un elemento positivo, entonces puede pasar a un nuevo plan de referencia que esté más cerca del óptimo. Para hacer esto, la columna con un elemento negativo en la fila f se toma como permisivo; Determinan la cadena de resolución a partir de la relación simplex mínima y realizan el paso de eliminación de Jordan. El plan de referencia resultante se examina nuevamente para determinar su optimidad. Esto se repite hasta que se encuentra el plan de referencia óptimo o se establece la irresolublebilidad del problema.

Algoritmo del método Gomori.

1. Utilizando el método simplex, se encuentra el plan óptimo para el problema. Si todos los componentes de un plan óptimo son números enteros, entonces es óptimo. De lo contrario, vaya al paso 2

2. Entre los componentes no enteros, debes elegir el que tiene fracción es el más grande y, usando la fila correspondiente de la tabla simplex, formule el límite correcto usando la fórmula

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Transformar la desigualdad formulada en una igualdad cero equivalente e incluirla en tabla simplex con un plan óptimo no entero

4. El problema extendido resultante se resuelve mediante el método simplex. Si el plan resultante no es un número entero, continúe con el paso 2.

Si durante el proceso de solución aparece una línea 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, el problema original tampoco tiene solución en números enteros. El método de Gomori tiene una aplicación limitada. Con su ayuda es recomendable solucionar pequeños problemas, porque... el número de interacciones puede ser muy grande.

Varias formas de notación de ZLP (general, canónica, simétrica)

Tareas MP: determinación del plan óptimo, determinación del volumen óptimo de producción, determinación de la combinación óptima de cultivos, formación del paquete óptimo de activos, maximización de las ganancias bancarias, etc.

Generalmente se llama ZLP. problema de maximización (minimización) función lineal f=Σcj*xj-max(min) (1) bajo restricciones lineales ∑aij *xj(=<,=,>=)bi (i=1,n) (2) siempre que xj>=0(j=1,n1), xj-arbitrario (j=n1+1,n)(3) donde cj,aij, números bi-constantes .

Simétrico La forma de escribir el ZLP se denomina problema de maximizar la función (1) bajo restricciones lineales en desigualdades con signo.< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >o = y variables no negativas. Canónico el formulario para registrar el PAP se llama tarea función máxima(1) bajo restricciones lineales de igualdades y variables no negativas. Cualquier otra forma se llama mezclado.

mín f(x) = -máx(-f(x))

La transformación de una desigualdad en una ecuación y viceversa se realiza sobre la base del Lema: para toda solución x1...xn de la desigualdad a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) y viceversa. Cada solución x1…xn,xn+1 de la ecuación 6 y la desigualdad 7 corresponde a una solución x1…xn de la desigualdad 5.

Para pasar del formulario de simulación posterior al formulario canónico posterior, debe ingresar equilibrar (igualar) las variables. Esto se basa en el teorema de la desigualdad: cualquier desigualdad se puede representar como una ecuación o una desigualdad simple.

Escribir la función objetivo y el sistema de restricciones en varias tareas la programación lineal no es lo mismo: en algunos problemas es necesario encontrar el mínimo de la función objetivo, y en otros, el máximo; en algunos casos las variables buscadas dependen de un índice y en otros de dos; en algunos problemas las restricciones se especifican en forma de un sistema de desigualdades lineales, y en otros, en forma de un sistema de ecuaciones lineales. En la práctica, también es posible tener problemas en los que algunas de las restricciones estén en forma de desigualdades lineales y otras en forma de ecuaciones lineales. Además, no todos los problemas pueden requerir que las variables no sean negativas.

Tener en cuenta tal variedad de problemas de programación lineal requiere el desarrollo de métodos especiales para resolver clases individuales de ellos. Centraremos nuestra atención en estudiar. propiedades generales y métodos de programación lineal escritos en la llamada forma canónica.

Si en un problema de programación lineal el sistema de restricciones iniciales toma la forma de ecuaciones como

y necesitas encontrar el máximo de la función objetivo lineal

entonces se considera que el problema de programación lineal está escrito en forma canónica.

Cualquier problema de programación lineal se puede reducir fácilmente a una forma canónica. EN caso general Para hacer esto, basta con poder, en primer lugar, reducir el problema de minimizar la función objetivo al problema de maximizarla, en segundo lugar, pasar de restricciones de desigualdad a restricciones de igualdad y, en tercer lugar, cambiar aquellas variables que no están sujetas a la condición de no negatividad.

En el caso de que necesites encontrar el mínimo de una función. , podemos proceder a encontrar el máximo de la función. , ya que la siguiente afirmación es cierta:
.

Desigualdad de restricciones problema original, que se parece a “ ", se puede convertir en una restricción de ecuación agregando una variable adicional no negativa a su lado izquierdo y una restricción de desigualdad de la forma " ” – restando una variable adicional no negativa de su lado izquierdo.

Tenga en cuenta que el número de variables no negativas adicionales introducidas siempre es igual al número de desigualdades en el sistema de restricciones original.

Las variables adicionales introducidas tienen un significado económico muy específico. Por lo tanto, si las restricciones del problema de programación lineal original reflejan los costos y la disponibilidad de los recursos de producción, entonces el valor numérico de la variable adicional muestra la cantidad del recurso no utilizado correspondiente.

Tenga en cuenta también que si alguna variable no obedece la condición de no negatividad, entonces debe ser reemplazada por dos variables no negativas Y , habiendo aceptado
.

Ejemplo. Escriba el siguiente problema de optimización lineal en forma canónica: encuentre el mínimo de la función
bajo restricciones

Solución

En este problema, es necesario encontrar el mínimo de la función objetivo y el sistema de restricciones incluye cuatro desigualdades. Para escribirlo en forma canónica, es necesario pasar de restricciones de desigualdad a restricciones de ecuación y también transformar la función objetivo.

Dado que el número de desigualdades incluidas en el sistema de restricciones del problema es igual a cuatro, esta transición debe realizarse con la introducción de cuatro variables adicionales no negativas. Además, en la segunda y cuarta desigualdad hay un signo “ ", por lo que agregamos variables adicionales a su lado izquierdo. En la primera y tercera desigualdad hay un signo “ “, lo que significa que restamos variables adicionales de su lado izquierdo.