Main Content

La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

intlinprog

Programación lineal de enteros mixtos (MILP)

Descripción

Solver de programación lineal de enteros mixta.

Encuentra el mínimo de un problema especificado por

minxfTx subject to {x(intcon) are integersAxbAeqx=beqlbxub.

f, x, intcon, b, beq, lb y ub son vectores, y A y Aeq son matrices.

Puede especificar f, intcon, lb y ub como vectores o arreglos. Consulte Argumentos de matriz.

Nota

intlinprog 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 = intlinprog(f,intcon,A,b) resuelve min f'*x de forma que los componentes de x en intcon son enteros y que A*x ≤ b.

x = intlinprog(f,intcon,A,b,Aeq,beq) resuelve el problema anterior y satisface, al mismo tiempo, las restricciones de igualdad Aeq*x = beq. Establezca A = [] y b = [] si no existen desigualdades.

ejemplo

x = intlinprog(f,intcon,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.

ejemplo

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) optimiza utilizando un punto factible inicial x0. Establezca lb = [] y ub = [], si no existen límites.

ejemplo

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) minimiza utilizando las opciones de optimización que se especifican en options. Utilice optimoptions para configurar estas opciones. Establezca x0 = [], si no existe ningún punto inicial.

ejemplo

x = intlinprog(problem) utiliza una estructura problem para encapsular todas las entradas de solver. 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,exitflag,output] = intlinprog(___), para cualquiera de los argumentos de entrada que se describen arriba, devuelve fval = f'*x, un valor exitflag que describe la condición de salida, y una estructura output que contiene información sobre el proceso de optimización.

Ejemplos

contraer todo

Resuelva el problema

