Hogar › Tarifas › Método de transformación simplex. Un ejemplo de resolución de un problema directo y dual mediante el método simplex. Problema de doble LP

Método de transformación simplex. Un ejemplo de resolución de un problema directo y dual mediante el método simplex. Problema de doble LP

Este método es un método de enumeración intencionada de soluciones de referencia a un problema de programación lineal. Le permite encontrar en un número finito de pasos solución óptima, o establecer que no existe una solución óptima.

El contenido principal del método simplex es el siguiente:

Indique un método para encontrar el óptimo. solución de referencia
Indique el método de transición de una solución de referencia a otra, en el que el valor de la función objetivo estará más cerca del óptimo, es decir indicar una forma de mejorar la solución de referencia
Establezca criterios que le permitan dejar de buscar rápidamente soluciones de soporte para la solución óptima o sacar una conclusión sobre la ausencia de una solución óptima.

Algoritmo del método simplex para la resolución de problemas de programación lineal.

Para resolver el problema método simplex necesitas hacer lo siguiente:

Lleva la tarea a forma canónica
Encontrar la solución de soporte inicial con una “base unitaria” (si no hay solución de soporte, entonces el problema no tiene solución debido a la incompatibilidad del sistema de restricciones)
Calcule estimaciones de descomposiciones vectoriales basadas en la solución de referencia y complete la tabla del método simplex
Si se cumple el criterio de unicidad de la solución óptima, entonces la solución del problema termina
Si se cumple la condición para la existencia de un conjunto de soluciones óptimas, entonces por búsqueda sencilla encontrar todas las soluciones óptimas

Un ejemplo de resolución de un problema utilizando el método simplex.

Ejemplo 26.1

Resuelva el problema usando el método simplex:

Solución:

Llevamos el problema a la forma canónica.

Para hacer esto, introducimos una variable adicional x 6 con coeficiente +1 en el lado izquierdo de la primera restricción de desigualdad. La variable x 6 se incluye en la función objetivo con un coeficiente de cero (es decir, no se incluye).

Obtenemos:

Encontramos la solución de soporte inicial. Para hacer esto, equiparamos las variables libres (no resueltas) a cero x1 = x2 = x3 = 0.

obtenemos solución de referencia X1 = (0,0,0,24,30,6) con base unitaria B1 = (A4, A5, A6).

calculamos estimaciones de descomposiciones vectoriales condiciones en base a la solución de referencia según la fórmula:

Δ k = C segundo X k - c k

C b = (c 1, c 2, ..., c m) - vector de coeficientes de la función objetivo para las variables básicas
X k = (x 1k, x 2k, ..., x mk) - vector de expansión del vector correspondiente A k según la base de la solución de referencia
C k es el coeficiente de la función objetivo para la variable x k.

Las estimaciones de los vectores incluidos en la base son siempre iguales a cero. La solución de referencia, los coeficientes de expansión y las estimaciones de las expansiones de los vectores de condición basados en la solución de referencia están escritos en tabla simplex:

En la parte superior de la tabla, para facilitar el cálculo de las estimaciones, se escriben los coeficientes de la función objetivo. En la primera columna "B" se escriben los vectores incluidos en la base de la solución de referencia. El orden en que se escriben estos vectores corresponde al número de incógnitas permitidas en las ecuaciones de restricción. En la segunda columna de la tabla "C b" los coeficientes de la función objetivo para las variables básicas están escritos en el mismo orden. En ubicación correcta Los coeficientes de la función objetivo en la columna "C b" de la estimación de los vectores unitarios incluidos en la base son siempre iguales a cero.

En la última fila de la tabla con estimaciones de Δ k en la columna "A 0" se escriben los valores de la función objetivo en la solución de referencia Z(X 1).

La solución de soporte inicial no es óptima, ya que en el problema máximo las estimaciones Δ 1 = -2, Δ 3 = -9 para los vectores A 1 y A 3 son negativas.

Según el teorema de mejora de la solución de soporte, si en el problema máximo al menos un vector tiene una estimación negativa, entonces se puede encontrar una nueva solución de soporte en la que el valor de la función objetivo será mayor.

Determinemos cuál de los dos vectores conducirá a un incremento mayor en la función objetivo.

El incremento de la función objetivo se encuentra mediante la fórmula: .

Calculamos los valores del parámetro θ 01 para la primera y tercera columnas usando la fórmula:

Obtenemos θ 01 = 6 para l = 1, θ 03 = 3 para l = 1 (Tabla 26.1).

