Resolviendo el problema mediante el método gráfico online. Resolución de problemas de programación lineal mediante el método gráfico. Encontrar una solución al problema de LP
Los métodos gráficos están asociados principalmente con imagen geométrica dependencia funcional utilizando líneas en un plano. Los gráficos se utilizan para encontrar rápidamente el valor de funciones según el valor del argumento correspondiente, para una representación visual. dependencias funcionales.
En el análisis económico se utilizan casi todos los tipos de gráficos: gráficos comparativos, gráficos de series temporales, curvas de distribución, gráficos de campos de correlación, cartogramas estadísticos. Los diagramas de comparación están especialmente extendidos en el análisis: para comparar los indicadores de informes con los planificados, períodos anteriores y empresas líderes de empresas nacionales o extranjeras. Para una representación visual de la dinámica de los fenómenos económicos (y en el análisis con series de tiempo tenemos que tratar muy a menudo) se utilizan diagramas de series de tiempo.
Mediante el uso red Los gráficos se construyen dependiendo, por ejemplo, del nivel de costos y también del volumen de productos producidos y vendidos. gráficos en los que se pueden representar correlaciones entre indicadores. En un sistema de ejes de coordenadas, la imagen muestra la influencia de varios factores sobre un indicador particular.
El método gráfico es ampliamente utilizado para la investigación. procesos de producción, estructuras organizativas, procesos de programación, etc. Por ejemplo, para analizar la eficiencia del uso de equipos de producción, se construyen gráficos de cálculo, incluidos gráficos de múltiples factores.
Notación: cada círculo se considera uno de los vértices del gráfico; el número en el sector superior de cada vértice significa su número de serie; A partir de los números de dos vértices adyacentes se forma el código de trabajo; la figura en el sector inferior de cada vértice es número de serie vértice anterior, y la línea que conecta estos dos vértices significa cierto trabajo. Debajo de la línea se encuentra la duración prevista de este trabajo; el número en el sector izquierdo de cada vértice significa la duración total de todo el trabajo anterior, el número en el sector derecho difiere del número de la izquierda en la cantidad de reserva (reserva de tiempo). Por lo tanto, para los vértices que se encuentran en el camino crítico, los números en los sectores izquierdo y derecho del vértice coinciden, ya que el margen de tiempo es 0.
En un sistema matemáticamente formalizado de análisis, planificación y gestión, los diagramas de red ocupan un lugar especial. Proporcionan un gran efecto económico en la construcción e instalación de empresas industriales y de otro tipo.
El diagrama de red (Fig. 6.1) permite identificar las más importantes de todo el complejo de obras, las que se encuentran en la ruta crítica, y concentrar en ellas los principales recursos de las organizaciones constructoras, establecer relaciones entre diversas organizaciones especializadas y coordinar sus trabajar. Las actividades en la ruta crítica requieren la espera más larga hasta que llegue el siguiente evento. En la etapa de análisis y gestión operativa, el cronograma de la red permite monitorear efectivamente el avance de la construcción y tomar medidas oportunas para eliminar posibles retrasos en el trabajo.
Solicitud graficos de red El análisis, la planificación y la gestión proporcionan, como muestran muchos ejemplos, una reducción del tiempo de construcción entre un 20% y un 30% y un aumento de la productividad laboral entre un 15% y un 20%.
En los análisis realizados directamente en las obras, el uso de materiales planificación de red y la gestión contribuye a la correcta identificación de los motivos que afectan el avance de la construcción y a la identificación de empresas que no aseguran la finalización de los trabajos que les son encomendados o la entrega de los equipos dentro de los plazos establecidos por el cronograma.
El desarrollo de un cronograma de red en construcción se lleva a cabo en presencia de: estándares para la duración de la construcción y el período de puesta en servicio de un objeto o conjunto de objetos, documentación de diseño y estimación, un proyecto para organizar la construcción y producción del trabajo, estándar mapas tecnológicos, estándares actuales para costos de mano de obra, materiales y operación de máquinas. Además, a la hora de elaborar el cronograma se aprovecha la experiencia en implementación. obras individuales, así como datos sobre la base de producción de las organizaciones de construcción e instalación.
A partir de todos estos datos se elabora una tabla de trabajos y recursos, donde en la secuencia tecnológica de producción del trabajo sus características, volumen, intensidad de mano de obra en días-hombre, ejecutante (organización y equipo), número de trabajadores, turnos, necesidad de Se indican los mecanismos y materiales, las fuentes de su suministro, la duración total del trabajo en días, así como la tarea anterior, tras la cual se puede comenzar. este trabajo. A partir de los indicadores de dicha tabla, se prepara un diagrama de red, que puede tener distintos grados de detalle según el esquema de producción adoptado.
gestión del trabajo y nivel de gestión; excepto horario general Los artistas desarrollan un cronograma para el trabajo que realizan.
Los principales elementos de un diagrama de red: evento, trabajo, espera, dependencia.
Al analizar el progreso de la construcción de una instalación, es necesario establecer si el cronograma de la red se ha elaborado correctamente, si no se ha sobreestimado el camino crítico, si se han tenido en cuenta todas las posibilidades para reducirlo al optimizar el cronograma, si cualquier trabajo se puede realizar en paralelo o se puede reducir el tiempo dedicado a ellos aumentando los medios de mecanización, etc. Esto es especialmente importante en los casos en que la duración del trabajo según el cronograma no garantiza la finalización de la construcción a tiempo.
El principal material para la planificación de la red utilizado en el análisis es información sobre el avance del trabajo según el cronograma, que generalmente se elabora al menos una vez por década. Como ejemplo, se proporciona un mapa de la tarea e información sobre el progreso del trabajo en un proyecto de construcción realizado de acuerdo con el cronograma de la red (Tabla 6.1). Según el mapa, el trabajo crítico se llevó a cabo a principios de mes antes de lo previsto, pero luego se permitió que se retrasara la instalación de las vigas de la grúa a lo largo de la fila B y se completó el trabajo posterior: la instalación de las vigas de la grúa a lo largo de la fila A. un día de retraso.
La optimización de los cronogramas de la red se lleva a cabo en la etapa de planificación reduciendo la ruta crítica, es decir, minimizando los tiempos de finalización. trabajo de construcción en niveles dados recursos, minimizando el nivel de consumo de materiales, mano de obra y recursos financieros con plazos fijos para la finalización de los trabajos de construcción. También es posible un enfoque mixto: para una parte del trabajo (más caro), minimizar el nivel de consumo de recursos con un plazo fijo para completar el trabajo, para la otra, minimizar el plazo para un nivel fijo de recursos.
La resolución de problemas de optimización se ve facilitada enormemente por la disponibilidad de paquetes. programas de aplicación(PPP), adaptado para compilar diagramas de red óptimos en una computadora.
En la práctica extranjera del análisis de sistemas, es común un método grafomatemático llamado "árbol de decisión". La esencia de este método es la siguiente.
Por Una revisión preliminar necesidades, un análisis preliminar de las posibles condiciones organizativas, técnicas o tecnológicas, se describen todas las opciones posibles para solucionar este problema. Primero desarrollado
| | Ejercicio | | Información | Reserva de tiempo para el trabajo. | Número ty |
|||||||
| Nombre obras | cifrar | fecha comenzó | fecha despues de terminar | planificado continuado | Re reservar tiempo | % aquellos- | tiempo requerido para | en rango | fecha actual | hallazgo actual | no ubicado | reservar tiempo con |
| | obras | obras (plan) | nia obras (plan) | habitante ness, días | a mí | Vaya listo ness | despues de terminar nia obras, días | zader mujer | despues de terminar nia obras | en el camino crítico | un camino crítico | inicio de mes, días |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Desarrollo del suelo | 1-2 | 1/IV | 6/IV | 5 | 0 | 100 | - | - | 6/IV | ¦- | - | - |
| Hormigonado de cimientos para calderas. | 2-3 | 7/IV | 17/1V | 9 | 0 | 100 | 14/IV | 2 | 2 |
|||
| Hormigonado de cimentaciones según fila A. | 2-4 | 7/IV | 14/1V | 7 | 2 | 100 | 14/IV | | | |
||
| Lo mismo para la fila B | 2-5 | 7/IV | 14/IV | 7 | 2 | 100 | - | - | 14/IV | | | |
| Dispositivo de distribución de tuberías | 6-18 | 18/IV | 21/IV | 4 | 19 | 100 | - | - | 29/IV | -7 |
||
| Dispositivo de relleno | 6-7 | 18/IV | 19/IV | 2 | 0 | 100 | 17/IV | 2 | 2 |
|||
| Instalación de estructuras prefabricadas de hormigón. | | | | | | | | | | | | |
| lonn: a lo largo de la fila B | 7-8 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | _ | - | - |
| a lo largo de la fila A | 7-9 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | - | - | - |
Construcción de vías de grúa e instalación de grúa torre 7-10
Instalación de marcos de soporte en la base para equipos 7-16 Instalación de vigas de grúa:
a lo largo de la fila B 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2
a lo largo de la fila A 10-12 25/IV 26/IV
Instalación de la primera parte de vigas y losas de recubrimiento 12-13 27/IV 4/V
Instalación de vías de grúa para puente lt;3 grúas 12-14 27/IV 3/V
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 0 | 100 | - | - | 22/IV | 1 | - | 1 |
| 14 | 100. | - | - | 29/IV | - | -5 | - |
| 1 | 100 | detrás- | 27/IV | -2 |
27/IV -1
apoyo con suministro de estructuras de hormigón armado
- 100 -
opciones ampliadas. Luego, al presentar condiciones adicionales cada uno de ellos se divide en una serie de opciones. Imagen gráfica de estas opciones le permite excluir las menos rentables y elegir la más aceptable.
Este método se puede utilizar para determinar el orden de procesamiento de determinadas piezas en varias máquinas para minimizar el tiempo total de procesamiento; al establecer el tamaño de los recursos para minimizar los costos generales de producción; al distribuir inversiones de capital y otros recursos entre instalaciones industriales; al resolver problemas de transporte y otros.
La solución se produce en tres etapas:
- Transición a KZLP. Cualquier LLP de la forma ax ≤ b , ax ≥ b , ax = b (F(X) → extr) se reduce a la forma ax = b , F(X) → max ;
- Transición a SZLP. Un CLLP de la forma ax = b se reduce a la forma ax ≤ b, F(X) → max;
- Solución mediante el método simplex;
Instrucciones. Seleccione el número de variables y el número de filas (número de restricciones). La solución resultante se guarda en un archivo de Word.
Transición del problema de minimización de la función objetivo al problema de maximización
El problema de minimizar la función objetivo F(X) se puede reducir fácilmente al problema de maximizar la función F*(X) bajo las mismas restricciones introduciendo la función: F*(X) = -F(X) . Ambos problemas tienen la misma solución X*, y al mismo tiempo min(F(X)) = -max(F*(X)) .Ilustremos este hecho gráficamente:
| F(x) → mín. |
F(x) → máx.  |
plano base– un plan con variables básicas definidas a través de libertad.
plan basico– plan de referencia con cero variables básicas.
plan optimo– un plan básico que satisfaga función óptima goles (FC).
Elemento principal (resolutivo) es el coeficiente de la incógnita libre, que se convierte en el básico, y el coeficiente mismo se convierte a la unidad.
Guía– la línea del elemento principal, en la que se encuentra la incógnita básica con un coeficiente unitario, excluida durante la transformación (línea con el coeficiente límite mínimo, ver más abajo).
Columna guía– columna del elemento principal, cuya incógnita libre se convierte en la básica (columna con beneficio máximo, vea abajo).
Las variables x 1, …, x m, incluidas con coeficientes unitarios en una sola ecuación del sistema, con coeficientes cero en el resto, se denominan básico o dependiente. EN sistema canónico Cada ecuación tiene exactamente una variable base. La transición se realiza mediante el método de Gauss-Jordan. La idea principal de este método es reducir un sistema de m ecuaciones con n incógnitas a forma canónica usando operaciones elementales en cuerdas.
Descansar variables n-m(x m +1 ,…, x n) se llaman no básico o variables independientes.
Solución básica llamado solución básica admisible, si los valores de las variables básicas incluidas en él x j ≥0, lo que equivale a la condición de no negatividad b j ≥0.
Una solución base factible es punto de esquina conjunto admisible S problemas de programación lineal y a veces se les llama plan de referencia.
Si entre los números no negativos b j hay cero, entonces la solución básica admisible se llama degenerar(punto de esquina degenerado) y el problema de programación lineal correspondiente se llama degenerar.
Ejemplo No. 1. Reducir el problema de programación lineal a un ZLP estándar.
F(X) = x 1 + 2x 2 - 2x 3 → min con restricciones:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x1 + 2x3 =9
Para trayendo PAP a la forma canónica es necesario:
1. Cambie el signo de la función objetivo. Reduzcamos el problema F(X) → min al problema F(X) → max. Para hacer esto, multiplique F(X) por (-1). En la primera desigualdad de significado (≤), introducimos la variable básica x 4 ; en la segunda desigualdad de significado (≥), introducimos la variable básica x 5 con un signo menos.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Transición a SZLP.
Matriz extendida del sistema de restricciones de igualdad para este problema:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Reduzcamos el sistema a la matriz identidad utilizando el método de transformación de Jordan.
1. Puedes elegir x 4 como variable base.
2. Elegimos x 2 como variable base.
Elemento de resolución RE=-2. La recta correspondiente a la variable x 2 se obtiene dividiendo todos los elementos de la recta x 2 por el elemento resolutivo RE = -2. En lugar del elemento de resolución obtenemos 1. En las celdas restantes de la columna x 2 escribimos ceros. Todos los demás elementos están determinados por la regla del rectángulo. Presentemos el cálculo de cada elemento en forma de tabla:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
Obtenemos una nueva matriz:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. Elegimos x 3 como variable base.
Elemento de resolución RE=2. La recta correspondiente a la variable x 3 se obtiene dividiendo todos los elementos de la recta x 3 por el elemento resolutivo RE=2. En lugar del elemento de resolución obtenemos 1. En las celdas restantes de la columna x 3 escribimos ceros. Todos los demás elementos están determinados por la regla del rectángulo. Presentemos el cálculo de cada elemento en forma de tabla:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
Obtenemos una nueva matriz:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Dado que el sistema tiene matriz de identidad, entonces tomamos X = (4,2,3) como variables básicas.
Las ecuaciones correspondientes son:
3/4 x 1 + x 4 - 1 1/2 x 5 = -14 3/4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
Expresemos las variables básicas en términos del resto:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1 / 2 x 1 +4 1 / 2
Sustituyémoslos en función objetivo:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
o
Sistema de desigualdades:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 x 1 +4 1/2 ≥ 0
Reducimos el sistema de desigualdades a siguiente vista:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 5 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → máx.
Simplifiquemos el sistema.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 2 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → máx.
Ejemplo No. 2. Primero se encuentra la solución al problema utilizando el método gráfico y luego el método símplex.
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) con restricciones:
-3x 1 + x 2 + x 3 = 3
4x 1 + 2x 2 - x 4 = 12
2x 1 - x 2 + x 5 = 2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
La programación lineal utiliza un método gráfico para determinar conjuntos convexos (poliedro solución). Si el principal problema de programación lineal tiene plan optimo, entonces la función objetivo toma un valor en uno de los vértices del poliedro solución (ver figura).
Objeto del servicio. Mediante el uso de este servicio posible en modo en línea resolver el problema de programación lineal utilizando el método geométrico, y también obtener una solución al problema dual (evaluar el uso óptimo de los recursos). Además, se crea una plantilla de solución en Excel.
Instrucciones. Seleccione el número de filas (número de restricciones).
Si el número de variables es más de dos, es necesario llevar el sistema al SZLP (ver ejemplo y ejemplo No. 2). Si la restricción es doble, por ejemplo, 1 ≤ x 1 ≤ 4, entonces se divide en dos: x 1 ≥ 1, x 1 ≤ 4 (es decir, el número de filas aumenta en 1).También puede crear un área de solución factible (ADA) utilizando este servicio.
Lo siguiente también se utiliza con esta calculadora:
Método simplex para resolver ZLP
Solución del problema del transporte.
Resolver un juego de matrices
Usando el servicio en línea, puede determinar el precio de un juego de matriz (límites inferior y superior), verificar 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.
Cálculo de límites
Resolver un problema de programación lineal por método gráfico incluye los siguientes pasos:
- Las rectas se construyen en el plano X 1 0X 2.
- Se determinan los semiplanos.
- Definir un polígono de solución;
- Se construye un vector N(c 1 ,c 2), que indica la dirección de la función objetivo;
- Avanzar función objetivo c 1 x 2 + c 2 x 2= 0 en la dirección del vector N hasta el punto extremo del polígono solución.
- Se calculan las coordenadas del punto y el valor de la función objetivo en este punto.
Ejemplo. La empresa produce dos tipos de productos: P1 y P2. Para la producción de productos se utilizan dos tipos de materias primas: C1 y C2. Precios al por mayor unidad de producción es igual a: 5 unidades. para P1 y 4 unidades para P2. El consumo de materias primas por unidad de producto de tipo P1 y tipo P2 se indica en la tabla.
Tabla - Consumo de materias primas para la producción.
Necesitas determinar:
¿Cuántos productos de cada tipo debería producir la empresa para maximizar los ingresos por la venta de productos?
- Formular modelo matemático Problemas de programación lineal.
- Resolver un problema de programación lineal. gráficamente(para dos variables).
Formulemos un modelo matemático del problema de programación lineal.
x 1 - producción de productos P1, unidades.
x 2 - producción de productos P2, unidades.
x1, x2 ≥ 0
Límites de recursos
6x1 + 4x2 ≤ 24
x 1 + 2 x 2 ≤ 6
Restricciones de demanda
x 1 +1 ≥ x 2
x 2 ≤ 2
Función objetiva
5x 1 + 4x 2 → máx.
Luego obtenemos el siguiente PLP:
6x1 + 4x2 ≤ 24
x 1 + 2 x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x1, x2 ≥ 0
5x 1 + 4x 2 → máx.
Método gráfico Decisiones de APP se basa en las declaraciones dadas en el párrafo 2.1. Según el teorema 2, solucion optima está en la parte superior de la región de soluciones admisibles y, por lo tanto, resuelve el ZLP: encuentre la parte superior de la región de soluciones admisibles, cuyas coordenadas dan valor optimo función objetivo.
El método gráfico se utiliza para resolver una clase limitada de problemas con dos variables, a veces con tres variables. Cabe señalar que para tres variables esta área no está lo suficientemente clara.
Algoritmo para el método gráfico de resolución de problemas.
Consideraremos la implementación del método gráfico para resolver el ZLP usando ejemplos.
Ejemplo 2.2.1. Resuelva gráficamente el ZLP:
(2.2.1)
máximo z=X 1 + 4X 2 (2.2.2)
Solución. Para construir una región de soluciones factibles, que consiste en la intersección de semiplanos correspondientes a cada desigualdad del sistema de restricciones (2.2.1), escribimos las ecuaciones de las rectas límite:
yo 1: X 1 + 5X 2 = 5; yo 2: X 1 + X 2 = 6; yo 3: 7X 1 + X 2 = 7.
yo 1 a la forma (2.2.3.) dividimos ambas partes entre 5: 
. Así, directamente yo 1 cortes en el eje Oh 1 5 unidades, en el eje Oh 2 1 unidad. De manera similar tenemos para yo 2:
Y yo 3:
.
Para determinar semiplanos que cumplan las restricciones del sistema (2.2.1), es necesario sustituir en las restricciones las coordenadas de cualquier punto que no se encuentre en la línea límite. Si obtenemos una desigualdad verdadera, entonces todos los puntos de este semiplano son soluciones a esta desigualdad. De lo contrario, elija otro semiplano.
Por lo tanto, el primer y segundo semiplano deseado están ubicados en la dirección opuesta al origen de coordenadas (0 – 5 0 
- 5; 7 0 + 0 
7), y el segundo – hacia el origen de coordenadas (0 + 0 
6). La región de soluciones factibles en la Figura 2.2.1 está sombreada.
Figura 2.2.1 – Área de soluciones factibles
Para encontrar el plano óptimo, que se ubicará en el vértice del polígono de solución, es necesario construir un vector de direcciones. 
=(Con 1 ,Con 2), que indica la dirección del mayor aumento en la función objetivo z=Con 1 X 1 +Con 2 X 2 .
En este problema, el vector de dirección 
= (1, 4): comienza en el punto ACERCA DE(0,0) y termina en el punto norte(1, 4).
A continuación, construimos una línea recta que pasa por la región de soluciones factibles, perpendicular al vector, y se llama línea de nivel objetivo funciones. Movemos la línea de nivel en la dirección del vector en caso de maximizar la función objetivo z y en sentido contrario, en el caso de la minimización z, hasta la última intersección con la región de soluciones factibles. Como resultado, se determina el punto o puntos donde la función objetivo alcanza un valor extremo, o se establece la ilimitación de la función objetivo. z sobre el conjunto de soluciones al problema.
Por tanto, el punto máximo de la función objetivo z es el punto A intersecciones de líneas yo 2 y yo 3 .
Calcular el valor óptimo de la función objetivo. z encontrar las coordenadas del punto A . Desde el punto A es el punto de intersección de las rectas yo 2 y yo 3, entonces sus coordenadas satisfacen un sistema de ecuaciones compuesto por las ecuaciones de las líneas límite correspondientes:
Entonces el punto A tiene coordenadas X 1 =1/6, X 2 = 35/6.
Para calcular el valor óptimo de la función objetivo, debe sustituir las coordenadas del punto en ella. A .
Sustituyendo las coordenadas del punto. A en la función objetivo (2.4), obtenemos
máximo z = 1/6 + 4·(35/6) = 47/2.
Ejemplo 2.2.2. Construya en el plano la región de soluciones factibles del sistema de desigualdades lineales (2.2.4) y encuentre los valores mayor y menor de la función objetivo (2.2.5):
(2.2.4)
z= –2X 1 –X 2 (2.2.5)
Solución. Para construir una región de soluciones factibles, que consiste en la intersección de semiplanos correspondientes a cada desigualdad del sistema de restricciones (2.2.4), escribimos las ecuaciones de las rectas límite:
yo 1: 4X 1 – X 2 = 0; yo 2: X 1 + 3X 2 = 6; yo 3: X 1 – 3X 2 = 6; yo 4: X 2 = 1.
Derecho yo 1 pasa por el punto de coordenadas (0;0). Para construirlo expresamos X 2 a través de X 1: X 2 = 4X 1 . Busquemos otro punto por donde pasa la recta. yo 1, por ejemplo (1;4). Por el punto de coordenadas (0;0) y el punto de coordenadas (1;4) trazamos una recta yo 1 .
Reducir la ecuación de una recta. yo 2 a la forma en segmentos sobre los ejes (2.2.3), dividimos ambas partes entre 6: 
. Así, directamente yo 2 cortes en eje Oh 1 6 unidades, en el eje Oh 2 - 2 unidades. De manera similar tenemos para yo 3:
y directo yo 4 paralelo al eje Oh 1 y pasa por el punto de coordenadas (0;1) .
Para determinar semiplanos que cumplan las restricciones del sistema (2.2.4), es necesario sustituir en las restricciones las coordenadas de cualquier punto que no se encuentre en la línea límite. Debido a restriccionesX 1 
0,
X 2 
0, la región de soluciones admisibles del ZLP se encuentra en el primer cuarto del plano de coordenadas.
ACERCA DE 
el área de soluciones factibles en la Figura 2.2.2 está sombreada.
Figura 2.2.2 – Área de soluciones factibles
Construyamos un vector de direcciones. 
= (–2,–1). A continuación, construimos una línea de nivel perpendicular al vector. .
Encontrar valor más alto de la función objetivo, movemos la línea de nivel en la dirección del vector hasta la última intersección con la región de soluciones factibles. Por tanto, el punto máximo de la función objetivo z es el punto A(intersección de líneas yo 1 y yo 2).
Calcular el valor óptimo de la función objetivo. z encontrar las coordenadas del punto A. Desde el punto A es el punto de intersección de las rectas yo 1 y yo 2, entonces sus coordenadas satisfacen un sistema de ecuaciones compuesto por las ecuaciones de las líneas límite correspondientes:
Entonces el punto A tiene coordenadas X 1 =6/13, X 2 = 24/13.
Sustituyendo las coordenadas del punto. A en la función objetivo (2.2.5), obtenemos el valor óptimo de la función objetivo
máximo z= – 2·(6/13) – (24/13) = – 36/13.
Encontrar valor más bajo de la función objetivo, movemos la línea de nivel en la dirección opuesta al vector hasta la última intersección con la región de soluciones factibles. En este caso, la función objetivo es ilimitada en la región de soluciones factibles, es decir ZLP no tiene mínimo.
Como resultado de la decisión del PPP, son posibles los siguientes casos:
La función objetivo alcanza su valor óptimo en un único vértice del polígono solución;
La función objetivo alcanza su valor óptimo en cualquier punto del borde del polígono de solución (el ZLP tiene alternativas planos de referencia con los mismos valores z );
El PAP no tiene planes óptimos;
ZLP tiene un plan óptimo en el caso de una gama ilimitada de soluciones factibles.
En esta lección nos familiarizaremos con el método de solución gráfica. problemas de programación lineal, es decir, aquellos problemas en los que se requiere encontrar una solución a un sistema de ecuaciones lineales y (o) desigualdades (sistema de restricciones) en los que la función objetivo, una función lineal, adquiere el valor óptimo.
Debido al hecho de que la visibilidad solución gráfica se logra sólo en un avión, podemos familiarizarnos con representación grafica problemas sólo en un espacio bidimensional. Esta representación es adecuada para un sistema de restricciones de desigualdad con dos variables o para sistemas de ecuaciones en los que el número de variables excede al número de ecuaciones en 2, es decir, el número de variables libres es dos.
Por lo tanto, el método gráfico tiene un ámbito de aplicación tan limitado que no se puede hablar de él como un método especial para resolver problemas de programación lineal.
Sin embargo, para producir representaciones visuales Para resolver problemas de programación lineal, el método gráfico resulta de cierto interés. Además, nos permite confirmar geométricamente la validez. teoremas de programación lineal .
Fundamentos teóricos del método gráfico.
Entonces, un problema de programación lineal. Se requiere encontrar valores no negativos de las variables y que satisfagan el sistema de desigualdades.
en el que la forma lineal adquiere el valor óptimo.
Ejemplo 3.
Ejemplo 4. Resuelve un problema de programación lineal usando un método gráfico en el que necesitas encontrar el mínimo de una función bajo restricciones.
Seguimos resolviendo problemas usando el método gráfico juntos.
Las conclusiones alcanzadas hasta el momento se han basado en el hecho de que el conjunto de soluciones de un problema de programación lineal está configurado de manera que la solución óptima es finita y única. Ahora veamos ejemplos en los que se viola esta condición. En estos ejemplos, el polígono de solución se construye como se muestra en los ejemplos anteriores. Detengámonos en las características que distinguen estos ejemplos excepcionales.
Ejemplo 5. Resuelve un problema de programación lineal usando un método gráfico, en el que necesitas encontrar el máximo de una función bajo restricciones.
Solución. La figura muestra: un área de solución poliédrica ilimitada para este sistema de restricciones, una línea de nivel inicial (negra), un vector (color burdeos) que indica la dirección de movimiento de la línea de nivel inicial para encontrar el máximo de la función objetivo.
Es fácil ver que la función F puede aumentar sin límite con sistema dado restricciones, por lo que podemos escribir eso condicionalmente.
Ejemplo 6. Resuelve un problema de programación lineal usando un método gráfico, en el que necesitas encontrar el máximo de una función bajo restricciones.
