Main Content

La traducción de esta página está obsoleta. Haga clic aquí para ver la última versión en inglés.

linprog

Resuelva problemas de programación lineal

Descripción

Solver de programación lineal

Encuentra el mínimo de un problema especificado por

minxfTx such that {Axb,Aeqx=beq,lbxub.

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.

ejemplo

x = linprog(f,A,b) resuelve el mínimo de f'*x de forma que A*x b.

ejemplo

x = linprog(f,A,b,Aeq,beq) incluye restricciones de igualdad Aeq*x = beq. Establezca A = [] y b = [] si no existen desigualdades.

ejemplo

x = linprog(f,A,b,Aeq,beq,lb,ub) define un conjunto de límites inferiores y superiores en las variables de diseño, 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 [].

ejemplo

x = linprog(f,A,b,Aeq,beq,lb,ub,options) minimiza con las opciones de optimización especificadas por options. Utilice optimoptions para configurar estas opciones.

ejemplo

x = linprog(problem) encuentra el mínimo para 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.

ejemplo

[x,fval] = linprog(___), para cualquier argumento de entrada, devuelve el valor de la función objetivo fun en la solución x: fval = f'*x.

ejemplo

[x,fval,exitflag,output] = linprog(___) devuelve adicionalmente un valor exitflag que describe la condición de salida y una estructura output que contiene información sobre el proceso de optimización.

ejemplo

[x,fval,exitflag,output,lambda] = linprog(___) devuelve adicionalmente una estructura lambda cuyos campos contienen los multiplicadores de Lagrange en la solución x.

Ejemplos

contraer todo

Resuelva un programa lineal simple definido por desigualdades lineales.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 -x(1)-x(2)/3.

f = [-1 -1/3];

Resuelva el programa lineal.

x = linprog(f,A,b)
Optimal solution found.
x = 2×1

    0.6667
    1.3333

Resuelva un programa lineal simple definido por desigualdades e igualdades lineales.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 x(1)+x(2)/4=1/2.

Aeq = [1 1/4];
beq = 1/2;

Utilice la función objetivo -x(1)-x(2)/3.

f = [-1 -1/3];

Resuelva el programa lineal.

x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1

     0
     2

Resuelva un programa lineal simple con desigualdades lineales, igualdades lineales y límites.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 x(1)+x(2)/4=1/2.

Aeq = [1 1/4];
beq = 1/2;

Establezca estos límites:

-1x(1)1.5

-0.5x(2)1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Utilice la función objetivo -x(1)-x(2)/3.

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

Resuelva un programa lineal con el algoritmo 'interior-point'.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 x(1)+x(2)/4=1/2.

Aeq = [1 1/4];
beq = 1/2;

Establezca estos límites:

-1x(1)1.5

-0.5x(2)1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Utilice la función objetivo -x(1)-x(2)/3.

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 selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.
x = 2×1

    0.1875
    1.2500

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

maxx(x+y/3)subjectto{x+y2x+y/41x-y2x/4+y-1x+y1-x+y2x+y/4=1/2-1x1.5-1/2y1.25

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.

Calcule el valor de la solución y de la función objetivo para un programa lineal simple.

Las restricciones de desigualdad son

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 -x(1)-x(2)/3.

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

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:

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)2.

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 x(1)+x(2)/4=1/2.

Aeq = [1 1/4];
beq = 1/2;

Establezca estos límites:

-1x(1)1.5

-0.5x(2)1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Utilice la función objetivo -x(1)-x(2)/3.

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 que linprog ha encontrado la solución durante la prerresolución y no ha tenido que iterar en absoluto.

Resuelva un programa lineal simple y examine la solución y los multiplicadores de Lagrange.

Utilice la función objetivo

f(x)=-5x1-4x2-6x3.

f = [-5; -4; -6];

Utilice las restricciones de desigualdad lineales

x1-x2+x320

3x1+2x2+4x342

3x1+2x230.

A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20;42;30];

Restrinja todas las variables para que sean positivas:

x10

x20

x30.

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.0000
    3.0000

ans = 3×1

         0
    1.5000
    0.5000

ans = 3×1

    1.0000
         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:

3x1+2x2+4x3=42

3x1+2x2=30.

Compruebe que esto sea cierto:

A*x
ans = 3×1

  -12.0000
   42.0000
   30.0000

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

contraer todo

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

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

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

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

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

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

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

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 Optimization Options Reference 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 Visualizar opciones.

Todos los algoritmos
Algorithm

Escoja el algoritmo de optimización:

  • 'dual-simplex' (valor predeterminado)

  • 'interior-point-legacy'

  • 'interior-point'

Para obtener información sobre cómo elegir el algoritmo, consulte Linear Programming Algorithms.

Diagnóstico

Muestre información de diagnóstico sobre la función que se desea minimizar o resolver. Escoja 'off' (predeterminada) o 'on'.

Display

