Ejemplo de programación lineal. Transición del problema de minimización de la función objetivo al problema de maximización

Este método es un método para enumerar intencionalmente soluciones de referencia al problema. 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:

1. Indique un método para encontrar la solución de referencia óptima.
2. Indique el método de transición de una solución de referencia a otra, en el que el valor función objetivo estará más cerca de lo óptimo, es decir indicar una forma de mejorar la solución de referencia
3. 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 un problema usando el método simplex, debes hacer lo siguiente:

1. Lleva la tarea a forma canónica
2. 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)
3. Calcule estimaciones de descomposiciones vectoriales basadas en la solución de referencia y complete la tabla del método simplex
4. Si se cumple el criterio de unicidad de la solución óptima, entonces la solución del problema termina
5. 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 en lado izquierdo Para la primera restricción de desigualdad, introducimos una variable adicional x 6 con un coeficiente de +1. 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. 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 se escriben 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). El uso de este método en el análisis económico permite resolver problemas relacionados principalmente con la planificación de las actividades de una 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.

Una solución muy común es la llamada problema de transporte utilizando 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 restricciones existentes con respecto al número de vehículos, su capacidad de carga, la duración de su operación y si existe 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 lineal, 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 restricciones de desigualdad 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. De este modo, 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.

La modelización matemática en la investigación de operaciones es, por un lado, un proceso muy importante y complejo, y por otro, un proceso prácticamente imposible de formalizar científicamente. Tenga en cuenta que se han realizado repetidos intentos para identificar principios generales la creación de modelos matemáticos condujo a la declaración de recomendaciones de carácter muy general, difíciles de aplicar para resolver problemas específicos o, por el contrario, a la aparición de recetas que en realidad sólo son aplicables a una gama reducida de tareas. Por tanto, parece más útil familiarizarse con la técnica de modelización matemática utilizando ejemplos concretos.

Los problemas de programación lineal se pueden resolver mediante los siguientes métodos:

algoritmo de Floyd;

Algoritmo de Dijkstra sobre gráficos;

método gráfico;

método de tabla simplex, etc.

Algoritmo para la resolución de problemas de programación lineal utilizando el método de Dijkstra en gráficos.

En la implementación más simple, se puede usar una matriz de números para almacenar números d[i], y se puede usar una matriz de variables booleanas para almacenar la membresía de un elemento en el conjunto U.

Al comienzo del algoritmo, la distancia para el vértice inicial se establece en cero y todas las demás distancias se rellenan con un número positivo grande (mayor que el máximo camino posible en el gráfico). La matriz de banderas está llena de ceros. Entonces comienza el bucle principal.

En cada paso del ciclo es necesario encontrar un vértice U con una distancia mínima y una bandera igual a cero. Luego debe establecer la bandera en 1 y verificar todos los vértices U adyacentes a ella. Si la distancia es mayor que la suma de la distancia al vértice actual y la longitud del borde, entonces debe reducirla. El ciclo termina cuando las banderas de todos los vértices se vuelven iguales a 1, o cuando todos los vértices tienen una bandera de 0. El último caso es posible si y sólo si el gráfico G no es conexo.

Método para resolver problemas de programación lineal. método gráfico.

El método gráfico para resolver un problema de programación lineal se basa en la interpretación geométrica de un problema de programación lineal y se utiliza principalmente para resolver problemas en un espacio bidimensional y solo algunos problemas en un espacio tridimensional, ya que es bastante difícil construir un Poliedro solución que se forma como resultado de la intersección de semiespacios. Generalmente es imposible representar gráficamente un problema en un espacio de dimensiones mayores a tres.

Sea el problema de programación lineal especificado en un espacio bidimensional, es decir, las restricciones contienen dos variables.

El valor mínimo de la función está determinado por la fórmula (1).

(1)

Las restricciones están representadas por las fórmulas (2) y (3).

(2)

(3)

Sea consistente el sistema (2) bajo la condición (3). Cada una de las desigualdades de los sistemas (2) y (3) define un semiplano con líneas límite representadas por la fórmula (4):

La función lineal (1) para valores fijos de Z es la ecuación de una recta:

Es necesario construir un polígono de soluciones al sistema de restricciones (2) y la gráfica de la función lineal (1) en Z=0. Entonces al problema de programación lineal planteado se le puede dar la siguiente interpretación:

Encuentre el punto del polígono solución en el que la línea
la referencia y la función Z alcanza un mínimo.

