Resolviendo el método simplex en línea en detalle. Resolver un problema de producción mediante el método tabular simplex. Reducción a la forma canónica de la ZLP
método simplex es un proceso iterativo de solución dirigida de un sistema de ecuaciones paso a paso, que comienza con solución de referencia y en busca 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 reducirse al KZLP, o usar este servicio. La solución determina automáticamente el uso. método M (método simplex 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) | ||
| 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 de referencia.. Ir a forma canónica problemas 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 uno nuevo plan de referencia . La transición a un nuevo plan se lleva a cabo como resultado del recálculo de la tabla simplex. Método 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) → mín, ver ejemplo de una solución de minimización de funciones) Y valor máximo((F(x) → máx, ver ejemplo de una solución de maximización de funciones)
Se logra una solución extrema en el límite de la región soluciones admisibles en uno de los vértices de los puntos de esquina del polígono, o en un segmento entre dos puntos de esquina 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 vecino 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 que LP tiene varias modificaciones.
La construcción de tablas simplex continúa hasta obtener 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, encontrará plan optimo.
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 la degeneración del problema en absoluto 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. Solución problema dual esta en el ultimo 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.
| - | x1 | + | x2 | - | S 1 | = | 1 | ||||||||||
| x1 | +3 | x2 | + | T 2 | = | 15 | |||||||||||
| - | 2 | x1 | + | x2 | + | S 3 | = | 4 |
| - | x1 | + | x2 | - | S 1 | + | Por tanto, se ha determinado el elemento que será la base. A continuación contamos. | = | 1 | |||||||||||
| x1 | +3 | x2 | + | T 2 | = | 15 | ||||||||||||||
| - | 2 | x1 | + | x2 | + | S 3 | = | 4 |
| R 1 x 1 = 0 x 2 = 0 S 1 = 0 |
S 2 = 15 S 3 = 4 R 1 = 1 |
| x1 | x2 | S 1 | T 2 | S 3 | Por tanto, se ha determinado el elemento que será la base. A continuación contamos. | Paso #1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | Calle. miembro | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 1 |
| - | x1 | + | x2 | - | S 1 | = | 1 | ||||||||||
| 4 | x1 | + | 3 | S 1 | + | T 2 | = | 12 | |||||||||
| - | x1 | + | S 1 | + | S 3 | = | 3 |
| x1 | x2 | S 1 | T 2 | S 3 | Paso #1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W - 0 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W - 0 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 1 |
| F-13 S 1 = 0 S 2 = 0 |
x 1 = 3 x 2 = 4 S 3 = 6 |
funciones f. Si necesita resolver un problema de programación lineal usando tablas simplex, entonces nuestro servicio en línea te daré gran ayuda . El método simplex implica la enumeración secuencial de todos los vértices de la región. valores aceptables
para encontrar el vértice donde la función toma un valor extremo. En la primera etapa, se encuentra alguna solución, que se mejora en cada paso posterior. Esta solución se llama básica. A continuación se muestra la secuencia de acciones al resolver un problema de programación lineal utilizando el método simplex:
Primer paso. En la tabla compilada, en primer lugar, debe mirar la columna con miembros gratuitos. Si contiene elementos negativos, entonces es necesario pasar al segundo paso, si no, al quinto. Segundo paso.
En el segundo paso, es necesario decidir qué variable excluir de la base y cuál incluir para volver a calcular la tabla simplex. Para hacer esto, miramos la columna con términos libres y encontramos un elemento negativo en ella. La línea con un elemento negativo se llamará principal. En él encontramos el elemento máximo negativo en módulo, la columna correspondiente es la esclava. Si entre los miembros gratuitos hay
| valores negativos | Miembros gratuitos bajo restricciones | Variables no básicas | |||||
| x1 | x2 | ... | xl | ... | 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 | -c 1 | -c 2 | ... | -c 1 | ... | -c norte |
Tercer paso.
En el tercer paso, recalculamos toda la tabla simplex usando fórmulas especiales que se pueden ver usando.
Cuarto paso.
Si después del nuevo cálculo quedan elementos negativos en la columna de términos libres, pase al primer paso, si no los hay, al quinto.
| Quinto paso. | Si ha llegado al quinto paso, entonces ha encontrado una solución aceptable. Sin embargo, esto no significa que sea óptimo. Será óptimo sólo si todos los elementos de la cadena F son positivos. Si este no es el caso, entonces es necesario mejorar la solución, para lo cual encontramos la fila y columna principales para el siguiente recálculo utilizando el siguiente algoritmo. Inicialmente, encontramos el número negativo mínimo en la cadena F, excluyendo el valor de la función. La columna con este número será la principal. Para encontrar la fila principal, encontramos la relación entre el término libre correspondiente y el elemento de la columna principal, siempre que sean positivos. La relación mínima le permitirá determinar la línea principal. Recalculamos la tabla nuevamente usando las fórmulas, es decir vaya al paso 3. | 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 | 1 | 9 | 3 | 96 | camisa 3 | 20 | 10 | 30 | 640 | Reservas | 1 | 2 | 2 | 44 | hilos (m.) | 2 | 5 | 4 |
botones (uds.)
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
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. 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.
| № | PA | cB | ao | x1 | x2 | x3 | x4 | x5 | x6 | simplex | 2 | 5 | 4 | 0 | 0 | 0 | relación | 0 | x4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 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.