Encontramos el incremento de la función objetivo al introducir en la base el primer vector ΔZ 1 = - 6*(- 2) = 12, y el tercer vector ΔZ 3 = - 3*(- 9) = 27.

En consecuencia, para una aproximación más rápida a la solución óptima, es necesario introducir el vector A3 en la base de la solución de referencia en lugar del primer vector de la base A6, ya que el mínimo del parámetro θ 03 se logra en la primera fila ( l = 1).

Realizamos la transformación de Jordan con el elemento X13 = 2, obtenemos la segunda solución de referencia X2 = (0,0,3,21,42,0) con la base B2 = (A3, A4, A5). (Tabla 26.2)

Esta solución no es óptima, ya que el vector A2 tiene una estimación negativa Δ2 = - 6. Para mejorar la solución, es necesario introducir el vector A2 en la base de la solución de referencia.

Determinamos el número del vector derivado de la base. Para hacer esto, calculamos el parámetro θ 02 para la segunda columna, es igual a 7 para l = 2. En consecuencia, derivamos el segundo vector base A4 de la base. Realizamos la transformación de Jordan con el elemento x 22 = 3, obtenemos la tercera solución de referencia X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabla 26.3).

Esta solución es la única óptima, ya que para todos los vectores no incluidos en la base las estimaciones son positivas.

Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

Respuesta: máx Z(X) = 201 en X = (0,7,10,0,63).

Método de programación lineal en análisis económico.

Método de programación lineal permite justificar el más óptimo decisión económica en condiciones de severas restricciones relacionadas con los recursos utilizados en la producción (activos fijos, materiales, recursos laborales). Aplicación de este método en análisis económico le permite resolver problemas relacionados principalmente con la planificación de las actividades de la organización. Este método ayuda a determinar los niveles óptimos de producción, así como las direcciones para la mayoría uso efectivo Recursos productivos de que dispone la organización.

Con este método se resuelven los llamados problemas extremos, que consiste en encontrar valores extremos, es decir, el máximo y mínimo de funciones. variables.

Este período se basa en la solución del sistema. ecuaciones lineales en los casos en que los fenómenos económicos analizados estén conectados linealmente, estrictamente dependencia funcional. El método de programación lineal se utiliza para analizar variables en presencia de ciertos factores limitantes.

Es muy común resolver el llamado problema de transporte mediante el método de programación lineal. El contenido de esta tarea es minimizar los costos incurridos en relación con la operación. vehículos bajo las restricciones existentes con respecto al número de vehículos, su capacidad de carga, la duración de su operación, si existe la necesidad de mantenimiento cantidad máxima clientes.

Además de esto, este método encuentra amplia aplicación al resolver el problema de programación. Esta tarea consiste en una distribución del tiempo de trabajo del personal de una organización determinada que sea más aceptable tanto para los miembros de este personal como para los clientes de la organización.

Esta tarea consiste en maximizar el número de clientes atendidos en condiciones de limitaciones en el número de miembros del personal disponibles, así como en el fondo de tiempo de trabajo.

Por tanto, el método de programación lineal es bastante común en el análisis de ubicación y uso. varios tipos recursos, así como en el proceso de planificación y previsión de las actividades de las organizaciones.

Aún programación matemática También se puede aplicar a aquellos fenómenos económicos cuya relación no es lineal. Para ello se pueden utilizar métodos de programación no lineales, dinámicos y convexos.

La programación no lineal se basa en la naturaleza no lineal de la función objetivo o las restricciones, o ambas. Las formas de la función objetivo y las desigualdades de restricciones en estas condiciones pueden ser diferentes.

La programación no lineal se utiliza en el análisis económico, en particular, cuando se establece la relación entre los indicadores que expresan la eficiencia de las actividades de una organización y el volumen de esta actividad, la estructura de los costos de producción, las condiciones del mercado, etc.

La programación dinámica se basa en la construcción de un árbol de decisiones. Cada nivel de este árbol sirve como escenario para determinar las consecuencias. decisión previa y eliminar opciones ineficaces para esta solución. Por lo tanto, la programación dinámica tiene una naturaleza de múltiples pasos y múltiples etapas. Este tipo de programación se utiliza en el análisis económico para encontrar opciones optimas desarrollo de la organización tanto ahora como en el futuro.

