Solución mediante el método simplex en Excel. Transformada de Jordan-Gauss y método simplex en Excel. Construyendo un modelo matemático
1. Transformar las desigualdades en igualdades
2. Encuentre la solución básica factible inicial.
3. Con base en la condición de optimización, se determina la variable de entrada. Si no hay variables de entrada, entonces el proceso finaliza.
4. Según la condición de admisibilidad, seleccione la variable excluida.
5. Calcula los elementos de la nueva fila principal.
nueva línea principal = línea actual/elemento principal
6. Calcule los elementos de las filas restantes, incluida la cadena z.
nueva fila = fila actual - sus coeficientes en la columna principal * nueva fila principal
Pasemos al paso 3.
Para facilitar el registro del proceso iterativo, escribimos todos los valores en una tabla Simplex.
2. Un ejemplo de cómo resolver el problema de lp usando el paquete ms excel
Para muchos problemas de optimización, es conveniente utilizar un modelo de programación lineal. La esencia del problema es compilar un sistema de desigualdades que describa las restricciones correspondientes del problema y especifique la función de optimización.
Para encontrar una solución en dichos modelos, puede utilizar la herramienta MS EXCEL - BÚSQUEDA DE SOLUCIONES.
Veamos cómo crear un modelo de programación lineal y encontrar su solución usando un ejemplo.
2.1. Formulación del problema
Se procesan dos tipos de piezas (A y B) en tres máquinas y cada pieza se procesa en todas las máquinas. Conocemos el tiempo de procesamiento de las piezas en cada máquina, el tiempo de funcionamiento de las máquinas durante un ciclo de producción y el beneficio de la venta de una pieza de cada tipo (datos en la tabla). Elaborar un plan de producción que proporcione el mayor beneficio.
2.2. Construyendo un modelo matemático
Denotemos por x 1 y x 2 el número de unidades de piezas de los tipos A y B planificadas para la producción. Entonces el tiempo de procesamiento x 1 de las piezas del tipo A en la primera máquina es 1 * x 1; x 2 partes del tipo B, respectivamente 2 * x 2. El tiempo total de funcionamiento de la máquina I para la producción del número planificado de piezas es igual a x 1 + 2 * x 2, está limitado a 16 horas de funcionamiento de esta máquina durante un ciclo de producción. Por lo tanto se debe satisfacer la desigualdad:
x1 +2*x2<=16;
De manera similar, para las máquinas II y III obtenemos las siguientes desigualdades, respectivamente:
x1 + x2<=10;
3*x1+x2<=24;
Además, en el sentido de la definición de los valores introducidos x 1 y x 2, se deben cumplir las siguientes condiciones: x 1 >=0; x2 >=0;
Así, obtenemos un sistema de desigualdades llamado sistema de restricciones del problema:
Cualquier solución (x 1; x 2) de un sistema de restricciones se denomina plan de producción o plan admisible para el problema.
El beneficio por la venta de x 1 unidades de piezas del tipo A es igual a 4. x 1, y el beneficio por la venta de x 2 unidades de piezas del tipo B es igual a 2x 2. El beneficio total por la venta de productos fabricados según el plan (x 1; x 2) es igual a:
F(X 1 ; X 2 )=4x 1 +2x 2 (mil rublos).
Función lineal F(X 1 ; X 2 ) se llama función objetivo del problema.
Según las condiciones del problema, se requiere encontrar un plan (x 1; x 2) en el que la ganancia sea máxima.
Así, se ha construido un modelo matemático del problema como un problema de programación lineal:
F(X 1 ; X 2 )=4x 1 +2x 2 → máximo
Ejercicio. Implemente todos los pasos a continuación en el procesador de hojas de cálculo de Excel necesarios para resolver el problema de LP.
Expliquemos la secuencia de acciones al resolver un problema de LP utilizando el método tabular simplex usando un ejemplo.
Tarea. Resuelva el problema utilizando el método tabular simplex.
bajo restricciones
Orden de trabajo:
I. Comprobar el cumplimiento de las condiciones necesarias para resolver el problema utilizando el método tabular simplex en su forma pura.
II. Registro de datos iniciales.
Abra una hoja de cálculo de Excel e ingrese un título Método tabular para resolver problemas de programación lineal..
Complete la tabla simplex inicial.
La siguiente fila de la tabla coincide con la primera restricción. La variable básica que se encuentra en la primera restricción, el término libre, los coeficientes de las variables de la restricción correspondiente. Las líneas 2 y 3 se rellenan de la misma forma.
La última línea es la línea de la función objetivo, que se completa de la siguiente manera, el término libre sin cambiar de signo y los coeficientes de las variables con el contrario (Fig. 26). 
Arroz. 26. Mesa simplex original.
Anota el valor de la función objetivo, el plan de referencia inicial, en base a la columna de términos libres (Fig. 27).
Arroz. 27. Valor de la función objetivo y plan de referencia inicial.
III. Encontrar el plan óptimo y el valor óptimo de la función objetivo.
Dado que la línea del índice contiene coeficientes negativos para las variables, el plan de referencia no es óptimo. Organiza el proceso de mejora de tu plan siguiendo los pasos sugeridos.
Entre los elementos negativos de la fila del índice, seleccione el elemento con el valor absoluto más grande. Llame a la columna correspondiente al frente. Esta columna muestra qué variable debe incluirse en la base (Fig. 28).
Arroz. 28. Seleccionar una columna principal.
Arroz. 29. Estableciendo relaciones.
Determine el resultado de la relación (Tabla 5), teniendo en cuenta que el resultado puede ser un número distinto de cero, 0 o infinito (Fig. 30).
Arroz. treinta. El resultado de la relación.
Elija la más pequeña de las proporciones. Llame a la línea en la que el resultado más pequeño es la línea principal (Fig. 31). Esta línea muestra qué variable debe excluirse de la base.
Arroz. 31. Selección de línea conductora.
En la intersección de la fila principal y la columna principal, se obtiene un elemento principal (Fig. 32).
Arroz. 32. Elemento protagonista.
Arroz. 33. Nueva base.
Para obtener 1 en la celda C13, debes dividir cada elemento de la fila principal por el elemento principal.
En la celda C13, escribe la fórmula = C5/2 (Figura 34), presiona Enter.
Arroz. 34. Recibiendo 1 en la celda C13.
Estire la fórmula (Fig. 35).
Arroz. 35. La primera fila de la segunda tabla simplex.
Luego obtenga un cero en la celda C14.
Para ello, en la segunda tabla simplex 1 (celda C13), multiplica por el elemento de la tabla anterior correspondiente al elemento de la celda C14, tomado con el signo opuesto, y suma con el mismo elemento.
Dado que el elemento correspondiente al elemento de la celda C14 es igual a 1 (celda C6), esto significa que todos los elementos de la primera fila de la segunda tabla simplex se multiplican por (-1) y se suman a los elementos correspondientes de la primera tabla simplex. mesa. Escriba la fórmula =C13*(-1)+C6 en la celda C14 (Fig. 36).
Arroz. 36. Elemento C14 de la segunda tabla simplex.
Del mismo modo, obtenga los elementos restantes de la columna base (Fig. 37 y Fig. 38).
Arroz. 37. Elemento C15 de la segunda tabla simplex. 
Arroz. 38. Elemento C16 de la segunda tabla simplex.
Estire las fórmulas de la columna base a lo largo de las filas para obtener una segunda tabla simplex (Fig. 39).
Arroz. 39. Primera y segunda tablas simplex.
Dado que la línea del índice contiene coeficientes negativos para las variables, el plan de referencia no es óptimo.
Anote el valor de la función objetivo, el nuevo plan de referencia encontrado, con base en la columna de términos libres (Fig. 40). Compruebe que el valor de la función objetivo esté maximizado.
Arroz. 40. El valor de la función objetivo y el plan de soporte de la segunda tabla simplex.
Organice el proceso de mejora del plan siguiendo los pasos sugeridos, comenzando con el paso 5, hasta que se cumpla cualquiera de los criterios de parada. Obtenga la tercera tabla simplex (Fig. 41).
Arroz. 41. Primera, segunda y tercera tablas simplex.
Ejercicio. Utilice los materiales del trabajo de laboratorio No. 3. Realice la prueba usando MathCad.
En Excel 2007, para habilitar el paquete de análisis, debe hacer clic en Ir al bloque Opciones de Excel haciendo clic en el botón en la esquina superior izquierda y luego en " Opciones de Excel"en la parte inferior de la ventana:
A continuación, en la lista que se abre, debe seleccionar Complementos, luego coloque el cursor en el elemento Encontrar una solución, presiona el botón Ir y en la siguiente ventana habilite el paquete de análisis. 
Completa los detalles
Los valores de las variables X i pueden diferir, pero la función objetivo F(x) debe tener el mismo valor. A veces la tarea suena así: realizar cálculos en una computadora y proporcionar una copia impresa de los resultados obtenidos.
MS Excel le permite presentar los resultados de la búsqueda de una solución en forma de informe. Hay tres tipos de informes de este tipo:
- Resultados (Respuesta). El informe incluye los valores iniciales y finales de las celdas objetivo y de influencia, e información adicional sobre las restricciones.
- Resiliencia (Sensibilidad). Un informe que contiene información sobre la sensibilidad de una solución a pequeños cambios en las celdas que se modifican o en las fórmulas de restricción.
- Límites. Además de los valores iniciales y finales de las celdas afectadas y objetivo, el informe incluye límites superiores e inferiores de los valores que las celdas influyentes pueden aceptar si se cumplen las restricciones.
Ejemplo. Hay 6 limpiadores mayores trabajando en la biblioteca. Cada uno de ellos, por sus capacidades físicas y estado de salud, puede realizar sólo determinados tipos de trabajo, y con una determinada productividad. Se conoce la superficie de cada una de las obras. Es necesario conseguir un mínimo de tiempo para la limpieza del local.
PRODUCTIVIDAD DE LAS ABUELA m 2. /min |
|||||||
| Baba Anya | Bella Petrovna | Baba Varya | Baba Galya | Domna Ivánovna | Evgenia Karlovna | Área de trabajo | |
| limpieza de ventanas | 2 | 0 | 0 | 1 | 0 | 0 | 46 |
| trapear pisos | 0 | 1 | 0 | 0 | 0 | 0 | 300 |
| mesas de limpieza | 0 | 0 | 2 | 0 | 0.2 | 1 | 50 |
| Caminos de limpieza | 0 | 0 | 0 | 2 | 0 | 4 | 100 |
Ejemplo.En la granja peletera se pueden criar zorros pardos y árticos. Para garantizar unas condiciones normales de cultivo se utilizan tres tipos de piensos. En la tabla se muestra la cantidad de alimento de cada tipo que deben recibir diariamente los zorros y los zorros árticos. También indica la cantidad total de alimento de cada tipo que puede utilizar la granja peletera y el beneficio de la venta de una piel de zorro y de zorro ártico.
Encuentre la proporción óptima entre la cantidad de alimento y la cantidad de zorros y zorros árticos.
Solution Finder es un complemento de Microsoft Excel que le ayuda a encontrar la solución óptima a un problema, teniendo en cuenta las limitaciones especificadas por el usuario.
Consideraremos encontrar una solución en (este complemento ha sufrido algunos cambios en comparación con la versión anterior en .
En este artículo veremos:
- crear un modelo de optimización en una hoja de MS EXCEL
- configuración Encontrar una solución;
- ejemplo simple (modelo lineal).
Instalación Buscar una solución
Equipo Encontrar una solución esta en el grupo Análisis en la pestaña Datos.
si el equipo Encontrar una solución en grupo Análisis no está disponible, debes habilitar el complemento del mismo nombre.
Para esto:
- en la pestaña Archivo selecciona un equipo Opciones, y luego la categoría Complementos;
- en el campo Control selecciona valor complementos de excel y presione el botón Ir;
- en el campo Complementos disponibles marque la casilla al lado del artículo Encontrar una solución y haga clic en Aceptar.
Nota. Ventana Complementos también disponible en la pestaña Desarrollador. Cómo habilitar esta pestaña.
Después de presionar el botón Encontrar una solución en grupo Análisis, se abrirá su cuadro de diálogo .
Con uso frecuente Encontrar una solución Es más conveniente iniciarlo desde la barra de herramientas de acceso rápido que desde la pestaña Datos. Para colocar un botón en el Panel, haga clic derecho sobre él y seleccione Agregar a la barra de herramientas de acceso rápido.
Acerca de los modelos
Esta sección es para aquellos que recién se están familiarizando con el concepto de modelo de optimización.
Consejo. Antes de usar Encontrar una solución Recomendamos encarecidamente estudiar la literatura sobre la resolución de problemas de optimización y la construcción de modelos.
A continuación se muestra un pequeño programa educativo sobre este tema.
Superestructura Encontrar una solución ayuda a determinar La mejor manera hacer algo:
- "Algo" puede incluir destinar dinero para inversiones, cargar un almacén, entregar mercancías o cualquier otra actividad temática en la que sea necesario encontrar la solución óptima.
- La “mejor manera” o solución óptima en este caso significa: maximizar beneficios, minimizar costes, conseguir la mejor calidad, etc.
A continuación se muestran algunos ejemplos típicos de problemas de optimización:
- Determinar cuál es el máximo de ingresos por la venta de productos manufacturados;
- Determinar en cuál los costos totales de transporte serían mínimos;
- Encuentre que los costos totales de producción serían mínimos;
- Determinar el plazo mínimo para completar todo el trabajo del proyecto (ruta crítica).
Para formalizar la tarea en cuestión, es necesario crear un modelo que refleje las características esenciales del área temática (y no incluya detalles menores). Tenga en cuenta que el modelo está optimizado. Encontrar una solución por un solo indicador(este indicador optimizado se llama función objetivo).
En MS EXCEL, un modelo es una colección de fórmulas interconectadas que utilizan variables como argumentos. Normalmente, estas variables sólo pueden aceptar valores válidos, sujetos a restricciones especificadas por el usuario.
Encontrar una solución selecciona tales valores de estas variables (sujetos a restricciones especificadas) que la función objetivo sea máxima (mínima) o igual a un valor numérico dado.
Nota. En el caso más sencillo, el modelo se puede describir mediante una única fórmula. Algunos de estos modelos se pueden optimizar utilizando la herramienta. Antes de conocernos por primera vez Encontrar una solución Primero tiene sentido comprender en detalle la herramienta relacionada.
Principales diferencias Selección de parámetros de Encontrar una solución:
- Selección de parámetros sólo funciona con modelos de variable única;
- es imposible establecer restricciones a las variables;
- no se determina el máximo o mínimo de la función objetivo, sino su igualdad a un determinado valor;
- funciona eficazmente sólo en el caso de modelos lineales; en el caso no lineal, encuentra un óptimo local (el más cercano al valor original de la variable).
Preparando un modelo de optimización en MS EXCEL
Encontrar una solución optimiza el valor de la función objetivo. Una función objetivo es una fórmula que devuelve un valor único en una celda. El resultado de la fórmula debe depender de las variables del modelo (no necesariamente directamente, sino a través del resultado del cálculo de otras fórmulas).
Se pueden imponer restricciones al modelo tanto en el rango de variación de las propias variables como en los resultados del cálculo de otras fórmulas del modelo que dependen de estas variables.
Todas las celdas que contienen variables y restricciones del modelo deben ubicarse en una sola hoja del libro de trabajo. Introducir parámetros en un cuadro de diálogo Encontrar una solución Sólo es posible desde esta hoja.
La función objetivo (celda) también debe ubicarse en esta hoja. Pero los cálculos intermedios (fórmulas) se pueden colocar en otras hojas.
Consejo. Organice los datos del modelo de modo que solo haya un modelo en una hoja de MS EXCEL. De lo contrario, para realizar cálculos tendrás que guardar y cargar configuraciones constantemente. Encontrar una solución(vea abajo).
Presentemos un algoritmo para trabajar con Encontrar una solución, recomendado por los propios desarrolladores (www.solver.com):
- Definir celdas con variables del modelo (variables de decisión);
- Crea una fórmula en una celda que calculará la función objetivo de tu modelo;
- Cree fórmulas en celdas que calcularán valores en comparación con las restricciones (lado izquierdo de la expresión);
- Usando el cuadro de diálogo Encontrar una solución ingrese enlaces a celdas que contienen variables, a la función objetivo, a fórmulas de restricciones y los valores de las propias restricciones;
- Correr Encontrar una solución para encontrar la solución óptima.
Repasemos todos estos pasos usando un ejemplo simple.
Ejemplo de uso sencillo Encontrar una solución
Es necesario cargar el contenedor con mercancías de modo que el peso del contenedor sea máximo. El contenedor tiene un volumen de 32 metros cúbicos. Los artículos están contenidos en cajas y cajones. Cada caja de mercancías pesa 20 kg y su volumen es de 0,15 m3. Caja: 80 kg y 0,5 m3, respectivamente. Es necesario que el número total de contenedores sea de al menos 110 piezas.
Organizamos estos modelos de la siguiente manera (ver archivo de ejemplo).
Las variables del modelo (cantidad de cada tipo de contenedor) están resaltadas en verde.
La función objetivo (el peso total de todas las cajas y cajones) está en rojo.
Limitaciones del modelo: cantidad mínima de contenedores (>=110) y volumen total (<=32) – синим.
La función objetivo se calcula mediante la fórmula =SUMAPRODUCTO(B8:C8,B6:C6) es el peso total de todas las cajas y cajones cargados en el contenedor.
De manera similar, calculamos el volumen total - =SUMAPRODUCTO(B7:C7,B8:C8). Esta fórmula es necesaria para establecer un límite en el volumen total de cajas y cajones (<=32).
Además, para establecer la limitación del modelo, calculamos el número total de contenedores =SUM(B8:C8) .
Ahora usando el cuadro de diálogo Encontrar una solución Ingresemos enlaces a celdas que contienen variables, una función objetivo, fórmulas para restricciones y los valores de las restricciones mismas (o enlaces a las celdas correspondientes).
Está claro que el número de cajas y cajones debe ser un número entero; esta es otra limitación del modelo.
Después de presionar el botón Encuentra una solución Se encontrará un número de cajas y cajones en el que su peso total (función objetivo) sea máximo y al mismo tiempo se cumplan todas las restricciones especificadas.
Resumen
De hecho, el principal problema al resolver problemas de optimización utilizando Encontrar una solución Lo que importa no son las sutilezas de configurar esta herramienta de análisis, sino la corrección de construir un modelo adecuado a la tarea en cuestión. Por lo tanto, en otros artículos nos concentraremos específicamente en la construcción de modelos, porque un modelo "torcido" es a menudo la razón por la que no se puede encontrar una solución utilizando Encontrar una solución.
A menudo es más fácil examinar varios problemas típicos, encontrar uno similar entre ellos y luego adaptar este modelo a su tarea.
Resolver problemas de optimización clásicos utilizando Encontrar una solución consideró .
Solver no pudo encontrar una solución factible
Este mensaje aparece cuando Encontrar una solución No se pudieron encontrar combinaciones de valores de variables que satisfagan simultáneamente todas las restricciones.
Si estas usando Método simplex para resolver problemas lineales., entonces puedes estar seguro de que realmente no hay solución.
Si utiliza un método para resolver problemas no lineales que siempre comienza con los valores iniciales de las variables, esto también puede significar que la solución factible está lejos de estos valores iniciales. Si tu corres Encontrar una solución con otros valores iniciales de las variables, entonces quizás se encuentre una solución.
Imaginemos que al resolver un problema utilizando un método no lineal, las celdas con variables se dejaron vacías (es decir, los valores iniciales son 0), y Encontrar una solución no encontré una solución. Esto no significa que realmente no haya una solución (aunque ese puede ser el caso). Ahora, con base en los resultados de una determinada evaluación de expertos, ingresaremos otro conjunto de valores en las celdas con variables, que, en su opinión, se acerca al óptimo (buscado). En este caso, Encontrar una solución puede encontrar una solución (si es que realmente existe).
Nota. Puede leer sobre la influencia de la no linealidad del modelo en los resultados del cálculo en la última sección del artículo.
En cualquier caso (lineal o no lineal), primero se debe analizar el modelo para determinar la coherencia de las restricciones, es decir, las condiciones que no se pueden satisfacer simultáneamente. En la mayoría de los casos, esto se debe a una elección incorrecta de la proporción (por ejemplo,<= вместо >=) o valor límite.
Si, por ejemplo, en el ejemplo discutido anteriormente, el valor del volumen máximo se establece en 16 m3 en lugar de 32 m3, entonces esta restricción contradice la restricción sobre el número mínimo de asientos (110), porque el número mínimo de plazas corresponde a un volumen igual a 16,5 m3 (110 * 0,15, donde 0,15 es el volumen de la caja, es decir, el contenedor más pequeño). Al establecer el límite de volumen máximo en 16 m3, Encontrar una solución no encontrará una solución.
Con un límite de 17 m3 Encontrar una solución encontrará una solución.
Algunas configuraciones Encontrar una solución
Método de solución
El modelo discutido anteriormente es lineal, es decir la función objetivo (M es el peso total que puede ser máximo) se expresa mediante la siguiente ecuación M=a1*x1+a2*x2, donde x1 y x2 son las variables del modelo (el número de cajas y cajones), a1 y a2 son sus pesos. En un modelo lineal, las restricciones también deben ser funciones lineales de las variables. En nuestro caso, la limitación de volumen V=b1*x1+b2*x2 también se expresa mediante una dependencia lineal. Obviamente, otra limitación, el número máximo de contenedores (n), también es lineal x1+x2.
En este caso, es necesario elegir un método para resolver el problema no lineal. Ejemplos de dependencias no lineales: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, donde x es una variable y V es una función objetivo.
Botones Agregar, Editar, Eliminar
Estos botones le permiten agregar, editar y eliminar restricciones del modelo.
Botón de reinicio
Para eliminar todas las configuraciones Encontrar una solución clic en el botón Reiniciar– el cuadro de diálogo se borrará.
Esta opción es conveniente cuando se utilizan diferentes opciones de restricción. Al guardar los parámetros del modelo (botón Cargar guardar, luego haga clic en el botón Ahorrar) se propone seleccionar la celda superior del rango (columna) en la que se colocará: un enlace a la función objetivo, enlaces a celdas con variables, restricciones y parámetros de los métodos de solución (disponibles a través del botón Opciones). Antes de guardar, asegúrese de que este rango no contenga datos del modelo.
Para cargar los parámetros guardados, primero presione el botón Cargar guardar, luego, en el cuadro de diálogo que aparece, el botón Descargar, luego especifique el rango de celdas que contienen las configuraciones previamente guardadas (no puede especificar solo la celda superior). Haga clic en Aceptar. Confirme restablecer los valores actuales de los parámetros de la tarea y reemplazarlos por otros nuevos.
Exactitud
Al crear un modelo, el investigador inicialmente tiene alguna estimación de los rangos de variación de la función y las variables objetivo. Teniendo en cuenta los cálculos en MS EXCEL, se recomienda que estos rangos de variación sean significativamente mayores que la precisión del cálculo (generalmente se establece entre 0,001 y 0,000001). Como regla general, los datos en el modelo están normalizados de modo que los rangos de variación de la función objetivo y las variables estén en el rango de 0,1 a 100.000. Por supuesto, todo depende del modelo específico, pero si sus variables cambian más. de 5 a 6 órdenes de magnitud, entonces quizás debería “hacer más rugoso” el modelo, por ejemplo, usando la operación logarítmica.
Enviar su buen trabajo en la base de conocimientos es sencillo. Utilice el siguiente formulario
Los estudiantes, estudiantes de posgrado y jóvenes científicos que utilicen la base de conocimientos en sus estudios y trabajos le estarán muy agradecidos.
Publicado en http://www.allbest.ru/
Resolviendo el problema usando Excel y el método simplex.
Tarea (distributiva)
método simplex
Resolver un problema usando Excel
Tarea (distributiva)
Problema 1 (distributivo)
En la empresa se pueden producir 4 tipos de productos en 3 máquinas intercambiables independientes.
Conocido:
· Tarea de producción para la producción de diferentes tipos de productos en el período planificado.
· Fondo para el tiempo de trabajo efectivo de los equipos en el período planificado - ;
· Normas para el costo del tiempo de máquina para la producción de una unidad de producción - ;
· Beneficio en rublos. de la venta de una unidad de producto producido en tal o cual equipo - .
La información inicial se muestra en la tabla del siguiente formulario.
Tabla 1. Datos iniciales
|
Fondo efectivo. esclavo. tiempo - |
Estándares de consumo de tiempo. por unidad productos - beneficio por unidad. productos - |
||||
El problema requiere encontrar un plan para distribuir la tarea de producción para la producción del producto entre los artistas.
en el que la tarea se completaría con el máximo beneficio total de las ventas del producto.
SOLUCIÓN
Desarrollo de un modelo económico y matemático.
Las variables requeridas caracterizan el volumen de producción del contratista.
Luego la matriz de las variables requeridas.
caracteriza el plan para distribuir las tareas de producción para la producción del producto entre los artistas.
Función objetiva
Se debe maximizar la caracterización del beneficio total de la venta de todos los productos.
Las restricciones a la disponibilidad y utilización del tiempo de trabajo efectivo de los artistas intérpretes o ejecutantes adoptarán la forma de un sistema de desigualdades lineales (2):
Este sistema de restricciones caracteriza la condición de que el gasto total de tiempo de trabajo efectivo por parte de cada artista en el período de planificación para la producción de todo tipo de productos no debe exceder el fondo de tiempo. Así, como resultado de la resolución del problema, cada ejecutante recibirá su propia tarea, en función de sus capacidades. Si alguna variable de equilibrio adquiere valor al resolver un problema, caracterizará el tiempo de trabajo efectivo subutilizado de uno u otro ejecutante, que en condiciones de producción puede utilizarse para producir productos que excedan la tarea.
El siguiente bloque de restricciones debe reflejar la condición para el cumplimiento obligatorio del objetivo general de producción para la producción de productos por tipo y estará representado por un sistema de ecuaciones lineales (3):
Condición para variables no negativas:
Llevemos el problema a forma canónica, para ello sumamos variables a las desigualdades (2) y sumamos 4 bases artificiales a las igualdades (3). Como resultado, escribimos el modelo matemático del problema en forma canónica:
método simplex
Resolvamos este problema usando el método simplex completando la tabla. La solución requiere varias iteraciones. Mostrémoslo.
tabla 1
Los coeficientes de la función objetivo se ingresan en la línea superior de la tabla, la segunda línea es el nombre de todas las incógnitas incluidas en las ecuaciones simplex. La primera columna de la izquierda contiene los coeficientes de la función objetivo, que corresponden a las incógnitas básicas incluidas en el programa original (escritas en la columna). La siguiente, tercera columna de la primera tabla simplex se completa con los valores de las incógnitas básicas. A continuación están las columnas que representan los vectores de condición. Su número es 19. En la siguiente primera columna después de la matriz de condiciones, se escriben las sumas de todos los elementos en las filas. La columna registra los cocientes de dividir los elementos de la columna B final en los elementos de una determinada columna, una matriz de condiciones. Como tenemos una base artificial, habrá dos cálculos en la línea del índice, en el primero de ellos teniendo en cuenta las variables, y en el segundo solo la base artificial. Como tenemos un problema de maximización, es necesario derivar bases artificiales a partir de la base. En la segunda línea del índice seleccionamos la puntuación positiva más grande. Esta es nuestra primera columna. Encontremos relaciones de valor.
Y. De estos ratios seleccionamos el más pequeño, para nosotros esta es la cuarta fila, para la cual el ratio estimado es igual a 1300. Seleccione la fila. La última columna es el coeficiente por el cual se multiplica cada elemento de la fila durante el recálculo. Se obtiene dividiendo los elementos de la columna seleccionada por el elemento clave, que se encuentra en la intersección de la columna seleccionada y la fila, para nosotros es 1. Hacemos el recálculo para todos los elementos no seleccionados, que se realiza como sigue: del elemento recalculado restamos el elemento de la fila clave, multiplicado por el coeficiente de la fila recalculado: y así sucesivamente para todos los elementos. De la base derivamos una base artificial, introduciendo al mismo tiempo una variable en la base.
Las dos últimas líneas son líneas de índice donde se recalculan los valores de la función objetivo, así como toda la línea de índice, cuando todos los elementos son positivos o cero, el problema estará resuelto.
Mostrémoslo.
Tabla 2
Seleccionemos la columna con la variable. Encontramos las proporciones estimadas, de las cuales seleccionamos la más pequeña: esto es 550. Derivamos una variable artificial de la base y, al mismo tiempo, introducimos una variable en la base. Cuando de la base se deriva una base artificial, se elimina la columna correspondiente.
Tabla 3
Seleccionemos la columna. La proporción estimada más pequeña, 600, se encuentra en la sexta fila. De la base derivamos una base artificial, introduciendo al mismo tiempo una variable en la base.
Tabla 4
Seleccionemos la columna con la variable. La proporción estimada más baja, 28,57, se encuentra en la primera fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 5
Seleccionemos la columna con la variable. La proporción estimada más baja, 407,7, se encuentra en la tercera fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 6
Seleccionemos la columna con la variable. La proporción estimada más baja, 344,3, se encuentra en la séptima fila. De la base derivamos una base artificial, introduciendo al mismo tiempo una variable en la base.
Tabla 7
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 3,273, se encuentra en la segunda fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 8
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 465, se encuentra en la séptima fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 9
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 109, se encuentra en la tercera fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 10
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 10, se encuentra en la primera fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 11
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 147, se encuentra en la segunda fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 12
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 367, se encuentra en la quinta fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 13
Seleccionemos la columna con la variable. La proporción estimada más pequeña, 128, se encuentra en la cuarta fila. Derivamos una variable de la base e introducimos una variable en la base.
Tabla 14
Dado que no hay estimaciones negativas en la recta del índice, se obtiene un plan óptimo en el que el volumen de producción está representado por la matriz
al mismo tiempo, el beneficio es máximo y asciende a 17.275,31 rublos.
Resolviendo el problema usando Sobresalir
El modelo matemático del problema debe ser transferido a ET EXCEL. Para esto:
· Considerar la organización de los datos iniciales del modelo (coeficientes de la función objetivo y restricciones), proporcionándoles nombres claros.
· Reservar variables independientes del modelo matemático en celdas separadas.
· En una de las celdas, crea una fórmula que defina la función objetivo.
· Selecciona celdas y coloca en ellas fórmulas que correspondan a los lados izquierdos de las restricciones.
· Ingrese al elemento del menú "Buscar una solución", ingrese los datos necesarios y obtenga la solución óptima al problema.
· Analizar la solución resultante y los informes.
Consideremos la secuencia de acciones para implementar estas etapas de resolución de un problema usando EXCEL.
Creemos una tabla para ingresar los datos iniciales.
Ingresaremos los datos iniciales en el formulario creado.
Los coeficientes de la función objetivo, que expresan el beneficio de la producción de una unidad de producto de cada tipo (beneficio unitario), se escriben en las celdas B6: M6.
Los coeficientes de restricción de recursos que determinan la necesidad de cada tipo de recurso para producir una unidad de producción se encuentran en las celdas B9:M15. Las celdas P9:P15 contienen los lados derechos de las restricciones de recursos. Las celdas B3:M3 están reservadas para las variables independientes del problema: los volúmenes de producción requeridos.
En la celda N7, ingrese la fórmula para la función objetivo usando el comando de inserción de función SUMPRODUCTO:
También completamos las restricciones en el lado derecho.
Después de esto, puedes empezar a buscar una solución. Para resolver problemas de optimización en EXCEL, utilice el comando BUSCAR SOLUCIÓN en el menú SERVICIO.
Este comando opera con tres componentes principales del modelo optimizado integrado en ET:
· Una celda que contiene la función objetivo del problema.
· Celdas editables que contienen variables independientes.
· Celdas que contienen los lados izquierdos de restricciones sobre recursos disponibles, así como restricciones simples sobre variables independientes.
Consideremos la secuencia de entrada de estos componentes.
El cursor está en la celda N7 y el comando SERVICIO - Buscar una solución. Aparecerá un cuadro de diálogo en la pantalla.
En la ventana, complete el campo Establecer celda de destino, que debe contener la dirección $N$7. A continuación, configure el botón para buscar el valor máximo. En el campo Cambiar celdas, ingrese las direcciones de las variables deseadas $B3:$M3. Luego debes ingresar restricciones usando el botón Agregar.
Ahora que se han establecido todas las restricciones para encontrar la solución óptima, podemos presionar el botón:
Luego de esto obtendremos una solución al problema.
Si los cálculos fueron exitosos, luego de completar la búsqueda de una solución, los valores se insertarán en la tabla, y también se podrá especificar el Tipo de Informe - Resultados, como resultado de lo cual podremos obtener el siguiente informe. trabajador tiempo equipo beneficio
En consecuencia, la solución en EXCEL es la misma que con el método SIMPLEX, lo que significa que el problema considerado se ha resuelto correctamente.
Publicado en Allbest.ru
...Documentos similares
Determinación del volumen óptimo de producción mediante el método matemático, el método simplex y el uso de Excel. Resolviendo el problema de la asignación óptima de inversiones utilizando el programa de aplicación Excel. Elaboración de un esquema de transporte óptimo.
trabajo del curso, añadido el 10/09/2012
Planificación de beneficios en la producción de dos tipos de combustible. Elaboración de un plan de producción óptimo para obtener el máximo beneficio de su venta. Determinación del plan básico de transporte de carga mediante el método de costo mínimo y utilizando Excel.
prueba, agregada el 12/11/2014
Algoritmo para la resolución de problemas de programación lineal mediante el método simplex. Construcción de un modelo matemático de un problema de programación lineal. Resolver un problema de programación lineal en Excel. Búsqueda de rentabilidad y plan de producción óptimo.
trabajo del curso, añadido el 21/03/2012
Utilizando el método simplex, se determina un plan de producción para obtener la máxima rentabilidad de manera que se consuma en su totalidad la materia prima tipo II. Resolver problemas de programación lineal utilizando una hoja de cálculo de Excel, creando un algoritmo.
trabajo del curso, añadido el 30/09/2013
Estudio del modelo matemático y económico de la empresa con el fin de desarrollar una solución óptima de producción para obtener el máximo beneficio y minimizar costes utilizando métodos de optimización y el programa MS Excel y el paquete de herramientas Matlab.
tesis, agregada el 15/06/2014
Revisión de algoritmos para la resolución de problemas de programación lineal. Desarrollo de un algoritmo para el método tabular simplex. Elaboración de un plan de producción que permita conseguir el máximo beneficio en ventas. Construcción de un modelo matemático del problema.
trabajo del curso, añadido el 21/11/2013
Determinar el número y tipo de silenciadores para tractores y automóviles que la empresa debe producir para maximizar sus beneficios. Resolución de problemas de programación lineal mediante métodos gráficos y simplex utilizando el editor de hojas de cálculo de Excel.
trabajo del curso, añadido el 09/04/2013
Optimización de costos de entrega de productos a los consumidores. Características del problema de transporte, forma general de solución, generalización; Formulación matemática y significativa del problema, solución utilizando MS Excel: listado de programas, análisis de resultados.
trabajo del curso, añadido el 04/02/2011
Fundamentos matemáticos de la optimización. Planteamiento del problema de optimización. Métodos de optimización. Resolver el problema mediante el método simplex clásico. Método gráfico. Resolución de problemas utilizando Excel. Coeficientes de la función objetivo. Programación lineal, método, problemas.
resumen, añadido el 21/08/2008
Determinar la cantidad de materias primas compradas para la producción por mes, durante todo el año y para el año en su conjunto. Algoritmo de acciones necesarias, presentación de resultados en forma gráfica. Resolviendo el problema en Excel y usando herramientas VBA.
