linprog: solve linear programming problems.

常用的syntax:

x = linprog(f,A,b)

x = linprog(f,A,b,Aeq,beq)

x = linprog(f,A,b,Aeq,beq,lb,ub)

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

x = linprog(problem)

[x,fval] = linprog(___)

[x,fval,exitflag,output] = linprog(___)

[x,fval,exitflag,output,lambda] = linprog(___)

Description

Linear programming solverFinds the minimum of a problem specified by

min_{x}=f^Tx such that { A⋅x≤b, Aeq⋅x=beq, lb≤x≤ub.f, x, b, beq, lb, and ub are vectors, and A and Aeq are matrices.

同時註釋note：linprogapplies only to the solver-based approach. For a discussion of the two optimization approaches, see

1.x= linprog(f,A,b) solves min f'*x such that A*x ≤ b.

2.x= linprog(f,A,b,Aeq,beq) includes equality constraints.

Aeq*x = beq

Set A = [] and b = [] if no inequalities exist.

3.x = linprog(f,A,b,Aeq,beq,lb,ub)

defines a set of lower and upper bounds on the design variables, x, so that the solution is always in the range lb ≤ x ≤ ub.

Set Aeq = [] and beq = [] if no equalities exist.

同時需要指出的是：

If the specified input bounds for a problem are inconsistent, the outputfvalis[].

4.x = linprog(f,A,b,Aeq,beq,lb,ub,options)

minimizes with the optimization options specified by options. Use optimoptions to set these options.5.x = linprog(problem) finds the minimum for problem, a structure described in problem.You can import a problem structure from an MPS file using mpsread. You can also create a problem structure from an OptimizationProblem object by using prob2struct.6.[x,fval] = linprog(___), for any input arguments, returns the value of the objective function fun at the solution x: fval = f'*x.7.[x,fval,exitflag,output] = linprog(___) additionally returns a value exitflag that describes the exit condition, and a structure output that contains information about the optimization process.8.[x,fval,exitflag,output,lambda] = linprog(___) additionally returns a structure lambda whose fields contain the Lagrange multipliers at the solution x.

相關的example:

Linear Program, Linear Inequality ConstraintsSolve a simple linear program defined by linear inequalities.For this example, use these linear inequality constraints:x(1)+x(2)≤2x(1)+x(2)/4≤1x(1)−x(2)≤2−x(1)/4−x(2)≤1−x(1)−x(2)≤−1−x(1)+x(2)≤2.寫成matrix形式：

A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1];

b = [2 1 2 1 -1 2];Use the objective function：

−x(1)−x(2)/3.

相應的寫成矢量矩陣形式：f = [-1 -1/3];

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

0.6667

1.3333

Linear Program with Linear Inequalities and EqualitiesSolve a simple linear program defined by linear inequalities and linear equalities.For this example, use these linear inequality constraints:x(1)+x(2)≤2x(1)+x(2)/4≤1x(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];

Use the linear equality constraint x(1)+x(2)/4=1/2.Aeq = [1 1/4]; beq = 1/2;Use the objective function −x(1)−x(2)/3.

相應的f寫成矩陣形式：f = [-1 -1/3];Solve the linear program.x = linprog(f,A,b,Aeq,beq)Optimal solution found. x = 2×1

0

2

Linear Program with All Constraint TypesSolve a simple linear program with linear inequalities, linear equalities, and bounds.For this example, use these linear inequality constraints:x(1)+x(2)≤2x(1)+x(2)/4≤1x(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];

Use the linear equality constraint：

x(1)+x(2)/4=1/2.

用矩陣表示出來：Aeq = [1 1/4]; beq = 1/2;Set these bounds:−1≤x(1)≤1.5−0.5≤x(2)≤1.25.用矩陣或則矢量的形式表示：lb = [-1,-0.5];

ub = [1.5,1.25];

同時相應的目標函數是：Use the objective function −x(1)−x(2)/3.f = [-1 -1/3];Solve the linear program.x = linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found. x = 2×1

0.1875

1.2500 Linear Program Using the 'interior-point' AlgorithmSolve a linear program using the 'interior-point' algorithm.For this example, use these linear inequality constraints:x(1)+x(2)≤2x(1)+x(2)/4≤1x(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];Use the linear equality constraint x(1)+x(2)/4=1/2.