La programación convexa es un tipo de programación no lineal. Este tipo de programación expresa la naturaleza no lineal de la relación entre los resultados de las actividades de una organización y sus costos. La programación convexa (también conocida como cóncava) analiza funciones objetivo convexas y sistemas de restricciones convexas (puntos valores aceptables). La programación convexa se utiliza en el análisis de actividades económicas con el objetivo de minimizar costos, y la programación cóncava con el objetivo de maximizar los ingresos bajo las restricciones existentes sobre la acción de factores que influyen en los indicadores analizados de manera opuesta. En consecuencia, con los tipos de programación considerados, las funciones objetivo convexas se minimizan y las funciones objetivo cóncavas se maximizan.

Se utilizan hilos, botones y telas para confeccionar tres tipos de camisas. Las existencias de hilo, botones y telas, las normas de su consumo para coser una camisa se indican en la tabla. Encuentre el beneficio máximo y el plan de producción de producto óptimo que lo asegure (encontrar).

camisa 1

camisa 2

camisa 3

Reservas

hilos (m.)

botones (uds.)

640

textil (

Beneficio (r.)

solución del problema

construcción de modelos

Hasta y el número de camisetas de los tipos 1, 2 y 3 destinadas a su lanzamiento.

Entonces las restricciones de recursos se verán así:

Además, según el significado de la tarea.

Función objetivo que expresa el beneficio recibido:

Obtenemos el siguiente problema de programación lineal:

Reducir un problema de programación lineal a forma canónica

Reduzcamos el problema a su forma canónica. Introduzcamos variables adicionales. Introducimos todas las variables adicionales en la función objetivo con un coeficiente igual a cero. Agregamos variables adicionales a los lados izquierdos de las restricciones que no tienen una forma preferida y obtenemos igualdades.

Resolviendo el problema usando el método simplex.

Complete la tabla simplex:

Como solucionamos el problema al máximo: la presencia en la línea de índice números negativos al resolver el problema al máximo nos indica que no hemos obtenido la solución óptima y que es necesario pasar de la tabla de la iteración 0 a la siguiente.

Procedemos a la siguiente iteración de la siguiente manera:

la columna principal corresponde

La fila clave está determinada por la proporción mínima de miembros libres y miembros de la columna principal (relaciones simples):

En la intersección de la columna clave y la fila clave encontramos el elemento habilitante, es decir 9.

Ahora procedemos a compilar la primera iteración: en lugar de un vector unitario, introducimos el vector.

EN nueva mesa en lugar del elemento habilitante escribimos 1, todos los demás elementos de la columna clave son ceros. Los elementos de la cadena clave se dividen en el elemento enable. Todos los demás elementos de la tabla se calculan utilizando la regla del rectángulo.

La columna clave para la primera iteración corresponde a

El elemento resolutivo es el número 4/3. Derivamos el vector de la base y en su lugar introducimos el vector. Obtenemos la tabla de la segunda iteración.

La columna clave para la segunda iteración corresponde a

Encontramos la línea clave, para ello definimos:

El elemento resolutivo es el número 10/3. Derivamos el vector de la base y en su lugar introducimos el vector. Obtenemos la tabla de la tercera iteración.

№

simplex

relación

32/3

640

F j - c j

-2

-5

-4

32/3

1/9

1/3

1/9

1600/3

170/9

80/3

-10/9

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

-1/12

1/6

-1/4

10/3

-20

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

1/4

1/40

-3/4

3/10

-6

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

Todos los términos en la línea índice no son negativos, por lo que obtenemos siguiente solución Problemas de programación lineal (los escribimos de la columna de términos libres):

Es necesario coser 24 camisas del 1er tipo, 7 camisas del 2do tipo y 3 camisas del 3er tipo. En este caso, el beneficio recibido será máximo y ascenderá a 95 rublos.

Puede encontrar ayuda para resolver sus problemas sobre este tema enviando un mensaje en VKontakte, Viber o completando el formulario. Costo de la solución tarea comienza desde 7 BYN. por tarea (200 rublos rusos), pero no menos de 10 rublos bielorrusos. (300 rublos) para todo el pedido. Diseño detallado. El costo de la asistencia para el examen en línea (en este caso, se requiere un pago anticipado del 100%) es de 30 BYR. (1000 rublos rusos) por la resolución del billete.

Breve teoría

Se han propuesto muchos métodos diferentes para resolver problemas de programación lineal. Sin embargo, el método simplex resultó ser el más eficaz y universal entre ellos. Cabe señalar que a la hora de resolver algunos problemas, otros métodos pueden resultar más eficaces. Por ejemplo, para un ZLP con dos variables el método óptimo es , y para resolverlo se utiliza el método potencial. El método simplex es básico y aplicable a cualquier PAP en forma canónica.

En relación con el teorema principal de la programación lineal, naturalmente surge la idea del siguiente camino Decisiones de APP con cualquier número de variables. Encuentre de alguna manera todos los puntos extremos del poliedro de planos (no hay más que ) y compare los valores de la función objetivo en ellos. Esta solución, incluso con relativamente un pequeño número variables y restricciones es prácticamente imposible, ya que el proceso de encontrar puntos extremos es comparable en dificultad a resolver problema original Además, el número de puntos extremos del poliedro de planos puede resultar bastante grande. En relación con estas dificultades, surgió el problema de la enumeración racional de puntos extremos.

La esencia del método simplex es la siguiente. Si se conoce algún punto extremo y el valor de la función objetivo en él, entonces obviamente no se necesitan todos los puntos extremos en los que la función objetivo toma el peor valor. Por lo tanto, el deseo natural es encontrar una manera de pasar de un punto extremo dado a uno mejor adyacente a lo largo del borde, de allí a uno aún mejor (no peor), etc. Para hacer esto, necesita tener una señal de que No hay mejores puntos extremos que un punto extremo dado. esto es lo que idea general el método simplex (método de mejora secuencial del plan) más utilizado actualmente para resolver el ZLP. Entonces, en términos algebraicos, el método simplex supone:

la capacidad de encontrar un plan de referencia inicial;
presencia de un signo de optimización plan de referencia;
la capacidad de pasar a un plan de referencia que no sea el peor.

Ejemplo de solución de problema

Condición problemática

Para vender tres grupos de bienes, una empresa comercial tiene tres tipos de recursos materiales y monetarios limitados en la cantidad de , , , unidades. Al mismo tiempo, por la venta de 1 grupo de productos por mil rublos. La rotación de mercancías consume el recurso del primer tipo en número de unidades, el recurso del segundo tipo en número de unidades, el recurso del tercer tipo en número de unidades. Para la venta de 2 y 3 grupos de productos por mil rublos. La rotación de productos básicos se gasta de acuerdo con el recurso del primer tipo en la cantidad de unidades, los recursos del segundo tipo en la cantidad de unidades y los recursos del tercer tipo en la cantidad de unidades. Beneficio de la venta de tres grupos de bienes por mil rublos. El volumen de negocios es, respectivamente, mil rublos.

Determine el volumen planificado y la estructura del volumen de negocios comercial para maximizar las ganancias de la empresa comercial.
Para el problema directo de planificación del volumen de negocios, resuelto mediante el método simplex, cree un problema de programación lineal dual.
Establecer pares conjugados de variables de los problemas directo y dual.
Según pares conjugados de variables, a partir de la solución del problema directo, se obtiene una solución al problema dual, en el que se estiman los recursos gastados en la venta de bienes.

Si tu admisión a la sesión depende de la resolución de un bloque de problemas y no tienes el tiempo ni las ganas de sentarte a hacer cálculos, utiliza las capacidades del sitio web. Ordenar tareas toma solo unos minutos. Puedes leer en detalle (cómo enviar una solicitud, precios, condiciones, métodos de pago) en la página Comprar soluciones a problemas de programación lineal...

solución del problema

construcción de modelos

Denotemos la facturación del primer, segundo y tercer tipo de bienes, respectivamente.

Entonces la función objetivo que expresa el beneficio recibido:

Limitaciones de recursos materiales y monetarios:

Además, según el significado de la tarea.

Obtenemos el siguiente problema de programación lineal:

Reducción a la forma canónica de la ZLP

Reduzcamos el problema a su forma canónica. Para transformar desigualdades en igualdades, introducimos variables adicionales. Las variables se incluyen en las restricciones con un coeficiente de 1. Introducimos todas las variables adicionales en la función objetivo con un coeficiente igual a cero.

La restricción tiene una forma preferible si, si el lado derecho no es negativo lado izquierdo tiene una variable incluida con un coeficiente igual a uno, y las restricciones de igualdad restantes, con un coeficiente igual a cero. En nuestro caso, las restricciones 1ª, 2ª y 3ª tienen una forma preferida con las variables básicas correspondientes.

Solución mediante el método simplex.

Completamos la tabla simplex de la 0ª iteración.

simplex
relación

520

65/2

140

810

-8

-6

-4

Dado que estamos resolviendo el problema al máximo, la presencia de números negativos en la línea índice al resolver el problema al máximo indica que no hemos obtenido la solución óptima y que es necesario pasar de la tabla de la iteración 0. al siguiente.

Procedemos a la siguiente iteración de la siguiente manera:

La columna principal corresponde a .

La fila clave está determinada por la proporción mínima de términos libres y miembros de la columna principal (relaciones simples):

En la intersección de la columna clave y la fila clave encontramos el elemento habilitante, es decir, 7.

Ahora comenzamos a compilar la primera iteración. En lugar de un vector unitario, introducimos el vector.

En la nueva tabla, en lugar del elemento habilitante escribimos 1, todos los demás elementos de la columna clave son ceros. Los elementos de la cadena clave se dividen en el elemento enable. Todos los demás elementos de la tabla se calculan utilizando la regla del rectángulo.

Obtenemos la tabla de la 1ª iteración:

simplex
relación

200

31/7

-16/7

1400/31

2/7

1/7

630

-7

-11/7

-9/7

160

-12/7

8/7

La columna clave para la primera iteración corresponde a .

Encontramos la línea clave, para ello definimos:

En la intersección de la columna clave y la fila clave encontramos el elemento habilitante, es decir 31/7.

El vector se deriva de la base y se introduce el vector.

Obtenemos la tabla de la 2da iteración:

simplex
relación

1400/31

14/31

7/31

-16/31

220/31

27/31

-2/31

9/31

21730/31

-195/31

11/31

-65/31

7360/31

86/31

12/31

8/31

En la fila del índice, todos los términos no son negativos, por lo que se obtiene la siguiente solución al problema de programación lineal (la escribimos de la columna de términos libres):

Por tanto, es necesario vender 7,1 mil rublos. bienes del primer tipo y 45,2 mil rublos. bienes del tercer tipo. No es rentable vender un producto del segundo tipo. En este caso, el beneficio será máximo y ascenderá a 237,4 mil rublos. Al implementar plan optimo el recurso restante del tercer tipo será de 701 unidades.

Problema de doble LP

Escribamos un modelo del problema dual.

Para construir un problema dual, debes utilizar las siguientes reglas:

1) si el problema directo se resuelve al máximo, entonces el problema dual se resuelve al mínimo y viceversa;

