linprog
Resolver problemas de programación lineal
Sintaxis
Descripción
Solver de programación lineal
Encuentra el mínimo de un problema especificado por
f, x, b, beq, lb y ub son vectores, y A y Aeq son matrices.
Nota
linprog
se aplica únicamente al enfoque basado en solvers. Para ver una exposición sobre los dos enfoques de optimización, consulte En primer lugar, elija el enfoque basado en problemas o el enfoque basado en solvers.
define un conjunto de límites inferiores y superiores en las variables de diseño, x
= linprog(f
,A
,b
,Aeq
,beq
,lb
,ub
)x
, de modo que la solución siempre se encuentra en el rango lb ≤ x ≤ ub
. Establezca Aeq = []
y beq = []
si no existen igualdades.
Nota
Si los límites de entrada especificados para un problema son inconsistentes, la salida fval
es []
.
encuentra el mínimo para x
= linprog(problem
)problem
, una estructura descrita en problem
.
Puede importar una estructura problem
de un archivo MPS utilizando mpsread
. También puede crear una estructura problem
a partir de un objeto OptimizationProblem
utilizando prob2struct
.
Ejemplos
Programa lineal, restricciones de desigualdad lineales
Resuelva un programa lineal simple definido por desigualdades lineales.
Para este ejemplo, utilice estas restricciones de desigualdad lineales:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Utilice la función objetivo .
f = [-1 -1/3];
Resuelva el programa lineal.
x = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
Programa lineal con desigualdades e igualdades lineales
Resuelva un programa lineal simple definido por desigualdades e igualdades lineales.
Para este ejemplo, utilice estas restricciones de desigualdad lineales:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Utilice la restricción de igualdad lineal .
Aeq = [1 1/4]; beq = 1/2;
Utilice la función objetivo .
f = [-1 -1/3];
Resuelva el programa lineal.
x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1
0
2
Programa lineal con todos los tipos de restricciones
Resuelva un programa lineal simple con desigualdades lineales, igualdades lineales y límites.
Para este ejemplo, utilice estas restricciones de desigualdad lineales:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Utilice la restricción de igualdad lineal .
Aeq = [1 1/4]; beq = 1/2;
Establezca estos límites:
lb = [-1,-0.5]; ub = [1.5,1.25];
Utilice la función objetivo .
f = [-1 -1/3];
Resuelva el programa lineal.
x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x = 2×1
0.1875
1.2500
Programa lineal con el algoritmo 'interior-point'
Resuelva un programa lineal con el algoritmo 'interior-point'
.
Para este ejemplo, utilice estas restricciones de desigualdad lineales:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Utilice la restricción de igualdad lineal .
Aeq = [1 1/4]; beq = 1/2;
Establezca estos límites:
lb = [-1,-0.5]; ub = [1.5,1.25];
Utilice la función objetivo .
f = [-1 -1/3];
Establezca opciones para utilizar el algoritmo 'interior-point'
.
options = optimoptions('linprog','Algorithm','interior-point');
Resuelva el programa lineal con el algoritmo 'interior-point'
.
x = linprog(f,A,b,Aeq,beq,lb,ub,options)
Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the function tolerance, and constraints are satisfied to within the constraint tolerance.
x = 2×1
0.1875
1.2500
Resolver la LP utilizando el enfoque basado en problemas para linprog
Este ejemplo muestra cómo configurar un problema utilizando el enfoque basado en problemas y cómo resolverlo utilizando el enfoque basado en solvers. El problema es
Cree un objeto OptimizationProblem
llamado prob
para representar este problema.
x = optimvar('x','LowerBound',-1,'UpperBound',1.5); y = optimvar('y','LowerBound',-1/2,'UpperBound',1.25); prob = optimproblem('Objective',x + y/3,'ObjectiveSense','max'); prob.Constraints.c1 = x + y <= 2; prob.Constraints.c2 = x + y/4 <= 1; prob.Constraints.c3 = x - y <= 2; prob.Constraints.c4 = x/4 + y >= -1; prob.Constraints.c5 = x + y >= 1; prob.Constraints.c6 = -x + y <= 2; prob.Constraints.c7 = x + y/4 == 1/2;
Convierta el objeto de problema en una estructura de problema.
problem = prob2struct(prob);
Resuelva la estructura de problema resultante.
[sol,fval,exitflag,output] = linprog(problem)
Optimal solution found.
sol = 2×1
0.1875
1.2500
fval = -0.6042
exitflag = 1
output = struct with fields:
iterations: 1
constrviolation: 0
message: 'Optimal solution found.'
algorithm: 'dual-simplex'
firstorderopt: 0
El valor fval
devuelto es negativo, aunque los componentes de la solución sean positivos. Internamente, prob2struct
convierte el problema de maximización en un problema de minimización del negativo de la función objetivo. Consulte Maximizar un objetivo.
¿Qué componente de sol
corresponde a qué variable de optimización? Examine la propiedad Variables
de prob
.
prob.Variables
ans = struct with fields:
x: [1x1 optim.problemdef.OptimizationVariable]
y: [1x1 optim.problemdef.OptimizationVariable]
Como cabe esperar, sol(1)
corresponde a x
y sol(2)
corresponde a y
. Consulte Algorithms.
Devolver el valor de la función objetivo
Calcule el valor de la solución y de la función objetivo para un programa lineal simple.
Las restricciones de desigualdad son
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
La función objetivo es .
f = [-1 -1/3];
Resuelva el problema y devuelva el valor de la función objetivo.
[x,fval] = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
fval = -1.1111
Obtener más salidas para examinar el proceso de resolución
Obtenga el indicador de salida y la estructura de salida para comprender mejor el proceso de resolución y la calidad.
Para este ejemplo, utilice estas restricciones de desigualdad lineales:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Utilice la restricción de igualdad lineal .
Aeq = [1 1/4]; beq = 1/2;
Establezca estos límites:
lb = [-1,-0.5]; ub = [1.5,1.25];
Utilice la función objetivo .
f = [-1 -1/3];
Establezca opciones para utilizar el algoritmo 'dual-simplex'
.
options = optimoptions('linprog','Algorithm','dual-simplex');
Resuelva el programa lineal y solicite el valor de la función, el indicador de salida y la estructura de salida.
[x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb,ub,options)
Optimal solution found.
x = 2×1
0.1875
1.2500
fval = -0.6042
exitflag = 1
output = struct with fields:
iterations: 1
constrviolation: 0
message: 'Optimal solution found.'
algorithm: 'dual-simplex'
firstorderopt: 0
fval
, el valor de la función objetivo, es mayor que Devolver el valor de la función objetivo porque hay más restricciones.exitflag
= 1 indica que la solución es fiable.output.iterations
= 0 indica quelinprog
ha encontrado la solución durante la prerresolución y no ha tenido que iterar en absoluto.
Obtener la solución y los multiplicadores de Lagrange
Resuelva un programa lineal simple y examine la solución y los multiplicadores de Lagrange.
Utilice la función objetivo
f = [-5; -4; -6];
Utilice las restricciones de desigualdad lineales
A = [1 -1 1 3 2 4 3 2 0]; b = [20;42;30];
Restrinja todas las variables para que sean positivas:
lb = zeros(3,1);
Establezca Aeq
y beq
en []
, lo que indica que no hay restricciones de igualdad lineales.
Aeq = []; beq = [];
Llame a linprog
para obtener los multiplicadores de Lagrange.
[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb);
Optimal solution found.
Examine la solución y los multiplicadores de Lagrange.
x,lambda.ineqlin,lambda.lower
x = 3×1
0
15
3
ans = 3×1
0
1.5000
0.5000
ans = 3×1
1
0
0
lambda.ineqlin
es distinto de cero para el segundo y tercer componente de x
. Esto indica que la segunda y la tercera restricción de desigualdad lineal se satisfacen con igualdades:
Compruebe que esto sea cierto:
A*x
ans = 3×1
-12
42
30
lambda.lower
es distinto de cero para el primer componente de x
. Esto indica que x(1)
se encuentra en su límite inferior de 0.
Argumentos de entrada
f
— Vector de coeficientes
vector real | arreglo real
Vector de coeficientes, especificado como un vector real o un arreglo real. El vector de coeficientes representa la función objetivo f'*x
. La notación asume que f
es un vector columna, pero puede utilizar un vector fila o un arreglo. Internamente, linprog
convierte f
en el vector columna f(:)
.
Ejemplo: f = [1,3,5,-6]
Tipos de datos: double
A
— Restricciones de desigualdad lineales
matriz real
Restricciones de desigualdad lineales, especificadas como una matriz real. A
es una matriz de M
por N
, donde M
es el número de desigualdades y N
es el número de variables (longitud de f
). Para problemas grandes, pase A
como una matriz dispersa.
A
codifica las M
desigualdades lineales
A*x <= b
,
donde x
es el vector columna de N
variables x(:)
y b
es un vector columna con M
elementos.
Por ejemplo, considere estas desigualdades:
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
Especifique las desigualdades introduciendo las siguientes restricciones.
A = [1,2;3,4;5,6]; b = [10;20;30];
Ejemplo: Para especificar que los componentes de x suman 1 o menos, tome A = ones(1,N)
y b = 1
.
Tipos de datos: double
Aeq
— Restricciones de igualdad lineales
matriz real
Restricciones de igualdad lineales, especificadas como una matriz real. Aeq
es una matriz de Me
por N
, donde Me
es el número de igualdades y N
es el número de variables (longitud de f
). Para problemas grandes, pase Aeq
como una matriz dispersa.
Aeq
codifica las Me
igualdades lineales
Aeq*x = beq
,
donde x
es el vector columna de N
variables x(:)
y beq
es un vector columna con Me
elementos.
Por ejemplo, considere estas igualdades:
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.
Especifique las igualdades introduciendo las siguientes restricciones.
Aeq = [1,2,3;2,4,1]; beq = [10;20];
Ejemplo: Para especificar que los componentes de x suman 1, tome Aeq = ones(1,N)
y beq = 1
.
Tipos de datos: double
b
— Restricciones de desigualdad lineales
vector real
Restricciones de desigualdad lineales, especificadas como un vector real. b
es un vector de M
elementos relacionado con la matriz A
. Si pasa b
como un vector fila, los solvers convierten internamente b
en el vector columna b(:)
. Para problemas grandes, pase b
como un vector disperso.
b
codifica las M
desigualdades lineales
A*x <= b
,
donde x
es el vector columna de N
variables x(:)
y A
es una matriz de tamaño M
por N
.
Por ejemplo, considere estas desigualdades:
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
Especifique las desigualdades introduciendo las siguientes restricciones.
A = [1,2;3,4;5,6]; b = [10;20;30];
Ejemplo: Para especificar que los componentes de x suman 1 o menos, utilice A = ones(1,N)
y b = 1
.
Tipos de datos: double
beq
— Restricciones de igualdad lineales
vector real
Restricciones de igualdad lineales, especificadas como un vector real. beq
es un vector de Me
elementos relacionado con la matriz Aeq
. Si pasa beq
como un vector fila, los solvers convierten internamente beq
en el vector columna beq(:)
. Para problemas grandes, pase beq
como un vector disperso.
beq
codifica las Me
igualdades lineales
Aeq*x = beq
,
donde x
es el vector columna de N
variables x(:)
y Aeq
es una matriz de tamaño Me
por N
.
Por ejemplo, considere estas igualdades:
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.
Especifique las igualdades introduciendo las siguientes restricciones.
Aeq = [1,2,3;2,4,1]; beq = [10;20];
Ejemplo: Para especificar que los componentes de x suman 1, utilice Aeq = ones(1,N)
y beq = 1
.
Tipos de datos: double
lb
— Límites inferiores
vector real | arreglo real
Límites inferiores, especificados como un vector real o un arreglo real. Si la longitud de f
es igual a la longitud de lb
, entonces lb
especifica que
x(i) >= lb(i)
para todo i
.
Si numel(lb) < numel(f)
, entonces lb
especifica que
x(i) >= lb(i)
para 1 <= i <= numel(lb)
.
En este caso, los solvers emiten una advertencia.
Ejemplo: Para especificar que todos los componentes de x son positivos, utilice lb = zeros(size(f))
.
Tipos de datos: double
ub
— Límites superiores
vector real | arreglo real
Límites superiores, especificados como un vector real o un arreglo real. Si la longitud de f
es igual a la longitud de ub
, entonces ub
especifica que
x(i) <= ub(i)
para todo i
.
Si numel(ub) < numel(f)
, entonces ub
especifica que
x(i) <= ub(i)
para 1 <= i <= numel(ub)
.
En este caso, los solvers emiten una advertencia.
Ejemplo: Para especificar que todos los componentes de x son menores que 1
, utilice ub = ones(size(f))
.
Tipos de datos: double
options
— Opciones de optimización
salida de optimoptions
| estructura como la que devuelve optimset
Opciones de optimización, especificadas como la salida de optimoptions
o una estructura como la que devuelve optimset
.
Algunas opciones son aplicables a todos los algoritmos y otras son relevantes para algoritmos particulares. Consulte Referencia de opciones de optimización para ver información detallada.
Algunas opciones no aparecen en la visualización optimoptions
. Estas opciones se muestran en cursiva en la siguiente tabla. Para obtener más detalles, consulte Consultar las opciones de optimización.
Todos los algoritmos | |
Algorithm | Escoja el algoritmo de optimización:
Para obtener información sobre cómo elegir el algoritmo, consulte Algoritmos de programación lineal. |
Diagnóstico | Muestre información de diagnóstico sobre la función que se desea minimizar o resolver. Escoja |
| Nivel de visualización (consulte Visualización iterativa):
|
| Número máximo de iteraciones permitidas, un entero positivo. La opción predeterminada es:
Consulte Tolerancias y criterios de detención y Iteraciones y recuentos de la función. Para |
| Tolerancia de terminación en la factibilidad dual, un escalar positivo. La opción predeterminada es:
Para |
Algoritmo interior-point | |
ConstraintTolerance | Tolerancia de factibilidad para restricciones, un escalar no negativo. Para |
Algoritmo dual simplex | |
ConstraintTolerance | Tolerancia de factibilidad para restricciones, un escalar de Para |
MaxTime | Tiempo máximo en segundos durante el que se ejecuta el algoritmo. La opción predeterminada es |
Preproceso | Nivel de preprocesamiento LP anterior a las iteraciones del algoritmo dual simplex. Especifique |
Ejemplo: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')
problem
— Estructura de problema
estructura
Estructura de problema, especificada como una estructura con los siguientes campos.
Nombre de campo | Entrada |
---|---|
| Vector de función objetivo lineal f |
| Matriz para restricciones de desigualdad lineales |
| Vector para restricciones de desigualdad lineales |
| Matriz para restricciones de igualdad lineales |
| Vector para restricciones de igualdad lineales |
lb | Vector de límites inferiores |
ub | Vector de límites superiores |
| 'linprog' |
| Opciones creadas con optimoptions |
Debe proporcionar al menos el campo solver
en la estructura problem
.
Tipos de datos: struct
Argumentos de salida
x
— Solución
vector real | arreglo real
Solución, devuelta como un vector real o un arreglo real. El tamaño de x
es el mismo que el tamaño de f
.
fval
— Valor de la función objetivo en la solución
número real
Valor de la función objetivo en la solución, devuelto como un número real. Por lo general, fval
= f'*x
.
exitflag
— Razón por la que linprog
se ha detenido
valor entero
Razón por la que linprog
se ha detenido, devuelta como un entero.
| La solución es factible con respecto a la tolerancia |
| La función ha convergido a una solución |
| El número de iteraciones ha sobrepasado |
| No se ha encontrado ningún punto factible. |
| El problema está desacotado. |
| Se ha encontrado el valor |
| Ni el problema primal ni el dual son factibles. |
| La dirección de búsqueda se ha vuelto demasiado pequeña. No se puede seguir progresando. |
| El solver ha perdido factibilidad. |
Los exitflag 3
y -9
están relacionados con soluciones que tienen infactibilidades amplias. Estas normalmente surgen de matrices de restricciones lineales que tienen un elevado número de condiciones, o de problemas que tienen un elevado número de componentes de solución. Para corregir estos problemas, intente escalar las matrices de coeficientes, eliminar las restricciones lineales redundantes o establecer límites más estrictos en las variables.
output
— Información sobre el proceso de optimización
estructura
Información sobre el proceso de optimización, devuelta como estructura con estos campos.
iterations | Número de iteraciones |
algorithm | Algoritmo de optimización utilizado |
cgiterations | 0 (solo algoritmo interior-point, incluido para retrocompatibilidad) |
message | Mensaje de salida |
constrviolation | Máximo de funciones de restricción |
firstorderopt | Medida de optimalidad de primer orden |
lambda
— Multiplicadores de Lagrange en la solución
estructura
Multiplicadores de Lagrange en la solución, devueltos como estructura con estos campos.
lower | Límites inferiores que corresponden a |
upper | Límites superiores que corresponden a |
ineqlin | |
eqlin |
Los multiplicadores de Lagrange para restricciones lineales satisfacen esta ecuación con componentes length(f)
:
basado en el lagrangiano
Esta convención de signos coincide con la de los solvers no lineales (consulte Teoría de optimalidad restringida). No obstante, este signo es el contrario del signo de mucha de la literatura de programación lineal, por lo que un multiplicador de Lagrange de linprog
es el negativo del "precio sombra" asociado.
Algoritmos
Algoritmo dual simplex
Para obtener una descripción, consulte Dual-Simplex-Legacy Algorithm.
Algoritmo Interior-Point-Legacy
El método 'interior-point-legacy'
se basa en LIPSOL (Linear Interior Point Solver, [3]), que es una variante del algoritmo predictor-corrector de Mehrotra [2], un método primal-dual de punto interior. Tienen lugar varios pasos de preprocesamiento antes de que el algoritmo comience a iterar. Consulte Interior-Point-Legacy Linear Programming.
Es posible que la primera fase del algoritmo implique cierto preprocesamiento de las restricciones (consulte Interior-Point-Legacy Linear Programming). Varias condiciones pueden provocar que linprog
salga con un mensaje de infactibilidad. En cada caso, linprog
devuelve un exitflag
negativo para indicar el fallo.
Si en
Aeq
se detecta una fila de ceros, pero el elemento correspondiente debeq
no es cero, el mensaje de salida esExiting due to infeasibility: An all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry.
Si se detecta que uno de los elementos de
x
no está acotado debajo, el mensaje de salida esExiting due to infeasibility: Objective f'*x is unbounded below.
Si una de las filas de
Aeq
solo tiene un elemento distinto de cero, entonces el valor asociado enx
se llama variable singleton. En este caso, el valor de ese componente dex
puede calcularse a partir deAeq
ybeq
. Si el valor calculado vulnera otra restricción, el mensaje de salida esExiting due to infeasibility: Singleton variables in equality constraints are not feasible.
Si la variable singleton puede resolverse, pero la solución vulnera los límites superiores o inferiores, el mensaje de salida es
Exiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.
Nota
Los pasos de preprocesamiento son acumulativos. Por ejemplo, incluso aunque en un principio la matriz de restricción no tenga una fila de ceros, otros pasos de preprocesamiento pueden provocar que aparezca una fila de este tipo.
Cuando el preprocesamiento finaliza, la parte iterativa del algoritmo comienza hasta que se cumplen los criterios de detención. (Para obtener más información sobre valores residuales, el problema primal, el problema dual y los criterios de detención relacionados, consulte Interior-Point-Legacy Linear Programming). Si los valores residuales aumentan en lugar de reducirse, o si los valores residuales no aumentan ni disminuyen, se muestra uno de los dos mensajes de terminación siguientes,
One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far:
o
One or more of the residuals, duality gap, or total relative error has stalled:
Después de que se haya mostrado uno de estos mensajes, aparece uno de los siguientes mensajes que indican que el dual, el primal o ambos no son factibles.
The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)
The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)
The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.
The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.
Both the primal and the dual appear to be infeasible.
Por ejemplo, el (objetivo) primal puede estar desacotado y el valor residual primal, que es la medida de la satisfacción de la restricción primal, puede ser pequeño.
Algoritmo interior-point
El algoritmo 'interior-point'
es similar al algoritmo 'interior-point-legacy'
, pero con una rutina de factorización mucho más eficaz y con preprocesamiento diferente. Consulte Interior-Point linprog Algorithm.
Funcionalidad alternativa
App
La tarea Optimize de Live Editor proporciona una interfaz visual para linprog
.
Referencias
[1] Dantzig, G.B., A. Orden, and P. Wolfe. “Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints.” Pacific Journal Math., Vol. 5, 1955, pp. 183–195.
[2] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp. 575–601.
[3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment.” Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.
Historial de versiones
Introducido antes de R2006a
Consulte también
intlinprog
| mpsread
| optimoptions
| prob2struct
| quadprog
| Optimize
Comando de MATLAB
Ha hecho clic en un enlace que corresponde a este comando de MATLAB:
Ejecute el comando introduciéndolo en la ventana de comandos de MATLAB. Los navegadores web no admiten comandos de MATLAB.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)