表示成矩陣形式就是：Aeq = [1 1/4]; beq = 1/2;Set these bounds:−1≤x(1)≤1.5−0.5≤x(2)≤1.25.lb = [-1,-0.5]; ub = [1.5,1.25];Use the objective function：−x(1)−x(2)/3.f = [-1 -1/3];

同時要註意要設置算法選擇就是：Set options to use the 'interior-point' algorithm.options = optimoptions('linprog','Algorithm','interior-point');Solve the linear program using the 'interior-point' algorithm.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

Solve LP Using Problem-Based Approach for linprogThis example shows how to set up a problem using the problem-based approach and then solve it using the solver-based approach. The problem is :

max_{x}=x(x+y/3) subject to

x+y≤2

x+y/4≤1

x−y≤2

x/4+y≥−1

x+y≥1

−x+y≤2

x+y/4=1/2

−1≤x≤1.5

−1/2≤y≤1.25Create an OptimizationProblem object named prob to represent this problem.x = optimvar('x','LowerBound',-1,'UpperBound',1.5); %Create optimization variables

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;

Convert the problem object to a problem structure.problem = prob2struct(prob);

Solve the resulting problem structure.[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 The returned fval is negative, even though the solution components are positive. Internally, prob2struct turns the maximization problem into a minimization problem of the negative of the objective function. See

Which component of sol corresponds to which optimization variable?

Examine the Variables property of prob.prob.Variablesans = struct with fields:

x: [1×1 optim.problemdef.OptimizationVariable]

y: [1×1 optim.problemdef.OptimizationVariable] As you might expect, sol(1) corresponds to x, and sol(2) corresponds to y. See Algorithms.

Return the Objective Function ValueCalculate the solution and objective function value for a simple linear program.The inequality constraints are：x(1)+x(2)≤2x(1)+x(2)/4≤1x(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];The objective function is −x(1)−x(2)/3.

相應的矩陣函數是：f = [-1 -1/3];Solve the problem and return the objective function value.[x,fval] = linprog(f,A,b)Optimal solution found. x = 2×1

0.6667

1.3333 fval = -1.1111

Obtain More Output to Examine the Solution ProcessObtain the exit flag and output structure to better understand the solution process and quality.For this example, use these linear inequality constraints:x(1)+x(2)≤2x(1)+x(2)/4≤1x(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];Use the linear equality constraint：x(1)+x(2)/4=1/2.Aeq = [1 1/4]; beq = 1/2;Set these bounds:−1≤x(1)≤1.5−0.5≤x(2)≤1.25.向量表示：lb = [-1,-0.5];

ub = [1.5,1.25];Use the objective function：−x(1)−x(2)/3.f = [-1 -1/3];Set options to use the 'dual-simplex' algorithm.

設置求解算法：options = optimoptions('linprog','Algorithm','dual-simplex');Solve the linear program and request the function value, exit flag, and output structure.[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

• fval, the objective function value, is larger than Return the Objective Function Value, because there are more constraints.
• exitflag = 1 indicates that the solution is reliable.
• output.iterations = 0 indicates that linprog found the solution during presolve, and did not have to iterate at all.

Obtain Solution and Lagrange MultipliersSolve a simple linear program and examine the solution and the Lagrange multipliers.Use the objective functionf(x)=−5x1−4x2−6x3.相應的函數向量：f = [-5; -4; -6];Use the linear inequality constraints：x1−x2+x3≤203x1+2x2+4x3≤423x1+2x2≤30.

變換成向量矩陣形式：A = [1 -1 1 3 2 4 3 2 0];

b = [20;42;30];Constrain all variables to be positive:x1≥0x2≥0x3≥0.給出下限的向量表示：lb = zeros(3,1);Set Aeq and beq to [], indicating that there are no linear equality constraints.Aeq = []; beq = [];

Call linprog, obtaining the Lagrange multipliers.

註意下面調用這個函數的時候，隻是給出瞭varaible的下限。[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb);Optimal solution found. Examine the solution and Lagrange multipliers.x,lambda.ineqlin,lambda.lowerx = 3×1

0

15.0000

3.0000

ans = 3×1

0

1.5000

0.5000

ans = 3×1

1.0000

0

0 lambda.ineqlin is nonzero for the second and third components of x. This indicates that the second and third linear inequality constraints are satisfied with equalities:3x1+2x2+4x3=423x1+2x2=30.Check that this is true:A*xans = 3×1 -12.0000 42.0000 30.0000 lambda.lower is nonzero for the first component of x. This indicates that x(1) is at its lower bound of 0.

相應的algorithms:

1. dual-simplex algorithm
2. interior-point-legacy algorithm
3. interior-point algorithm

• 相關的參數說明

輸入參數f – 系數向量實數向量 | 實數數組系數向量，指定為實數向量或實數數組。系數向量表示目標函數 f'*x。該表示法假設 f 是列向量，但您也可以使用行向量或數組。linprog 在內部將 f 轉換為列向量 f(:)。示例： f = [1,3,5,-6]數據類型： double

A – 線性不等式約束實矩陣

線性不等式約束，指定為實矩陣。A 是 M×N 矩陣，其中 M 是不等式的數目，而 N 是變量的數目（f 的長度）。對於大型問題，將 A 作為稀疏矩陣傳遞。A 以如下形式編寫 M 個線性不等式A*x <= b，其中，x 是由 N 個變量組成的列向量 x(:)，b 是具有 M 個元素的列向量。例如，假設有以下不等式：x1 + 2×2 ≤ 103×1 + 4×2 ≤ 205×1 + 6×2 ≤ 30。通過輸入以下約束來指定不等式。A = [1,2;3,4;5,6]; b = [10;20;30];示例： 要指定 x 的各個分量加起來等於或小於 1，請指定 A = ones(1,N) 和 b = 1。數據類型： double

Aeq – 線性等式約束實矩陣

線性等式約束，指定為實矩陣。Aeq 是 Me×N 矩陣，其中 Me 是等式的數目，而 N 是變量的數目（f 的長度）。對於大型問題，將 Aeq 作為稀疏矩陣傳遞。Aeq 以如下形式編寫 Me 個線性等式Aeq*x = beq，其中，x 是由 N 個變量組成的列向量 x(:)，beq 是具有 Me 個元素的列向量。例如，請參考以下等式：x1 + 2×2 + 3×3 = 102×1 + 4×2 + x3 = 20。通過輸入以下約束來指定等式。Aeq = [1,2,3;2,4,1]; beq = [10;20];示例： 要指定 x 分量之和為 1，請指定 Aeq = ones(1,N) 和 beq = 1。數據類型： double

b – 線性不等式約束實數向量

線性不等式約束，指定為實數向量。b 是與 A 矩陣相關的包含 M 個元素的向量。如果將 b 作為行向量傳遞，求解器會在內部將 b 轉換為列向量 b(:)。對於大型問題，將 b 作為稀疏向量傳遞。b 以如下形式編寫 M 個線性不等式A*x <= b，其中，x 是由 N 個變量組成的列向量 x(:)，A 是大小為 M×N 的矩陣。例如，假設有以下不等式：x1 + 2×2 ≤ 103×1 + 4×2 ≤ 205×1 + 6×2 ≤ 30。通過輸入以下約束來指定不等式。A = [1,2;3,4;5,6]; b = [10;20;30];示例： 要指定 x 分量總和等於或小於 1，請使用 A = ones(1,N) 和 b = 1。數據類型： double

beq – 線性等式約束實數向量

線性等式約束，指定為實數向量。beq 是與 Aeq 矩陣相關的包含 Me 個元素的向量。如果將 beq 作為行向量傳遞，求解器會在內部將 beq 轉換為列向量 beq(:)。對於大型問題，將 beq 作為稀疏向量傳遞。beq 以如下形式編寫 Me 個線性等式Aeq*x = beq，其中，x 是由 N 個變量組成的列向量 x(:)，Aeq 是大小為 Me×N 的矩陣。例如，請參考以下等式：x1 + 2×2 + 3×3 = 102×1 + 4×2 + x3 = 20。通過輸入以下約束來指定等式。Aeq = [1,2,3;2,4,1]; beq = [10;20];示例： 要指定 x 分量總和為 1，請使用 Aeq = ones(1,N) 和 beq = 1。數據類型： double

lb – 下界實數向量 | 實數數組

下界，指定為實數向量或實數數組。如果 f 的長度等於 lb 的長度，則 lb 指定x(i) >= lb(i)（對於全部 i）。如果 numel(lb) < numel(f)，則 lb 指定x(i) >= lb(i) (1 <= i <= numel(lb))。在這種情況下，求解器會發出警告。示例： 要指定所有 x 分量都為正，請指定 lb = zeros(size(f))。數據類型： double

ub – 上界實數向量 | 實數數組

上界，指定為實數向量或實數數組。如果 f 的長度等於 ub 的長度，則 ub 指定x(i) <= ub(i)（對於全部 i）。如果 numel(ub) < numel(f)，則 ub 指定x(i) <= ub(i) (1 <= i <= numel(ub))。在這種情況下，求解器會發出警告。示例： 要指定所有 x 分量都小於 1，請使用 ub = ones(size(f))。數據類型： double

options – 優化選項optimoptions 的輸出 | optimset 返回的結構體

優化選項，指定為 optimoptions 的輸出或 optimset 返回的結構體。一些選項適用於所有算法，其他選項則與特定算法相關。有關詳細信息，請參閱優化選項參考。optimoptions 顯示中缺少某些選項。這些選項在下表中以斜體顯示。有關詳細信息，請參閱查看選項。

problem – 問題結構體結構體

問題結構體，指定為含有以下字段的結構體。

輸出參數

x – 解實數向量 | 實數數組

解，以實數向量或實數數組形式返回。x 的大小與 f 的大小相同。

fval – 解處的目標函數值實數

解處的目標函數值，以實數形式返回。通常，fval = f'*x。

exitflag – linprog 停止的原因整數

linprog 停止的原因，以整數形式返回。

退出標志 3 和 -9 與不可行性較大的解相關。此類問題通常源於具有較大條件數的線性約束矩陣，或源於具有較大解分量的問題。要糾正這些問題，請嘗試縮放系數矩陣，消除冗餘線性約束，或對變量給出更嚴格的邊界。

output – 有關優化過程的信息結構體

有關優化過程的信息，以包含下列字段的結構體形式返回。

lambda – 解處的拉格朗日乘數結構體

解處的拉格朗日乘數，以包含下列字段的結構體形式返回。

線性約束的拉格朗日乘數滿足以下具有 length(f) 個分量的方程：f+ATλineqlin +AeqTλeqlin+λupper−λlower=0,基於拉格朗日函數fTx+λTineqlin(Ax−b) +λTeqlin(Aeq x−beq)+λTupper(x−ub)+λTlower(lb−x).此符號約定與非線性求解器的符號約定一致（請參閱受約束的最優性理論）。然而，此符號與許多線性規劃文獻中的符號相反，因此 linprog 拉格朗日乘數是關聯的“影子價格”的負數。

算法：對偶單純形算法有關說明，請參閱對偶單純形算法

內點傳統算法'interior-point-legacy' 方法基於 LIPSOL（線性內點求解器，[3]），它是 Mehrotra 預測-校正算法 [2]（一種原始-對偶內點方法）的變體。在算法開始迭代之前，您需要采取許多預處理步驟。請參閱內點傳統線性規劃。算法的第一階段可能涉及約束的一些預處理（請參閱內點傳統線性規劃）。一些情況可能會導致 linprog 退出，並顯示不可行性消息。在每種情況下，linprog 都返回一個負值 exitflag，表示失敗。

• 如果在 Aeq 中檢測到一行全部為零，但 beq 的對應元素不為零，則退出消息為Exiting due to infeasibility: An all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry.
• 如果發現 x 的元素之一無下界，則退出消息為Exiting due to infeasibility: Objective f'*x is unbounded below.
• 如果 Aeq 的某一行隻有一個非零元素，則 x 中與之對應的值稱為單值變量。在這種情況下，可以根據 Aeq 和 beq 計算 x 的該分量的值。如果計算的值違反另一個約束，則退出消息為Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.
• 如果單值變量可以得到求解，但該解違反上界或下界，則退出消息為Exiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.註意預處理步驟是累積的。例如，即使約束矩陣一開始沒有全部為零的行，其他預處理步驟也可能導致出現這樣的行。預處理完成後，算法的迭代部分開始執行，直到滿足終止條件。（有關殘差、原始問題、對偶問題和相關終止條件的詳細信息，請參閱內點傳統線性規劃。）如果殘差在增大而不是減小，或殘差既不增大也不減小，則對應顯示以下兩條終止消息之一，One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far:或One or more of the residuals, duality gap, or total relative error has stalled:顯示上述消息後，還將顯示以下消息之一，表明對偶問題、原始問題或兩者似乎都不可行。
• 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.例如，原始（目標）可以無界，原始殘差（用於度量原始約束的滿足程度）可以很小。

內點算法'interior-point' 算法類似於 'interior-point-legacy'，但具有更高效的分解例程和不同的預處理。請參閱內點 linprog 算法。