2) en el problema de máxima, las restricciones de desigualdad tienen el significado ≤, y en el problema de minimización tienen el significado ≥;

3) cada restricción del problema directo corresponde a una variable del problema dual, y viceversa, cada restricción del problema dual corresponde a una variable del problema directo;

4) la matriz del sistema de restricciones del problema dual se obtiene de la matriz del sistema de restricciones del problema original por transposición;

5) los términos libres del sistema de restricciones del problema directo son coeficientes de las variables correspondientes de la función objetivo del problema dual, y viceversa;

6) si se impone una condición de no negatividad a la variable del problema directo, entonces la restricción correspondiente del problema dual se escribe como una restricción de desigualdad, si no, como una restricción de igualdad;

7) si alguna restricción del problema directo se escribe como una igualdad, entonces la condición de no negatividad no se impone a la variable correspondiente del problema dual.

Transponemos la matriz del problema original:

Solución del problema del LP dual.

Correspondencia entre las variables del problema original y dual:

Con base en la tabla simplex, se obtuvo la siguiente solución al problema de programación lineal dual (la escribimos desde la línea inferior):

Por tanto, el recurso del primer tipo es el más escaso. Su puntuación es máxima e igual a . El recurso del tercer tipo es redundante: su valor dual es cero. Cada unidad adicional de bienes del segundo grupo vendida reducirá la ganancia óptima en
Se considera un método gráfico para resolver un problema de programación lineal (LPP) con dos variables. Se da un ejemplo de la tarea. descripción detallada construir un dibujo y encontrar una solución.

