典型的线性规划问题

打开实时脚本

此示例说明如何求解典型的线性规划问题

minxfTxsuchthat{A⋅x≤b,Aeq⋅x=beq,x≥0.

加载 sc50b.mat 文件，该文件在运行此示例时可用，它包含矩阵和向量 A、Aeq、b、beq、f 以及下界 lb。

load sc50b

该问题有 48 个变量、30 个不等式和 20 个等式。

disp(size(A))
    30    48

disp(size(Aeq))
    20    48

设置选项以使用 dual-simplex 算法和迭代输出。

options = optimoptions(@linprog,Algorithm="dual-simplex",Display="iter");

该问题没有上界，因此将 ub 设置为 []。

ub = [];

通过调用 linprog 求解问题。

[x,fval,exitflag,output] = ...
    linprog(f,A,b,Aeq,beq,lb,ub,options);
Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
LP   has 50 rows; 48 cols; 118 nonzeros
Coefficient ranges:
  Matrix [3e-01, 3e+00]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [3e+02, 3e+02]
Presolving model
37 rows, 37 cols, 93 nonzeros  0s
21 rows, 21 cols, 63 nonzeros  0s
16 rows, 16 cols, 58 nonzeros  0s
Dependent equations search running on 2 equations with time limit of 1000.00s
Dependent equations search removed 0 rows and 0 nonzeros in 0.00s (limit = 1000.00s)
14 rows, 14 cols, 63 nonzeros  0s
Presolve : Reductions: rows 14(-36); columns 14(-34); elements 63(-55)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -8.6188182450e-01 Ph1: 10(13.6343); Du: 1(0.861882) 0s
         17    -7.0000000000e+01 Pr: 0(0) 0s
Solving the original LP from the solution after postsolve
Model status        : Optimal
Simplex   iterations: 17
Objective value     : -7.0000000000e+01
P-D objective error :  0.0000000000e+00
HiGHS run time      :          0.00

Optimal solution found.

检查退出标志、解处的目标函数值以及 linprog 用于求解问题的迭代次数。

exitflag,fval,output.iterations
exitflag = 
1

fval = 
-70.0000

ans = 
17

您还可以在迭代输出中找到目标函数值和迭代次数。