Nivel de visualización (consulte Iterative Display):

  • 'final' (predeterminada) solo muestra la salida final.

  • 'off' o 'none' no muestran salida alguna.

  • 'iter' muestra la salida en cada iteración.

MaxIterations

Número máximo de iteraciones permitidas, un entero positivo. La opción predeterminada es:

  • 85 para el algoritmo 'interior-point-legacy'

  • 200 para el algoritmo 'interior-point'

  • 10*(numberOfEqualities + numberOfInequalities + numberOfVariables) para el algoritmo 'dual-simplex'

Consulte Tolerancias y criterios de detención y Iteraciones y recuentos de la función.

Para optimset, el nombre es MaxIter. Consulte Nombres de opciones actuales y antiguos.

OptimalityTolerance

Tolerancia de terminación en la factibilidad dual, un escalar positivo. La opción predeterminada es:

  • 1e-8 para el algoritmo 'interior-point-legacy'

  • 1e-7 para el algoritmo 'dual-simplex'

  • 1e-6 para el algoritmo 'interior-point'

Para optimset, el nombre es TolFun. Consulte Nombres de opciones actuales y antiguos.

Algoritmo interior-point
ConstraintTolerance

Tolerancia de factibilidad para restricciones, un escalar de 1e-10 a 1e-3. ConstraintTolerance mide la tolerancia de factibilidad primal. La opción predeterminada es 1e-6.

Para optimset, el nombre es TolCon. Consulte Nombres de opciones actuales y antiguos.

Preproceso

Nivel de preprocesamiento LP anterior a las iteraciones del algoritmo. Especifique 'basic' (predeterminada) o 'none'.

Algoritmo dual simplex
ConstraintTolerance

Tolerancia de factibilidad para restricciones, un escalar de 1e-10 a 1e-3. ConstraintTolerance mide la tolerancia de factibilidad primal. La opción predeterminada es 1e-4.

Para optimset, el nombre es TolCon. Consulte Nombres de opciones actuales y antiguos.

MaxTime

Tiempo máximo en segundos durante el que se ejecuta el algoritmo. La opción predeterminada es Inf.

Preproceso

Nivel de preprocesamiento LP anterior a las iteraciones del algoritmo dual simplex. Especifique 'basic' (predeterminada) o 'none'.

Ejemplo: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')

Estructura de problema, especificada como una estructura con los siguientes campos.

Nombre de campoEntrada

f

Vector de función objetivo lineal f

Aineq

Matriz para restricciones de desigualdad lineales

bineq

Vector para restricciones de desigualdad lineales

Aeq

Matriz para restricciones de igualdad lineales

beq

Vector para restricciones de igualdad lineales
lbVector de límites inferiores
ubVector de límites superiores

solver

'linprog'

options

Opciones creadas con optimoptions

Debe proporcionar al menos el campo solver en la estructura problem.

Tipos de datos: struct

Argumentos de salida

contraer todo

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.

Valor de la función objetivo en la solución, devuelto como un número real. Por lo general, fval = f'*x.

Razón por la que linprog se ha detenido, devuelta como un entero.

3

La solución es factible con respecto a la tolerancia ConstraintTolerance relativa, pero no es factible en lo que respecta a la tolerancia absoluta.

1

La función ha convergido a una solución x.

0

El número de iteraciones ha sobrepasado options.MaxIterations o el tiempo de resolución en segundos ha sobrepasado options.MaxTime.

-2

No se ha encontrado ningún punto factible.

-3

El problema está desacotado.

-4

Se ha encontrado el valor NaN durante la ejecución del algoritmo.

-5

Ni el problema primal ni el dual son factibles.

-7

La dirección de búsqueda se ha vuelto demasiado pequeña. No se han podido hacer más progresos.

-9

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.

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

Multiplicadores de Lagrange en la solución, devueltos como estructura con estos campos.

lower

Límites inferiores que corresponden a lb

upper

Límites superiores que corresponden a ub

ineqlin

Desigualdades lineales que corresponden a A y b

eqlin

Igualdades lineales que corresponden a Aeq y beq

Los multiplicadores de Lagrange para restricciones lineales satisfacen esta ecuación con componentes length(f):

f+ATλineqlin+AeqTλeqlin+λupperλlower=0,

basado en el lagrangiano

fTx+λineqlinT(Axb)+λeqlinT(Aeqxbeq)+λupperT(xub)+λlowerT(lbx).

Esta convención de signos coincide con la de los solvers no lineales (consulte Constrained Optimality Theory). 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

contraer todo

Algoritmo dual simplex

Para obtener una descripción, consulte Dual-Simplex 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 de beq no es cero, el mensaje de salida es

    Exiting 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 es

    Exiting 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 en x se llama variable singleton. En este caso, el valor de ese componente de x puede calcularse a partir de Aeq y beq. Si el valor calculado vulnera otra restricción, el mensaje de salida es

    Exiting 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