Solución del problema del transporte.
Revisado en detalle problema de transporte, su modelo matemático y métodos de solución: encontrar el plan de referencia mediante el método del elemento mínimo y buscar la solución óptima mediante el método potencial.

Toma de decisiones en condiciones de incertidumbre.
La solución de un juego matricial estadístico en condiciones de incertidumbre se considera utilizando los criterios de Wald, Savage, Hurwitz, Laplace y Bayes. Utilizando un problema de ejemplo, se muestra en detalle la construcción de una matriz de pagos y una matriz de riesgos.

Si el enunciado del problema contiene restricciones con el signo ≥, entonces se pueden reducir a la forma ∑a ji b j multiplicando ambos lados de la desigualdad por -1. Introduzcamos m variables adicionales x n+j ≥0(j =1,m) y transformemos las restricciones a la forma de igualdades.

(2)

Supongamos que todas las variables iniciales del problema x 1 , x 2 ,..., x n no son básicas. Entonces las variables adicionales serán básicas y una solución particular al sistema de restricciones tendrá la forma

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)

Dado que en este caso el valor de la función objetivo F 0 = 0, podemos representar F(x) de la siguiente manera:

F(x)=∑c yo x yo +F 0 =0 (4)

La tabla simplex inicial (tabla simplex 1) se compila en base a las ecuaciones (2) y (4). Si las variables adicionales x n+j están precedidas por un signo “+”, como en (2), entonces todos los coeficientes delante de las variables x i y el término libre b j se ingresan en la tabla simplex sin cambios. Al maximizar la función objetivo, los coeficientes se ingresan en la fila inferior de la tabla simplex con signos opuestos. Los términos libres de la tabla simplex determinan la solución del problema.