Valores
disminución en la dirección del vector
, por lo tanto la recta Z=0 debe moverse paralela a sí misma en la dirección del vector N.

Si el polígono solución está acotado, entonces la línea recta se convierte en una línea de soporte dos veces con respecto al polígono solución (en los puntos B y E), y valor mínimo toma en el punto E. Coordenadas del punto
debe encontrarse resolviendo el sistema de ecuaciones de las rectas DE y EF.

Si el polígono solución es un área poligonal ilimitada, entonces son posibles dos casos.

Caso 1. Directo
, moviéndose en la dirección del vector N o en dirección opuesta a él, interseca constantemente el polígono solución y no es un punto de referencia para él en ningún punto. En este caso, la función lineal no está limitada por el polígono solución ni desde arriba ni desde abajo.

Caso 2. La línea recta, mientras se mueve, se convierte en un soporte con respecto al polígono de solución. Luego, dependiendo del tipo de dominio, una función lineal puede estar acotada desde arriba y no acotada desde abajo, acotada desde abajo y no acotada desde arriba, o acotada tanto desde abajo como desde arriba.

Para solucionar este problema se optó por el método simplex, el más conocido y utilizado en la práctica para la resolución de problemas de programación lineal. A pesar de que el método simplex es un algoritmo bastante eficaz que ha mostrado buenos resultados en la resolución de problemas de programación lineal aplicada, es un algoritmo de complejidad exponencial.

El método simplex de problemas de programación lineal se basa en la transición de un plan de referencia a otro, en el que el valor de la función objetivo aumenta o disminuye.

Antes de compilar una tabla simplex, se debe transformar el problema, llevar el sistema de restricciones a una forma básica aceptable, con la ayuda de la cual se deben excluir las variables básicas de la función objetivo como se muestra en la Figura 1.

Figura 1 – Transformación inicial del sistema de restricciones

Aquí, para mayor precisión de la notación, se supone que las variables X1, X2, ..., Xr pueden tomarse como variables básicas y que b1, b2,..., br ≥ 0 (la solución básica correspondiente es la referencia uno).

Para compilar una tabla simplex en todas las igualdades en el planteamiento del problema, los términos que contienen variables se transfieren al lado izquierdo, los libres se dejan al lado derecho, es decir, el problema está escrito en forma de un sistema de igualdades como se muestra en la Figura 2.

Figura 2 – Transformación del sistema de desigualdades

El algoritmo para pasar a la siguiente tabla es el siguiente:

Se revisa la última fila (índice) de la tabla y entre los coeficientes de esta fila (excluyendo la columna de términos libres) se selecciona el número negativo más pequeño al encontrar el máximo, o el positivo más grande al buscar el mínimo. Si no hay ninguna, entonces la solución básica original es óptima y esta tabla es la última;

Se revisa la columna de la tabla correspondiente al coeficiente negativo (positivo) seleccionado en la última fila: la columna clave, y en esta columna se seleccionan los coeficientes positivos.

Si no las hay, entonces la función objetivo es ilimitada en el rango de valores permisibles de las variables y el problema no tiene solución;

Entre los coeficientes seleccionados de la columna, se selecciona aquel para el cual el valor absoluto de la relación entre el término libre correspondiente (ubicado en la columna de términos libres) y este elemento es mínimo. Este coeficiente se llama coeficiente resolutivo y la línea en la que se ubica es clave;

en el futuro, la variable básica correspondiente a la fila del elemento resolutivo debe transferirse a la categoría de libre, y la variable libre correspondiente a la columna del elemento resolutivo debe ingresarse al número de básicos.

Se construye una nueva tabla que contiene los nuevos nombres de las variables básicas:

Dividamos cada elemento de la línea clave (excluyendo la columna de términos libres) en un elemento de resolución y escribamos los valores resultantes en la línea con la variable básica modificada de la nueva tabla simplex.

la cadena del elemento permitido se divide por este elemento y la cadena resultante se escribe en una nueva tabla en el mismo lugar.

en la nueva tabla, todos los elementos de la columna clave = 0, excepto la columna de corte, que siempre es igual a 1.

una columna que tiene un 0 en su fila clave será la misma en la nueva tabla. una fila que tiene un 0 en su columna clave será la misma en la nueva tabla. a otras células

Figura 3: Compilación de un nuevo elemento en una tabla simplex

Como resultado se obtiene una nueva tabla simplex que corresponde a la nueva solución básica.

Ahora debes fijarte en la línea de la función objetivo (índice), si no contiene valores negativos (en el problema de encontrar el valor máximo) o valores positivos (en el problema de encontrar el valor mínimo) excepto para el que está parado (columna libre), entonces significa que se recibió la solución óptima. De lo contrario, pasamos a una nueva tabla simplex usando el algoritmo descrito anteriormente.

Para resolver el problema de este trabajo de curso, se eligió la dirección del problema para la distribución óptima de fondos en la empresa. El plan óptimo o la solución óptima a un problema de programación lineal es un plan en el que el valor objetivo aumentará (disminuirá).

Después de analizar la información recopilada, se compiló un problema de programación lineal para el taller número 8 de NefAZ OJSC sobre el transportador de pintura sobre el que se pintan las piezas. Es necesario pintar la cantidad óptima de piezas en un turno de trabajo para maximizar las ganancias.

Para resolver aún más el problema, es necesario crear un enunciado del problema y un modelo matemático del problema.

Objeto del servicio. La calculadora en línea está diseñada para resolver problemas de programación lineal utilizando el método simplex yendo a KZLP Y SZLP. En este caso, el problema de encontrar el mínimo de la función objetivo se reduce al problema de encontrar el máximo mediante la transformación de la función objetivo F*(X) = -F(X) . También es posible crear un problema dual.

La solución se produce en tres etapas:

1. 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 ;
2. Transición a SZLP. Un CLLP de la forma ax = b se reduce a la forma ax ≤ b, F(X) → max;
3. 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.

Número de variables 2 3 4 5 6 7 8 9 10
Número de filas (número de restricciones) 1 2 3 4 5 6 7 8 9 10

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.

Para optimizar la función objetivo utilizamos los siguientes conceptos y métodos.
plano base– un plan con variables básicas definidas a través de libertad.
plan básico – 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.
línea 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 una forma canónica utilizando operaciones elementales en cadenas.
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 la 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 es una rama de la programación matemática que estudia métodos para resolver problemas extremos que se caracterizan por una relación lineal entre variables y un criterio lineal. Estos problemas encuentran amplias aplicaciones en diversos campos de la actividad humana. El estudio sistemático de problemas de este tipo comenzó en 1939-1940. en las obras de L.V. Kantorovich.

Los problemas matemáticos de programación lineal incluyen estudios de situaciones económicas y de producción específicas, que de una forma u otra se interpretan como problemas sobre el uso óptimo de recursos limitados.

La gama de problemas que se resuelven mediante métodos de programación lineal es bastante amplia. Estos son, por ejemplo:

problema sobre uso optimo recursos para la planificación de la producción;

problema de mezcla (planificación de la composición del producto);

el problema de encontrar la combinación óptima de diferentes tipos de productos para el almacenamiento en almacenes (gestión de inventarios o);

Tareas de transporte (análisis de ubicación de la empresa, movimiento de mercancías).

La programación lineal es la sección más desarrollada y utilizada de la programación matemática (además, esto incluye: programación entera, dinámica, no lineal y paramétrica). Esto se explica a continuación:

modelos matemáticos gran número los problemas económicos son lineales con respecto a las variables requeridas;

Este tipo de problema es actualmente el más estudiado. Para ello se han desarrollado métodos especiales con los que se resuelven estos problemas y los correspondientes programas informáticos;

muchos problemas de programación lineal, una vez resueltos, han encontrado una amplia aplicación;

algunos problemas, que en la formulación original no son lineales, después de una serie restricciones adicionales y los supuestos pueden volverse lineales o reducirse a una forma tal que puedan resolverse mediante métodos de programación lineal.

El modelo económico y matemático de cualquier problema de programación lineal incluye: una función objetivo, valor optimo cuál (máximo o mínimo) debe encontrarse; restricciones en forma de sistema de ecuaciones lineales o desigualdades; requisito de no negatividad de las variables.

En general, el modelo se escribe de la siguiente manera:

función objetivo

(1.1) con restricciones

(1.2) requisitos de no negatividad

(1.3) donde incógnita j– variables (desconocidas);

- coeficientes del problema de programación lineal.

El problema es encontrar el valor óptimo de la función (1.1) sujeto a las restricciones (1.2) y (1.3).

El sistema de restricciones (1.2) se denomina restricciones funcionales del problema y las restricciones (1.3) se denominan directas.

Un vector que satisface las restricciones (1.2) y (1.3) se denomina solución (plan) admisible de un problema de programación lineal. El plan bajo el cual la función (1.1) alcanza su valor máximo (mínimo) se llama óptimo.

1.2. Método simplex para resolver problemas de programación lineal.

El método simplex fue desarrollado y utilizado por primera vez para resolver problemas en 1947 por el matemático estadounidense J. Danzig.

Los problemas de programación lineal bidimensional se resuelven gráficamente. Para el caso N=3, podemos considerar un espacio tridimensional y la función objetivo alcanzará su valor óptimo en uno de los vértices del poliedro.

Una solución admisible (plan admisible) del problema de LP dada en formulario estándar, es un conjunto ordenado de números (x1, x2, ..., xn) que satisfacen las restricciones; es un punto en el espacio n-dimensional.

El conjunto de soluciones admisibles forma la región de soluciones admisibles (ADS) del problema LP. ODR es un poliedro convexo (polígono).

En general, cuando el problema involucra N-incógnitas, podemos decir que la región de soluciones factibles, definida por el sistema de condiciones límite, está representada por un poliedro convexo en un espacio n-dimensional y se logra el valor óptimo de la función objetivo. en uno o más vértices.

Una solución básica es una solución en la que todas las variables libres son iguales a cero.

Una solución de soporte es una solución básica no negativa. La solución de soporte puede ser no degenerada y degenerada. Una solución de referencia se llama no degenerada si el número de sus coordenadas distintas de cero es igual al rango del sistema; de lo contrario, es degenerada.

Una solución admisible en la que la función objetivo alcanza su valor extremo se llama óptima y se denota .

Es muy difícil resolver estos problemas gráficamente cuando el número de variables es superior a 3. existe método universal Resolver problemas de programación lineal, llamado método simplex.

El método simplex es método universal resolución de problemas de PL, que es un proceso iterativo que comienza con una solución y, en busca de la mejor opción, avanza por los puntos de las esquinas de la región de soluciones factibles hasta alcanzar el valor óptimo.

Puede utilizarse para resolver cualquier problema de programación lineal.

El método simplex se basa en la idea de mejora secuencial de la solución resultante.

El significado geométrico del método simplex es una transición secuencial de un vértice del poliedro restringido al vecino, en el que la función objetivo toma el mejor (o al menos no el peor) valor hasta encontrar la solución óptima: el vértice donde el valor óptimo se logra en función del objetivo (si el problema tiene un óptimo final).

Así, al tener un sistema de restricciones reducido a forma canónica (todas las restricciones funcionales tienen la forma de igualdad), encuentran cualquier solución básica a este sistema, preocupándose sólo por encontrarla de la manera más simple posible. Si la primera solución básica encontrada resulta factible, se comprueba su optimización. Si no es óptima, se pasa a otra solución básica, necesariamente admisible. método simplex garantiza que con esta nueva solución la función objetivo, si no alcanza el óptimo, se acercará a él (o al menos no se alejará de él). La nueva solución básica factible se trata de la misma manera hasta que se encuentra una solución óptima.

El proceso de aplicación del método simplex implica la implementación de sus tres elementos principales:

un método para determinar cualquier solución básica inicial viable a un problema;

la regla de transición hacia la mejor solución (más precisamente, no peor);

Criterio para comprobar la optimización de la solución encontrada.

El método simplex incluye varias etapas y puede formularse como un algoritmo claro (una instrucción clara para realizar operaciones secuenciales). Esto le permite programarlo e implementarlo con éxito en una computadora. Los problemas con una pequeña cantidad de variables y restricciones se pueden resolver manualmente utilizando el método simplex.

El método simplex es un procedimiento iterativo para resolver problemas de LP en forma canónica (cualquier problema de LP se puede reducir a forma canónica:

Habrá n+m variables en total en el problema.

Las variables incluidas con coeficientes unitarios en una sola ecuación del sistema y con coeficientes cero en el resto se denominan básico. En el sistema canónico, cada ecuación corresponde exactamente a una variable básica. Las n variables restantes se denominan variables no básicas.

Ejemplo 1.

Resolvamos el problema:

Para encontrar la solución básica inicial, dividimos las variables en básicas y no básicas. Dado que el determinante de la matriz de coeficientes para x 3, x 4 x 5 y x 6 es diferente de cero (cada una de estas variables está incluida en una sola restricción y con un coeficiente de 1, es decir, la matriz de coeficientes para ellas será unidad), entonces se pueden tomar como variables básicas. Las variables restantes x 1 y x 2 son menores.

Regla: en el primer paso, como variables principales, se deben seleccionar aquellas que están incluidas en solo una de las ecuaciones del sistema de restricciones, mientras que no existen ecuaciones que no incluyan ninguna de estas variables.

Si las variables adicionales tienen el mismo signo que los términos libres del lado derecho, entonces satisfacen esta regla.

1). En el primer paso obtenemos:

Variables básicas	Variables no básicas
x 3, x 4 x 5 x 6

Expresemos las variables no centrales en términos de las principales:

(*)

Obtenemos la solución básica del sistema X 1 = (0; 0; 18; 16; 5; 21). Si lo comparamos con la solución gráfica de este problema, entonces X 1 corresponde al punto O(0;0) del polígono OABCDE (ver Fig. 1).

Dado que esta solución es factible, no se puede descartar que sea óptima.

,z(X1)=0.

La función z se puede incrementar con una variable no primaria (ambas entran en la ecuación con un coeficiente >0). Esto se puede hacer pasando a una nueva solución de base factible en la que una de estas variables se convierta en la principal. Si la nueva solución es degenerada, entonces la función objetivo conservará su valor. Geométricamente, se trata de una transición a otro vértice vecino, en el que la función objetivo al menos no será peor. En el problema que nos ocupa, tanto x 1 como x 2 se pueden convertir en variables básicas, ya que ambas están incluidas en la función objetivo con el signo “+”.

Para mayor precisión, en tal situación elegiremos la variable con el coeficiente más grande en la función objetivo. En este problema es x 2.

El sistema de restricciones (*) impone restricciones al crecimiento de x2, ya que es necesario mantener la admisibilidad de la solución (todas las variables deben ser "0). Por lo tanto, se deben satisfacer las siguientes desigualdades para x 1 = 0:

Cualquier ecuación del sistema (*) (excepto la última) determina la relación de evaluación: el límite de crecimiento de la variable x 2, que preserva la no negatividad de la variable correspondiente. Este límite está determinado por el valor absoluto de la relación entre el término libre y el coeficiente en x 2, si tienen diferentes signos. Dado que x 2 no está incluido en la última restricción (incluido con un coeficiente de 0), entonces el crecimiento de x 2 no está limitado, x 2<∞. Будем так же считать, сто граница переменной х 2 равно ∞, если коэффициент перед х 2 и свободный член имеют одинаковые знаки. Нет ограничений на рост х 2 и в том случае, если свободные член равен 0. Но если при этом коэффициент при х 2 отрицательный, то рост этой переменной ограничен 0.

Dado que todas las variables deben mantener la no negatividad, la nueva variable básica x 2 =min(6; 16; 5; ∞)=5. La ecuación que corresponde a la estimación mínima se llama ecuación resolutiva. En este ejemplo, esta es la tercera ecuación.

En consecuencia, la variable x 5 =0 y pasa a variables no básicas.

2). Llegamos al segundo paso:

Variables básicas	Variables no básicas
x 3, x 4 x 2 x 6

De la tercera ecuación del sistema expresamos: x 2:

Sustituyendo el lado derecho de la igualdad en todas las demás ecuaciones en lugar de x 2 obtenemos:

Obtenemos una nueva solución básica del sistema X 2 = (0; 5; 3; 11; 0; 21). Esto corresponde al punto A(0;5) del polígono OABCDE (ver Fig. 1).

Expresemos la función objetivo en términos de variables no principales:
,z(X2)=15.

De manera similar al razonamiento realizado en el primer paso, concluimos que la función objetivo se puede mejorar introduciendo x 1 en las variables básicas.

x 1 =min(∞; 13; 11/2; ∞)=3, por lo tanto la segunda ecuación se resuelve y x 3 se deriva de la base.

3). Llegamos al tercer paso:

Variables básicas	Variables no básicas
x 1, x 4 x 2 x 6

De la segunda ecuación del sistema expresamos: x 1:

Sustituyendo el lado derecho de la igualdad en todas las demás ecuaciones en lugar de x 1, obtenemos:

Obtenemos una nueva solución básica del sistema X 3 =(3; 5; 0; 5; 0; 12). Esto corresponde al punto B(3;5) del polígono OABCDE (ver Fig. 1).

Expresemos la función objetivo en términos de variables no principales:
,z(X3)=21.

De manera similar a los dos primeros pasos, introducimos x 5 en las variables básicas.

