Hogar › Teléfono › Método de programación lineal para resolver multiplicadores. El concepto de programación lineal. Tipos de problemas de programación lineal. Ejemplo de no solución

Método de programación lineal para resolver multiplicadores. El concepto de programación lineal. Tipos de problemas de programación lineal. Ejemplo de no solución

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

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

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

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

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

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

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

Ejemplo 26.1

Resuelva el problema usando el método simplex:

Solución:

Llevamos el problema a la forma canónica.

Para hacer esto 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. La solución de referencia, los coeficientes de expansión y las estimaciones de expansión de vectores de condiciones sobre la base de 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. La primera columna "B" contiene 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 un problema de 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 la solución económica más óptima 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 consisten en encontrar valores extremos, es decir, el máximo y mínimo de funciones de cantidades variables.

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

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

Además, 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.

Sin embargo, la 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 desigualdades de restricciones en estas condiciones pueden ser diferentes.

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

La programación dinámica se basa en la construcción de un árbol de decisiones. Cada nivel de este árbol sirve como escenario para determinar las consecuencias. decisión previa y eliminar opciones ineficaces para esta solución. 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 óptimas para el desarrollo de una 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.

Los métodos de programación lineal se utilizan para resolver muchos problemas extremos que a menudo se abordan en economía. Resolver estos problemas se reduce a encontrar los valores extremos (máximo y mínimo) de algunas funciones de cantidades variables.
La programación lineal se basa en la resolución de un sistema de ecuaciones lineales (con transformación en ecuaciones y desigualdades), cuando la relación entre los fenómenos que se estudian es estrictamente funcional. Se caracteriza por una expresión matemática de variables, un cierto orden, secuencia de cálculos (algoritmo) y análisis lógico. Sólo se puede utilizar en los casos en que las variables y factores en estudio tengan certeza matemática y limitaciones cuantitativas, cuando, como resultado de una secuencia conocida de cálculos, los factores sean intercambiables, cuando haya lógica en los cálculos, lógica matemática se combinan con una comprensión lógicamente fundamentada de la esencia del fenómeno que se está estudiando.
Usando este método en producción industrial, por ejemplo, el óptimo rendimiento general máquinas, unidades, líneas de producción (con una determinada gama de productos y otros valores determinados), se resuelve el problema del corte racional de materiales (con un rendimiento óptimo de piezas de trabajo). EN agricultura se utiliza para determinar el costo mínimo de las raciones de alimento para una determinada cantidad de alimento (por tipo y nutrientes que contienen). El problema de la mezcla también se puede utilizar en fundición(composición de la carga metalúrgica). Se utiliza el mismo método para resolver problema de transporte, la tarea de vincular racionalmente las empresas consumidoras a las empresas productoras.
Todos los problemas económicos resueltos mediante programación lineal se distinguen por soluciones alternativas y ciertas condiciones limitantes. Resolver tal problema significa elegir la mejor, la óptima, entre todas las opciones (alternativas) admisiblemente posibles. La importancia y el valor de utilizar el método de programación lineal en economía es que la opción óptima se selecciona entre un número muy significativo opciones alternativas. Es casi imposible resolver este tipo de problemas utilizando otros métodos.