El algoritmo para resolver el problema es el siguiente:

1er paso.

Se ven los miembros de la columna de miembros gratuitos. Si todas son positivas, entonces se ha encontrado una solución básica admisible y se debe proceder al paso 5 del algoritmo, que corresponde a encontrar la solución óptima. Si la tabla simplex inicial tiene términos libres negativos, entonces la solución no es válida y se debe ir al paso 2.

2do paso.

Para encontrar una solución admisible, se lleva a cabo y es necesario decidir cuál de las variables no básicas incluir en la base y cuál eliminar de la base.	Tabla 1.	variables básicas
	Tabla 1.	Miembros gratuitos bajo restricciones	Variables no básicas	...	x1	...
x l	xn	xn+1	segundo 1	...	un 11	...	un 12
un 1l	un 1n	xn+2	segundo 2	...	un 21	...	un 22
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
un 2l	un 2n	xn+r	b2	...	un r1	...	un r2
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
un rl	arn	xn+m	b m	...	un m1	...	un m2
un ml	un minuto	F(x)máx	F 0	...	F(x)máx	...	-c 1

-c 2

-c norte

Para hacer esto, seleccione cualquiera de los elementos negativos de la columna de términos libres (sea b 2 principal o resolutivo. Si no hay elementos negativos en la fila con un término libre negativo, entonces el sistema de restricciones es inconsistente y el problema no tiene solución. Al mismo tiempo, la variable que es la primera en cambiar de signo cuando aumenta el NP x l seleccionado se excluye del BP. Este será x n+r, cuyo índice r se determina a partir de la condición aquellos. la variable que corresponde a proporción más pequeña

término libre al elemento de la columna principal seleccionada. Esta relación se llama relación simplex. Sólo deben considerarse relaciones símplex positivas. La recta correspondiente a la variable x n+r se llama

liderar o permitir. El elemento de la tabla simplex a rl, que se encuentra en la intersección de la fila principal y la columna principal, se llama elemento principal o de resolución. Encontrar el elemento principal finaliza el trabajo con cada tabla simplex regular. 3er paso.

Primero, la nueva tabla simplex completará la fila y columna que encabezaban la tabla simplex anterior. La expresión (5) significa que el elemento a" rl en lugar del elemento principal es igual al recíproco del elemento de la tabla simplex anterior. Los elementos de la fila a ri se dividen por el elemento principal, y los elementos de la fila la columna a jl también se divide por el elemento principal, pero se toma con el signo opuesto. Los elementos b" r y c" l se calculan según el mismo principio.

El resto de fórmulas se pueden escribir fácilmente usando .

El rectángulo se construye según la antigua tabla simplex de tal manera que una de sus diagonales esté formada por los elementos recalculados (a ji) y principales (a rl) (Fig. 1). La segunda diagonal está determinada de forma única. Para encontrar un nuevo elemento a" ji, el producto de los elementos de la diagonal opuesta dividido por el elemento principal se resta del elemento a ji (esto se indica con el signo “-” al lado de la celda). Elementos b" j, (j≠r) y c"i se recalculan de la misma manera. (i≠l).

4to paso.

El análisis de la nueva tabla simplex comienza con el primer paso del algoritmo. La acción continúa hasta que se encuentre una solución básica factible, es decir. Todos los elementos de la columna flotante deben ser positivos.

5to paso.

Creemos que se ha encontrado una solución básica admisible. Nos fijamos en los coeficientes de la recta de la función objetivo F(x). Un signo de la optimización de una tabla simplex es la no negatividad de los coeficientes de las variables no básicas en la fila F. Arroz. 1. Regla del rectángulo Si entre los coeficientes de la fila F hay negativos (con la excepción del término libre), entonces es necesario pasar a otra solución básica. Al maximizar la función objetivo, la base incluye una de las variables no básicas (por ejemplo x l), cuya columna corresponde al máximo

valor absoluto coeficiente negativo c l en la fila inferior de la tabla simplex. Esto le permite seleccionar la variable cuyo aumento conduce a una mejora en la función objetivo. La columna correspondiente a la variable x l se llama columna principal. Al mismo tiempo, se excluye de la base la variable x n+r, cuyo índice r está determinado por la relación simplex mínima:

La fila correspondiente a x n+r se llama principal, y el elemento de la tabla simplex a rl, que se encuentra en la intersección de la fila principal y la columna principal, se llama

Durante la optimización de la solución, si todos los elementos de la columna principal no son positivos, entonces no se puede seleccionar la fila principal. En este caso, la función en el área soluciones admisibles el problema no está limitado desde arriba y F max ->&∞.

Si, en el siguiente paso de búsqueda de un extremo, una de las variables básicas se vuelve igual a cero, entonces la solución básica correspondiente se llama degenerada. En este caso, se produce el llamado ciclo, caracterizado por el hecho de que la misma combinación de BP comienza a repetirse con cierta frecuencia (se conserva el valor de la función F) y es imposible pasar a una nueva solución básica factible. . El bucle es una de las principales desventajas del método simplex, pero es relativamente raro. En la práctica, en tales casos, generalmente se niegan a ingresar en la base la variable cuya columna corresponde al valor absoluto máximo del coeficiente negativo en la función objetivo y seleccionan aleatoriamente una nueva solución base.

Ejemplo 1. Resuelve el problema.

máx(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Usando el método simplex y dando interpretación geométrica proceso de decisión.

En la figura 2 se presenta una interpretación gráfica de la solución al problema. 2. El valor máximo de la función objetivo se logra en el vértice del ODZP con coordenadas. Resolvamos el problema usando tablas simplex. Multipliquemos la segunda restricción por (-1) e introduzcamos variables adicionales para llevar las desigualdades a la forma de igualdades, luego

Tomamos las variables iniciales x 1 y x 2 como no básicas, consideramos las adicionales x 3, x 4 y x 5 como básicas y compilamos una tabla simplex (tabla simplex 2). La solución correspondiente a la tabla simplex. 2, no es válido; el elemento principal se delinea y selecciona de acuerdo con el paso 2 del algoritmo anterior. La siguiente tabla simplex. 3 define una solución básica admisible; el vértice del ODZP en la Fig. 1 le corresponde. 2 El elemento principal se delinea y selecciona de acuerdo con el quinto paso del algoritmo de resolución de problemas. Mesa 4 corresponde a la solución óptima del problema, por lo tanto: x 1 = x 5 = 0; x2 = 4; x3 = 3; x4 = 8; F máx = 20.

Arroz. 2. Solución gráfica tareas

método simplex Es un proceso iterativo de solución dirigida de un sistema de ecuaciones paso a paso, que comienza con una solución de referencia y en busca de mejor opción se mueve a lo largo de los puntos de las esquinas del área de solución factible, mejorando el valor de la función objetivo hasta que la función objetivo alcanza el valor óptimo.

Objeto del servicio. El servicio está destinado a soluciones en línea Problemas de programación lineal (LPP) utilizando el método simplex en siguientes formularios entradas:

en forma de tabla simplex (método de transformación de Jordan); forma básica archivos;
método simplex modificado; en forma de columna; en forma de línea.

Instrucciones. Seleccione el número de variables y el número de filas (número de restricciones). La solución resultante se almacena en archivo de palabra y Excel.

En este caso, no tenga en cuenta restricciones como x i ≥ 0. Si no hay restricciones en la tarea para algún x i, entonces el ZLP debe convertirse al KZLP o utilizar este servicio. Al resolver, el uso se determina automáticamente. método M(método simple con base artificial) y método simplex de dos etapas.

Lo siguiente también se utiliza con esta calculadora:
Método gráfico para resolver ZLP.
Solución del problema del transporte.
Resolver un juego de matrices
Usando el servicio en modo en línea puedes determinar el precio de un juego de matrices (límites superior e inferior), consulta la disponibilidad punto de silla, encuentre una solución a una estrategia mixta utilizando los siguientes métodos: minimax, método simplex, método gráfico (geométrico), método de Brown.
Extremo de una función de dos variables.
Problemas de programación dinámica
Distribuir 5 lotes homogéneos de bienes entre tres mercados para obtener ingreso máximo de su venta. Los ingresos por ventas en cada mercado G(X) dependen del número de lotes vendidos del producto X y se presentan en la tabla.

Volumen de producto X (en lotes)	Ingreso G(X)
Volumen de producto X (en lotes)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algoritmo del método simplex incluye los siguientes pasos:

Elaboración del primer plan básico. Transición a la forma canónica del problema de programación lineal mediante la introducción de variables de equilibrio adicionales no negativas.
Comprobar la optimización del plan. Si hay al menos un coeficiente de línea de índice menor que cero, entonces el plan no es óptimo y debe mejorarse.
Determinar la columna y fila principal. De los coeficientes negativos de la línea del índice, se selecciona el mayor en valor absoluto. Luego, los elementos de la columna de miembros libres de la tabla simplex se dividen en elementos del mismo signo de la columna principal.
Construyendo un nuevo plan de referencia. La transición a un nuevo plan se lleva a cabo recalculando la tabla simplex utilizando el método de Jordan-Gauss.

Si es necesario encontrar el extremo de la función objetivo, entonces estamos hablando de acerca de la búsqueda valor mínimo(F(x) → min , ver ejemplo de resolución de una función de minimización) y valor máximo((F(x) → max , ver ejemplo de resolución de una maximización de función)

Una solución extrema se logra en el límite de la región de soluciones factibles en uno de los vértices de los puntos de las esquinas del polígono, o en el segmento entre dos puntos de las esquinas adyacentes.

Teorema fundamental de la programación lineal. Si el objetivo función ZLP alcanza un valor extremo en algún punto de la región de soluciones factibles, luego toma este valor en el punto de la esquina. Si la función objetivo ZLP alcanza un valor extremo en más de un punto de esquina, entonces toma el mismo valor en cualquiera de las combinaciones lineales convexas de estos puntos.

La esencia del método simplex.. El movimiento al punto óptimo se realiza moviéndose desde un punto de esquina al vecino, lo que acerca y más rápido a X opt. Tal esquema para enumerar puntos, llamado método simplex, sugerido por R. Danzig.
Los puntos de esquina se caracterizan por m variables básicas, por lo que la transición de un punto de esquina a uno adyacente se puede lograr cambiando solo una variable básica en la base a una variable de una no base.
Implementación del método simplex vigente varias características y planteamientos de problemas, LP tiene varias modificaciones.

La construcción de tablas simplex continúa hasta obtener la solución óptima. ¿Cómo se puede utilizar una tabla simplex para determinar que la solución a un problema de programación lineal es óptima?
Si la última línea (valores de la función objetivo) no contiene elementos negativos, por tanto, encontrará el plan óptimo.

Observación 1. Si una de las variables básicas es igual a cero, entonces el punto extremo correspondiente a dicha solución básica es degenerado. La degeneración ocurre cuando hay ambigüedad en la elección de la línea guía. Es posible que no notes en absoluto la degeneración del problema si eliges otra línea como guía. En caso de ambigüedad, se debe seleccionar la fila con el índice más bajo para evitar bucles.

Observación 2. Dejemos que en algún punto extremo todas las diferencias simplex sean no negativas D k ³ 0 (k = 1..n+m), es decir se obtiene una solución óptima y existe A k - un vector no básico para el cual D k = 0. Entonces el máximo se logra al menos en dos puntos, es decir existe un óptimo alternativo. Si introducimos esta variable x k en la base, el valor de la función objetivo no cambiará.

Observación 3. La solución al problema dual está en la última tabla simplex. Los últimos m componentes del vector de diferencias simplex (en las columnas de variables de equilibrio) son la solución óptima al problema dual. Significado funciones objetivo Los problemas directo y dual coinciden en puntos óptimos.

Observación 4. Al resolver el problema de minimización, se introduce en la base el vector con la mayor diferencia simplex positiva. A continuación se aplica el mismo algoritmo que para el problema de maximización.

Si se especifica la condición “Es necesario que las materias primas tipo III se consuman por completo”, entonces la condición correspondiente es una igualdad.

Popular en la categoría: