Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

linprog

Resuelve problemas de programación lineal

Descripción

Solucionador de programación lineal

Busca el mínimo de un problema especificado por

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

,,,, y son vectores, y son matrices.fxbbeqlbubAAeq

Nota

linprog solo se aplica al enfoque basado en el solucionador. Para ver una explicación de los dos enfoques de optimización, consulte.Elija primero el enfoque basado en problemas o basado en Solver

ejemplo

x = linprog(f,A,b) resuelve min tal que ≤.f'*xA*x  b

ejemplo

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

ejemplo

x = linprog(f,A,b,Aeq,beq,lb,ub) define un conjunto de límites inferior y superior en las variables de diseño, de modo que la solución siempre esté en el intervalo.xlb ≤ x ≤ ub Establecer y si no existen ecualidades.Aeq = []beq = []

Nota

Si los límites de entrada especificados para un problema son incoherentes, la salida es.fval[]

ejemplo

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

ejemplo

x = linprog(problem) encuentra el mínimo para, donde se describe una estructura.problemproblemArgumentos de entrada

Cree la estructura exportando un problema desde la aplicación de optimización, como se describe en.problemExportar su trabajo Puede importar una estructura desde un archivo MPS utilizando.problemmpsread También puede crear una estructura a partir de un objeto mediante.problemOptimizationProblemprob2struct

ejemplo

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

ejemplo

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

ejemplo

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

Ejemplos

contraer todo

Resuelve un programa lineal simple definido por desigualdades lineales.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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 objetiva

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Resuelve el programa lineal.

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

    0.6667
    1.3333

Resuelve un programa lineal simple definido por desigualdades lineales y ecualidades lineales.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>=</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
</mrow>
</math>
.

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

Utilice la función objetiva

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Resuelve el programa lineal.

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

     0
     2

Resuelve un programa lineal simple con desigualdades lineales, ecualidades lineales y límites.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>=</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
</mrow>
</math>
.

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

Establezca estos límites:

<math display="block">
<mrow>
<mo>-</mo>
<mn>1</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>5</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mn>0</mn>
<mo>.</mo>
<mn>5</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>2</mn>
<mn>5</mn>
<mo>.</mo>
</mrow>
</math>

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

Utilice la función objetiva

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Resuelve el programa lineal.

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

    0.1875
    1.2500

Resuelve un programa lineal usando el algoritmo.'interior-point'

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>=</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
</mrow>
</math>
.

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

Establezca estos límites:

<math display="block">
<mrow>
<mo>-</mo>
<mn>1</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>5</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mn>0</mn>
<mo>.</mo>
<mn>5</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>2</mn>
<mn>5</mn>
<mo>.</mo>
</mrow>
</math>

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

Utilice la función objetiva

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Configure las opciones para utilizar el algoritmo.'interior-point'

options = optimoptions('linprog','Algorithm','interior-point');

Resuelve el programa lineal usando 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

En este ejemplo se muestra cómo configurar un problema mediante el enfoque basado en problemas y, a continuación, resolverlo mediante el enfoque basado en el solucionador. El problema es

<math display="block">
<mrow>
<munder>
<mrow>
<mi mathvariant="normal">max</mi>
</mrow>
<mrow>
<mi>x</mi>
</mrow>
</munder>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo>/</mo>
<mn>3</mn>
<mo stretchy="false">)</mo>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mspace width="0.5em"></mspace>
<mi>s</mi>
<mi>u</mi>
<mi>b</mi>
<mi>j</mi>
<mi>e</mi>
<mi>c</mi>
<mi>t</mi>
<mspace width="0.5em"></mspace>
<mi>t</mi>
<mi>o</mi>
<mspace width="0.5em"></mspace>
</mrow>
</mstyle>
</mrow>
<mrow>
<mo>{</mo>
<mrow>
<mtable columnalign="left left left left left left left left left left left left left left left left left left left left">
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo></mo>
<mn>2</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>-</mo>
<mi>y</mi>
<mo></mo>
<mn>2</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>/</mo>
<mn>4</mn>
<mo>+</mo>
<mi>y</mi>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo></mo>
<mn>1</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo></mo>
<mn>2</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo>/</mo>
<mn>4</mn>
<mo>=</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mo>-</mo>
<mn>1</mn>
<mo></mo>
<mi>x</mi>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>5</mn>
</mrow>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mrow>
<mo>-</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
<mo></mo>
<mi>y</mi>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>2</mn>
<mn>5</mn>
</mrow>
<mrow></mrow>
</mrow>
</mtd>
</mtr>
</mtable>
</mrow>
</mrow>
</mrow>
</math>

Cree un objeto denominado para representar este problema.OptimizationProblemprob

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 problemático en una estructura problemática.

problem = prob2struct(prob);

Resuelva la estructura del 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: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

El resultado es negativo, aunque los componentes de la solución son positivos.fval Internamente, convierte el problema de maximización en un problema de minimización del negativo de la función objetiva.prob2struct Ver.Maximizando un objetivo

¿Qué componente corresponde a qué variable de optimización?sol Examine la propiedad de.Variablesprob

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

Como es de esperar, corresponde a, y corresponde a.sol(1)xsol(2)y Ver.Algoritmos

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

Las restricciones de desigualdad son

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Resuelva el problema y devuelva el valor de la función objetiva.

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

    0.6667
    1.3333

fval = -1.1111 

Obtenga la marca de salida y la estructura de salida para comprender mejor el proceso de solución y la calidad.

Para este ejemplo, utilice estas restricciones de desigualdad lineales:

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>2</mn>
<mo>.</mo>
</mrow>
</math>

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

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>4</mn>
<mo>=</mo>
<mn>1</mn>
<mo>/</mo>
<mn>2</mn>
</mrow>
</math>
.

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

Establezca estos límites:

<math display="block">
<mrow>
<mo>-</mo>
<mn>1</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>5</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mo>-</mo>
<mn>0</mn>
<mo>.</mo>
<mn>5</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
<mo>.</mo>
<mn>2</mn>
<mn>5</mn>
<mo>.</mo>
</mrow>
</math>

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

Utilice la función objetiva

<math display="block">
<mrow>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>-</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>/</mo>
<mn>3</mn>
</mrow>
</math>
.

f = [-1 -1/3];

Configure las 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, la marca 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: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

  • , el valor de la función objetiva, es mayor que, porque hay más restricciones.fvalDevuelva el valor de función objetiva

  • = 1 indica que la solución es fiable.exitflag

  • = 0 indica que se encontró la solución durante el PRESOLVE, y no tenía que iterar en absoluto.output.iterationslinprog

Resuelve un programa lineal simple y examina la solución y los multiplicadores de Lagrange.

Utilice la función objetiva

<math display="block">
<mrow>
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo>-</mo>
<mn>5</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>-</mo>
<mn>4</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo>-</mo>
<mn>6</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</msub>
<mo>.</mo>
</mrow>
</math>

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

Utilice las restricciones de desigualdad lineales

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>-</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</msub>
<mo></mo>
<mn>2</mn>
<mn>0</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mn>3</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>4</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</msub>
<mo></mo>
<mn>4</mn>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mn>3</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo></mo>
<mn>3</mn>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

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

Restrinja todas las variables para que sean positivas:

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo></mo>
<mn>0</mn>
</mrow>
</math>

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo></mo>
<mn>0</mn>
</mrow>
</math>

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</msub>
<mo></mo>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

lb = zeros(3,1);

Establecer y a, indicando que no hay ninguna restricción de igualdad lineal.Aeqbeq[]

Aeq = []; beq = [];

Llama, obteniendo los multiplicadores de Lagrange.linprog

[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

es distinto de cero para los componentes segundo y tercero de.lambda.ineqlinx Esto indica que la segunda y la tercera restricción de desigualdad lineal se satisfacen con ecualidades:

<math display="block">
<mrow>
<mn>3</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>4</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</msub>
<mo>=</mo>
<mn>4</mn>
<mn>2</mn>
</mrow>
</math>

<math display="block">
<mrow>
<mn>3</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msub>
<mo>=</mo>
<mn>3</mn>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

Compruebe que esto es cierto:

A*x
ans = 3×1

  -12.0000
   42.0000
   30.0000

es distinto de cero para el primer componente de.lambda.lowerx Esto indica que está en su límite inferior de 0.x(1)

Argumentos de entrada

contraer todo

Vector de coeficiente, especificado como un vector real o una matriz real. El vector de coeficiente representa la función objetiva.f'*x La notación asume que es un vector de columna, pero usted es libre de utilizar un vector de fila o una matriz.f Internamente, convierte al vector de columna.linprogff(:)

Ejemplo: f = [1,3,5,-6]

Tipos de datos: double

Restricciones de desigualdad lineales, especificadas como una matriz real. es un-por-matriz, donde es el número de desigualdades, y es el número de variables (longitud de).AMNMNf Para problemas grandes, pase como una matriz dispersa.A

codifica las desigualdades linealesAM

,A*x <= b

donde está el vector de columna de variables, y es un vector de columna con elementos.xNx(:)bM

Por ejemplo, para especificar

x1 + 2x2 ≤ 10 3
x1 + 4x2 ≤ 20 5
x1 + 6x2 ≤ 30,

dar estas restricciones:

A = [1,2;3,4;5,6]; b = [10;20;30];

Ejemplo: Para especificar que los componentes x suman 1 o menos, tome yA = ones(1,N)b = 1

Tipos de datos: double

Restricciones de igualdad lineales, especificadas como una matriz real. es un-por-matriz, donde es el número de ecualidades, y es el número de variables (longitud de).AeqMeNMeNf Para problemas grandes, pase como una matriz dispersa.Aeq

codifica las equalidades linealesAeqMe

,Aeq*x = beq

donde está el vector de columna de variables, y es un vector de columna con elementos.xNx(:)beqMe

Por ejemplo, para especificar

x1 + 2x2 + 3x3 = 10 2
x1 + 4x2 +x3 = 20,

dar estas restricciones:

Aeq = [1,2,3;2,4,1]; beq = [10;20];

Ejemplo: Para especificar que los componentes x suman 1, tome yAeq = ones(1,N)beq = 1

Tipos de datos: double

Restricciones de desigualdad lineales, especificadas como un vector real. es un vector de elemento relacionado con la matriz.bMA Si se pasa como un vector de fila, los solucionadores se convierten internamente al vector de columna.bbb(:) Para problemas grandes, pase como un vector disperso.b

codifica las desigualdades linealesbM

,A*x <= b

donde está el vector de columna de variables, y es una matriz de tamaño por.xNx(:)AMN

Por ejemplo, para especificar

x1 + 2x2 ≤ 10 3
x1 + 4x2 ≤ 20 5
x1 + 6x2 ≤ 30,

Ingrese estas restricciones:

A = [1,2;3,4;5,6]; b = [10;20;30];

Ejemplo: Para especificar que los componentes x suman 1 o menos, utilice y.A = ones(1,N)b = 1

Tipos de datos: double

Restricciones de igualdad lineales, especificadas como un vector real. es un vector de elemento relacionado con la matriz.beqMeAeq Si se pasa como un vector de fila, los solucionadores se convierten internamente al vector de columna.beqbeqbeq(:) Para problemas grandes, pase como un vector disperso.beq

codifica las equalidades linealesbeqMe

,Aeq*x = beq

donde está el vector de columna de variables, y es una matriz de tamaño por.xNx(:)AeqMeN

Por ejemplo, para especificar

x1 + 2x2 + 3x3 = 10 2
x1 + 4x2 +x3 = 20,

Ingrese estas restricciones:

Aeq = [1,2,3;2,4,1]; beq = [10;20];

Ejemplo: Para especificar que los componentes x suman 1, utilice y.Aeq = ones(1,N)beq = 1

Tipos de datos: double

Límites inferiores, especificados como un vector real o una matriz real. Si la longitud de es igual a la de, a continuación, especifica queflblb

para todos.x(i) >= lb(i)i

Si, a continuación, especifica quenumel(lb) < numel(f)lb

Para.x(i) >= lb(i)1 <= i <= numel(lb)

En este caso, los solucionadores emiten una advertencia.

Ejemplo: Para especificar que todos los componentes x son positivos,lb = zeros(size(f))

Tipos de datos: double

Límites superiores, especificados como un vector real o una matriz real. Si la longitud de es igual a la de, a continuación, especifica quefubub

para todos.x(i) <= ub(i)i

Si, a continuación, especifica quenumel(ub) < numel(f)ub

Para.x(i) <= ub(i)1 <= i <= numel(ub)

En este caso, los solucionadores emiten una advertencia.

Ejemplo: Para especificar que todos los componentes x son menores que uno,ub = ones(size(f))

Tipos de datos: double

Opciones de optimización, especificadas como la salida de o una estructura como devoluciones.optimoptionsoptimset

Algunas opciones se aplican a todos los algoritmos, y otras son relevantes para determinados algoritmos. Consulte para obtener información detallada.Opciones de optimización referencia

Algunas opciones están ausentes en la pantalla.optimoptions Estas opciones aparecen en cursiva en la tabla siguiente. Para obtener más información, consulte.Ver opciones

All Algorithms
Algorithm

Elija el algoritmo de optimización:

  • predeterminado'dual-simplex'

  • 'interior-point-legacy'

  • 'interior-point'

Para obtener información sobre cómo elegir el algoritmo, consulte.Algoritmos de programación lineal

Diagnostics

Mostrar información de diagnóstico sobre la función que se debe minimizar o resolver. Elija (predeterminado) o.'off''on'

Display

Nivel de visualización (ver):Visualización iterativa

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

  • o no muestra ninguna salida.'off''none'

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

MaxIterations

Número máximo de iteraciones permitidas, un entero positivo. El valor predeterminado es:

  • para el algoritmo85'interior-point-legacy'

  • para el algoritmo200'interior-point'

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

Mira y.Tolerancias y criterios de detenciónIteraciones y recuentos de funciones

El nombre es.optimsetMaxIter Ver.Las tablas de nombres de opciones actuales y heredadas

OptimalityTolerance

Tolerancia de terminación en la viabilidad dual, un escalar positivo. El valor predeterminado es:

  • para el algoritmo1e-8'interior-point-legacy'

  • para el algoritmo1e-7'dual-simplex'

  • para el algoritmo1e-6'interior-point'

El nombre es.optimsetTolFun Ver.Las tablas de nombres de opciones actuales y heredadas

interior-point Algorithm
ConstraintTolerance

Tolerancia de viabilidad para las restricciones, un escalar desde. mide la tolerancia de viabilidad primaria.1e-101e-3ConstraintTolerance El valor predeterminado es.1e-6

El nombre es.optimsetTolCon Ver.Las tablas de nombres de opciones actuales y heredadas

Preprocess

Nivel de preprocesamiento de LP antes de las iteraciones del algoritmo. Especifique (valor predeterminado) o.'basic''none'

Algoritmo dual-simplex
ConstraintTolerance

Tolerancia de viabilidad para las restricciones, un escalar desde. mide la tolerancia de viabilidad primaria.1e-101e-3ConstraintTolerance El valor predeterminado es.1e-4

El nombre es.optimsetTolCon Ver.Las tablas de nombres de opciones actuales y heredadas

MaxTime

Cantidad máxima de tiempo en segundos que se ejecuta el algoritmo. El valor predeterminado es.Inf

Preprocess

Nivel de preprocesamiento LP antes de iteraciones duales del algoritmo simplex. Especifique (valor predeterminado) o.'basic''none'

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

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

Nombre de campoEntrada

f

Vector de función objetivo linealf

Aineq

Matriz para las restricciones de desigualdad lineal

bineq

Vector para las restricciones de desigualdad lineal

Aeq

Matriz para las restricciones de igualdad lineal

beq

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

solver

'linprog'

Opciones

Las opciones creadas conoptimoptions

Debe suministrar al menos el campo en la estructura.solverproblem

La forma más sencilla de obtener una estructura es exportar el problema desde la aplicación de optimización.problem

Tipos de datos: struct

Argumentos de salida

contraer todo

Solución, devuelta como un vector real o una matriz real. El tamaño de es el mismo que el tamaño de.xf

Valor de la función objetiva en la solución, devuelto como un número real. Generalmente, =.fvalf'*x

Motivo detenido, devuelto como un entero.linprog

3

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

1

Función convergida a una solución.x

0

Número de iteraciones superada o tiempo de solución en segundos excedido.options.MaxIterationsoptions.MaxTime

-2

No se encontró ningún punto factible.

-3

El problema es ilimitado.

-4

valor se encontró durante la ejecución del algoritmo.NaN

-5

Tanto los problemas primarios como los duales son inviables.

-7

La dirección de búsqueda se hizo demasiado pequeña. No se podrían hacer más progresos.

-9

Solver perdió viabilidad.

Exitflags y se relacionan con soluciones que tienen grandes inbilidades.3-9 Estos suelen surgir de matrices de restricciones lineales que tienen un número de condición grande, o problemas que tienen grandes componentes de la solución. Para corregir estos problemas, intente escalar las matrices de coeficiente, elimine las restricciones lineales redundantes o dé límites más estrictos a las variables.

Información sobre el proceso de optimización, devuelta como una estructura con estos campos.

iterations

Número de iteraciones

algorithm

Algoritmo de optimización utilizado

cgiterations

0 (solo algoritmo de punto interior, incluido para compatibilidad con versiones anteriores)

message

Mensaje de salida

constrviolation

Máximo de funciones de restricción

firstorderopt

Medida de optimalidad de primer orden

Los multiplicadores de Lagrange en la solución, devueltos como una estructura con estos campos.

lower

Los límites inferiores corresponden alb

upper

Los límites superiores corresponden aub

ineqlin

Las desigualdades lineales correspondientes yAb

eqlin

Ecualidades lineales correspondientes a yAeqbeq

Algoritmos

contraer todo

Algoritmo dual-simplex

Para obtener una descripción, consulte.Algoritmo dual-simplex

El algoritmo de punto interior-heredado

El método se basa en LIPSOL (linear interior Point Solver,), que es una variante del algoritmo de corrector de predictores de Mehrotra, un método de punto interior doble primitivo.'interior-point-legacy'[3][2] Se producen varios pasos de preprocesamiento antes de que el algoritmo empiece a iterar. Ver.Programación lineal de punto interior heredado

La primera fase del algoritmo puede implicar algún preprocesamiento de las restricciones (consulte).Programación lineal de punto interior heredado Varias condiciones pueden causar salir con un mensaje de infactibilidad.linprog En cada caso, devuelve un valor negativo, indicando que indica un error.linprogexitflag

  • Si una fila de todos los ceros se detecta en, pero el elemento correspondiente de no es cero, a continuación, el mensaje de salida esAeqbeq

    Exiting due to infeasibility: An all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry.
  • Si uno de los elementos de se encuentra que no se limita a continuación, el mensaje de salida esx

    Exiting due to infeasibility: Objective f'*x is unbounded below.
  • Si una de las filas tiene solo un elemento distinto de cero, el valor asociado en se denomina variable.Aeqxsingleton En este caso, se puede calcular el valor de ese componente de y.xAeqbeq Si el valor calculado infringe otra restricción, el mensaje de salida se

    Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.
  • Si se puede resolver la variable singleton, pero la solución infringe los límites superior o inferior, el mensaje de salida se

    Exiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.

Nota

Los pasos de preprocesamiento son acumulativos. Por ejemplo, incluso si la matriz de restricciones no tiene una fila de todos los ceros para empezar, otros pasos de preprocesamiento pueden provocar que se produzca dicha fila.

Cuando finaliza el preprocesamiento, la parte iterativa del algoritmo comienza hasta que se cumplen los criterios de detención. (Para obtener más información sobre los residuos, el problema primario, el problema dual y los criterios de detención relacionados, consulte.)Programación lineal de punto interior heredado Si los residuos están creciendo en lugar de ser más pequeños, o los residuales no están creciendo ni encogiendo, uno de los dos siguientes mensajes de terminación se muestra, respectivamente,

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 muestre uno de estos mensajes, es seguido por uno de los siguientes mensajes que indican que el dual, el primitivo, o ambos parecen ser inviables.

  • 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 primario (objetivo) puede ser ilimitado y el residuo primigenio, que es una medida de la satisfacción de las restricciones primarias, puede ser pequeño.

Algoritmo de punto interior

El algoritmo es similar, pero con una rutina de factorización más eficiente, y con un preprocesamiento diferente.'interior-point''interior-point-legacy' Ver.Algoritmo de punto interiorlinprog

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.

Introducido antes de R2006a