Como ejemplo, considere resolver el problema del uso racional del tiempo de trabajo. equipo de producción.
De acuerdo a plan operativo Durante la primera semana de diciembre, la sección de rectificado produjo 500 anillos para rodamientos tipo A, 300 anillos para rodamientos tipo B y 450 anillos para rodamientos tipo B. Todos los anillos fueron rectificados en dos máquinas intercambiables. rendimiento diferente. tiempo de la máquina cada máquina es de 5000 min. La complejidad de las operaciones (en minutos por anillo) en la fabricación de varios anillos se caracteriza por los siguientes datos (Tabla 6.5).
Tabla 6.5
Es necesario determinar la opción óptima para distribuir las operaciones entre máquinas y el tiempo que se invertiría con esta opción óptima. Completemos la tarea usando el método simplex.
para compilar modelo matemático Para este problema presentamos lo siguiente simbolos: jc, x2, xъ, - respectivamente, el número de anillos para rodamientos de tipo L, B, V, fabricados en la máquina I; x4, x5, x6: respectivamente, el número de anillos para rodamientos de los tipos A, B, C, fabricados en la máquina II.
La forma lineal que refleja el criterio de optimización se verá así:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 con restricciones
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Transformemos la condición del problema introduciendo variables adicionales (auxiliares) y ficticias. Escribamos la condición así:
pico lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Un sistema de ecuaciones que refleja las condiciones restrictivas del tiempo de computadora y la cantidad de productos producidos:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
La solución a este problema se presenta en la tabla. 6.6. La opción óptima se obtuvo en la séptima etapa (iteración). Si la máquina I produjera 125 anillos de rodamiento del tipo A, 450 anillos de rodamiento del tipo B y la máquina II produjera 375 anillos de rodamiento del tipo A y 300 anillos de rodamiento del tipo B, entonces con tal carga de equipo se necesitarían 350 minutos de tiempo de máquina. liberado para la máquina II. El tiempo total invertido bajo la opción óptima sería de 9650 minutos, mientras que en realidad se invirtieron 10.000 minutos de tiempo de computadora.
Un problema muy típico resuelto mediante programación lineal es el problema del transporte. Su significado es minimizar la rotación de carga al entregar bienes de consumo del fabricante al consumidor, con almacenes mayoristas y bases en empresas de comercio minorista. Se puede resolver mediante el método simplex o el método de distribución.
La solución al problema del transporte mediante el método de distribución se dio en la tercera edición del libro de texto “Teoría análisis económico"(Finanzas y Estadística, 1996).

Resolver el problema del uso racional de máquinas herramienta mediante el método simplex.

Base	Con	ro	4	10	10	6	8	20	0	0	metro	metro	metro
Base	Con	ro	l	rg	R	l	R ъ		Pi	P8	pag*	L 0	L,
l	0	5000	4	10	0	0	0	0	і	0	0	0	0
R,	0	5000	0	0	0	6	8	20	0	1	0	0	0
l	metro	500	1	0	0	1	0	0	0	0	1	0	0
L 0	metro	300	w	0	0	0	1	0	0	0	0	1	0
l.	metro	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250M	M-4	M-10	M-10	M-6	M-8	M-20	0	0	0	0	0
Pi	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
pag*	0	5000	0	0	0	6	8	20	1	1	0	0	0
ro	4	500	1	0	0	1	0	0	0	0	1	0	0
lo	metro	300	0	1	0	0	w	0	0	0	0	1	0
l.	metro	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750L/+2000	0	M-10	M-10	-2	M-8	ACERCA DE 2	0	0	-M+4	0	0

Base	CON	P0	4	Pi	10	6	8	20	0	0	metro	metro	METRO
		P0	Pi	10	^3	yo	P5	p6	Pi	pag"	p9	PI 0	radiocontrol
Pi	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
PAG*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
PR	METRO	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450L/+4400	0	-2	M-10	-2	0	M-20	0	0	-M+4	-M+8	0
R	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
PAG%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
radiocontrol	METRO	150	0	-1	0	j4_ 10	0	1	_J_ 10	0	4 10	0	1
zrCj		150L/+7400	0	-M+S	0	-M-6 10	0	M-20	-~M+1 10	0	-±m 10	- Af+8"	0

Base	Con	L,	4	10	10	6	8	20	0	0		METRO	METRO	metro
Base	Con	L,	l	rg	l	yo	PD	p6	Pi	pam;		P9	lo	l.
l	10	300	0	1	1	4	0	0	1		0	4	0	0
						“10			Eso			“ 10
p6	20	130	0	4	0	3	0	1	0		1	0	4	0
				~Ї0		10					20		10
yo	4	500	1	0	0	1	0	0	0		0	1	0	0
PD	8	300	0	1	0	0	1	0	0		0	0	1	0
R\\	METRO	20	0	6	0	1	0	0	1		1	4	4	1
				10		~10			Eso		20	Eso	10
Zj-Cj		20M+10000	0		0	-metro	0	0	m+\		-m+\	--METRO	-*METRO	0
				10		10			10	20		10	10
yo	10	380	0	14	1	0	0	0	3		2	12	0	0
				10					10		10	10
pag%	20	70	0	14	0	0	0	1	3		2	12	16	-3
				10					10		10	10	10
l	4	300	1	6	0	0	0	0	1		1	-3		-10
											2
p5	8	300	0	1	0	0	1	0	0		0	0	1	0
P4	6	200	0	-6	0	1	0	0	-1		1	4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1		-METRO	-METRO	-metro

Base		ligero;	4	10	10	6	8	20	0	0	metro	metro	l/
Base	oh	ligero;	l	rg	ръ	PAG*	P5	P6	l	Pamp;	p9	L 0	l.
rg	10	450	0	0	1	0	0	1	0	0
PAG%	0	350	0	7	0	0	0	5	3 5	1
l	4	125	1	5 2	0	0	0	5 2	1 4	0
PD	8	300	0	1	0	0	1	0	0	0
P4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0

La programación lineal es una de las ramas más importantes de las matemáticas, donde se estudian los fundamentos teóricos y metodológicos para la resolución de determinados problemas. Esta disciplina matemática es ampliamente utilizada en últimos años en diversos ámbitos económicos y áreas técnicas, donde no se le da el último papel a la planificación y el uso matemático sistemas automáticos cálculos. Esta rama de la ciencia se dedica al estudio de modelos de optimización lineal. Es decir, la programación lineal se trata de números. Por primera vez este término fue propuesto por T. Koopmans en 1951. Plan óptimo para cada uno. programa lineal debe vincularse automáticamente a nivel optimo precios, es decir, con valoraciones determinadas objetivamente.

Programación lineal: métodos

Utilizando esta técnica, es posible resolver un número considerable de problemas extremos relacionados con la economía. EN en este caso Por lo general, es necesario encontrar los valores extremos de algunas funciones de una variable. La solución de un sistema de ecuaciones y desigualdades transformables se expresa como la base de la programación lineal. este tipo La programación se caracteriza por una formulación matemática de variables, secuencia y en un cierto orden cálculos, así como análisis lógico. Esto se aplica:

Si existe certeza matemática y limitación cuantitativa entre los factores que se estudian y cantidades variables;

Si existe intercambiabilidad de factores debido a la secuencia de cálculos;

Si se combina la lógica matemática con la comprensión de la esencia de los fenómenos que se estudian.

Programación lineal en Facilita el cálculo rendimiento óptimo todas las máquinas, líneas de producción, unidades, así como la solución de problemas de uso racional de los materiales disponibles.

En la agricultura utilizando este método El coste mínimo de la ración de alimentación se determina teniendo en cuenta la cantidad de pienso disponible. Esto tiene en cuenta los tipos y el contenido de determinadas sustancias beneficiosas que contienen.

en fundicion esta técnica permite encontrar una solución al problema del transporte y al problema de las mezclas que forman parte de la carga metalúrgica. La esencia del problema del transporte en este caso implica la vinculación óptima de las empresas consumidoras a las empresas que se dedican a la producción.

Programación lineal: problemas

rasgo distintivo todos tareas económicas, que se resuelven mediante técnicas de programación lineal, es la elección ciertas opciones soluciones, así como condiciones limitantes. Al resolver un problema de este tipo, es posible encontrar la solución óptima entre todas las opciones alternativas.

Un valor significativo del uso de técnicas de programación lineal en economía es la elección del opcion optima de gran cantidad todas las opciones que se consideren aceptables. Tareas similares es casi imposible resolverlo de otras formas, ya que sólo ellas permiten encontrar el grado de racionalidad de aplicación. Utilizando la programación lineal se resuelve un problema tan básico como el transporte, que debería minimizar la rotación de carga de los bienes de consumo durante su entrega. el fabricante.

Programación lineal en Excel

En el proceso de resolución de tales problemas, primero es necesario crear un modelo, lo que implica la formulación de condiciones sobre lenguaje matemático. Después de esta etapa, se puede encontrar una solución método gráfico. Para hacer esto en programa excel existe función especial"Encontrar una solución."

Como ya se desprende de lo anterior, la programación lineal tiene un ámbito de aplicación muy amplio.

Anotación: Esta conferencia revela una serie de cuestiones dedicadas a la programación lineal como una de las secciones. programación matemática; en particular, formula los principales tipos de problemas de programación lineal, revela las diferencias entre estos problemas y problemas clásicos análisis matemático; presenta varias formas registra estas tareas, las configura y estudia su estructura. La cuestión de la resolución de problemas de programación lineal utilizando el método simplex se explora más a fondo.

1. El concepto de programación matemática.

es una disciplina matemática en la que se desarrollan métodos para encontrar valores extremos de una función objetivo entre sus muchas valores posibles, determinado por restricciones.

La presencia de restricciones hace que los problemas sean fundamentalmente diferentes de los problemas clásicos del análisis matemático de encontrar valores extremos de una función. Métodos de análisis matemático para la búsqueda. extremo de la función en tareas programación matemática resultar inadecuado.

para resolver problemas programación matemática Se han desarrollado y se están desarrollando métodos y teorías especiales. Dado que resolver estos problemas requiere realizar una cantidad significativa de cálculos, cuando evaluación comparativa metodos gran valor Se presta atención a la eficiencia y conveniencia de su implementación en una computadora.

Puede considerarse como un conjunto de secciones independientes involucradas en el estudio y desarrollo de métodos para resolver determinadas clases de problemas.

Dependiendo de las propiedades de la función objetivo y de la función de restricción, todos los problemas programación matemática se dividen en dos clases principales:

problemas de programación lineal,
tareas programación no lineal.

Si la función objetivo y las funciones de restricción son funciones lineales, entonces el problema correspondiente de encontrar un extremo es un problema de programación lineal. Si al menos uno de funciones especificadas es no lineal, entonces el problema correspondiente de encontrar un extremo es el problema programación no lineal.

2. El concepto de programación lineal. Tipos de problemas de programación lineal

programación lineal(LP) – una de las primeras y más estudiadas secciones programación matemática. Exactamente programación lineal fue la sección a partir de la cual comenzó a desarrollarse la propia disciplina" programación matemática". El término "programación" en el nombre de la disciplina no tiene nada en común con el término "programación (es decir, compilar un programa) para una computadora" no tiene nada en común, ya que la disciplina " programación lineal" surgió incluso antes de que las computadoras comenzaran a usarse ampliamente para resolver problemas matemáticos, de ingeniería, económicos y de otro tipo.

El término " programación lineal" surgió como resultado de una traducción inexacta del inglés "programación lineal". Uno de los significados de la palabra "programación" es hacer planes, planificar. En consecuencia, traducción correcta La "programación lineal" en inglés no sería " programación lineal", y "planificación lineal", que refleja con mayor precisión el contenido de la disciplina. Sin embargo, los términos programación lineal, programación no lineal, programación matemática etc. se han vuelto generalmente aceptados en nuestra literatura y, por lo tanto, se conservarán.

Entonces, programación lineal Surgió después de la Segunda Guerra Mundial y comenzó a desarrollarse rápidamente, atrayendo la atención de matemáticos, economistas e ingenieros por la posibilidad de una amplia aplicación práctica, así como por la armonía matemática.

Se puede decir que programación lineal aplicable a la resolución de modelos matemáticos de aquellos procesos y sistemas que pueden basarse en la hipótesis de una representación lineal del mundo real.

programación lineal utilizado en la resolución de problemas económicos, en tareas como la gestión y planificación de la producción; en problemas de determinación colocación óptima equipos en embarcaciones marítimas, en talleres; en problemas de determinación plan optimo transporte de carga (tarea de transporte); en problemas de distribución óptima del personal, etc.

problema de programación lineal(LP), como ya se desprende de lo dicho anteriormente, consiste en encontrar el mínimo (o máximo) de una función lineal bajo restricciones lineales.

forma general el problema tiene la forma: encontrar bajo las condiciones

Junto con forma general también ampliamente utilizado canónico Y estándar formas. Tanto en forma canónica como estándar.

Aquellos. todas las variables en cualquier solución factible del problema deben tomar valores no negativos (tales variables generalmente se denominan no negativo a diferencia de los llamados gratis variables cuyo rango de valores no está sujeto a tales restricciones). La diferencia entre estas formas es que en un caso I 2 = 0, y en el otro, I 1 = 0.

El problema del LP en forma canónica.

programación lineal

programación lineal- una disciplina matemática dedicada a la teoría y los métodos de resolución de problemas extremos en conjuntos de espacio vectorial dimensional definido por sistemas de ecuaciones lineales y desigualdades.

La programación lineal es un caso especial de programación convexa, que a su vez es un caso especial de programación matemática. Al mismo tiempo, es la base de varios métodos para resolver problemas de programación entera y no lineal. Una generalización de la programación lineal es la programación lineal fraccionada.

Muchas propiedades de los problemas de programación lineal también pueden interpretarse como propiedades de poliedros y, por tanto, formularse y probarse geométricamente.

Historia

El método del punto interior fue mencionado por primera vez por I. I. Dikin en 1967.

Tareas

El principal problema de programación lineal (estándar) se llama el problema de encontrar el mínimo de una función objetivo lineal ( forma lineal) de la forma:

bajo condiciones

, .

El problema de programación lineal tendrá vista canónica , si en el problema principal en lugar del primer sistema de desigualdades hay un sistema de ecuaciones:

El problema principal se puede reducir a canónico introduciendo variables adicionales.

Los problemas de programación lineal de la forma más general (problemas con restricciones mixtas: igualdades y desigualdades, presencia de variables libres de restricciones) se pueden reducir a equivalentes (que tienen el mismo conjunto de soluciones) reemplazando variables y reemplazando igualdades con un par de desigualdades.

Es fácil ver que el problema de encontrar el máximo puede reemplazarse por la tarea de encontrar el mínimo tomando coeficientes con el signo opuesto.

Problemas de muestra

Coincidencia máxima

Considere el problema de correspondencia máxima en un gráfico bipartito: hay varios niños y niñas, y para cada niño y niña se sabe si son atractivos entre sí. Necesitamos casar a tantas parejas como sea posible con simpatía mutua.

Introduzcamos variables que correspondan al par de niño y niña y satisfagan las restricciones:

con función objetivo. Se puede demostrar que entre las soluciones óptimas a este problema existe una entera. Las variables iguales a 1 corresponderán a parejas que deberían estar casadas.

Flujo máximo

Sea un gráfico (con aristas orientadas) en el que para cada arista se indique su capacidad. Y se dan dos vértices: drenaje y fuente. Es necesario indicar para cada borde cuánto líquido fluirá a través de él (no más que su capacidad) para maximizar el flujo total desde la fuente hasta el drenaje (el líquido no puede aparecer ni desaparecer en todos los vértices excepto en el drenaje y la fuente).

Tomemos como variable la cantidad de líquido que circula por la nervadura. Entonces

¿Dónde está la capacidad de ese borde? Estas desigualdades deben complementarse con la igualdad de la cantidad de fluido que entra y sale por cada vértice, excepto el drenaje y la fuente. Como función, es natural tomar la diferencia entre la cantidad de fluido que sale y que entra en la fuente.

Una generalización del problema anterior es flujo máximo de costo mínimo. En este problema, se dan los costos para cada borde y es necesario seleccionar el flujo con el costo mínimo entre los flujos máximos. Este problema se reduce a dos problemas de programación lineal: primero es necesario resolver el problema del flujo máximo y luego agregar a este problema la restricción, ¿dónde está la cantidad? flujo máximo y resolver el problema con nueva característica- costo de flujo.

Estos problemas se pueden resolver más rápido que algoritmos generales resolver problemas de programación lineal debido a la estructura especial de ecuaciones y desigualdades.

Tarea de transporte

Existe una cierta carga homogénea que debe trasladarse de los almacenes a las fábricas. Para cada almacén se conoce cuánta carga contiene, y para cada planta se conoce su demanda de carga. El costo del transporte es proporcional a la distancia desde el almacén hasta la fábrica (se conocen todas las distancias desde el décimo almacén hasta la décima fábrica). Se requiere componer lo más plan barato transporte.

La variable decisiva en este caso son las cantidades de carga transportadas desde el décimo almacén hasta la décima planta. Cumplen las restricciones:

Función objetivo tiene la forma: , que debe minimizarse.

juego de suma cero

Hay una matriz de tamaño. El primer jugador elige un número del 1 al , el segundo, del 1 al . Luego verifican los números y el primer jugador obtiene puntos, y el segundo jugador obtiene puntos (el número elegido por el primer jugador obtiene el segundo). Necesitamos encontrar la estrategia óptima para el primer jugador.

Supongamos que en una estrategia óptima, por ejemplo, el primer jugador debe elegir un número con probabilidad . Entonces la estrategia óptima es una solución al siguiente problema de programación lineal:

, , (),

en el que la función necesita ser maximizada. El valor en la solución óptima será la expectativa de pago del primer jugador en el peor de los casos.

Algoritmos de solución

Los más famosos y utilizados en la práctica para resolver. tarea común La programación lineal (LP) es un método simplex. A pesar de que el método simplex es un algoritmo bastante eficaz que ha demostrado buenos resultados al resolver problemas de LP aplicados, es un algoritmo con complejidad exponencial. La razón de esto es la naturaleza combinatoria del método simplex, que itera secuencialmente sobre los vértices del poliedro. soluciones admisibles al buscar la solución óptima.

El primer algoritmo polinomial, el método del elipsoide, fue propuesto en 1979 por el matemático soviético L. Khachiyan, resolviendo así el problema. por mucho tiempo quedó sin resolver. El método del elipsoide tiene una naturaleza completamente diferente y no combinatoria que el método simplex. Sin embargo, desde el punto de vista computacional, este método resultó poco prometedor. Sin embargo, el hecho mismo de la complejidad polinomial de los problemas llevó a la creación de una clase completa algoritmos eficientes LP- métodos de punto interior, el primero de los cuales fue el algoritmo de N. Karmarkar propuesto en 1984. Los algoritmos de este tipo utilizan una interpretación continua del problema LP, cuando en lugar de enumerar los vértices del poliedro de soluciones al problema LP, se realiza una búsqueda a lo largo de trayectorias en el espacio. variables del problema, sin pasar por los vértices del poliedro. El método del punto interior, que, a diferencia del método simplex, atraviesa puntos desde el interior de la región factible, utiliza métodos de programación no lineal de barrera logarítmica desarrollados en la década de 1960 por Fiacco y McCormick.

Ver también

Método gráfico para resolver un problema de programación lineal.

Notas

Literatura

Thomas H. Corman y otros. Capítulo 29. Programación lineal // Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 2ª ed. - M.: “Williams”, 2006. - P. 1296. - ISBN 5-8459-0857-4
Akulich I.L. Capítulo 1. Problemas de programación lineal, Capítulo 2. Problemas especiales de programación lineal // Programación matemática en ejemplos y problemas. - M.: Escuela de posgrado, 1986. - 319 p. -ISBN 5-06-002663-9
Karmanov V. G. Programación matemática. - 3ª edición. - M.: Nauka, 1986. - 288 p.
Danzig George Bernard "Recuerdos del comienzo de la programación lineal"

Campo de golf

- Paquete de optimización gratuito diseñado para resolver problemas de programación lineal, entera y por objetivos.
Vershik A. M. "Acerca de L. V. Kantorovich y la programación lineal"
Bolshakova I. V., Kuralenko M. V. “Programación lineal. Manual educativo y metodológico para la prueba."
Barsov A. S. "¿Qué es la programación lineal?", Conferencias populares sobre matemáticas, Gostekhizdat, 1959.
M. N. Vyalyi Desigualdades lineales y combinatoria. -MCNMO, 2003.

Fundación Wikimedia.