minx8x1+x2subjectto{x2isanintegerx1+2x2-14-4x1-x2-332x1+x220.

Escriba el vector de función objetivo y el vector de variables enteras.

f = [8;1];
intcon = 2;

Convierta todas las desigualdades al formato A*x <= b multiplicando las desigualdades "mayor que" por -1.

A = [-1,-2;
    -4,-1;
    2,1];
b = [14;-33;20];

Llame a intlinprog.

x = intlinprog(f,intcon,A,b)
LP:                Optimal objective value is 59.000000.                                            


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x = 2×1

    6.5000
    7.0000

Resuelva el problema

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+2x2+x3=12.

Escriba el vector de función objetivo y el vector de variables enteras.

f = [-3;-2;-1];
intcon = 3;

Escriba las restricciones de desigualdad lineales.

A = [1,1,1];
b = 7;

Escriba las restricciones de igualdad lineales.

Aeq = [4,2,1];
beq = 12;

Escriba las restricciones de límite.

lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binary

Llame a intlinprog.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x = 3×1

         0
    5.5000
    1.0000

Compare el número de saltos para resolver un problema de programación de enteros tanto con un punto factible inicial como sin él. El problema tiene ocho variables y cuatro restricciones de igualdad lineales, y tiene todas las variables restringidas para ser positivas.

Defina la matriz y el vector de igualdad lineales.

Aeq = [22    13    26    33    21     3    14    26
    39    16    22    28    26    30    23    24
    18    14    29    27    30    38    26    26
    41    26    28    36    18    38    16    26];
beq = [ 7872
       10466
       11322
       12058];

Establezca límites inferiores que restrinjan todas las variables para que sean no negativas.

N = 8;
lb = zeros(N,1);

Especifique que todas las variables son valores enteros.

intcon = 1:N;

Establezca el vector de función objetivo f.

f = [2    10    13    17     7     5     7     3];

Resuelva el problema sin utilizar un punto inicial y examine la visualización para ver el número de nodos de ramificación y acotación.

[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1591.000000.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.83         0              -              -                                          
   18025      1.19         1   2.906000e+03   4.509804e+01                                          
   21857      1.43         2   2.073000e+03   2.270974e+01                                          
   23544      1.53         3   1.854000e+03   1.180593e+01                                          
   24097      1.57         3   1.854000e+03   1.617251e+00                                          
   24293      1.58         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

Encuentre la solución utilizando un punto factible inicial y compare.

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1591.000000.                                                      
                   Relative gap is 59.20%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    3627      0.42         2   2.154000e+03   2.593968e+01                                          
    5844      0.54         3   1.854000e+03   1.180593e+01                                          
    6204      0.56         3   1.854000e+03   1.455526e+00                                          
    6400      0.57         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
  • Sin un punto inicial, intlinprog necesitó unos 30.000 saltos de ramificación y acotación.

  • Con un punto inicial, intlinprog necesitó unos 5.000 saltos.

Proporcionar un punto inicial no siempre ayuda. Para este problema, proporcionar un punto inicial ahorra tiempo y saltos computacionales. Sin embargo, para algunos problemas, proporcionar un punto inicial puede provocar que intlinprog dé más saltos.

Resuelva el problema

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+2x2+x3=12

sin mostrar una visualización iterativa.

Especifique las entradas del solver.

f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary
x0 = [];

No especifique ninguna visualización.

options = optimoptions('intlinprog','Display','off');

Ejecute el solver.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)
x = 3×1

         0
    5.5000
    1.0000

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

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+2x2+x3=12

Cree un objeto OptimizationProblem llamado prob para representar este problema. Para especificar una variable binaria, cree una variable de optimización con tipo de entero, un límite inferior de 0 y un límite superior de 1.

x = optimvar('x',2,'LowerBound',0);
xb = optimvar('xb','LowerBound',0,'UpperBound',1,'Type','integer');
prob = optimproblem('Objective',-3*x(1)-2*x(2)-xb);
cons1 = sum(x) + xb <= 7;
cons2 = 4*x(1) + 2*x(2) + xb == 12;
prob.Constraints.cons1 = cons1;
prob.Constraints.cons2 = cons2;

Convierta el objeto de problema en una estructura de problema.

problem = prob2struct(prob);

Resuelva la estructura de problema resultante.

[sol,fval,exitflag,output] = intlinprog(problem)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sol = 3×1

         0
    5.5000
    1.0000

fval = -12
exitflag = 1
output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'

Tanto sol(1) como sol(3) tienen valores binarios. ¿Qué valor corresponde a la variable de optimización binaria xb?

prob.Variables
ans = struct with fields:
     x: [2x1 optim.problemdef.OptimizationVariable]
    xb: [1x1 optim.problemdef.OptimizationVariable]

La variable xb aparece la última en la visualización Variables, por lo que xb se corresponde con sol(3) = 1. Consulte Algorithms.

Llame a intlinprog con más salidas para ver los detalles de la resolución y del proceso.

El objetivo es resolver el problema

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+2x2+x3=12.

Especifique las entradas del solver.

f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary

Llame a intlinprog con todas las salidas.

[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x = 3×1

         0
    5.5000
    1.0000

fval = -12
exitflag = 1
output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'

La estructura de salida muestra que numnodes es 0. Esto significa que intlinprog resolvió el problema antes de ramificar. Es una indicación de que el resultado es fiable. Asimismo, los campos absolutegap y relativegap son 0. Esta es otra indicación de que el resultado es fiable.

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 usted es libre de utilizar un vector fila o un arreglo. Internamente, linprog convierte f en el vector columna f(:).

Si especifica f = [], intlinprog trata de encontrar un punto factible sin intentar minimizar una función objetivo.

Ejemplo: f = [4;2;-1.7];

Tipos de datos: double

Vector de restricciones de enteros, especificado como un vector de enteros positivos. Los valores de intcon indican los componentes de la variable de decisión x que son valores enteros. intcon tiene valores de 1 a numel(f).

intcon también puede ser un arreglo. Internamente, intlinprog convierte un arreglo intcon en el vector intcon(:).

Ejemplo: intcon = [1,2,7] significa que x(1), x(2) y x(7) solo toman valores enteros.

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 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 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 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 o un arreglo de dobles. lb representa los límites inferiores por elementos en lb x ub.

Internamente, intlinprog convierte un arreglo lb en el vector lb(:).

Ejemplo: lb = [0;-Inf;4] significa x(1) ≥ 0, x(3) ≥ 4.

Tipos de datos: double

Límites superiores, especificados como un vector o un arreglo de dobles. ub representa los límites superiores por elementos en lb x ub.

Internamente, intlinprog convierte un arreglo ub en el vector ub(:).

Ejemplo: ub = [Inf;4;10] significa x(2) ≤ 4, x(3) ≤ 10.

Tipos de datos: double

Punto inicial, especificado como un arreglo real. El número de elementos de x0 es el mismo que el número de elementos de f, cuando existe f. De lo contrario, el número es el mismo que el número de columnas de A o de Aeq. Internamente, el solver convierte un arreglo x0 en un vector x0(:).

Proporcionar x0 puede cambiar la cantidad de tiempo que necesita intlinprog para convergir. Es difícil predecir cómo x0 afecta al solver. Para sugerencias sobre cómo utilizar una Heuristics adecuada con x0, consulte Consejos.

x0 debe ser factible con respecto a todas las restricciones. Si x0 no es factible, el solver genera un error. Si no tiene un x0 factible, establezca x0 = [].

Ejemplo: x0 = 100*rand(size(f))

Tipos de datos: double

Opciones para intlinprog, especificadas como la salida de optimoptions.

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.

OpciónDescripciónValor predeterminado
AbsoluteGapTolerance

Valor real no negativo. intlinprog se detiene si la diferencia entre los límites superior (U) e inferior (L) calculados internamente en la función objetivo es menor que o igual a AbsoluteGapTolerance:

U – L <= AbsoluteGapTolerance.

0
BranchRule

Regla para escoger el componente para la ramificación:

  • 'maxpscost': el componente fraccional con el máximo pseudocoste. Consulte Branch and Bound.

  • 'strongpscost': el componente fraccional con el máximo pseudocoste y una estimación más precisa del pseudocoste que en 'maxpscost'. Consulte Branch and Bound.

  • 'reliability': el componente fraccional con el máximo pseudocoste y una estimación incluso más precisa del pseudocoste que en 'strongpscost'. Consulte Branch and Bound.

  • 'mostfractional': el componente cuya parte fraccional es la que más se acerca a 1/2.

  • 'maxfun': el componente fraccional con un componente correspondiente máximo en el valor absoluto del vector objetivo f.

'reliability'
ConstraintToleranceValor real de 1e-9 a 1e-3 que es la discrepancia máxima que pueden tener las restricciones lineales para que se sigan considerando satisfactorias. ConstraintTolerance no es un criterio de detención.1e-4
CutGeneration

Nivel de generación de corte (consulte Cut Generation):

  • 'none': ningún corte. Hace que CutMaxIterations sea irrelevante.

  • 'basic': generación de corte normal.

  • 'intermediate': utiliza más tipos de corte.

  • 'advanced': utiliza la mayoría de tipos de corte.

'basic'
CutMaxIterationsNúmero de pases por todos los métodos de generación de cortes antes de entrar en la fase de ramificación y acotamiento, un entero de 1 a 50. Deshabilite la generación de cortes estableciendo la opción CutGeneration en 'none'.10
Display

Nivel de visualización (consulte Iterative Display):

  • 'off' o 'none': sin visualización iterativa

  • 'final': muestra solo los valores finales

  • 'iter': muestra la visualización iterativa

'iter'
Heuristics

Algoritmo para buscar puntos factibles (consulte Heuristics for Finding Feasible Solutions):

  • 'basic'

  • 'intermediate'

  • 'advanced'

  • 'rss'

  • 'rins'

  • 'round'

  • 'diving'

  • 'rss-diving'

  • 'rins-diving'

  • 'round-diving'

  • 'none'

'basic'
HeuristicsMaxNodesEntero estrictamente positivo que limita el número de nodos que puede explorar intlinprog en su búsqueda de ramificación y acotación de puntos factibles. Se aplica únicamente a 'rss' y a 'rins'. Consulte Heuristics for Finding Feasible Solutions.50
IntegerPreprocess

Tipos de preprocesamiento de enteros (consulte Mixed-Integer Program Preprocessing):

  • 'none': utiliza muy pocos saltos de preprocesamiento de enteros.

  • 'basic': utiliza un número moderado de saltos de preprocesamiento de enteros.

  • 'advanced': utiliza todos los saltos de preprocesamiento de enteros disponibles.

'basic'
IntegerToleranceValor real de 1e-6 a 1e-3, donde se da la desviación máxima del entero que puede tener un componente de la solución x para que se siga considerando un entero. IntegerTolerance no es un criterio de detención.1e-5
LPMaxIterationsEntero estrictamente positivo, el número máximo de iteraciones de algoritmo simplex por nodo durante el proceso de ramificación y acotamiento.

max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))

En esta expresión, numberOfEqualities significa el número de filas de Aeq, numberOfInequalities significa el número de filas de A y numberOfVariables significa el número de elementos de f.

LPOptimalityToleranceValor real no negativo donde los costes reducidos deben superar LPOptimalityTolerance para que una variable se incorpore a la base.1e-7
LPPreprocess

Tipo de preprocesamiento para la solución al programa lineal relajado (consulte Linear Program Preprocessing):

  • 'none': sin preprocesamiento.

  • 'basic': utiliza preprocesamiento.

'basic'
MaxNodesEntero estrictamente positivo que es el número máximo de nodos que explora intlinprog en su proceso de ramificación y acotación.1e7
MaxFeasiblePointsEntero estrictamente positivo. intlinprog se detiene si encuentra MaxFeasiblePoints puntos factibles enteros.Inf
MaxTimeValor real positivo que es el tiempo máximo en segundos que se ejecuta intlinprog.7200
NodeSelection

Escoja el nodo que desea explorar a continuación.

  • 'simplebestproj': mejor proyección. Consulte Branch and Bound.

  • 'minobj': explora el nodo con la función objetivo mínima.

  • 'mininfeas': explora el nodo con la suma mínima de infactibilidades enteras. Consulte Branch and Bound.

'simplebestproj'
ObjectiveCutOffValor real mayor que -Inf. Durante el cálculo de ramificación y acotación, intlinprog descarta los nodos en los que la solución de programación lineal tiene un valor objetivo mayor que ObjectiveCutOff.Inf
ObjectiveImprovementThresholdValor real no negativo. intlinprog cambia la solución factible actual solo cuando ubica otra con un valor de función objetivo que es al menos menor que ObjectiveImprovementThreshold: (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold.0
OutputFcn

Una o más funciones que una función de optimización llama en eventos. Especifíquelas como 'savemilpsolutions', un identificador de función o un arreglo de celdas de identificadores de función. Para funciones de salida personalizadas, pase identificadores de función. Una función de salida puede detener el solver.

  • 'savemilpsolutions' recopila los puntos factibles enteros en la matriz xIntSol del espacio de trabajo, donde cada columna es un punto factible entero.

Para obtener más información sobre escribir una función de salida personalizada, consulte intlinprog Output Function and Plot Function Syntax.

[]
PlotFcn

Representa varias medidas de progreso mientras el algoritmo se ejecuta; seleccione una de las gráficas predefinidas o escriba la suya propia. Pase 'optimplotmilp', un identificador de función o un arreglo de celdas de identificadores de función. Para funciones de gráfica personalizadas, pase identificadores de función. La opción predeterminada es ninguno ([]):

  • 'optimplotmilp' representa los límites superiores e inferiores calculados internamente en el valor objetivo de la solución.

Para obtener más información sobre cómo escribir una función de gráfica personalizada, consulte intlinprog Output Function and Plot Function Syntax.

[]
RelativeGapTolerance

Valor real de 0 a 1. intlinprog se detiene si la diferencia relativa entre los límites superior (U) e inferior (L) calculados internamente en la función objetivo es menor que o igual a RelativeGapTolerance:

(U – L)/(|U| + 1) <= RelativeGapTolerance.

Nota

Aunque especifique RelativeGapTolerance como un número decimal, la visualización iterativa y output.relativegap indican el intervalo como un porcentaje, lo que significa 100 veces el intervalo relativo medido. Si el mensaje de salida se refiere al intervalo relativo, este valor es el intervalo relativo medido, no un porcentaje.

1e-4
RootLPAlgorithm

Algoritmo para resolver programas lineales:

  • 'dual-simplex': algoritmo dual simplex

  • 'primal-simplex': algoritmo primal simplex

'dual-simplex'
RootLPMaxIterationsEntero no negativo que es el número máximo de iteraciones del algoritmo simplex para resolver el problema de programación lineal inicial.

max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))

En esta expresión, numberOfEqualities significa el número de filas de Aeq, numberOfInequalities significa el número de filas de A y numberOfVariables significa el número de elementos de f.

Ejemplo: options = optimoptions('intlinprog','MaxTime',120)

Estructura que encapsula las entradas y las opciones, especificada con los siguientes campos.

fVector que representa f'*x objetivo (necesario)
intconVector que indica variables que toman valores enteros (necesario)
AineqMatriz en restricciones de desigualdad lineales Aineq*x bineq

bineq

Vector en restricciones de desigualdad lineales Aineq*x bineq

Aeq

Matriz en restricciones de igualdad lineales Aeq*x = beq

beq

Vector en restricciones de igualdad lineales Aeq*x = beq
lbVector de límites inferiores
ubVector de límites superiores
x0Punto factible inicial
solver'intlinprog' (necesario)

options

Opciones creadas utilizando optimoptions (necesario)

Debe especificar al menos estos campos en la estructura del problema. Otros campos son opcionales:

  • f

  • intcon

  • solver

  • options

Ejemplo: problem.f = [1,2,3];
problem.intcon = [2,3];
problem.options = optimoptions('intlinprog');
problem.Aineq = [-3,-2,-1];
problem.bineq = -20;
problem.lb = [-6.1,-1.2,7.3];
problem.solver = 'intlinprog';

Tipos de datos: struct

Argumentos de salida

contraer todo

Solución, devuelta como un vector que minimiza f'*x sujeto a todos los límites, restricciones de enteros y restricciones lineales.

Cuando un problema no es factible o está desacotado, x es [].

Valor objetivo, devuelto como el valor escalar f'*x en la solución x.

Cuando un problema no es factible o está desacotado, fval es [].

Condición de detención de algoritmo, devuelta como un entero que identifica la razón por la que el algoritmo se detuvo. A continuación, se enumeran los valores de exitflag y las razones correspondientes por las que intlinprog se detuvo.

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.

2

intlinprog se detuvo prematuramente. Punto factible inicial encontrado.

1

intlinprog ha convergido a la solución x.

0

intlinprog se detuvo prematuramente. No se ha encontrado ningún punto factible inicial.

-1

intlinprog detenido por una función de salida o una función de gráfica.

-2

No se ha encontrado ningún punto factible.

-3

El problema de LP de raíz está desacotado.

-9

El solver ha perdido factibilidad.

El mensaje de salida puede proporcionar información más detallada sobre la razón por la que intlinprog se detuvo, como sobrepasar la tolerancia.

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.

Resumen de un proceso de resolución, devuelto como una estructura que contiene información sobre el proceso de optimización.

relativegap

Diferencia de porcentaje relativa entre los límites superiores (U) e inferiores (L) de la función objetivo que calcula intlinprog en su algoritmo de ramificación y acotación.

relativegap = 100*(U - L) / (abs(U) + 1)

Si intcon = [], relativegap = [].

Nota

Aunque especifique RelativeGapTolerance como un número decimal, la visualización iterativa y output.relativegap indican el intervalo como un porcentaje, lo que significa 100 veces el intervalo relativo medido. Si el mensaje de salida se refiere al intervalo relativo, este valor es el intervalo relativo medido, no un porcentaje.

absolutegap

Diferencia entre los límites superiores e inferiores de la función objetivo que calcula intlinprog en su algoritmo de ramificación y acotación.

Si intcon = [], absolutegap = [].

numfeaspoints

Número de puntos factibles enteros encontrados.

Si intcon = [], numfeaspoints = []. Asimismo, si el problema relajado inicial no es factible, numfeaspoints = [].

numnodes

Número de nodos en el algoritmo de ramificación y acotación. Si se encontró la solución durante el preprocesamiento o durante los cortes iniciales, numnodes = 0.

Si intcon = [], numnodes = [].

constrviolation

Vulneración de restricciones que es positiva para las restricciones vulneradas.

constrviolation = max([0; norm(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-bi)])

message

Mensaje de salida.

Limitaciones

  • Con frecuencia, algunos componentes que supuestamente son valores enteros de la solución x(intCon) no son exactamente enteros. intlinprog considera como enteros todos los valores de solución dentro de la IntegerTolerance de un entero.

    Para redondear todos los supuestos enteros para que sean enteros exactos, utilice la función round.

    x(intcon) = round(x(intcon));

    Precaución

    Las soluciones de redondeo pueden provocar que la solución se convierta en no factible. Compruebe la factibilidad después del redondeo:

    max(A*x - b) % See if entries are not too positive, so have small infeasibility
    max(abs(Aeq*x - beq)) % See if entries are near enough to zero
    max(x - ub) % Positive entries are violated bounds
    max(lb - x) % Positive entries are violated bounds
  • intlinprog no exige que los componentes de la solución tengan valores enteros cuando sus valores absolutos sobrepasan 2.1e9. Cuando la solución tiene esos componentes, intlinprog le advierte. Si recibe esta advertencia, compruebe la solución para ver si los componentes que supuestamente tienen valores enteros de la solución están cerca de los enteros.

  • intlinprog no permite que los componentes del problema, como los coeficientes de f, A o ub, sobrepasen 1e25 en valor absoluto. Si intenta ejecutar intlinprog con un problema de ese tipo, intlinprog genera un error.

Sugerencias

  • Para especificar valores binarios, establezca que las variables sean enteros en intcon y proporcióneles límites inferiores de 0 y límites superiores de 1.

  • Ahorre memoria especificando las matrices de restricciones lineales dispersas A y Aeq. Sin embargo, no puede utilizar matrices dispersas para b y beq.

  • Si incluye un argumento x0, intlinprog utiliza este valor en la heurística 'rins' y en la heurística de inmersión guiada hasta que encuentra un punto factible entero mejor. Así, cuando proporciona x0, puede obtener buenos resultados estableciendo la opción 'Heuristics' en 'rins-diving' u otro ajuste que utiliza 'rins'.

  • Para proporcionar índices lógicos para componentes enteros, es decir, un vector binario en el que 1 indica un entero, convierta al formato intcon utilizando find. Por ejemplo:

    logicalindices = [1,0,0,1,1,0,0];
    intcon = find(logicalindices)
    intcon =
    
         1     4     5
  • intlinprog reemplaza a bintprog. Para actualizar código bintprog antiguo para utilizar intlinprog, realice los siguientes cambios:

    • Establezca intcon en 1:numVars, donde numVars es el número de variables del problema.

    • Establezca lb en zeros(numVars,1).

    • Establezca ub en ones(numVars,1).

    • Actualice todas las opciones relevantes. Utilice optimoptions para crear opciones para intlinprog.

    • Cambie la llamada a bintprog como sigue:

      [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options)
      % Change your call to:
      [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)

Funcionalidad alternativa

App

La tarea Optimize de Live Editor proporciona una interfaz visual para intlinprog.

Historial de versiones

Introducido en R2014a

expandir todo