x 5 =min(∞; 5; 1;4/3) = 1, por lo tanto, la tercera ecuación se resuelve y x 4 se deriva de la base.

4). Llegamos al cuarto paso:

Variables básicas	Variables no básicas
x 1, x 5 x 2 x 6

De la tercera ecuación del sistema expresamos: x 5:

Sustituyendo el lado derecho de la igualdad en todas las demás ecuaciones, en lugar de x 5 obtenemos:

Obtenemos una nueva solución básica del sistema X 4 =(6; 4; 0; 0; 1; 6). Esto corresponde al punto C(6;4) del polígono OABCDE (ver Fig. 1).

Expresemos la función objetivo en términos de variables menores: ,z(X 4)=24.

La función objetivo no se puede mejorar pasando a otra solución básica, ya que todos los coeficientes de las variables no básicas son menores que 0, por lo tanto, el problema está resuelto. El beneficio máximo en este caso es 24, y el plan de producción óptimo: 6 unidades del primer producto y 4 unidades del segundo producto. Variables adicionales muestran la diferencia entre el gasto de cada tipo de recurso y su consumo. x 3 = x 4 = 0, por lo tanto los recursos S 1 y S 2 se consumen completamente en el proceso de producción, y los saldos S 3 y S 4 son iguales a 1 y 3, respectivamente.

En la práctica, los cálculos al resolver problemas mediante el método simplex se realizan utilizando tablas simplex. Consideremos el algoritmo del método simplex utilizando tablas simplex.

Algoritmo del método simplex:

Nosotros definimos . Si no hay un mínimo final, entonces el problema no tiene un óptimo final (z max =). Si el mínimo es finito, entonces seleccionamos la recta q en la que se logra (si hay varias, entonces cualquiera), y la llamamos recta resolutiva. En la intersección de la fila de resolución y la columna de resolución hay un elemento de resolución a qs.

Pasemos a la siguiente tabla según las reglas (transformada de Gauss-Jordan o regla del rectángulo):

1. en la columna de la izquierda escribimos una nueva base: en lugar de la variable principal x q - variable x s;

   en las columnas correspondientes a las variables básicas ingresamos ceros y unos: 1- en la intersección de la fila y columna correspondientes a una misma variable básica; 0 – en todas las demás posiciones de las columnas de las variables básicas;

   Obtenemos una nueva línea q a partir de la anterior dividiendo por el elemento de resolución a qs ;

   todos los demás elementos a ij " se calculan según la regla:

(2)

Ejemplo 6.

Resolvamos el problema:

Llevemos el sistema de restricciones a la forma canónica. Obtenemos el sistema extendido:

Representemos la función objetivo como z-2x 1 -3x 2 =0.

Las variables básicas serán variables adicionales x 3, x 4, x 5, x 6.

Completemos la primera tabla simplex:

	Miembro gratuito	variables						Relaciones evaluativas

Comprobamos el criterio de optimización del problema. La última línea de estimación tiene coeficientes negativos. Elegimos el módulo más grande de ellos – (-3). Por lo tanto s=2, la variable x 2 es la base de entrada y la columna correspondiente es la de resolución.

Encontramos los ratios estimados y seleccionamos el mínimo de ellos (=5). Por lo tanto, q=3, la variable x 5 se deriva de la base y se resuelve la fila correspondiente.

en la nueva base las variables principales son x 3, x 4, x 2, x 6;

organizar 0 y 1; por ejemplo, en la intersección de la columna y la fila correspondientes a la variable x 3 establecemos 1, y los elementos restantes de la columna x 3 son iguales a 0, etc.

La tercera línea se obtiene dividiendo por el elemento resolutivo a 33 =1. Completamos las celdas restantes de la tabla según las fórmulas (2). Por ejemplo:

	Miembro gratuito	variables						Relaciones evaluativas

Obtenemos la segunda tabla simplex:

Nuevamente no se cumple el criterio de optimización. Ahora la primera columna se está resolviendo y x 1 es la variable de entrada. Calculamos los ratios estimados y encontramos la recta resolutiva, la primera y la variable derivada de la base, x 3. Elemento de resolución a 11.

	Miembro gratuito	variables						Relaciones evaluativas

Pasemos a la nueva tabla simplex:

Y esta vez no se cumple el criterio de optimización.

	Miembro gratuito	variables						Relaciones evaluativas

Variable de salida x 4; ingresado x 5. Pasemos a una nueva tabla.